Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat: add binary trie #129

Merged
merged 19 commits into from
May 17, 2022
Merged

feat: add binary trie #129

merged 19 commits into from
May 17, 2022

Conversation

tshakalekholoane
Copy link
Contributor

@tshakalekholoane tshakalekholoane commented Apr 8, 2022

trie diagram

Trie representation versus the example in the StarkNet documentation for 3-bit keys.

  • Add encoding and hashes.
  • Integrate data store.
  • Add Delete method.
  • Extend to arbitrary sized keys.
  • Add proof verification.

Changes:

  • Add the binary Merkle-Patricia trie used in the StarkNet protocol.

Types of changes

  • New feature (non-breaking change which adds functionality)

Testing

Requires testing

  • Yes
  • No

In case you checked yes, did you write tests??

  • Yes
  • No

Comments about testing , should you have some (optional)

Functional tests:

func main() {
  tests := [...]struct {
    key, val *big.Int
  }{
    {big.NewInt(2) /* 0b010 */, big.NewInt(1)},
    {big.NewInt(5) /* 0b101 */, big.NewInt(1)},
  }
  db := store.New()
  t := trie.New(db, 3)

  // Put.
  for _, test := range tests {
    fmt.Printf("put(key=%d, val=%d)\n", test.key, test.val)
    t.Put(test.key, test.val)
  }

  // Get.
  for _, test := range tests {
    val, _ := t.Get(test.key)
    fmt.Printf("get(key=%d) = %d\n", test.key, val)
  }

  // Delete.
  fmt.Printf("delete(key=%d)\n", tests[0].key)
  t.Delete(tests[0].key)
}

Debug trace:

----------------------------------------
PUT
----------------------------------------
put(key=2, val=1)
------------------
enc = (0, 0, 1)
hash = 1

enc = (1, 0, 1)
hash = 8a95

enc = (2, 2, 1)
hash = 8028

enc = (3, 2, 1)
hash = 8029

put(key=5, val=1)
------------------
enc = (0, 0, 1)
hash = 1

enc = (1, 1, 1)
hash = 8ead

enc = (2, 1, 1)
hash = 8eae

enc = (0, 0, 7ab5)
hash = 7ab5

----------------------------------------
GET
----------------------------------------
get(key=2) = 1
get(key=5) = 1

----------------------------------------
DELETE
----------------------------------------
delete(key=2)

re-enc: (3, 5, 1)
hash = 2f28

@tshakalekholoane tshakalekholoane added the Core Features or changes related to core package label Apr 8, 2022
@tshakalekholoane tshakalekholoane self-assigned this Apr 8, 2022
@tshakalekholoane tshakalekholoane linked an issue Apr 8, 2022 that may be closed by this pull request
@codecov
Copy link

codecov bot commented Apr 8, 2022

Codecov Report

Merging #129 (e665dcd) into main (2240b0e) will not change coverage.
The diff coverage is 100.00%.

@@             Coverage Diff             @@
##              main      #129     +/-   ##
===========================================
  Coverage   100.00%   100.00%             
===========================================
  Files           26        31      +5     
  Lines         1427      3571   +2144     
===========================================
+ Hits          1427      3571   +2144     
Flag Coverage Δ
unittests 100.00% <100.00%> (ø)

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files Coverage Δ
pkg/crypto/pedersen/pedersen.go 100.00% <100.00%> (ø)
pkg/crypto/pedersen/points.go 100.00% <100.00%> (ø)
pkg/store/store.go 100.00% <100.00%> (ø)
pkg/trie/node.go 100.00% <100.00%> (ø)
pkg/trie/trie.go 100.00% <100.00%> (ø)
pkg/trie/utils.go 100.00% <100.00%> (ø)
pkg/crypto/weierstrass/weierstrass.go 100.00% <0.00%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 2240b0e...e665dcd. Read the comment docs.

stdevMac and others added 2 commits April 22, 2022 10:03
This also fixes an issue where deleting certain keys would not result in
an updated commitment value.
Tshaka Eric Lekholoane added 9 commits April 27, 2022 16:11
Cater for the assumption that a key-value pair where the value is zero
implies key deletion.
Simplify the Pedersen hash function by introducing panics for a broken
contract and remove a check for a condition that never evaluates to
true. This not only improves the efficiency of the function but also
simplifies its signature to only return the digest instead of the digest
and an error.

This is made possible by the fact that the condition in the inner loop
of pedersen.go that checks whether the shift point is compared to itself
is never true as `pt2` will only ever the assigned to the points in the
range 2..=505.

The hexadecimal strings that represent the points are also hardcoded in
the init function in order to reduce the memory footprint of the
package along with other redundant global variables.

BREAKING CHANGE: `Digest` and `ArrayDigest` now return a single argument

Any previous calls to these functions should discard their error
handling logic.
Introduce minor performance optimisations aimed at reducing the amount
of time it takes to process a block.

This is done by preferring much more efficient alternatives to some
functions such as:

  - Comparing against the length field of a slice instead of the entire
    slice when querying the root node.
  - Replacing string formatting with appending raw bytes or using
    dedicated type formatting functions for basic types as the latter
    uses reflection and as a result is more costly.
Tshaka Eric Lekholoane added 2 commits May 17, 2022 14:09
Remove the test that checks whether the inputs are in the required
field. This function now panics if that's the case as it is considered
to be a broken contract.
This was linked to issues May 17, 2022
Tshaka Eric Lekholoane added 2 commits May 17, 2022 18:23
Comment out the array digest benchmark which is currently failing.
Add a test for querying the commitment of an empty trie.
@stdevMac stdevMac merged commit ca6026a into main May 17, 2022
@tshakalekholoane tshakalekholoane deleted the core/trie branch May 26, 2022 15:08
IronGauntlets pushed a commit that referenced this pull request Aug 18, 2022
* feat: create binary trie

* refactor: implement delete method

* docs: update documentation

* test: add tests for exported methods

* refactor: substitute recursive put with loop

This also fixes an issue where deleting certain keys would not result in
an updated commitment value.

* test: satisfy code coverage tool

* refactor: minor changes to improve clarity

* fix: fix issue caused by overflow

* test: add test for state commitment

* test: improve test coverage

Cater for the assumption that a key-value pair where the value is zero
implies key deletion.

* fix: fix typo

* fix: fix erroneously reversed keys in trie.Put

* refactor: update the Pedersen hash function

Simplify the Pedersen hash function by introducing panics for a broken
contract and remove a check for a condition that never evaluates to
true. This not only improves the efficiency of the function but also
simplifies its signature to only return the digest instead of the digest
and an error.

This is made possible by the fact that the condition in the inner loop
of pedersen.go that checks whether the shift point is compared to itself
is never true as `pt2` will only ever the assigned to the points in the
range 2..=505.

The hexadecimal strings that represent the points are also hardcoded in
the init function in order to reduce the memory footprint of the
package along with other redundant global variables.

BREAKING CHANGE: `Digest` and `ArrayDigest` now return a single argument

Any previous calls to these functions should discard their error
handling logic.

* refactor: minor optimisations

Introduce minor performance optimisations aimed at reducing the amount
of time it takes to process a block.

This is done by preferring much more efficient alternatives to some
functions such as:

  - Comparing against the length field of a slice instead of the entire
    slice when querying the root node.
  - Replacing string formatting with appending raw bytes or using
    dedicated type formatting functions for basic types as the latter
    uses reflection and as a result is more costly.

* tests: delete Pedersen hash limit test

Remove the test that checks whether the inputs are in the required
field. This function now panics if that's the case as it is considered
to be a broken contract.

* tests: comment out array digest benchmark

Comment out the array digest benchmark which is currently failing.

* tests: satisfy coverage tool

Add a test for querying the commitment of an empty trie.

Co-authored-by: Marcos Antonio Maceo <35319980+stdevMac@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Core Features or changes related to core package
Projects
None yet
Development

Successfully merging this pull request may close these issues.

State Commitment Add StarkWare Merkle Patricia Trie
2 participants