Citation

Bahrani, M., Neuder, M., Weinberg, S. M. “Adversarial procurement in blockchains.” arXiv:2605.05559v1 [cs.GT] (May 7, 2026). Ritual / Princeton (Neuder + Weinberg). EF Grant FY25-2276 + NSF CAREER Award CCF-1942497.

Core Question

The L1-zkEVM design pattern hinges on verifiable outsourcing: the protocol delegates an expensive task (writing a ZK proof of correct EVM execution) to specialized provers, while every validator verifies the proof cheaply. One correct proof per block is enough. So the protocol-design question becomes:

How do you incentivize at least one correct proof in a pseudonymous, adversarial environment without overpaying?

The two failure modes have asymmetric costs:

  • Liveness fault (no proof produced) → chain halts → economic catastrophe of magnitude C
  • Overprocurement (paying many provers when one would do) → linear waste

The protocol must minimize max(C × Pr[fault], expected payments).

Model

  • n pseudonymous provers, at least h < n honest (worst-case adversarial bound).
  • Each proof costs 1 to produce (normalized).
  • Penalty C if no proof is produced.
  • Mechanism designs a (possibly random) request rule + payment-as-a-function-of-submitted-proofs rule.
  • Incentive-compatibility requirement: each prover, given that all others follow the mechanism, optimizes their own payoff by also following.

Worst-case lens: protocol designer accounts for any adversarial behavior the n − h malicious provers might pursue (drop the proof to cause a liveness fault; submit unrequested proofs to inflate payment, etc.).

Headline Results

1. Logarithmic loss

The optimal protocol’s worst-case loss scales logarithmically in C (the cost of a liveness fault), scaled by the adversarial fraction of the network. Crucially: not linear, not constant — log.

Practical implication: if a chain halt costs $1B (C = 10⁹) and adversaries control 25% of provers, the optimal protocol loses on the order of log(C)·adv-fraction per block — small in absolute terms.

2. Optimal structure: leader + fallback committee

In many regimes, the optimal mechanism has an intuitively simple structure:

  • Designate a single, random node as the primary worker (the most-likely-to-prove individual).
  • Use a committee as a fallback (those activated only if the primary doesn’t deliver).

This is strikingly reminiscent of leader-based consensus mechanisms — Bahrani–Neuder–Weinberg note this isn’t a coincidence: similar adversarial-procurement structures show up across blockchain design.

3. Slashing helps in some asymptotic regimes

Negative payments (slashing in blockchain parlance) become particularly helpful in specific asymptotic regimes — the paper characterizes when the marginal cost of recruiting honest behavior is best paid via slashing-the-defectors vs paying-the-actors.

4. Concrete practitioner advice

Section 4 (Rem. 4.5) gives an explicit mechanism that the authors recommend for L1-zkEVM prover markets, justified for the empirical orders-of-magnitude observed in Ethereum (Rems. 4.1–4.4).

Worked Examples in the Paper

SchemeWhatIssue
Single centralized proverCheapestLiveness-failure: prover can simply turn off; bribery-vulnerable (e.g., during MEV-volatility periods)
All n provers proveStrongest 1-of-n livenessn× overpayment; far too expensive in large-n regimes
Pick k < n and pay themTunableOptimal k depends on prover cost vs C; analyzed in Exs 3.1–3.3
Fixed prize split among all submittersTunableDifferent incentive-compatibility profile from per-request payments

Why the Result Matters

For L1-zkEVM (EIP-8025 and beyond)

The L1-zkEVM roadmap (covered in L1 zkEVM: Optional Execution Proof Verification (EIP-8025)) currently leans on optional/altruistic proving for EIP-8025’s opt-in phase. Once proving becomes mandatory in the protocol, the prover market needs an explicit mechanism. Bahrani–Neuder–Weinberg’s leader-and-committee structure is the recommended baseline, with slashing applied in the asymptotic regimes where it dominates.

Beyond zkEVM

The paper explicitly notes the model’s applicability to any permissionless delegation with concern for liveness faults (§ 1.2). Concrete fits:

  • Builder selection (a single builder chosen, fallback structure for liveness)
  • Relay selection (similar structure)
  • DA sampling (some-of-many primary, committee fallback for liveness)
  • Capacity oracles (cf Capacity Oracles — same structural problem)

Theoretical contribution

First adversarial-mechanism-design treatment of pseudonymous task procurement that explicitly couples the cost-of-liveness-failure with the payment-required-to-incentivize. Prior literature treated either the procurement question or the liveness/safety question, not both jointly.

Empirical Calibration (in the paper)

The authors ground their recommendation by plugging in observed Ethereum order-of-magnitude values for C (block-halt cost), prover cost, and adversarial fraction (Rems. 4.1–4.4). The recommended mechanism at Rem. 4.5 is the directly-deployable distillation.

Connection to Wiki

Open Questions

❓ Bahrani–Neuder–Weinberg model assumes proving cost is uniform across provers. Real prover markets have heterogeneous hardware — does the leader-and-fallback result generalize, or does heterogeneity favor different structures?

❓ The mechanism is designed worst-case. What’s the average-case improvement when adversarial fraction is small (typical Ethereum case)?

❓ Slashing requires committed stake from provers — but L1-zkEVM provers may be GPU operators outside the validator economy. How is the staking integrated?

See Also