arkworks-rs / crypto-primitives

Interfaces and implementations of cryptographic primitives, along with R1CS constraints for them
https://www.arkworks.rs
Apache License 2.0
167 stars 79 forks source link

Incremental Merkle Tree Implementation #72

Open stechu opened 3 years ago

stechu commented 3 years ago

Description

This PR implements an incremental merkle tree data structure. This is an append only merkle tree that only maintains Log N internal nodes. An invariant this implementation tries to maintain is that all operations is Log N.

closes: #69


Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

tsunrise commented 3 years ago

advertisement: You may also check if ark-sponge to see if that crate is also helpful for your application

stechu commented 3 years ago

Since @daira's concern about the inner node empty value is not specific to this PR. Please let me know whether I should address her concern in this PR or not. @tsunrise @weikengchen @Pratyush