Zerocoin: spending a coin without saying which (2013)

Miers, Garman, Green and Rubin proposed an extension to Bitcoin in which a user mints a coin by publishing a commitment \(C = g^S h^r\) to a random serial number \(S\), and later spends it by revealing \(S\) with a zero-knowledge proof that some minted coin opens to it. Spent serials are recorded, so no coin is spent twice, but the spend points to no particular mint: every coin ever minted is in the anonymity set.

To keep the proof short, the coins are gathered in an RSA accumulator \(A = u^{c_1 c_2 \cdots c_n} \bmod N\); each coin’s witness is the accumulator of all the others, and

\[w_i^{\,c_i} \equiv A \pmod N .\]

Here the spend instead proves membership with a ring signature over all coins, since \(C_i g^{-S} = h^{r}\) exactly for the coin being spent.

import matplotlib.pyplot as plt

import blockchainkit as bk

The accumulator

pool = bk.privacy.ZerocoinPool()
coins = [(1_000 + 37 * i, 50 + i) for i in range(12)]
for serial, blinding in coins:
    pool.mint(bk.privacy.mint_coin(serial, blinding))
primes = [bk.privacy.hash_to_prime(c) for c in pool.coins]
accumulator = pool.accumulator
for i, prime in enumerate(primes):
    assert bk.privacy.verify_membership(
        accumulator, prime, bk.privacy.membership_witness(primes, i)
    )
print(f"12 coins, one {accumulator.bit_length()}-bit accumulator")

12 coins, one 59-bit accumulator

Spending, once

serial, blinding = coins[7]
spend = bk.privacy.prove_zerocoin_spend(pool.coins, serial, blinding, b"pay alice", seed=1)
pool.spend(spend, b"pay alice")
try:
    pool.spend(spend, b"pay alice")
except ValueError as error:
    print("second spend:", error)
assert pool.spent == {serial}

second spend: double spend: this serial was already revealed

The proof looks the same for every coin

Every ring member gets a response, so the spent coin does not stand out.

q = bk.crypto.TEACHING_GROUP.q
fig, ax = plt.subplots(figsize=(7, 3.5))
ax.bar(range(12), [r / q for r in spend.proof.responses], color="#2563eb")
ax.set(xlabel="minted coin", ylabel="response / q", ylim=(0, 1))
ax.set_title("Which of the 12 coins was spent? The proof does not say")
fig.tight_layout()

plt.show()

Exercise

The proof here grows with the number of coins, while Zerocoin’s stays constant. Roughly how many group elements does a spend from a pool of a million coins carry here, and why did Zerocoin need a trusted RSA modulus to do better? A worked solution is in Exercises: privacy.