search

Sovereign-Labs / sovereign-sdk

A framework for building seamlessly scalable and interoperable rollups that can run on any blockchain
https://sovereign.xyz
Apache License 2.0
361 stars 104 forks source link

Build a transaction trie from a simple binary Merkle Tree #206

Open citizen-stig opened 1 year ago

citizen-stig commented 1 year ago

Background

Currently, we have good default implementation of a sparse merkle trie (the jmt) which is generic over hash function so that it can run efficiently in any zkvm. But, many implementers will probably want a standard (non-sparse) merkle trie as well.

Desired Outcome

Provide a non-sparse binary merkle trie which is generic over hash function. https://github.com/Sovereign-Labs/nmt-rs/tree/master/src/simple_merkle is a good candidate, but it should be extracted into its own package and tested/audited if we want to use it.

https://github.com/Sovereign-Labs/nmt-rs/tree/master/src/simple_merkle

citizen-stig commented 1 year ago

@preston-evans98 please help groom this issue and populate details about desired outcome

preston-evans98 commented 1 year ago

Background

Currently, we have good default implementation of a sparse merkle trie (the jmt) which is generic over hash function so that it can run efficiently in any zkvm. But, many implementers will probably want a standard (non-sparse) merkle trie as well.

Desired Outcome

Provide a non-sparse binary merkle trie which is generic over hash function. https://github.com/Sovereign-Labs/nmt-rs/tree/master/src/simple_merkle is a good candidate, but it should be extracted into its own package and tested/audited if we want to use it.

preston-evans98 commented 1 year ago

Marking this as low priority since we don't currently have any customers asking for it and we managed to build the demo-rollup without it.