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,프로젝트로 돌아가기