Read on Twitter
(1/7) Recproofs () is a Merkle tree with updatable batch proofs. Let me try to unpack this: One attractive feature of Merkle trees is their fast updatability—when a Merkle leaf changes, leaf proofs can be updated with log n hash computations.lagrange.dev/recproofs
(2/7) This is however not true for Merkle batch proofs (A Merkle batch proof is a succinct proof for a set of Merkle leaves.) For one thing, we only know how to compute Merkle batch proofs with SNARKs. Updating such SNARK-based Merkle batch proofs requires re-computing the SNARK.
(3/7) Recproofs addresses the above problem via recursive SNARKs. It builds a succinct Merkle batch proof by going up the Merkle batch subtree (i.e., the subtree of paths from the Merkle root to the leaves in the batch), recursively calling the prover of a fixed-size circuit.
(4/7) This procedure yields a highly-parallelized batch-specific data structure that allows us to perform batch updates fast.
(5/7) What are the applications of Recproofs? One application is in proving BLS aggregate keys of an ever evolving set of signers: E.g., a map-reduce generalization of Recproofs can prove an aggregate BLS key is the product of at least T BLS keys contained in a Merkle digest.
(6/7) When the signers set evolves and the aggregate key changes, Recproofs can update our BLS aggregate key proof in time proportional to the symmetric difference of the two signers sets. E.g., if one signer is replaced with someone else, only log n computation is required.
(7/7) Looking forward to presenting Recproofs next week at the Science of Blockchain Conference at Stanford!
• • •
Missing some Tweet in this thread? You can try to
force a refresh
