An introduction to the blockDAG paradigm
Contrary to popular belief in the crypto community, using a directed acyclic graph (DAG) as a distributed ledger isn’t about removing proof-of-work mining, blocks, or transaction fees. It’s 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 isn’t a novel concept or technology, and it’s definitely not a consensus mechanism; it’s a mathematical structure originating from centuries ago. Technically, a DAG is a graph with directed edges and no cycles (i.e., there’s 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. The blockDAG originated as part of the solution to blockchain’s orphan rate problem.
Blockchain’s orphan rate problem
There are many barriers to blockchain scalability, including processing speeds, disk input/output, 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 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’s well-established that a high orphan rate compromises security; the more honest blocks end up outside the longest chain due to spontaneous forks, the less secure 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. With Bitcoin’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 natural 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.
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 “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 — iterate over all transactions according to the agreed order, and accept each transaction consistent with those accepted so far. This method preserves consistency by construction.
We’re 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’ll be agreed upon, eventually, by all nodes.
The natural topology of a DAG already induces a partial ordering over the blocks: if there’s 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; see the co-author’s explainer.)
Advantages of blockDAGs
BlockDAG protocols such as SPECTRE and PHANTOM avoid 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; this also 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.
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 describes 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 orphan blocks.
_________________________________________________________________
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.
