Kaspa 백서

Kaspa

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 4쪽 중 1쪽

PHANTOM GHOSTDAG A Scalable Generalization of Nakamoto Consensus November 10, 2021 Yonatan Sompolinsky yoni_sompo@cs.huji.ac.il School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel Shai Wyborski shaide@cs.huji.ac.il School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel Aviv Zohar avivz@cs.huji.ac.il School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel ABSTRACT In 2008 Satoshi Nakamoto invented the basis for blockchain-based distributed ledgers. The core concept of this system is an open and anonymous network of nodes, or miners, which together maintain a public ledger of transactions. The ledger takes the form of a chain of blocks, the blockchain , where each block is a batch of new transactions collected from users. One primary problem with Satoshi’s blockchain is its highly limited scalability. The security of Satoshi’s longest chain rule, more generally known as the Bitcoin protocol, requires that all honest nodes be aware of each other’s blocks very soon after the block’s creation. To this end, the throughput of the system is artificially suppressed so that each block fully propagates before the next one is created, and that very few “orphan blocks” that fork the chain be created spontaneously. In this paper we present PHANTOM, a proof-of-work based protocol for a permissionless ledger that generalizes Nakamoto’s blockchain to a direct acyclic graph of blocks (blockDAG). PHANTOM includes a parameter k that controls the level of tolerance of the protocol to blocks that were created concurrently, which can be set to accommodate higher throughput. It thus avoids the security-scalability tradeoff which Satoshi’s protocol suffers from. PHANTOM solves an optimization problem over the blockDAG to distinguish between blocks mined properly by honest nodes and those created by non-cooperating nodes who chose to deviate from the mining protocol. Using this distinction, PHANTOM provides a robust total order on the blockDAG in a way that is eventually agreed upon by all honest nodes. Implementing PHANTOM requires solving an NP-hard problem, and to avoid this prohibitive computation, we devised an efficient greedy algorithm GHOSTDAG that captures the essence of PHANTOM. The GHOSTDAG protocol has been implemented as the underlying technology of the Kaspa cryptocurrency. The Kaspa network allows us to produce statistics about the performance of 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 permissions@acm.org. AFT ’21, September 26–28, 2021, Arlington, VA, USA © 2021 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery. ACM ISBN 978-1-4503-9082-8/21/09. . . $15.00 https://doi.org/10.1145/3479722.3480990 GHOSTDAG in real world scenarios. We provide an analysis of confirmation times obtained by observing the Kaspa network. We provide a formal proof of the security of GHOSTDAG, namely, that its ordering of blocks is irreversible up to an exponentially negligible factor. We discuss the properties of GHOSTDAG and how it compares to other DAG based protocols. 1 INTRODUCTION The security of the Bitcoin protocol relies on blocks propagating quickly to all miners in the network [ 9, 14, 19]. Block creation itself is slowed down via the requirement that each block contain a proof-of-work. For the Bitcoin protocol to be secure, block propagation must be faster than the typical time it takes the network together to create the next block. In order to guarantee this property, the creation of blocks in Bitcoin is regulated by the protocol to occur only once every 10 minutes, and the block size itself is limited to allow for fast transmission. As a result, Bitcoin suffers from a highly restrictive throughput on the order of 3-7 transactions per second (tps)1. The PHANTOM protocol. In this paper we present PHANTOM, a protocol that generalizes Nakamoto’s longest chain protocol. In Bitcoin, blocks reference a single predecessor in the chain, hence form a tree; in contrast, PHANTOM blocks reference multiple predecessors, thus forming a Directed Acyclic Graph, a blockDAG. Each block can thus include several hash references to predecessors. PHANTOM then provides a total ordering over all blocks and transactions, and outputs a consistent set of accepted transactions. Unlike the Bitcoin protocol, where blocks that are not on the main chain are discarded, PHANTOM incorporates all blocks in the blockDAG into the ledger, but places blocks that were created by attackers later in the order. In rough terms, PHANTOM consists of a three-step procedure: (1) Using the structure of the blockDAG, we recognize a set of well-connected blocks (we later refer to these as blue blocks); this procedure is used to exclude blocks created by misbehaving nodes and is the heart of the protocol: Blocks that either reference only old blocks from the DAG, or are withheld by their creator for some time, will be excluded from the set of blue blocks with high probability. (2) We complete the DAG’s naturally induced partial order to a full topological one (i.e., an order which respects the 1The exact figure varies according to the size of a typical transaction, and changes if one includes protocol changes such as SegWit, Schnorr signatures, etc. , , Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar topology) in a way that favours blocks inside the selected cluster and penalizes those outside it. (3) The order over blocks induces an order over transactions; transactions in the same block are ordered according to the order of their appearance in the block. We iterate over all transactions in this order, and accept each one that is consistent (according to the underlying consistency notion) with all transactions approved so far. Propagation delay. The first step above involves assuming an upper bound on the network’s delay diameter D, and parameterizing the protocol accordingly; k denotes this parameter. Such an assumption is made in Nakamoto Consensus as well. In fact, if PHANTOM is set to process low throughput, we can set k = 0, in which case PHANTOM coincides with Nakamoto Consensus. However, while Nakamoto Consensus suppresses the throughput and sets the block creation rateλ such that D·λ≪ 1, PHANTOM does not impose an a priori constraint over λ. Instead, the throughput (in terms ofλ and the block size) can be set to approach the network’s capacity, and thenk can be set after the fact to ensure the safety of the protocol. This alleviates the security-scalability tradeoff that Nakamoto Consensus suffers. Still, increasing k does not come without cost, as we will discuss shortly. GHOSTDAG. In its vanilla form, PHANTOM requires solving an NP-hard problem, and is therefore unsuitable for practical applications. Instead, we use the intuition behind PHANTOM to devise a greedy algorithm, GHOSTDAG, which can be implemented efficiently. We prove formally that GHOSTDAG is secure, in the sense that its ordering of blocks becomes exponentially difficult to reverse as time develops. The main achievement of GHOSTDAG can be summarized as follows: Theorem (Informal). Given two transactions tx 1, tx 2 that were published and embedded in the blockDAG at some point in time, the probability that GHOSTDAG’s order between tx 1 and tx 2 changes over time decreases exponentially as time grows, even under a high block creation rate that is non-negligible relative to the network’s propagation delay, assuming that a majority of the computational power is held by honest nodes. We will reformalize this theorem in Section 3, and provide a formal proof in Appendix A. We now proceed to describe the PHANTOM and GHOSTDAG protocols more formally. 2 THE PHANTOM PROTOCOL 2.1 Preliminaries The following terminology is used extensively throughout this paper. A DAG of blocks is denoted G =(C, E), whereC represents blocks and E represents the hash references to previous blocks. We frequently write B∈ G instead of B∈C . past(B, G)⊂C denotes the subset of blocks reachable from B (excluding B), and similarly f uture(B, G)⊂C denotes the subset of blocks from which B is reachable (excluding B); these are blocks that were provably created before and after B, correspondingly. An edge in the DAG points back in time, from the new block to previously created blocks which it extends. We denote by anticone(B, G) the set of blocks outside Figure 1: An example of a block DAG G. Each block references all blocks that were known to its miner at the time it was created. The DAG terminology applies to H as follows: past(H) = {Genesis , C, D, E} – blocks which H references directly or indirectly, and which were provably created before H ; f utur e(H) = {J , K , M} – blocks which reference H directly or indirectly, and which were provably created after H ; ant icone(H) = {B, F , I , L} – the order between these blocks and H is ambiguous. Reaching consensus on the order between blocks and other blocks in their anticone is the main challenge that we face. t ips(G) = {J , L, M} – leaf-blocks, namely, blocks with in-degree 0; these will be referenced in the header of the next block. past(B, G) and f uture(B, G) (excluding B itself); this is the set of blocks in the DAG which did not reference B (directly or indirectly via their predecessors) and were not referenced by B (directly or indirectly via B’s predecessors).2 Finally, tips(G) is the set of blocks with in-degree 0 (usually, the most recent blocks). This terminology is demonstrated in Figure 1. 2.2 The DAG mining protocol Rather than extending a single chain, a miner in PHANTOM references in its new block all blocks in tips(G), where G is the DAG that the miner observes locally at the time when the new block is created. Additionally, the miner should broadcast its new block as fast as possible. These two rules together constitute the DAG mining protocol in PHANTOM. 2.3 The DAG ordering protocol The aforementioned DAG mining protocol implies in particular that even when two blocks contain conflicting transactions, both blocks are incorporated into the blockDAG and referenced by all (honest) miners. The core challenge is then how to recover the consistency of the blockDAG. This is done in our framework by ordering all blocks – and by extension, all transactions – and accepting transactions one by one, eliminating individual transactions that are inconsistent 2We will frequently abbreviate the notation and write, e.g., ant icone(B), instead of ant icone(B, G). PHANTOM GHOSTDAG A Scalable Generalization of Nakamoto ConsensusNovember 10, 2021 , , with those approved before them. PHANTOM achieves consensus on the order of blocks, and this guarantees agreement on the set of accepted transactions as well. Essentially, Bitcoin can be seen as an ordering protocol as well, according to which transactions embedded in the longest chain of blocks precede those off the longest chain. Unfortunately, Bitcoin’s protocol is known to be secure only under slow block rates (see Section 4). The ordering rule of PHANTOM has two stages: First, we divide the blocks to Blues and Reds; the Blue set represents blocks that appear to have been mined by cooperating nodes, whereas blocks in the Red set are outliers that were most likely mined by malicious or strategic nodes. Then, we order the DAG in a way that favours blue blocks and penalizes red ones. The latter step is rather immediate, and the novelty of PHANTOM lies mainly in the first colouring procedure. 2.3.1 The intuition behind PHANTOM. Just like Bitcoin, PHANTOM relies on the ability of honest nodes to communicate to their peers recent blocks in a timely manner, and on the assumption that honest nodes possess more than 50% of the hashrate. The block rate in Bitcoin is suppressed so as to ensure block creation is slower than the time it takes to communicate them. In PHANTOM, on the other hand, we notice that the set of honest blocks can be recognized even when the block rate is high and many forks appear spontaneously: Due to the communication and cooperation of honest miners, we should expect to see in the DAG a “well-connected” cluster of blocks. Indeed, let D be an upper bound on the network’s propagation delay. If block B was mined by an honest miner at time t, then any block published before time t− D necessarily arrived at its miner before time t, and is therefore included in past(B). Similarly, the honest miner will publish B immediately, and so B will be included in the past set of any block mined after timet +D. As a result, the set of honest blocks in B’s anticone is typically small, and consists only of blocks created in the interval[t− D, t + D]. The proof-of-work mechanism guarantees that the number of blocks created in an interval of length 2· D is typically below some k > 0. In short, the set of blocks created by honest nodes is well-connected. The following definition captures “well-connectedness”: Definition 1. Given a DAG G =(C, E), a subset S⊆C is called a k-cluster, if∀B∈ S :|anticone(B)∩ S|≤ k. Attacker nodes may deviate arbitrarily from the mining rules, have large anticones, and even artificially increase the anticone of honest blocks. Nonetheless, since honest miners possess more proof-of-work power, it is usually impossible for malicious miners to create a well-connected set of blocks that is larger than that created by honest nodes. PHANTOM utilizes this fact and selects the largest well-connected set within the DAG, by solving the following optimization problem: Maximum k-cluster SubDAG (MCS k ) Input: DAG G =(C, E) Output: A subset S∗ ⊂ C of maximum size, s.t. |anticone(B)∩ S∗|≤ k for all B∈ S∗. In this formulation, the parameter k is predetermined; see Section 4 for more details. An example of a maximum k-cluster appears in Figure 2. 2.3.2 The PHANTOM protocol. Following the above intuition, the ordering protocol of PHANTOM comprises the following two steps: (1) Given a block G, solve MCS k(G); let’s refer to its output as the Blue set and to its complement set as the Red one. (2) Determine the order between Blue blocks according to some topological sort. Then, for any Blue block B, add to the order just before B all of the Red blocks in past(B) that weren’t added to the order yet; these Red blocks too should be added in a topological manner.3 An example of the output of the PHANTOM procedure on the small blockDAG from Figure 2 is:(A, D, C, G, B, F, I, E,J, H, K). Unfortunately, the Maximumk-cluster SubDAG problem is NP hard (see problem [GT26] in [10]), and PHANTOM is therefore of less practical use for an ever-growing blockDAG. We thus introduce a greedy algorithm that is more suitable for implementation. We call this greedy variant GHOSTDAG.4 2.4 The GHOSTDAG protocol Similar to PHANTOM, the GHOSTDAG protocol selects ak-cluster, which induces a colouring of the blocks as Blues (blocks in the selected cluster) and Reds (blocks outside the cluster). However, instead of searching for the largest k-cluster, GHOSTDAG finds a k-cluster using a greedy algorithm. The algorithm constructs the Blue set of the DAG by first inheriting the Blue set of the best tip Bmax, i.e., the tip with the largest Blue set in its past, and then adds to the Blue set blocks outside Bmax’s past in a way that preserves the k-cluster property. Observe that this greedy inheritance rule induces a chain: The last block of the chain is the selected tip of G, Bmax; the next block in the chain is the selected tip of the DAG past(Bmax); and so on down to theдenesis . We denote this chain byChn(G) =(дenesis = Chn0(G),Chn1(G), . . . ,Chnh(G)). The final order over all blocks, in GHOSTDAG, follows a similar path as the colouring procedure: We order the blockDAG by first inheriting the order of Bmax on blocks in past(Bmax), then adding Bmax itself to the order, and finally adding blocks outside past(Bmax) according to some topological ordering. Thus, essentially, the order over blocks becomes robust as the colouring procedure. 2.4.1 Formal algorithm. The procedures described above are formalized in Algorithm 1 below. The algorithm begins with the base case where the DAG consists of the дenesis block only (lines 2-3). Next, it performs a recursive call to compute the Blue sets and ordering of the past of each of the DAG’s tips (lines 4-5), and inherits those of the best tip (lines 6-8). Then, the selected 3The topological sorts in this second step are additionally required to be agnostic to future blocks: For any Blue block B, the order on blocks in past(B) should remain the same if we remove from the DAG blocks inf utur e(B). This can be implemented, for instance, using a priority queue that pops out blocks according to the size of their past set. 4In previous versions of this paper we referred to both versions as PHANTOM. Essentially, GHOSTDAG can be seen as a fix of the greedy algorithm introduced by the authors in [ 19], called the GHOST protocol. We thank Ethan Heilman for suggesting this name. , , Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar Figure 2: An example of the largest 3-cluster of blocks within a given DAG: A, B, C, D, F , G, I ,J (coloured blue). It is easy to verify that each of these blue blocks has at most 3 blue blocks in its anticone, and (a bit less easy) that this is the largest set with this property. Setting PHANTOM’s inter-connectivity parameter with k = 3 means that at most 4 blocks are assumed to be created within each unit of delay, so that typical anticone sizes should not exceed 3. Blocks outside the largest 3-cluster, E, H , K (coloured red), belong to the attacker (w.h.p.). For instance, block E has 6 blue blocks in its anticone ( B, C, D, F , G, I ); these blocks didn’t reference E, presumably because E was withheld from their miners. Similarly, block K admits 6 blue blocks in its anticone ( B, C, G, F , I ,J ); presumably, its malicious miner received already some of these blocks but violated the mining protocol by not referencing them. tip is added to the Blue set BlueSet G and to the last position in the current ordered list OrderedList G (lines 9-10). Then we iterate over anticone(Bmax, G) in some topological way which guarantees that a block is visited only after its predecessors are (lines 11-14).5 For every block we visit, we check if adding B to the Blue set will preserve the k-cluster property, and if this condition is satisfied, we add B to the Blue set (lines 9-13); either way, we add B to the current last position in the list (line 14). Finally, we return the Blue set and the ordered Note that the recursion in the algorithm (line 5) halts, because for any block B∈ G:|past(B)| <|G|. We demonstrate the operation of this algorithm in Figure 3.We have an efficient implementation of Algorithm 1, and we tested it under high block rates (λ = 10, 25 blocks per second, for blocks of size 0.1-1 MB). We will make the implementation available in the full version of this paper. 2.5 Collapse to Bitcoin when k = 0 If the block creation rate is kept low, as in Bitcoin, the parameter k can be safely set to 0, as honest blocks are likely to create a chain 5This can be implemented in several ways, e.g., by inserting all blocks in ant icone(Bmax) into a deterministic priority queue which respects the topology. That is, the queue should pop out a block only after all of its parents have been popped out, and the order in which it pops blocks should be fully determined by the
프로젝트로 돌아가기