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^*$ is a rerandomization of a commitment $c \in \{c_1, \ldots, 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 ($6.2$ 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 $\pi_{one-many}$ 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.