Nimbus Verkle Tree implementation (WIP)

This repo will contain an implementation of Verkle trees, in the Nim programming language, to be integrated into the Nimbus project when the implementation matures.

TODO

Banderwagon commitments

• [X] Implement the logic by making use of IPA Multipoint / Banderwagon / blst
• [ ] Create tests focusing on the integration between the high-level Nim code and libraries, e.g. big/little endian issues

Verkle tree implementation

• [X] Implement the Verkle tree structure, with basic operations (e.g. adding nodes)
• [X] Support computation of commitments / proofs. Possibly, cache them in the tree.
• [X] Support tree mutation with minimal recomputation of commitments
• [ ] Create tests, focusing on edge cases (empty tree, sparse tree, dense tree, consistency after mutations). Possibly use fuzzing with deterministic random, as done in rust-verkle.
• [ ] Create comparative tests between the various Verkle implementations; given an identical tree, identical commitments are expected The compatibility/ folder contains git submodules of other verkle implementations, extended with compatibility tests. See: compatibility/go-verkle/compatibility.result compatibility/rust-verkle/verkle-trie/tests/compatibility.result

Performance

• [ ] Analyze how Nimbus accesses the Merkle tree
• [ ] Optimize the most common access patterns in the equivalent Verkle tree
• [ ] Evaluate whether parallelism can be leveraged