search

arkworks-rs / crypto-primitives

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

Parallelize the Merkle tree implementation #122

Closed WizardOfMenlo closed 8 months ago

WizardOfMenlo commented 10 months ago

It would be nice if we could enable parallelization of the Merkle trees (more specifically, the commitment phase). In a few projects I am working on the Merkle tree portion accounts for a majority of the runtime, and it seems like an obvious target for parallelization.

Ideally, we would gate this behind a feature flag (as it is done for parallel FFTs in algebra).

The parallelization is slightly non-trivial (naively, we would probably choose a layer k, compute the 2^k subtrees at that layer in parallel, and then compute the remaining smaller Merkle tree), but should be relatively doable. Not sure if there are more clever ways to do this.

burdges commented 10 months ago

Afaik you cannot use this Merkle tree for much anyways, given how it handles empty leaves. It's maybe not that hard to change it to work in an MMR though.

WizardOfMenlo commented 10 months ago

What's the problem with empty leaves? In my application this is not really an issue, but if you could open an issue describing how it could be improved it would be great!