The Nakamoto Consensus: Model and Preliminary Analysis
DONGNING GUO
January 22, 2023
1 INTRODUCTION
Copyright By PowCoder代写 加微信 powcoder
The goal of a blockchain system is to forge consensus between participants about transactions that arrive over time. Typically the specific goal is to decide upon the validity of the transactions and establish an order of those transactions as a running consensus. The permissionless distributed consensus problem is challenging because it cannot be built on trust between individual participants. Instead, the participants trust that a majority (or maybe a supermajority) of participants follow the default protocol, but no more than that.
With cryptography, it has become easy to ensure that transaction signatures are not forged. It remains challenging to forge consensus on the ordering of two contradicting transactions signed by the same owner. In the Bitcoin system, this challenge takes the form of double spending. That is, two or more transactions consuming the same UTXO are proposed, possibly to different set of miners at different times, in order to confuse the miners so that they fail to reach and maintain consensus with some probability. To have confidence in the system, the probability of this happening must be negligible.
The solution we focus on here is the Nakamoto consensus, by which we mean mining by proof- of-work and according to the longest-chain protocol. We introduce a mathematical model for blockchains and mining; we establish probabilistic safety and liveness guarantees for the Nakamoto consensus as a function of the honest and adversarial mining rates and the desired confirmation latency. We shall see that the Nakamoto consensus is a very strong protocol with great properties (we do not claim that the Nakamoto consensus is necessarily a best protocol).
2.1 Review of the Nakamoto Consensus
The Nakamoto consensus centers around the proof-of-work mechanism and the “longest-chain- win” rule. The gist of the protocol can be described succinctly: At any point in time, every honest miner attempts to mine a new block that extends the longest blockchain in that miner’s view;
Author’s address: ,
once a new block is mined or received, the honest miner publishes or forwards it through the peer-to-peer mining network.
If an honest miner mines a block at time t , the block must extend the miner’s longest blockchain immediately before t. The honest miner will also immediately publish the block through a peer- to-peer network. Under the ∆-synchrony model, where ∆ is a known upper bound on block propagation delays, all other miners will receive the block by time t + ∆. Note that ∆ upper bounds the end-to-end delay between every pair of miners regardless of the number of hops between them.
In contrast, if an adversarial miner mines a block at time t , the block may extend any blockchain mined by time t and may be presented to individual honest miners at any time after t .
2.2 Formal Model for the Nakamoto Consensus
In this subsection we present a lean model for blockchain and mining processes which capture the essence of the Nakamoto consensus for our purposes.
Definition 1 (Block and mining). A genesis block, also referred to as block 0, is mined at time 0. Subsequent blocks are referred to as block 1, block 2, and so on, in the order they are mined. Let tb denote the time when block b is mined.
A block in a practical blockchain system is a data structure that contains a unique identifier, a reference to its parent block, and some application-level data. The block number and mining time are tools in our analysis and are not necessarily included in the block. The probability that two blocks are mined at the same time is zero in the continuous-time model. Nevertheless, for mathematical rigor, we can break ties in some deterministic manner even if they occur.
Definition 2 (Blockchain and height). Every block has a unique parent block that is mined strictlybeforeit.Weusefb ∈{0,1,…,b−1}todenoteblockb’sparentblocknumber.Thesequence b0,b1,…,bndefinesablockchainifb0=0andfbi =bi−1fori=1,…,n.Itisalsoreferredtoas blockchain bn since bn uniquely identifies it. The height of both block bi and blockchain bi is said to bei.
Throughout this paper, “by time t ” means “at some time s ∈ (0, t ]”.
Definition 3 (A miner’s view). A miner’s view at time t is a subset of all transactions and blocks mined by time t . A miner’s view can only increase over time. A block is in its own miner’s view from the time it is mined.
Definition 4 (A miner’s longest blockchain). A blockchain is in a miner’s view at time t if
all blocks of the blockchain are in the miner’s view at time t . A miner’s longest blockchain at time t is 2
a blockchain with the maximum height in the miner’s view at time t. Ties are broken in an arbitrary manner.1
Definition 5 (Honest and adversarial miners). Each miner is either honest or adversarial. A block is said to be honest (resp. adversarial) if it is mined by an honest (resp. adversarial) miner. An honest block mined at time t must extend its miner’s longest blockchain immediately before t .
We assume all block propagation delays are upper bounded by ∆ units of time in the following sense.
Definition 6 (Block propagation delay bound ∆). If a block is in any honest miner’s view by time t, then it is in all miners’ views by time t + ∆.
The adversary may use an arbitrary strategy subject to (only) the preceding constraints. Specifi- cally, an adversary can choose to extend any existing blockchain. Once an adversarial block is mined, its miner can determine when it enters each individual honest miner’s view subject to the delay bound ∆ (Definition 6).
This treatment cannot be fully rigorous without a well-defined probability space. At first it appears to be intricate to fully described blockchains and an all-encompassing probability space. For our purposes it is sufficient (and most convenient) to include no more than the mining times of the honest and adversarial blocks in the probability space. We show that barring a certain
“bad event” in this probability space, blockchain consistency is guaranteed under all adversarial strategies and network schedules (under ∆-synchrony). Thus, the adversary’s strategies and the network schedules do not have to be included in the probability space.
Definition 7 (Mining processes). Let Ht (resp. At ) denote the total number of honest (resp. adversarial) blocks mined during (0, t ]. We assume (Ht , t ≥ 0) and (At , t ≥ 0) to be independent homogeneous Poisson point processes with rate h and a, respectively.
In lieu of specifying the number of honest and adversarial miners, this model is only concerned with their respective aggregate (constant) mining rates. This is in the same spirit as the permission- less nature of the Nakamoto consensus. In fact the model is not concerned with whether mining is centralized or decentralized. We caution that the preceding model does not consider the issues of incentives; the model simply stipulates the honest and adversarial mining powers as given and fixed.
Definition 8 (Public). A blockchain is public at time t if it is included in all honest nodes’ views at time t . We say block b is public if and only if blockchain b is public.
1The Bitcoin protocol favors the earliest to enter the view. How ties are broken has essentially no impact on the security–latency trade-off.
Definition 9 (Credible). A blockchain is credible at time t if it is no shorter than any public blockchain at time t .
There can be multiple t -credible blockchains, which may or may not be of the same height. Once a block is published, it takes no more than the time of ∆ to propagate to all miners. Hence at time t , an honest miner must have seen all blockchains published by t − ∆. It follows that every honest miner’s longest blockchain must be t -credible. It is unnecessary to keep tabs of individual miner’s views as far as the fundamental security is concerned. Focusing on credible blockchains allows us to develop a simple rigorous proof with minimal notation.
The longest-chain rule does not specify how or when a block is regarded as committed by a miner. The best known rule for committing a block is as soon as a certain number of additional blocks in a credible blockchain confirm it. An alternative is to commit a block if it is seen in a credible blockchain after a sufficient amount of time elapses since it was mined or published.
If we use confirmation by depth, we define confirmation and safety violation as follows: Definition 10 (Confirmation by depth of k ). If some t -credible blockchain of height hb + k − 1
or higher includes block b, then block b is said to be confirmed by depth of k at time t.
Definition 11 (Safety violation or a target transaction). A target transaction’s safety is violated if a block containing 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.
We would like safety violations to be extremely unlikely even if the adversary strives to make this happen. The security of the blockchain system rests to a large extent on this, so that the adversary finds it unprofitable to attempt to double spend, even with all its privileges not share by honest minors.
Definition 12 (Privte-mining attack against a target transaction tx). Starting from time 0, every adversarial block extends a longest blockchain that does not contain tx. 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 tx by making all blocks public.
3 A SIMPLE CASE: HEIGHT-1 SAFETY WITH ZERO DELAY
In this section we carry out an analysis of a special case under the following assumptions:
(1) Block propagations take zero delay (∆ = 0). (2) Only the safety at height-1 is of concern. (3) Confirmation is by depth of k.
When ∆ = 0, a t -credible blockchain is a longest blockchain at time t . 4
Lemma 1. If all block propagation delays are zero, then every honest block mined is strictly higher than all honest blocks mined before it.
In particular, as soon as a block enters one honest miner’s view, it enters all honest miners’ views.
Once we can guarantee the safety of height-1, our analysis can be generalized to the case of height-2 and so on.
3.1 The Private-Mining Attack Is the Strongest Attack
Under the private-mining attack, an honest height-1 block gets confirmed after long enough time. We shall show that, as long as the honest mining rate is higher than the adversarial mining rate, the probability of a safety violation vanishes exponentially with k.
Before that, let us first establish an important observation that the private-mining attack is the strongest attack the adversary can pull off under the assumptions in this section.
Theorem 2. For every realization of the mining processes (Ht , t ≥ 0) and (At , t ≥ 0), if there exists an attack that violates the safety of height-1, then the private-mining attack also violates the safety of height-1.
Proof: Suppose a certain attack violates the safety of height-1. By definition, at least two public longest blockchains (possibly at different times) of height k or higher do not share the same height-1 block. Let t be the first time this occurs, i.e., a longest blockchain b is published to confirm a second height-1 block. At t , among all public blockchains that include the first confirmed height-1 block, let blockchain д denote a longest one of them. Since blockchain b is a longest blockchain, we must have
hb ≥hд. (1)
If hb > hд , then the last hb − hд blocks in blockchain b are adversarial, otherwise an honest block c in blockchain b is higher than block д, so blockchain c confirms the second height-1 block sooner than blockchain b.
Recall Ht and At denote the number of honest and adversarial blocks mined by t. Blockchains д and b share no blocks except for the genesis block. To confirm two height-1 blocks requires
Ht +At ≥hд +hb (2) ≥ 2k. (3)
By Lemma 1, every longest blockchain at time t is no shorter than Ht . Hence
Ht ≤hд. (4) 5
By (2) and (4), we have
P(D > 0) ≤ E[esD]. (11)
E[esD] = E[esD |D > 0]P(D > 0) + E[esD |D < 0]P(D < 0) (12) ≥ E[1|D > 0]P(D > 0) (13) = P(D > 0). (14)
At ≥hд +hb −Ht (5) ≥ hb (6) ≥ hд (7) ≥ Ht (8)
where the last step is again due to (4). By (8) and (3), we have
2At ≥Ht +At (9)
≥ 2k, (10)
soAt ≥k.SinceAt ≥Ht,weconcludethatiftheadversaryminesasingleprivateblockchain, thereareenoughadversarialblockstoconfirmaheight-1blockattimet.IfHt
Lemma4. LetZbeanexponentialrandomvariablewithmean1/λ.Itsmomentgeneratingfunction is given by
E[esZ]= λ (15) λ−s
where the region of convergence is s ∈ (−∞, λ).
The integral converges if and only if s < λ, where the result is given by (15). □
Let Xi denote the difference between the mining times of the i-th honest block and the (i − 1)- st honest block. Then X1, X2, . . . are independent and identically distributed (i.i.d.) exponential random variables with mean 1/h. Let Yi denote the difference between the mining times of the i-thadversarialblockandthe(i−1)-stadversarialblock.ThenY1,Y2,... arei.i.d.exponential random variables with mean 1/a. Also, all the X and Y variables are mutually independent.
For given integer j > 0, let Ej denote the event that the j-th adversarial block is mined before the j-th honest block after the genesis block. With confirmation by depth of k, the safety of height-1 is violatedifEj occursforanyj=k,k+1,….Then
P(Ej)=P Xi >Yi (17)
i=1 i=1 j
=P (Xi−Yi)>0 . (18) i=1
We discuss two different cases, namely, a > h and a < h. 1)Inthecaseofa >h,
lim P(Ej) = 1. (19) j→∞
ThisisbecauseE[Xi−Yi]=1−1>0,sointhelimitofj→∞,j (Xi−Yi)>0occurswith ha i=1
probability 1. This implies that the private mining attack almost surely wins regardless of the confirmation depth. There is no security at all.
2) In the case of a < h, we have for every s > 0, j
P(Ej)=P (Xi−Yi)>0 (20) i=1
≤E exp[s(Xi−Yi)] (21)
e−λzeszdz. (16)
sX1 −sY1j
where (21) is due to Lemma 3. By Lemma 4, we need s < h and −s < a for both expectations to be finite, in which case
P(Ej)≤ h−sa+s . (23)
To seek the tightest bound, we select s that minimizes the product in (23). Recall that s > 0 and that s ∈ (−a, h). Since a < h, the optimal choice is s = (h − a)/2, at which point the derivative of the product with respect to s is equal to 0. Therefore,
P(Ej) ≤ cj (24) c= h · a (25)
h − h−a a + h−a 22
= 4ah . (26) (a + h)2
Putting it all together, the probability of safety violation for height-1 is upper bounded by an exponential function in k:
P∪∞ E≤P(E) (27)
as long as a < h. This upper bound is exponential in the confirmation depth k. On the other hand, if a > h, there is no security at all regardless of k.
(28) = (1 − c)−1ck (29)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com