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

Incremental Merkle Tree #69

Open
stechu opened this issue Aug 18, 2021 · 1 comment · May be fixed by #72
Open

Incremental Merkle Tree #69

stechu opened this issue Aug 18, 2021 · 1 comment · May be fixed by #72
Labels
D-medium Difficulty: medium T-feature Type: new features

Comments

@stechu
Copy link
Contributor

stechu commented Aug 18, 2021

As we are building manta (https://github.com/Manta-Network), we figured out that we need an incremental merkle tree that has Log N internal nodes, which is not supported in the current MerkleTree implementaion. The properties that we need for this merkle tree:

  1. Able to generate ZK membership proofs
  2. The merkle tree can be fixed sized and append only (i.e. mark the unused leaf node as a filler, etc)
  3. The number of internal nodes is Log N. (since we need to store the internal nodes on chain, O(N) storage would be too expensive).
    I think 3 is only possible if this merkle tree only support append. Happy to submit a PR on this. Would also like to hear is there any design considerations that need to take care of during the implementation.
@stechu stechu linked a pull request Aug 23, 2021 that will close this issue
6 tasks
@burdges
Copy link

burdges commented Aug 24, 2021

@Pratyush Pratyush added D-medium Difficulty: medium T-feature Type: new features labels Sep 9, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
D-medium Difficulty: medium T-feature Type: new features
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants