PaperlayerView exact revision on arXiv

Source-linked AI summary

STAKE: Preventing a colluding majority from double spending

Zahra Naderi, Vincent Gramoli

arXiv:2610.01169v2cs.GT

TL;DR

Open-network delays challenge blockchain security, and traditional protocols require a supermajority of honest participants. STAKE combines incentives and stake with repeated consensus to reach robust equilibrium with fewer honest players, while successful ζ-uple attacks become exponentially less likely.

  • Problem

    Unexpected message delays can expose blockchains to double spending, while partial-synchrony protocols require more than two-thirds of participants to be honest.

    Source: §1 · pp. 1–2

  • Method

    STAKE models consensus as an imperfect-information game and uses betrayal incentives, proof-of-fraud evidence, and a commit-reveal phase to expose attacks and distribute rewards.

    Source: §4 · p. 9, §5 · p. 10

  • Results

    STAKE is reported to reach (k,t)-robust equilibrium with t < n/3 Byzantine players and k = n/3 rational players, while ζ-uple attack probability drops exponentially with ζ.

    Source: §1 · p. 2, §8 · p. 16

  • Takeaways & Limitations

    Because successful ζ-uple attacks are difficult, the stake-to-liquidity ratio need not be high to secure a blockchain.

    Source: §8 · p. 16

    The model bounds Byzantine players by ⌈n/3⌉−1 and assumes that after GST the adversary cannot extend scheduling control and players proceed in locksteps.

    Source: §2 · p. 3

Abstract

from arXiv · show

Blockchains typically operate in open networks where it is hard to control the delay of messages. While classic blockchain protocols assumed synchrony, newer protocols try to remain secure despite unexpected network delays. Unfortunately, in the traditional model where $n$ participants can either be honest or Byzantine, we need a supermajority, or $\lfloor 2n/3\rfloor + 1$, of them to be honest. Recent work have explored the question of reducing the number of needed honest nodes in a game theory model to a majority sometimes by introducing $k$ rational players and $t$ Byzantine players. Yet, to our knowledge, no blockchain protocol managed to reduce it further. In this paper, we offer a blockchain protocol called Secure and Tolerant Algorithm through ($k,t$)-robust Equilibrium (STAKE) that works with only $\lfloor n/3\rfloor + 1$ honest players. STAKE requires each consensus participant to stake a sufficiently large amount $s$ compared to their liquidity $\ell$. We show that the probability that a coalition manages to execute $\zeta$ double spending attacks (we call them a $\zeta$-uple attack) drops exponentially fast with $\zeta$. This allows us to demonstrate that STAKE reaches a ($k,t$)-robust equilibrium, or that rational players do not collude with Byzantine, even with a relatively low $s/\ell$ ratio.

1 Introduction

Open networks make message delays difficult to control, while classic synchrony assumptions leave blockchains vulnerable to delay-related double spending. STAKE uses incentives and stake to pursue robust equilibrium with fewer honest participants, while repeated ζ-uple attacks become exponentially less likely.

1 Introduction

  • Classic protocols assume synchrony, so unexpected network delays can expose them to double spending.The introduction cites prior delay-related incidents.Source: §1 · p. 1
  • Partial-synchrony approaches prevent forks through consensus on a unique block, but require more than two-thirds of participants to be honest.The authors describe this honesty requirement as unrealistic in settings where misbehavior can steal substantial cryptocurrency.Source: §1 · pp. 1–2
  • Prior incentive-based approaches either retain the more-than-two-thirds honesty requirement or address only one-shot consensus, not repeated games with strategy adaptation.The paper frames its approach as addressing the repeated-game challenge, where players use observations from earlier instances.Source: §1 · pp. 2–3
  • With only ⌊n/3⌋+1 honest players, STAKE is presented as a blockchain protocol that works in partial synchrony and requires participants to stake a sufficiently large amount relative to liquidity.The stake requirement is described as applicable to regulated public blockchains with non-discretionary account rules.Source: §1 · p. 2
  • The probability of a coalition executing ζ double-spending attacks falls exponentially with ζ, as multiplying partitions makes it harder to isolate honest players.The paper says this attack difficulty supports equilibrium even with a relatively low stake-to-liquidity ratio.Source: §1 · p. 2

2 Model

The model treats consensus as a repeated game under partial synchrony, with honest, rational, and Byzantine players. Its adversary controls scheduling before GST, while assumptions on types, information, and cryptography delimit the setting.

2 Model

  • The model includes at most t0 = ⌈n/3⌉−1 Byzantine players, rational players seeking to maximize expected utility, and honest players who follow the protocol.The authors state that the Byzantine bound is needed for consensus and that a larger Byzantine set could replace the consensus algorithm as shadow authorities.Source: §2 · p. 3
  • Before GST, an adversary controls message scheduling and delivery timing; after GST, players proceed in locksteps and the adversary cannot extend its scheduling influence.The scheduler controls message order and delivery times before GST.Source: §2 · pp. 3–4
  • Players have imperfect information but perfect recall, and their strategies map their type, past actions, and received messages to actions.The game includes attack, bribe, betrayal, and commit choices.Source: §2 · p. 4
  • The model assumes unforgeable signatures, oblivious transfer, a public-key infrastructure, and transferable authentication so players can verify moves and identify message generators.The adversary is slowly adaptive, changing attackers and strategies only between local rounds.Source: §2 · p. 4
  • Players divide assets into stake s and transferable liquidity ℓ; a successful ζ-uple attack can multiply liquidity by ζ.The model holds the stake-to-liquidity ratio constant and omits transaction fees.Source: §2 · p. 5

3 The Problem of Coping with ζ-uple Spending Attacks

The problem is to secure repeated consensus against ζ-uple spending while minimizing the required stake. The proposed incentive hinges on rational players betraying attackers, with a theorem specifying when their messages reach all honest players.

3 The Problem of Coping with ζ-uple Spending Attacks

  • The protocol aims for an ϵ-(k,t)-robust equilibrium despite attackers, using a minimal stake requirement among n selected consensus participants.The stated problem includes t Byzantine players, of whom f may be detectable attackers, and k rational players.Source: §3 · p. 5
  • A ζ-uple spending attack creates ζ branches and can yield attackers up to ζ−1 times their liquidity.The network is modeled as a disk with uniformly distributed honest players; each additional branch requires another successful isolation attack across a radius.Source: §3 · pp. 5–6, Figure 1 · p. 6
  • Theorem 1 states that if the specified number of rational players sends m′, all honest players receive m′.The theorem identifies a minimum number of rational betrayers needed to inform the honest players of an attack.Source: §3 · p. 6
  • The paper distinguishes this coalition guarantee from Nash equilibrium, which only prevents a single rational player from benefiting by deviating alone.The desired incentives make behaving preferable to attacking and betrayal preferable to joining an attack coalition.Source: §3 · p. 6
  • Robust equilibrium rules out gains above negligible ϵ from rational players joining attackers, including when they coordinate with Byzantine players.The definition also includes t-immunity, under which Byzantine players cannot reduce others’ payoffs.Source: §3 · pp. 6–7

4 Stake: A Solution to the ζ-uple Spending Attack

STAKE combines consensus, attack evidence, and incentives to expose ζ-uple attacks before final decisions. It identifies attackers and betrayers, slashes attacker stake, and rewards valid betrayers.

4 Stake: A Solution to the ζ-uple Spending Attack

  • STAKE gives rational coalition members a choice between keeping attack profits and betraying to earn an incentive and alert honest players.The betrayal path is intended to let honest players stop an attack before it succeeds.Source: §4 · p. 7
  • The pre-decision phase runs Byzantine fault-tolerant consensus; the commit-reveal phase resends encrypted pre-decided blocks or proof-of-fraud lists before the final decision.Encryption prevents others from identifying betrayers or detecting betrayal before the specified sub-phase.Source: §4 · pp. 7, 9
  • Transferable authentication lets betrayers gather contradictory signed messages as proofs of fraud, which can identify guilty players.The underlying consensus must provide safety with fewer than one-third attackers, liveness with fewer than two-thirds, and transferable authentication.Source: §4 · p. 9
  • The protocol slashes attackers’ stake and distributes rewards equally among valid betrayers, while temporarily excluding betrayers from consensus.Rewards are divided equally because partial synchrony does not guarantee message ordering, so players cannot reliably determine who submitted first.Source: §4 · p. 9
  • STAKE solves Fully Accountable Agreement at each new blockchain index, ensuring detection, convergence, agreement, validity, and termination.The agreement properties are stated for honest players’ outputs and decision block.Source: §4 · p. 10

5 Tolerating ζ-uple spending attacks

Stake uses incentives and repeated-game reasoning to deter rational players from joining double-spending coalitions. Its security analysis bounds the success of multi-branch attacks and establishes equilibrium guarantees both with and without bribery.

5 Tolerating ζ-uple spending attacks

  • In the repeated game, betrayal is a dominant, self-enforcing strategy, while slashed stake and rewards return to betrayers as liquidity after removing them from consensus.When Byzantine players are inactive, pre-decision Byzantine fault-tolerant consensus properties help ensure rational players adhere to the protocol.Source: §5 · pp. 10–11

5.1 Why a successful ζ-uple spending attack, with ζ > 2, is rare

  • For ζ ≥3, the probability of a successful ζ-uple attack is bounded by ε = (e/λ)3 under independent isolation attacks.The analysis conservatively allows up to m ≥3 independent isolation attempts for attacks creating more than two branches.Source: §5.1 · p. 11

5.2 Attacks without bribery

  • Without bribery, rational players join an attack only for their personal gain stolen during it.The section frames the no-bribery case as one where Stake is immune to ζ-uple spending attacks.Source: §5.2 · pp. 11–12

5.2 Attacks without bribery; 5.3 Attacks despite bribery

  • Stake is an ϵ-(k, t)-robust equilibrium against ζ-uple spending attacks both without bribery and, under stated constraints, when Byzantine players can bribe rational players.The bribery scenario can be implemented through a smart contract that redistributes attack gains exclusively to rational players.Source: §5.2 · p. 12, §5.3 · p. 12

6 Analysis

The analysis relates required stake to liquidity, attacker configuration, and isolation-attack probability. The required ratio can remain low, while bribery narrows workable configurations and increases the stake needed in some cases.

6.1 The Impact of bribery on the required stake

  • When Byzantine players can bribe rational players, workable configurations are more limited, although the required s/ℓ ratio is not high and the overall trend changes insignificantly.The comparison states that bribery requires a slightly higher staking-over-liquidity ratio.Source: §6.1 · pp. 12–13, Figure 3 · p. 13

6.2 How much stake to secure the Stake protocol

  • At p = 10−3, the required stake is s = 5ℓ· 10−7; at p = 0.1, it is at most ℓ· 10−2, depending on the number of Byzantine players.The paper gives examples of US$500 stake for US$1B transfers at p = 10−3 and US$10 for US$1K transfers at p = 0.1.Source: §6.2 · p. 14

6.3 Comparison between bribery and without bribery

  • As the Byzantine share increases, Byzantine players gain greater power to induce rational players to join the coalition, explaining differences between the bribery and no-bribery results.The table analysis considers detected Byzantine players f, honest players h, rational players k, and isolation-attack success probability p.Source: Table 1 · p. 13, §6.3 · p. 14

7 Related Work

Prior work studies equilibrium concepts, incentives, and fault assumptions for consensus and blockchains. The paper distinguishes Stake by its lower honest-player threshold and its focus on preventing double spending under partial synchrony.

Related work

  • Stake reaches the ⌊n/3⌋+ 1 honest-player threshold, whereas Trap reaches ⌊n/2⌋+ 1 but does not address repeated consensus games.Trap's internal commit-reveal consensus protocol uses a baiting strategy to trade honest players for rational players.Source: §7 · p. 14
  • Other equilibrium approaches have different scope constraints: Perfect Bayesian Equilibria address invalid-block proposals, while CPNE requires all players to be rational.SNE cannot apply to consensus because a sufficiently large coalition can prevent consensus; SPPNE also assumes all players are rational.Source: §7 · pp. 14–15
  • Ouroboros and Fruitchain mitigate selfish mining but require a majority of honest stake or players for their stated coalition-gain bounds.Ouroboros uses a δ-Nash equilibrium; Fruitchain uses an n/2-coalition-safe 3δ-Nash equilibrium.Source: §7 · p. 15
  • Solidus reaches (k, t)-robust equilibrium using incentives but requires k + t < n/3, while Stake works for k + t < 2n/3.ZLB reimburses victims to resolve forks; Stake instead protects against double-spending attacks.Source: §7 · p. 15
  • CoBRA reaches the same threshold by assuming synchrony, whereas Stake requires participants to stake a portion of liquidity to withstand unexpected delays.The cited impossibility result [7] rules out (k, t)-robust equilibrium for state machine replication in the general model.Source: §7 · p. 15

8 Discussion and Conclusion

Stake uses rewards and punishments to incentivize rational players, and its extensive game models their choices under imperfect information. The discussion links the incentive scheme to the number of rational and Byzantine players.

8 Discussion and Conclusion

  • More rational players increase the total betrayal reward, requiring more Byzantine stake to cover it.The paper also states that a relatively low stake-to-liquidity ratio can suffice because successful ζ-uple attacks are difficult.Source: §8 · pp. 15–16
  • Stake aims to secure against double spending with only ⌊n/3⌋+1 honest players.It defines rewards and punishments to incentivize rational players to behave or betray Byzantine players.Source: §8 · pp. 15–16

A Formal Definition of the Extensive Game

  • For two rational players, the extensive-form game represents Byzantine players initiating attacks and rational players choosing actions under endogenous uncertainty.Honest players are omitted from the game tree because they always follow the protocol; their number instead affects rational players’ utility.Source: A Formal Definition of the Extensive… · p. 19, Figure 4 · p. 19

B Pseudocode for the Stake protocol

Stake repeats a single-shot consensus protocol and uses accountable agreement, commit-reveal, and proofs of fraud to resolve blocks and punish attackers. Valid proof-of-fraud evidence also funds rewards for betrayers.

B Pseudocode for the Stake protocol

  • The pseudocode defines a proof of fraud, pof, as a structure containing evidence, attackers, a betrayer, and block index r; attackers are a subset of Attacker, and the betrayer belongs to Betrayer.Source: B Pseudocode for the Stake protocol · p. 20
  • Accountable Byzantine agreement returns a unique pre-decision block or proofs of fraud, after which commit-reveal hides the decision until reveal.The protocol resolves forks involving conflicting blocks or returns the unique pre-decided block.Source: B Pseudocode for the Stake protocol · p. 21
  • Valid proofs of fraud slash attackers’ stake, which the protocol allocates to betrayers who reveal the proofs.The pseudocode records slash amounts in a global wallet before and after allocating them to betrayers.Source: B Pseudocode for the Stake protocol · pp. 20–21

C Proof of Theorem 1

The proof analyzes when betrayal messages reach honest players during a ζ-uple attack. It uses a pigeonhole argument to establish that a randomly selected set of rational players sending m′ reaches all honest players.

C Proof of Theorem 1

  • In a successful ζ-uple spending attack, attackers should create ζ disjoint groups of honest players to create ζ branches and spend their money ζ times; each branch should have more than 2n.Source: C Proof of Theorem 1 · p. 22
  • If ⌊(k+t)/6⌋+1 randomly selected rational players send m′ during the attack, all honest players receive m′.The proof uses a partition of the attackers and the pigeonhole principle to derive the number of betrayers needed to notify all honest players before termination.Source: C Proof of Theorem 1 · pp. 22–23

D Proof of Theorem 2

The proof establishes eventual identification of attackers and agreement among honest players on valid betrayers and attackers. It then uses these properties, termination, agreement, and validity to show fully accountable agreement.

D Proof of Theorem 2

  • The passage says their proofs may not be seen by enough honest players at the right time, describing a possibility rather than a certainty.Source: D Proof of Theorem 2 · p. 24
  • All honest players eventually agree on the same list of valid betrayers and attackers.The proof explains that valid proofs are broadcast and that eligible double-signed proofs establish the common list of betrayers.Source: D Proof of Theorem 2 · pp. 24–26
  • Rational players gather and broadcast additional proofs over time, allowing honest players eventually to identify all attackers.The additional proofs increase betrayers’ rewards because attacker punishment funds those rewards.Source: D Proof of Theorem 2 · p. 25
  • Stake solves Fully Accountable Agreement for each new blockchain index.The proof derives detection and convergence from Lemma 4, termination from Lemma 5, and agreement and validity from the protocol’s block selection.Source: D Proof of Theorem 2 · p. 26

E Proof of Lemma 1

The proof bounds the chance of a ζ-uple spending attack by modeling isolation attempts as independent trials and applying a Chernoff bound. Because the number of attempts is bounded, attackers cannot repeat isolation attacks indefinitely.

E Proof of Lemma 1

  • The probability of a successful ζ-uple spending attack, for ζ ≥ 3, is at most ε = (e/λ)^3.The bound assumes up to m independent isolation attacks, each succeeding with probability p.Source: E Proof of Lemma 1 · p. 26
  • Creating a ζ-uple spending attack requires ζ successful isolation attacks, each delaying messages across a radius of the modeled disk network.The proof models honest players as uniformly distributed in a disk.Source: E Proof of Lemma 1 · p. 27
  • The proof treats the number of successful isolation attempts as a sum of m independent Bernoulli trials, each with success probability p.Its expected number of successes is μ = m · p.Source: E Proof of Lemma 1 · p. 27
  • A Chernoff bound is used to bound the probability of obtaining at least ζ successful attacks.The derivation invokes the bound for all δ > 0 and then uses the bounded number of attacker attempts.Source: E Proof of Lemma 1 · p. 27

F Proofs of Theorems 3–4

The proofs establish incentive conditions for STAKE by comparing the rewards and costs of betrayal and cheating. Under the stated stake conditions, the protocol is an ε-(k, t)-robust equilibrium against ζ-uple spending attacks and bribery.

Proofs of Theorems 3–4

  • The equilibrium proof assumes at least one Byzantine attacker so that betrayers can be rewarded with an attacker’s stake.The authors state that this assumption simplifies the proof.Source: F Proofs of Theorems 3–4 · p. 27
  • A betrayer’s reward is at least f·s/k, where f is the number of detected Byzantine attackers.The minimum reward occurs when all k rational players betray and divide the stake of the f attackers.Source: F Proofs of Theorems 3–4 · pp. 27–28
  • The cost of betraying is zero because a rational player’s slashed stake is returned as liquidity after revealing fraud proofs.The supplied proof attributes this to the protocol’s handling of the player’s conflicting messages and fraud proofs.Source: F Proofs of Theorems 3–4 · p. 28
  • The cost of cheating is s when a cheating player is caught and does not unlock their stake.This is the amount of stake slashed that decreases the player’s utility.Source: F Proofs of Theorems 3–4 · p. 28
  • For ζ-uple attacks, the cheating benefit is bounded by ℓ·p2 + O(1/λ3), with the supplied theorem proof relating this bound to the stake-over-liquidity requirement.The argument compares the benefit of cheating with the benefits and costs of betrayal and cheating; the displayed condition is incomplete in the supplied passages.Source: F Proofs of Theorems 3–4 · p. 29
  • Under the specified condition, STAKE remains secure as an ε-(k, t)-robust equilibrium against ζ-uple spending attacks.The theorem’s stake-condition expression is fragmented in the supplied passage.Source: F Proofs of Theorems 3–4 · pp. 27, 29
Loading 2610.01169v2…