PoW, PoS and DAGs are NOT consensus protocols

The much hyped concepts of Proof-Of-Work, Proof-of-Stake and Directed Acyclic Graphs are often mistakenly advertised as “consensus protocols”. Neither of them are, but rather address the key challenges of a robust blockchain design: Sybil resistance and asynchronicity.

Preface

Despite a sheer amount of buzz around blockchain, it seems that even very basic ideas are constantly getting confused even by seemingly reputable sources. Here is a recent example, pointed out by Emin Gün Sirer:

In fact, his #microlecture, delivered earlier in a smashing tweeter-storm served as the main source of inspiration.

I decided to write a more detailed note, explaining not only what is actually PoW, PoS and DAGs, but also why we need these devices in order to build a secure blockchain. And yes, they are not consensus protocols.

Here I present a short excerpt, the full article is available on GitHub. The full version contains many details I omitted in the Medium article, as well as an extensive list of references for further in-depth diving.

TL;DR

1. The consensus is needed since each participant has it own slightly different view of the world.
2. Finality is needed to prevent double-spends.
3. If you can flood the network with many clones (Sybils) supporting you, you can revert the consensus. Finality is incompatible with Sybil attacks, thus Sybil attacks should be hard.
4. PoW is a Sybil resistance scheme (not a consensus protocol): one has to spend a lot of resources to propose a block, so a Sybil attack is expensive.
5. Nakamoto consensus is a static rule: take the chain with the highest difficulty. No network communication is needed.
6. PoS is another Sybil resistance scheme: block producers are pre-defined, one has to spend the internal currency in order to have a chance to become a block producer. Thus, producing many blocks for a Sybil attack is expensive.
7. By using PoW or PoS one can make the network is synchronous if the average block proposal time is larger than the network latency.
8. High block proposal rates are only possible in asynchronous networks with many forks. DAG is a data structure which allows a block to have many parents, efficiently keeping track of many intertwined forks. In general, if two blocks are conflicting, the one included in more (weighted) forks become canonical.
9. Building a Sybil-resistant decentralized asynchronous system with fast transaction confirmations (time to finality) is hard.

Local views vs Global state

A blockchain is a distributed system whose state evolves over time. A classical example of a state is a ledger with account balances, but it really can be anything (e.g. in Ethereum, it’s the state of EVM, so in particular it contains all the states of all smart contracts in the network). It’s tricky, however, to define a global state for a distributed system and here is why.

Each node participating in the network has its own view of the state, so there are actually as many versions of the state as the number of nodes in the network. In order to define the global state of the blockchain, we need to have an efficient protocol which would allow all the participating nodes to agree on the same state and update their local views accordingly. In other words, the global state is a version of the view everyone agrees upon.

State is a chain of blocks

Most blockchains, batch incoming transactions into blocks, which are stacked on top of each other. In the simplest case, each full node in the network keeps all the blocks ever produced by the network, but uses only some of them in order to build its local view.

The algorithm is the same for each node and is basically as follows.

1. Keep all blocks in collection B containing all the blocks
2. Choose a chain of blocks form B
3. Construct the local view S by applying the transactions in the blocks from (2)

Double-spends

The two most important things one should think of designing a blockchain is to how to avoid double-spends and Sybil attacks.

Double-spends may look as follows: you buy a coffee, pay at the desk, the transaction is seemingly valid and accepted, but eventually it turns out that your transaction is not included in the ledger. While you’re happy since you got your coffee for free, the barista will not use such a lousy payment system anymore.

While in centralised systems like Visa, the merchant can appeal to the processing authority, there’s none to ask in a decentralised system. That’s why it should be guaranteed that once your payment is accepted, it’s always included in the global state of the ledger. But it means that each network node (at least those following the network rules faithfully), will include your transaction the local view, now matter what happens later on. In other words, chooseBlockSequence(B) should always include the block with your transaction. A transaction guaranteed to be present in the global state is called final. The time one has to wait until a transaction is final is called confirmation time, or time to finality.

Sybil attacks

Sybil attack is an attack preventing finality. The fundamental weakness of anonymous decentralised systems is that they have no arbiters representing the ground truth (like the Constitution, the Supreme Court, etc.). The network truth (the global state) is based solely on the way each node builds its local view, that is on which blocks are picked up by chooseBlockSequence(B).

Now, assume Alice has the ability to produce many blocks indistinguishable from those used to build the global state. In particular, Alice can instantaneously flood the network with so many blocks that B becomes dominated by them. Then, chooseBlockSequence(B) will inevitably pick up Alice’s blocks and all global state is going to be completely rewritten, together with the history.

This is certainly incompatible with finality guarantees and the much hyped mantra that the “distributed ledgers are unalterable”.

Nakamoto consensus and PoW

So why then Bitcoin transactions are unalterable? Well, because there is a clever mechanism, called Proof-of-Work, which makes it hard to produce blocks undistinguishable from the ones already accepted by the network. This property, difficulty, is very useful since:

1. Anyone can check that a block X has higher difficulty than Y.
2. It takes a lot of resources to produce a block with high difficulty. This is why it is called proof of work: anyone can check that producing X required much more computational resources (and thus, money) than producing Y.

So while Alice can flood the Bitcoin with formally valid blocks, none of them have a chance to rewrite the global state since only very mighty mining pools can produce blocks with difficulty high enough.

In turn, the Nakamoto consensus is simply a very concrete implementation chooseBlockSequence(B): choose those blocks forming a valid chain with highest difficulty.

So Proof-of-Work is a mechanism preventing Sybil attacks and thus providing finality (the famous rule of thumb “wait until 6 block confirmations” simply means that the difficulty required to revert the transaction is high enough). The Nakamoto consensus is a rule how to resolve forks.

Proof of Stake

Proof of Stake is another mechanism, preventing Sybil attacks. While arguably the only truly battle-tested solution, PoW takes too much resources and the mining power becomes too concentrated in the hands of a few huge pools. The premise of PoS is to replace the external resources (hardware and electricity needed for mining in PoW) with the internal resource (the underlying cryptocurrency).

PoS has many flavours (see the references in the main article), but the underlying idea is as follows: one has to acquire a certain amount of crypto in order to produce a block. In particular, if Alice wants to rewrite the history, she is going to invest quite a lot of crypto in order to mass-produce enough blocks and shift the global consensus on her side.

However, PoS is susceptible to an issue known as nothing-at-stake. At the philosophical level, the problem is that the cryptocurrency ledger, used in order to prevent Sybil attacks, is itself encoded in the underlying blockchain. In particular, if a fork happens, the block producer has her money invested in both versions of the global state for free. For example, when Bitcoin/Bitcoin Cash fork happened, all BTC holders got their BCH out of thin air, while still holding the same amount of BTC. In particular, former die-hard bitcoiners have all the reasons to support both forks since they profit both from BTC and BCH prices surges.

DAGs

Both PoW and PoS have another important feature not mentioned so far: new blocks appear rather rarely, so the time a new valid block is produced serves as a network clock. Even though the exact time is random, the difficulty is adjusted in such a way the average time between two consecutive blocks in the canonical chain is stable and accurate (10 mins for Bitcoin) when averaged over many consecutive blocks. Since 10 mins exceeds the network latency, it’s fairly safe to assume that a block reaches all the network nodes before a new one is mined. What it means is that the network is essentially synchronous.

Synchronicity is essential to Nakamoto consensus: the majority of the nodes should have the same collection of blocks B so that chooseBlockSequence(B) returns the same chain and so everyone agrees on a unique canonical fork. It comes at a price: the transaction throughput in synchronous single-chain systems is inevitably capped by the number of transactions in the block divided by the network latency. This is a serious challenge, since increasing the maximal block size increases latency and may compromise the protocol security. To put it simple, synchronous blockchains don’t scale.

So in order to scale, one has to deal with many forks and it’s not longer the case that only a single fork is canonical. Instead, the routine chooseBlockSequence(B), which build the local view from the collection of all blocks B, should merge the forks in the most efficient way possible. Here DAGs (directed acyclyc graphs) come handy: if classical blockchains are essentially trees where a block has a single parent, DAGs allows multiple parents. So DAG is just a data structure used for storing blocks.

A DAG. Source: Wikimedia

The philosophy behind the DAG approach is that having multiple parents, each block is included in a large amount of small interconnected forks. Such a complex entangled system, continuously updated by independent rational actors, is expected to be metastable in the following sense. If two blocks X and Y are conflicting, and, say, X happen to be included in just a few more forks than Y, then eventually all future forks will include X while Y will be abandoned. What is important here is that even though each node in the network has it own local DAG and updates arrive in a random order, the preference of X over Y becomes visible in all the local views, so it becomes a global consensus that X is canonical while Y is abandoned.

In theory, DAGs can accommodate a very high throughput and fast confirmation times. The problem is that it’s much harder to tackle double-spends and Sybil attacks in asynchronous systems, especially in the case when making a transaction is cheap. Indeed, in the extreme case when everybody can quickly submit and confirm a transaction at no cost, nothing prevents a Sybil to flood the system with transactions. Pouring a large set of transactions to the network within a short period of time is essentially equivalent to the situation when a network recovers after a partition, so with costless transactions noting prevents an adversary to build up a convincing support for her “alternative truth”.

The existing DAG solutions employ various ad-hoc solutions to enforce finality by anchoring local views to a global source of the ground truth. ByteBall uses special witnesses, Vite has a separate PoW-based chains keeping snapshots, IOTA has a special coordinator whose transactions are always assumed to be valid.

Disclaimer: the whole thing should be taken with a grain of salt, all inaccuracies are solely mine. I strongly recommend consulting the additional sources cited in the full article.

Anyway, don’t remember to clap if you liked the article. You can also follow me on Twitter: @dizhel where I occasionally post crypto stuff.

Get Best Software Deals Directly In Your Inbox