search

celestiaorg / smt

A Go library that implements a Sparse Merkle tree for a key-value map.
https://godoc.org/github.com/celestiaorg/smt
MIT License
138 stars 53 forks source link

Fix proof direction and key bit order #22

Closed adlerjohn closed 3 years ago

adlerjohn commented 3 years ago

Fixes #20 and conforms to https://github.com/lazyledger/lazyledger-specs/pull/129.

adlerjohn commented 3 years ago

Looks like everything works as of c5a394b except for deletions. Looking into it now.

Edit: deleteWithSideNodes is actually incorrect, filed #25.

musalbas commented 3 years ago

Can we perhaps add tests to ensure that the keys are added with the correct key bit order?

adlerjohn commented 3 years ago

Can we perhaps add tests to ensure that the keys are added with the correct key bit order?

Sure, but how specifically would we test for that? I guess we could add two leaves that are one bit apart and the proof needs to be 256 side nodes?

musalbas commented 3 years ago

You could generate some trees, and compare it to the expected trees according to the spec.

adlerjohn commented 3 years ago

@musalbas Updated the max depth test to manipulate the LSB directly instead of going through a function in 4c9f680.

musalbas commented 3 years ago

How does that ensure that the keys are added with the correct key bit order?

adlerjohn commented 3 years ago

How does that ensure that the keys are added with the correct key bit order?

It adds a check at the end that the proof is 256 nodes. If traversal isn't done in the correct bit order, the proof would be 256-8 = 248 nodes (maybe off-by-one, but you get the idea).