many thanks to @Pierre for discussions and comments that led to this write-up.
see the github repo for benchmarks.
Privacy applications like Tornado Cash and RAILGUN may be able to use EIP-8141 frame transactions to drop their off-chain relayers and have strong censorship resistance guarantees. That is only possible if the transactions could propagates through the public mempool, which caps validation budget at MAX_VERIFY_GAS = 100k.
We show that the lowest required verification budget for such transactions sits at 211,828 gas, a single-note spend, while the largest deployed one (spending and nullifying eight notes) needs at least 351,828 gas. Hence, we strongly encourage the MAX_VERIFY_GAS to be increased to at least 250k, which admits most typical transactions.
Throughout, a spend consumes ν nullifiers and creates m new note commitments, and its proof carries ℓ public inputs. A Tornado withdrawal is ν = 1, m = 0. We focus on Groth16 proofs only, which are most widely used and cheapest SNARKs to verify on-chain.
1. What the cap counts
The sum of limits.execution across the validation prefix, plus the intrinsic cost of validating tx.signatures, must not exceed MAX_VERIFY_GAS.
| gas | included | ||
|---|---|---|---|
| proof verification execution | see section 3 | yes | pairing check, public-input accumulation, and the glue around them, all of it the frame’s own execution |
frame entry, access to resolved_target |
100 | yes | charged inside the frame’s limits.execution; warm, since a recognised self_verify frame must target tx.sender |
ARBITRARY signature validation |
100 | yes | the signature-validation intrinsic is the one intrinsic term the cap counts |
KEYED_NONCE_FIRST_USE_GAS |
20,000 · ν | yes | EIP-8250 deducts it from the remaining gas of the frame executing the payment-scoped APPROVE |
| the proof and the hashed preimage | 16 per non-zero byte | no | signature_data_cost for the proof, which rides in the ARBITRARY entry, and frame_data_cost for the preimage; both are frame_tx_intrinsic_gas |
FRAME_TX_PER_FRAME_COST |
475 per frame | no | frame_tx_intrinsic_gas |
FRAME_TX_INTRINSIC_COST |
12,000 per transaction | no | frame_tx_intrinsic_gas |
| EIP-8272 recent-root reference | 4,402 + ~1,184 | no | intrinsic, added by EIP-8272 |
2. Minimising the verify frame
Keyed nonces replace the nullifier write. Currently privacy protocols store spent nullifiers in contract state: a cold SLOAD plus a zero-to-nonzero SSTORE, 22,100 per nullifier. Under EIP-8250 the nullifier is the nonce key and inclusion marks it used atomically with payment approval. The protocol charges only 20,000, which is cheaper but it still counts towards the mempool verification cost cap.
Recent roots remove the last state read. Tornado walks a 100-entry root ring buffer; RAILGUN reads a rootHistory mapping. Both are reads of storage the validation prefix may not touch. EIP-8272 supplies the root as a transaction field checked before execution, which is readable with RECENTROOTREFLOAD at 3 gas. Its 4,402 intrinsic and ~1,184 gas cost of calldata fall outside the cap.
Defer everything that is not verification. Transfers, note commitment insertions, logs, and account creation belong in sender frames. For Tornado that is 78,765, and for RAILGUN it is the dominant cost of the protocol: inserting two commitments into a depth-16 tree is 17 calls to the deployed PoseidonT3 library at 29,616 gas each, which is a whopping 503,472 gas in total. That is 1.6x of its proof verification gas cost!
Use sigHash to bind tx to the proof, and remove relayer-related public inputs. Tornado’s circuit public inputs include recipient, relayer, fee and refund, which are held in the constraint system by four dummy squares, purely to bind the proof to the transaction (otherwise the proof could be re-pointed while it sits in the mempool). relayer, fee, and refund become unnecessary when we switch to native AA (there is no relayer to be paid anymore), so we simply remove them. However, the proof still needs to be binded to recipient.
A verification frame that is not binded with the sigHash remains malleable, and the subsequent sender frames could be changed while verify frame still authenticates, consumes nullifers, and pays! And when the spend authority lies within a proof, the proof has to binded to transaction with sigHash. Adding sigHash as a public input allows us to remove recipient, since recipient would be specified in a subsequent sender frame that is committed to by the sigHash already. TXPARAM(0x08) returns sigHash for 2 gas and the contract hashes nothing.
For Tornado that reduces public inputs from ℓ = 6 to ℓ = 3 (removing recipient, relayer, fee and refund, while adding sigHash). Note that the proof must be supplied as an ARBITRARY signature entry rather than in frame data to avoid circular dependency with sigHash. Also sigHash covers fee parameters, so a pending transaction cannot be bumped without generating a new proof; Appendix B proposes a fix to decouple max_fee_per_gas and the proof.
Compress every public input into one. Each public input costs 6,645 in the verify frame (an ecMul, an ecAdd and the loop around them). After the reduction above Tornado carries three and RAILGUN still carries 2 + ν + m public inputs. That is 13,290 and 73,095 gas respectively above a single-input verifier.
We can fold all public inputs into one. The contract computes c = sha256(root ‖ nullifiers ‖ commitments ‖ context) % r from frame data, passes c as the single public input, and the circuit recomputes the same hash over the preimage it holds privately. A sender frame that needs the values back recomputes c the same way and compares, reading the digest out of the verify frame’s data with FRAMEDATALOAD. ℓ = 1, for any ν and any m.
The hashing does still scale with the list, just barely: precompile 0x02 costs 60 + 12 per 32-byte word, and with the FRAMEDATACOPY and memory around it the frame pays roughly 240 gas over Tornado’s three elements and 380 over RAILGUN’s twelve. That is about 15 gas per additional nullifier, against the 20,000 the same nullifier adds through the nonce surcharge, so it disappears into the pool glue logic and the floor in section 3 does not move with it.
The cost is entirely the prover’s, because Groth16 verification is constant in circuit size. Measured with circom --r1cs, circomlib’s SHA-256 costs 31,264 constraints per 64-byte block plus 255 per field element decomposed into bits, so Tornado’s three-element commitment pads to two blocks and adds 63,294 against its own 36,448-constraint circuit: 2.7x the prover work. Here we take this trade off anyway, because the question is, what is the absolute minimum MAX_VERIFY_GAS for which a privacy protocol could still utilize frame transactions in public mempool. Appendix A works out this tradeoff a bit more carefully, in two variants, both trading a slightly higher verification cost for a significantly lower circuit size.
Use gas optimized verifiers and hardcode the verifying key in contract code. Tornado’s 2019 websnark verifier costs 244,401 at ℓ = 6 against the current snarkjs assembly template’s 223,853. RAILGUN is worse off on two counts: its memory-struct loop costs 8,522 per public input against the template’s 6,645, and it reads its verifying key out of a storage mapping, which is 64,288 of cold slots at 2×2 and 88,393 at 8×2.
The storage read costs more than gas. A privacy pool on EIP-8141 routes every user through one shared sender contract, so its users transact in parallel only if several of that sender’s transactions can be pending at once. EIP-8250’s keyed-nonce concurrency permits exactly that, but only for transactions whose validation trace records no sender storage reads. A verifying key in storage is such a read.
3. The floor
Every figure is one verify frame with all six reductions of section 2 applied. Verification is fixed at public input length ℓ = 1, so the only thing that varies across shapes is the number of nullifiers ν.
| ν | shapes | verification | 20,000 · ν | entry, sig, logic | total cost |
|---|---|---|---|---|---|
| 1 | Tornado withdrawal, RAILGUN 1×2 | 190,628 | 20,000 | 1,200 | 211,828 |
| 2 | RAILGUN 2×2, RAILGUN 2×3 | 190,628 | 40,000 | 1,200 | 231,828 |
| 8 | RAILGUN 8×2 | 190,628 | 160,000 | 1,200 | 351,828 |
| 16 | `MAX_NONCE_KEYS`, the protocol maximum | 190,628 | 320,000 | 1,200 | 511,828 |
Verification is the current snarkjs template measured at ℓ = 1; entry, signature and pool logic are 100 + 100 + ~1,000, the last estimated and covering the frame’s TXPARAM reads, its RECENTROOTREFLOAD, the sha256 over the preimage and the nonce_keys_hash check.
What remains is irreducible: a BN254 pairing check at 181,000, and the protocol’s own 20,000 per nullifier. Nothing fits in 100,000, and no choice of proof system, hash or frame layout available to these applications changes that.
4. Recommendation
| cap | admits |
|---|---|
| 100,000 | nothing; the BN254 pairing check alone is 181,000 |
| 250,000 | every common shape: Tornado and RAILGUN up to two nullifiers, 231,828 |
| 300,000 | up to five nullifiers, and every common shape even without public input compression |
| 400,000 | RAILGUN’s 8×2 at 351,828 |
| 525,000 | the protocol’s maximum, 16 nullifiers at 511,828 |
At least 250k, below 200k the use case does not exist. 250,000 admits every typical shape people transact in, if the circuit carries section 2’s public input compression trick, which makes client-side proof generation meaningfully slower. Appendix A introduces strategies that would avoid significant blowup in circuit size, but still fits most typical transactions under 250k.
Appendix A. Two ways to avoid the in-circuit hash
Section 2 folds every public input into one SHA-256 commitment and charges the prover for it. A protocol unwilling to pay that proving cost has two alternatives: carry the inputs and pay for them at the verifier (A.1), or keep one commitment but let the contract and the circuit hash with different functions (A.2).
A.1. Split the inputs based on type
Values the circuit only binds (recipient, relayer, fee, the transaction context) sigHash already commits to all necessary binding values and TXPARAM(0x08) returns it for 2 gas, so the circuit pins a single input with one dummy constraint and the contract hashes nothing. RAILGUN’s hashBoundParams is the pre-AA version of this, a keccak over an ABI-encoded struct that the contract pays for.
Values the circuit produces that the verify frame never inspects (the output commitments) fold under one Poseidon commitment that a sender frame opens, reading the digest from the verify frame’s data with FRAMEDATALOAD for 3 gas. Poseidon because the commitment must be cheap in-circuit and computable on-chain. Opening costs 29,616 per two elements, in a sender frame, outside the cap. If the opening fails the sender frame reverts, and the attacker has burned a real note to do it! There is no threat to the pool and honest users, only attacker (i.e. owner of the burned note) hurts.
Values the verify frame must check (the root, and the nullifiers) cannot fold at all without in-circuit hashing, because the frame needs them in hand; (a) they could be carried directly, one public input each, we would pay higher verification cost; or (b) they could be compressed with sha-256, and we eat constraints overhead.
The following table compares the gas cost (which counts towards the MAX_VERIFY_GAS) and the circuit size under these different strategies.
| verify frame | ν | minimum gas cost | (a) ℓ | (a) gas cost | (a) circuit size reduction | (b) ℓ | (b) gas cost | (b) circuit size reduction |
|---|---|---|---|---|---|---|---|---|
| Tornado withdrawal | 1 | 211,828 | 3 | 225,119 (+13,291) | −63% | 2 | 218,473 (+6,645) | −0.3% |
| RAILGUN 1×2 | 1 | 211,828 | 4 | 231,764 (+19,936) | −81% | 3 | 225,119 (+13,291) | −27% |
| RAILGUN 2×2 | 2 | 231,828 | 5 | 258,408 (+26,580) | −80% | 3 | 245,119 (+13,291) | −40% |
| RAILGUN 2×3 | 2 | 231,828 | 5 | 258,408 (+26,580) | −80% | 3 | 245,119 (+13,291) | −40% |
| RAILGUN 8×2 | 8 | 351,828 | 11 | 418,279 (+66,451) | −71% | 3 | 365,119 (+13,291) | −20% |
A.2. Use hybrid compression for data matching
ePrint 2025/1500 looks at problem of compressing a shared input to the circuit and contract, and proposes a method that avoids doing non-SNARK-friendly hashes in circuit or doing SNARK-friendly ones in contract!
The contract computes α = SHA-256(stmt); the user supplies β = Poseidon(stmt), which the contract never checks; both sides then evaluate a universal hash γ = Σ (α+β)^(j-1)·x_j over the statement, one mulmod and one addmod per element on-chain against one constraint per element in-circuit. The circuit proves β and γ, the contract checks α and γ, and forging a statement means colliding a universal hash under a random seed neither side controls (i.e. Fiat-Shamir). Neither side ever runs the other’s hash, and the statement is three public inputs, (α, β, γ), for any ν and any m. Note that the circuit size for A.1.(a) and A.2. is roughly the same. The following is a comparison of their verification gas cost.
| verify frame | ν | statement length k | ℓ under A.1.(a) | A.1.(a) gas cost | A.2 gas cost | difference |
|---|---|---|---|---|---|---|
| Tornado withdrawal | 1 | 3 | 3 | 225,119 | 225,194 | +75 |
| RAILGUN 1×2 | 1 | 5 | 4 | 231,764 | 225,244 | −6,520 |
| RAILGUN 2×2 | 2 | 6 | 5 | 258,408 | 245,269 | −13,139 |
| RAILGUN 2×3 | 2 | 7 | 5 | 258,408 | 245,294 | −13,114 |
| RAILGUN 8×2 | 8 | 12 | 11 | 418,279 | 365,419 | −52,860 |
Tornado’s statement is already three elements, so hybrid compression is unable to reduce the cost. However, every RAILGUN shape carries more than three public inputs, and hybric compression takes all of them for two public inputs, 13,290, plus a few hundred gas to evaluate the universal hash function; slightly above section 3’s floor. Hybrid compression makes most common Railgun shapes fit under the 250k threshold, with almost no circuit overhead.
Appendix B. Decoupling fee and proof
As we mentioned earlier, binding the proof to sigHash binds it to the fee as well, so a user who wants to bump the gas price has to generate a proof again. The verify frame does not have to use sigHash, instead, it can calculate its own digest, which skips over the max_fee_per_gas, and bind to that instead. FRAMEPARAM exposes mode, flags, resolved_target, value, both limits and len(data), FRAMEDATACOPY gives the frame data and TXPARAM(0x09) the frame count, so hashing the frame list together with the chain id, tx.sender and the nonce costs a few hundred gas. To that we add TXPARAM(0x03), the priority fee, and leave out TXPARAM(0x04), max_fee_per_gas. It is still one public input and the overhead is very small. Everything outside the frame list is still unbound, so the frame pins it with three checks costing a few gas each. TXPARAM(0x07) == 0 rejects injected blobs, whose cost TXPARAM(0x06) includes. TXPARAM(0x0B) == 1 rejects appended ARBITRARY signature entries, which are not protocol-validated, cost the payer 16 gas per byte, and count against MAX_VERIFY_GAS.
The digest binds the priority fee, so the proof can not be used to authorize a transaction that pays a higher gas price than base_fee + max_priority_fee_per_gas, which makes the tip rather than the cap the user’s real spend limit; however, if the base fee moves quickly, the user can adjust max_fee_per_gas and replace the transaction without re-computing a new proof.