(Im)possibility of Incentive Design for Challenge-based Blockchain Protocols
Suhyeon Lee, Dieu-Huyen Nguyen, Donghwan Lee · 2025
Read (Im)possibility of Incentive Design for Challenge-based Blockchain Protocols by Suhyeon Lee, Dieu-Huyen Nguyen, Donghwan Lee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20864.txt.
Introduction
Suhyeon Lee, Dieu-Huyen Nguyen, and Donghwan Lee ask whether blockchain challenge systems actually pay people to police fraud. Systems like optimistic rollups compute off-chain and call the chain only when someone challenges a result. That design assumes at least one honest challenger will bother, an assumption about incentives rather than code.
The authors model a colluding minority, varied participant costs, and three ordering modes. Two goals must hold together: honest challengers should never lose money, and fraud should be deterred. In single-winner designs, they prove both goals cannot reliably be met at scale. In multi-winner designs, simple explicit conditions achieve both, giving protocol designers a clear fork in the road.
Catalog record
| CREATOR | Suhyeon Lee, Dieu-Huyen Nguyen, Donghwan Lee |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-20864
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
(Im)possibility of Incentive Design for Challenge-based Blockchain Protocols Suhyeon Lee, Dieu-Huyen Nguyen, Donghwan Lee Abstract Blockchains offer a decentralized and secure execution environment strong enough to host cryptocurrencies, but the state-replication model makes on-chain computation expensive. To avoid heavy on-chain workloads, systems like Truebit and optimistic rollups use challenge-based protocols, performing computations off-chain and invoking the chain only when challenged. This keeps normal-case costs low and, if at least one honest challenger exists, can catch fraud. What has been less clear is whether honest challengers are actually incentivized and a dishonest proposer is properly damaged under the worst case environment. We build a model with a colluding minority, heterogeneous costs, and three ordering modes. We then ask whether two goals can be met together: honest non-loss and fraud deterrence. Our results are clear: in single-winner designs, the incentive design is impossible or limited in scale. By contrast, in multi-winner designs, we obtain simple, explicit conditions under which both goals hold. 1 Introduction Blockchains offer a decentralized, verifiable execution environment. Because many nodes must replicate state, on-chain computation is costly. To scale, systems shift intensive work off-chain and verify correctness only when disputes arise through challenge protocols, including Truebit-style verification, fraud proofs in optimistic rollups, and data-availability audits. These mechanisms keep the common case cheap while retaining a safety valve: if at least one honest party challenges, fraud can be surfaced and a slashed deposit funds the payout. It seems very easy to satisfy. However, this impression is not enough to construct a blockchain protocol for users considering its nature. For example, if a dishonest proposer is disputed by a challenger account which is actually the proposer’s Sybil account, the dishonest proposer will be able to avoid any loss. In this paper, we raise two questions. First, are honest challengers are incentivized in the blockchain environments? The first question is to guarantee at least one honest validator exists. Second, do dishonest proposers who post wrong values get proper economic damage that the system intends? The second question is to guarantee dishonest proposers do not appear. To answer the question, we develop a mechanism-agnostic model that captures different ordering properties and asks whether two goals can be met together: honest non-loss for included challengers and explicit deterrence against the proposer. The model features multiple challengers (validators) with heterogeneous but bounded costs, a proposer deposit and reward share, and a colluding subset of size A<N/2 . Ordering is treated in three modes that differ in who captures priority value: fair ordering (random within short arrival intervals), unfair-by-builder, and unfair-by-proposer. We analyze single-winner and multi-winner with unbounded inclusion. Our contributions are as follows: • Problem formalization. Prior work mainly posed the challenge via examples; we provide a clean formal model that makes the incentive question analyzable. • Single-winner limits. We show that, under realistic ordering assumptions, single-winner challenge designs are either impossible to incentivize or tightly constrained. • Multi-winner feasibility. We model multi-winner designs and prove that, unlike single-winner schemes, these systems generally make it easier to design fair and effective incentives. The rest of the paper is organized as follows. Section 2 briefly reviews related work. Section 3 formalizes the model and design goals. Section 4 presents single-winner limits under proposer- and builder-ordered priority and the scalability bound under fair ordering. Section 5 establishes feasibility for multi-winner and shows scalability-free calibration. Section 6 discusses the design trade-offs and implications. Section 7 concludes with implications and implementation guidance. 2 Related Work Prior work develops concrete dispute protocols and fraud-proof algorithms for rollups, including BoLD and Dave [ 1 , 10 ] . These protocols, however, enforce single-winner designs through duplicate prevention mechanisms at the protocol level. Separate strands analyze validator behavior, covering incentive alignment [ 8 ] and diligence under economic frictions [ 12 ] , and study censorship risks in fraud-proof timelines [ 2 ] . Announcement-game dynamics [ 7 ] and risks around sequencer centralization and censorship [ 9 ] are documented alongside broader rollup attack surfaces [ 4 ] and accountable designs [ 13 ] . Within this space, Lee [ 5 ] explicitly articulates a vulnerability of fraud-proof incentive systems in optimistic-rollup dispute games and sketches countermeasures, but does not provide a general feasibility criterion or proofs that rule out the failure modes. Our work provides that missing layer via a compact formal model that separates ordered priority and single- versus multi-winner settings, proving single-winner limits and a feasibility boundary for multi-winner inclusion. 3 Model and Design Goals In this section, we formalize a minimal model for challenge-based rewards: players, costs with an upper bound, deposits, ordering modes, and winner multiplicity. We state two design goals used in the following sections. 3.1 Players, costs, and deposits The game is modeled in normal form under complete information, such that the entire payoff structure is common knowledge among all players, who then choose their strategies simultaneously. We consider N challengers to a specific proposal and assume a conservative Sybil and collusion bound where only a subset of challengers with A=|\mathcal{A}|<N/2 may collude with the proposer P . Pooling mechanisms such as BoLD’s AssertionStakingPool count as one challenger, since the protocol registers only the pool address as a single economic entity [ 11 ] . Each challenger stakes the same deposit s , and to submit a successful valid challenge they incur a cost c_{i}>0 . The cost c_{i} comprises of the initial cost to identify fraud and the cost to process the challenge till the end (e.g. executing the smart contract to prove).Costs may vary across agents and across challenge processes, but admit known finite upper bounds. Let c_{i}\;=\;c_{i}^{\textsf{init}}+c_{i}^{\textsf{proc}},\qquad\tilde{c}^{\textsf{init}}\;\geq\;\sup_{i}c_{i}^{\textsf{init}},\qquad\tilde{c}^{\textsf{proc}}\;\geq\;\sup_{i}c_{i}^{\textsf{proc}}. Define the aggregate worst-case cost bound as \tilde{c}\;:=\;\tilde{c}^{\textsf{init}}+\tilde{c}^{\textsf{proc}}, so that c_{i}\leq\tilde{c} for all i . The bound \tilde{c} serves as a worst-case guarantee for verifying individual rationality (IR). 3.2 Reward pool, winners, and splits Slashing. Upon acceptance of a valid fraud proof, the proposer’s deposit D_{p} is slashed. A fraction \alpha D_{p} is paid to challengers designated as winners and the remainder (1-\alpha)D_{p} is burned, with \alpha\in(0,1] . Even though burning a part of the slashed deposit in challenge-based protocols is not generally adopted, we introduce this rule to force a minimal economic damage under a possibility of collusion. Winner set. The system has the number of winners m . The single-winner setting m=1 is a special case which does not allow multiple winners. In the multi-winner setting, the protocol imposes no ex-ante numeric cap on winners. However, runtime constraints (for example, dispute-window length and blockchain throughput) imply that the realized number of winners m is finite and ex-post bounded. Split rule. We adopt equal split among winners: each of the m included winners receives \alpha D_{p}/m . That is, with fewer winners, each winner receives a larger share. Lastly, we add an assumption to consider the worst reward of the honest challengers and an observation follows. Assumption 1 (Best-effort participation) Validators try to submit a valid challenge during the dispute period whenever a public conservative bound on net payoff is non-negative using an exogenous upper bound on fees and the announced inclusion capacity. The realized winners do not exceed capacity or the number of valid challengers, and in the worst case the