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