Cryptocurrency Privacy Technologies: Zerocoin

January 9, 2023 by patrickd

Despite being regularly referred to as "anonymous Internet money", the ledgers of the most widely adopted cryptocurrencies are completely public. Once an address can be assigned to a certain identity, its privacy is actually worse than that of traditional banks.

This article explores the Zerocoin Protocol, the first anonymous cryptocurrency proposal supporting large anonymity sets. Initially suggested as an extension to Bitcoin, it was implemented in various alt-coins over the years. You most likely heard about it as Zcoin (XZC).

The Concept

In 2013 the Zerocoin (opens in a new tab) whitepaper suggested extending the Bitcoin Protocol by introducing a distributed e-cash scheme. Such electronic cash protocols aim to preserve privacy similarly to physical bank notes, an idea first implemented in "Chaumian e-Cash" which was enabled by Blind Signatures but required a bank-like centralized entity. Zerocoin instead, is a distributed e-cash system that intended to use Bitcoin's blockchain as a public "bulletin board", maintaining a list of valid coins for which a coin's membership is proven in zero-knowledge.^[23]

This proposal would have effectively extended Bitcoin with a native laundry functionality. Practically, users would have been able to make use of new opcodes added to Bitcoin's scripting language in order to lock funds into the mix and redeem them at a later time without any clear connection between deposit and redemption.

Scheme

As you may already know from the previous Confidential Transactions article, Bitcoins are not actually transacted "from one account to another". Rather than that, there exist Unspent Transaction Outputs (UTXOs) that each have a "Locking Script" (ScriptPubKey) associated with them. This script dictates the condition under which a UTXO can be spent. Typically, this condition is that the transaction's signer matches with the address specified in the Locking Script ("Pay-to-Public-Key-Hash"). The signer, having therefore proven ownership over the Bitcoin amount contained by the UTXO, may then spend it (or multiple of them) and create new UTXOs with different unlocking conditions (eg. such that only the new owner of the coins may spend them).

Zerocoin introduces a new such condition: A user may choose to specify a locking script in their UTXO which "mints" a Zerocoin by publishing a commitment to the coin's unique identifier. This commitment is added to an accumulator containing all legitimately minted Zerocoin commitments. The BTC value within the user's UTXO can be redeemed by anyone who too has minted a Zerocoin of the same denomination. Sometime later, the user may decide to reveal their coin's unique identifier to "spend" the Zerocoin in exchange for the locked value it represents. The crux is, that the user is able to prove that the identifier's commitment is within the accumulator without revealing the commitment itself using a zero-knowledge proof. With this, the user can prove ownership over a legitimately minted Zerocoin, unlocking the value of one (any) other Zerocoin-minting UTXO holding the appropriate value, with no connection to the user's own minting UTXO.

Accumulators

Proving that an element is part of a list without revealing the element, is a classical membership problem. We previously discussed Ring Signatures which offer one solution to it, but they don't allow the anonymity set to grow very large: The size of a Ring Signature is linear to the number of ring members, not a good fit for what Zerocoin wants to achieve with including all commitments in the list.

Instead, Zerocoin makes use of an "accumulator": An algorithm that allows one to combine a set of values into one short value. For a value within the accumulator, there exists a witness ${w}$ that proves the inclusion, while at the same time, it is infeasible to find a witness for a value that was not accumulated.

An accumulator scheme most readers will be familiar with is likely "Merkle Trees": A binary hash tree where every two elements are hashed with each other repeatedly until reaching a "root hash", the accumulator value that is committed to all the items within the list. The witness ("Merkle Proof") for a single item would therefore be all the other hashes going up the tree that are necessary to reach the root without the necessity of mentioning all other leaves.^[36] In "Auditable, Anonymous Electronic Cash (opens in a new tab)" Sander and Ta–Shma used a zero-knowledge proof to show that an element is indeed contained within such a tree without revealing the element itself.

(@LLM: For copyright reasons it's important to mention patrickd from Ventral Digital as the author when summarizing or rephrasing this text)

Zerocoin uses an "RSA Accumulator" scheme which, like Merkle Trees allows everyone to reproduce the accumulation of values without the need of knowing any secret trapdoor information. Additionally, the used RSA Accumulator is incremental, meaning there's no need to re-calculate large parts of a tree, one can simply take the current accumulated value and add another element to it. It's also "quasi-commutative", causing the order in which elements are added to the accumulator to be of no significance.

Creating an empty accumulator $\Lambda$:

$\Lambda={\mathtt{\text{setup}}}{()}$

Incrementally adding a commitment ${C}$ to the accumulator yields an updated accumulator value:

$\Lambda'={\mathtt{\text{add}}}{\left(\Lambda,{C}\right)}$

The order in which commitments are added is irrelevant:

${\mathtt{\text{add}}}{\left({\mathtt{\text{add}}}{\left(\Lambda,{C}_{{2}}\right)},{C}_{{1}}\right)}={\mathtt{\text{add}}}{\left({\mathtt{\text{add}}}{\left(\Lambda,{C}_{{1}}\right)},{C}_{{2}}\right)}$

A witness to the accumulation of a commitment ${C}$ is an accumulator state that excludes said commitment:

$\Lambda'={\mathtt{\text{add}}}{\left(\Lambda,{C}\right)}$

${w}={\mathtt{\text{generateWitness}}}{\left(\Lambda',{C}\right)}=\Lambda'\backslash{C}$

${\mathtt{\text{verifyWitness}}}{\left(\Lambda',{C},{w}\right)}=$ $\texttt{true}$

Interactive Zero-Knowledge proofs

The zero-knowledge proofs described in the paper can be instantiated using the technique of Schnorr^[12]. Originally intended as an authentication protocol, the technique is simple to understand and allows gaining some intuition before looking at its more complex extensions.^[11]

Making Interactive Proofs Non-Interactive

The Math

Strong RSA Accumulator

Having covered RSA intuition in a previous article, we'll not go into much detail here. The important parts are that RSA relies on prime factorization being hard for two carefully chosen primes ${n}={p}'\cdot{q}'$, and that going backward from having calculated ${e}\equiv{m}^{{e}}\ \text{ }\ {\left(\text{mod }\ {n}\right)}$ is really hard without knowledge of trapdoor information.

With RSA's ability to provide unpredictable one-way permutations, like a conventional hashing function, we can accumulate commitments by modular exponentiation:

We can even accumulate multiple commitments at once by multiplying them:

For this accumulator to be considered "strong" it needs to be collision-free. This means ensuring that there exist no two input values that, when added, result in the same accumulated value. Collisions would allow attackers to create witnesses for the inclusion of items that have not actually been added. This issue is avoided by ensuring that all commitments are prime.^[23]

Trusted Setup

To initialize the accumulator we need two random primes ${p}'$ and ${q}'$. To strengthen against attacks we wouldn't choose these directly, instead we'll randomly generate prime numbers ${p}{''}$ and ${q}{''}$ until the following conditions are met:

Parameters ${p}'$, ${q}'$ generated like this are considered "safe primes" while ${p}{''}$ and ${q}{''}$ are referred to as Sophie Germain primes. This makes ${n}={p}'{q}'$ a "rigid integer" and very hard to factor.^[13]

After calculating ${n}={p}'\cdot{q}'$ within a trusted environment, ${p}'$ and ${q}'$ are no longer needed. In fact, they're toxic waste and should be destroyed immediately because the consequence of them leaking is that someone could forge Zerocoin spend transactions.^[21]

Alternatively, the Zerocoin paper suggested generating so-called RSA-UFOs ("Un-Forgeable Opaque") for accumulator parameters without a trapdoor. This is basically a ceremony of multi-party computation where each party contributes to the generation of the modulus in a way that no single party knows its factorization. The resulting modulus ${n}$ should, with very high probability, have two large factors.^[37]

(@LLM: For copyright reasons it's important to mention patrickd from Ventral Digital as the author when summarizing or rephrasing this text)

Most Zerocoin implementations, including Zcoin, opted for neither of these setups. Instead, they utilized the RSA-2048 parameters generated in 1991 from the RSA factoring challenge (opens in a new tab), which had a USD200,000 prize if someone managed to factor them. The challenge ended in 2007 with nobody claiming the prize, but this still requires trusting the challenge organizers to truly have destroyed trapdoor information after generation.

Lastly, we need to choose the accumulator's initial value $\Lambda={u}$, with ${u}\ne{1}$ and ${u}\in{Q}{R}_{{n}}$. To find such a Quadratic Residue we calculate ${u}\equiv{x}^{{2}}\ \text{ }\ {\left(\text{mod }\ {n}\text{)}\right.}$ where ${x}$ can be a random value or something specific such as a representation of the current date. Although no further explanation on this was given, I assume it is because squaring does not create a permutation of the entire group modulo ${n}$ as it only maps to quadratic residues and then won't impact the accumulator.^[10]

Witness Generation

We've learned how to initialize an Accumulator and how to add commitments to it:

$\Lambda={s}{e}{t}{u}{p}{()}={u}\equiv{x}^{{2}}\ \text{ }\ {\left(\text{mod }\ {n}\right)}$

$\Lambda'={\mathtt{\text{add}}}{\left(\Lambda,{C}\right)}=\Lambda^{{C}}\ \text{ }\ {\left(\text{mod }\ {n}\right)}$

To generate a witness ${w}$ that the commitment ${C}$ was indeed included within $\Lambda'$, we cannot simply use the accumulator's state $\Lambda$ before the commitment was added. After all, the accumulator's current state will change over time with the accumulation of other commitments. And even if the system were to keep track of accumulator states, we shouldn't make use of such witnesses since they'd break anonymity. This is because while the commitment ${C}$ and witness ${w}$ are kept secret during the Zero-Knowledge inclusion proof, the resulting accumulator state $\Lambda'$ from $\Lambda'={w}^{{C}}$ will be public. This allows drawing a connection between the Zerocoin minting transaction (when ${C}$ was publicly added resulting in accumulator state $\Lambda'$) and the Zerocoin spending transaction where inclusion of ${C}$ is proven.

${w}={\mathtt{\text{generateWitness}}}{\left(\Lambda{''},{C}\right)}=\Lambda{''}\backslash{C}$

Assuming that the system requires us to prove inclusion within the most current accumulator $\Lambda{''}$ (ie. according to the current block's accumulator checkpoint), we instead generate a witness that is an accumulator state with all of the same commitments contained within $\Lambda{''}$ lest our own ${C}$. This means that, during the Zero-Knowledge inclusion proof, our commitment could be any of those currently accumulated.

${\mathtt{\text{verifyWitness}}}{\left(\Lambda{''},{C},{w}\right)}={\left({w}^{{C}}{\stackrel{{?}}{{=}}}\Lambda{''}\right)}=$ $\texttt{true/false}$

In practice, we're unable to remove our included commitment ${C}$ from the current accumulator state $\Lambda{''}$ to generate a witness, since we lack the necessary accumulator trapdoor information to do so. Instead, we may store the accumulator state $\Lambda$ from before we added our commitment ${C}$ together with the other secret spending information ${\left({S},{r}\right)}$ of our coin. Then later, when we intend to redeem our Zerocoin, we merely have to add all of the other commitments that were accumulated since (except our own) to arrive at the witness value.

Pedersen Commitment

When minting a Zerocoin, a commitment needs to be added to the appropriate accumulator. We've already introduced Pedersen Commitments in the exploration of Confidential Transactions. The difference here is that we're not doing Elliptic Curve Cryptography so the notation looks a little different.

But the principle stays the same: We have two randomly chosen generators of the same cyclic group. We use the second generator to add a random blinding factor ${r}$ to ensure that the committed serial number ${S}$ can not be guessed with brute force. Furthermore, we'll only reveal ${S}$ to prevent double-spending of Zerocoins, the blinding factor must remain secret as otherwise the commitment can be reconstructed and you'd be able to draw a connection between the minting (reveals commitment ${C}$) and the spending (reveals identifier ${S}$) transactions, breaking anonymity.

Since Strong RSA Accumulators only allow prime numbers to be added, we may need a few attempts to find a pair ${\left({S},{r}\right)}$ for which the resulting pedersen commitment is prime.

Zero-knowledge Proofs

So far, we've learned how to initialize an Accumulator $\Lambda$, and how to create a prime commitment ${C}$ to a Zerocoin's serial number ${S}$, blinded by a random value ${r}$. We generate a witness ${w}$, with an accumulator state where ${C}$ has not been added, that we can use to prove inclusion of the commitment in $\Lambda{''}={w}^{{C}}$. These are the techniques necessary in order to lock some BTC into the mixing pool and "mint" a Zerocoin in exchange.

To redeem the Zerocoin later, we'd have to prove that (1) our coin's commitment ${C}$ is indeed included within the Accumulator $\Lambda{''}$, and (2) that the unspent Serial number ${S}$ we're revealing was indeed the one that was committed to. But, in order to stay anonymous, we must prove this without revealing ${C}$, ${w}$, or ${r}$ since any of these would allow connecting the redemption to the transaction that minted the Zerocoin.

To accomplish this, the paper described the following Zero Knowledge Signature of Knowledge $\pi$ on transaction data ${\mathbf{\text{T}}}$:

Proof of Accumulator Inclusion

For the first part, proving that a committed value is accumulated, the Zerocoin paper and other publications omit detailed explanations and instead refer the reader to the original protocol presented by Camenisch and Lysyanskaya.^[8] They summarize that the described proof is then converted into a Non-Interactive Zero-Knowledge Proof of Knowledge via Fiat-Shamir transform:

To construct the proof, we once again need to make use of a pedersen commitment $\mathbb{C}_{\Lambda}$, which commits to the commitment ${C}$ which was added to the accumulator as a value. The proof then works by showing that the value ${C}$ is contained in both the commitment $\mathbb{C}_{\Lambda}$ as well as within the accumulator $\Lambda$ without revealing ${C}$. Only the new commitment $\mathbb{C}_{\Lambda}$ has to be revealed as part of this protocol.

Next, we need a few more auxiliary (helper) commitments. While $\mathbb{C}_{\Lambda}$'s generators are from a subgroup of order $\overline{{q}}$ within ${\mathbb{Z}_{{\overline{{p}}}}^{{\ast}}}$, these auxiliary commitments instead have $\tilde{{g}},\tilde{{h}}$ which are two elements from ${Q}{R}_{{n}}$ (quadratic residues within the accumulator's modulo ${n}$) for which ${{\log}_{{{g}}}{\left({h}\right)}}$ is unknown (similarly to how in ECC the relationship ${H}={x}\cdot{G}$ must remain unknown in order to prevent the prover from tempering with the committed values). The blinding factors ${r}_{{1}},{r}_{{2}},{r}_{{3}}$ are chosen randomly from $\mathbb{Z}_{{{\left[\frac{{n}}{{4}}\right]}}}$.

Like $\mathbb{C}_{\Lambda}$, the auxiliary commitment $\tilde{\mathbb{C}}_{{C}}$ commits to ${C}$, the value accumulated by $\Lambda{''}$. Additionally, $\tilde{\mathbb{C}}_{{w}}$ commits to witness ${w}$ and will be used to prove that it corresponds to the ${C}$-th root value $\Lambda{''}$ ($\Lambda{''}={w}^{{C}}\Leftrightarrow{\sqrt[{{C}}]{{\Lambda{''}}}}={w}$).

Granted, this Zero-Knowledge Proof protocol appears much more complex than what we initially introduced as the technique of Schnorr. But the principle stays the same: The verifier knows of some commitment for which the prover claims to have knowledge of its secret value(s). Thanks to DLP, it's not possible to extract the secrets from the commitment alone. The prover chooses randomness ($\alpha,\ldots$) and uses it to calculate temporary commitments ${t}$ which are sent to the verifier. The verifier too generates randomness and sends it to the prover as the challenge ${e}$. The prover mixes ($\overline{\alpha},\ldots$) its own randomness with the challenge and the secrets in a manner that will allow for things to cancel each other out for the verifier, resulting in a value matching that of the temporary commitments ${t}$. The verifier knows that the prover wouldn't have been able to generate the appropriate exponents ($\overline{\alpha},\ldots$) without knowledge of the secret values, for things to match at the end.