# STAKE: Preventing a colluding majority from double spending

Crypto.world

> Classic blockchain consensus needs more than two thirds of participants to be honest (⌊2n/3⌋+1), an assumption the authors argue is unrealistic when misbehaviour can steal large amounts of…

**arXiv**: 2610.01169

**Published**: 2026-10-01

**Authors**: Zahra Naderi, Vincent Gramoli

## AI summary

STAKE: Preventing a Colluding Majority from Double Spending — Summary

## Overview

**Research area:** Distributed systems and blockchain consensus, specifically the intersection of Byzantine fault tolerance with algorithmic game theory (the paper is filed under Computer Science and Game Theory, arXiv:2610.01169v1, dated 1 October 2026).

**Technical level:** Advanced. The paper assumes familiarity with partial synchrony, Byzantine fault tolerance thresholds, extensive-form games, Nash equilibrium variants, and cryptographic assumptions such as oblivious transfer. The prose is readable, but the results are formal theorems with proofs deferred to appendices.

**Scope (one sentence):** The paper designs and analyses STAKE (Secure and Tolerant Algorithm through (K,t)-robust Equilibrium), a blockchain protocol that reduces the required fraction of honest consensus participants to ⌊n/3⌋+1 by staking and by making betrayal of an attacking coalition the rational choice, and proves it attains an ε-(k,t)-robust equilibrium in partial synchrony.

## What This Paper Is About

Classic blockchain consensus needs more than two thirds of participants to be honest (⌊2n/3⌋+1), an assumption the authors argue is unrealistic when misbehaviour can steal large amounts of cryptocurrency. Earlier game-theoretic work lowered the bar to a simple majority (Trap, ⌊n/2⌋+1) but only for one-shot consensus, not for a repeated blockchain setting where players adapt across blocks. STAKE's goal is to go further, to ⌊n/3⌋+1 honest players, by requiring each consensus participant to stake a sufficiently large amount s relative to its liquidity ℓ and by making it profitable for rational players to betray an attacking coalition rather than join it.

## Key Contributions

1. **A protocol reaching the ⌊n/3⌋+1 honest-player threshold.** The authors present STAKE as the first blockchain protocol working with only ⌊n/3⌋+1 honest players, in a partial synchrony model where this was originally believed impossible (the paper positions its result against the CoBRA impossibility line of work, which bypasses the impossibility by assuming synchrony).
2. **The ζ-uple spending attack abstraction.** The paper generalises double spending to a ζ-uple spending attack (ζ ≥ 2), where attackers create ζ branches to gain up to ζ−1 times their liquidity, and models success as ζ isolation attacks on a disk-shaped network with honest players uniformly distributed.
3. **A two-phase accountable protocol design.** STAKE combines a pre-decision phase (any BFT consensus with safety below 1/3 attackers, liveness below 2/3 attackers, and transferable authentication, e.g., Polygraph, ABC, or ABC++) with a commit-reveal phase, producing undeniable proofs-of-fraud (PoFs), slashing attackers' stake, and rewarding betrayers. Theorem 4.1 states that STAKE solves the newly defined Fully Accountable Agreement problem at each new chain index, satisfying Detection, Convergence, Agreement, Validity, and Termination.
4. **Equilibrium proofs with and without bribery, plus concrete stake guidance.** Theorems 5.1 and 5.2 give stake-to-liquidity conditions under which STAKE is an ε-(k,t)-robust equilibrium, and Table 1 translates these into minimum s/ℓ values (as low as 5·10⁻⁷ without bribery at p = 0.001, and 10⁻⁶ with bribery at p = 0.001).

## Main Findings

- **Honest threshold of ⌊n/3⌋+1:** STAKE requires only ⌊n/3⌋+1 honest players, compared with ⌊2n/3⌋+1 in the traditional Byzantine model. The paper contrasts this with Solidus, which needs k + t < n/3 while STAKE works as long as k + t < 2n/3, and with Trap, which needs ⌊n/2⌋+1.
- **ζ-uple attack probability drops polynomially fast in ζ:** The probability that a coalition executes ζ double spending attacks falls polynomially with the number ζ of carefully selected partitions, a consequence of the growing difficulty of partitioning honest players from one another as partitions multiply.
- **Betrayal threshold (Theorem 3.1):** If t + k attackers attempt a ζ-uple spending attack and ⌊(k+t)/2 − n/6⌋+1 rational players, randomly selected from the k rational players, send message m′, then all honest players receive m′. This count also defines a "betraying coalition" (Definition 3) and sets t₀ + 1 re-signed PoFs as the PoF-ledger a betrayer must collect.
- **Isolation attack success is bounded (Proposition 1):** The number of isolation attack attempts m multiplied by the success probability p satisfies m·p < 3/e = 1.1. Attackers are conservatively granted m ≥ 3 independent isolation attempts for more than two branches.
- **Attack probability bound (Lemma 1):** With up to m independent isolation attacks each succeeding with probability p, the probability of a successful ζ-uple attack with ζ ≥ 3 is upper bounded by ε = (e/λ)³, derived via Chernoff bounds.
- **No-bribery equilibrium (Theorem 5.1):** If s/ℓ > k·p²/(f+k), the STAKE protocol is an ε-(k,t)-robust equilibrium against ζ-uple spending attacks, where f ≤ t is the number of detectable attackers.
- **Bribery-resistant equilibrium (Theorem 5.2):** If s/ℓ > p², the STAKE protocol is an ε-(k,t)-robust equilibrium that protects against ζ-uple spending attacks and bribery.
- **Stake requirements are modest in practice:** At isolation-attack success probability p = 10⁻³ without bribery, a minimum s/ℓ of 5·10⁻⁷ suffices, which the paper equates to staking only US$500 to transfer US$1B per transaction. At p = 0.1, at most ℓ·10⁻² is needed depending on the Byzantine count — for example, staking US$10 to transfer US$1K per transaction, regardless of bribery.
- **Table 1 numerical trends (n = 10⁶ in Figure 3):** Without bribery, minimum s/ℓ is 5·10⁻⁷ at p = 0.001, 5·10⁻⁵ at p = 0.01, and 5·10⁻³ at p = 0.1 (with f = ⌈n/3⌉−1 and h = ⌊n/3⌋+1); with h = ⌊2n/3⌋ the value becomes (1/⌈n/3⌉)·10⁻², and with f = 1 and h = ⌊2n/3⌋ it becomes (1 − 1/⌈n/3⌉)·10⁻². With bribery, the corresponding values are 10⁻⁶, 10⁻⁴, and 10⁻² (all three lower-f rows equal 10⁻²).
- **Bribery has a modest effect on the required ratio:** Comparing the two panels of Figure 3, bribery requires a slightly higher stake-over-liquidity ratio, but its impact on the overall trend is described as insignificant. The explanation offered is that without bribery the only variable affecting rational players' profit is the Byzantines' stake, whereas with bribery a larger Byzantine share grants more power to incentivise collusion.

## Methodology in Plain English

The authors begin by setting up a formal model. There are n players, each of one of three types: honest (always follow the protocol), rational (maximise expected utility), or Byzantine (attack regardless of apparent profitability), with t ≤ t₀ = ⌈n/3⌉ − 1 Byzantine players and k rational players such that t + k < n − t₀. The system is partially synchronous: an adversary controls scheduling until a Global Stabilization Time (GST), after which players proceed in locksteps. The adversary is slowly adaptive and can change strategy only between local rounds.

They model the whole thing as an extensive-form game with imperfect information and perfect recall. But instead of solving a single game, they need a repeated one — and the Folk theorem blocks simply carrying a one-shot equilibrium over to the repeated game, which is exactly the gap the paper identifies in prior work like Trap.

The protocol they design runs in two phases per chain index. In the pre-decision phase, players run a standard BFT consensus that either agrees on a block b or lets attackers attempt a ζ-uple attack; crucially, the consensus must support transferable authentication so that misbehaving players leave undeniable proofs-of-fraud. In the commit-reveal phase, players re-send their encrypted pre-decided block or PoF list, and the encryption ensures nobody can tell who betrayed until a designated sub-phase, so Byzantine players cannot pretend to be betrayers. Once revealed, attackers' stake is slashed and redistributed to betrayers, and betrayers sit out consensus for a predetermined number of rounds.

To argue that ζ-uple attacks are rare, they reason about network topology: attackers must isolate ζ "radii" of a disk in which honest players are uniformly distributed, and they bound the aggregate success probability with Chernoff bounds under the assumption m·p < 3/e. They then prove the equilibrium properties in two cases — first assuming Byzantine players cannot bribe, then allowing bribery via a smart contract that redistributes attack proceeds. Finally, they plug numbers into the theorems to produce Table 1 and the plots of Figure 3 for n = 10⁶.

## Why This Matters

**Impact on research:** The paper pushes the honest-participant requirement from ⌊2n/3⌋+1 down to ⌊n/3⌋+1 in a partial synchrony, repeated-consensus setting — a regime the literature had treated as blocked by impossibility results. It also contributes a new problem definition (Fully Accountable Agreement, which outputs all attackers and betrayers so incentives can be applied) and shows how to bridge the one-shot-to-repeated-game gap the Folk theorem otherwise prevents.

**Real-world applications:**

- **Permissioned and regulated public blockchains** where validators must meet non-discretionary rules to create accounts — the paper explicitly names Avalanche Evergreen subnetwork, Concordium, Mina, and Redbelly, and notes that stake checks can be automated via smart contracts.
- **Payment networks that need low capital lock-up**, since the required s/ℓ can be as small as 5·10⁻⁷ at p = 10⁻³ (US$500 backing a US$1B transaction in the paper's example).
- **Exchange and custody settlement layers**, where double spending is the primary economic threat and where validators are known, identifiable entities.
- **Consortium chains with weak honesty assumptions**, where participants are profit-driven rather than altruistic and the k-rational/t-Byzantine model matches reality better than the classic 2/3-honest assumption.

**Industry relevance:** The result turns "how much must a validator lock up?" into a quantitative engineering question tied to measurable network properties (isolation-attack success probability p, detectable attacker count f, rational player count k). That is directly actionable for chain operators setting staking parameters, and it strengthens the case for accountable consensus protocols with slashing and fraud proofs.

## Future Directions

- **Relaxing the stake requirement.** Theorems 5.1 and 5.2 give sufficient conditions (s/ℓ > k·p²/(f+k) without bribery, s/ℓ > p² with bribery); the paper does not report whether these are tight, leaving open whether better bounds or alternative incentive schemes could lower the stake further.
- **Extending the accountability machinery empirically.** The paper does not report an implementation, testbed, or deployment measurements for STAKE; evaluating the two-phase protocol's latency and throughput against the named consensus backends (Polygraph, ABC, ABC++) is a natural next step.
- **Tighter modelling of isolation-attack probability.** The analysis leans on Proposition 1 (m·p < 3/e) and on granting attackers m ≥ 3 attempts. The paper does not report empirical calibration of p against real network topology, AS-level peering, or BGP behaviour, which future work could supply.
- **Stronger equilibrium notions and adversarial models.** The authors note that Nash equilibrium, Strong Nash Equilibrium, Coalition-Proof Nash Equilibrium, and Subgame-Perfect Pure Nash Equilibrium each fail to fit this setting (some require all players to be rational, others are impossible for consensus). Refining the ε-(k,t)-robust definition, or handling a fully adaptive rather than slowly-adaptive adversary, remains open.

## Target Audience

Researchers in distributed consensus and blockchain security who work on Byzantine fault tolerance thresholds, accountability, and incentive design; game theorists interested in repeated games with Byzantine participants and in equilibrium refinements for mixed honest/rational/Byzantine populations; and protocol engineers and chain operators who need to set staking parameters from a formal security argument rather than from convention. Readers without a background in partial synchrony or extensive-form games will find the theorem statements accessible but will need to consult the appendices for the proofs.

## Authors’ abstract

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…

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

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

---

Canonical: https://crypto.world/paper/stake-preventing-a-colluding-majority-from-double-spending-2610.01169
