Bitcoin’s Latency–Security Analysis Made Simple
Northwestern University
University of Illinois at Urbana-Champaign
Copyright By PowCoder代写 加微信 powcoder
non-lockstep synchrony model [6, 10–12]. The fundamental fault tolerance limit of the Nakamoto consensus has also been obtained [2, 4].
Most existing latency-security analysis of the Nakamoto consensus focused on asymptotic results. This means they showed that transactions in the Nakamoto consensus even- tually become permanent (also called committed, decided, finalized, or immutable in the literature), but do not provide concrete results on when that happens. Several recent works give concrete analysis [5, 7, 8] but their methods are quite complex. In particular, [7, 8] resort to a stochastic analysis of races between renewal processes and focus on confirmation by time rather than the more practically relevant confirmation by depth. Reference [5] involves an complicated analysis of forkable strings and an iterative dynamic programming algo- rithm to numerically evaluate a Markov chain, and the results are not in a closed form.
In this paper, we develop two sets of simple upper and lower bounds on the security of the Nakamoto consensus as a function of the confirmation depth, the mining rates, and a block propagation delay upper bound. One set of upper and lower bounds are essentially exponential functions in the confirmation depth. A second set of closed-form bounds are numerically closer and still easy to compute using finite sums of geometric and binomial distribution functions.
The gap between the upper and lower bounds is small for the Bitcoin parameters. For example, assuming on aver- age one block is mined every ten minutes, the delay bound is ten seconds, and 10% of the mining power is adversar- ial, the probability of safety violation of the 6-block rule of thumb is bounded between 0.11% and 0.35%. If the adver- sarial mining power increases to 25%, one needs a 20-block rule to achieve similar bounds. For the Bitcoin parameters and relatively small confirmation depths, our new upper bound is tighter than the best existing result in [5].
In this paper, we introduce a new reduction technique to an- alyze Nakamoto consensus protocols. We describe a “rigged” model in which some selected blocks mined by honest nodes are converted into adversarial blocks. Such conversion can only make the adversary more powerful. We judiciously se- lect those blocks for conversion such that the sequence of honest/adversarial blocks remains memoryless in the rigged model. We show that the well-understood private-mining attack is a best attack in the rigged model. Finally, we ob- tain simple upper and lower bounds on the safety violation probability for the original model by analyzing the success probability of the private-mining attack in the rigged model.
The remainder of the paper is organized as follows. In Sec- tion 2, we present the canonical model for the Nakamoto
Simple closed-form upper and lower bounds are developed for the security of the Nakamoto consensus as a function of the confirmation depth, the honest and adversarial block min- ing rates, and an upper bound on the block propagation delay. The bounds are exponential in the confirmation depth and apply regardless of the adversary’s attack strategy. The gap between the upper and lower bounds is small for Bitcoin’s parameters. For example, assuming an average block interval of ten minutes, a network delay bound of ten seconds, and 10% adversarial mining power, the widely used 6-block confir- mation rule yields a safety violation between 0.11% and 0.35% probability.
ACM Reference Format:
and . 2022. Bitcoin’s Latency–Security Analy- sis Made Simple. In 4th ACM Conference on Advances in Financial Tech- nologies (AFT ’22), September 19–21, 2022, San Francisco, CA, USA. ACM, , NY, USA, 10 pages. https://doi.org/10.1145/3558535. 3559791
1 INTRODUCTION
The famed Bitcoin white paper presented a novel Byzantine fault tolerant consensus algorithm that is now known as the Nakamoto consensus [9]. A notable property of the Nakamoto consensus is that the deeper a transaction is in a longest blockchain, the safer it is to commit the transaction. In fact, the probability that a transaction’s safety is violated decreases essentially exponentially with the number of “confirmations”. A latency-security analysis of the Nakamoto consensus aims at deriving upper bounds on the safety violation probability of a given confirmation rule, under all possible attacks allowed in a formally described model.
While the Nakamoto consensus protocol is simple and ele- gant, rigorously analyzing its latency and security turns out to be quite challenging. The Bitcoin white paper did not provide a formal model or rigorous analysis; instead, it only consid- ered one specific attack. Garay et al. [3] provided the first latency-security analysis for the Nakamoto consensus against all possible attacks. Follow-up works extended their analy- sis from a lockstep synchrony model to the more realistic
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 ACM 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
AFT ’22, September 19–21, 2022, San Francisco, CA, USA
© 2022 Association for Computing Machinery. ACM ISBN 978-1-4503-9861-9/22/09. . . $15.00 https://doi.org/10.1145/3558535.3559791
consensus. The main theorems are given in Section 3. In Sec- tion 4, we show that the well-known private-mining attack is optimal under a special condition. In Section 5, we construct a rigged model which on one hand makes the adversary more powerful, and on the other hand makes the private-mining attack optimal. Two sets of upper and lower bounds on the probability of safety violation are then obtained in Sections 5 and 6. Numerical results are given in Section 7.
2 THE CANONICAL MODEL
We assume the readers are familiar with how the Nakamoto consensus protocol works. We briefly describe the protocol be- low only to introduce notation. The protocol builds a growing sequence of transaction-carrying blocks where every block is chained to its predecessor block by a solution to a computa- tional puzzle (i.e., a proof of work). At any point in time, every honest node attempts to “mine” a new block that extends a longest chain of blocks (blockchain) to its knowledge; once a new longest blockchain is mined or received, an honest node sends it to other nodes through a gossip network. We will use chains and blockchains interchangeably in this paper. A node commits a block when at least 𝑘 − 1 blocks are mined on top of it as part of a longest blockchain known to that node, where 𝑘 is a natural number chosen by the node. We call this the 𝑘-confirmation commit rule.
We now define the blockchain data structure. Let us num- ber all the blocks in the time order they are mined. The 𝑗-th block in this numbering is called block 𝑗 for short. We de- note a blockchain using a sequence of block numbers, e.g., inblockchain (𝑏0,𝑏1,𝑏2,…,𝑏𝑚),the𝑖-thblockinthechainis block 𝑏𝑖 . A blockchain always starts with the Genesis block 𝑏0 = 0 that is known to all nodes by time 0, when the protocol starts. Each subsequent block 𝑏𝑖 must contain a proof of work thatbindsittothepredecessorblock𝑏𝑖−1.Thelastblock,𝑏𝑚 in the above example, uniquely identifies the entire blockchain, so we will also refer to the above blockchain as blockchain 𝑏𝑚 or chain 𝑏𝑚 . The position of a block in the blockchain is called its height. We will use h𝑏 to denote the height of block 𝑏. In the
confirmation depth
total mining rate
fraction of honest mining rate
block propagation delay upper bound height of block 𝑏
mining time of block 𝑏
fraction of honest blocks in the rigged model
above example, block 𝑏𝑖 is on height 𝑖, i.e., h𝑏 block is on height 0).
We adopt a natural continuous-time model and model proof-of-work mining as a homogeneous Poisson point pro- cess. Let 𝜆 be the total mining rate of the network (honest and adversarial nodes combined). Let 𝜌 ∈ ( 12 , 1] be the fraction of honest mining rate and 1 − 𝜌 be the fraction of adversarial mining rate. Note that the model allows some of the nodes to have zero mining rate, hence capturing light nodes. In the canonical model, a block is said to be honest (resp. adversar- ial) if it is mined by an honest (resp. adversarial) node. One can think of honest block arrivals and adversarial blocks as two independent Poisson processes with rates 𝜌𝜆 and (1 − 𝜌)𝜆, respectively. Due to the Poisson merging and splitting proper- ties, it is equivalent to think of all blocks arrivals as a single Poisson process with rate 𝜆 where each block is honest with probability 𝜌 and adversarial with probability 1 − 𝜌.
Table 1: Some frequently used notations.
We use 𝑡𝑗 to denote the time block 𝑗 is mined. Evidently, 0=𝑡0 ≤𝑡1 ≤𝑡2 ≤….Ifblock𝑗isminedbyanhonestnode,it must extend a longest blockchain to that node’s knowledge immediately before 𝑡 𝑗 . Ties are broken arbitrarily or by the ad- versary at will. The honest node will also immediately publish the newly mined block 𝑗 through a gossip network.
Without loss of generality, we assume a single adversary controls all adversarial mining power. If the adversary mines block 𝑗, the block may extend any blockchain mined by time 𝑡 𝑗 and may be presented to each individual honest node at any time from 𝑡 𝑗 onward at will. The adversary in practice cannot predict the arrival times of future blocks but our results hold even against an omniscient adversary that sees the arrival times of all future blocks.
We assume the standard (non-lockstep) synchrony model. We abstract away the topology and operations of the gossip network by assuming a universal block propagation delay upper bound, denoted as Δ ≥ 0. Applying it to the Nakamoto consensus, if any honest node mines or receives a new longest blockchain 𝑏 at time 𝑡 , then all nodes receive blockchain 𝑏 by time 𝑡 + Δ.
A block may contain an arbitrary number of transactions. A transaction may appear in multiple chains but it can appear at most once in any given chain. The adversary’s goal is to attack the safety of a target transaction [9], as defined below.
DEFINITION 1 (SAFETY VIOLATION OF A TARGET TRANSAC- TION). Atargettransaction’ssafetyisviolatedifablockcontaining the target transaction is committed and a different block (which may or may not contain the target transaction) is also committed on the same height.
In this paper, we assume the target transaction appears in every node’s view at time 𝜏. We also assume all honest nodes adopt the 𝑘-confirmation commit rule with the same 𝑘. Our goal is to obtain tight bounds on the probability that the adversary violates the safety of the target transaction.
= 𝑖 (the Genesis
Table 1 illustrates frequently used notations in this paper.
MAIN RESULTS
THEOREM 1. Given the confirmation depth 𝑘 as a natural num- ber, the delay bound Δ ≥ 0, the total mining rate 𝜆 > 0, and the fraction of honest mining power 𝜌 ∈ (0, 1], as long as
a target transaction’s safety can be violated with probability no target transaction’s safety can be violated with probability no greater
greater than
2+2 (4𝑝(1−𝑝))𝑘 (2) 1−𝑝
(4𝑝(1−𝑝))𝑘 =𝑒−2𝑘𝑑(12 ∥𝑝) (4) where𝑑(𝑝∥𝑞) =𝑝log𝑝 +(1−𝑝)log1−𝑝 denotestherelative
entropy between the Bernoulli(𝑝) and the Bernoulli(𝑞) distri- butions. As we shall see, the safety violation event is tied in some ways to the event that 𝑘 or more out of 2𝑘 independent Bernoulli trials are successful. For large 𝑘, the probability of this event decays exponentially in 𝑘 , where the exponent takes the form of a relative entropy, as is expected from the per- spective of large deviations. We emphasize that the bounds in Theorem 1 apply to all adversarial mining strategies and all
The proofs of these bounds are relegated to Sections 4–6. The exponential bounds in Theorem 1 can be thought of as the large deviations approximations of those in Theorem 2. As we shall see in Section 7, the bounds in Theorem 2 are numerically closer than the bounds in Theorem 1.
4 THE PRIVATE-MINING ATTACK IS CONDITIONALLY OPTIMAL
Let us introduce the simple private-mining attack. Its general structure was mentioned explicitly in [15] and even earlier works.
DEFINITION 2 (PRIVATE-MINING ATTACK AGAINST A TAR- GET TRANSACTION 𝑡𝑥). Starting from time 0, every adversarial block extends a longest blockchain that does not contain 𝑡𝑥. The propagation of every honest block is maximally delayed (i.e., by Δ). All adversarial blocks are kept private until the the adversary can violate the safety of 𝑡𝑥 by publishing all blocks.
Throughout this section, we assume the following simple condition on block heights is always upheld:
CONDITION 3. All honest blocks are on different heights. Also, honest blocks mined after time 𝜏 (when the target transaction ap- pears) are higher than honest blocks mined by time 𝜏 .
Condition 3 always holds if the delay bound Δ = 0. With Δ > 0, honest nodes may mine multiple blocks on the same height. But Condition 3 can be upheld by keeping no more than one honest block on each height. This changes the mining statistics and we relegate this discussion to Section 5, where we use this technique along with a reduction argument to bound the safety violation probability. In this section, we will prove that under Condition 3, the private-mining attack is one best attack in the following sense:
THEOREM 3. Under Condition 3, if any attack succeeds in vio- lating the target transaction’s safety, then the private-mining attack also succeeds in violating the target transaction’s safety.
Theorem 3 holds for any given honest and adversarial block mining times; in other words, as long as Condition 3 holds,
choices of the confirmation depth.
We also provide another pair of upper and lower bounds
that are tighter than the bounds in Theorem 1. The second set of bounds take somewhat more complicated form as fi- nite series sums, but are still very easy to evaluate using the probability mass function (pmf) and cumulative distribution function (cdf) of the binomial and geometric distributions. Specifically, we use the following variant of the geometric distributionwithparameter𝑝 =1−𝑞 > 12.For𝑖 =1,2,…,its pmf is expressed as
𝑞𝑖−1 𝑞 1−
and its complementary cdf is expressed as
𝐹2(𝑗;𝑛,𝑞) = ∑︁ 𝑃2(𝑙;𝑛,𝑞). 𝑙=𝑗+1
(6) We also denote the pmf of the binomial distribution with
parameters (𝑛,𝑞) as 𝑃2(𝑗;𝑛,𝑞) =
𝑞𝑗(1−𝑞)𝑛−𝑗 and the corresponding complementary cdf as
THEOREM 2. Given the confirmation depth 𝑘 as a natural num- ber, the delay bound Δ ≥ 0, the total mining rate 𝜆 > 0, and the frac- tionofhonestminingpower𝜌 ∈ (0,1],aslongas𝑝 =𝜌𝑒−𝜆Δ > 12,a
𝑃1(𝑖;𝑝)· 𝐹2(𝑘−𝑖;2𝑘+1−𝑖,1−𝑝) +∑︁𝑃2(𝑗;2𝑘 +1−𝑖,1−𝑝) ·𝐹1(2𝑘 +1−2𝑖 −2𝑗;𝑝)
regardless of the adversary’s attack strategy.
Conversely, there exists an attack that violates the target transac-
tion’s safety with probability at least
√ (4𝜌(1−𝜌))𝑘.
regardless of the adversary’s attack strategy.
Conversely, there exists an attack that violates the target transac-
tion’s safety with probability at least
Interestingly, both the upper bound (2) and the lower bound (3) can be expressed in the exponential form using a simple equality:
𝑃1(𝑖;𝜌)· 𝐹2(𝑘−𝑖;2𝑘+1−𝑖,1−𝜌)
𝑖=1 +∑︁𝑃2(𝑗;2𝑘+1−𝑖,1−𝜌)·𝐹1(2𝑘+2−2𝑖−2𝑗;𝜌) . (10)
the private-mining attack is a best attack for every sample path, regardless of statistics. It was claimed in [2, Appendix F] that the private-mining attack is optimal in violating the safety of a predetermined target block in the special case of Δ = 0, but the proof therein does not apply to the case when the target block is mined by an adversary. Thus, the optimality of the private-mining attack has not been fully established thus far even in the case of Δ = 0.
Before proving the theorem, we establish some additional terminology and simple facts. The private-mining attack con- sists of two stages. In the first stage, between time 0 to 𝜏, the adversary tries to build a “lead”, formally defined as follows:
DEFINITION 4 (LEAD). The lead (of the adversary) at time 𝑡 is the height of the highest block mined by time 𝑡 minus the height of the highest honest block mined by 𝑡 .
By definition, the lead is never negative. In the private- mining attack up to time 𝜏, if a highest (private) adversarial block is higher than any honest block (the lead is positive), the adversary mines on this highest adversarial block to try to increase the lead; otherwise, the lead is zero, and the adversary mines on a highest honest block to try to obtain a positive lead. We can show that this strategy maximizes the lead.
LEMMA 5. Under condition 3, the private-mining attack maxi- mizes the lead at all times up to 𝜏 .
PROOF. Let 𝑙𝑡 denote the lead at time 𝑡. The lead may only change upon block arrivals. Upon the mining of every adver- sarial block, the lead advances by at most 1. Upon the mining of every honest block, the lead decreases by at least 1 unless it stays 0. Under the private-mining attack up to 𝜏, the lead advances by exactly 1 upon the mining of every adversarial block; the lead decreases by exactly 1 unless it stays 0 upon the mining of every honest block. Hence, the private-mining attack achieves the maximum lead at all times up to 𝜏 . □
The second stage of the private-mining attack starts at time 𝜏. Honest nodes will include 𝑡𝑥 in the next block on the honest chain. The adversary tries to build a private chain that does not contain the target transaction 𝑡𝑥. If there ever comes a time after an honest node commits the target transaction, that the adversary’s private chain is as long as the public chain, then the adversary publishes its private chain and the attack succeeds in violating the safety of 𝑡𝑥. If such an instance never occurs, then the private-mining attack on 𝑡𝑥 fails.
For convenience, we define the following notions:
DEFINITION 6 (PUBLIC). A blockchain is public at time 𝑡 if it is included in all honest nodes’ views at time 𝑡. We say block 𝑏 is public if and only if blockchain 𝑏 is public.
DEFINITION 7 (CREDIBLE). A blockchain is credible at time 𝑡 if it is no shorter than any public blockchain at time 𝑡 .
Equivalently, a credible blockchain at time 𝑡 must be no shorter than at least one honest node’s longest blockchain at time 𝑡 . Under the 𝑘 -confirmation rule, a credible blockchain can be used to convince at least one honest node to commit blocks that are 𝑘 deep in this blockchain. Furthermore, an
Figure 1: Illustrations of blockchains 𝑐 and 𝑑. Illustrations ofthetwocasesintheproofofLemma9:h𝑎 ≥h𝑏 −1(left) and h𝑎 < h𝑏 − 1 (right).
honest node attempts to extend only credible blockchains. A block mined by an honest node must be credible at its mining time; it then loses its credibility at a later time, and cannot regain credibility afterward.
We are now ready to prove Theorem 3.
PROOF OF THEOREM 3. Let us first consider the hypothet- ical attack that violates the safety of the target transaction 𝑡𝑥. Let block 𝑐 and 𝑑 be a pair of blocks that minimize h+ = max(h𝑐,h𝑑) and satisfy the following conditions (see Figure 1 for illustrations):
(1) Blockchain 𝑐 is credible at time 𝑡𝑐 , contains the target transaction in a block 𝑏, and has height h𝑐 ≥ h𝑏 + 𝑘 − 1, and
(2) Blockchain 𝑑 is credible at time 𝑡𝑑 , has height h𝑑 ≥ h𝑏 + 𝑘 − 1, does not contain block 𝑏, and does not contain the target
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com