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 Curve 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 232 a proof is approximately 2KB, a verifier runs in ≈160ms (easily parallelizable to ≈80ms) and a prover in ≈3.6s 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 ≈320ms (and trivially parallelizable to run in ≈160ms) or <10 ms when batch-verifying multiple (>100) transactions simultaneously. Transaction sizes are <3KB. 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.