In collaboration with @winderica
TLDR: we port Tornado Cash to Flock, a post-quantum binary-field SNARK, proving a depth-32 withdrawal over SHA-256 in under 30 ms, and describe a simple recovery protocol, requiring only that wallets derive note secrets from a seed, that lets existing pools survive a discrete log break.
Introduction
Privacy pools such as Tornado Cash rest on the hardness of the discrete logarithm, through both their Pedersen commitments and their Groth16 proofs. Recent autoresearch efforts, both at lowering quantum resource estimates and at breaking hash functions, suggest that quantum discrete-logarithm circuits with far lower gate counts than the published ones, and yet-undiscovered attacks on the hash functions these pools use, may already exist. Recent progress in binary-field proving systems, ZCash’s deployment of ZIP 2005 in Ironwood, and the leanVM aggregation work all point the same way: privacy pools should now start to transition their stack to battle-tested cryptographic primitives.
In this post we demonstrate a working Tornado Cash-like pool built on Flock: a plausibly post-quantum transparent hash based binary-field SNARK. We instantiate its merkle tree and nullifier derivation function with SHA-256. We also describe a simple quantum recoverability protocol for Tornado Cash like pools, requiring a tiny wallet change. This writeup will show:
- Implementation and first benchmarks of Tornado Cash ported to Flock along recursive aggregation performances.
- A recovery protocol inspired by ZIP 2005, deployable in any Tornado Cash-like protocol.
Implementation
To prove a Tornado Cash withdrawal from a Merkle tree of height 32, we need 34 SHA-256 compressions: one for the commitment, one for the nullifier hash, and 32 for the Merkle path up to the root. A single monolithic circuit containing all 34 compressions works, but it wastes Flock’s main strength: Flock proves many copies of one circuit at once, and a single large circuit leaves most of the committed witness idle. Instead, we observe that all three hash roles in a withdrawal share the same shape, and write one tiny circuit containing a single SHA-256 compression and a small multiplexer. Controlled by a private bit, the multiplexer swaps the order of the two inputs, so the same circuit serves as the commitment hash, the nullifier hash, or a Merkle node depending only on what is fed into it. A sumcheck-based glue argument over the committed witnesses then ties the 34 invocations together, enforcing that each output feeds the right input of the next.
By shrinking the circuit size from 34 compressions down to just one, the core task of the prover now became proving 34 invocations of a small circuit. Flock is designed for this batched setting, resulting in significant performance improvements. Below is the prover time comparison across different tree depths. At depth 32, the stepwise approach made proof generation 28× faster than our initial monolithic circuit.
| depth | monolithic | stepwise | ratio |
|---|---|---|---|
| 8 | 0.23 s | 31.7 ms | 7.3× |
| 20 | 0.50 s | 27.4 ms | 18× |
| 32 (266 KiB) | 0.81 s | 28.6 ms | 28× |
Note that, the prover time barely scales as the tree gets larger because 1) the circuit size is independent of tree depth and 2) Flock’s shipped configs for Ligerito commitment require a committed witness of at least 2^22 bits, so proofs for all depths from 8 up to about 126 have the same witness size.
Aggregating Withdrawals Recursively
Flock’s upstream repository recently gained a recursion layer, which we used to build a user/aggregator) split. Each user proves their own withdrawal on their own machine while an aggregator checks every submitted proof and folds them all into one. The final proof attests to the number of withdrawals and to a digest over every withdrawal’s (nullifier hash, root). We measured both sides at tree depth 32. On the user side, proving one withdrawal takes 19.5 ms and produces a 203.6 KiB proof, regardless of how many withdrawals are aggregated. The aggregator’s cost depends on the number of withdrawals it folds:
| withdrawals | aggregator wall time | final proof size | verify |
|---|---|---|---|
| 4 | 1.7 s | 343.9 KiB | 46 ms |
| 16 | 10.2 s | 343.9 KiB | 62 ms |
| 64 | 43.6 s | 343.9 KiB | 60 ms |
| 128 | 87.6 s | 343.9 KiB | 64 ms |
The final proof size and verification time are constant in the number of withdrawals. The cost moves to the aggregator, at about 0.68 s per withdrawal. We envision such app layer privacy pools working in combination with in mempool aggregation.
Recoverability Protocol
Privacy pools built on classical cryptography still remain exposed to a future quantum attacker. We would however want a note deposited today to still be spendable in a few years. This matters even more as protocols start connecting privacy pools to DeFi. ZIP 2005 addresses this for ZCash Ironwood by, among other things, deriving the commitment randomness from a seed, so that notes can later be re-proven under a post-quantum proving system. We adapt the idea to a Tornado Cash-like pool, where it yields a particularly simple recovery setup.
Protocol
Recall that to deposit in Tornado Cash, a user samples two random 248-bit strings (k, r) and computes C = \mathrm{Pedersen}(k || r). To withdraw, the user publishes the nullifier hash h = \mathrm{Pedersen}(k) along with a proof \pi that C is in the Merkle tree and that h is derived from its opening. The only change the recovery protocol requires on the deposit side is that wallets stop sampling (k, r) and instead derive them from a 256-bit seed s as k || r = H(s), with H(s) = \mathrm{truncate}(\mathrm{SHA512}(s), 496).
When a cryptographically relevant quantum computer becomes public knowledge, the pool is frozen and users withdraw through a “recovery verifier” instead. Using a post-quantum zkSNARK, they prove knowledge of a seed s with k || r = H(s) such that C = \mathrm{Pedersen}(k || r) is in the Merkle tree and h = \mathrm{Pedersen}(k). Since the nullifier hash is the same as before, the contract keeps a single set of spent nullifiers: a note spent before the freeze cannot be spent again after it.
Assumptions
We work under an epoch assumption. Before the freeze the adversary is classical and Groth16 is sound. After the freeze the adversary knows every discrete log: it can open any Pedersen commitment and forge Groth16 proofs. The freeze must therefore come before the break, otherwise the pool is drained through the old verifier before the recovery starts.
We use a knowledge-sound post-quantum zkSNARK and keep the pool’s existing MiMC Merkle tree, which we assume stays collision resistant against a quantum adversary.
We model the derivation function H as a random oracle: hashing a seed s yields a fresh, uniformly random 496-bit string H(s), independent of every other seed. We also assume that Pedersen is close to uniformly distributed on uniform inputs. Together, those two assumptions say that the map from seeds to note commitments behaves like a random function, even for an adversary who breaks discrete log.
Security Intuition
We want three properties from the recovery path: (1) an attacker cannot double spend its own notes, (2) an attacker cannot steal other users’ notes, and (3) every seed-derived note can be spent. In the first epoch the adversary may deposit as many commitments as it likes, but the pool is then exactly as secure as Tornado Cash is today. In the second epoch the pool no longer accepts deposits and only the recovery verifier is enabled. We therefore only analyze what happens after the freeze.
Recall the derivation function H from the protocol, and write k || r = H(s) for the derived nullifier and commitment randomness. Next, define F as the seed-to-commitment map:
F : \{0,1\}^{256} \rightarrow \mathbb{G}, \qquad F(s) = \mathrm{Pedersen}(H(s))
where \mathbb{G} is the babyjubjub prime-order subgroup, of size about 2^{251}.
The pool holds n = m + l deposits at the freeze, m controlled by the attacker and l by honest users. By knowledge soundness, an accepted recovery proof for a commitment C yields a seed s' with F(s') = C. A double spend is a multi-target second pre-image attack on F against the attacker’s own m commitments, for which it already holds one seed each and needs a different one. A theft is a multi-target pre-image attack on F against the l honest commitments.
Second pre-image attacks after the freeze
Since Pedersen spreads uniform 496-bit inputs close to uniformly, the set of openings of a commitment C has about 2^{496} / 2^{251} = 2^{245} elements. Although a quantum attacker can compute discrete logs, the recovery verifier does not ask for an opening of C: it asks for a seed s' whose image H(s') lies in that set. Because H is a random oracle, a fresh seed lands there with probability 2^{245} / 2^{496} = 2^{-251}.
Note that second pre-images do exist: F maps 2^{256} seeds onto about 2^{251} group elements, so each commitment has about 32 seed pre-images. The attacker holds one seed for each of its m commitments and needs a different one for any of them. Excluding its own seeds barely changes the attack cost. A fresh seed opens one of its m commitments with probability about m \cdot 2^{-251}. A grover search therefore needs about \sqrt{2^{251} / m} evaluations of F.
Pre-image attacks after the freeze
Although a quantum attacker is able to efficiently describe the set of openings of any commitment C in the tree, it does not control the output of the random oracle H. The pre-image search is over the l honest users’ leaves and thus also costs \sqrt{2^{251}/l} with grover.
Spendability
An honest user holds s, and H is deterministic, so recomputing k || r = H(s) yields the C in the tree and the nullifier hash h = \mathrm{Pedersen}(k). Completeness of the zkSNARK then ensures the recovery proof is accepted.
Social Layer Coordination
For protocols yet to be deployed, we recommend the recovery verifier to ship together with the pool. Already existing upgradeable pools would have to install it through governance instead. The only privileged action should be a one-way freeze disabling the old verifier such that whoever holds it can stop the old withdrawal path and strand notes that were not derived from a seed, but cannot steal. Note that immutable pools cannot install a recovery verifier at all: for those, a social layer effort is needed to encourage migrating funds to pools that offer at least a recovery path.