An overview of PHANTOM: A blockDAG consensus protocol (part 3)

This will be the final part of my mini-series on Proof of Work based cryptocurrency/blockchain/blockDAG consensus protocols though there will certainly be more to come. As a recap, we started by analyzing Bitcoin’s longest chain rule and GHOST’s heaviest subtree rule. These protocols built tree structures by design and differed primarily in fork selection. The first blockDAG protocol that we looked at, SPECTRE, abstracts away from this to build a directed acyclic graph structure over blocks. It provides separate mechanisms for mining and consensus on valid transactions, which allows the end user an extra dosage of freedom in the transactions they want to accept. In all of these papers, we explored how intelligently designing protocols leads to greater scalability and security.

Some important factors dictating a protocol’s scalability:

1. Propagation delay on the network
2. Mining difficulty / block creation rate
3. Block size

Given the focus of this piece is also about blockDAG protocols, let’s recap some of what we learned from how SPECTRE is constructed. Miners will create blocks which link to all leaf blocks they currently see in their network view. End users will construct sets of verified and robustly verified transactions that are tunable by how likely transactions are to being reversed. The primary way we achieve this is through a voting scheme that all blocks participate in. In this voting scheme, each block will identify a preference ordering over pairs of blocks based on which block they believe occurred first. The final ordering is taken as a majority vote on pairwise orderings across all blocks. The rules of the voting scheme ensure that honest miners are protected from 50% attacks with high probability.

In the end however, the aggregate ordering at each round is not necessarily linearizable. In addition, there is no guarantee that any linear ordering over blocks & transactions exists without double-spend transactions. SPECTRE proves to be a useful protocol for payment focused networks where transactions can be out of order but still make up the totality of a particular payment. On the other hand, this phenomenon makes SPECTRE unsuitable for smart contract cryptocurrency networks where computation is paramount; having out of order computations can cause some to fail (think about cases when your computation is not commutative, i.e. hashing).

To that end, we will now introduce a new blockDAG protocol, PHANTOM, designed by Yonatan Sompolinsky and Aviv Zohar at The Hebrew University of Jerusalem. PHANTOM sacrifices speed for the ability to totally order blocks and transactions. This total ordering allows us to build smart contracts on this protocol since computation occurs in exactly the way the designer intended.

PHANTOM

For starters, PHANTOM assumes a malicious mining coalition is not the majority, i.e. an attacker has <50% mining power. This puts the asymptotic maximum security threshold of the system at 1/2, similar to that of GHOST and SPECTRE. The PHANTOM protocol differs from SPECTRE in that it enforces a strict ordering over blocks and thus transactions in the system. PHANTOM is usable for smart contract systems in this light but only at the cost of forcing a proper ordering over blocks. The tradeoff can be quantified in the time that it takes nodes in the PHANTOM protocol to reach consensus, which although scalable is not as fast as a protocol like SPECTRE which can run without these guarantees.

blockDAG example clustering picture taken from PHANTOM paper

Mining

Mining is similar to that in SPECTRE, we quote our description with small changes from the previous article:

The mining protocol utilized by PHANTOM follows a similar Proof of Work system as Bitcoin, where the computational puzzles are finding hashes under a target difficulty. At each step in an individual node’s mining process, it examines its view of the blockDAG network and does the following:

Finds the set of all blocks with 0 in-degree, denoted B.

Computes hashes until it finds a hash h<D.

Creates a block b with hash h, includes B in the header (directed edges to those blocks), and broadcasts b.

Consensus

PHANTOM uses purely topological tools for achieving consensus. Differing from the voting scheme used by SPECTRE, the PHANTOM protocol actually determines a “correct blockchain” within the blockDAG as it builds the set of valid blocks in aggregate. Finding this chain happens recursively and forces the total ordering on the transactions included within such a chain. PHANTOM adds these blocks using a greedy approximation algorithm to an optimization problem that will be defined below. For some intuition into this process, the picture below will be useful.

Stepwise examples of the clustering algorithm execution, taken from PHANTOM paper

The main task at the heart of finding the best, honest blocks begins with finding the maximum k-cluster subDAG indicated by the picture above. The formal problem is defined below. The task of picking the best parameter k also presents an interesting problem, since it involves various tradeoffs given the actual network delay is unknown. For starters, the parameter is closely tied to the expected propagation delay of the entire network. Since we operate under the partial synchronous model, this delay is bounded but not explicitly known.

Let’s parse apart this problem statement. Recall from our previous article the definitions of past(x) and future(x). The cone(x) is defined to be the union of past(x) and future(x). Therefore, we define the anticone(x) as the complement of the union of these two sets. These are all blocks where there does not exist a path to block x or no path from x to these blocks.

Now, given a value k and a DAG G, we want to find the largest sized subDAG, such that for any block B in our subDAG, the number of blocks with no paths to B or no paths from B to these blocks intersected with our subDAG is bounded by k. The picture above is an example of the maximum sized subDAG for k=3. If mathematical notation appeals to you more, then it’s probably more sensical to read the problem statement than my description, but hopefully they both help.

Furthermore, the maximum k-cluster subDAG problem is NP Hard. This means that in order to build such a coloring/find such a subDAG, we must employ approximation algorithms. Some resources defining this result and approximation strategies can be found below:

• Tight bound of best cast approximation
• Approximation algorithms for solving it in general

Now assuming we choose our parameter k as wisely as possible and using our chosen approximation algorithm, we would end up with a really nice coloring of our blockDAG like the pictures shown above, and this coloring would favor honestly mined blocks more because we also assume they make up the majority fraction of computational power. We’ve talked repeatedly about the types of attacks malicious mining participants try to execute but for clarity we will restate the two most important.

We restrict attention to the main attack of double-spending. In this event, an attacker who seeks to revert the confirmation of transactions already published to the blockDAG will do one of the following:

1. Withhold blocks that will form an attacker subDAG/chain, publishing them at a later time.
2. Build on top of an attacker subDAG so as to increase the sizes of anticones of honest blocks.

In the first instance, the attacker loses all possible connections from honest blocks that have been generated in the time he/she withheld blocks. Thus, these withheld blocks form a majority of the anticones of blocks that are honestly generated. If these blocks are withheld for too long, then surely the subDAG consisting of the honest blocks will be substantially larger. The success probability of this attack decreases exponentially the longer the attacker chooses to withhold blocks.

In the second instance, the attacker cannot reliably build a subDAG larger or faster than the honest miners since he/she makes up a minority fraction of the computational power. Thus, this attack has low probability of success as time increases in general.

Now, we have yet to discuss how we compute an ordering over the chosen subDAG. We know the DAG induces a topological sort/ordering from the previous article on SPECTRE, but, different from that, we now want to enforce a strict ordering based on the transactions that occur. Assume through some parameter k and some approximation algorithm we arrive at a coloring of our graph like that in the picture. We will focus attention on the honest (blue) subDAG, denoted BLUE_k(G). Starting at the genesis block (the root), we will iteratively look at its children in a manner much like breadth-first search (maintain a queue, etc) and do the following. This is a rudimentary sketch of the ordering algorithm. The paper should be consulted for those more interested:

Ordering Algorithm Sketch

1. Initialize an empty queue Q and list L.
2. Add the genesis block into Q.
3. While !Q.isEmpty():
4. — — Add B←Q.pop() into L.
5. — — Iterate over the blue children C of B:
6. — — — — Iterate over blocks D in past(C) and in anticone(B):
7. — — — — — — Add D into Q.
8. — — — — Add C into Q.
9. Output L.

We assume that redundant insertions are ignored as well for the sake of clarity. The intuition for the algorithm is that we prioritize blue blocks in our ordering primarily because they are honestly mined. Therefore, no blocks will have conflicting transactions or times. The tricky inclusions would involve including some blocks outside our blue coloring because there may actually be valid transactions within them, i.e. our choice of k could be poorly chosen and fragment G in undesirable ways. In order to account for this, we consider all blocks in the anticone of each blue block along our DAG traversal. These blocks are those referenced by honestly mined blocks, i.e. blocks that an honestly mined block points to. In this way, the only blocks that can precede honest blocks are those that honest blocks believe precede them. If an attacker wanted to reverse transactions in an honestly mined block, the eventual block(s) they publish will not be referenced in blocks early enough to precede the honestly mined block.

Given L, how do we guarantee that we achieve liveness and safety? Recall in the previous DAG based protocol, SPECTRE, we could only achieve weak liveness since we could not guarantee total orderings over the transactions and blocks. Now that we can achieve such an ordering from above, we should also be able to achieve the full capabilities of a liveness condition. To do so, we must define the likelihood that a transaction/block within our ordering gets preceded by another block not currently in our ordering, denoted Risk. The risk defines how likely an event such as a double spend/transaction reversal occurs. The authors show, as the t*→ ∞, the Risk(B,t*) over all blocks B in the globally correct blockDAG at some non-zero time t, with 0<t≤t*, can converge to arbitrarily low values of 𝜖 for certain ordering rules.

The convergence of this probability or risk rests on the chosen ordering rule that end users opt in to use. It follows that in order to guarantee liveness and safety, honest end-users are incentivized to use converging ordering rules, i.e. ordering rules with the property that the Risk of blocks and consequently transactions approaches 0 in the limit. When there is negligible risk, then honest users can surely accept transactions (as merchants) without the Risk that these transactions will get reversed. Thus, individual users can agree that their transactions are robustly confirmed and can guarantee that all other users will eventually have the same confirmed sets of transactions.

Formalizing this however still remains part of future work and presents an interesting direction for future work in DAG based protocols.

Future Work

For some ideas about how this work can be extended, there is certainly the broad idea of testing out new consensus mechanisms such as using a solution to the maximum sized k-cluster subDAG problem. Consider the wide variety of optimization problems that can be defined on graphs such as clique finding, etc. There are a plethora of tools that can potentially be used to develop new protocols.

We leave a list of these ideas and problems:

1. Formalize liveness and safety conditions for PHANTOM given it needs to be well-defined over every nodes’ view of the blockDAG rather than the hypothetical “best” blockDAG that could exist over the history seen thus far.
2. Investigate in a real network the effect of varying values of k under different network delays D.
3. Investigate dynamic k-cluster maximization in a DAG, using multi-armed bandits for parameter selection. This would entail defining a local (by individual miners) or global utility function of the blockDAG and learning to maximize that utility with respect to a given k.
4. Implement the protocol with different approximation algorithms and ordering algorithms for honest block selection and consensus.

If you enjoyed this piece, definitely read the previous sections part 1 and part 2 if you haven’t and follow me on twitter @dungulator