Paper 2022/756

Curve Trees: Practical and Transparent Zero-Knowledge Accumulators

Matteo Campanelli, Protocol Labs
Mathias Hall-Andersen, Aarhus University
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
snarks accumulator zero-knowledge set membership anonymous payment systems
Contact author(s)
matteo @ protocol ai
ma @ cs au dk
History
2022-06-15: revised
2022-06-13: received
See all versions
Short URL
https://ia.cr/2022/756
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/756,
      author = {Matteo Campanelli and Mathias Hall-Andersen},
      title = {Curve Trees: Practical and Transparent Zero-Knowledge Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2022/756},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/756}},
      url = {https://eprint.iacr.org/2022/756}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.