The fee paradox: why every smart-contract privacy mixer needs a relayer

The first time I read the Tornado Cash whitepaper I missed the fee paragraph. I noticed the Merkle inclusion, the nullifier hash, the snarkjs circuit. I did not notice the part where, to actually withdraw to a fresh address, you need somebody else to broadcast the transaction. It was buried under “operator/relayer” — a word I generously read as “convenience”. It is not a convenience. It is the load-bearing wall of every smart-contract privacy mixer in production.

This post is post 2 of 11 in the relayerless-privacy series. Post 1 introduced the framework $\mathcal{F}_{\text{RP}}$ and outlined what the rest of the series builds. Here we slow down on the fee paradox itself — what it is, why every system using fees in a public token suffers it, and the three approaches that resolve it.

Definition: the fee paradox

On any blockchain $\mathcal{B}$ with a fee-based inclusion mechanism:

1. To submit a transaction, the submitter’s address must pay a gas fee $f > 0$.
2. To hold gas, the address must have been previously funded.
3. Funding an address creates an on-chain link to the funding source.

Therefore, any address that submits a transaction has a traceable funding history. Any privacy-preserving withdrawal to a fresh (unfunded) address requires an external party to pay the gas fee.

Formally, in the fee paradox game:

1. User $\mathcal{U}$ deposits value $v$ into a shielded pool.
2. $\mathcal{U}$ wishes to withdraw to a fresh $\mathsf{addr}_{\mathsf{recv}}$ with no prior on-chain history.
3. Adversary $\mathcal{A}$ observes all transactions.
4. If $\mathcal{U}$ funds $\mathsf{addr}_{\mathsf{recv}}$ to pay gas, $\mathcal{A}$ traces the funding source.
5. $\mathcal{A}$ wins by linking the withdrawal to a prior deposit with non-negligible advantage.

The advantage is overwhelming. The deck is stacked because the chain literally requires an attestation from a funded account before it will include any state transition. Privacy at the cryptographic layer collides with funding at the consensus layer, and the consensus layer wins.

Why UTXO chains don’t have this problem

Bitcoin and Zcash inherit a different model. A UTXO transaction’s “fee” is the difference between input value and output value:

The miner takes $f$ as the implicit fee. There is no separate “gas account” that needs to exist beforehand. In Zcash specifically, a Sapling or Orchard transaction’s valueBalance field — the net flow from the shielded pool to the transparent pool — is the fee. The binding signature proves the value commitment balance. The miner is paid out of value the prover is already moving, signed by the prover, with the prover’s identity hidden by the ZK proof.

Result: Zcash is relayer-free by construction. Penumbra, Aleo, Namada, and Monero are too — for the same reason. They all run on chains whose native fee model is fee-from-balance, not gas-from-account.

The fee paradox is specific to account-model chains like Ethereum and Solana, where transactions require an explicit fee payer signature and the fee is debited from a known account.

Three approaches to resolution

The paper section §2.3 enumerates three approaches to resolving the paradox without a relayer:

Approach A — Protocol-Native Fee Abstraction via ZK Fee Proofs

The fee is extracted from the shielded pool inside the ZK proof itself. The proof attests that

where $f$ is a public input to the proof and $v_i, v'_j$ are private inputs. Pedersen commitments make this clean: with $C_i = v_i \cdot G + r_i \cdot H$ for input notes and $C'_j = v'_j \cdot G + r'_j \cdot H$ for output notes,

where $r_\Delta = \sum_i r_i - \sum_j r'_j$ is a blinding-factor residual that the prover demonstrates equals the right thing.

The validator extracts $f$ as inclusion compensation directly. The submitter does not need a public balance. This is what SPST does, and it’s the path the whole series builds toward.

Approach B — Nullifier-Derived Fee Authorization

A second derivation from the spending key, parallel to the nullifier:

The ZK proof proves both come from the same $(k, \rho)$, that $\mathsf{fee\_auth}$ encodes $f$, and that the underlying note has sufficient balance. The fee is bound to the nullifier cryptographically — no party can alter the fee post-proof-generation.

This is more invasive than Approach A (changes the nullifier scheme) but gives a stronger non-malleability property. Most production designs use Approach A; Approach B becomes interesting when the protocol wants stricter binding for compliance audits.

Approach C — Recursive Fee Amortization via Batch Proofs

For high-frequency private transactions, fold $n$ proofs into a single Nova-style accumulator:

The folded proof attests that all $n$ transactions are individually valid and that the cumulative fee $F_n = \sum_{k=1}^n f_k$ has been correctly accumulated. A single on-chain verification covers all $n$ transactions.

On Solana, with ~200,000 CU per Groth16 verification and a per-transaction limit of ~1,400,000 CU, batches of $n \leq 7$ fit within a single transaction’s compute budget. The amortised per-transaction CU cost drops by an order of magnitude.

Tradeoff summary

What the relayer-dependent protocols do instead

Tornado Cash, RAILGUN, and Light Protocol’s older privacy phase all chose none of the above. They use a relayer who pays the gas in the host chain’s native asset, takes a fee from the withdrawn amount, and broadcasts the transaction. The architecture is roughly:

The proof is binding — the relayer cannot redirect funds, cannot change the fee — but the relayer can refuse to broadcast. They can also log the user’s IP, timing, and metadata. In RAILGUN this is mitigated by routing over the Waku P2P network; in Tornado Cash it was just an HTTPS endpoint. Either way: the relayer is a third party, and that third party is a regulatory and operational single point of failure.

What changes when fees are folded into the proof

Once the fee comes from inside the proof, three things become different:

1. The submitter does not need a balance. The transaction can be broadcast by the user themselves from a fresh address that has zero of the host chain’s native asset. The chain’s transaction-broadcasting interface accepts transactions from any party with a valid signature; that signature now binds nothing to the user’s identity.

2. The validator gets paid out of the shielded pool’s escrow. On Solana, this is realised by having the privacy program’s PDA hold a lamport reserve. The fee $f$ — proven inside the SPST proof — authorises a transfer from this reserve to the validator. The shielded pool’s internal accounting decrements by $f$. Every deposit replenishes the reserve.

3. Censorship surface collapses. There is no “approved relayer list” for an adversary to attack. There is no operator to subpoena. The user’s only dependency is chain liveness — and that’s what Solana’s PoS consensus guarantees.

This is the Self-Sovereignty Theorem in informal form. The next post (SPST) makes it formal.

Bibliography

• Pertsev, A., Semenov, R., Storm, R. (2019). Tornado Cash Privacy Solution v1.4. https://berkeley-defi.github.io/assets/material/Tornado%20Cash%20Whitepaper.pdf
• RAILGUN Documentation. Privacy System Architecture. https://docs.railgun.org
• Hopwood, D. et al. (2016–2026). Zcash Protocol Specification. https://zips.z.cash/protocol/protocol.pdf
• Pedersen, T. P. (1991). Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. CRYPTO 1991.
• Kothapalli, A., Setty, S., Tzialla, I. (2022). Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. https://eprint.iacr.org/2021/370

Previous: Series intro ← · Next: SPST: self-paying shielded transactions →