Kaspa 백서

Kaspa

원문

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

blockDAG. Algorithm 1 Ordering the DAG Input: G – a block DAG, k – the propagation parameter Output: BLU Ek(G) – the Blue set of G; ord – an ordered list containing all blocks in G 1: function OrderDAG(G, k) 2: if G =={дenesis} then 3: return[{дenesis} ,{дenesis}] 4: for B∈ tips(G) do 5: [BlueSet B, OrderedList B]←OrderDAG(past(B) , k) 6: Bmax ← arg max{|BlueSet B| : B∈ tips(G)} (break ties according to lowest hash) 7: BlueSet G← BlueSet Bmax 8: OrderedList G← OrderedList Bmax 9: add Bmax to BlueSet G 10: add Bmax to the end of OrderedList G 11: for B∈ anticone(Bmax, G) do in some topological ordering 12: if BlueSet G∪{B} is a k-cluster then 13: add B to BlueSet G 14: add B to the end of OrderedList G 15: return[BlueSet G, OrderedList G] (see Section 4). In such a setup, both PHANTOM and GHOSTDAG converge to Bitcoin’s rule in the sense that, in case of a chain split, blocks on the longest chain precede those off the longest chain. These protocols would differ from Bitcoin’s rule in that, as of according to the DAG mining protocol, blocks in the longest chain would eventually reference those off the longest chain, in PHANTOM or GHOSTDAG, and will thereby insert them in the order. In fact, it is easy to see that the longest chain is, by definition, the largest 0-cluster of the DAG. Accordingly, our protocols can be seen as a generalization of Satoshi’s longest-chain rule to a setup where block rate is high and propagation delays are not negligible. In Appendix A we prove that GHOSTDAG remains secure under high block creation rates as well. We leave the formal analysis of PHANTOM for future work. 3 FORMAL MODEL AND STATEMENT In this section we describe our formal framework. While we introduce new notation and terminology, the reader should keep in mind that we stick to Nakamoto Consensus’s model in almost every respect—transactions, blocks, Proof-of-work, computationally bounded attacker, P2P propagation of blocks, probabilistic security guarantees, etc. The “only” difference is that a block references (possibly) several predecessors rather than a single one. While this has far reaching consequences on how the ledger is to be interpreted, on the mining side things remain largely the same. 3.1 Network We follow the model specified in [18]. The network of nodes (or miners) is denotedN, honest denotes the set of nodes that abide to the mining protocol (as defined below), and malicious denotes the rest of the nodes. Honest nodes form a connected component in N’s topology, and the communication delay diameter of the honest PHANTOM GHOSTDAG A Scalable Generalization of Nakamoto ConsensusNovember 10, 2021 , , Figure 3: An example of a blockDAG G and the operation of GHOSTDAG to construct its blue set BLU E k(G) set, under the parameter k = 3. The small circle near each block X represents its score, namely, the number of blue blocks in the DAGpast(X). The algorithm selects the chain greedily, starting from the highest scoring tip M , then selecting its predecessor K (the highest scoring tip in past(M)), then H , D (breaking the C, D, E tie arbitrarily), and finally Genesis . For methodological reasons, we add to this chain a hypothetical “virtual” block V – a block whose past equals the entire current DAG. Blocks in the chain (дenesis , D, H , K , M , V) are marked with a light-blue shade. Using this chain, we construct the DAG’s set of blue blocks, BLU E k(G). The set is constructed recursively, starting with an empty one, as follows: In step 1 we visit D and addдenesis to the blue set, as the only block in past(D). Next, in step 2, we visit H and add to BLU E k(G) blocks that are blue in past(H), namely, C, D, E. In step 3 we visit K and add H , I ; note that block B is in past(K) but was not added to the blue set, since it has 4 blue blocks in its anticone. In step 4 we visit M and add K to the blue set; again, note that F∈ past(M) could not be added to the blue set due to its large blue anticone. Finally, in step 5, we visit the block vir tual(G) = V , and add M and to BLU E k(G), leaving L away due to its large blue anticone, and leaving J away because adding it would cause I to suffer too large a blue anticone (it already has C, D, and H in it). subnetwork is D: if an honest nodev∈N sends a message of size b MB at time t, it arrives at all honest nodes by time t + D the latest. The attacker is assumed to suffer no delays on its outgoing or incoming links. The real value ofD is a priori unknown. The PHANTOM protocol assumes that D is always smaller than some constant Dmax (both depend on the block sizeb). The parameter Dmax is not hard-coded explicitly in the protocol, rather it influences another parameter, k = k(Dmax), which is hard-coded and decided once and for all at the inception of the system. Roughly speaking,k(Dmax) represents an upper bound on the number of blocks that the network creates in one unit of delay and that may not be referenced by one another. Section 4 discusses this parameter in more detail. 3.2 Mining framework Proof-of-work. Nodes create blocks of transactions by solving Proof-of-work puzzles. Block creation follows a Poisson process with parameterλ. For the sake of simplicity, we assume thatλ is constant.6 We denote by time(B) the absolute time of B’s creation. The computational power of nodev∈N is captured by 0 <αv < 1, which represents the probability that node v will be the creator of the next block in the system (at any point in time; this is a memoryless process). 6In practice, λ must occasionally be readjusted to account for shifting network conditions. PHANTOM can support a retargeting mechanism similar to Bitcoin’s, e.g., readjust every time thatChn(G) grows by 2016 blocks. Block references. Every block specifies its direct predecessors by referencing their ID in its header (a block’s ID is obtained by applying a collision resistant hash to its header); the choice of predecessors will be described in the next subsection. This results in a structure of a directed acyclic graph of blocks (as blocks can only reference blocks created before them), denoted typicallyG =(C, E). Recall that the topology of the DAG induces a natural partial ordering over blocks (Subsection 2.1): if B∈ past(C) (equiv. C∈ f uture(B)) then C was provably created after B and therefore B should precede C in the order.7 DAG mining protocol. Gvt denotes the block DAG that nodev∈ N observes at time t. This DAG represents the history of all (valid) block-messages received by the node. A node does not consider a block as valid until it receives its entire past set. The unique block дenesis is the block created at the inception of the system, and every valid block must have it in its past set. A tip of the DAG is a leaf-block, namely, a block with in-degree 0. The instructions to a miner in the DAG paradigm are simple: (1) When creating or receiving a block, transmit it to all of one’s peers inN . Formally, this implies that∀v, u∈ honest : Gvt ⊆ Gut +D . (2) When creating a block, embed in its header a list containing the hash of all tips in the locally-observed DAG. Formally, this 7Note that an edge in the DAG points back in time, from the new block to previously created blocks which it references. , , Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar implies that if block B was created at time t, by honest node v, then past(B) = Gvt .8 Since these are the only two mining rules in our system, a byzantine behaviour of the attacker (which controls up to α of the mining power) amounts to an arbitrary deviation from one or both of these instructions. For convenience, we additionally regard the virtual block of the DAG,virtual(G), which is a hypothetical (un-mined) block which points to the DAG’s tips as its parents. Thus,past(virtual(G)) = G. Essentially,virtual(G) represent the block template for the next block to be created by the miner, if it is honest. 3.3 DAG client protocol The DAG as described so far possibly embeds conflicting transactions. In our work, these conflicts are resolved via an ordering protocol, namely, a protocol through which all nodes agree on the order of all transactions in the system. We refer to the ordering rule as the client protocol, as every participant in the network can run the ordering procedure on its client locally without any need to communicate additional messages with other clients. Once such an order is agreed, one can iterate over all transactions in the prescribed order and approve each transaction that is consistent with those approved so far. In the case where transactions represent payments in Bitcoin’s UTXO model, a transaction would be consistent with the set of previously approved transactions if its inputs belong to this set and none of these inputs are already spent by another transaction in the set (i.e., no “double spend”). However, our work is agnostic to the precise definitions of the transaction space and of the underlying consistency notion—for our purpose, suffice it to regard an abstract transaction spaceU and an abstract consistency function that determines whether a set of transactions T⊆U is consistent or not. Formally, an ordering rule ord takes as input a blockDAG G and outputs a linear order over G’s blocks, ord(G) =(B0, B1, . . . , B|G|). Transactions in the same block are ordered according to their appearance in it, and this convention allows us to talk henceforth on the order of blocks only. With respect to a given rule ord , we write B≺or d(G) C if the index of B precedes that of C in ord(G); we abbreviate and write B≺G C or even B≺ C when the context is understood. For convenience, we use the same notation B≺G C when B∈ G but C < G. 3.4 Convergence of the order The following definition captures the desired security of the protocol, in terms of the probability that some order between two blocks will be reversed. Definition 2. Fix a rule ord , time t > 0, and node u∈N . • For B∈ Gut , Risku(B, t, r) is defined by the probability that, from the point of view of u, a block that did not precede B in time t + r will later come to precede it: Risku(B, t, r) := Pr  ∃s > t + r,∃C∈ Gus : B≺Gut +r C∧ C≺Gus B • If B < Gut we define Risku(B, t, r) = 1. 8Technically it is more accurate to write past(B) = Gvt \{B}, as a block does not belongs to its own past set. • The function Risk is the maximal Risku over honest nodes: Risk(B, t, r) := max u∈honest Risku(B, t, r) Intuitively,t represents the time at which blockB was included in the DAG, andt + r the time at which transactions in B can be safely accepted as no conflicting ones would be able to bypass them. In the definition above, the probability is taken over all random events in the network, including block creation and propagation, as well as the attacker’s arbitrary behaviour. The convergence property below guarantees that the order between a block and those succeeding it (or those not published yet) will not be reversed, w.h.p. This captures the security of the protocol, as it provides honest nodes with (probabilistic) security guarantees regarding possible reorgs. Property 1. An ordering rule ord is said to (1-α)-converge if∀t > 0, ∀u ∈ honest and∀B ∈ Gut : limr→∞ Risk(B, t, r) = 0, even when a fractionα of the mining power is byzantine. Ideally, we would want Risk(B, t,·) to vanish exponentially fast so as to ensure speedy confirmation times. Remark. Property 1 essentially couples the Safety and Liveness properties required from consensus protocols. Indeed, once Risk(B, t, r) <ϵ, a decision to accept transactions in B can be made (Liveness), and is guaranteed to be irreversible (Safety) up to an error probability of ϵ—as in Nakamoto Consensus and similar protocols, decisions are only irreversible in the probabilistic sense. Nevertheless, we avoid phrasing our results in these terms, for the sake of clarity of presentation. The complication arises from the need to analyze the system from the perspective of every node Gvt ; this technicality is not unique to PHANTOM, and should be regarded in any work that formalizes blockchain based consensus (unless propagation delays are assumed to be negligible). We leave the task of bridging this gap to a later version. The security threshold is the minimal portion of the hashing power that an attacker must acquire in order to disrupt the protocol’s operation: Definition 3. The security threshold of an ordering rule ord is defined as the maximal α (attacker’s relative computational power) for which ord (1-α)-converges exponentially fast. 3.5 Main result A protocol is scalable if it is safe to increase the block creation rateλ without compromising the security, that is, if the security threshold does not deteriorate asλ increases (this can be phrased also in terms of increasing the block size b rather thanλ). We claim that GHOSTDAG is indeed a scalable protocol, in this sense: Theorem 4 (GHOSTDAG scales). Given a block creation rateλ > 0, δ > 0, and Dmax > 0, if Dmax is equal to or greater than the network’s propagation delay diameter D, then the security threshold of GHOSTDAG, parameterized with k(Dmax ,λ,δ), is lower bounded by 12·( 1−δ). The parameterization of GHOSTDAG via k(Dmax ,λ,δ) is defined in the subsequent section. Theorem 4 encapsulates the main achievement of our work. We prove the theorem formally in PHANTOM GHOSTDAG A Scalable Generalization of Nakamoto ConsensusNovember 10, 2021 , , Section A. Contrast this result to a theorem regarding Nakamoto Consensus, which appears in several forms in previous work (e.g., [15, 19]): Theorem 5 (Nakamoto Consensus does not scale) . The security threshold of Nakamoto Consensus goes to 0 as D·λ grows. Finally, we note that even if Dmax ̸≥ D, the system’s security does not immediately break apart. Rather, the minimal power needed to attack the system goes from 50% (times ( 1−δ)) to 0, deteriorating at a rate that depends on the error gap D− Dmax . 4 SCALABILITY AND NETWORK DELAYS 4.1 The propagation delay parameter Dmax The scalability of a distributed algorithm is closely tied to the assumptions it makes on the underlying network, and specifically on its propagation delay D = D(b) where b is the block-size in KB. The real value of D is both unknown and sensitive to shifting network conditions. For this reason, Bitcoin operates under the assumption that D is much smaller than 10 minutes, and sets the average block interval time to 10 minutes. While this seems like an overestimation of the network’s propagation delay under normal conditions (at least in 2018’s Internet terms), some safety margin must be taken, to account for peculiar network conditions as well. Similarly, in PHANTOM (and GHOSTDAG) we assume that the unknown D is upper bounded by some Dmax = Dmax(b) which is known to the protocol. The protocol does not explicitly encode Dmax , rather, it is used to parameterize k, as will be described in the next subsection. The use of an a priori known bound Dmax distinguishes GHOSTDAG’s (and PHANTOM’s) security model from that of SPECTRE [18]. While the security of both protocols depends on the assumption that the network’s propagation delay D is upper bounded by some constant, in SPECTRE the value of such a constant need not be known or assumed by the protocol, whereas GHOSTDAG makes explicit use of this parameter (via k) when ordering the DAG’s blocks. The fact that the order between any two blocks becomes robust in GHOSTDAG, but not in SPECTRE, should be ascribed to this added assumption; see further discussion in Section 5. 4.2 The anticone size parameter k The parameter k is decided from the outset and hard-coded in the protocol. It is defined as follows: k(Dmax ,λ,δ) := min n ˆk∈ N : f( ˆk, Dmax ,λ) <δ o (1) f( ˆk, Dmax ,λ) := max    ∞Õ j= ˆk +1 e−2·c·(2· c)j j! , 2· cˆk + 2· c    , (2) where c := Dmax · λ. The motivation behind this definition is twofold. Natural anticone size. First, we want to devise a bound over the number of blocks created in parallel. Since the block creation rate follows a Poisson process, for an arbitrary block B created at time t, k(Dmax ,λ,δ) bounds the number of additional blocks created in the time interval[t− Dmax , t + Dmax], with probability of at least 1−δ; the term ˝∞j= ˆk+1 e−2·Dmax·λ·(2·Dmax·λ)jj! from (2) bounds the probability that more than k blocks were created in parallel to B in the time interval[t− Dmax , t + Dmax]. Observe that blocks created in the intervals[0, t− Dmax) and (t + Dmax ,∞), by honest nodes, belong to B’s past and future sets, respectively. Consequently, in principle,|anticone(B)| ≤ k with probability of 1−δ at least. However, an attacker can artificially increase B’s anticone by creating blocks that do not reference it and by withholding his blocks so that B cannot reference them. Chain growth rate. The second motivation for (1) is potential manipulations by attackers on the increase rate of the blue set. GHOSTDAG does not guarantee that discovering new blocks necessarily increases the size of the blue set. Fortunately, by increasing k, we are able guarantee that the adverse effect is arbitrarily small. Indeed, a worst case analysis carried out in Lemma 9 shows that the overall decrease is at most by a factor of 1− 2·Ck +2·C  . This is the role of the right-hand size term inside (2). We note one caveat here: the probability 2·Ck +2·C does not vanish exponentially fast with k. To fix this, a tighter analysis of the effect of these attacks is needed; we leave this challenge to future work. 4.3 Trade-offs Theorem 4, and the parameterization of GHOSTDAG in (1), tie together k, Dmax , λ, and δ. Striving for a better performance by modifying one parameter (e.g., increasing λ to obtain larger throughput and more frequent blocks) must be understood and considered against the effect on all other parameters. Increased block creation rate. Although the security threshold does not deteriorate as λ is increased, λ cannot be increased indefinitely, or otherwise the network becomes congested. The value of λ should be set such that nodes that are expected to participate in the system can support such a throughput. For instance, if nodes are required to maintain a bandwidth of at least 1 MB per second, and blocks are of size b = 1 MB, then the block creation rate should be set toλ = 1 blocks per second (this is merely a back-of-the-envelope calculation, and in practice other messages consume the bandwidth as well). Higher security threshold. Theorem 4 states the security threshold in terms ofδ. Following (1) we notice that tightening the security threshold – by choosing a lowerδ – requires increasing k. A large k leads to slow confirmation times, as will be discussed shortly.9 Larger safety margin. Similarly, if Dmax is to be increased, one needs to increase k as well in order to maintain the same security level (represented byδ). As discussed in Subsection 4.1, it is better to overestimate D and choose a large Dmax in order to remain on the safe side.10 Recall that the security of Bitcoin’s chain depends on the assumption that D·λ≪ 1, namely, that w.h.p. at least D seconds pass between consecutive blocks, so that forks are rare. Thus, Bitcoin’s large 9The advanced reader should notice that although increasingλ has a similar negative effect on k, it has at the same time a positive effect on confirmation times, and so a certainλ will be optimal as far as confirmation times are concerned. 10Several blockchain based projects do not do so, and consequently compromise the security threshold of their system. , , Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar safety margin over D suppresses its throughput severely as it requires selecting a very low block rate λ = 1/600 (one block per 10 minutes). This is not the case with GHOSTDAG’s DAG, as the security of the DAG ordering does not rely on the assumption D·λ≪ 1. Therefore, even if we overestimate D, we can still allow for very high block creation rates while maintaining the same level of security. Consequently,
프로젝트로 돌아가기