An overview of Proof of Work based blockchain consensus protocols (part 1)
The shape and topology of blockchain (or DAG) based consensus protocols is inherent to future development and research of scalable cryptocurrencies. To that end, it is useful to classify and remark upon how each differs and provide improvements or drawbacks in relation to one another. I also think it’s important to get these ideas out in the open to help educate people who are interested in cryptocurrency & decentralized technology research.
In this first section we will analyze 2 consensus mechanisms, that of Bitcoin and protocols adhering to similar constructions and the GHOST protocol.
As a primer for those interested in consensus research, I would recommend the following topics:
- Algorithmic game theory & Mechanism Design (a textbook on the subject)
- Distributed systems theory, especially that of FLP Impossibility & Byzantine theory
- Bitcoin whitepaper
- Applied Cryptography: hashing/secure multi-party computation
Some jargon
Before we dive in, recall that blockchains are distributed systems. They are run in a decentralized fashion by nodes that do not need to trust one another. Participants do work solving computationally challenging problems (from the perspective of Proof of Work) in order to compete to win block rewards and secure the network. This process provides the underlying security and consensus model for agreeing on the honest state of the blockchain.
We use the term honest as follows. In a blockchain network, honest participants follow the protocol. They compete to mine blocks on the correct blockchain they have seen so far. They may see many blockchains at some time t, but honest miners mine according to the blockchain that adheres to the underlying consensus protocol. On the other hand, malicious miners mine on a malicious or incorrect chain. Usually we consider these scenarios as they relate to double-spending attacks on blockchains. Malicious miners are interested in overtaking the honest chain with a malicious chain.
Consensus
Consensus, in distributed systems terms, is the process of getting a set of processes (in many cases faulty) to agree on a history or state of the world. When we design blockchain consensus protocols we want them to satisfy certain properties defined below:
- Liveness. Every non-faulty node decides on a blockchain in finite time
- Safety. Every non-faulty node decides on the same blockchain
Proof of Work
Proofs of work were initially introduced by Dwork in this paper to combat spam. The main goal of a proof of work is to prevent Sybil attacks; these are attacks that can be highly parallelized by the abundance of computing resources in existence today. Thus, a proof of work is some computationally hard but tractable puzzle that requires users interested in a resource to provide to gain access to said resource. Its computational nature allows us the ability to quantify how much work a given proof contains. Blockchains utilize these to prevent Sybil attacks and most importantly achieve consensus. These proofs provide the necessary security to make claims above the likelihood that transactions on blockchains are confirmed.
Bitcoin
The first consensus protocol worth mentioning is precisely the first blockchain based consensus mechanism, Bitcoin’s longest chain consensus rule. The protocol is to mine on top of the longest chain with respect to the highest aggregate amount of work put into a chain. Recall that Bitcoin miners mine a block when they find inputs that hash to outputs smaller than a dynamically updating, difficulty parameter D. In aggregate, we can compute the longest chain by considering which chain took the most work to mine by analyzing the difficulties of each block in that specific blockchain. For simplicity, we assume the longest chain by height also correlates to the longest chain by aggregate work/hashes computed.
(by Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar)
The rules of the game are as follow. Consider a miner, Alice. Alice is participating in Bitcoin protocol as an honest miner. Over time, Alice constructs a blockchain based on the messages (blocks) she has seen from other peers she is connected to in the Bitcoin network. Since she follows the protocol, at some time t, Alice mines a block b_t+1 on top of her most up-to-date, correct blockchain B=(b_1, b_2, …, b_t), a list of blocks.
Let’s denote the height of a blockchain by the function h, such that h(B) is B’s height. If at any point, Alice sees a new block b’ from one of her peers extending B, Alice will stop mining on B and begin mining on B’=(b_1, b_2,…, b_t, b’). This is because Alice is an honest participant and honest participants adhere to the protocol.
Throughout this process, the difficulty D continuously updates to keep block arrivals around ~10 minutes. The combination of this with the added proof of work/computational hash power provides liveness and safety of the Bitcoin protocol. We can assume with high probability that after some number of blocks, it is infeasible to reverse transactions. Therefore, every 10 minutes we are guaranteed liveness and every k*10 minutes safety in the Bitcoin protol.
Forks
In the figure above, a fork in the blockchain is depicted. Fork’s are a common occurrence since blockchain networks are run asynchronously. Peers gossip about the latest blocks they’ve seen, but, due to network delays and geographic separation, they may hear about different blocks which are mined at seemingly similar times. In the event a fork as described previously, nodes on opposing ends of the fork compete independently to extend their differing blockchains. This race finalizes with 1 longest chain. Since the probability that two distinct subsets of the blockchain network continuously find blocks simultaneously vanishes as the length of the forked chains increases, we can say with high probability that these forks will eventually converge to one correct chain. Make note that once a fork is resolved, all transactions on the “losing” blockchain are invalidated unless they were simultaneously included in the correct, winning blockchain by the consensus rules. We call these blocks orphans. Orphaned blocks are valid blocks (eventually invalid), and the transactions are eventually invalidated. Instead, the transactions are re-included into the transaction pool for future inclusion into blocks on the correct blockchain.
Given this concept, a core attack that adversaries look to execute is that of overtaking the honest blockchain. If an adversarial coalition can create blocks at a faster rate than the honest coalition, the attack will succeed with probability 1. This result has been formulated by Lewenberg, Sompolinsky, and Zohar and is easy to accept. If the bad actors create blocks faster than the good ones, then they can immediately start rewriting the history and publish this to the network at some later point (once they overtake the honest chain). From the picture above, simply imagine the attack builds a longer chain in secret.
Bitcoin’s longest chain consensus rule is thus susceptible to attacks in this variant, commonly called the 51% attack and with decent probability smaller fractions of the network. We won’t go into much detail on how other attacks relate to this ability but yield references to interesting analyses and research.
- Eclipse attacks & censhorship for causing forks by Heilman et al.
- Selfish mining & block withholding attacks by Eyal et al.
Currently, Ethereum also follows this rule with small changes to how orphaned block miners are rewarded.
For more papers utilizing this consensus mechanism albeit improving security concerns, there has been work in combining Proof of Work with general Byzantine fault-tolerant consensus algorithms using leader elections.
Future Work
- Extend the result from this paper to tolerate 50% attacks.
- Build a classification of hybrid Proof of Work and BFT consensus protocols, including the effect of different leader elections on scalability.
- Analyze hybrid protocols under eclipse and block withholding attacks.
Scalability
Bitcoin is not very scalable. On average, people will tell you that it a transaction is “confirmed” once it is buried 6 blocks into the blockchain. This is taken to be a sufficient proof of work such that reversing 6 blocks to double spend coins in a specific transaction is infeasible. As we mentioned however, the Bitcoin blockchain creates blocks at an average rate of around ~10 minutes, so that’s roughly ~1 hour of your time waiting to fully spend your money. That means if you wanted to purchase your Starbucks’ coffee with bitcoin, you’d surely want to bring a book.
- Bitcoin’s block time is designed to hover around ~10 minutes (the difficulty parameter updates to converge to this)
- Bitcoin’s block size is currently 1 MB
- Layer 2 scaling solutions are the main approach to scalability
The long block time explains a lot about the dynamics and topology of the resulting chain, including all orphaned blocks throughout its history. Having a long block time allows messages ample time to travel across the network. This in turn enables nodes to be quite in sync. Forks occur every so often but are likely not extended due to the rarity of two blocks being found at similar times twice in a row, three times in a row, etc. This yields the resulting picture:
One might ask, can we design with Layer 1 technology with scalable-first principles? Yes we can.
GHOST: Greedy Heaviest-Observed Sub-Tree
The GHOST consensus protocol was designed by Sompolinsky and Zohar in Secure High-Rate Transaction Processing in Bitcoin. GHOST is a Proof of Work blockchain protocol much like Bitcoin’s, except in how it resolves the correct blockchain. As the name entails, instead of a longest chain consensus rule, GHOST follows the path of the subtree with the combined hardest proof of work/difficulty. This can be succinctly visualized as the path of the largest subtree by cardinality and refer to that for simplicity, however the consensus rule, similar to Bitcoin, is based on aggregate computational power/hashes but of subtrees instead of single links.
(by Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar)
The GHOST protocol overlays onto traditional Proof of Work challenges like hashing; think back to the game Alice plays. Now, Alice instead chooses to mine on the chain according to the heaviest subtree consensus rule. Now, the main reason why subtrees are created in the first place seems to be because forks are constantly being generated along the main chain as depicted in the figure above. By the second layer, there is a three-pronged fork and another by the 3rd layer.
To show that the GHOST protocol satisfies liveness and safety it helps to describe the formalization of the authors. A Proof of Work blockchain network using the GHOST consensus protocol is modeled by a connected graph network G=(V,E) with the following properties:
- Nodes are vertices and edges are peer connections.
- Each node has some fraction of the total computational power p.
- Each edge has a time delay d.
- The network generates blocks according to a Poisson process.
The GHOST protocol satisfies liveness because, similar to Bitcoin, individual non-faulty nodes can mine and broadcast new blocks once they solve the proof of work puzzle. The safety guarantee comes by construction since the network has some bounded delay D≤d_1+d_2+…+d_m, denoted by the sum of individual node delays. From this, we can argue that if any block B has not been accepted or rejected by the entire network, then either, in the next span of D, this block B will be broadcast to the network or, from the last time all nodes were in sync, a new block will have propagated sooner to the whole network in time ≥2D. This seems natural since we have a dynamically updating difficulty ensuring liveness from the participants, a rule for deciding the correct chain to mine on, and the assumption of bounded delay. As a final clarification, the authors define a collapsing of a fork to be the earliest time a block is either abandoned or accepted by all nodes.
Forks
Sompolinsky and Zohar use the fact that reducing the block time and increasing the block size increases the number of forks that occur: the difficulty threshold is reduced, blocks take longer to propagate, so geographically dispersed miners find blocks sooner and hear of blocks later. They use forks for the protocol’s advantage. This represents some of the primary ways for increasing scalability in Layer 1 blockchain technology, as long as nodes manage to reach consensus. In the case of Bitcoin, higher block throughput leads to a reduction of the cost needed to attack the correct, honest blockchain. In the case of GHOST however, it does not.
Consider an attacker Eve, whom mines blocks with a rate a. If Eve has half the computational power on the network, she can reliably extend her malicious blockchain. Consider the event where a block B is on the main blockchain at time t=time(B)+e but off the main blockchain at some time ≥t. Let the random variable denoting the collapse of B be c_B such that c_B≥t. The event we are interested in investigating is the event that the collapse has not occurred: c_B≥t. It has not been accepted or rejected by all nodes yet. However, since the GHOST protocol satisfies safety we know the expected value of c_B is finite. It follows that the probability B gets accepted or rejected by all nodes goes to 1 as e->infinity. We need only consider the case when it was accepted and then later rejected. Given B is accepted, the attacker is begins building the malicious blockchain in subtree(B). Yet, this since this only adds weight to the subtree, the Eve is never able to overcome the subtree weight by extending a single chain. The subtree grows farther and farther away from Eve’s blockchain as e->infinity and thus we have greater security to 50% attacks. Since blocks are confirmed by their subtrees, attackers will always be contributing to the subtree of honestly generated blockchains or fail undeniably when attackers have ≤50% computational power.
Thanks to the authors, we have upper and lower bounds for a variety of nice quantities such as the worst case time it takes for a collapsing to occur and the rate of growth of the blockchain. Another interesting direction for this work is to consider Eclipse attacks. If an adversary can cut off a large portion of the nodes in the network, then it could be possible for a mining coalition to generate subtrees at a faster rate. I would guess this number to be around 67% since the attacker could use each third to extend various subtrees favorably.
For a further description of the paper and a nice general framework for analyzing blockchain protocols including an analysis of the GHOST protocol, refer to the links.
Future Work
- Investigate hybrid consensus models using the GHOST protocol and derive their security and consensus guarantees, i.e. with leader election etc.
- Derive bounds of selfish mining abilities for mining coalitions in the GHOST protocol.
- Investigate the effect of peer delay on expected rewards of well connected miners vs not well connected miners.
- Classify other blockchain protocols using similar models used in the GHOST protocol and formulate problems in a statistical framework.
Scalability
Since we can securely increase throughput and velocity of blocks using the GHOST protocol, it provable scales faster than Bitcoin. Thus, it will be interesting to see precisely by how much in a live network, though it is most likely, easily parameterized.
I believe Ethereum is also considering implementing the GHOST protocol within the first output of Casper The Friendly Finality Gadget but may be incorrect. In any case, these mechanisms can be extended to Proof of Stake protocols but the underlying security of Proof of Stake protocols is still an actively researched area.
Conclusion
In this first set of analyses, we investigated Proof of Work based blockchain consensus protocols. We saw two different metrics for deciding on the correct, main blockchain that honest miners extend. Each of these mechanisms share similar quantitative notions of a blocks aggregate proof of work/hash power but differ qualitatively: aggregate chain work vs aggregate subtree work. The ability to generate subtrees is inherent to the GHOST blockchain’s consensus mechanism and thus we can tolerate proliferation of subtrees, enabling greater transaction throughput.
As we can see, the ability to increase throughput is a seemingly topological phenomenon. Rather than focusing on a 1-dimensional view of aggregate work, we focus on a 2-dimensional view. We both extend the longest chain (1st axis) by the weight of subtrees (2nd axis). In the next part, we will investigate more consensus mechanisms as they relate to scalability, advancing our notion of dimensionality to blockDAGs or “blockchains” built over directed acyclic graphs.
Special thanks to Derek Hsue for thoughts and edits. Follow me on twitter for more researchy content @dungulator
