PaperlayerView exact revision on arXiv

Source-linked AI summary

Everything is a Race and Nakamoto Always Wins

Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, Ofer Zeitouni

arXiv:2005.10484v4cs.CR

TL;DR

The paper asks whether Nakamoto’s private double-spend attack is the worst attack on longest-chain protocols, a question left open by gaps between earlier bounds and the private-attack threshold. It reduces general attacks to races against an honest chain and shows that the true security threshold matches the private-attack threshold for the three studied protocol classes.

  • Problem

    Earlier analyses left the true security threshold uncertain for positive λ∆, with a growing gap from the private-attack threshold.

    Source: §1.1 · p. 1

  • Method

    The paper analyzes general attacks by modeling adversary blocks racing against honest blocks, including multiple adversary branches in a unified framework.

    Source: §1.2 · p. 2, §2.2 · p. 5

  • Results

    The private-attack threshold is the true security threshold for PoW and Ouroboros/SnowWhite PoS, and the Chia protocol’s persistence and liveness hold with probability at least 1 −e^−Ω(σ^(1−ε)), for any ε > 0.

    Source: §4.1 · p. 10

  • Takeaways & Limitations

    The private attack characterizes the security threshold for all three studied protocol classes, including Chia, whose threshold is lower than those for PoW and PoS.

    Source: §4.1 · p. 10

    The PoS analysis assumes static stake in a single epoch and a common clock, while the Chia model assumes fixed resource allocations and permits adversarial mining across the blocktree.

    Source: §2.3 · p. 6, §2.4 · p. 7

Abstract

from arXiv · show

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

1 INTRODUCTION

The paper asks whether Nakamoto’s private double-spend attack captures the worst attack and answers yes for PoW, Ouroboros/SnowWhite PoS, and Chia PoSpace. It connects general attacks to races against an honest chain and uses that connection to identify security thresholds and relate its approach to earlier analyses.

1.1 Background

  • The private double-spend attack races an adversary’s private chain against the public longest chain, but earlier analyses left a gap between known bounds and its threshold when λ∆ > 0.The gap grows as λ∆ grows; λ∆ is the number of blocks mined per network delay.Source: §1.1 · p. 1

1.2 Main contribution

  • The true security threshold equals the private-attack threshold for Nakamoto PoW, Ouroboros/SnowWhite PoS, and Chia PoSpace in the ∆-synchronous model.For Chia, the threshold is lower than for PoW and PoS because the adversary has increased mining power.Source: §1.2 · p. 2
  • Blocktree partitioning represents a general attack as multiple adversary subtrees racing against a fictitious chain of honest blocks.Each subtree’s growth is bounded by the private-attack adversary chain; Nakamoto blocks mark honest blocks past which earlier adversary trees cannot catch up.Source: §1.2 · p. 2, Figure 2 · p. 3, Figure 3 · p. 3

1.3 Related works

  • Earlier PoW analyses used block counting and convergence opportunities, while PoS work used forkable strings or protocol-specific pivots to establish chain convergence.The pivot approach can fail to give non-trivial bounds for Chia, where adversary slot-winning rates grow exponentially over time.Source: §1.3 · p. 3
  • The paper presents Nakamoto blocks as a structural, general-protocol counterpart to pivots and analyzes directly in the ∆-synchronous model to obtain tight results there.It contrasts this with [KQR20], whose Praos result in that model is not tight, and notes independent work obtaining the same PoW and Ouroboros results through forkable strings.Source: §1.3 · pp. 3–4

1.4 Outline

  • The paper introduces a unified model, develops blocktree partitioning and Nakamoto blocks, analyzes the three protocol classes, and then examines whether the private attack is worst case in a stronger sense.The analysis is organized across Sections 2–5.Source: §1.4 · p. 4

2 MODELS

The paper models longest-chain growth in continuous time, then unifies PoW, Praos/SnowWhite PoS, and Chia by varying the adversary’s block-mining process. Their shared honest-node and network assumptions make the models comparable, while their lottery mechanisms give the adversary different ways to mine across the blocktree.

2 MODELS

  • The analysis uses a continuous-time model with bounded honest-node communication delay ∆ and assumes ideal randomness, setting cryptographic security analysis aside.The model is intended to capture the ∆-synchronous setting in the limit of many lottery rounds during a network delay.Source: §2 · p. 4, §2.1 · p. 4

2.1 Modeling proof-of-work longest chain

  • In the PoW model, honest nodes extend their locally viewed longest chain, while the adversary can mine anywhere in the mother tree and control when blocks become public.The mother tree includes mined blocks that remain private or have not yet reached other honest nodes; honest-node views may differ by up to ∆.Source: §2.1 · pp. 4–5

2.2 From PoW to a unified model

  • The unified model keeps honest behavior fixed and changes M1: PoW mines on one chosen parent, Praos/SnowWhite append each adversary arrival across the tree, and Chia uses independent processes per parent.The adversary’s total mining rate grows with the tree in PoS and Chia, but mining events across blocks are dependent in PoS and independent in Chia.Source: §2.2 · p. 5

2.3 Ouroboros Praos and Snow White Proof-of-Stake model

  • The Praos/SnowWhite model assumes fixed stake and common randomness at genesis, a single epoch, and synchronous common clocks; honest nodes extend the longest chain while a winning adversary may build on distinct chains.A VRF determines proposal eligibility, and its output can be validated using the corresponding public key.Source: §2.3 · p. 6

2.4 Chia Proof-of-Space model

  • In Chia, each node’s mining time is uniform on (0,T), yielding expected inter-arrival time T/(N+1); the adversary has independent Poisson mining processes at each tree block.Honest and adversarial rates are proportional to their respective disk space, and the adversary can compute VDF outputs in parallel.Source: §2.4 · p. 7

3 BLOCKTREE PARTITIONING AND NAKAMOTO BLOCKS

The section reduces general attacks to races between adversary subtrees and a fictitious honest chain or tree. Honest blocks that win these races are Nakamoto blocks, which remain in the longest chain, including when network delay causes honest-chain forking.

3.1.1 Blocktree partitioning

  • Blocktree partitioning divides the mother tree into adversary subtrees rooted at honest blocks, each containing adversary blocks reachable without passing through another honest block.Each subtree begins when its root honest block is mined and grows as adversary blocks extend its chains.Source: §3.1.1 · p. 7

3.1.2 Nakamoto blocks

  • A Nakamoto block wins a race against every adversary tree rooted at an earlier honest block in a fictitious system whose chain contains only honest blocks.The construction lets the analysis represent general attacks as multiple adversary chains racing the honest chain.Source: §3 · p. 7, §3.1.2 · p. 8
  • At zero network delay, any Nakamoto block remains in the longest chain forever, so its preceding prefix is permanent.Although the race is defined using a fictitious honest chain, the actual longest chain can grow at least as fast.Source: §3.1.2 · p. 8

3.2 General network delay ∆

  • With positive delay, the definition requires the honest block to be a loner and compares adversary trees against a fictitious honest tree that allows worst-case forking.The changes address honest-node split views and the overestimate of chain growth from simply counting mined honest blocks.Source: §3.2 · pp. 8–9
  • For any ∆, a Nakamoto block remains in the chain forever, and the chain through that block has stabilized by time τh_j + ∆.The framework applies across all three models without statistical assumptions about the adversary’s mining process for the stability result.Source: §3 · p. 7, §3.2 · p. 9
  • The race-based definition tightens the Praos/SnowWhite security threshold to match the private-attack threshold, unlike the pivot definition in.The paper attributes the tight characterization to defining Nakamoto blocks directly through the race against the fictitious honest chain.Source: §3.2 · p. 9

4 SECURITY ANALYSIS

The section establishes that the private-attack threshold is the true security threshold for all three models, then derives persistence and liveness guarantees from Nakamoto-block occurrence. It applies a shared method to PoW, Ouroboros/SnowWhite PoS, and Chia.

4.1 Statement of results

  • For all mining rates and network delays, the three models’ security threshold equals Nakamoto’s private-attack threshold and depends only on λ∆.Source: §4 · p. 9, §4.1 · p. 10
  • For all three models, each transaction has persistence (τ = σ) and liveness (u = σ) with probability at least 1 − e^-Ω(σ^(1−ε)), for any ε > 0.These are per-transaction guarantees on the infinite horizon; for a finite ledger over a polynomial time horizon, a union bound yields whole-ledger high-probability guarantees.Source: §4.1 · p. 10
  • The guarantees are per transaction on the infinite horizon; whole-ledger high-probability guarantees are stated for finite ledgers over polynomial horizons.The finite-ledger guarantee follows by applying the union bound.Source: §4.1 · p. 10

4.2 Approach

  • Bounding intervals without Nakamoto blocks is sufficient: if P(B_s,s+t) < q^t independently of s and adversary strategy, persistence and liveness follow.Source: §4.2 · p. 10
  • Recursive bootstrapping bounds the probability of no Nakamoto blocks by exp(−Ω(t^(1−ε))) for any ε > 0, improving on the exp(−Ω(√t)) bound cited for.Source: §4.2 · p. 10

4.3 Nakamoto PoW and Praos/SnowWhite PoS Models

  • Nakamoto blocks occur regularly in PoW and Praos/SnowWhite PoS; proving this for the stronger PoS adversary suffices for both models.The probability that any j-th honest block is a Nakamoto block is bounded below by a positive constant.Source: §4.3 · pp. 10–11

4.4 Chia Proof-of-Space Model

  • In Chia, adversary-tree depth grows at rate eλa, an e-fold increase over Praos/SnowWhite because mining opportunities at different blocks are independent.Source: §4.4 · p. 11
  • In Chia, every j-th honest block has probability greater than p > 0 of being a Nakamoto block.Source: §4.4 · p. 11

5 DOES NAKAMOTO REALLY ALWAYS WIN?

The private attack matches the tight security threshold across the three models, but the deterministic worst attack can differ by model and mining-time sequence. With zero network delay, a strengthened private attack matches arbitrary PoW attacks under the same mining times; atypical arrival sequences give Praos/SnowWhite a counterexample.

5 DOES NAKAMOTO REALLY ALWAYS WIN?

  • The private-attack threshold is the tight security threshold for M1-PoW, M1-PS, and M1-Chia.The section asks whether this statistical result also means the private attack is deterministically worst.Source: §5 · p. 11
  • At ∆=0, the pre-mining strategy πSZ matches arbitrary attacks on persistence and liveness under the same mining times.If an arbitrary attack violates persistence for a block, πSZ does too; likewise for the specified consecutive honest blocks that violate liveness.Source: §5 · p. 11
  • For the first honest block at ∆=0, πSZ reduces to Nakamoto’s private attack, and no honest blocks fork across depths.The proof uses the fact that at most one honest block can occur at any depth.Source: §5 · p. 12
  • Under the Figure 5 mining times, the arbitrary attack succeeds with L(t)=3, while the private attack has A=4 and H=2 and can remove b1 when the honest chain reaches 3.The proof bounds adversary blocks by A ≥ max{H,k}; under the private attack, the private chain has length A while the honest chain has length H.Source: Figure 5 · p. 12, §5 · p. 12
  • For Praos/SnowWhite, an atypical arrival sequence lets a balance attack violate persistence even when the private attack cannot, despite a 1/2 security threshold at ∆=0.The example relies on periodic arrivals and is not sustainable in a random environment.Source: §5 · p. 12, Figure 6 · p. 12

A DEFINITIONS AND PRELIMINARY LEMMAS FOR THE PROOFS

This appendix introduces depth-increment and event notation used in the proofs, including loner and Nakamoto-block events and an adversary catch-up event.

A DEFINITIONS AND PRELIMINARY LEMMAS FOR THE PROOFS

B PROOF OF THEOREM 3.2

The proof bounds honest-chain growth under message delay, then uses that bound to establish stabilization properties for Nakamoto blocks.

B PROOF OF THEOREM 3.2

  • Dh(t) provides a conservative bound on chain growth from s to t, supporting the proof that a Nakamoto block remains in future chains.The proof considers the j-th honest block being a loner and argues by contradiction if it is absent from a future chain.Source: B PROOF OF THEOREM 3.2 · p. 14
  • Delaying every honest block by ∆ minimizes the increase in an honest miner’s chain length over the specified interval.With all blocks delayed by ∆ and no adversary blocks heard in [s,t], the depth process follows Dh; earlier delivery or adversary blocks only increase the chain-length difference.Source: B PROOF OF THEOREM 3.2 · p. 14
  • The stabilization argument combines the Nakamoto-block event with a bound on growth in the tree rooted at an earlier honest block.The cited proof steps use the event and Proposition B.1 to derive a contradiction.Source: B PROOF OF THEOREM 3.2 · p. 14

C PROOFS FOR SECTION 4.3

These appendix proofs characterize honest-depth increments under delay and define an event tracking adversary arrivals during depth growth.

C PROOFS FOR SECTION 4.3

  • Each depth-increment time Xd has the form ∆+Yd, where the Yd are i.i.d. exponential random variables with rate λh.Consequently, the Xd are i.i.d. with mean stated in the proposition’s continuation.Source: C PROOFS FOR SECTION 4.3 · pp. 14–15
  • The ∆ offset arises because honest blocks arriving within ∆ of the first block at a depth map to that same depth.After that interval, the next honest arrival is exponential with rate λh by memorylessness.Source: C PROOFS FOR SECTION 4.3 · p. 14
  • Bn is the event that at least n adversary arrivals occur while Dh grows from depth 0 to depth n.Its proposition is proved using a Chernoff bound and Proposition C.1.Source: C PROOFS FOR SECTION 4.3 · p. 15

C.1 Proof of Lemma 4.5

The proof lower-bounds the chance that an honest block is a Nakamoto block by conditioning on it being a loner and analyzing adversary catch-up with a random walk. It obtains a positive bound independent of the block index.

C.1 Proof of Lemma 4.5

  • The proof bounds the event that the deepest adversary tree stays behind by decomposing it into events at honest-block arrival times and using independence of E2 and E3.E1 requires the deepest adversary tree to trail the honest tree at the j-th honest block’s arrival; E3 constrains the depths of earlier adversary trees.Source: §C.1 · p. 15
  • With zero network delay, S[n] tracks the difference between honest and adversary arrivals; positive delay requires a modified walk because honest-chain growth depends on ∆.For ∆=0, honest arrivals increase the walk by one and adversary arrivals decrease it by one.Source: §C.1 · p. 16
  • The proof reduces E2 to a random walk whose positive drift makes every state transient and leaves a positive probability of never hitting or falling below zero.The argument invokes the Strong Law of Large Numbers and finite expected absolute jump size.Source: §C.1 · p. 16
  • P(Fj | Uj) ≥ e^-2λa∆c^2 = p > 0, with p independent of j, lower-bounds the chance of no catch-up given a loner block.The bound combines a positive probability for the random-walk event E2 with the probability of no adversary arrivals during the delay window.Source: §C.1 · p. 16

C.2 Alternative Proof of Lemma 4.5

In the Praos/SnowWhite model, adversary trees grow at the adversary arrival rate while the honest tree grows more slowly under network delay. Below the resulting rate threshold, an honest block has a nonzero chance of being a Nakamoto block.

C.2 Alternative Proof of Lemma 4.5

  • When λa < λh/(1 + λh∆), each honest block has a nonzero probability of being a Nakamoto block.Adversary trees grow at rate λa, whereas the honest tree grows at rate λh/(1+λh∆); trees rooted farther behind the honest tip fall behind and cannot catch up.Source: §C.2 · p. 16
  • The analysis can focus on adversary trees rooted at honest blocks immediately preceding hj, because trees rooted farther back fall behind when λa < λh/(1 + λh∆).There are only a small number of immediately preceding honest blocks, so there is a nonzero chance none of their adversary trees catches up.Source: §C.2 · p. 16
  • For sufficiently large B, the proof obtains a bound below any chosen positive constant c4 < 1 for the event B′2, uniformly over j.This bound is used in the alternative proof’s control of the catch-up probability.Source: §C.2 · p. 17

C.3 Proof of Lemma 4.6

The proof controls the probability of adversary trees catching up by combining interval-based independence with bounds on atypical arrival events. It derives exponential decay in the separation between block indices.

C.3 Proof of Lemma 4.6

  • P( B̂ik) < C2e^-C3(k-i) for k > i+1, giving an exponentially decreasing bound as the block-index gap grows.The constants C2 and C3 are positive and chosen as functions of fixed δ.Source: §C.3 · p. 17
  • The proof partitions a time interval into sub-intervals and uses independent catch-up events Cℓ to bound the probability of avoiding catch-up across them.It separately controls atypical events in which arrival counts are unusually high or low.Source: §C.3 · p. 18
  • A recursive bootstrapping argument extends the bound from the base case m = 2 to all θ ≥ 1.The recursion is mk = 2mk−1−1, with mk = k+1 and limit 1.Source: §C.3 · pp. 18–19

D.1 The adversary tree via branching random walks

The adversary tree is represented as a branching random walk whose vertex labels encode block appearance times. The appendix uses this representation and a stationary extension to establish growth and positive-probability bounds.

D.1 The adversary tree via branching random walks

  • The proof constructs a labelled rooted tree in which each vertex is the indexed child of its parent, with generations corresponding to block depth.A vertex’s ancestors are represented by its successive prefixes.Source: §D.1 · p. 19
  • The adversary tree is encoded as a branching random walk: exponential waiting times label vertices, and Sv gives each vertex’s appearance time.The minimum at level k corresponds to the time of appearance of a block at that depth.Source: §D.1 · p. 19
  • For sufficiently large t, D0(t) is bounded above by eλat; if eλa > λh, it eventually exceeds λht.The bounds follow from Lemmas D.1 and D.2 and equation (56).Source: §D.1 · p. 20

D.2 Proof of Lemma 4.8

  • Extending the processes to negative time and adding independent adversary trees allows the proof to establish P(Ê0) > 0.The argument chooses n sufficiently large so the accumulated bounds are small enough.Source: §D.2 · pp. 20, 22

D.3 Proof of Lemma 4.9

The proof establishes the claim first for ε = 1/2, then extends it to arbitrary ε by recursively bootstrapping the bound. Its estimates control atypical events and use independent catch-up events in separated time intervals.

D.3 Proof of Lemma 4.9

  • The proof proceeds in two steps: establish the bound for ε = 1/2, then bootstrap recursively to arbitrary ε.The bootstrap starts from m = 2 and uses a recursion whose thresholds approach 1.Source: §D.3 · pp. 22–23
  • The proof uses a uniform positive lower bound on P( F̂_j ) when bounding the probability of the selected events.The supplied passage gives p as a uniform lower bound for all j, provided by Lemma 4.8.Source: §D.3 · p. 22
  • Atypical events in which an adversary tree catches up with a far-ahead honest block are bounded as part of the proof.The argument also controls atypical arrival counts in intervals of length √t using Poisson-process properties and a union bound.Source: §C.3 · p. 18, §D.3 · pp. 22–23
  • Independent catch-up events in separated sub-intervals provide the repeated opportunities used in the bootstrap argument.The proof selects every third sub-interval and states that the corresponding events are independent.Source: §D.3 · pp. 22–23

E PROOF OF PERSISTENCE AND LIVENESS

This proof establishes persistence by bounding the probability that two honest nodes adopt incompatible longest chains. It establishes liveness by finding a future honest block whose ancestry is retained in every future longest chain, thereby stabilizing a transaction already received by all honest nodes.

E PROOF OF PERSISTENCE AND LIVENESS

  • The persistence proof assumes incompatible chains and partitions recent honest blocks by whether they occur on either chain or neither.It prunes each chain to blocks mined by t − σ and uses the resulting prefix condition to derive the stated low-probability event.Source: E PROOF OF PERSISTENCE AND LIVENESS · p. 23
  • A transaction received by all honest nodes is stabilized when a suitable honest block mined within [t, t + σ] and its ancestors appear in every future longest chain.The proof places the transaction in that block or an ancestor because it was received before the block was mined.Source: E PROOF OF PERSISTENCE AND LIVENESS · pp. 23–24

F.1 Proof of Theorem 5.1

For zero network delay, the proof compares an arbitrary successful attack with the πSZ strategy on the same block-mining times. It shows πSZ can prevent persistence and liveness whenever the arbitrary attack does so.

F.1 Proof of Theorem 5.1

  • πSZ also succeeds in preventing persistence whenever an arbitrary attack does so for the same mining-time sequence.The strategy pre-mines private chains, restarting from each new honest block when its current private chain is shorter, before beginning a private attack.Source: §F.1 · p. 24
  • The argument compares the public longest chain C, containing b at time t, with a parallel chain C′ at least as deep that excludes b; both share a last honest block hi.Figure 8 gives a visual example of the chains C and C′.Source: §F.1 · p. 24
  • Under πSZ, the private chain can exclude a block b and reach at least the public chain’s depth, so b can be removed after becoming k-deep.The proof compares the public chain depth with a private chain built from adversary blocks mined after the last shared honest block.Source: §F.1 · p. 25
  • πSZ also prevents liveness for k consecutive honest blocks whenever an arbitrary attack violates their liveness on the same mining-time sequence.The proof constructs a private chain excluding those blocks and broadcasts it at time t∗.Source: §F.1 · pp. 25–26

F.2 Discussion on ∆> 0

When network delay is positive, no single attack is worst on every mining-time sequence. The proof shows that two possible actions are preferable under different sequence classes, while atypical sequences where an attack is dominated can have positive, though possibly very small, probability.

F.2 Discussion on Δ > 0

  • When Δ > 0 and λa < λh/(1 + Δλh), no worst attack succeeds on every mining-time sequence except a measure-zero set.This is the condition stated in Lemma F.1.Source: §F.2 · p. 26
  • The optimal action switches across sequence classes: action 1 is preferable under sequence 1, while action 2 is preferable under sequence 2.For each class, the proof identifies positive-probability later sequences on which the other action fails to prevent persistence.Source: §F.2 · p. 27
  • For any fixed attack, some positive-probability mining-time sequences may favor another strategy, but for the private attack these atypical sets shrink to zero as k grows.The stated asymptotic claim fixes finite Δ and concerns the private attack’s role in achieving the security threshold.Source: §F.2 · p. 27
Loading 2005.10484v4…