arXiv CSopen access

Adversarial procurement in blockchains

Adversarial procurement in blockchains Maryam Bahrani∗ Ritual

Michael Neuder∗• Princeton University

S. Matthew Weinberg◦ Princeton University

arXiv:2605.05559v1 [cs.GT] 7 May 2026

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, adversarial environments. We formalize this as a mechanism design question. The protocol balances the economic cost of a liveness fault, where the work is not completed, with the payments required to incentivize specific behavior from candidate suppliers. We show that the loss of the optimal protocol scales logarithmically in the cost of a liveness fault, scaled up by the adversarial fraction of the network. Further, we find that the optimal equilibria have an intuitive structure, allowing us to provide concrete advice to practitioners. Specifically, in many regimes, the optimum designates a single, random node as the primary worker and a committee as a fallback, which is reminiscent of leader-based consensus mechanisms. We also characterize the asymptotic regimes where having negative payments (i.e., slashing in blockchain parlance) is especially helpful.

1

Introduction

In the early days of Bitcoin, every user transacting on the network ran a full node and could easily mine blocks on their personal computers. Once the network became sufficiently valuable, however, specialization emerged. Miners who invested in better hardware and had a lower cost of electricity were able to capture larger shares of the block rewards. Even in its most basic form, this separation between miners and users was possible by leveraging the cryptographically asymmetric task of Proof-of-Work. The miners perform the difficult pre-image search of SHA-256, while the users of the chain can easily confirm that they were included in a valid fork by checking the value of the hashed nonce. This asymmetry has extended far beyond Proof-of-Work mining. Many core services of modern blockchains are outsourced, allowing for scale and adoption that would otherwise be impossible. For example, when sending locally signed transactions, most users will broadcast the signed transaction through a wallet interface that uses an external RPC provider (e.g., Infura (27)) rather than running a node and gossiping it to the P2P network directly.1 Similarly, users often confirm their transaction is included onchain via block explorers rather than running a consensus node locally. Outsourcing is no silver bullet, of course, as relying on any intermediaries introduces choke points and trust assumptions. Still, the ecosystem seems to have converged on the combination of selfcustody of private keys while relying on external parties to include and verify transactions as a reasonable trade-off between usability and self-sovereignty. ∗

Authors listed alphabetically. Author supported in part by the Ethereum Foundation: Grant FY25-2276. ◦ Author supported in part by NSF CAREER Award CCF-1942497. 1 RPC (remote-procedure call) providers expose simple blockchain APIs such as eth sendTransaction. •

1

Proposer-Builder Separation: outsourced block-building. Due to the rise of Maximal Extractable Value (MEV) (15) in the Ethereum ecosystem,2 even consensus participants now outsource key tasks. Specifically, creating a value-maximizing block is a complex task where specialized “builders” significantly outperform a representative “proposer” participating in Ethereum’s consensus protocol. Therefore, proposers outsource the job of creating a high-value block to builders, and rely on relays as trusted third parties to verify the value (and validity) of that block before proposing it in-protocol.3 This is the first notable example of unbundling the consensus “duties” that were homogeneous among validators. See Monnot (34) for a discussion of how this pattern can extend beyond block building to other parts of the consensus mechanism. A key aspect of Proposer-Builder Separation (PBS) is that every consensus participant (henceforth, validator ) can continue to verify the validity of each block. If only specialized actors can check block validity, then Ethereum loses its trustless verifiability, which is a core tenet of the protocol. Indeed, the famous “Endgame” post by Vitalik Buterin in 2021 highlights this as a key design criterion: “block production is centralized, block validation is trustless and highly decentralized, and censorship is still prevented” (10). So, the good news is that block building can be outsourced to highly specialized entities under PBS. The bad news is that, in order to maintain a meaningfully decentralized validator set, every validator must fully verify the contents in each block, which limits the viable throughput of the Ethereum Virtual Machine (EVM). That is, the EVM can proceed no faster than the slowest validator, which at present is set to accommodate, at minimum, a two-core CPU and a 10 MBit/s internet connection (18), in order to ensure wide accessibility to Ethereum validation (q.v., some hobbyists run on nodes on a Raspberry Pi (37)). But, Ethereum’s endgame is not to operate the EVM at the pace of a Raspberry Pi on a home internet connection; instead, Ethereum aims to scale up significantly via a Zero-Knowledge EVM (zk-EVM).4 In the zk-EVM, each block would contain a list of transactions, a claimed newState, and a ZK proof (henceforth, “proof”) that the EVM’s new state after executing the list of transactions from the original state is exactly newState. The potential scaling benefits of such an upgrade are immediate; since proof verification is computationally lightweight, Ethereum can maintain a highly decentralized set of validators who now only verify validity proofs and no longer even need to execute all transactions in a block, while allowing block content to be optimized by highly-specialized builders and proofs written by highly-specialized provers, thereby enabling the EVM to progress at the pace of the fastest specialized prover rather than that of the slowest executor.5 Given the recent advancements in ZK proving speed and architecture (31, 45, 7), the feasibility of “real-time proving” is now a near-term goal (24). 2

MEV describes the economic value created by the proposer’s unilateral control over the inclusion, exclusion, and ordering of transactions within a block. 3 See Heimbach et al. (26) for more details on Ethereum’s MEV market structure. 4 Again quoting Vitalik, “In 2027-30, large further gas limit increases, as ZKEVM becomes the primary way to validate blocks on the network” (11). 5 To clarify: by this, we mean that the current EVM must operate no faster than the slowest validator can download and execute transactions (to verify block validity). Notice that the zk-EVM is a scaling technology for both bandwidth and compute, as it allows placing the block contents into Ethereum blobs for validators to sample instead of fully downloading the transaction contents (40). Under this paradigm, the zk-EVM can operate at a faster pace, so long as someone in the network can both execute transactions and produce a correct proof (because sampling the transaction data and verifying the produced proof is sufficiently lightweight that the entire validator network can do so). Depending on the prover efficiency of the proof system, this may or may not be an improvement – on one hand, we operate at the pace of the fastest (rather than slowest) participant, but on the other, that participant must now both execute transactions and also write a ZK proof of correctness.

2

Verifiable outsourcing to untrusted sources. The above discussion motivates an exciting application of verifiable outsourcing in the blockchain space: Ethereum validators will outsource transaction execution to specialized “provers,” and verify only the proof that the endState is correctly computed. So, let us quickly consider a single, centralized, and highly specialized prover who is asked to prove every single zk-EVM block. Soundness of ZK proof systems guarantees that a malicious prover cannot trick validators into believing an incorrect endState, but nothing prevents a malicious prover from simply turning off their machines, causing a liveness fault. That is, if the ecosystem becomes overly reliant on a single prover, that prover can simply stop providing proofs and cause the chain to halt. Doing so could be a highly profitable act,6 and relying on reputational harm as the primary defense is completely antithetical to the premise of blockchain systems.7 A next idea is to build a network of (say) n provers, and ask every prover to prove every block. As long as at least one-of-n provers is honest, the proof is delivered. This solution is extremely secure for large n, but also correspondingly expensive: we really only need a single correct proof, but are paying for n. Some overhead is certainly necessary to avoid failure caused by malicious provers, inducing a trade-off. Still, there are many ways to navigate this – two simple examples include (a) pick a set of k < n provers and pay them to prove and (b) offer a prize of k to be split among all provers who submit proofs (discussed in Exs. 3.1 to 3.3). Are either of these optimal? If so, how does one optimize k as a function of the prover cost versus the harm caused by a liveness fault? Our Work. This work formulates an adversarial mechanism design question to capture this problem: a protocol has access to n untrusted provers and knows that at least h < n of them are honest. The goal is to design a procurement protocol that minimizes the worst-case economic harm caused by either a liveness fault (if no proof is produced) or overprocurement (if too many proofs are paid for). Importantly, depending on the payment rule, dishonest provers might harm the protocol either by not proving when asked to prove (thus inducing a liveness fault) or by proving when asked not to (thus, perhaps, inducing a higher payment). While prover markets in the upcoming zk-EVM is a core motivation for our model, our results provide insight into any problem of permissionless delegation with concern for liveness faults – see the end of Section 1.2 for a brief discussion of our model’s applicability to other domains.

1.1

Summary of results

Our main practical contribution is providing an explicit mechanism that we advise practitioners to adopt (Rem. 4.5), and arguing that it is feasible and optimal given the order of magnitude of various empirical values observed in the Ethereum ecosystem (Rems. 4.1 to 4.4). The theoretical contributions outlined below justify this recommendation. Section 2 formally introduces the model and focuses on the unique requirements of this domain. A single proof is needed, and a penalty of C is incurred if we fail to procure one. There are n pseudonymous provers capable of producing the proof for a cost of 1, h < n of whom are honest. Our goal is to design a mechanism that (perhaps randomly) requests proofs from a subset of participants and offers payments as a function of submitted proofs. This mechanism must be incentive compatible: for each prover i, provided that all other provers follow the mechanism, prover i optimizes their payoff by following the mechanism as well. We then take a worst-case lens and 6

By accepting bribes from proposers who want to steal MEV from the preceding block’s proposer during periods of market volatility, for example. 7 For example, significant resources in the PBS ecosystem are put towards maintaining relays, protocols (c.f., BuilderNet (20)), and Trusted Execution Environments (TEEs) that limit the damage a single builder can do, even though there are presently only a small number of dominant builders who are all known by name (41).

3

ask, for each such mechanism, if the n − h non-honest provers deviate from the mechanism in the worst possible way, how bad can our total cost be? Note that this includes both monetary payments and the procurement-failure penalty. In blockchain parlance, we assess the performance of a mechanism against a Byzantine attacker who adversarially chooses a set of n − h provers to control fully (whereas the remaining h will follow the mechanism – see Def. 2.2). Our core proposed mechanism is designated : pick a single “leader” (or “designate”) from whom to definitely request a proof, and a set of k “backups” from whom to request a proof with probability s < 1 (and, optimize k, s as a function of n, h). We prove: (a) for many n, h, including those that well-capture current prover markets, the designated mechanism is optimal among all mechanisms (Rem. 3.7), (b) for all n, h, the designated mechanism is an additive 1-approximation8 to the optimal mechanism (Thm. 3.1). We provide an extended discussion for applying these theoretical results to practice (Section 4.1). The use of specially nominated leaders, committees, and staking and slashing (negative payments) will be familiar to the blockchain community, due to their frequent use in the design of permissionless consensus mechanisms. We argue, based on reasonable assumptions about: the potential economic impact of a liveness fault (Rem. 4.1), SNARK proving costs (Rem. 4.2), the proportion of honest provers (Rem. 4.3), and the amount of capital already staked by Ethereum validators (Rem. 4.4), that the optimal designated mechanism should be adopted (Rem. 4.5). Section 3 contains significant further exploration of the problem. For example, we consider a weaker adversary (Lem. 3.1) against which we can fully characterize the optimal mechanism (Lem. 3.3). Specifically, the optimal mechanism against the weaker adversary is either designated or symmetric (a symmetric mechanism requests that each of k providers provide a proof with probability s).9 We moreover show that whenever a designated mechanism is optimal against the weaker adversary, that same mechanism is optimal against the full adversary (Lem. 3.4). We also show that in many regimes where a symmetric mechanism is optimal against the weaker adversary, that same mechanism is optimal against the full adversary (Lem. 3.5 and Lem. 3.6).10 Finally, Section 3 also analyzes the asymptotic cost of the optimal mechanism as a function of various parameters. Specifically, the worst-case cost of the optimal mechanism scales with O( nh · log C).11 We moreover demonstrate that if the mechanism permits negative payments, the optimal solution can greatly improve (Lem. 3.12). Negative payments are a common motif in blockchain design, where agents post collateral (stake) that is forfeited (slashed) as a result of unexpected behavior.

1.2

Related work

Reverse (or procurement) auctions have a long and rich history in the economics literature; see (17) as a reference text on the subject. As in traditional (forward) auction theory literature, however, most previous works rely on a fixed set of known identities, where the bidders can misreport with a single identity but cannot arbitrarily introduce new ones. There are a few notable exceptions, starting with Yokoo et al. (43), which introduced “false-name proof” mechanisms in the context 8

Recall that we’ve normalized the cost of producing a single proof to 1 – this means that the designated mechanism is optimal up to the cost of producing a single additional proof. 9 That is, a symmetric mechanism has the “backups” from a designated mechanism but not the “leader.” 10 To be explicit: this does not cover all regimes – there are parameter ranges for which the optimal mechanism against the weaker adversary is not implementable against the full adversary. See Section B.1 for discussion on these regimes. We leave as an open problem to fully characterize the optimal mechanism in these remaining regimes (keeping in mind that a designated mechanism is an additive 1-approximation). 11 Recall that C is the ratio of the penalty for a liveness fault to the cost of producing a single proof, and h/n is the fraction of honest provers.

4

of combinatorial auctions. Since that paper, the concept has been extended to other domains as surveyed in (14). Recent work by Pan et al. (36) demonstrates that under the standard quasilinear utility model of single-item auctions, the only “Sybil-proof” mechanism is the second-price auction with symmetric tie breaking. Another recent work by Garimidi et al. (23) studies the single-item procurement setting with Sybils, while also trying to avoid winner-take-all equilibria. The key distinction between our work and these works is that we consider both strategic users (by ensuring that the proposed mechanism is incentive compatible) and worst-case behavior (by evaluating mechanisms based on their performance with n − h provers adversarially deviating from equilibrium). Prior work also considers a mix of strategic and malicious behavior, specifically in routing games. Here, Karakostas and Viglas (28) first introduces the model, which is further studied in (4, 38). Moscibroda et al. (35) coins the term “Price of Malice” and calculated the value for an internet virus game. Our work differs from these in that we study a completely different game. Specific to prover markets, Wang et al. (42) introduces a two-sided ZK proof matching protocol to match users to provers. Their algorithm greedily assigns tasks and imposes system-level constraints to address issues such as misreporting capacity, creating Sybils, and failing to deliver when assigned. Ahmadvand et al. (1) study the problem of prover orchestration as a systems question, but without modeling the economic decisions of individual provers. From the industry side, a few prover markets have launched, and several others are in development. Succinct (39) posts a fixed prize to turn the procurement into a forward auction, in effect running a Tullock contest (see (22) for an extended discussion). Axiom (3), EigenCloud (30), Brevis (8), Ritual (5), =nil (29), and RISC zero (44) have all announced development of various ZK coprocessor and prover marketplaces. These proposals have various degrees of formalism; our approach, model, results, and recommendations are novel and provide actionable insights to these teams. In addition to the specific projects noted above, we conjecture that the paradigm of outsourcing expensive but verifiable work to a set of permissionless and specialized providers will continue to gain adoption for more general tasks beyond correctness proofs for Ethereum blocks. For example, our model captures a basic trusted-execution environment (TEE) implementation of verifiable inference of machine learning models.12 This type of off-chain proving for onchain verification was coined as a “ZK coprocessor” architecture by Axiom in 2023 (3). This concept has resurfaced many times since then. Notably, EigenLayer’s July 2025 rebrand to EigenCloud (30) and their announcement of verifiable AI inference as a specific target market (2) fits this model. Similarly, Ritual aims to build a two-sided marketplace for general heterogeneous computational tasks, and they propose using brokers to facilitate the matching of tasks to suppliers in an efficient way (5). Our qualitative lessons (Section 4.1) apply equally to any of these domains, and not just to Ethereum prover markets.

2

Model

Setup. There is a mechanism designer (“the protocol”) who wants to procure a proof from a set of n players. We normalize the cost of generating a proof to 1, which we assume is identical across each player and publicly known. We further assume that the validation of the proof is negligible, akin to SNARK verification being nearly constant time (i.e., linear in the public inputs rather than 12

The costly work being done is acquiring the trusted hardware and running the inference in that environment; the low-cost verification being done is checking that the hardware-generated signature attests to the output running in a verifiable way.

5

the circuit size) (25). The players have pseudonymous IDs (i.e., it is possible to request a proof from Player One but not Player Two), but no reputation or commitment power (i.e., no player can credibly promise “if you pay me, I will produce the proof.”). We use the notation di to denote the indicator variable for whether prover i delivers a proof. Design space. The protocol specifies a strategy profile s and a payment rule p(·). The strategy profile simply states, for each prover i, what is the probability si that the prover delivers a proof? The payment rule p(·) specifies, for each prover i and each vector d, what is the payment pi (d) given to player i when the set d of proofs is received? For our main results, we must have pi (d) ≥ 0 for all i, d. We also consider extensions where each prover i stakes a deposit B/n, allowing any pi (d) ≥ −B/n to be feasible. Payoffs. Prover i’s ultimate payoff is pi (d) − di . Denote [n] := {1, 2, . . . , n} . The protocol’s cost P is P p i∈[n] i (d), the total sum of payments, whenever d ̸= 0 (i.e., at least one proof is produced), and i∈[n] pi (0) + C if no proofs are produced. More formally, we define protocol cost. Definition 2.1 (Protocol cost). The protocol cost under a payment rule p and delivery profile d is the total payment to players, plus the failure penalty C if no proofs are delivered, X Y cost(p, d) := pi (d) + C · (1 − di ). i∈[n]

i∈[n]

Prover incentives and protocol evaluation. Provers are risk-neutral and quasilinear, and therefore will only follow the protocol if doing so maximizes their expected utility (in expectation over other provers also following the protocol). Because there is no private information, each prover i can compute their expected payoff DeliverPayi when submitting a proof (the expected value, when all other players j submit a proof independently with probability sj to produce d−i , of pi (d−i ; 1i ), minus the unit cost of delivering), and their expected payoff NoDeliverPayi when not submitting the expected value, when all other players j submit a proof independently with probability sj to produce d−i , of pi (d−i ; 0i )). Therefore, if si > 0 it must be that DeliverPayi ≥ NoDeliverPayi , and if si < 1 it must be that NoDeliverPayi ≥ DeliverPayi (and so if si ∈ (0, 1), they must be equal). A protocol is incentive compatible if it satisfies these constraints. We refer to S(p) as the set of all strategy profiles s such that (s, p(·)) is incentive compatible, and say p implements s if s ∈ S(p). The protocol designer cares for worst-case guarantees. Specifically, they worry that up to n − h of the provers will deviate from equilibrium and behave arbitrarily. Brief modeling discussion. One way to interpret our model is as follows. In steady-state, all provers prove according to the strategy profile s, which is an equilibrium of p(·). The protocol wants to be robust to a one-time worst-case event where, for whatever reason, up to n − h provers behave arbitrarily rather than as expected. Therefore, incentive compatibility constrains the protocol design (as otherwise, the prescribed equilibrium could not be a steady-state outcome), while the worst-case desideratum guides the analysis. Remark 2.1 (Worst-case analysis as an adversary). A mathematically equivalent way to interpret the model again has all provers proving according to s in steady-state. Then, an adversary corrupts up to n − h provers for one slot and aims to cause as much damage as possible. In the running example of the zk-EVM, the threat model is a one-off attack, where a proposer aims to cause a liveness fault on the slot preceding their own in order to steal the MEV that would’ve otherwise been paid to the previous slot’s proposer. Again, incentive compatibility constrains the protocol 6

design, while adversarial robustness guides analysis. Through this lens, our adversary is powerful in the sense that it can choose which provers to corrupt on the basis of their pseudonyms (i.e., after learning s), and cause them to behave arbitrarily (i.e., not only by shutting down their prover, but by having them produce a proof they otherwise wouldn’t). Our adversary is only limited in that both its corruption and delivery decisions are made without knowing the outcome of the private random coins of honest participants. Based on this interpretation, it is often useful to personify the worst-case analysis as an adversary that is trying to maximally harm the protocol. Denote by A ⊂ [n] the set of adversarial provers, such that |A| = n−h, and H = [n]\A as the set of honest (playing the rational equilibrium) provers. Then, the protocol designer evaluates a protocol s, p(·) according to following loss function: Definition 2.2 (Loss). The loss of a payment rule p(·) and strategy profile s is n h
io ℓ(p, s) := max E cost p, dA |dH , A,dA dH ∼sH

where dA |dH concatenates the adversarial and honest delivery decisions to construct the full delivery vector d. The goal of the designer is therefore to solve the following optimization problem, which minimizes loss over all incentive compatible (s, p(·)). Definition 2.3 (Protocol objective). The protocol solves OPT1 := min {ℓ(p, s)}.

(PROG1)

p,s∈S(p)

3

Results

Before analyzing the solutions to this program, the following examples serve to illustrate the difficulty of the design problem concretely. Consider the following basic payment rule. Example 3.1 (Pay a designated subset to deliver). Randomly choose a subset of k provers, and pay them 1 + ε if they deliver. All k players delivering is a pure-strategy Nash equilibrium. This naı̈ve payment rule seems promising, but let’s consider the worst-case, represented by the Byzantine adversary (Rem. 2.1) corrupting a := n − h provers. Since the adversary observes p, they will check if k ≤ a. If so, they can corrupt all k of the designated provers and cause them not to deliver, deterministically causing the liveness penalty of C (which is worse for the protocol assuming C > k(1 + ε)). If k > a, at least one honest player will deterministically deliver a proof, so the worst-case is the protocol paying the full k(1 + ε) each round. While choosing a high value of k gives a robust mechanism, it is cost-prohibitive to pay for k proofs each slot, especially if the value of a is large. A natural alternative is to commit to a fixed payment and ask players to use a symmetric mixed strategy to determine who delivers. Example 3.2 (Lottery payment rule). Award a fixed prize P randomly to one prover who delivers. Each player delivering with a symmetric probability s is a mixed-strategy Nash equilibrium. This mechanism is powerful because it allows the protocol to commit to a fixed prize size and leverage the independent randomness of the players to exponentially bound the probability of no one delivering (e.g., (1 − s)n ).13 From the perspective of the worst-case attacker, however, this 13

This intuition is correct, and we show that this lottery payment rule is a 2−approximation of optimal (Lem. A.1).

7

payment rule leads them not to deliver the full set of corrupted provers. This greatly increases the probability of no proof being delivered from (1 − s)n → (1 − s)h (only the honest players are flipping coins), and the protocol’s expected cost increases correspondingly. Further, the lottery indeed loses some efficiency because it has to overpay to incentivize everyone to mix with the same probability s (see (8) for the exact equation); one last example payment rule tries to address this. Example 3.3 (Pay deliverers deterministically). Ask provers to deliver with some uniform probability s, paying any prover that delivers 1. Each prover delivering with a symmetric probability s is a mixed-strategy Nash equilibrium (provers are indifferent between delivering and not because their payment exactly offsets their cost). This payment rule tries to be more cost-efficient by paying for precisely the number of proofs that are delivered. If everyone were honest, this would avoid the overpayment of the lottery payment rule. Consider the adversary; they will compare the protocol’s expected cost if none of the corrupted provers deliver (which lowers the payment by a·s, but also increases the probability of a liveness failure) with the cost if all of the corrupted provers deliver (which guarantees no liveness failure, but increases the payment by a · (1 − s) – importantly, this increased payment could be quite significant when a is large and s is small!), choosing the higher of the two. These examples illustrate the difficulty of designing for the worst-case, where some provers may over- or underdeliver, depending on the specifics of the payment rule. The remainder of this work formalizes exactly this trade-off. Solving (PROG1) directly is complex; see Section A.1 for its expanded form. To start, the number of attacker constraints is exponential in a, which arises from the adversary choosing either action for any of the corrupted provers. Further, the protocol has to choose s in such a way that the payment rule achieves a low cost. To make the analysis tractable, we construct a lower bound on OPT1 that is only a function of s; proof in Section A.2. Lemma 3.1 (Lower bound function g(s)). Consider the protocol parameterized with (h, a, n, C). Without loss of generality, re-index the players such that s is decreasing in i. Then define g(s) as,   n  X Y Y g(s) := max si + C (1 − si ), C (1 − si ) . (1)   i∈[n]

i∈[n]

i=a+1

Then the solution to the following program, OPT2 := min g(s) s∈[0,1]n

(PROG2)

s.t., 1 ≥ s1 ≥ s2 ≥ . . . ≥ sn ≥ 0 is a lower bound on the solution to (PROG1): OPT2 ≤ OPT1. Remark 3.1 (Interpreting g as a weakened attacker). The construction of g as used in the proof of Lem. 3.1 is to limit the action space of the Byzantine players. In particular, we force the attacker to choose between playing a fully honest strategy (i.e., playing si , ∀i ∈ A) or a fully non-delivering strategy (i.e., playing di = 0, ∀i ∈ A). The resulting expected protocol loss is represented as the left and right branches of (1). Remark 3.2 (Interpreting g as a powerful mechanism). One alternative view of g is that it is the loss achieved by a mechanism that can immediately detect when the largest a players in the protocol are playing di = 0 and refusing to pay in that circumstance. This detection is represented by the 8

right branch of the max, which is only the expected value of the liveness penalty being caused by h smallest indices (and no direct payments). While this seems like a powerful mechanism, we show that in many cases, the bound is achievable (Rem. 3.7). In order to make the solution of (PROG2) more amenable to analysis, we first prove a structural property about the minimizer of g; we show it must occur exactly when the left and right branches of the max are equal. Lemma 3.2 (Minimizer of g occurs at equality). The vector s∗ that minimizes (1) occurs where the two branches of the max are equal. More formally, we have X

Y

s∗i + C

(1 − s∗i ) = C

(1 − s∗i ).

i=a+1

i∈[n]

i∈[n]

n Y

Proof in Section A.3. Using Lem. 3.2, we can define a simpler constrained optimization problem for minimizing g, OPT3 := min C s∈[0,1]n

n Y

(1 − si )

(PROG3)

i=a+1

s.t., 1 ≥ s1 ≥ s2 ≥ . . . ≥ sn ≥ 0 n X Y Y si + C (1 − si ) = C (1 − si ). i∈[n]

i=a+1

i∈[n]

Since this is exactly equivalent to (PROG2), we have OPT3 = OPT2 ≤ OPT1, so the solution to (PROG3) is a lower bound on the protocol loss. This transformation simplifies the analysis of the lower bound. Next, we define two “types” of equilibria that characterize possible shapes of the solutions to (PROG3). Definition 3.1 (Designated uniform committee equilibrium). A strategy vector s is a designated uniform committee equilibrium if it has (i) a single deterministic deliverer, (ii) a committee of size k ≤ n − 1 who each mix with the same probability s ∈ (0, 1), (iii) a (potentially empty) set of players who deliver with probability 0. That is,   1 if i = 1 si = s if i ∈ {2, 3, . . . , k + 1}   0 otherwise. We sometimes use the vector notation for these equilibria s = [1,

s, . . . , s, | {z }

0, . . . , 0].

committee of size k

Further, we often refer to them simply as “designated” equilibria (where the “designate” is the player who deterministically delivers by playing si = 1), but will include further context whenever the uniformity or the size of the committee is important. Definition 3.2 (Symmetric committee equilibrium). A strategy vector s is a symmetric committee equilibrium if it has (i) a committee of size k ≤ n who each mix with the same probability s ∈ (0, 1), (ii) a (potentially empty) set of players who deliver with probability 0. That is, ( s if i ∈ {1, 2, . . . , k} si = 0 otherwise. 9

We sometimes use the vector notation for these equilibria s=[

s, . . . , s, | {z }

0, . . . , 0].

committee of size k

Further, we often refer to them simply as “symmetric” equilibria, but will include further context whenever the size of the committee is important. The minimizers of g are exclusively one of those two shapes. Lemma 3.3 (Characterizing the minimizer of g). Let s∗ denote the minimizing vector s∗ := arg mins∈[0,1] g(s). Then s∗ is either a designated uniform committee equilibrium or a symmetric committee equilibrium (Defs. 3.1 and 3.2). Proof in Section A.4. Lem. 3.3 gives us a geometric picture of the minimizers of g, but remember that this function is only a lower bound (Lem. 3.1) on the protocol loss parameterized just by the strategy vector s, without saying anything about the corresponding payment rule p. Definition 3.3 (Implementable optimal equilibria). An equilibrium vector s∗ that is a lower bound on g is implementable if there exists a payment rule p such that s∗ ∈ S(p) and ℓ(p, s∗ ) = g(s). An implementable optimal equilibrium achieves the lowest possible protocol cost by making the lower bound tight and thus being a solution to (PROG1). The rest of this section analyzes the implementability of the lower bound. Section 3.1 shows that all designated equilibria are implementable and further, that there exists a designated equilibrium vector that achieves cost no more than 1 unit higher than the optimal loss (i.e., an additive 1−approximation). Section 3.2 demonstrates the conditions under which symmetric minimizers are implementable. Section 3.3 examines how the minimizer of g transitions between the two equilibrium shapes and their relative committee sizes. Section 3.4 examines the asymptotic scaling of the worst-case loss and how negative payments (i.e., staking and slashing) can reduce it.

3.1

Designated equilibria

If the minimizer of g is designated, we can implement it with the following payment rule recipe. Proof in Section A.5. Lemma 3.4 (All designated uniform committee equilibria are implementable). Given a designated uniform committee equilibrium parameterized by committee size k ≤ n − 1 and a mixing probability s, there exists a payment rule that implements the equilibria and achieves the minimal protocol loss of 1 + ks. Remark 3.3 (Simplicity of designated mechanism). The payment rule recipe used in the proof of Lem. 3.4 is simple and extends naturally from our lower bound construction (Lem. 3.1). In particular, the protocol commits to: (i) paying a fixed amount 1 + ks, if at least one proof is delivered, no matter how many copies are produced, and (ii) telling a single prover to deliver with probability 1, and conditioning the other provers’ payment on the deterministic player.

10

This allows the protocol to choose s such that both branches of the max are equal (Lem. 3.2) and thus achieve exactly the loss of g. From the adversarial perspective (i.e., worst-case analysis Rem. 2.1), the options are very limited. If they corrupt player 1 and choose not to deliver d1 = 0, then the protocol will not pay (by (ii) above), and the best they can do is try to cause a liveness penalty by playing a fully non-delivering strategy. If they don’t corrupt player 1, the protocol will certainly acquire a proof, but will only pay a fixed amount (by (i) above). Thus, the payment rule forces the attacker into one of two branches of the lower bound (Lem. 3.1) and is optimal. Lem. 3.4 tells us that if the minimizer of g is designated, then we can implement the optimal mechanism. While this is a positive result, we know that the minimizer of g is sometimes symmetric Lem. 3.3. Section 3.2 studies that shape. There is some good news before then, which is that for any payment rule p and equilibrium s with loss ℓ(p, s), there exists a corresponding payment rule p′ and designated equilibrium s′ such that ℓ(p′ , s′ ) ≤ ℓ(p, s) + 1. That is, there is a designated equilibrium that is an additive-1 approximation to the loss of an arbitrary payment rule and equilibrium pair; proof in Section A.6. Theorem 3.1 (Payment rule reduction). Given any payment rule, p, and corresponding equilibrium, s ∈ S(p), there exists a modified payment rule, p′ , and a modified equilibrium, s′ ∈ S(p′ ), such that the modified equilibrium is designated and ℓ(p′ , s′ ) ≤ ℓ(p, s) + 1. Corollary 3.1 (Designated equilibria are approximately optimal). By Thm. 3.1, given the optimal payment rule p∗ and optimal equilibrium s∗ , there exists a modified payment rule p′ and a correspondingly modified designated equilibrium s′ such that ℓ(p′ , s′ ) ≤ ℓ(p∗ , s∗ ) + 1. Remark 3.4 (On the strength of the approximately optimal construction). Our main practical takeaway is advising practitioners to use the optimal designated equilibrium (Rem. 4.5), which extends directly from the simplicity (Rem. 3.3) and approximate optimality (Cor. 3.1) of this construction. We also show that the mechanism is asymptotically optimal in C because the additive 1 error doesn’t impact the O(log C) scaling (Lem. 3.11) and that stake can further improve the scaling of the loss (Lem. 3.12). Before discussing the asymptotic scaling, however, we cover the non-asymptotic and discrete cases for the optimal loss of the protocol, turning our attention to the symmetric shape for minimizing equilibria of g (Section 3.2) and the transition dynamics of the minimizing equilibrium of g (Section 3.3).

3.2

Symmetric equilibria

The other possible form of the minimizer of g is a symmetric equilibrium (Def. 3.2). This subsection analyzes the feasibility of implementing such equilibria while achieving the lower bound g (i.e., finding when the lower bound is tight on the symmetric shape). The following lemma allows us to only consider simple anonymous payment rules that only pay based on the total number of proofs delivered.

11

Lemma 3.5 (Symmetric payment rule reduction). Any payment rule p that implements a symmetric equilibrium s with a committee size of k can be transformed into an anonymous payment rule p′ with the following form: ( ft /t if di = 1, ||d||1 = t, i ≤ k ′ pi (d) = 0 otherwise. where ft is a fixed total prize that the protocol pays under the event that there are exactly t proofs delivered. The symmetric vector is still an equilibrium under the modified payment rule s ∈ S(p′ ) and p′ has weakly lower cost ℓ(p′ , s) ≤ ℓ(p, s). Proof in Section A.7. Lem. 3.5 allows us to simply focus on payment rules that set a fixed prize as a function of the number of proofs delivered (i.e., payment rules that are anonymous and don’t pay non-deliverers). Consider a symmetric equilibrium with h honest players each mixing with probability s. Let X ∼ Binomial(h, s) denote a random variable counting the number of honest deliveries. Further, let fi denote the total protocol payment given i proofs are delivered, and f0 := C by definition. Then the optimal payment rule can be written as the solution to the following LP, where X ∼ Binomial(n − 1, s):

min

f1 ,...fn ≥0

t

(LP1)

s.t., E[fi+X ] ≤ t ∀i ∈ {0, 1 . . . , a}   f1+X E = 1. 1+X

(attacker delivers i) (equilibrium condition)

See Section A.8 for a more verbose form of the LP. Each of the (attacker delivers i) constraints are defined by the protocols’ expected payment over the random distribution of honest payments. Similarly, the (equilibrium condition) constraint ensures that each player’s expected payment is exactly 1 if they deliver, making them indifferent between delivering and not delivering (both with utility 0), which is a requirement for them to play a mixed strategy. We constructed g such that the protocol never pays if it detects that it is being attacked (Rem. 3.2). When the minimizer of g is designated (Section 3.1), this is easy to do as we can condition the payments on the delivery of the deterministic player. In the symmetric case, it is more involved. First, we define the following linear system, which must be solved to find the values of fi in order for the lower bound to be tight. Definition 3.4 (Feasible symmetric linear system). Consider the values of fi in (LP1). In order to detect that the attacker has played the fully non-delivering strategy (and thus achieve the lower bound on the right branch of g), the payment rule never needs to pay if there are fewer than h + 1 deliveries. More formally, it sets f1 = f2 = . . . = fh = 0. With that, the (attacker delivers i) constraint with i = 0 becomes C(1 − s)h ≤ t, which is exactly the right branch of g, thus we know that the constraint must be tight. Further, in order for the solution to the (LP1) to achieve this bound, each of the other (attacker delivers i) constraints must also be tight.

12

This allows us to construct the following linear (in fi>h ) system of equations, which has exactly a equations and unknowns: (1 − s)h C

=t

h

=t

s fh+1

(LS1)

sh fh+2 + hsh−1 (1 − s)fh+1 = t ... h   X h i s (1 − s)h−i fa+i i

= t.

i=0

Each equation in the system corresponds to one of the attacker constraints in (LP1) (e.g., the ith equation is the expected protocol payment under i attacker deliveries). In order to achieve the lower bound on g, each of the constraints needs to be tight. The following lemma gives us an upper bound on C for when symmetric minimizers of g are implementable. Lemma 3.6 (Optimal symmetric implementability). For a given (h, a, n), a symmetric minimizer of g is implementable if C≥

hn(h + 1)n−1 . (h + 1)a − 1

Proof in Section A.9. Lem. 3.6 gives us an upper bound on the value of C past which symmetric minimizers of g are implementable (Def. 3.3) with the payment rule presented in Lem. 3.5. Notice that this lemma works for any subcommittee size k. However, it is not always the case that these symmetric minimizers are implementable. Example 3.4 (Non-implementable minimizer). Consider h = 2, n = 5, C = 7. Then g is minimized in the fully symmetric equilibrium (Def. 3.2) with s1 = . . . = sn ≈ 0.4735 which results in a g(s∗ ) ≈ 10 · (1 − 0.4735)2 ≈ 2.772. By Lem. 3.5, we know that we only need to check the feasibility of the anonymous symmetric payment rule. Solving (LS1), gives f4 = −15.133. Since negative payments are not allowed, this equilibrium is not implementable (Def. 3.3). This example demonstrates that our lower bound is sometimes loose. More formally, there exist equilibria s, such that s solves (PROG3), but ∄p, s ∈ S(p) : ℓ(p, s) = g(s). This is a limitation of our lower bound function g. However, by Thm. 3.1, we know that the optimal designated equilibrium is an additive 1−approximation of the true optimal loss. Thus, it follows that if the best implementable symmetric equilibrium (the solution to (LP1)) has a lower loss than the optimal designated equilibrium, it too is an additive 1−approximation of the true optimal. Section A.10 points out that a lottery, which is a much simpler symmetric payment rule than the solution to the LP, is a 2−approximation of optimal. Sections 3.1 and 3.2 study the designated and symmetric minimizers of g, respectively. Section 3.3 explores the transition points between these regimes for the minimizer of g.

3.3

Transition dynamics of g

The lower bound on g is the solution to a non-linear constrained optimization problem, which results in non-obvious properties; consider the relatively small numerical example below. 13

Figure 3.1: A 3−dimensional example of the transition dynamics of the solution to (PROG3) at h = 1, n = 3 and C = 2 (lower surface) and C = 5 (higher surface). The colorbars denote the value of g at [s1 , s2 , s3 ], and the circle and square markers indicate the minimizers over the intersection of the surface and the polytope. Example 3.5 (h = 2, n = 5). As we increase the value of C, the minimizer s∗ of g takes multiple shapes: • C = 5 =⇒ s∗ = [1, 0.323, 0.323, 0.323, 0.323] (designated full). • C = 7 =⇒ s∗ = [0.473, 0.473, 0.473, 0.473, 0.473] (symmetric full). • C = 10 =⇒ s∗ = [0.926, 0.926, 0.926, 0.926, 0.] (symmetric committee). In words, the shape of the minimizer changes from designated to symmetric. Further, as C increases, the committee size of the symmetric optimizer changes from 5 to 4. From Lem. 3.3, we know that the minimizer of g is either a designated or symmetric equilibrium, but exactly which it is depends on the specific (h, n, C) values. Geometrically, the solution to (PROG3) is subject to: • Ordering constraints: Notice that 1 ≥ s1 ≥ . . . ≥ sn ≥ 0 forms an n−dimensional polytope. • Branching constraint: By setting the two branches of g equal, the constraint forms an n−dimensional surface. Combining the above observations, we get that the minimizer of g is the minimizing value of the objective on the intersection of the surface and the polytope. In three dimensions, we can visualize this explicitly. 14

Fig. 3.1 shows the h = 1, n = 3 example where the two surfaces (C = 2, lower & C = 5, higher) at s = [s1 , s2 , s3 ] with the colorbars indicating the value of g. The circle and square markers are the respective minimizers over the intersection of the polytope and each surface. Notice that with C = 2, the minimizer lies on the edge [1, s, s] (square marker). Conversely, at C = 5, the minimizer flips to the diagonal [s, s, s] (circle marker). This is exactly what happens in higher dimensions, but the minimizer can also jump to an edge that represents a smaller committee size (Ex. 3.5). To analyze the transition between these edges algebraically, we start by defining the minimizers over the respective shapes. Definition 3.5 (Minimizing symmetric and designated losses). For a given (h, a, n, C), let Sk∗ , Dj∗ be the value of g at the minimizing symmetric and designated equilibria, respectively, where j, k denote the optimal committee sizes and hj := j − a, hk := k − a the resulting number of honest committee members. More formally,  Dj∗ := min 1 + (hj + a − 1)s hj ∈[h] s∈[0,1]

s.t. 1 + (hj + a − 1)s = C(1 − s)hj  Sk∗ := min (hk + a)s + C(1 − s)hk +a hk ∈[h] s∈[0,1]

s.t. (hk + a)s + C(1 − s)hk +a = C(1 − s)hk . Note that in each case, the optimal committee sizes are j = (a+hj ), k = (a+hj ) respectively, and could be different sizes. The minimizing values consider all possible committee sizes by iterating over the possible values of the size of the honest committee members hj , hk ∈ [h]. For each committee size, the optimizer also finds the minimum value of s ∈ [0, 1]. In Ex. 3.5, we see that the minimizer of g transitions from designated to symmetric. Lems. 3.8 and 3.9 show that this is the case generally, so long as a > 1. In particular, over the interval C ∈ (1, ∞), the minimizer of g is always designated as C → 1+ and always symmetric when C → ∞. First, however, we need to handle one special case of a = 1. Lemma 3.7 (For a = 1, designated is always optimal). For all C > 1, h ≥ 1, if a = 1 then the optimal designated equilibrium is always better than the optimal symmetric: Dj∗ < Sk∗ . Proof in Section A.11. For the remainder of this paper, we will restrict attention to the a ≥ 2 case. First, we show that for small values of C, the minimizer is designated. Lemma 3.8 (Minimizer of g is designated for C < 1 + 1/a). For very small penalty values C < 1 + 1/a, the minimizing vector s is a designated equilibrium. Proof in Section A.12. On the other side of the spectrum, as C gets arbitrarily large, we actually prefer a symmetric equilibrium in the limit. Lemma 3.9 (Minimizer of g is symmetric for C → ∞). For large penalty values C → ∞, the minimizing vector s is a symmetric equilibrium. Proof in Section A.13. Given that the minimizer changes shape from designated to symmetric on the endpoints of C ∈ (1, ∞), the smallest value of C where the transition occurs is well defined. Definition 3.6 (Transition value, Ct ). For a given (h, a, n), let Ct denote the smallest C such that the optimal shape of the minimizer of g is symmetric instead of designated. More formally,  Ct := inf C : Sj∗ < Dk∗ . C∈R>1

15

Figure 3.2: This plot shows Ct (on log scale) as a function of the continuous honest ratio τ = h/n ∈ (0, 1) when h, n → ∞ as calculated in Lem. 3.10 (solid line). The dashed lines denote the corresponding values with stake B = 10 (Section 3.4) as calculated in Cor. A.3. Remark 3.5 (Ct reduces to root finding on high-degree polynomials). Notice that to find Ct , for each candidate C we need to solve for the roots of the 2h polynomial equations defined by the constraints in Def. 3.5. In other words, there is no general algebraic solution to Ct for all n, h pairs. Rem. 3.5 tells us that we can’t hope for a general expression of Ct for all discrete values of h, n. However, the following lemma reduces the analysis to the continuous setting, allowing us to arrive at a more tractable implicit equation. Lemma 3.10 (Limit behavior of Ct ). As h, n → ∞ with τ = h/n ∈ (0, 1) as the continuous “honest proportion,” the value of Ct at which the optimal symmetric equilibrium achieves a lower loss than the optimal designated equilibrium is: lim Ct (τ ) = ex , where 1 + x = e(1−τ )x .

n→∞

Proof in Section A.14. Fig. 3.2 shows the analytic bound calculated in Lem. 3.10 as h, n → ∞ as a function of τ in red. In this continuous setting, we see that Ct is monotone increasing and super-exponential (not the log scale of the y axis) in τ . The discrete setting is not necessarily monotone, but converges to the limit as h, n get large; see Section A.15 for a figure with numerical values in the discrete case. Remark 3.6 (Ct growth is super-exponential in τ ). As shown in Fig. 3.2, the growth of Ct is superlinear even with the log-scaled y axis. For a given τ , if we are below the red curve, then we know the designated equilibrium is optimal. As such, the super-exponential scaling in τ is very strong. Intuitively, it tells us that the marginal increase in the honest fraction of provers leads to a much larger corresponding set of C values where designated is exactly the optimal mechanism. Remark 3.7 (Designated is often optimal). Fig. 3.2 shows that for any τ , if C < Ct (below the red line), the designated equilibrium is optimal. The super-exponentiality in τ (Rem. 3.6) means that for larger regimes of C, we have the true optimal mechanism. For example, with no stake and assuming the τ = 2/3 honesty threshold from consensus mechanisms, ∀C < 140, designated is optimal. Stake, as introduced in Section 3.4 below, significantly increases this regime; for the same τ = 2/3 with stake B = 10, designated is optimal ∀C < 3000. 16

Figure 3.3: The optimal protocol loss as a function of C for various values of τ ∈ [0.5, 0.9]. The solid lines are without stake. Lem. 3.11 shows that this loss scales as O (log(C)/τ ). The dashed lines include stake (Section 3.4) of B = 1000. For C ≤ 1000, the cost is constant. For C > 1000, we again enter a logarithmic scaling regime; Lem. 3.12 details the optimal loss as a function of the asymptotic regimes of B.

3.4

Protocol loss scaling and negative payments

The value of Ct is just the transition point of when the best symmetric equilibrium is better than the best designated equilibrium (e.g., when our lower bound is tight). We now consider the scaling of the optimal protocol loss as a function of C. In words, we want to know how much the protocol should expect to pay in the worst-case, given a liveness penalty of magnitude C. We continue in the continuous setting, where the fraction of honest provers is τ ∈ (0, 1). Lemma 3.11 (Asymptotic designated loss). The loss of the optimal designated equilibrium scales as O (log(C)/τ ). Proof in Section A.16. Remark 3.8 (Logarithmic scaling of loss). Lem. 3.11 is a strong result. Even with an adversary that controls any fixed proportion of the provers, we still have asymptotically logarithmic scaling in the magnitude of the liveness penalty C. Fig. 3.3 demonstrates this numerically, where the solid lines represent the worst-case protocol loss in the unstaked setting (solid lines) as a function of C and for various values of τ (colorbar). We introduce the staked (dashed lines) setting below. Even when C gets extremely large, the optimal loss is well controlled and only the coefficient of the log scaling changes with τ . Intuitively, the log scaling comes from the fact that each honest prover is playing an independent mixed strategy. The protocol leverages this to minimize the probability of receiving no proofs. To this point, every payment rule we have proposed was constrained to positive payments. We now consider the impact of allowing negative payments.14 Using the nomenclature common in blockchain protocol design, we model this as each player posting a “stake” (collateral), which may 14

Recall that the solution to the (LS1) could result in negative values, which we disallowed. This section relaxes that constraint and again performs a lower bound analysis.

17

be “slashed” (seized) by the protocol. Of course, the possibility of being slashed is factored into the incentive compatibility of each prover through their equilibrium constraints. That is, any risk of negative payments must be offset by a corresponding positive expected utility from participation. Remark 3.9 (Negative payments as insurance). Slashing in our model serves as a form of “insurance” for the protocol, which is similar to STAKESURE (16). That is, the stake that is slashed by the protocol serves not only as a negative payment for the attacker, but also as a positive payment to the protocol to compensate for the damage caused. In our running example of zk-EVM proofs, the proposer of a slot is protected by the collateral posted by the provers so that if their block is not proved (and thus they miss out on the rewards), they are refunded through the slashed collateral. This is a subtle but important distinction from slashing in traditional Proof-of-Stake systems (13)), where the seized collateral is “burned,” because there is not an obvious single victim of an attack on the consensus mechanism that could be compensated. Note that if the negative payments can be made arbitrarily large, then there is a trivial payment rule that ensures that the protocol achieves the minimal possible cost of 1. Example 3.6 (Unbounded stake optimal). Require each prover to post a collateral of C − 1. Designate prover 1 as the “elected prover” and pay them according to the following payment rule: ( −(C − 1) if d1 = 0 p1 (d) = 1 if d1 = 1. Then both outcomes (the prover delivering or not) have the same protocol cost of 1. Obviously, this would be the ideal situation for the protocol designer, but asking each prover to post this large a stake is infeasible in most situations, especially if C is large (discussed in Rem. 4.1). As such, we analyze the setting where the maximum stake posted by each prover is bounded. We model the aggregate amount of stake across provers that the protocol can elicit as B (for bond), where we are measuring according to the unit, common-value cost of generating a single proof. For example, if B = 100 and n = 100, we require each prover to post a collateral of the cost of generating 1 proof to participate in the system. We argue in Rem. 4.2 that the unit cost of generating a proof should be small, so asking for a potentially large stake is feasible. With B defined, we modify our original lower bound (Lem. 3.1) to now include the slashed collateral as a refund that reduces the protocol cost in the case of an attack. Corollary 3.2 (Staked lower bound function gB (s)). Extending the lower bound of Lem. 3.1, consider the protocol parametrized with (h, a, n, C) and with aggregate stake of B. Then define gB (s) as,   n  X Y Y gB (s) := max si + C (1 − si ), C (1 − si ) − B .   i∈[n]

i∈[n]

i=a+1

Then for the solution to the following program, OPT4 := min gB (s) s∈[0,1]n

s.t., 1 ≥ s1 ≥ s2 ≥ . . . ≥ sn ≥ 0 we have OPT4 ≤ OPT1. Proof in Section A.17. 18

(PROG4)

Remark 3.10 (Correlation of slashing). Part of what makes this slashing mechanism powerful is the fact that we can correlate all players’ negative payments with the behavior of the attacker. Recall that we are modeling the equilibrium conditions for the non-corrupted players as non-responsive to the threat of an attacker.15 We still think this is the correct model given the fact that liveness attacks (e.g., on Ethereum’s zk-EVM) would likely be specific one-off instances. However, with negative payments, this assumption may be harder for provers to abide by. In particular, they may be less willing to post collateral if they know that it could be slashed under an attack, and despite submitting a proof themselves. Still, there is a precedent for correlated penalties; if Ethereum enters an “inactivity leak” period (see get inactivity penalty deltas in (21)), then every validator receives 0 rewards for the duration of the attack. As such, we think it is a reasonable assumption that if the stakes are small enough, correlated slashing is practical. Further, the correlation can be weakened by designating k provers as deterministic, and only slashing if all k fail to deliver, while only incurring an additional constant overhead of k. Given gB (s) (Cor. 3.2) and its structural similarity to the lower bound g(s) (Lem. 3.1), much of the analysis we have established extends directly to the negative payments regime. See Section A.18 for details. Beyond simply calculating the values of C such that we can achieve the optimal cost, we can also make quantitative claims about the sensitivity of the protocol’s worst-case loss to the amount of aggregate stake. The following examples show that stake is much more impactful in a high-C, τ regime. Example 3.7 (Moderate staking amounts result in large percentage loss reduction if τ, C are large.). Let n = 100, a = 33 (τ = 2/3), and C = 10, 000. If B = 500 (5% of C), then the protocol loss drops 47.5% compared to the no stake environment. See the left half of the table in Section A.19 for more numerical values. Example 3.8 (Moderate staking amounts yield low percentage cost reduction if τ, C are moderate.). Let n = 200, a = 100 (τ = 1/2), and C = 20. If B = 1 (5% of C), then the protocol loss drops by 4.5% compared to the no stake environment. Contrast this with the 47.5% drop in Ex. 3.7. See the right half of the table in Section A.19 for more numerical values. Remark 3.11. Exs. 3.7 and 3.8 show that the benefits from acquiring stake that accounts for 5% of the liveness penalty can vary greatly; in this case, the difference in cost reduction was a full order of magnitude higher when τ, C are larger. Fig. 3.3 shows the impact of stake B = 1000 on the optimal loss scaling as dashed lines with various τ (colorbar). We see that across the spectrum of τ and C values, stake can meaningfully reduce the expected protocol loss. Asymptotically, we also consider how the optimal loss scales as a function of B, C, τ . Lemma 3.12 (Asymptotic losswith staking). The  loss of the optimal designated equilibrium with log C−log(log C+B) staking amount B, scales as O . Observe that this implies the following regimes τ B = O(1)

=⇒ loss = O (log(C)/τ )

B = Θ(C/polylog C) =⇒ loss = O (log(log C)/τ ) B = Θ(C)

=⇒ loss = O (1/τ ) .

Proof in Section A.20. Exs. 3.7 and 3.8 and Lem. 3.12 show that stake can significantly reduce the protocol loss. We use these results to motivate our concrete takeaways for practitioners in Section 4.1. 15

Further work could consider honest players who modify their behavior (through changing their equilibrium conditions) based on the threat of the existence of an attacker, but this is out of scope for the present work.

19

4

Discussion

Section 3 studies the minimizers and transition dynamics of the lower bound g (Lem. 3.1) on OPT1 (PROG1). The lower bound is highly tractable, and we show that it is tight in some regimes (Lems. 3.4 and 3.6) and that we can get good approximations in all regimes (Thm. 3.1 and Lem. A.1). Further, we showed that no closed form exists for when the transition occurs (Rem. 3.5), but we analyzed the limit behavior and gave numerical and asymptotic bounds (Lems. 3.10 and 3.12). This section builds on these results by considering only implementable symmetric and designated equilibria, conjecturing that the true solution (PROG1) is the better of the optimal and implementable symmetric or designated equilibria. Intuitively, this conjecture would say that the minimizing shapes of g are the minimizing shapes of (PROG1) more generally. In the symmetric case, the best implementable payment rule is exactly the solution to (LP1). Lem. 3.6 showed that this is equal to the lower bound on g if and only if f1 = . . . = fh = 0, but the solution to the LP is the optimal implementable symmetric payment rule more generally. In the designated case, all equilibria are implementable (Lem. 3.4). Thus, to find the optimal implementable equilibrium, we consider a modification of (PROG3), where we simplify the program by fixing s1 = 1. Also, by the same argument we make for the shape of g in Lem. 3.3, the solution to the modified program will be a designated uniform committee equilibrium (Def. 3.1). Thus, we can write the simplified program for the full set of n players as: OPT5 := min C(1 − s)h

(PROG5)

s∈[0,1]

s.t., 1 + (n − 1)s = C(1 − s)h We now define the minimizing implementable symmetric and designated losses (denoted Ŝk , D̂j resp.), which is very similar to Def. 3.5 (Sk∗ , Dj∗ ), but with the enforcement of implementability rather than searching over the general lower bound g. Definition 4.1 (Minimizing implementable symmetric and designated losses). For a given (h, a, n, C), let Ŝk , D̂j be the values of the minimizing implementable symmetric and designated equilibria, respectively, where j, k denote the respective optimal committee sizes and hj := j − a, hk := k − a denote the resulting number of honest committee members. More formally,   D̂j := min P ROG5(hj ) , Ŝk := min LP 1(hk ) , hj ∈[h] s∈[0,1]

hk ∈[h] s∈[0,1]

where P ROG5(hj ), LP 1(hj ) denote the solutions to the programs parameterized by committee sizes of j = a + hj , k = a + hk . Conjecture 4.1 (Optimal is designated or symmetric). The solution to (PROG1) is the smaller of the implementable minimizing designated and symmetric equilibria. More formally, n o ? OPT1 = min D̂j , Ŝk . This conjecture is motivated through the analysis of the lower bound g in Section 3, where we are able to explicitly pin down the shape to designated and symmetric minimizers of g (Lem. 3.3). Section B.1 discusses this conjecture and its relationship with the lower bound of g in detail. Section B.2 considers several conjectures that would make the analysis of the general optimal 20

mechanism or lower bound more structured and tractable. However, we also show a counterexample to each conjecture, further justifying the complexity of the optimal mechanism and the value of the approximately optimal construction (Thm. 3.1). We leave Conj. 4.1 as an open question for future work. Based on our estimates of the relative size of C, τ, B and proving costs (Rems. 4.1 to 4.4), our main recommendation is to use designated equilibria (Rem. 4.5). The following subsection argues that the practicality and near-optimality of the best designated equilibrium make it a powerful tool.

4.1

Recommendations to practitioners

The results in Section 3 are readily interpretable and have immediate applicability for blockchain protocol design today. This section distills these takeaways. First, we begin with a set of observations that help frame the results by considering the magnitude of the model’s variables based on empirical reference values. Remark 4.1. C is large. We believe that protocol designers should model the cost of a liveness penalty as being quite large. For example, in the zk-EVM model, the “economic loss” of a liveness penalty is a missed slot because the fork-choice rule will reject a block without an accompanying proof. Even though blocks on average have relatively low MEV payments, there are occasional, extremely large rewards (c.f., a recent block (6) with 189 ETH of MEV ≈ $440,000 at April 2026 prices). The attack model in this situation is the proposer of the following slot, who stands to benefit greatly from the previous block not being included and thus capturing the MEV for themselves. To be robust during these high-volatility periods, protocols should consider that a liveness penalty may have a very high economic cost. Remark 4.2. Proving cost is relatively small. Remember that our model uses the commonvalue setting, where we assume a unit proving cost compared to the liveness penalty C (i.e., if C = 100, then the liveness penalty is 100× the cost of generating a proof). Given the size of C described above, we think designers should consider the proving cost as a small fraction of it. For example, in the zk-EVM use-case, we see prices for proofs on today’s blocks are on the order of $0.1 (19), though this number may go up based on Ethereum’s resulting scaling and doesn’t factor in the upfront cost of purchasing hardware. For other verifiable workloads, the ratio between the proving cost and the liveness penalty might be smaller. For example, if the protocol is trying to procure a verifiable inference on an LLM, the cost of running it (e.g., on a TEE) may be relatively higher compared to the cost of not getting the result delivered to the user. In this regime, the protocols may choose different parameters. Still, we think for a majority of blockchain protocols, liveness will be a first-order concern, so the large-C paradigm is the focus of this work. Remark 4.3. Honest fraction τ is at least moderate. The honest proportion of the prover set τ plays an important role in our analysis. Unlike the consensus literature that typically requires a 2/3 honesty assumption, our mechanism is general for any value of τ . Of course, as τ → 0+ , the worst-case protocol cost will approach C (at τ = 0, the adversary can deterministically cause a liveness penalty), but we believe that assuming a non-zero fraction of the provers are honest is reasonable. One justification for this assumption is that staking provides a budget constraint for the attacker. For example, with τ = 0.5, we could view the attacker budget as being able to stake (or bribe) up to 50% of the prover set. For larger values of τ (à la the 2/3 honesty assumption of Byzantine consensus), the results are even stronger. In Fig. 3.2, we see that Ct is super-exponential in τ , meaning for moderate to large values of τ , the minimizer of g is designated for many values of C and thus the lower bound is tight (Lem. 3.4). In Fig. 3.3, we see that the τ coefficient on the log scaling meaningfully reduces the protocol cost 21

in absolute terms. Asymptotically, the optimal unstaked protocol loss scales as O (log(C)/τ ). If τ = Ω(1), the logarithmic scaling of the loss is preserved. If τ does approach zero, but has scaling τ = Ω(1/polylog C), then the loss scales faster, but only as O(polylog C). Remark 4.4. The aggregate staking amount B is large. In our model, we consider the total amount of stake put up by the provers (Cor. 3.2). Asymptotically, we see that if B = Θ(C), the protocol loss scales constantly if τ is constant in C (Lem. 3.12). While B being the same order as C sounds far-fetched in light of the magnitude of C (Rem. 4.1), consider that B is the total amount of stake rather than an individual’s contribution. As such, even if C is on the order of $10mm worth of capital (1.5 orders of magnitude higher than discussed in Rem. 4.1), then asking the prover set in aggregate to stake that much is plausible. For example, if there were 100 provers, each would have to stake $100, 000. In Ethereum today, the minimum validator balance is 32 ETH ≈ $74, 000 at April 2026 prices, meaning the provers would be asked to stake a mere 33% more than the solo stakers already do today. Remark 4.5. Practitioners should use the optimal designated uniform committee equilibrium (Def. 3.1). This confident recommendation is grounded in the empirical estimates from the Ethereum ecosystem of: the magnitude of MEV spikes (Rem. 4.1), the current average cost of generating SNARKS for EVM blocks (Rem. 4.2), reasonable honesty assumptions (Rem. 4.3), and the dollar amount of capital that validators currently stake (Rem. 4.4). With this context, the theoretical results are extremely compelling. Lem. 3.4 shows us that any designated equilibrium is implementable; Rem. 3.3 notes the simplicity and interpretability of the payment rule. Thm. 3.1 demonstrates that the optimal designated loss is at most the cost of generating a single proof larger than the optimal loss; in light of today’s proving costs, this may be less than a dollar (Rem. 4.2). Lem. 3.12 shows that if the aggregate stake is of the same order as C, which Rem. 4.4 argues is reasonable, then the optimal protocol will only incur a constant cost. Beyond the optimality of protocol loss considerations, designated equilibria are readily interpretable and have many similarities to familiar permissionless consensus protocols that underpin today’s blockchains. The analogs are striking. In both, a single node is elected each round to have a “special role” (e.g., the leader in Tendermint (9)). Further, each suggests a committee that “checks” the power of the single node (e.g., the attesting committee in HLMD GHOST (13)). Lastly, each leverages staking as a form of accountability (e.g., “accountable safety” in Casper (12) and “accountable liveness” (32)). As such, we believe the blockchain community will be open to seriously considering our design as a viable architecture for implementing prover markets and general procurement tasks. Based on the above, we strongly advocate for the usage of the optimal designated equilibrium. Namely, the protocol designed can find D̂j (Def. 4.1) and use the resulting optimal committee size j and mixing probability s. However, if the protocol designer only wants to consider symmetric equilibria, then we also provide pragmatic advice when considering the optimal symmetric approach. Remark 4.6. How to implement symmetric equilibria. If C is exceedingly large, we may be in the symmetric regime (e.g., C > Ct Def. 3.6) and the optimal symmetric equilibrium may be implementable (Lem. 3.6). In that case, the lower bound is tight, and this symmetric equilibrium is optimal. Alternatively, the protocol designer might care about the type of permissionlessness in the architecture. For example, if the protocol cannot require stake and provers are free to come and go at will in any round (the fully permissionless environment as defined in (33)), then a lottery mechanism (Def. A.2) is a good fit and still achieves a 2−approximation of the optimal loss (Lem. A.1), leading to the same asymptotic scaling.

22

5

Conclusion

This paper studies how blockchain protocols can leverage the asymmetry between performing computational work and verifying it. We argue that a robust procurement mechanism should withstand a Byzantine attacker and model the protocol as a mechanism design problem. Given the economic loss caused by a liveness penalty, the protocol aims to minimize its loss under an attacker behaving arbitrarily with a portion of the nodes in the network. Our results are theoretical and have clear insights for practitioners.

References [1] Mohsen Ahmadvand, Rok Pajnič, and Ching-Lun Chiu. 2026. push0: Scalable and Fault-Tolerant Orchestration for Zero-Knowledge Proof Generation. arXiv preprint arXiv:2602.16338 (2026). [2] David Ribeiro Alves, Vishnu Patankar, Matheus Pereira, Jamie Stephens, Nima Vaziri, and Sreeram Kannan. 2026. EigenAI: Deterministic Inference, Verifiable Results. arXiv preprint arXiv:2602.00182 (2026). [3] Axiom. 2023. We are announcing Axiom, the ZK coprocessor for Ethereum. https://x.com/ axiom_xyz/status/1620104714322051073 [4] Moshe Babaioff, Robert Kleinberg, and Christos H Papadimitriou. 2007. Congestion games with malicious players. In Proceedings of the 8th ACM conference on Electronic commerce. 103–112. [5] Maryam Bahrani and Naveen Durvasula. 2024. Resonance: Transaction fees for heterogeneous computation. arXiv preprint arXiv:2411.11789 (2024). [6] MEV-Boost Bot. 2026. High Proposer Payment Alert! status/2024852422460321829

https://x.com/mevproposerbot/

[7] Brevis. 2025. Announcing Pico Prism, the state-of-the-art zkVM for Ethereum real-time proving. https://x.com/brevis_zk/status/1978430670390133237 [8] Brevis. 2025. Brevis ProverNet Whitepaper. provernet.pdf

https://brevis.network/whitepaper/

[9] Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2018. The latest gossip on BFT consensus. arXiv preprint arXiv:1807.04938 (2018). [10] Vitalik Buterin. 2021. endgame.html

Endgame.

https://vitalik.eth.limo/general/2021/12/06/

[11] Vitalik Buterin. 2026. Potential ZK-EVM Rollout Tweet. https://x.com/VitalikButerin/ status/2007559523528233041 [12] Vitalik Buterin and Virgil Griffith. 2017. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437 (2017). [13] Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X Zhang. 2020. Combining ghost and casper. arXiv preprint arXiv:2003.03052 (2020). 23

[14] Vincent Conitzer and Makoto Yokoo. 2010. Using mechanism design to prevent false-name manipulations. AI magazine 31, 4 (2010), 65–78. [15] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. 2020. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 910–927. [16] Soubhik Deb, Robert Raynor, and Sreeram Kannan. 2024. Stakesure: Proof of stake mechanisms with strong cryptoeconomic safety. arXiv preprint arXiv:2401.05797 (2024). [17] Nicola Dimitri, Gustavo Piga, and Giancarlo Spagnolo. 2006. Handbook of procurement. Cambridge University Press. [18] Ethereum.org. 2026. Spin up your own Ethereum node. https://ethereum.org/developers/ docs/nodes-and-clients/run-a-node/ [19] Ethproofs. 2026. Provers – Ethproofs. https://ethproofs.org/provers [20] Flashbots. 2024. Introducing BuilderNet. introducing-buildernet/4173

https://collective.flashbots.net/t/

[21] Ethereum Foundation. 2026. Phase 0 – The Beacon Chain. https://github.com/ethereum/ consensus-specs/blob/master/specs/phase0/beacon-chain.md [22] Pranav Garimidi, Michael Neuder, and Tim Roughgarden. 2025. Tullock Contests in the Wild: Applications in Blockchains. ACM SIGecom Exchanges 23, 1 (July 2025), 24–34. [23] Pranav Garimidi, Michael Neuder, and Tim Roughgarden. 2026. Beyond Winner-Take-All Procurement Auctions. arXiv preprint arXiv:2603.27779 (2026). [24] Sophia Gold. 2025. Shipping an L1 zkEVM #1: Realtime Proving. https://blog.ethereum. org/2025/07/10/realtime-proving [25] Jens Groth. 2016. On the size of pairing-based non-interactive arguments. In Annual international conference on the theory and applications of cryptographic techniques. Springer, 305–326. [26] Lioba Heimbach, Lucianna Kiffer, Christof Ferreira Torres, and Roger Wattenhofer. 2023. Ethereum’s proposer-builder separation: Promises and realities. In Proceedings of the 2023 ACM on Internet Measurement Conference. 406–420. [27] Infura. 2026. Infura – Web3 Development Platform. https://www.infura.io/ [28] George Karakostas and Anastasios Viglas. 2003. Equilibria for networks with malicious users. In International Symposium on Algorithms and Computation. Springer, 696–704. [29] Mikhail Komarov. 2023. proof-market

=nil; Proof Market.

https://nil.foundation/blog/post/

[30] Eigen Labs. 2025. EigenCloud Whitepaper. https://docs.eigencloud.xyz/assets/files/ EigenCloud_Whitepaper-127a6743029d2c4858e7633196c47ea4.pdf

24

[31] Succinct Labs. 2025. SP1 Hypercube announcement thread. https://x.com/SuccinctLabs/ status/1925306484281553262 [32] Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Luca Zanolini. 2025. Accountable liveness. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. 3431–3445. [33] Andrew Lewis-Pye and Tim Roughgarden. 2023. Permissionless consensus. arXiv preprint arXiv:2304.14701 (2023). [34] Barnabé Monnot. 2024. Unbundling staking: Towards rainbow staking. https://ethresear. ch/t/unbundling-staking-towards-rainbow-staking/18683 [35] Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer. 2006. When Selfish Meets Evil: Byzantine Players in a Virus Inoculation Game. In 25th Annual Symposium on Principles of Distributed Computing (PODC). Denver, Colorado, USA. [36] Minghao Pan, Bruno Mazorra, Christoph Schlegel, and Akaki Mamageishvili. 2024. On sybilproof mechanisms. arXiv preprint arXiv:2407.14485 (2024). [37] Web3 Pi. 2025. Web3 Pi: Your Ethereum Node on Raspberry Pi. https://www.web3pi.io/ [38] Aaron Roth. 2008. The price of malice in linear congestion games. In International Workshop on Internet and Network Economics. Springer, 118–125. [39] Uma Roy, John Guibas, M Pai, K Kulkarni, and Dan Robinson. 2024. Succinct network: Prove the world’s software. https://resources.cryptocompare.com/asset-management/20420/ 1754473565450.pdf [40] Toni Wahrstätter. 2026. Blocks Are Dead. Long Live Blobs. blocks-are-dead-long-live-blobs/24611

https://ethresear.ch/t/

[41] Toni Wahrstätter. 2026. MEV-Boost Dashboard. https://mevboost.pics/ [42] Wenhao Wang, Lulu Zhou, Aviv Yaish, Fan Zhang, Ben Fisch, and Benjamin Livshits. 2025. Prooφ: A ZKP Market Mechanism. In International Conference on Financial Cryptography and Data Security. Springer, 180–196. [43] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. 2004. The effect of false-name bids in combinatorial auctions: New fraud in Internet auctions. Games and Economic Behavior 46, 1 (2004), 174–188. [44] RISC Zero. 2025. Boundless Whitepaper. https://read.boundless.network/ [45] ZKsync. 2025. Airbender enters the Ethproofs leaderboard as the fastest zkVM. //x.com/zksync/status/1983243385147146291

25

https:

A

Section 3 Appendices

A.1

Expanded form of (PROG1)

It is helpful to consider the protocol objective (PROG1) as a two-layer optimization. Once the equilibrium vector s is set, then the minimal protocol loss (encoded as payments made under different delivery vectors) can be solved as a linear program. Definition A.1 (Two-level optimization). First, consider an arbitrary fixed strategy vector s ∈ [0, 1]n . The protocol can then solve the following linear program (LP) in p. L(s) := min t s.t.

E

p,t≥0 n hX

dH ∼sH

(LP2) pi (dA | dH ) + C

i=1

n Y

(1 − di )

i

∀(A, dA )

(attacker)

≥1

∀i if si > 0

(equil. 1)

≤1

∀i if si < 1

(equil. 2)

i=1

 pi (1 | d−i ) − pi (0 | d−i ) d−i ∼s−i   E pi (1 | d−i ) − pi (0 | d−i ) E

≤t



d−i ∼s−i

This LP uses an epigraph variable to define the upper bound constraints on the protocol loss given any attacker set and action pair (attacker). Further, the equilibrium constraints (equil. 1,equil. 2) ensure that the strategy is an equilibrium implemented by p, i.e., s ∈ S(p). If si ∈ (0, 1), then these constraints are both tight at 1, and otherwise, deterministically delivering or not delivering are dominant strategies. Given this inner LP, we define the outer optimization problem, OPT1 = min L(s),

(2)

s∈[0,1]n

and we have that the solution to this program is the solution to (PROG1) and minimizes the protocol’s objective.

A.2

Proof of Lem. 3.1

Lemma (Lower bound function g(s)). Consider the protocol parameterized with (h, a, n, C). Without loss of generality, re-index the players such that s is decreasing in i. Then define g(s) as,   n X  Y Y g(s) := max si + C (1 − si ), C (1 − si ) . (3)   i∈[n]

i∈[n]

i=a+1

Then the solution to the following program, OPT2 := min g(s) s∈[0,1]n

(PROG2)

s.t., 1 ≥ s1 ≥ s2 ≥ . . . ≥ sn ≥ 0 is a lower bound on the solution to (PROG1): OPT2 ≤ OPT1. Proof. First, consider a restricted attacker that chooses between two options: behaving honestly (e.g., playing the strategy si for all corrupted indices i ∈ A) and fully not delivering, with the largest a values of s (e.g., setting di = 0 for d ∈ [a]). 26

P If the attacker plays honestly, the protocol must pay at least i∈[n] si to the provers in order for the mechanism to be individually rational. Further, there may be some non-zero probability of the event that all of the provers don’t deliver and the protocol incurs the penalty C. In particular, since Q the provers are mixing independently, the probability that none of them deliver is i∈[n] (1 − si ) (recall that si is their mixing probability for delivering). Thus, the left branch of the max in g(s) is exactly the protocol’s expected cost under an attacker that plays the fully honest strategy. By similar reasoning, if the attacker doesn’t deliver (di = 0) with the largest a values of si , then the protocol will incur the penalty with Q probability equal to that of the smallest h indices (the remaining honest players) not proving ni=a+1 (1 − si ). Thus, the right branch of the max is a lower bound on the protocol’s cost under a fully non-delivering attacker. Since the max of these two branches is always a viable action for the attacker and the protocol loss (Def. 2.2) is defined over all attacker actions and sets, this is a lower bound on OPT1.

A.3

Proof of Lem. 3.2

Lemma (Minimizer of g occurs at equality). The vector s∗ that minimizes g occurs where the two branches of the max are equal. More formally, we have X

s∗i + C

i∈[n]

Y

n Y

(1 − s∗i ) = C

(1 − s∗i ).

i=a+1

i∈[n]

Proof. We show that the optimizer can never be strictly in either branch. Recall that,   n X  Y Y g(s) := max si + C (1 − si ), C (1 − si ) ,   i∈[n]

i=a+1

i∈[n]

and define L, R as the left and right branches of the max: X Y L(s) := si + C (1 − si ) i∈[n]

R(s) := C

i∈[n]

n Y

(1 − si ).

i=a+1

Assume, towards a contradiction, that s∗ (the minimizing s of g) is strictly in the right branch of the max L(s∗ ) < R(s∗ ). First note that s∗i < 1 for all i ∈ {a + 1, . . . , n}, because if any s∗i = 1, then R(s∗ ) would be zero and it couldn’t be the minimizer because L(s∗ ) > 0. Now consider the partial derivatives of R with respect to each value s∗i , where i ∈ {a + 1, . . . , n}, n Y ∂R = −C · (1 − s∗j ) < 0. ∂s∗i j=a+1 j̸=i

Since these partials are all negative, increasing the value of any si will decrease the objective. Choose some i ∈ {a + 1, . . . , n} and set s′i = s∗i + ε while holding all other values s∗j for j ̸= i constant. Then, by continuity, we can choose ε small enough such that s′ still respects the original ordering constraints and we are still in the right branch of the max. Under our new strategy vector s′ , the objective has decreased, which means the original s∗ could not have been optimal. Intuitively, if we are strictly in the right branch, then we can increase one of those values of si , lowering the value of the objective and contradicting the optimality. 27

Now assume, again towards a contradiction, that s∗ (the minimizing s of g is strictly in the left branch of the max L(s∗ ) > R(s∗ ). First, consider that R is unchanged under perturbation of si for i ∈ [a]. Now take two coordinates i > j ∈ [a] and by the strictness of the inequality, there exists ε such that with s′i = s∗i + ε and s′j = s∗j − ε, ordering constraints are preserved. Then evaluating the difference L(s′ ), we have X Y s∗k + (s′i + s′j ) +C (1 − s∗k )(1 − (s∗i + ε))(1 − (s∗j − ε)) . L(s′ ) = k∈[n] k̸=i,j

|

k∈[n] k̸=i,j

{z

}

sum term

|

{z

product term

}

The sum term is exactly the same as L(s∗ ). Expanding the product term, we have Y Y (1 − s∗k )(1 − (s∗i + ε))(1 − (s∗j − ε)) = (1 − s∗k )((1 − s∗i )(1 − s∗j ) + ε(s∗j − s∗i ) − ε2 ) k∈[n] k̸=i,j

k∈[n] k̸=i,j

<

Y

(1 − s∗i ),

i∈[n]

where the last inequality comes from the fact that s∗j −s∗i is negative, giving the following inequality ∀ε > 0, (1 − s∗i )(1 − s∗j ) + ε(s∗j − s∗i ) − ε2 < (1 − s∗i )(1 − s∗j ). Thus, the L(s′ ) < L(s∗ ), contradicting the optimality of s∗ . So the minimizing s∗ occurs at equality of L(s∗ ) = R(s∗ ).

A.4

Proof of Lem. 3.3

Lemma (Characterizing the minimizer of g). Let s∗ denote the minimizing vector s∗ := arg mins∈[0,1] g(s). Then s∗ is either a designated uniform committee equilibrium or a symmetric committee equilibrium (Defs. 3.1 and 3.2). Proof. We perform this analysis using (PROG3). First, we will show that if s∗i < 1, ∀i ∈ [n], then the shape of the optimizer is symmetric. Let A = {1, . . . , a}, H = {a+1, . . . , n} denote the attacker and honest controlled indices and Y Y πA = (1 − si ), πH = (1 − si ) i∈A

i∈H

denote the probability of the attacker and honest sets having no deliveries respectively. First we show that all honest players with non-zero mass have the same probability. Assume, towards a contradiction, that there exists i, j ∈ H such that si > sj . Then consider s′ where all indices maintain their corresponding value in s except i, j and s′i = si + ε,

s′j = sj − ε,

for some small eps. This transformation preserves the order and the sum of s. For the product term πH each of the non i, j indices are the same and (1 − s′i )(1 − s′j ) = (1 − (si + ε))(1 − (sj − ε)) = (1 − si )(1 − sj ) + ε(sj − si ) − ε2 < (1 − si )(1 − sj ). 28

(by sj < si , ε > 0)

Thus, CπH , the objective of (PROG3), decreases. Examining the equality constraint of (PROG3), we have X X si + CπH (πA − 1) = 0. si + CπA πH = CπH =⇒ i∈[n]

i∈[n]

Given πH decreased but the sum is preserved, we need to restore feasibility. Choose an attacker index k ∈ A and fix all other values of s. Then the equality constraint becomes Y  X (1 − si ) (1 − sk ) = 0 (4) si + CπH sk + i∈[a] i̸=k

i∈[n] i̸=k

Notice that (4) is affine in sk . Thus, given a new value of πH , we can solve this linear equation by increasing some corresponding value of sk to the unique value that restores the feasibility. With the reduced objective and the constraint satisfied, the transformation decreased the optimal value of (PROG3), which is a contradiction. We have that si = sj , ∀i, j ∈ H, si , sj > 0. Intuitively, this argument pushes probability mass up from the smallest values of H to the higher probability members, concentrating the mass symmetrically among them. Thus we have sa+1 = sa+2 = . . . = sk , where k is the committee size of the symmetric equilibrium. Next, we show that the attacker indices also share that same value. Assume, again towards a contradiction, that there exists i ∈ A such that si > sa+1 (i.e., there is an attacker index with a higher probability that the first honest index). Recall that we are in the case where si < 1, ∀i, so there can be no deterministic deliverers. Then consider s′ where we transform s′a+1 = s′a+1 + ε. The objective CπH decreases. Again, we turn to feasibility. Since (4) is affine in si , we adjust si to restore equality with 0. Again, we have reduced the value of the conjectured optimizer, and we have a contradiction. Intuitively, this step equalizes the attacker values with the honest ones because any probability mass that isn’t evenly spread over all indices is being “wasted” on the attacker. So far, we know that if si > 1 for all i, then the shape of the optimizer is a symmetric committee equilibrium s1 = s2 = . . . = sa+1 = . . . sk (Def. 3.2). Now consider the case that there exist some deterministic deliverers in s (which, by the ordering constraint, implies s1 = 1). First, we show that for all i, j such that si , sj ∈ (0, 1), si = sj . In words, this is the fact that all the non-deterministic players have the same P probability. Notice that with s1 = 1, the objective remains CπH , but the constraint changes to i∈[n] si = CπH . This case is much simpler. For any i, j ∈ [n] if si > sj and si , sj ∈ (0, 1), perform the transformation s′i = si + ε,

s′j = sj − ε.

Thus sum is preserved and the objective CπH is weakly decreasing (it is strictly decreasing only if j ∈ H. Thus, the equality can be preserved and the objective is weakly lower, which is a contradiction. So all non-deterministic players have the same value. Lastly, we show that there is only one deterministic deliverer, thus s1 = 1 =⇒ si < 1, ∀i ∈ {2, . . . , n}. Assume towards a contradiction, that there are multiple players with si = 1. Let k denote the largest index such that sk = 1 and consider the modified equilibrium s′ , where all indices are the same except s′k = 1 − ε. This reduces the sum, but doesn’t change the objective. Using (4), we can solve for a value δ such that s′a+1 = sa+1 + δ restores the feasibility and strictly increases the value of sa+1 , which reduces the objective and leads to a contradiction. Intuitively, this step exploits the fact that multiple deterministic deliverers doesn’t help because πA is already 0 with just s1 = 1. That probability mass can be shifted down to reduce CπH instead. Thus, if there exists a deterministic deliverer, the shape of the minimizer is a designated uniform committee equilibrium (Def. 3.1). 29

A.5

Proof of Lem. 3.4

Lemma (All designated uniform committee equilibria are implementable). Given a designated uniform committee equilibrium parameterized by committee size k ≤ n − 1 and a mixing probability s, there exists a payment rule that implements the equilibria and achieves the minimal protocol loss of 1 + ks. Proof. We construct a payment rule that satisfies the following properties: (i) only pay if a proof is delivered, and (ii) always pay 1 + ks no matter how many proofs are delivered. We achieve property (i) by conditioning all payments on player 1 delivering. Since player 1 is designated with s1 = 1, this doesn’t impact the equilibrium conditions. The committee members (indices {2, . . . , k + 1}) ks mix with uniform probability s and have a prize of size 1−(1−s) k split evenly among the committee members who deliver. We formalize this below. Notice that the L1-norm ||d||1 counts the number of deliveries. Then consider the following payment rule   if d1 = 0  0 if ||d||1 = 1 p1 (d) = 1 + ks   1 − (1−s)k ksk if ||d||1 > 1 1−(1−s) ( 0 if d1 = 0 pi>1 (d) = ks 1 if di = 1, i ∈ {2, . . . , k + 1}. · 1−(1−s)k ||d||1 −1 We can quickly confirm that this is an equilibrium. Consider player 1’s expected payoff from delivering,   (1 − s)k ks k E[p1 (d)] = (1 + ks) · (1 − s) + 1 − · (1 − (1 − s)k ) 1 − (1 − s)k = 1. The other players also have the same expected payoff from delivering E[pi>1 (d)] =

k−1  X j=0

1 ks · · Pr[X = j] k 1 − (1 − s) j + 1

 = 1,

where X ∼ Binomial(k − 1, s). Thus [1, s, . . . , s, 0, . . . , 0] is an equilibrium. For any ||d||1 > 1, the protocol pays 1 + ks: 1−

(1 − s)k ks ks + = 1 + ks. k 1 − (1 − s) 1 − (1 − s)k

Similarly, if ||d||1 = 1, the protocol pays 1 + ks.

A.6

Proof of Thm. 3.1

Theorem (Payment rule reduction). Given any payment rule, p, and corresponding equilibrium, s ∈ S(p), there exists a modified payment rule, p′ , and a modified equilibrium, s′ ∈ S(p′ ), such that the modified equilibrium is designated and ℓ(p′ , s′ ) ≤ ℓ(p, s) + 1. 30

Proof. Without loss, re-index the entries of s to be decreasing, 1 ≥ s1 ≥ s2 ≥ . . . ≥ sn ≥ 0. If s1 = 1, the equilibrium is already designated and the claim holds trivially. Thus we consider if s1 < 1. We assign s′1 → 1 and keep all remaining entries of s. That is, s′ = [1, s2 , s3 , . . . , sn ]. To construct p′ , we start by paying player 1 exactly 1 if they deliver and 0 otherwise, independently of the rest of the players’ actions. For the remaining players, their payments under p could depend on the realized action of player 1, d1 . Under p′ , we pay them exactly the average of their payments weighted by s1 , but only if player 1 does deliver. More formally, we set ( pi (d|d1 = 0) · (1 − s1 ) + pi (d|d1 = 1) · s1 if d1 = 1 ′ pi (d) = 0 otherwise. Under s′ , the honest player 1 will always deliver, so si>1 maintains the same expected payments and ′ ′ ′ thus remains an honest equilibrium,  i.e., P s ∈′ S(p ). Furthermore, p has the following properties: a) its total payment is always in 0, i∈[n] si for all delivery outcomes d, and b) it never pays when there is no delivery. With p′ , s′ defined, consider the loss of any attacker set and delivery decision, A, dA , under the original p, s. Again, we bound this loss below by the maximum of the attacker being fully honest and the attacker fully non-delivering with the a largestPvalues of si . The loss under an honest attacker is at least the total payment, which is at least i∈[n] si since for s to be an equilibrium, expected payments must cover expected proving costs. Qn Furthermore, the loss under the fully nondelivering attacker is at least the penalty term C · i=a+1 (1 − si ) even if there are no payments. Together, we have ℓ(p, s) ≥ max

X

n Y

si , C ·

 (1 − si ) .

(5)

i=a+1

i∈[n]

Now consider the loss of the new payment rule p′ under the modified equilibrium s′ . We break the possible attacker actions into two cases. If the attacker corrupts the designate and doesn’t deliver (i.e., 1 ∈ A, a1 = 0), then p′ pays nothing and the highest possible loss occurs when the Q attacker controls the largest values s1 , . . .P , sa , resulting in a loss of C · ni=a+1 (1 − s′i ). Otherwise, the designate delivers and cost is always s′i . Thus ′

′

ℓ(p , s ) = max

X

s′i , C ·

i∈[n]

n Y

(1 − s′i ) i=a+1

 .

(6)

The first term of Eq. (5) is 1 − s1 larger than the first term of Eq. (6). The second terms of Eq. (5) and Eq. (6) are equal if a ≥ 1. It follows that ℓ(p′ , s′ ) ≤ ℓ(p, s) + 1.

31

A.7

Proof of Lem. 3.5

Lemma (Symmetric payment rule reduction). Any payment rule p that implements a symmetric equilibrium s with a committee size of k can be transformed into an anonymous payment rule p′ with the following form: ( ft /t if di = 1, ||d||1 = t, i ≤ k ′ pi (d) = 0 otherwise. where ft is a fixed total prize that the protocol pays under the event that there are exactly t proofs delivered. The symmetric vector is still an equilibrium under the modified payment rule s ∈ S(p′ ) and p′ has weakly lower cost ℓ(p′ , s) ≤ ℓ(p, s). Proof. Suppose p implements s = (s, . . . , s, 0, . . . , 0) for s ∈ (0, 1) where k ∈ [n] denotes the number of committee members. First, let p′i (d) = 0, ∀i > k. This weakly lowers the loss of the protocol because the players with index i > k deliver with probability 0 and thus any positive payments to them only increase the cost to the protocol without reducing the probability of a penalty. Further, these payments don’t interact with the equilibrium conditions of the k committee members because the index i > k players are playing the pure strategy of never delivering and they will continue to not deliver. Now, we only consider the payments to the committee members with indices i ≤ k, who are playing the symmetric strategy si = s. Partition the outcomes of d into sets based on the count of proofs delivered t = ||d||1 . Notice that for each player i in the committee, the probability of each outcome that results in exactly t − 1 other deliveries is identical: st−1 (1 − s)k−t . Further, the probability of each outcome that results in exactly t other deliveries is: st (1 − s)k−t−1 . Thus, consider an intermediate payment rule p̂, where the payment received by player i in the case that there are exactly t deliveries is, ( pi,t,1 if i ≤ k, di = 1, ||d||1 = t p̂i (d) = pi,t,0 if i ≤ k, di = 0, ||d||1 = t, where pi,t,1 and pi,t,0 are the average payment that player i receives under the original payment rule p if they deliver or don’t deliver respectively and there are a total of t deliveries: pi,t,1 =

1

X

k t−1

pi (d),

pi,t,0 =

1
k t

d:||d||1 =t di =1

X

pi (d).

d:||d||1 =t di =0

Under the intermediate payment rule p̂, player i has exactly the same expected payment and thus s continues to be an equilibrium strategy. Next, we average the payments over all committee members. Define p̄t,1 and p̄t,0 to be the average payments for delivering and not delivering among the committee members conditioned on exactly t deliveries: k

p̄t,1 =

k

1X pi,t,1 , k

p̄t,0 =

i=1

1X pi,t,0 , k i=1

If we pay all of the committee members according to p̄ (e.g., if there are t deliveries, pay each of the deliverers p̄t,1 and each of the non-deliverers p̄t,0 ), then we have exactly the same payments as p. Since the equilibrium has not changed, we have ℓ(p̄, s) = ℓ(p, s).

32

To conclude, we perform one more reduction where we remove the payments made to nondeliverers. Let f¯t be the aggregate payments made to all players in the event of exactly t deliveries: f¯t = t · p̄t,1 + (k − t) · p̄t,0 . Consider the payment rule where only the t deliverers are paid exactly f¯t /t and the non-deliverers are paid 0. This preserves the total payment made by the protocol, but might make delivering too attractive. In particular, the expected reward from delivering is now  k  X k − 1 t−1 f¯t V := s (1 − s)k−t . t t−1 t=1

Our concern about overpaying for deliverers is encoded by f¯t /t = p̄t,1 + k−t t p̄t,0 ≥ p̄t,1 . That is, when we pay f¯t /t only to the deliverers, they are weakly better off delivering under this payment rule than they were delivering under the p̄ payment rule. In order to ensure s is still an equilibrium, the expected value of payments conditioned on delivery must be exactly 1, because we are not paying anything to the non-deliverers. Further, under the p̄ rule, we had the following indifference condition:  k  X k − 1 t−1 s (1 − s)k−t (p̄t,1 − p̄t−1,0 ) = 1, t−1 t=1

where the expected value of delivering less the expected value of not delivering is exactly 1. Since f¯t /t ≥ p̄t,1 ≥ p̄t,1 − p̄t−1,0 , we scale the final payment rule by dividing by V : (¯ ft if di = 1, ||d||1 = t, i ≤ k p′i (d) = V t 0 otherwise. Since the non-deliverers are not paid, we only have to check the indifference condition of delivery:  k  X k − 1 t−1 f¯t s (1 − s)k−t = V /V = 1. t−1 Vt t=1

¯ Since V ≥ 1, ftt preserves the exact payments of p, and s is still an equilibrium, we have ℓ(p′ , s) ≤ ℓ(p, s). To match the final form of the lemma statement, simply let fi = f¯i /V .

A.8

Expanded form of (LP1) min

f1 ,...fn ≥0

s.t.,

t

h   X h i=0

i

h   X h i=0

i

(LP1)

si (1 − s)h−i fa+i ≤ t si (1 − s)h−i fa−1+i ≤ t

.. .

(attack delivers a)

(attack delivers a − 1)

(attacker delivers with {a − 2, a − 3, . . . , 1})   h X h i s (1 − s)h−i fi + C(1 − s)h ≤ t (attack delivers 0) i i=1  n  X n − 1 i−1 fi (equilibrium condition) s (1 − s)n−i = 1 i−1 i i=1

33

A.9

Proof of Lem. 3.6

Lemma (Optimal symmetric implementability). For a given (h, a, n), a symmetric minimizer of g is implementable if C≥

hn(h + 1)n−1 . (h + 1)a − 1

h Proof. (LS1) can be solved by setting fh+1 = C 1−s (from the first two equations in the system), s and then recursively solving fh+i by substituting fh+j for j < i into the equation. Algebraically, this yields the following relation:  fh+i = C

1−s s

h X     i−1 1−s j j h+j−1 · · . (−1) s j j=0

Since the values of fh+1 , fh+2 , . . . , fh+a are fully determined, the feasibility check needs to confirm that all of their values are positive. Thus we need
to evaluate the sign of the alternating j sum. The magnitude of the j th term of the sum is h+j−1 ( 1−s s ) . We will consider the pair-wise j ratio of the odd (negative) and even (positive) terms. This ratio is h+(j+1)−1 j+1
h+j−1 j

1−s j+1 h+j 1−s s · , =
1−s j j+1 s s

which is weakly decreasing in j, so it is maximized at j = 0, which gives h · 1−s s . For the sum to be positive, this ratio must be less than 1 (i.e., the positive term is larger than the negative terms) and the monotonicity in j ensures that the remaining terms are also less than 1, which yields h·

1−s h ≤ 1 =⇒ s ≥ . s h+1

Further, consider any value of h · 1−s s > 1. Then evaluate fh+2 :  fh+2 = C

1−s s

h   1−s 1−h· . s

h Then h · 1−s s > 1 =⇒ fh+2 < 0. This implies that s ≥ h+1 is both a necessary and sufficient condition for of fh+i > 0 and thus the symmetric equilibrium to be implementable. From the equality condition on the minimizers of g (Lem. 3.2), we have

ns + C(1 − s)n = C(1 − s)h =⇒ C =

ns (1 − s)h (1 − (1 − s)a )

h , Evaluating this at the boundary point s = h+1

C= =

h n( h+1 ) h h (1 − ( h+1 ))h (1 − (1 − ( h+1 ))a )

hn(h + 1)h+a−1 , (h + 1)a − 1

which is the desired bound. 34

.

A.10

Lottery payment rules

Definition A.2 (Lottery payment rule). A lottery payment rule sets a prize with magnitude P , which is delivered at random to a single deliverer if there are proofs delivered. Under no deliveries, no payment is made. More formally, let D ⊆ [n] denote the set of deliverers, where |D| = ||d||1 . Choose the “winner” w ∈ D index uniform randomly from the deliverers. Then the lottery payment rule p is defined as ( P if ||d||1 > 0, i = w pi (d) = 0 otherwise. The following lemma shows that this simple and intuitive payment rule is a (multiplicative) 2−approximation of optimal. Lemma A.1 (Lottery payment rules are a 2−approximation of symmetric OPT). If the minimizer of g is a symmetric committee equilibrium s∗ (Def. 3.2), then there exists a lottery payment rule p (Def. A.2) with a loss that is a two-approximation of OPT where s∗ is still an equilibrium: 2ℓ(p, s∗ ) ≤ g(s∗ ) ≤ OPT. Proof. Let s denote the symmetric minimizer of g. From the equality condition on the minimizers of g (Lem. 3.2), we have C(1 − s)h = ns + C(1 − s)h+a =⇒ ns = C(1 − s)h (1 − (1 − s)a ) ns =⇒ C(1 − s)h = . 1 − (1 − s)a

(7)

This is the optimizing value of g(s), g(s) =

ns . 1 − (1 − s)a

Choose a lottery prize of P =

ns , 1 − (1 − s)n

(8)

which ensures that all n players are indifferent between delivering and not (hence can play a mixed strategy) and s is an equilibrium:  n  X n − 1 i−1 P s (1 − s)n−i · = 1. i−1 i i=1

Notice that against a lottery, the best action the attacker can do is not deliver by setting di = 0, ∀i ∈ A. Thus the lottery achieves a loss of   ℓ(p, s) = P 1 − (1 − s)h + C(1 − s)h . Evaluating the relative error of ℓ(p, s) against g(s) and rewriting C(1 − s)h from (7) gives
ns ns ns h + ℓ(p, s) − g(s) 1−(1−s)n 1 − (1 − s) 1−(1−s)a − 1−(1−s)a = ns g(s) 1−(1−s)a

1 − (1 − s)a 1 − (1 − s)h = ≤ 1, 1 − (1 − s)n where the last step uses (1 − p)(1 − q) ≤ (1 − pq), ∀p, q ∈ [0, 1). A relative error of 1 corresponds to a 2−approximation of the optimal. 35

A.11

Proof of Lem. 3.7

Lemma (For a = 1, designated is always optimal). For all C > 1, h ≥ 1, if a = 1 then the optimal designated equilibrium is always better than the optimal symmetric: Dj∗ < Sk∗ . Proof. First, we simplify the constraint of Sk∗ with a = 1, (hk + 1)s + C(1 − s)hk +1 = C(1 − s)hk =⇒ (hk + 1)s

= C(1 − s)hk (1 − (1 − s))

=⇒ (hk + 1)s

= C(1 − s)hk s

If s = 0, then Sk∗ = C and if s > 0, then we have Sk∗ = hk + 1, which is minimized at hk = 1. Thus, S1∗ = min{C, 2}. Next, we turn to the designated constraint fixing a = 1. This gives us 1 + hj s = C(1 − s)hj , which has a unique solution s∗ ∈ (0, 1). The value of the constraint is minimized with hj = 1, so we get 1 + s = C(1 − s) =⇒ s =

C −1 , C +1

D1∗ =

2C . C +1

For C > 1, it is true that D1∗ =

A.12

2C < min{C, 2} = S1∗ . C +1

Proof of Lem. 3.8

Lemma (Minimizer of g is designated for C < 1 + 1/a). For very small penalty values C < 1 + 1/a, the minimizing vector s is a designated equilibrium. Proof. For a symmetric equilibrium s to be optimal, we know from Lem. 3.2 that the following equality holds: C(1 − s)h = ns + C(1 − s)n =⇒ n = C(1 − s)h

(1 − (1 − s)a ) . s

For all s ∈ (0, 1), h ≥ 1, we have (1 − s)h < 1 and (1 − (1 − s)a ) ≤ sa, thus we can apply the equality constraint: (1 − (1 − s)a ) s < Ca =⇒ C > n/a.

n = C(1 − s)h

Since n = a + h, we also have C > 1 + h/a which implies for all h ≥ 1, C > 1 + 1/a. Since the minimizer is only symmetric or designated (Lem. 3.3) and the symmetric equilibrium isn’t feasible for C < 1 + 1/a, the minimizer s must be designated. 36

A.13

Proof of Lem. 3.9

Lemma (Minimizer of g is symmetric for C → ∞). For large penalty values C → ∞, the minimizing vector s is a symmetric equilibrium. Proof. At C → ∞, the protocol will ensure that it never faces the catastrophic loss of receiving no proofs. Thus, both the optimal designated and symmetric equilibria will converge to the same binary vector [1, . . . , 1, 0 . . . , 0], where there are exactly a + 1 ones. This will guarantee the protocol cost stays bounded at exactly a+1. This is just the limit behavior, but for any finite C, the optimal symmetric and designated equilibria, denoted ssym , sdes respectively, will have the shapes ssym = [1 − ε, . . . , 1 − ε, 0, . . . , 0] | {z } a+1 copies ′

sdes = [1, 1 − ε , . . . , 1 − ε′ , 0, . . . , 0] | {z } a copies

where there are a+1 copies of 1−ε in the symmetric case and a copies of 1−ε′ in the designated case (because the initial coordinate is already fixed at 1). This allows us to fix attention to hj = hk = 1. Then, the designated equality constraint (Lem. 3.2) reduces to 1 + a(1 − ε′ ) = Cε′ =⇒ ε′ =

1+a , C +a

and the loss of this designated equilibrium is D1∗ = Cε′ . Similarly, the symmetric version of the equality constraint simplifies to (a + 1)(1 − ε) + Cεa+1 = Cε (a + 1)(1 − ε) = Cε(1 − εa )
a + 1 = Cε 1 + ε + . . . + εa−1 a+1
, =⇒ C = ε 1 + ε + . . . + εa−1

(dividing (1 − ε)) (9)

and the loss of this symmetric equilibrium is S1∗ = Cε. Thus it suffices to show that there exists a 1+a C such that ε < ε′ and correspondingly S1∗ < D1∗ . Plugging in the designated value ε′ = C+a to (9), we get C=

C +a 1 + ε′ + . . . + ε′a−1

C +a 1 + ε′ C +a (C + a)2 = = . 1+a C + 2a + 1 1 + C+a ≥

The inequality is true for all C > a2 . Now observe that the RHS of (9) is strictly decreasing in ε, and we confirmed that evaluating it at ε′ resulted in a value that was less than C. The optimal symmetric equilibrium solves this function exactly for C, so we must have ε < ε′ and thus S1∗ < D1∗ .

37

A.14

Proof of Lem. 3.10

Lemma (Limit behavior of Ct ). As n → ∞ the value of Ct at which the optimal symmetric equilibrium achieves a lower loss than the optimal designated equilibrium as a function of the honest proportion τ ∈ (0, 1) is: lim Ct (τ ) = ex , where 1 + x = e(1−τ )x .

n→∞

Proof. We first show that as n → ∞, the minimizing equilibria at the boundary Ct set hj = hk = h. That is both the designated and symmetric minimizers use the full honest set in the limit. First, we start with the designated case. For a given, h, n, C, the optimal designated equilibrium mixing probability, s, solves the following implicit equation 1 + (n − 1)s = C(1 − s)h . Let n → ∞ for a fixed honest fraction τ ∈ (0, 1), and observe that the LHS of the equation is increasing to infinity as s → 1 and the RHS of the equation is decreasing to zero as s → 1. Thus, in order for the constraint to hold, we have s = Θ(1/n). Define this constant as td (for designated), and let s = td /n. Then, consider the possible committee honest committee size of β ∈ (0, τ ] (which is hj in the discrete case). Then we can write the continuous version of the designated constraint 1 + (1 − τ + β)td = C(1 − td /n)βn

(10)

≈ Ce−βtd

(by exponential bound)

Using the continuous version of the designated loss, Dβ := 1 + (1 − τ + β)td =⇒ td =

Dβ − 1 . 1−τ +β

Plugging this into the exponential bound gives, Dβ = Ce

−β·

 D −1  β 1−τ +β

=⇒ C = Dβ · e

  (Dβ −1)· 1−τβ+β

.

Hence for a fixed C, we have that 1−τβ+β is strictly increasing in β ∈ (0, τ ], so Dβ must be strictly decreasing to hold the constraint tight. Thus the minimizing Dβ occurs at the endpoint β = τ . Plugging this in to (10), we get a much simplified Dτ = 1 + td = Ce−τ td

(11)

Turning to the symmetric constraint, we choose s = ts /n (for symmetric)w as the ansantz for the same reason as the designated case. Again, let β ∈ (0, τ ] denote the proportion of honest committee employed (the hk value in Def. 3.5). The continuous version of the symmetric constraint is (1 − τ + β)ts + (1 − ts /n)(1−τ +β)n = C(1 − ts /n)βn (1 − τ + β)ts + Ce−(1−τ +β)ts = Ce−βts

(by exponential bound)

Using the continuous version of the symmetric loss, Sβ := Ce−βts =⇒ (1 − τ + β)ts + Sβ e−(1−τ )ts = Sβ ,

38

and rewriting gives (1 − τ + β)ts . 1 − e−(1−τ )ts Now consider the fact that at Ct , we have that Sβ = Dτ = 1 + td . Solving for β gives Sβ =

(1 − τ + β)ts = 1 + td 1 − e−(1−τ )ts
(1 + td ) 1 − e−(1−τ )ts =⇒ β = − (1 − τ ). ts

(12)

Plugging this into Ce−βts = 1 + td , we have C = (1 + td )e(1+td )(1−e

−(1−τ )ts )−(1−τ )t ) s

.

The minimizing symmetric mechanism will choose ts to minimizes this expression over ts for a fixed target Dτ = 1 + td . Taking the derivative of the exponent with respect to ts ,  ∂  (1 + td )(1 − e−(1−τ )ts ) − (1 − τ )ts ∂s = (1 − τ )((1 + td )e−(1−τ )ts − 1). Setting this equal to zero, we get (1 − τ )((1 + td )e−(1−τ )ts − 1) = 0 1 =⇒ e−(1−τ )ts = . 1 + td Plugging this expression into our function for β (12), we get
1 (1 + td ) 1 − 1+t d β= − (1 − τ ) ts td = − (1 − τ ). ts From Dτ = Sβ , we have that e−τ td = e−βts and correspondingly τ td = βts . Plugging in the value of β gives the final result,   td τ td = − (1 − τ ) ts ts = td − (1 − τ )ts =⇒ (1 − τ )td = (1 − τ )ts and td = ts and β = τ. This derivation allows us to confirm that at the transition point, we have Sτ , which simplifies to ts . Sτ = −(1−τ )ts 1−e Combining this with (11) and the fact that ts = td (which we denote simply as t hereafter), we have that t satisfies the following equation: t 1+t= =⇒ 1 + t = e(1−τ )t . −(1−τ )t 1−e Applying this equality to (11), we have that 1 + t = Ce−τ t =⇒ e(1−τ )t = Ce−τ t =⇒ C = et , which, combined with 1 + t = e(1−τ )t is the limit of Ct given in the lemma statement. 39

A.15

Figure showing discrete values of Ct for various n

Figure A.1: This plot shows Ct (on log scale) as a function of τ for various values of n and the limit behavior of Ct as calculated in Lem. 3.10 (in red). In addition to the continuous limit (Fig. 3.2), this figure also includes the discrete values for n ∈ {40, 60, 80, 100}. The dashed lines denote the corresponding values with stake B = 10 (Section 3.4) and the red dashed line is as calculated in Cor. A.3.

A.16

Proof of Lem. 3.11

Lemma  (Asymptotic designated loss). The loss of the optimal designated equilibrium scales as log C O . τ Proof. From (11), we have Dτ = 1 + td = Ce−τ td . Rewriting with td = Dτ − 1, we get Dτ = Ce−τ (Dτ −1) =⇒ Dτ eτ Dτ = Ceτ . Multiplying through by τ gives an expression of the form yey = x, which is the definition of the Lambert W function: τ Dτ eτ Dτ = Cτ eτ =⇒ τ Dτ = W (Cτ eτ ). Using the first two terms of asymptotic expansion of the Lambert W function, we have 1 (ln(Cτ eτ ) + O(ln ln(Cτ eτ ))) τ   ln C ln ln C = +O τ τ   log C =O . τ

Dτ =

40

A.17

Proof of Cor. 3.2

Corollary (Staked lower bound function gB (s)). Extending the lower bound of Lem. 3.1, consider the protocol parameterized with (h, a, n, C) and with aggregate stake of B. Then define gB (s) as,   n  X Y Y (1 − si ), C si + C (1 − si ) − B . gB (s) := max   i=a+1

i∈[n]

i∈[n]

Then for the solution to the follow program, OPT4 := min gB (s)

(PROG4)

s∈[0,1]n

s.t., 1 ≥ s1 ≥ s2 ≥ . . . ≥ sn ≥ 0 we have OPT4 ≤ OPT1. Proof. Recall that OPT1 (the solution to (PROG1) is the minimizing protocol loss over any payment rule that satisfies the equilibrium conditions. The left branch of the max is exactly the same as the proof of Lem. 3.1, where if the attacker plays honestly, the protocol incurs at least the cost of the honest equilibrium. The right branch of the max is similar to before, but now has a −B linear term, meaning that in the case that the attacker is playing the non-delivery strategy, the protocol can detect it (as before, this detection is used to ensure that there is no positive payment in this case). But further, this attack detection can be used to slash the full bond posted by the provers to mitigate the expected cost of an attack. Thus this is the best that the protocol could hope to do, and is still a lower bound on the optimal loss.

A.18

Lower bound g analysis with stake B

Corollary A.1 (Minimizer of gB occurs at equality). As in Lem. 3.2, the vector s∗ that minimizes gB occurs where the two branches of the max are equal. More formally, we have X i∈[n]

s∗i + C

Y

(1 − s∗i ) = C

n Y

(1 − s∗i ) − B.

i=a+1

i∈[n]

Proof. This proof follows the exact procedure as that of Lem. 3.2. We show that the optimizer can never be strictly in either branch. Recall that,   n X  Y Y gB (s) := max si + C (1 − si ), C (1 − si ) − B ,   i∈[n]

i=a+1

i∈[n]

and define L, R as the left and right branches of that max: X Y L(s) := si + C (1 − si ) i∈[n]

R(s) := C

i∈[n]

n Y

(1 − si ) − B.

i=a+1

41

Since only the right branch is a function of B, we only have to rule out the case that the optimizer is strictly in that branch. Assume, towards a contradiction, that s∗ (the minimizing s of g) is strictly in the right branch of the max L(s∗ ) < R(s∗ ). Notice that since B is just a constant shift, the partial derivative of the right branch is independent of it: n Y ∂R = −C · (1 − s∗j ) < 0. ∂s∗i j=a+1 j̸=i

Thus the same transformation used in the proof of Lem. 3.2 holds and the minimizer cannot be strictly in the right branch, regardless of the stake value B. Corollary A.2 (Characterizing the minimizer of gB ). As in Lem. 3.3, let s∗ denote the minimizing vector s∗ := arg mins∈[0,1] gB (s). Then s∗ is either a designated uniform committee equilibrium or a uniform committee equilibrium (Defs. 3.1 and 3.2). Proof. The stake value B only enters gB in the RHS of the equality constraint as a linear shift. Thus the feasible surface is distinct from g, but the transformations still hold. In particular, the equality constraint becomes Y  X sk + si + B + CπH (1 − si ) (1 − sk ) = 0, (13) i∈[n] i̸=k

i∈[a] i̸=k

which is still affine in sk . Thus the transformations continue to reduce the objective and we can restore the feasibility by move back to the constraint surface. Corollary A.3 (Limit behavior of Ct with B). As in Lem. 3.10, with n → ∞ the value of Ct at which the optimal symmetric equilibrium achieves a lower loss than the optimal designated equilibrium as a function of the honest proportion τ ∈ (0, 1) is: lim Ct (τ ) = ex , where 1 + x + B = e(1−τ )x .

n→∞

Proof. This proof mirrors the structure of that for Lem. 3.10. On the designated side, the discrete implicit equation becomes 1 + (n − 1)s = C(1 − s)h − B. The corresponding continuous version is 1 + (1 − τ + β)td = Ce−βtd − B. The resulting optimal designated loss is also minimized at β = τ , yielding the simplified Dτ = 1 + td = Ce−τ td − B Taking the continuous version of the symmetric constraint also with β = τ , we have Sτ =

ts + Be−(1−τ )ts . 1 − e−(1−τ )ts

42

(14)

Because Sτ = Dτ at the transition point Ct , we have 1+t=

t + Be−(1−τ )t =⇒ 1 + t + B = e(1−τ )t . 1 − e−(1−τ )t

Combining with (14), we get Ce−τ t = e(1−τ )t =⇒ C = et . This combined with 1 + t + B = e(1−τ )t is the limit of Ct given in the lemma statement.

Figure A.2: The value of limn→∞ Ct (τ ) (Cor. A.3) with various values of B (indicated by the colorbar) as a function of τ . Each point can be interpreted as, “Given τ, B, we plot the first value of C such that designated has a lower cost that symmetric and thus the optimal is implementable. Fig. A.2 shows the limit behavior of Ct with stake (Cor. A.3) for various values of τ, B. As with Fig. 3.2, the area under the curve represents the values of C such that the designated equilibrium is better than the symmetric on gB , and thus the lower bound on the optimal cost is tight and implementable with a designated payment rule.

43

A.19

Table for Exs. 3.7 and 3.8 n = 100, a = 33, C = 10,000

n = 200, a = 100, C = 20

B

B/C

Desig.

Symm.

% red.

B

B/C

Desig.

Symm.

% red.

0 10 50 100 500

0% 0.1% 0.5% 1% 5%

10.62 9.78 8.32 7.48 5.31

10.12 9.79 9.64 9.56 9.37

– 3.3% 17.8% 26.1% 47.5%

0 0.02 0.1 0.2 1

0% 0.1% 0.5% 1% 5%

4.12 4.11 4.09 4.06 3.81

3.99 3.99 3.99 3.98 3.97

– – – – 4.5%

Table A.1: Optimal designated and symmetric costs under varying stake levels. Left: high τ and C (n = 100, a = 33, C = 10,000) leading to a large 47.5% cost reduction from 5% stake to penalty ratio (Ex. 3.7). Right: lower τ and C (n = 200, a = 100, C = 20); even at B/C = 5%, the designated mechanism reduces loss by only 4.5% (Ex. 3.8). All % reductions are relative to the symmetric cost at B = 0.

A.20

Proof of Lem. 3.12

Lemma (Asymptotic loss with staking). The loss of the optimal designated equilibrium with staking amount B, scales as   log C − log(log C + B) O . τ Observe that this implies the following regimes =⇒ loss = O (log C/τ )

B = O(1)

B = Θ(C/polylog C) =⇒ loss = O (log log C/τ ) =⇒ loss = O (1/τ ) .

B = Θ(C)

Proof. As in the proof of Lem. 3.11, we start with the loss of the optimal designated equilibrium in the continuous setting but now with stake added: Dτ = 1 + td = Ce−τ td − B Rewriting with td = Dτ − 1, we get Dτ = Ce−τ (Dτ −1) − B =⇒ (Dτ + B)eτ Dτ = Ceτ . Multiplying through by τ eτ B gives an expression of the form yey = x, which is the definition of the Lambert W function: τ (Dτ + B)eτ (Dτ +B) = Cτ eτ (B+1) =⇒ τ (Dτ + B) = W (Cτ eτ (B+1) ) 1 =⇒ Dτ = W (Cτ eτ (B+1) ) − B. τ Using the first three terms of asymptotic expansion of the Lambert W function as W (x) = ln x − ln ln x + o(ln ln x), we have ln C ln(ln C + B) − + o(1) τ τ  log C − log(log C + B) =O , τ

Dτ =

which is the expression in the lemma statement. Now let’s consider each of the regimes. 44

• B = O(1): With a constant B, log(logτC+B) scales as log log C/τ , thus the full scaling is Dτ = O(log C/τ ). • B = Θ(C/polylog C): Evaluating the second expression with B = C/ logp C for some p ≥ 0, log(log C + B) = log(log C + C/ logp C) = log(C/ logp C) + O(1) = log C − p log log C + o(1). Thus the full scaling is Dτ = O(log log C/τ ). • B = Θ(C): Evaluating the second expression with B = γC for some γ ∈ (0, 1), we have log(log C + B) = log(log C + γC) = log C + O(1). Thus the full scaling is Dτ = O(1/τ ).

B

Section 4 appendices

B.1

Discussion of tightness regimes

Definition B.1 (Regimes of conjectured optimal). Given the conjectured minimizers Ŝk , D̂j (Def. 4.1) and the g minimizers Sk∗ , Dj∗ (Def. 3.5), four regimes are possible based on the shape of the equilibria and the tightness with the lower bound g. These regimes arise from the minimizer of g being designated as C → 1+ (Lem. 3.8) and symmetric as C → ∞ (Lem. 3.9). 1. Dj∗ = D̂j < Sk∗ : designated and tight. As long as the minimizers of g are designated, we know that the lower bound is implementable (Lem. 3.4). 2. Sk∗ < D̂j < Ŝk : designated and not tight. At C > Ct , the minimizer of g becomes symmetric. However, it is possible that the symmetric minimizer is not implementable (c.f., Ex. 3.4). In this regime, it is possible that D̂j < Ŝk , so the best implementable designated equilibrium is better than the best implementable symmetric equilibrium. 3. Sk∗ < Ŝk < D̂j : symmetric and not tight. Similarly, it is possible that Ŝk < D̂j and thus the best implementable symmetric equilibrium is better than the best designated. However, there is still no solution to (LS1) with all fi>h ≥ 0, thus the bound is not tight. 4. Sk∗ = Ŝk : symmetric and tight. Lastly, once C is sufficiently large (lower bounded by Lem. 3.6), (LS1) will be implementable with non-negative payments, and the lower bound will again be tight. The transition points between the different regimes do not admit a general closed form (Rem. 3.5) as they are the solutions to corresponding high-dimensional polynomial root finding problems. Fig. B.1 shows these pictorially as a function of C increasing. Fig. B.2 shows the numerical regimes in the discrete case for all values of h < n − 1 for n ∈ {3, 4, . . . , 7}. To further illustrate this point, consider the following example. 45

Figure B.1: The four regimes (Def. B.1) of the conjectured optimum shown pictorially. The designated and symmetric endpoints are colored the same as the lower bound to show that they are optimal.

Figure B.2: The numerical values of the four regimes (Def. B.1) for various values of {(n, h) : n ∈ {3, 4, . . . , 7}, h ∈ {1, 2, . . . , n − 2}} as a function of C. We use the same color palette as Fig. B.1.

46

Example B.1 (h = 3, n = 6 regimes). Let h = 3, n = 6 and consider the following regimes as a function of C: 1. C ∈ [1, 11.88] Phase 1: designated and tight. 2. C ∈ [11.88, 21.60] Phase 2: designated and not tight. 3. C ∈ [21.60, 31.14] Phase 3: symmetric and not tight. 4. C ∈ [31.13, ∞) Phase 4: symmetric and tight.

B.2

Counter examples for potential structure

This section examines many potential conjectures that would make the analysis of the lower bound function g (Lem. 3.1) and of the conjectured optimal mechanism (Conj. 4.1) more tractable. We show counter-examples to each conjecture, demonstrating the complexity of problem. Conjecture B.1 (false). The transition point Ct of g (Def. 3.6) always occurs with hj = hk . This conjecture would simplify the analysis of Dj∗ , Sk∗ because we would set the values of the respective committees as the same value. Example B.2 (Counter-example of Conj. B.1). Let h = 14, n = 19. Then Ct = 470.2382 and we transition from a designated equilibrium with k = 19, hk = 14 to a symmetric equilibrium with k = 12, hk = 7. Intuitively, what this counter-example shows is that we must consider all possible committee sizes for the candidate for the smallest value at which any symmetric equilibria achieves a lower cost than any designated equilibrium, because that is the point at which the lower bound ceases to be tight and achievable. Conjecture B.2 (false). The shape of the conjectured optimal mechanism (Conj. 4.1) has a single transition point as we increase h ↗ n − 1. Example B.3 (Counter-example to Conj. B.2). Consider n = 7, C = 15. Then the following are the solution to the conjectured optimal (Conj. 4.1) as a function of h. • h = 1 =⇒ s∗ = (0.682, 0.682, 0.682, 0.682, 0.682, 0.682, 0.682) (symmetric full). • h = 3 =⇒ s∗ = (1, 0.393, 0.393, 0.393, 0.393, 0.393, 0.393) (designated full). • h = 5 =⇒ s∗ = (0.829, 0.829, 0.829, 0, 0, 0, 0) (symmetric committee k = 3). • h = 6 =⇒ s∗ = (1, 0.875, 0, 0, 0, 0, 0) (designated committee k = 1). Intuitively, this counter-example shows that the phase transitions of the shape are not monotone in h. In the geometric interpretation (c.f., Fig. 3.1), this means that the optimizer is bouncing between multiple edges of the polytope as we increase the value of h. Conjecture B.3 (false). The shape of the conjectured optimal mechanism (Conj. 4.1) has a single transition point if we hold h and increase n. 47

Example B.4 (Counter-example to Conj. B.3). Consider h = 3, C = 15. Then the following are the solution to the conjectured optimal (Conj. 4.1) as a function of n. • n = 4 =⇒ s∗ = (1, 0.875, 0, 0) (designated committee k = 1). • n = 5 =⇒ s∗ = (0.829, 0.829, 0.829, 0, 0) (symmetric committee k = 3). • n = 6 =⇒ s∗ = (1, 0.411, 0.411, 0.411, 0.411, 0.411, 0.411) (designated committee k = 5). • h = 15 =⇒ s∗ = (0.311, . . . , 0.311) (symmetric committee k = 15). This counter example extends Conj. B.2 to consider holding h fixed and considering the geometry of the conjectured optimal as we increase n. Just as in the previous counter-example, we see that the minimizer transitions from designated to symmetric edges of the polytope in a non-monotone way. Conjecture B.4 (false). The solution to the optimal implementable symmetric equilibrium (LP1) results in a predictable set of constraints being tight and fi values being set to 0 (e.g., their is a threshold i past which all of the (attacker delivers i) constraints are tight). Example B.5 (Counter-example to Conj. B.4). Consider n = 16, h = 8. With C = 3000, we have, f1 , f2 , f3 , f4 , f5 , f8 , f9 , f12 , f15 , f16 = 0 f6 , f7 , f10 , f11 , f13 , f14 > 0. Further, the tight constraints (attacker delivers i) are i = 0, 3, 4, 5, 6, 8 and the slack constraints are i = 1, 2, 7. Reducing to h = 7, we have a fully different shape for the zero values of fi (differences are highlighted in red): f1 , f2 , f3 , f4 , f5 , f8 , f11 , f14 , f15 = 0 f6 , f7 , f9 , f10 , f12 , f13 , f16 > 0, and different slack constraints: i = 1, 2, 5. Intuitively, this example shows that there isn’t a simple story about the set of tight constraints or the values of fi that the optimal symmetric equilibrium will set in the solution to the LP. Conjecture B.5 (false). The transition from symmetric to designated of the conjectured optimal Conj. 4.1 always occurs with hj = hk (similar to Conj. B.1). Example B.6 (Counter-example to Conj. B.5). Consider n = 7, h = 4. The transition value C for which D̂j > Ŝk occurs at C ≈ 26.093, and we transition from a designated equilibrium with hj = 4, s = 0.399 to a symmetric equilibrium with hk = 2, s = 0.653. Just as in Conj. B.1, we see that the size of the subcommittee is a key determinant in the optimal conjectured transition point. These two claims together imply that there is no simple way to determine any of the transition points of the conjectured minimizer as described in Fig. B.1. 48