Session 3B: Blockchain I CCS ’19, November 11–15, 2019, London, United Kingdom
Stanford University
University of Washington at Seattle
David University
Copyright By PowCoder代写 加微信 powcoder
Prism: Deconstructing the Blockchain to Approach Physical Limits
University of Illinois at Urbana-Champaign
Performance measures
The concept of a blockchain was invented by to maintain a distributed ledger. In addition to its security, important performance measures of a blockchain protocol are its transaction throughput and confirmation latency. In a decentralized setting, these measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propaga- tion delay. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest trans- actions proportional to the propagation delay D, with confirmation error probability exponentially small in the bandwidth-delay prod- uct CD; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing Nakamoto’s blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.
ACM Reference Format:
, , , , and . 2019. Prism: Deconstructing the Blockchain to Approach Physical Limits.
In 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS ’19), November 11–15, 2019, London, United Kingdom. ACM, , NY, USA, 18 pages. https://doi.org/10.1145/3319535.3363213
1 INTRODUCTION
In 2008, invented the concept of a blockchain, a mechanism to maintain a distributed ledger in a permissionless setting. Honest nodes mine blocks on top of each other by solving Proof-of-Work (PoW) cryptographic puzzles; by following a longest chain protocol, they can come to consensus on a transaction ledger that is difficult for an adversary to alter. Since then, many other blockchain protocols have been invented.
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
CCS ’19, November 11–15, 2019, London, United Kingdom
© 2019 Association for Computing Machinery. ACM ISBN 978-1-4503-6747-9/19/11. . . $15.00 https://doi.org/10.1145/3319535.3363213
The fundamental performance measures of a PoW blockchain pro- tocol are:
(1) the fraction β of hashing power the adversary can control with- out compromising system security, assuming the rest of the nodes follow protocol;
(2) thethroughputλ,numberoftransactionsconfirmedpersecond; (3) the confirmation latency, τ , in seconds, for a given probability ε that a confirmed transaction will be removed from the ledger
in the future.
For example, Bitcoin is secure against an adversary holding up to 50% of the total network hash power (β = 0.5), has throughput λ of a few transactions per seconds and confirmation latency of the order of tens of minutes to hours. There is a tradeoff between the confirmation latency and the confirmation error probability: the smaller the desired confirmation error probability, the longer the needed latency is in Bitcoin. For example, Nakamoto’s calculations [16] show that for β = 0.3, while it takes a latency of 6 blocks (on the average, 60 minutes) to achieve an error probability of 0.15, it takes a latency of 30 blocks (on the average, 300 minutes) to achieve an error probability of 10−4.
1.2 Physical limits
Bitcoin has strong security guarantees but its throughput and la- tency performance are poor. In the past decade, much effort has been expended to improve the performance in these metrics. But what are the fundamental bounds that limit the performance of any blockchain protocol?
Blockchains are protocols that run on a distributed set of nodes connected by a physical network. As such, their performance is limited by the attributes of the underlying network. The two most important attributes are C, the communication capacity of the net- work, and D, the speed-of-light propagation delay across the net- work. Propagation delay D is measured in seconds and the capacity C is measured in transactions per second. Nodes participating in a blockchain network need to communicate information with each other to reach consensus; the capacity C and the propagation de- lay D limit the rate and speed at which such information can be communicated. These parameters encapsulate the effects of both fundamental network properties (e.g., hardware, topology), as well as resources consumed by the network’s relaying mechanism, such
Session 3B: Blockchain I
CCS ’19, November 11–15, 2019, London, United Kingdom
Slope = 𝑂(D) 𝑂(𝐷
Slope = 𝑂 /0 1
𝑂(𝐶𝐷/𝐵-) Security parameter: log ()
Prism (order optimal) Bitcoin
as validity checking of transactions or blocks.
each transaction needs to be communicated at least once across the network, it holds that λ, the number of transactions which can be confirmed per second, is at most C, i.e.
λ < C. (1) One obvious constraint on the confirmation latency τ is that
τ > D. (2)
Another less obvious constraint on the confirmation latency comes from the network capacity and the reliability requirement ε. Indeed, if the confirmation latency is τ and the block size is Bv transactions, then at most C/Bv · τ mined blocks can be communicated across the network during the confirmation period for a given transaction. These mined blocks can be interpreted as confirmation votes for a particular transaction during this period; i.e. votes are communi- catedatrateC/Bv andCτ/Bv votesareaccumulatedoverduration τ. (The parameter Bv can be interpreted as the minimum block size to convey a vote.) On average, a fraction β < 0.5 of these blocks are adversarial, but due to the randomness in the mining process, there is a probability, exponentially small in Cτ /Bv , that there are more adversarial blocks than honest blocks; if this hap- pens, confirmation cannot be guaranteed. Hence, this probability is a lower bound on the achievable confirmation error probability, i.e. ε = exp(−O(Cτ/Bv)). Turning this equation around, we have the following lower bound on the latency for a given confirmation probability ε:
Assuming that
Figure 1: Confirmation latency vs. security parameter for Prism . The latency of Prism is independent of the security pa- rameter value up to order CD/Bv and increases very slowly after that (with slope Bv/C). For Bitcoin , latency increases much more rapidly with the security parameter, with slope proportional to D. (Since CD/Bv ≫ 1, this latter slope is much larger.)
1.3 Main contribution
The main contribution of this work is a new blockchain protocol,
Bv 1 τ=Ω C ·logε .
Comparing the two constraints, we see that if
CD 1 B ≫logε,
(1) Security: (Theorem 4.3) a total ordering of the transactions, with consistency and liveness guarantees.
(2) Throughput: (Theorem 4.4) a throughput
λ = 0.9(1 − β)C transactions per second. (4)
(3) Latency: (Theorem 4.8) confirmation of all honest transactions (without public double spends) with an expected latency of
E[τ] < max c1(β)D,c2(β) C log ε seconds, (5)
withconfirmationreliabilityatleast1−ε (Figure1).Here,c1(β) and c2(β) are constants depending only on β
Notice that the worst-case optimal throughput of any protocol with 1 − β fraction of hash power is (1 − β)C transactions/second, assuming each transaction needs to be communicated across the network. Hence, Prism’s throughput is near-optimal. At the same time, Prism achieves a confirmation latency for honest transactions matching the two physical limits (2) and (3). In particular, if the de- sired security parameter log ε1 ≪ CD/Bv , the confirmation latency is of the order of the propagation delay and independent of log 1/ε . Put another way, one can achieve latency close to the propagation delay with a confirmation error probability exponentially small in the bandwidth-delay product CD/Bv . Note that the latency is worst-case over all adversarial strategies but averaged over the randomness in the mining process.
To the best of our knowledge, no other existing PoW protocol has
guaranteed performance which can match that of Prism. Two novel
ideas which enable this performance are 1) a total decoupling of
transaction proposing, validation and confirmation functionalities
in the blockchain, allowing performance scaling; 2) the concept of
confirming a list of possible ledgers rather than a unique ledger,
enabling honest non-double-spend transactions to be confirmed
3 quickly .
2The powerful adversary will be precisely defined in the formal model.
3This idea was inspired by the concept of list decoding from information theory.
the latency is limited by the propagation delay; otherwise, it is limited by the confirmation reliability requirement. The quantity CD/Bv is analogous to the key notion of bandwidth-delay product in networking (see eg. [11]); it is the number of “in-flight" votes in the network.
To evaluate existing blockchain systems with respect to these limits, consider a global network with communication links of capacity 20 Mbits/second and speed-of-light propagation delay D of 1 second. If we take a vote block of size 100 bytes, then the bandwidth-delay product CD/Bv = 25000 is very large. Hence, the confirmation latency is limited by the propagation delay of 1 seconds, but not by the confirmation reliability requirement unless it is astronomically small. Real-world blockchains operate far from these physical network limits. Bitcoin, for example, has λ of the order of 10 transactions per second, τ of the order of minutes to hours, and is limited by the confirmation reliability requirement rather than the propagation delay. Ethereum has λ ≈ 15 transactions per second and τ ≈ 3 minutes to achieve an error probability of 0.04 for β = 0.3 [4].
1 We define confirmation formally in Section 2, but informally, we say a node ε -confirms a transaction if, upon successfully evaluating a confirmation rule under parameter ε, the transaction has a probability of at most ε of being reverted by any adversary.
Prism, which, in the face of any powerful adversary β < 0.5, can simultaneously achieve:
with power
Session 3B: Blockchain I
CCS ’19, November 11–15, 2019, London, United Kingdom
1.4 Performance of existing PoW protocols
High forking protocols. Increasing the mining rate in Bitcoin can decrease latency and improve throughput, however, this comes at the expense of decreased security [25]. Thus, unlike Prism, the throughput and latency of Bitcoin is security-limited rather than communication-limited. To increase the mining rate while maintain- ing security, one line of work (GHOST [25], Inclusive [14], Spectre [23], Phantom [24], Conflux [15]) in the literature has used more complex fork choice rules and added reference links to convert the blocktree into a directed acyclic graph (DAG). This allows blocks to be voted on by blocks that are not necessarily its descendants.
While GHOST remains secure at low mining rates[10], there is a balancing attack by the adversary [12, 17], which severely limits the security at high mining rates. Thus, like Bitcoin, the throughput of GHOST is security-limited. The other protocols Inclusive and Conflux that rely on GHOST inherit this drawback. While Spectre and Phantom improve latency and throughput, Spectre cannot pro- vide a total order on all transactions (required for smart contracts) and Phantom does not yet have a formal proof of security. Decoupled consensus. Protocols such as BitcoinNG [7] decou- ple transaction proposal and leader election (which are coupled together in Bitcoin). BitcoinNG elects a single leader to propose many transaction blocks till the next leader is elected by PoW. While this achieves high throughput, the latency cannot be reduced using this approach. Furthermore, BitcoinNG is vulnerable to bribery or DDoS attacks, whereby an adversary can corrupt a leader af- ter learning its identity (unlike Bitcoin). Subchains [22] and weak blocks [2, 26] both employ blocks with lower hash threshold (“weak blocks”) along with regular blocks in an attempt to scale through- put. However, since weak blocks are required to form a chain, it does not achieve the optimal throughput.
Hybrid blockchain-BFT consensus. Several protocols combine ideas from Byzantine fault tolerant (BFT) based consensus into a PoW setting [1, 13, 20, 21]. ByzCoin [13] and its predecessor Disc- Coin [6] attempt to address the latency shortcoming of BitcoinNG but is proven in a later paper [20] to be insecure when the ad- versarial fraction β > 0.25. Hybrid consensus uses a combination of proof-of-work based committee selection with Byzantine fault tolerance (BFT) consensus [20]. However, this protocol is secure only till β = 0.33. While the protocol latency is responsive, i.e., it decreases with network delay linearly, for a known network delay, it has similar non-optimal dependence on ε as Bitcoin.
A closely-related protocol called Thunderella [21] achieves very low latency under optimistic conditions, i.e., when the leader is hon- est and β < 0.25. However even when β is very small, a dishonest leader can keep delaying transactions to the Bitcoin latency (since such delaying behavior is detected by a slow PoW blockchain).
1.5 Our Approach
Increasing the mining rate is critical to improving the throughput and latency of blockchain protocols. The challenges facing the DAG approaches arise from the fact that the DAG is unstructured, due to the excessive random forking when the mining rate is increased. In contrast, Prism is based on a structured DAG created by crypto- graphic sortition of the mined blocks into different types of different functionalities and scaling these functionalities separately.
Figure 2: Deconstructing the blockchain into transaction blocks, partially ordered proposal blocks arranged by level, and voter blocks organized in a voter tree. The main chain is selected through voter blocks, which vote among the pro- posal blocks at each level to select a leader block. For exam- ple, at level 3, block b is elected the leader over block a.
Figure 3: Prism. Throughput, latency and reliability are scaled to the physical limits by increasing the number of transaction blocks and the number of parallel voting chains.
Deconstruction. We start by deconstructing the basic blockchain structure into its atomic functionalities, illustrated in Figure 2. The selection of a main chain in a blockchain protocol (e.g., the longest chain in Bitcoin) can be viewed as electing a leader block among all the blocks at each level of the blocktree, where the level of a block is defined as its distance (in number of blocks) from the genesis block. Blocks in a blockchain then serve three purposes: they stand for election to be leaders, they add transactions to the main chain, and they vote for ancestor blocks through parent link relationships. We explicitly separate these three functionalities by representing the blocktree in a conceptually equivalent form (Figure 3). In this representation, blocks are divided into three types: proposer blocks, transaction blocks and voter blocks. The voter blocks vote for transactions indirectly by voting for proposer blocks, which in turn link to transaction blocks . Proposer blocks are grouped according to their level in the original blocktree, and each voter block votes among the proposer blocks at the same level to select a leader block among them. The elected leader blocks can then bring in the transactions to form the final ledger. The valid voter blocks are the ones in the longest chain of the voter tree, and this longest chain maintains the security of the whole system. Scaling. This alternative representation of the traditional blockchain, although seemingly more complex than the original blockchain representation, provides a natural path for scaling performance to approach physical limits (Figure 3). To increase the transaction throughput, one can simply increase the number of transaction blocks that a proposer block points to without compromising the security of the blockchain. This number is limited only by the phys- ical capacity of the underlying communication network. To provide fast confirmation, one can increase the number of parallel voting trees, voting on the proposal blocks in parallel to increase the voting
Transaction block
Voter block
Proposer block
Leader block
Parent Link Reference Link
Decoupling Transactions Deconstructing Blockchain
Decoupling Voting
Transaction block
Voter block
Proposer block
L Leader block
Parent Link Reference Link
Chain 1 Chain 2 Chain 𝑚
Session 3B: Blockchain I
CCS ’19, November 11–15, 2019, London, United Kingdom
rate, until reaching the physical limit of confirming with speed-of- light latency and extremely high reliability. Note that even though the overall block generation rate has increased tremendously, the number of proposal blocks per level remains small and manage- able, and the voting blocks are organized into many separate voting chains with low block mining rate per chain and hence little forking. The overall structure, comprising of the different types of blocks and the links between them, is a structured DAG.
Sortition. The sortition of blocks into the three types of blocks, and further into blocks of different voting trees, can be accomplished by using the random hash value when a block is successfully mined. This sortition splits the adversary power equally across the struc- tures and does not allow it to focus its power to attack specific structures. This sortition is similar to the 2-for-1 PoW technique used in [9], which is also used in Fruitchains [19] for the purpose of providing fairness in rewards. In fact, the principle of decoupling functionalities of the blockchain, central to our approach, has al- ready been applied in Fruitchains, as well as other works such as BitcoinNG. The focus of these works is only on decoupling the transactions-carrying functionality. In our work, we broaden this principle to decouple all functionalities.
Concurrent work. We were made aware of two independent but
related works [8, 27] which appeared after we posted this work on-
line. [8] proposes two protocols, one achieves high throughput O (C ) √
butBitcoinlatency,andtheotherachieveslowlatencyO(1/ C)but low throughput O(1). In contrast, Prism achieves simultaneously high throughput O(C) and even lower latency O(1/C). Although [8] also uses the concept of multiple chains, the key difference with Prism is that there is no decoupling: the blocks in each chain both carry transactions and vote. Thus, either different transactions are put on the different chains to increase throughput, but the voting rate is low and hence the latency is poor, or the same transaction is repeated across all the chains to increase the voting rate, but the throughput is poor. In contrast, Prism decouples blocks into transaction blocks and voter blocks, tied together through proposer blocks, and allocate a frac
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com