Paper 2021/327

Veksel: Simple, Efficient, Anonymous Payments with Large Anonymity Sets from Well-Studied Assumptions

Matteo Campanelli and Mathias Hall-Andersen

Abstract

We propose Veksel, a simple generic paradigm for constructing efficient non-interactive coin mixes. The central component in our work is a concretely efficient proof ${\pi }_{one-many}$ that a homomorphic commitment $c^{\ast }$ is a rerandomization of a commitment $c\in \{c_1,\dots ,c_{\ell }\}$ without revealing $c$. We formalize anonymous account-based cryptocurrency as a universal composability functionality and show how to efficiently instantiate the functionality using ${\pi }_{one-many}$ in a straightforward way (Veksel). We instantiate and implement ${\pi }_{one-many}$ from Strong-RSA, DDH and random oracles targeting $\approx 112$ bits of security. The resulting NIZK has constant size ($|{\pi }_{one-many}|=5.3\text{KB}$) and constant proving/verification time ($\approx 90\text{ms}$), on an already accumulated set. Compared to Zerocash—which offers comparable marginal verification cost and an anonymity set of every existing transaction—our transaction are larger ($$ KB) and verification is slower. On the other hand, Veksel relies on more well-studied assumptions, does not require an expensive trusted setup for proofs and is arguably simpler (from an implementation standpoint). Additionally we think that $$ might be interesting in other applications, e.g. proving possession of some credential posted on-chain. The efficiency of our concrete NIZK relies on a new Ristretto-friendly elliptic curve, Jabberwock, that is of independent interest: it can be used to efficiently prove statements on "committments on commitments" in Bulletproofs.

Note: Mention new curve in abstract.