Many-out-of-Many Proofs and Applications to Anonymous Zether

Anonymous Zether, proposed by Bünz, Agrawal, Zamani, and Boneh (FC'20), is a private payment design whose wallets demand little bandwidth and need not remain online; this unique property makes it a compelling choice for resource-constrained devices. In this work, we describe an efficient construction of Anonymous Zether. Our protocol features proofs which grow only logarithmically in the size of the "anonymity sets" used, improving upon the linear growth attained by prior efforts. It also features competitive transaction sizes in practice (on the order of 3 kilobytes). Our central tool is a new family of extensions to Groth and Kohlweiss's one-out-of-many proofs (Eurocrypt 2015), which efficiently prove statements about many messages among a list of commitments. These extensions prove knowledge of a secret subset of a public list, and assert that the commitments in the subset satisfy certain properties (expressed as linear equations). Remarkably, our communication remains logarithmic; our computation increases only by a logarithmic multiplicative factor. This technique is likely to be of independent interest. We present an open-source, Ethereum-based implementation of our Anonymous Zether construction. * I would like to thank Markulf Kohlweiss and Michele Ciampi for many helpful discussions and suggestions. Overview of our contribution One-out-of-many proofs, introduced by Groth and Kohlweiss [GK15], allow a prover to demonstrate knowledge of a secret element among a public list of commitments, together with an opening of this commitment