Session 3C: Consensus CCS ’20, November 9–13, 2020, Virtual Event, USA
Everything is a Race and Nakamoto Always Wins
Stanford University
David University
Copyright By PowCoder代写 加微信 powcoder
Nakamoto invented the longest chain protocol, and claimed its se- curity 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) -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.
CCS CONCEPTS
• Security and privacy → Distributed systems security.
Proof-of-Work; Proof-of-Stake; Proof-of-Space; Security Analysis
ACM Reference Format:
, , Tas, , , Xuechao Wang, and . 2020. Everything is a Race and Nakamoto Always Wins. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS ’20), Novem- ber 9–13, 2020, Virtual Event, USA. ACM, , NY, USA, 20 pages. https://doi.org/10.1145/3372297.3417290
The authors are listed alphabetically. For correspondence on the paper, please contact DT at
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from
CCS ’20, November 9–13, 2020, Virtual Event, USA
© 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-7089-9/20/11. . . $15.00 https://doi.org/10.1145/3372297.3417290
University of Washington
University of Illinois Urbana-Champaign
Weizmann Institute of Science
Tas Stanford University
Xuechao Wang University of Illinois Urbana-Champaign
1 INTRODUCTION
1.1 Background
In 2008, invented the concept of blockchains as a
technology for maintaining decentralized ledgers [Nak08]. A core
contribution of this work is the longest chain protocol, a deceptively
simple consensus algorithm. Although invented in the context of
Bitcoin and its Proof-of-Work (PoW) setting, the longest chain
protocol has been adopted in many blockchain projects, as well as
extended to other more energy-efficient settings such as Proof-of-
Stake (PoS) (eg. [BPS16], [KRDO17],[DGKR18],[BGK 18],[FZ18])
andProof-of-Space(PoSpace)(eg.[AAC 17,CP19,PKF 18]). Used to maintain a ledger for a valued asset in a permissionless environment, the most important property of the longest chain protocol is its security: how much resource does an adversary need to attack the protocol and revert transactions already confirmed?
Nakamoto analyzed this property by proposing a specific attack: the private double-spend attack (Figure 2(a)). The adversary grows a private chain of blocks in a race to attempt to outpace the public longest chain and thereby replacing it after a block in the public chain becomes k-deep. Let λh and λa be the rate at which the honest nodes and the adversary mine blocks, proportional to their respec- tive hashing powers. Then it is clear from a law of large numbers argument that if λa > λh, then the adversary will succeed with high probability no matter how large k is. Conversely, if λa < λh , the probability of the adversary succeeding decreases exponentially with k. When there is a network delay of ∆ between honest nodes, this condition for security becomes:
λa < λgrowth(λh, ∆), (1) where λgrowth(λh, ∆) is the growth rate of the honest chain under
worst-case forking. In a fully decentralized setting with many hon- est nodes each having small mining power, [SZ15] calculates this to be λgrowth = λh /(1 + λh ∆). If we let β to be the adversary fraction of power, then (1) yields the following condition:
β< 1−β . (2) 1+(1−β)λ∆
Here, λ is the total mining rate, and λ∆ is the number of blocks mined per network delay. 1/(λ∆) is the block speed normalized by the network delay. Solving (2) at equality gives a security thresh- old βpa(λ∆). When λ∆ is small, βpa(λ∆) ≈ 0.5, and this leads to
Session 3C: Consensus
CCS '20, November 9–13, 2020, Virtual Event, USA
Nakamoto’s main claim in [Nak08]: the longest chain protocol is secure as long as the adversary has less than 50% of the total hash- ing power and the mining rate is set to be low. A more aggressive mining rate to speed up the blockchain reduces the security thresh- old. Hence (2) can be viewed as a tradeoff between security and block speed.
The private double-spend attack is a specific attack, and Nakamoto claimed security based on the analysis of this attack alone. But what about other attacks? Are there other worse attacks? A per- tinent question after Nakamoto’s work is the identification of the true security threshold β∗(λ∆) in the face of the worst attack. The groundbreaking work [GKL15] first addressed this question by formulating and performing a formal security analysis of the Proof- of-work longest chain protocol. They used a lock-step round-by- round synchronous model, and the analysis was later extended to the more realistic ∆-synchronous model [PSS17]. The results show that when λ∆ → 0, indeed β∗(λ∆) approaches 50%, thus validating Nakamoto’s intuition. However, for λ∆ > 0, there is a gap between their bounds and the private attack security threshold, and this gap grows when λ∆ grows.
1.2 Main contribution
The main contribution of this work is a new approach to the security analysis of longest chain protocols. This approach is driven by the question of whether the private attack is the worst attack for longest chain protocols in a broad sense. Applying this approach to analyze three classes of longest chain protocols in the ∆−synchronous model[PSS17], we answer this question in the affirmative in all cases: the true security threshold is the same as the private attack threshold:
β∗(λ∆) = βpa(λ∆) for all λ∆ ≥ 0 (3)
(Figure 1). The three classes are: 1) the original Nakamoto PoW protocol; 2) [DGKR18] and SnowWhite [PS17, BPS16] PoS protocols; 3) Space protocol [CP19]. They all use the longest chain rule but differ in how the lotteries for proposing blocks are run. (Figure 4) In the first two protocols, we close the gap between existing bounds and the private attack threshold by identifying the true threshold to be the private attack threshold at all values of λ∆. For Chia, the adversary is potentially very powerful, since at each time, the adversary can mine on every block of the blocktree, and each block provides an independent opportunity for winning the lottery. It was not known to be secure for any non- zero fraction of adversary power. (More specifically, while [CP19] proved the chain growth and chain quality properties for the Chia protocol, the crucial common prefix property is missing.) Our result not only says that Chia is secure, but it is secure all the way up to the private attack threshold (although the private attack threshold is smaller for Chia than for the other two classes of protocols due to the increased power of the adversary).
That the true security threshold matches the private attack threshold in all these protocols is not a coincidence. It is due to an intimate connection between the private attack and any gen- eral attack. Our approach exposes and exploits this connection by defining two key concepts: blocktree partitioning and Nakamoto blocks. Through these concepts, we can view any attack as a race between adversary and honest chains, not just the private attack.
Figure 1: True security threshold as a function of normalized block speed, compared to bounds in the literature. (a) Proof- of-work model; (b) Ouroboros/SnowWhite Proof-of-Stake model; (c) -of-Space model. In (a) and (b), the blue curve represents β∗(λ∆) = βpa(λ∆); both PoW and PoS have the same (true) security threshold. In (a), the red, green and yellow curves are obtained by solving β = (1 − β)e−2(1−β)λ∆, β = (1−β)(1−2λ∆(1−β)) and β = (1−β)(1−10λ∆(1−β)) respec- tively. In (b), the red and green curves are (1−β)/(1+λ∆) = 1/2 and (1 − β)(1 − λ∆) = 1/2 respectively. In (c), the blue curve is
the solution of eβ = 1−β , the true threshold, and also 1+(1−β)λ∆
that of private attack. Unlike in (a) and (b), the true thresh- old does not reach 0.5 when λ∆ → 0, but reach 1/(1 + e) in- stead. Note that while in all cases , the true security thresh- old equals the private attack threshold, the threshold is dif- ferent for Chia than for the other two.
However, unlike the private attack, a general attack may send many adversary chains to simultaneously race with the honest chain.
The entire blocktree, consisting of both honest and adversary blocks, public or private, is particularly simple under a private attack: it can be partitioned into two chains, one honest and one adversary (Figure 2(a)). In contrast, under a general attack where the adversary can make public blocks at multiple time instances, a much more complex blocktree can emerge (Figure 2(b)). However, what we observe is that by partitioning this more complex tree into sub-trees, each rooted at a honest block and consisting otherwise entirely of adversary blocks, one can view the general attack as initiating multiple adversary sub-trees to race with a single fictitious chain consisting of only honest blocks (Figure 3). The growth rate of each of these adversary sub-trees is upper bounded by the growth rate of the adversary chain used in the private attack. Therefore, if the private attack is unsuccessful, we know that the growth
Session 3C: Consensus CCS ’20, November 9–13, 2020, Virtual Event, USA
Figure 2: (a)Nakamoto’s private attack as a race between a single adversary chain and the honest chain. (b) By blocktree par- titioning, a general attack is represented as multiple adversary chains simultaneously racing with a fictitious honest chain. Note that this fictitious chain is formed by only the honest blocks, and may not correspond to the longest chain in the actual system. However, the longest chain in the actual system must grow no slower than this fictitious chain.
Figure 3: Race between the adversary trees and the fictitious honest chain. While there may be multiple adversary trees simultaneously racing with the honest chain, the growth rate of each tree is bounded by the growth rate of the ad- versary chain in the private attack. An honest block is a Nakamoto block when all the previous adversary trees never catch up with the honest chain past that block.
rate of each of the adversary trees must be less than that of the fictitious honest chain. What we show, for each of the three classes of protocols, is that under that condition, there must exist honest blocks, which we call Nakamoto blocks, each having the property that none of the past adversary trees can ever catch up after the honest chain reaches the block. These Nakamoto blocks serve to stabilize the blockchain: when each such block enters the blocktree, complex as it may be, we are guaranteed that the entire prefix of
1 the longest chain up to that block remains immutable in the future .
When Nakamoto blocks occur and occur frequently, the persistence and liveness of the blockchain is guaranteed.
1.3 Related works
There have been several significant ideas that have emerged from
the security analysis of blockchains in the past few years, and below
we put our contribution in the perspective of these ideas.
[GKL15] initiated blockchain security analysis through defining
key backbone properties2 of chain common prefix, chain quality
and chain growth. Applying this framework to analyse the PoW
longest chain protocol in the lock-step round-by-round model, it is
shown that the common prefix property, the most difficult property
to analyze, is satisfied if the number of adversary blocks over a
long window is less than the number of uniquely successful honest
blocks . A similar block counting analysis is conducted by [PSS17]
in the ∆− synchronous model, with the notion of uniquely suc- cessful blocks replaced by the notion of convergence opportunities. The resulting bound is tight when λ∆ is small but loose in gen- eral. Moreover, the block-counting technique completely breaks down for analyzing PoS longest chain protocols because of the notorious Nothing-at-Stake problem: winning one lottery can yield a very large number of blocks for the adversary. To overcome this issue, two new ideas were invented. In the Ouroboros line of work [KRDO17, DGKR18, BGK+18], a new notion of forkable strings was invented and a Markov chain analysis was performed to show con- vergence of the longest chain regardless of adversary action if the adversary stake is below a certain threshold. Sleepy Consensus and SnowWhite [PS17, BPS16] took a different approach and defined a notion of a pivot, which is a time instance t such that in all time in- tervals around t , there are more honest convergence opportunities than the number of adversary slots. They showed that a pivot forces convergence of the longest chain up to that time, and moreover if the adversary stake is less than a certain threshold, then these pivots must occur and they must occur often.
Despite this impressive stream of ideas, the true security thresh- old was still unknown for both the PoW and PoS longest chain protocols. Moreover, the analysis techniques seem very tied to the specific longest chain protocol under study. The definition of a pivot in [PS17], for example, is tied to the specific longest chain protocol, SnowWhite, they designed. In contrast, the notion of Nakamoto blocks in our approach can be viewed as a more general notion of pivots, but defined for general longest chain protocols and designed to tie the problem back to the private attack. Even though the anal- ysis method in [PS17] has already evolved (or, shall we say, pivoted) from the analysis method in [GKL15], the influence of the block 2
Properties of the blocktree, independent of the content of the blocks.
13 Thus, Nakamoto blocks have a god-like permanence, they exist, but nobody knows
which block is a Nakamoto block.
A uniquely successful honest block is one that is the only honest block mined in a round.
Session 3C: Consensus
CCS ’20, November 9–13, 2020, Virtual Event, USA
counting method is still felt in the definition of a pivot. We depart from this method by defining a Nakamoto block directly in terms of structural properties of the evolving blocktree itself. In fact, our approach was motivated from analyzing a protocol like Chia, where the rate of adversary winning slots grows exponentially over time and hence a condition like the one used in [PS17] does not give non-trivial bounds.
The present paper is an extension of an earlier version [BDK+19], where we introduced and applied this approach to analyze a PoS longest chain protocol [FZ18] similar to the Chia protocol. Since we released that early version, we became aware of an indepen- dent work [KQR20], which obtains the true security threshold as well as linear consistency for the protocol in the lock-step round-by-round model. They achieved this by tightening the definition of a pivot in [PS17] to count all honest slots, includ- ing concurrent ones, not only uniquely successful ones. Like the original definition of pivots, however, this definition is tied to the specific protocol. The approach would not give non-trivial bounds for the Chia protocol, for example. Moreover, their result on the Praos protocol under the ∆-synchronous model is not tight (Figure 1(b)). We believe this is due to their analysis technique of mapping the ∆-synchronous model back to the lock-step round-by-round model. In contrast, our analysis is directly in the ∆-synchronous model and yields tight results in that model.
After the initial submission of this paper, we were made aware of independent work [GKR20], which obtained the same results for the PoW and the Ouroboros PoS protocols, but using totally a different set of techniques based on forkable strings.
1.4 Outline
In Section 2, we introduce a unified model for all three classes of protocols. In Section 3, we introduce the central concepts of this work: blocktree partitioning and Nakamoto blocks. These concepts are applicable to any longest chain protocol. In Section 4, we use these concepts in the security analysis of the three classes of pro- tocol attaining the private attack security threshold of each. In Section 5 we explore the question of whether the private attack is worst case in a stronger sense for longest chain protocols.
A key goal of this paper is to provide a common framework to analyze the security properties of various longest chain protocols. We focus here primarily on the graph theoretic and the stochastic aspects of the problem: some resource-dependent randomness is utilized by these protocols to select which node is eligible to create a block. The modality in which the randomness is generated leads to different stochastic processes describing the blocktree growth. Understanding these stochastic processes and the ability of the adversary to manipulate these processes to its advantage is the primary focus of the paper.
Different longest chain protocols use different cryptographic means to generate the randomness needed. We specifically exclude here the cryptographic aspects of the protocols, whose analysis is necessary to guarantee the full security of these protocols. In most of the protocols we consider (for example [GKL15, KRDO17]), the cryptographic aspects have already been carefully studied in the
original papers and are not the primary bottleneck. In others, further work may be necessary to guarantee the full cryptographic security. In all of these protocols, we assume ideal sources of randomness to create a model that can then be analyzed independently.
We will adopt a continuous-time model, following the tradi- tion set by Nakamoto [Nak08] and also used in several subsequent influential works (eg. [SZ15]) as well as more recent works (eg. [Ren19] and [LG20]). The continuous-time model affords analytical simplicity and allows us to focus on the essence of the problem without being cluttered by too many parameters. Our model corre- sponds roughly to the ∆−synchronous network model introduced in [PSS17] in the limit of a large number of lottery rounds over the duration of the network delay. This assumption seems quite reasonable. For example, the total hash rate in today’s Bitcoin net-
work is about 100 ExaHash/s, i.e. solving 10
Nevertheless, we believe our results can be extended to the discrete setting.
We first explain the model in the specific context of Nakamoto’s Proof-of-Work longest chain protocol, and then generalize it to a unified model for all three classes of protocols we study in this paper.
2.1 Modeling proof-of-work longest chain
The blockchain is run on a network of n h
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com