Toxic waste: trusted setups, STARKs and the quantum question

Part 4 of Zero Knowledge, Full Proof, a series on zero-knowledge proofs and privacy on-chain.

On 13 January, the Ethereum Foundation opened a ceremony and invited anyone in the world to take part [1]. Each participant’s device generated a random number, mixed it into a shared result, and threw it away. The ceremony ran until August; by late July it had already passed 120,000 contributions [2], which makes it by far the largest of its kind. Its output will anchor the commitments that EIP-4844, Ethereum’s next scaling upgrade, uses to check the data that rollups post [3].

It is a strange thing for a system built on the idea of not trusting anyone to do. Part 3 ended on the same puzzle: Tornado Cash’s proofs rest on a ceremony from 2020, and Zcash launched a new shielded pool, Orchard, last year on a proof system that needs none. This post explains what the ceremonies protect against, which proof systems need them, and what happens to all of them if someone builds a large quantum computer.

What the ceremony is for

Part 2 showed that a zk-SNARK reduces a program to a polynomial identity, which the verifier checks at a single random point, usually called τ (tau):

p (x) = h (x) \cdot Z (x)

checked as p (τ) = h (τ) \cdot Z (τ)

If the prover knew τ in advance, it could build a false p(x) that happens to satisfy the equation at that one point, and the check would pass. So in pairing-based systems such as Groth16, τ is hidden. The setup publishes it only in hidden form, as a list of elliptic-curve points, where g is a fixed generator and d bounds the size of the circuit:

(g, g^{τ}, g^{τ^{2}}, \dots, g^{τ^{d}})

That list is enough to work with polynomials at τ without knowing τ. A KZG commitment [4], for example, commits to a polynomial with coefficients p₀, …, p_d by combining the published points:

C = g^{p (τ)} = \prod_{i = 0}^{d} {(g^{τ^{i}})}^{p_{i}}

Nobody who computes C ever sees τ; they only raise published points to the coefficients they already know. Groth16 needs a few more secrets of the same kind, one of them generated in a second phase specific to each circuit, but the principle is the same: the numbers must be used once and never known.

Whoever does learn τ can forge proofs for false statements. In Zcash, that would have meant creating coins out of nothing, invisibly. What τ does not allow is reading anyone’s secrets: Groth16 proofs have perfect zero knowledge [5], so they reveal nothing about the witness even to an attacker with unlimited power. The danger is to soundness, not to privacy. The Zcash team, who ran a ceremony for Zcash’s launch in 2016, called the secret “the toxic waste” [6].

The Electric Coin Company post The Design of the Ceremony by Zooko Wilcox, 26 October 2016, with the heading The Toxic Waste, and Other Ways To Counterfeit Zcash, explaining that the private key could be used to create counterfeit Zcash but not to violate anyone's privacy. — Zcash's own explanation, written the week of its launch [6]: the key could be used to counterfeit coins, but not to break anyone's privacy.

One honest participant is enough

The 2016 ceremony split the job among six people in different places, each holding one part of the secret [6]. The idea generalises. In the multi-party design by Bowe, Gabizon and Miers, each participant multiplies a fresh random factor into the running result and then deletes it [7]. Participant k, holding a secret s_k, raises the i-th published point to the power s_kⁱ, which turns powers of τ into powers of τ·s_k without revealing either:

g^{τ^{i}} \mapsto {(g^{τ^{i}})}^{s_{k}^{i}} = g^{{(τ s_{k})}^{i}}

τ = s_{1} s_{2} \dots s_{n}

The final τ is the product of every contribution. Recovering τ requires every single factor. The parameters are safe, in the paper’s words, “if at least one of the n players is honest” [7].

A multi-party ceremony, after Bowe, Gabizon and Miers [7]. Each contributor only ever sees their own secret, and the chain is safe unless every one of them kept theirs.

That is why the ceremonies keep growing. The Powers of Tau ceremony that fed Zcash’s Sapling upgrade drew 87 contributions in 2017 and 2018 [8]; Tornado Cash’s, in 2020, drew 1,114 [9]; Ethereum’s this year drew over a hundred times as many. Each new participant is one more chance that somebody really did delete their share. Newer systems also reduce how often a ceremony is needed. Groth16 requires one for every circuit, but PLONK, built on KZG commitments, uses a single universal setup that works for any circuit up to a given size, and can be extended later by new participants [10], [4].

Proofs without a ceremony

The other route is to avoid secret parameters altogether. Two families of proof systems do this, in different ways.

The first is Halo, which replaced pairings with an inner-product argument over ordinary elliptic curves [11]. Zcash adopted its successor, Halo 2, for the Orchard shielded pool in its NU5 upgrade of May 2022, and described the change as eliminating the trusted setup [12]. Its proofs are larger than Groth16’s and slower to check, but nobody holds a secret that could break them.

The second is STARKs, introduced in 2018 by Ben-Sasson, Bentov, Horesh and Riabzev [13]. A STARK needs no trusted party at all; its security rests only on collision-resistant hash functions. The cost is size. StarkWare’s own benchmarks report proofs of about 40 to 62 kilobytes for a computation of nearly 100,000 hashes at 80-bit security [14], against the couple of hundred bytes of a Groth16 proof. The STARK paper itself estimates that SNARK proofs are about a thousand times shorter [13]. StarkWare’s systems, including StarkEx and StarkNet, run on STARKs.

	Groth16	PLONK with KZG	Halo 2	STARK
Setup	one ceremony per circuit	one universal ceremony	none	none
Proof size	3 group elements, under 200 bytes	7 to 9 group elements and 6 field elements, about half a kilobyte	grows slowly with the circuit	tens of kilobytes
Rests on	elliptic-curve pairings	elliptic-curve pairings	discrete logarithms	hash functions
If a large quantum computer arrives	proofs can be forged	proofs can be forged	proofs can be forged	believed to hold

The quantum question

The last row of that table is why a physics student cares about any of this. Every proof system in the first three columns relies, in the end, on the difficulty of computing discrete logarithms on an elliptic curve. In 1994, Peter Shor showed that a quantum computer could compute discrete logarithms, and factor large numbers, in polynomial time [15], and the same approach carries over to elliptic curves, which is the case the resource estimates below consider. A large enough quantum computer would let an attacker forge Groth16, PLONK and Halo 2 proofs as easily as someone who had kept the toxic waste. It would not, however, expose the secrets inside existing Groth16 proofs; perfect zero knowledge [5] holds against any attacker, quantum or not. That protects the proof, not everything around it: a private transaction usually carries other data, such as encrypted notes, whose encryption rests on elliptic curves too.

Hash functions fare better. The best known quantum attack on them, Grover’s search algorithm, gives only a quadratic speed-up [16]. Finding an input that hashes to a given n-bit output goes from

2^{n} guesses, classically

\to \approx 2^{n / 2} with Grover

which a longer hash output can absorb: doubling n restores the original margin. That is why the STARK paper describes its construction as post-quantum [13], though it calls the claim informal: no one has a proof that hash functions will stay secure against quantum attack, only the absence of an attack.

How close is the threat? Roetteler and colleagues estimated in 2017 that breaking a 256-bit elliptic curve needs about 2,330 logical qubits, the error-corrected kind, and around 10¹¹ Toffoli gates [17]. Error correction multiplies that many times over. Webber and colleagues estimated last year that, under their assumptions about error rates and speed, breaking the elliptic-curve keys used by Bitcoin within a day would take about 13 million physical qubits, or 317 million to do it within an hour [18]. The largest processor IBM has unveiled, Osprey, has 433 [19].

The gap between IBM's largest processor [19] and one estimate of what breaking 256-bit elliptic-curve keys would take [18]. Each gridline is a factor of ten.

A gap of more than four orders of magnitude, with error rates that also have to fall, is why nobody expects this soon. It is not why nobody should plan for it. On 24 August, NIST released draft standards for its first post-quantum algorithms, for key exchange and for signatures [20].

NIST news release of 24 August 2023: NIST to Standardize Encryption Algorithms That Can Resist Attack by Quantum Computers. Three new algorithms are expected to be ready for use in 2024. — NIST's announcement of the draft standards, 24 August 2023 [20].

Systems meant to last, and blockchains are meant to last, will need an answer before the machines exist, not after.

What I take from this

A trusted setup is not the scandal it sounds like. It is a precise, limited assumption: someone, among thousands, deleted a number. Its failure would allow forgery, but it would not reveal what the proofs hide, and the ceremonies now make it about as safe as such an assumption can be. The more interesting line runs elsewhere, between proof systems built on elliptic curves, which are small and fast today but have a known expiry date, and those built on hashes, which are larger but have none that anyone knows of. Part 5 will look inside a modern prover, and at what it takes to make proving fast.

References

EF Protocol Support Team. Announcing the KZG ceremony. Ethereum Foundation blog, 16 January 2023. blog.ethereum.org. Archived copy: 7 September 2023.
KZG ceremony sequencer, status endpoint, archived 23 July 2023. web.archive.org.
Vitalik Buterin, Dankrad Feist, Diederik Loerakker, George Kadianakis, Matt Garnett, Mofi Taiwo and Ansgar Dietrichs. EIP-4844: Shard blob transactions. eips.ethereum.org.
Aniket Kate, Gregory M. Zaverucha and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Advances in Cryptology: ASIACRYPT 2010, pp. 177–194, 2010. doi:10.1007/978-3-642-17373-8_11.
Jens Groth. On the size of pairing-based non-interactive arguments. In Advances in Cryptology: EUROCRYPT 2016, pp. 305–326, 2016. doi:10.1007/978-3-662-49896-5_11. Preprint: IACR ePrint 2016/260.
Zooko Wilcox. The design of the ceremony. Electric Coin Company, 26 October 2016. Archived copy.
Sean Bowe, Ariel Gabizon and Ian Miers. Scalable multi-party computation for zk-SNARK parameters in the random beacon model. 2017. IACR ePrint 2017/1050.
Zcash Foundation. Conclusion of the Powers of Tau ceremony. 13 April 2018. zfnd.org.
Mike Orcutt. Ethereum mixer Tornado Cash completes its trusted set-up ceremony. The Block, 13 May 2020. theblock.co.
Ariel Gabizon, Zachary J. Williamson and Oana Ciobotaru. PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. 2019. IACR ePrint 2019/953.
Sean Bowe, Jack Grigg and Daira Hopwood. Recursive proof composition without a trusted setup. 2019. IACR ePrint 2019/1021.
Electric Coin Company. NU5 activates on mainnet, eliminating trusted setup and launching a new era for Zcash. 31 May 2022. electriccoin.co.
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. 2018. IACR ePrint 2018/046.
StarkWare Team. ethSTARK documentation, version 1.2. 2021, updated July 2023. IACR ePrint 2021/582, version of 25 July 2023.
Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), pp. 1484–1509, 1997. doi:10.1137/S0097539795293172. Preprint: arXiv:quant-ph/9508027.
Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96), pp. 212–219, 1996. doi:10.1145/237814.237866. Preprint: arXiv:quant-ph/9605043.
Martin Roetteler, Michael Naehrig, Krysta M. Svore and Kristin Lauter. Quantum resource estimates for computing elliptic curve discrete logarithms. In Advances in Cryptology: ASIACRYPT 2017, pp. 241–270. doi:10.1007/978-3-319-70697-9_9. Preprint: IACR ePrint 2017/598.
Mark Webber, Vincent Elfving, Sebastian Weidt and Winfried K. Hensinger. The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime. AVS Quantum Science 4, 013801, 2022. doi:10.1116/5.0073075. Preprint: arXiv:2108.12371.
IBM. IBM unveils 400 qubit-plus quantum processor and next-generation IBM Quantum System Two. 9 November 2022. newsroom.ibm.com.
NIST. NIST to standardize encryption algorithms that can resist attack by quantum computers. 24 August 2023. nist.gov.