# Adversarial procurement in blockchains

Crypto.world

> Modern blockchains increasingly outsource costly computation — zero-knowledge proofs for a zk-EVM, block building, RPC service — to specialized parties, exploiting the asymmetry between the effort…

**arXiv**: 2605.05559

**Published**: 2026-05-07

**Authors**: Maryam Bahrani, Michael Neuder, S. Matthew Weinberg

## AI summary

## Overview

**Research area:** Computer Science and Game Theory (cs.GT), specifically algorithmic mechanism design applied to blockchain protocol security; accepted at the 2026 ACM SIGSAC Conference on Computer and Communications Security (CCS '26), The Hague, Netherlands, November 15–19, 2026.

**Technical level:** Advanced. The paper is written for readers comfortable with mechanism design, incentive compatibility, mixed-strategy equilibria, and worst-case (Byzantine) adversarial analysis.

**Scope (one sentence):** The paper formalizes how a blockchain protocol should procure expensive-but-easily-verified work (such as ZK proofs) from a permissionless, pseudonymous set of provers when up to some fraction of them may behave adversarially, and derives an optimal, practically implementable payment design.

## What This Paper Is About

Modern blockchains increasingly outsource costly computation — zero-knowledge proofs for a zk-EVM, block building, RPC service — to specialized parties, exploiting the asymmetry between the effort needed to *produce* a result and the near-trivial effort needed to *verify* it. The catch is liveness: a malicious provider can simply switch off its machines and halt the chain, so the protocol must pay for redundancy without overpaying. The paper asks how to design a payment rule that minimizes the worst-case combined cost of overpaying provers and suffering a liveness fault, given `n` provers, at least `h < n` of whom are honest, and a penalty `C` for failing to obtain a proof.

## Key Contributions

1. **A formal adversarial procurement model for blockchain work.** The authors define a mechanism-design problem in which `n` pseudonymous provers each face a normalized proof-generation cost of `1`, at least `h` are honest, and the protocol's loss is evaluated against a worst-case Byzantine adversary controlling `a := n − h` provers (Definition 2.2). Payment rules are restricted to depend only on the *realized set* of deliveries, not on timing or ordering.
2. **An explicit, near-optimal "designated" mechanism.** The proposed mechanism picks a single deterministic "leader" or designate plus a committee of `k` backups each asked to prove with probability `s < 1`. It is proven optimal among all mechanisms for many values of `n` and `h` — including regimes that capture current prover markets — and is an additive `1`-approximation to the optimal mechanism for *all* `n, h` (Theorem 3.11), meaning it is optimal up to the cost of one extra proof.
3. **A tractable lower bound and a characterization against a weaker adversary.** Lemma 3.4 constructs a lower-bound objective `g(s)` by restricting the adversary to either fully honest or fully non-delivering play. Against this weaker adversary the optimum is fully characterized as either *designated* or *symmetric* (Lemma 3.8), and the paper shows when these remain optimal against the full adversary (Lemmas 3.10, 3.13, 3.15).
4. **Asymptotic analysis and the value of slashing.** The worst-case cost of the optimal mechanism scales as `O((n/h) · log C)` — logarithmic in the liveness-fault penalty and inflated by the adversarial fraction. The paper further shows that permitting negative payments (staking and slashing) can greatly improve the optimum in certain asymptotic regimes (Lemma 3.29).

## Main Findings

- **Logarithmic dependence on the fault penalty:** The loss of the optimal protocol scales logarithmically in `C`, the cost of a liveness fault, scaled up by the adversarial fraction of the network; formally `O((n/h) · log C)`.
- **Leader-plus-committee is the right shape:** In many regimes the optimal equilibria have an intuitive structure — a single random node designated as primary worker with a committee as fallback — explicitly reminiscent of leader-based consensus mechanisms.
- **The designated mechanism is a safe default:** For every `n, h`, it is within an additive `1` (i.e., one proof's cost) of the optimal mechanism; for many parameters, including those matching current prover markets, it is exactly optimal (Remark 11).
- **Naïve schemes fail under worst-case behavior:** Paying a randomly chosen subset of `k` provers `1 + ε` (Example 3.1) either deterministically incurs the penalty `C` if `k ≤ a`, or forces paying all `k(1 + ε)` every round if `k > a`. The lottery rule (Example 3.2) lets the adversary withhold all corrupted deliveries, pushing failure probability from `(1 − s)^n` to `(1 − s)^h`. Paying each deliverer exactly `1` (Example 3.3) exposes the protocol to the adversary choosing between cheap-but-risky and expensive-but-safe extremes.
- **Lottery is a 2-approximation:** Despite its weaknesses against an adversary, the fixed-prize lottery payment rule is shown to be a `2`-approximation of optimal (Lemma B.3).
- **Structure of the optimum under a weakened attacker:** The lower-bound objective's two `max` branches are equal at the minimizer (Lemma 3.5), reducing the problem to a cleaner constrained program whose solutions are either designated or symmetric committee equilibria.
- **Slashing helps in identifiable regimes:** When mechanisms may impose negative payments — enabled by each prover posting a deposit of `B/n`, so that `p_i(d) ≥ −B/n` — the optimal solution can be greatly improved in certain asymptotic regimes (Lemma 3.29).
- **Robustness below super-majority honesty:** Unlike consensus protocols, the procurement mechanism functions even if fewer than a super-majority of nodes are honest, though expected cost rises as the honest fraction falls (Fig. 3, Lemma 3.24).
- **Practical recommendation:** Based on assumptions about the economic impact of a liveness fault (Remark 16), SNARK proving costs (Remark 17), the proportion of honest provers (Remark 19), and capital already staked by Ethereum validators (Remark 20), the authors advise practitioners to adopt the optimal designated mechanism (Remark 21). The truncated paper content does not report the specific numerical values behind these remarks.

## Methodology in Plain English

The authors set up an optimization problem rather than running experiments. A protocol chooses two things: a strategy profile saying how likely each prover is to deliver, and a payment rule mapping the set of proofs actually received to payments. Provers are risk-neutral and profit-maximizing, so the protocol must be *incentive compatible* — each prover must prefer following the prescribed strategy when everyone else does too. On top of that, the designers take a worst-case view: an adversary who knows the mechanism, chooses which `n − h` provers to corrupt, and dictates their behavior (either withholding proofs to cause a fault, or delivering extra proofs to inflate payments), all without seeing the honest players' private coin flips. The protocol's loss is the sum of payments plus `C` if no proof arrives, maximized over adversary play. Because the direct optimization has exponentially many adversary constraints, the authors construct a lower bound that depends only on the strategy profile, show the minimizing profile sits where two branches of that bound meet, and use structural lemmas to prove that a simple leader-plus-committee design attains or nearly attains the bound. A threshold-encryption sketch shows how the required private randomness could actually be implemented on-chain, with validators publishing encrypted proof-or-dummy payloads and decrypting shares alongside their consensus votes.

## Why This Matters

**Impact on research.** The paper joins two literatures that are usually kept apart: Sybil-proof / false-name-proof procurement auction theory (Yokoo et al. 2004; Conitzer and Yokoo 2010; Pan et al. 2024; Garimidi et al. 2026) and the "Price of Malice" line of work on mixing strategic and malicious agents in routing games (Karakostas and Viglas 2003; Moscibroda et al. 2006). It contributes a rare case where a simple, recognizable mechanism is provably near-optimal in a Byzantine setting, and it leaves a clean open characterization problem.

**Real-world applications:**

- **zk-EVM proving markets:** Selecting and paying provers who produce validity proofs for Ethereum blocks, where a missing proof means a skipped slot.
- **Proposer-Builder Separation and relays:** The same leader-plus-fallback and slashing logic applies to outsourcing block construction and verifying delivered value.
- **Verifiable AI inference via TEEs:** The model covers any task where the costly step is trusted-hardware inference and the cheap step is checking a hardware attestation.
- **General "ZK coprocessor" and heterogeneous compute marketplaces:** Any two-sided market matching off-chain computation to on-chain verification, including broker-mediated designs such as Ritual's.

**Industry relevance.** The paper engages directly with deployed and announced systems — Succinct (fixed prize, effectively a Tullock contest per Garimidi et al. 2025), Axiom, EigenCloud, Brevis, Ritual, =nil, and RISC Zero — and argues its recommendations are actionable for these teams. It is also positioned against Ethereum's stated endgame of scaling via zk-EVM and real-time proving.

## Future Directions

- **Fully characterize the remaining regimes.** Section C.1 acknowledges parameter ranges where the mechanism optimal against the weaker adversary is not implementable against the full adversary; the authors leave a complete characterization as an open problem, noting the designated mechanism remains an additive `1`-approximation there.
- **Design and standardize prover-privacy schemes.** The threshold-encryption and time-lock-puzzle constructions are sketched only at a high level; precise mechanisms for hiding honest parties' delivery randomness until consensus votes are cast remain implementation work.
- **Extend beyond delivery-set-based payments.** The model deliberately excludes order- and time-based payment rules (bounties, races) because of latency races, winner-take-all concentration (ZK proving has no randomness, so the fastest prover deterministically wins), and manipulable timestamps; analyzing whether any such rule is ever worth its risks is left open.
- **Transfer the framework to non-proof domains.** The authors conjecture the paradigm of outsourcing expensive-but-verifiable work will spread to TEE-based inference, ZK coprocessors, and general heterogeneous compute, and that the qualitative lessons carry over.

## Target Audience

Protocol designers and researchers working on Ethereum scaling, PBS/MEV, and prover markets; mechanism-design and algorithmic game theory researchers interested in Sybil-proof procurement and mixed strategic-adversarial models; and engineers at ZK proving, coprocessor, and verifiable-compute companies who need concrete guidance on how many provers to solicit and how to structure rewards and slashing. Readers should be comfortable with formal game-theoretic definitions; the practical recommendations in Section 4.1 are accessible to a broader technical audience.

## Authors’ abstract

An emerging blockchain protocol design pattern leverages the asymmetry between the computational effort in performing versus verifying tasks. For example, cryptographic validity proofs (e.g., SNARKS) require the prover to expend significant effort demonstrating the correctness of their claim, while the verifiers benefit from extremely easy validation. The operationalization of this paradigm requires efficiently soliciting the performance of expensive tasks in pseudonymous,…

[The full abstract on arXiv](https://arxiv.org/abs/2605.05559)

[Read the original paper](https://arxiv.org/abs/2605.05559)

---

Canonical: https://crypto.world/paper/adversarial-procurement-in-blockchains-2605.05559
