Welcome to the resource topic for 2022/756
Title:
Curve Trees: Practical and Transparent Zero-Knowledge Accumulators
Authors: Matteo Campanelli and Mathias Hall-Andersen
Abstract:In this work we propose a new accumulator construction and efficient ways to prove knowledge of some element in a set without leaking anything about the element. This problem arises in several applications including privacy-preserving distributed ledgers (e.g., Zcash) and anonymous credentials. Our approaches do not require a trusted setup and significantly improve on the efficiency state of the of the art. We introduce new techniques inspired by commit-and-prove techniques and combine shallow Merkle trees, 2-cycles of elliptic curves to obtain constructions that are highly practical. Our basic construction—which we dub $\mathsf{Curve} \ \mathsf{Trees}$—is completely transparent (does not require a trusted setup) and is based on simple standard assumptions (DLOG and Random Oracle Model). It has small proofs and commitments and very efficient proving and verification time. Curve trees can be instantiated to be efficient in practice: the commitment to a set (accumulator) is 256 bits for any set size; for a set of size 2^{32} a proof is approximately 2KB, a verifier runs in $\approx 160$ms (easily parallelizable to $\approx 80$ms) and a prover in $\approx 3.6$s on an ordinary laptop. Using our construction as a building block we can construct a simple and concretely efficient anonymous cryptocurrency with full anonymity set. We estimate the verification time to be $\approx 320$ms (and trivially parallelizable to run in $\approx 160$ms) or $< 10$ms when batch-verifying multiple (> 100) transactions simultaneously. Transaction sizes are $< 3$KB. Our timings are competitive with those of the approach in Zcash Sapling and trade slightly larger proofs (proofs in Zcash are 0.2KB) for a completely transparent setup.
ePrint: https://eprint.iacr.org/2022/756
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .