Foundations of Distributed Consensus and Blockchains
(Preliminary Draft)
Copyright By PowCoder代写 加微信 powcoder
Dedicated to the memory of my beloved mother, Honghua Ding (1952-2017), the kindest and most talented person I’ve known.
献给我最爱的母亲丁虹华 (1952-2017)
This is a preliminary (read: still somewhat rough) draft. I will be continually updating it as I teach this course in the next few years. Please always check back for the latest version.
Acknowledgements: I would like to thank my student who first got me interested in distributed consensus about five years ago. I am indebted to my colleague , who, since I joined Cornell, blocked out time from his busy life to discuss consensus with me, and who also suggested to write this textbook. Thanks especially to , my best friend and collaborator, for discussing distributed consensus, research, life, universe, and everything with me, throughout the past almost two decades, and for always understanding that I meant “left” when I said “right”.
Many people have provided me valuable feedback on the first draft of the textbook, including , , , Qixing Huang, , , , , , and . I am still working on addressing some of this feedback. A few of the chapters benefited from scribe notes from the students in my graduate-level course “CS6432 Distributed Consensus and Blockchains”. Last but not the least, many thanks to , , , , and for their moral support, help, and/or for discussions about distributed consensus.
This book is in part supported by an NSF grant under the number CNS-1561209.
If you have any comments or feedback about the book or exercises, please do not hesitate to email me!
Elaine (Runting) Shi, Summer, 2020
1 Distributed Consensus: from Aircraft Control to Cryptocur- rencies 1
2 Preliminaries 3
2.1 Negligible Function and Security Parameter . . . . . . . . . . 3
2.2 CollisionResistantHashFunctions …………… 4
2.3 RandomOraclesandProof-of-Work ………….. 5
2.4 DigitalSignatures …………………… 6
2.5 ChernoffBound ̧ …………………… 7
3 Byzantine Broadcast and the Dolev-Strong Protocol 9
3.1 Introduction………………………. 9
3.1.1 TheByzantineGenerals’Problem . . . . . . . . . . . 9
3.1.2 AModernVariant ……………….. 10
3.1.3 Analogy to Reliable Distributed Systems . . . . . . . . 10
3.2 ProblemDefinition…………………… 11 3.2.1 SynchronousNetwork ……………… 12 3.2.2 DefinitionofByzantineBroadcast . . . . . . . . . . . 12
3.3 ANa ̈ıve(Flawed)Protocol ………………. 13
3.4 TheDolev-StrongProtocol ………………. 14 3.4.1 Intuition…………………….. 15 3.4.2 Analysis…………………….. 16 3.4.3 FurtherDiscussions ………………. 17
3.5 TheMuddyChildrenPuzzle………………. 17
3.6 AdditionalExercises ………………….. 18
4 Byzantine Broadcast without Digital Signatures (Lower Bound) 21
4.1 Impossibility of Consensus with 1/3 Corruptions without Dig- italSignatures …………………….. 23
8 CONTENTS 4.2 ProvingtheLowerBound ……………….. 24
4.3 AdditionalExercises ………………….. 25
5 Byzantine Broadcast without Digital Signatures (Upper Bound) 27
5.1 Protocol………………………… 27 5.2 Analysis………………………… 29 5.3 AdditionalExercises ………………….. 31
6 Blockchain and State Machine Replication 33
6.1 ModelingNetworkDelayMoreGenerally . . . . . . . . . . . 33
6.2 DefiningaBlockchainProtocol …………….. 34
6.3 Construction of a Blockchain Protocol from Byzantine Broadcast 36
6.4 Discussions ………………………. 38
7 A Simple Blockchain Protocol — Streamlet 39
7.1 TheStreamletProtocol ………………… 40 7.1.1 EpochandLeaderRotation…………… 40 7.1.2 BlocksandBlockchain……………… 40 7.1.3 VotesandNotarization …………….. 41 7.1.4 Protocol…………………….. 41
7.2 Consistency………………………. 43
7.3 Liveness………………………… 45
7.4 The Partial Synchronous Model and Choosing the Epoch Length 46
7.5 HistoricalAnecdotes ………………….. 47
7.6 AdditionalExercises ………………….. 48
8 Lower Bound for Partial Synchrony 49
8.1 ProblemDefinition…………………… 49
8.2 Impossibility of Partial Synchronous Consensus under n/3
Corruptions………………………. 51
8.3 AdditionalExercises ………………….. 53
9 Round Complexity of Deterministic Consensus ̧ 55
9.1 WeaklyValidByzantineAgreement. . . . . . . . . . . . . . . 55
9.2 ProvingtheLowerBoundforf=2…………… 56
9.2.1 OverviewoftheProof ……………… 56
9.2.2 SequenceofExecutionsforf=2 . . . . . . . . . . . . 58
9.3 Extending the Argument for General Choices of f . . . . . . 60
CONTENTS 9
10 Round Complexity of Randomized Consensus ̧ 65 10.1 RoundComplexityofRandomizedBB . . . . . . . . . . . . . 65 10.2SurveyofRecentResults………………… 67
11 Communication Complexity of Consensus ̧ 69 11.1 Communication Lower Bound for Deterministic Consensus . . 70 11.2 Communication-Efficient Randomized Consensus . . . . . . . 72 11.3SurveyofRecentResults………………… 74
12 Asynchronous Consensus: The FLP Impossibility 77
12.1 Definitions: Asynchronous Consensus and Execution Model . 78 12.2 Impossibility of Asynchronous, Deterministic Consensus . . . 78 12.3ProvingtheFLPImpossibility …………….. 78
12.3.1 Terminology ………………….. 79 12.3.2 ProofRoadmap…………………. 79
Selfish Mining Attack and Incentive Compatibility
. . 108 . . 110
12.3.3 Existence of a Bivalent Initial Configuration . . 12.3.4 One Bivalent Configuration Leads to Another .
…. 80 …. 80
13 A Randomized Asynchronous Consensus Protocol ̧ 13.1Assumption:ACommonCoinOracle …………. 85 13.2 RandomizedAsynchronousConsensus . . . . . . . . . . . . . 86 13.3Consistency………………………. 88 13.4Liveness………………………… 89 13.5Termination………………………. 91 13.6AdditionalExercises ………………….. 91
14 Bitcoin and Nakamoto’s Blockchain Protocol 93
14.1 Nakamoto’sIngeniousIdeainaNutshell . . . . . . . . . . . . 94
14.2 Nakamoto’s Blockchain: Formal Description . . . . . . . . . . 96
14.3 ChoosingtheMiningDifficultyParameter . . . . . . . . . . . 99
14.4 PropertiesofNakamoto’sBlockchain . . . . . . . . . . . . . . 101
14.4.1 ChainGrowthLowerBound……………102 14.4.2 ChainQuality ………………….103 14.4.3 Consistency……………………104 14.4.4 Liveness……………………..105
15.1 The Selfish Mining Attack . . . . . . . . . . . . . . . . . .
15.2 Fruitchain: an Incentive-Compatible Blockchain ̧ . . . .
10 CONTENTS
16 A Simple, Deterministic Longest-Chain-Style Protocol 113
16.1 Deterministic Longest-Chain-Style Consensus Protocol . . . . 114 16.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 16.3AdditionalExercises …………………..117
17 Analysis of Nakamoto’s Blockchain ̧ 119 17.1 Ideal-World Protocol . . . . . . . . . . . . . . . . . . . . . . . 119 17.2Notations ………………………..121 17.3ConvergenceOpportunities ……………….121
17.4 Chain Growth Lower Bound . . 17.5 Chain Quality . . . . . . . . . . 17.6 Consistency . . . . . . . . . . .
18 Proof of Stake (Brief Overview)
. . . . . . . . . . . . . . . . . 124 . . . . . . . . . . . . . . . . . 125 . . . . . . . . . . . . . . . . . 127
Distributed Consensus: from Aircraft Control to
Cryptocurrencies
Back in the 1970s, it became clear that computers were going to be used in aircraft control. Since this was a mission-critical system, it was important to replicate it on multiple machines. But how do we make sure that the multiple machines share a consistent view and make consistent decision?
To understand this problem better, NASA sponsored the Software Imple- mented Fault Tolerance (SIFT) project [WLG+89], whose goal was to build a resilient aircraft control system that tolerated faults of its components. The famous work of Lamport et al. [LSP82] which introduced the well-known
“Byzantine Generals” problem, came out of this project. This work laid the foundation of distributed consensus. Since then, distributed consensus has come a long way and has been deployed in many application settings.
In the past couple of decades, companies like Google and Facebook have adopted distributed consensus as part of their computing infrastructure, e.g., to replicate mission-critical services such as Google Wallet and Facebook Credit.
Starting in 2009, Bitcoin and various subsequent cryptocurrencies came around and became popular. The cryptocurrencies achieved a new break- through in distributed consensus, since they showed, for the first time, that consensus is viable in a decentralized, permissionless environment where anyone is allowed to participate.
In this course, you will learn the mathematical foundations of distributed consensus as well as how to construct consensus protocols and prove them
secure. We will motivate distributed consensus with a modern narrative, and yet we will cover the classical theoretical foundations of consensus. We will cover both classical, permissioned consensus protocols, as well as modern, permissionless consensus protocols such as Bitcoin.
A note on the terminology. Throughout this course, we will formally define several consensus abstractions, including notably, Byzantine Broadcast, and blockchains (i.e., state machine replication). On the other hand, we use the term “consensus” in an informal and generic manner to refer to any related abstraction that captures the act of reaching agreement in a distributed system.
Although multiple fault models have been studied in the past (e.g., fail- stop, crash, omission, and Byzantine faults), in this course, we focus on the hardest case, i.e., Byzantine faults. A node or system component that exhibits Byzantine fault can behave arbitrarily maliciously and need not follow the prescribed consensus protocol. Multiple Byzantine nodes can collude with each other and coordinate in their attack. Unless otherwise noted, whenever we say a node/player is “corrupt” or “malicious”, we specifically mean Byzantine faults.
Unless otherwise noted, we assume that corruption is static, i.e., the adversary decides which set of nodes to corrupt a-priori before the protocol execution starts.
The consensus protocols we will cover sometimes make use of crypto- graphic primitives such as digital signatures or collision-resistant hashing.
Intended audience. Chapters and sections marked with “ ̧” are meant as more advanced contents: they are recommended to be taught in a graduate- level course or in a special-topics course on distributed consensus. Other chapters can be taught at the senior undergraduate level assuming a general background of discrete mathematics.
Chapter 2 Preliminaries
We briefly review some simple cryptographic primitives and probability tools that will become useful in constructing and reasoning about consensus protocols. We will only cover the basic concepts and not go into detailed constructions and proofs; and the reader could use this chapter for reference purposes. For a more extensive course on cryptography, we refer the reader to several other textbooks [BS,PS,KL07].
Throughout the course, we will use {0, 1}∗ to mean a string of arbitrary length; we use {0, 1}l to mean a string of l bits; and we use [n] to mean {1,2,…,n}.
2.1 Negligible Function and Security Parameter
In cryptographic schemes such as encryption and digital signatures, we often need to choose a secret key of length λ. The longer the key length λ, the more secure the scheme is. Ideally, we want the following desired property: as we increase the key length a little, the probability that a polynomial-time adversary can break the cryptographic scheme drops very sharply. This way, we can get sufficient security with key lengths that are not too long.
We typically use a so-called negligible function to capture such a sharply dropping function. We say that negl(λ) is a negligible function iff for any fixed polynomial function p(λ), there exists λ0 such that for any λ > λ0, negl(λ) < 1/p(λ). In other words, a negligible function is one that drops off faster than any inverse-polynomial function. For example, exp(− log2 λ), λ− log λ, and 2−λ are all negligible functions. If negl(λ) is a negligible function and poly(λ) is a polynomial function in λ, then negl(λ)·poly(λ) is a negligible function in λ.
The parameter λ is often said to be a security parameter. Throughout this textbook, we will use λ to denote the security parameter. For example, λ may refer to the length of a secret key, or the length of a hash function’s outcome depending on the context. We will assume that any adversary trying to attack our consensus protocols (possibly controlling a subset of corrupt players) is restricted to running in time that is polynomial in λ.
2.2 Collision Resistant Hash Functions
Later in our course, we will construct blockchain protocols where a dis- tributed set of nodes jointly maintain an ever-growing, linearly-ordered log of transactions. It will be convenient if we can use a short digest to “uniquely” identify a blockchain (i.e., a linearly ordered log) or any prefix of it. For this purpose, we can take a so-called hash function and hash the blockchain to a short digest. For any function that maps a long string to a short digest, obviously a “collision” must exist, i.e., there must exist two different inputs that map to the same digest. However, if a hash function is cryptographically secure, it is computationally infeasible for any polynomial-time adversary to find such collisions. This way, the short “hash” cryptographically binds to the blockchain. Below, we define a hash function more formally which essentially conveys the above intuition.
Given a hash function h : {0, 1}∗ → {0, 1}λ, a collision is a pair (x, x′) such that x ̸= x′ but h(x) = h(x′). A collision-resistant hash family H is a family of hash functions, such that if we draw a hash function from the family at random, it is hard for a polynomial-time adversary to find a collision.
Formally, let H = {hs : {0, 1}∗ → {0, 1}λ}s∈{0,1}λ be a family of hash functions indexed by s ∈ {0, 1}λ. We say that H is a collision-resistant hash family, iff:
• hs can be computed in polynomial time;
• foranyadversaryArunningintimepolynomialinλ,thereisanegligible
function negl(·), such that for every λ, Prs←${0,1}λ:A(s)outputsacollisionforh ≤negl(λ)
where ←$ means “randomly sample”.
Note that since the domain is larger than the range, a collision must exist by the pigeon-hole principle. However, the point here is that a compu- tationally bounded adversary cannot find collisions except with negligible probability.
In practice, we often use a single hash function, such as SHA256 [sha], as a collision-resistant hash function. SHA256 is a function that hashes long messages into 256-bit digests. It is commonly believed that finding collisions for SHA256 is difficult.
2.3 Random Oracles and Proof-of-Work
In practice, hash functions such as SHA256 are believed to give random- looking outcome for each distinct query. For this reason, we often pretend that a cryptographic hash function (e.g., SHA256) is an idealized object called a random oracle.
A random oracle H : {0, 1}∗ → {0, 1}λ captures a function that is chosen completely at random. Whenever we query the function H with a fresh input x ∈ {0, 1}∗ that has not been queried before, H generates a random answer from {0, 1}λ and returns it. Whenever a repeat query x is made, H simply returns the same answer it gave before for the input x.
We sometimes also use random oracles whose output range is not exactly {0, 1}λ for some λ. For example, we sometimes use H : {0, 1}∗ → [n] whose output range is [n].
Remark 1. A single deterministic function like SHA256 in fact cannot realize a random oracle; nonetheless, we often pretend that it’s a random oracle as a heuristic. If a cryptographic scheme employs random oracles and is proven secure assuming the existence of random oracles, we often replace the random oracle with a concrete hash function in practice and hope that it is still secure. This heuristic has been adopted in various contexts, and we have some empirical evidence why this could be a good approach (if used carefully).
We often use cryptographic hash functions such as SHA256 as a Proof- of-Work (PoW) random oracle. In this case, not only are we assuming that every fresh invocation of the function returns a random answer, we are also assuming that every invocation consumes some computational resources, and that there is no obvious short-cut one can exploit to speed up the computation. If one would like to learn the outcome of the function at many places, there should be no better way than brute-force evaluating the function at all of these inputs.
2.4 Digital Signatures
In our consensus protocols later, often times, when Alice says “I propose that we agree on the bit 0”, Bob might later on want to convince Charles that Alice indeed said this. If Bob is malicious, however, he could potentially alter Alice’s message and try to convince Charles that Alice suggested to agree on 1. Digital signature schemes can help us here. Alice can cryptographically sign the message she sends, producing a so-called “digital signature”. The digital signature can ensure to a recipient (e.g., Charles), that the message indeed was signed by Alice, and that the message was not altered by Bob.
Formally, a digital signature scheme consists of three algorithms, Gen, Sign, and Vf:
• pk, sk ← Gen(1λ): Gen takes in the security parameter λ and generates a public- and secret-key pair denoted pk and sk respectively.
• σ ← Sign(sk, m): the signing algorithm Sign takes in a secret key sk, a message m ∈ {0, 1}∗, and outputs a signature σ.
• {0, 1} ← Vf(pk, m, σ): the verification algorithm takes in the public key pk, a message m, a signature σ, and outputs either 1 indicating
“accept” or 0 indicating “reject”.
A digital signature scheme (Gen,Sign,Vf) is said to be correct if for every pk, sk pair in the support of the Gen algorithm, for any m ∈ {0, 1}∗, Vf(pk, m, Sign(sk, m)) = 1.
A digital signature scheme is secure, iff, roughly speaking, no polynomial- time adversary can forge signatures without the secret key, on any fresh messages whose signatures it has not seen. More formally, a digital signature scheme (Gen,Sign,Vf) is said to be secure, iff for every polynomial-time A, there exists a negligible function negl(·), such that for every λ,
$ λ Sign(sk,·) A did not query m
Pr pk,sk←Gen(1 ),(m,σ) ← A (pk) : ∧ Vf(pk,m,σ) = 1 ≤ negl(λ)
In the above, the notation ASign(sk,·)(pk) means that A, who obtains the public key pk, can interact with a signing oracle which uses the secret key sk to sign any message that is queried by A, and gives the signature to A. In other words, even if A can obtain signatures on messages of its choice, it still cannot forge a signature on any fresh, unqueried message.
Ideal signatures. In our course, we often assume the ideal signature model where the adversary simply cannot forge signatures. Formally, this means that we often argue our consensus protocols secure, ignoring the negligible probability with which the adversary can break the signature scheme.
2.5 Chernoff Bound ̧
The Chernoff bound is often used to prove that the sum of independent random variables is highly concentrated around its mean. In this course, we will use the following version of Chernoff bound.
Theorem 1 (Chernoff bound). Let X := ni=1 Xi where each Xi = 1 with probability pi and Xi = 0 with probability 1 − pi. Further, all Xi’s are independent. Let μ := ni=1 pi. Then, we have t
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com