Technical Summary: Adversarial Procurement in Blockchains

Problem Statement

The paper addresses the challenge of adversarial procurement in blockchain protocols, specifically within the context of emerging designs that leverage the computational asymmetry between performing and verifying tasks (e.g., Zero-Knowledge proofs, or SNARKs). In these systems, a protocol must outsource expensive computational tasks (like generating a validity proof for a block) to a set of $n$ pseudonymous, untrusted provers.

The core problem is designing a mechanism that:

1. Incentivizes at least one prover to perform the task (ensuring liveness).
2. Minimizes economic loss in the worst-case scenario where up to $n-h$ provers are adversarial (Byzantine) and may deviate from the protocol to cause a liveness fault (no proof delivered) or induce overpayment.
3. Operates without trust, as provers have no reputation and cannot credibly commit to future actions.

The authors model this as a mechanism design problem where the protocol designer seeks to minimize the sum of payments made and the penalty $C$ incurred if no proof is delivered, assuming an adversary controls a subset of provers and acts to maximize the protocol's loss.

Methodology

The authors formalize the problem using a game-theoretic framework:

• Setup: There are $n$ provers, $h$ of whom are honest. The cost of generating a proof is normalized to 1. If no proof is produced, the protocol incurs a liveness penalty $C$.
• Adversary Model: The adversary can corrupt up to $a = n-h$ provers. The adversary observes the mechanism and chooses the worst-case behavior (either refusing to deliver proofs to trigger the penalty $C$, or delivering proofs to manipulate payments).
• Objective: Minimize the worst-case loss $\ell(p, s)$, defined as the expected total cost (payments + penalty) under the worst-case adversarial strategy, subject to the constraint that the mechanism is incentive-compatible (honest provers maximize utility by following the protocol).

To make the problem tractable, the authors:

1. Derive a lower bound function $g(s)$ on the optimal protocol loss, parameterized by the strategy vector $s$ (the probability each prover delivers a proof). This bound assumes a "weakened" adversary that chooses between two extreme strategies: acting fully honestly or fully refusing to deliver.
2. Analyze the minimizers of this lower bound, characterizing them as either Designated Uniform Committee Equilibria (one deterministic leader + a committee of randomizers) or Symmetric Committee Equilibria (a committee of randomizers with no designated leader).
3. Investigate implementability: determining if a payment rule exists that induces these equilibria while achieving the lower bound cost.
4. Extend the analysis to include negative payments (slashing/staking), where provers post collateral that can be forfeited if the protocol detects an attack.

Key Contributions and Results

1. Characterization of Optimal Equilibria

The paper proves that the minimizers of the lower bound $g(s)$ are exclusively of two types:

• Designated Equilibria: One prover is designated to deliver with probability 1, while a committee of size $k$ delivers with probability $s \in (0, 1)$.
• Symmetric Equilibria: A committee of size $k$ delivers with probability $s$, and no single prover is designated.

2. Approximation Guarantees

• Additive 1-Approximation: The authors prove that for any payment rule and equilibrium, there exists a designated equilibrium whose loss is at most 1 unit (the cost of a single proof) higher than the optimal loss (Theorem 3.1).
• Implementability: All designated equilibria are implementable with a simple payment rule (Lemma 3.4). In contrast, symmetric equilibria are only implementable under specific conditions (e.g., when $C$ is sufficiently large relative to $n$ and $h$), and often require complex payment structures or negative payments to be feasible.

3. Asymptotic Scaling

• Logarithmic Scaling: The worst-case loss of the optimal designated equilibrium scales as $O(\frac{\log C}{\tau})$, where $\tau = h/n$ is the fraction of honest provers. This indicates that even with a fixed fraction of adversaries, the protocol cost grows only logarithmically with the severity of the liveness penalty.
• Impact of Staking: Introducing a total stake $B$ (collateral) significantly improves the scaling. If $B$ is proportional to $C$, the loss scales as $O(1/\tau)$, effectively becoming constant relative to $C$.

4. Transition Dynamics

The paper analyzes the transition between designated and symmetric optimality as a function of $C$ (penalty magnitude) and $\tau$ (honesty fraction).

• For small $C$ or high $\tau$, the designated mechanism is optimal.
• For very large $C$, the symmetric mechanism becomes optimal in the lower bound analysis.
• However, due to implementability constraints, the designated mechanism often remains the practical choice even in regimes where the symmetric lower bound is lower, because the symmetric solution may require negative payments that are infeasible or complex to implement.

Significance and Practical Recommendations

The paper argues that the theoretical results provide actionable guidance for blockchain protocol designers, particularly for zk-EVM (Zero-Knowledge Ethereum Virtual Machine) and other verifiable outsourcing markets.

• Recommendation: The authors strongly recommend adopting the optimal designated uniform committee equilibrium. This design designates a single "leader" (or primary worker) to deterministically produce the proof, supported by a committee of "backups" that produce proofs with a calculated probability $s$.
• Justification:
  1. Simplicity: The payment rule is intuitive and resembles existing consensus mechanisms (e.g., leader-based consensus with attesting committees).
  2. Near-Optimality: The loss is at most one proof cost away from the theoretical optimum, which is negligible given current proving costs (often fractions of a dollar).
  3. Robustness: It handles the worst-case adversarial behavior effectively, scaling logarithmically with the penalty $C$.
  4. Feasibility: Unlike symmetric mechanisms which may require complex lottery-style payments or negative payments (slashing) to be optimal, designated mechanisms are always implementable with positive payments.

The paper concludes that while symmetric mechanisms are theoretically interesting and optimal in specific asymptotic regimes, the designated mechanism offers the best balance of theoretical optimality, implementability, and familiarity to the blockchain community. The authors note that their model applies broadly to any permissionless delegation problem involving liveness faults, including verifiable AI inference and TEE-based computations.