Implement compute-optimised Merkle tree

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

Implement compute-optimised Merkle tree #5

Closed musalbas closed 4 years ago

musalbas commented 4 years ago

WIP

With whitespaces changes hidden: https://github.com/lazyledger/smt/pull/5/files?diff=unified&w=1

musalbas commented 4 years ago

The entire optimised tree is now implemented and tests pass. TODOs:

[x] Add more comprehensive tests for proof verification.
[x] Double check proof input sanity checks.
[x] Double check what happens to a non-compacted / compacted proof in the case of a single element / no element in the tree.
[x] Clean up variable naming (leaf data vs leaf data hash etc) - especially in DeepSparseMerkleSubTree.AddBranches.
[x] Investigate/enforce constaint for DeepSparseMerkleSubTree.AddBranches to take as input a non-compacted proof.
[x] Add issue/fix for optimising Prover so that the leaf doesn't have to be gotten twice from the MapStore via ms.Get().
[x] Add test for smt.Get when path is 256 bits long.
[x] Ensure DeepSparseMerkleSubTree works for adding new keys and improve tests.

musalbas commented 4 years ago

This looks like great work! Do you plan to wrap up the outstanding todos (#5 (comment)) before merging?

On a sidenote we might consider fuzzing to ensure we aren't missing some weird edge cases.

Yes, I still intend to wrap up the remaining TODOs before it's ready to be merged.

I may add some lite fuzzing or random proofs for the proof verifier testing.

musalbas commented 4 years ago

TODO: investigate why this case is not being hit by test. https://coveralls.io/builds/32535000/source?filename=proofs.go#L80

Edit: done.

liamsi commented 4 years ago

It's probably a good idea to run sth like golangci-lint run locally or in CI, too (will likely not help with the above problem though).

musalbas commented 4 years ago

Looks like the DeepSparseMerkleSubTree.AddBranches needs to be reimplemented and cannot simply call the updateWithSideNodes function in an optimised tree, as this does more than simply add branches from the proof.

musalbas commented 4 years ago

I think this is ready to be merged.

musalbas commented 4 years ago

Speedtest to update 10,000 keys in a fresh tree: Before optimisations: 0m3.355s After optimisations: 0m0.327s

This confers to up to a ~10x speed-up.

musalbas commented 4 years ago

Ok, I'm going to split compact proofs to a different type.

musalbas commented 4 years ago

Done