Closed intx4 closed 8 months ago
There is currently a change of semantics between the parallel and non-parallel version. Namely, if one of the hash functions (the leaf hash or the two to one hash) return Err
, the serial version would return it correctly to the caller, while the parallel version would panic. This can be fixed easily enough as long as the error type bound is changed to dyn Error + Send
.
Send
bound for the parallel bound? Or even, can we have ark_std::Error
to require Send
by default?LeafHash, TwoToOneHash
to be allowed to fail? In most use-cases I can think of the hashing should always succeed. I would be in favour to refactor those traits to remove the error path. The conversion traits I can see more usecases, but also wouldn't mind changing the API there as well.@mmagician @Pratyush what are your thoughts?
Rather than duplicating the entire method for the parallel
feature, I would instead try to re-use as much code as possible and only but blocks of code under #[cfg(feature = "parallel")]
and #[cfg(not(feature = "parallel"))]
@mmagician thanks for your feedback, I will address them and get back to you
@mmagician thanks for your feedback, I will address them and get back to you
@mmagician I should have addressed your comments, feel free to get back with feedback :)
I think it's fine to change the crate::Error
from Box<dyn ark::std::Error>
to Box<dyn ark::std::Error + Send>
. That should solve the issues around unwrapping.
Description
This PR implements a Parallel Version of the Merkle Tree, completely transparent to the user, i.e. it defines two new versions of
MerkleTree::new(...)
andMerkleTree::new_with_leaf_digest(...)
which are compiled (in place of the legacy ones) when the "parallel" feature is enabled. The implementation can be found insrc/merkle_tree/mod.rs
. We have also included some benchmarks inbenches/merkle_tree.rs
. Using our implementation, for a Merkle Tree with2^20
leaves, using SHA256, we obtain a speedup of 80% over legacy on a M1 MacBook.closes: #122
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.
Pending
section inCHANGELOG.md
Files changed
in the Github PR explorer