An Introduction to the BlockDAG Paradigm

Contrary to popular belief, using a DAG (directed acyclic graph) as a distributed ledger is not about removing proof-of-work mining, blocks, or transaction fees. It is about leveraging the structural properties of DAGs to potentially solve blockchain’s orphan rate problem. The ability of a DAG to withstand this problem and thus improve on scalability is contingent on the additional rules implemented to deal with transaction consistency, and any other design choices made.

Directed acyclic graphs

A DAG is not a novel concept or technology, and it is definitely not a consensus mechanism; it is purely a mathematical structure originating from centuries ago. Technically, a DAG is a graph with directed edges and no cycles (i.e., there is no path from a vertex back to itself).

In the context of distributed ledgers, a blockDAG is a DAG whose vertices represent blocks and whose edges represent references from blocks to their predecessors. Evidently, in a blockDAG, blocks may have several predecessors instead of just one; this will be described in more detail below. First, let us recall the orphan rate problem.

Blockchain’s orphan rate problem

There are many barriers to blockchain scalability, including processing speeds, disk I/O, RAM, bandwidth, and syncing new nodes. While these limitations can be addressed with improved hardware and technology, a major barrier exists on the protocol level: the orphan rate. Orphans are blocks that are created outside the longest chain due to unavoidable network propagation delays.

Accelerating block creation and/or increasing block sizes increases the orphan rate: by the time a new block propagates throughout the network, other new blocks which do not reference it are likely to be created. It is well established that a high orphan rate amounts to compromised security; the more honest blocks that end up outside the longest chain due to spontaneous forks, the less secure is the chain.¹

Blockchain protocols typically impose a maximum block size and constant block creation rate to accommodate the network propagation and minimize orphans. This artificial limit of transaction throughput and lower bound on latency (in Bitcoin’s case, to 3–7 transactions per second and tens of minutes confirmation times) is a hard pill for blockchains to swallow — while it impedes on-chain scaling, it guarantees that spontaneous forks and orphans are rare and, therefore, that the main chain is secure. DAG protocols, however, may deal with orphans in other ways.

The blockDAG paradigm

The notion of a fork is organically absorbed in the DAG framework, so it seems worthwhile to consider if a DAG could do better than the chain/linked list structure of blockchains. Accordingly, with Satoshi’s proof-of-work system as the starting point, we need to make one change to the mining protocol in order to yield a blockDAG: blocks may reference multiple predecessors instead of a single parent. A canonical way to extend the ledger is to have blocks reference all tips of the graph (that their miners observe locally) instead of referencing the tip of the single longest chain, as in Satoshi’s original protocol.

In a canonical blockDAG ledger, new blocks reference all tips of the graph (blocks that have not yet been referenced) that their miners see locally. As in a blockchain, blocks are published immediately.

However, unlike a blockchain which, by construction, preserves consistency (every block in the chain adds transactions that are consistent with its predecessors in the chain), a blockDAG incorporates blocks from different “branches” and so may contain many conflicting transactions. Because of this, a DAG, or blockDAG, cannot be considered a “solution” or “novel approach” or “new protocol” in and of itself. Instead, a blockDAG is a framework for devising consensus protocols that may (or may not) be as secure as and more scalable than chain-based protocols.²

We therefore need a method to recover consistency; in other words, a blockDAG system requires replacing Satoshi’s longest chain rule with a new consensus protocol.

Consensus via ordering

Observe that if a distributed system achieves consensus on the order of all events in it, then we can easily extend this agreement to achieve consensus on the state — we simply iterate over all transactions according to the agreed order, and accept each transaction that is consistent with those accepted so far. This method preserves consistency by construction.

We are left with the task of defining an ordering protocol on all events in the system — in our context, on all blocks in the DAG — in a way that will be agreed upon, eventually, by all nodes.

The natural topology of a DAG already induces a partial ordering over the blocks: if there is a path from block X to block Y in the DAG, then block Y was provably created before block X and so should precede X in the global order, and vice versa. Thus, we only need to define an order over blocks created in parallel, i.e. any set of blocks such that there is no path that connects them.

This paradigm began with the blockDAG-based protocols developed out of the Hebrew University (Inclusive, SPECTRE, and PHANTOM); these protocols each define an algorithm that outputs an order over the DAG’s blocks, iterates the DAG by that order, and eliminates transactions that conflict with previous ones. (Actually, SPECTRE does something slightly weaker, but that’s a topic for a separate blog post.)

Advantages of blockDAGs

BlockDAG protocols such as SPECTRE and PHANTOM circumvent the problems associated with high orphan rates. This comes with many advantages:

  • It allows for confirmation times on the order of seconds, at least when there are visible double-spends and conflicts
  • It allows for a large transaction throughput, limited only by the network backbone and endpoints’ capacity; as a derivative, it implies low fees
  • It contributes to mining decentralization by allowing for roughly 100,000 blocks per day, which reduces the incentive to join a mining pool
  • It avoids the risk of orphaning, which comes with many additional benefits (such as Layer Two compatibility)
  • It eliminates selfish mining by rewarding all blocks without discriminating between on-chain and off-chain blocks

We will expand on each of these points and how SPECTRE and PHANTOM achieve them in future blog posts.

BlockDAGs vs. blockless DAGs

Almost every single DAG-based cryptocurrency on the market (IOTA, Byteball, Nano, etc.) has deviated from Satoshi’s blockchain paradigm, not only by using the DAG structure, but also in economic design: some have relegated mining to their users, some have eliminated proof-of-work mining altogether, many have no transaction fees, and practically all have no blocks, chaining together individual transactions. These design decisions may work in a DAG system, but they are characteristics independent of DAGs. In fact, these projects’ use of a DAG is probably their least defining characteristic.

The rising popularity of these DAG systems has heavily influenced the community’s perception of DAGs. On the one hand, there are the fervent supporters who tout DAG technology as “blockchain 3.0”, and on the other, the skeptics who dismiss it as vaporware. Almost all, however, praise or criticize the economic design choices of existing DAG protocols, which have nothing to do with DAGs.

For instance, in a recent Q&A, renowned blockchain expert Andreas Antonopoulos described DAGs as “an alternative consensus mechanism” opposed to proof-of-work. “If you don’t have decentralized proof-of-work mining, you don’t really need blocks,” Antonopoulos says. “You can just chain transactions together, which is the basis of directed acyclic graphs.”

But, as explained above, DAGs are not about replacing proof-of-work or blocks. DAGs are merely a mathematical structure that happen to be used by several projects that deviate from Satoshi’s proof-of-work system. In contrast, blockDAGs are the applications of DAGs to a Nakamoto-based system (in particular, with proof-of-work), only redesigning the data structure and consensus layer.

Bram Cohen of BitTorrent and Chia hits closer to the mark with this scathing tweet:

Indeed, a DAG is purely a structural alternative to a chain — and a chain is also not novel, notable, or exciting. What made Satoshi’s system novel is its overall design: proof-of-work mining, blocks, transactions, and a protocol that reaches consensus in a permissionless system and incentivizes participation. BlockDAG systems like SPECTRE and PHANTOM generalize over Satoshi’s innovative design and achieve novelty through their unique consensus protocols for ordering the DAG in an irreversible way, thus avoiding the security-scalability tradeoffs brought on by orphans.

Endnotes:

  • For proofs of this statement see [a][b][c]
  • For example, if a DAG protocol sorts transactions by having those in the longest chain precede all others, it suffers from the same security-scalability tradeoffs of a blockchain.