What a lovely hat

Paper 2022/1104

$\mu$Cash: Transparent Anonymous Transactions

Abstract

Zero Knowledge Set Membership Proofs (zkSMPs) allow efficiently, i.e. sublinearly in the size of the set, proving membership of a value in a set in zero knowledge with respect to the value. They have been used to construct anonymous cryptocurrencies such as ZCash, which uses a zero knowledge Merkle proof to show that the inputs of a transaction belong to the Transaction Output (TXO) set. Using a Merkle tree instantiated with a pair of Pedersen hash functions between an amicable cycle of elliptic curves, similarly to Curve Trees, and the Weil Elliptic Curve Inner Product (ECIPs) proofs, I design a set membership protocol with substantially smaller witness sizes than other Merkle zkSMPs. This protocol uses a pair of communicating Bulletproofs, one over each curve, whose total proof size I am able to reduce by proving portions of each verifier inside the other proof. Using these techniques, along with an adaptation of the Bulletproofs++ confidential transaction protocol, I design an anonymous transaction protocol for a decentralized cryptocurrency, whose security argument is reducible to the discrete log problem over a pair of elliptic curves and that does not require a trusted setup. Over a $256$ bit field, these transactions are $1349 + 64n + 32 \lceil \log_2 c \rceil$ bytes for $n$ inputs, $m$ outputs, $d$ depth, and $c$ proof capacity, which is bounded by a linear function of $n d$, $n$, and $m$ and is equal to $1$ for up to $m < 1000$ or $n < 37$ when $d = 48$. Proving complexity is quasilinear and verifier complexity is linear in both $n d$ and $m$, and in practice verification will be dominated by the cost of two Bulletproof verifications of length $1536$ and $1744$ for $c=1$. $\mu$Cash support efficient batch verification, user defined assets and multi-asset confidential transactions, privacy preserving multi-party proving, adaptor signatures, absolute and relative time locks, and a multiphase transaction structure to support scriptless scripts for private atomic swaps and payment channels. This protocol is likely compatible with the Halo accumulation scheme, although I do not investigate this.