Scaling Bitcoin’s POW (Part 2/2)
Zhijie_Ren last edited by Zhijie_Ren
by Zhijie Ren and Ziheng (Peter) Zhou
In the previous article, we discussed the scalability of Bitcoin and analyzed the reason why it does not scale, i.e., the security of the POW scheme depends on the condition that "miners should mine on the same block for approximately the same duration". Otherwise, the POW game is no longer fair which ruins the whole idea of POW and gives advantages to attackers.
In order to meet this condition, the synchronization period of a block has to be made significantly smaller than the running time of POW. For instance, when the block interval is 10 min, a block should be synchronized to the whole network in less than 1 min to guarantee that the security is not severely compromised. Such a requirement limits the block size and block interval, and thus the throughput and scalability of Bitcoin.
One solution to scaling POW is to parallel the POW process and the block synchronization to revoke the constraint of "the synchronization period has to be significantly smaller than the POW block interval". We have seen the method of "leader/committee selection", in which the POW is used to only determine the valid leader/committee that proposes a new block rather than the block itself. As a result, nodes could conduct block synchronization and compute the hashes for the next POW simultaneously.
Let us call the "leader/committee selection" algorithms the "first consensus then synchronization" approach, in which all nodes firstly reach some consensus (on the leader or committee of that round) and then work on synchronizing of the transactions. There is another category of algorithms that first let all nodes transmit their transactions, synchronize with other nodes' transactions as much as they can, and then use some algorithms to determine which ones are valid. Moreover, these algorithms will guarantee that malicious nodes could not perform a double spending attack unless they control the majority of mining power. We call these algorithms "first synchronization then consensus" algorithms.
GHOST is probably the first attempt on the "first synchronization then consensus" approach. It is a straightforward extension of Bitcoin, focusing on solving the problem of "security degradation caused by forks". As we discussed before, the naive approaches of increasing the blocks size or reducing the block interval would result in creating more forks in the system. Forks cause the waste of mining power since any miner observing them had to make a decision on which one would be eventually on the "longest chain". If they chose a wrong block to mine, then their mining power would not contribute to the security of the system. As a result, attackers would be able to perform a double spending attack, i.e., creating a longer chain, with less than 50% of the mining power.
In , a fairly simple modification is made on the Bitcoin POW to mitigate this problem to prevent the mining power from being wasted. It proposes a "heaviest branch rule" instead of the "longest chain rule" to determine the valid blocks. The weight of a block is the total mining power that confirmed this block, which is determined by the number of blocks that are directly or indirectly connected to it (including itself).
The above figure illustrates the rule. Here, block 1B has a weight of 12 and block 1A has only 6, hence the branch of 1B should be selected. Similarly, block 2D has a weight of 4 while block 2C has a weight of 5, thus 2C is selected.
It seems that "the heaviest chain" rule gives a perfect solution to the larger block size or shorter block interval modifications of Bitcoin POW. However, there is a severe problem. In GHOST, to guarantee the security of the 50% of the mining power, all nodes have to synchronize and validate the whole graph of blocks. However, eventually only the transactions on the selected chain are confirmed and seen as part of the blockchain. This is a huge waste of resources, especially the bandwidth. Moreover, as larger blocks will result in more forks, the bandwidth efficiency would decrease as the block size increases. As a result, rather than the security, the bandwidth efficiency becomes the constraint on the throughput and scalability of POW. In  as well as the implementation of a modified version of GHOST in Ethereum, it has also been shown that its improvement on throughput over Bitcoin POW is not very impressive.
From Chain to DAG
GHOST opens up a new horizon of replacing the chain structure of Bitcoin by the directed acyclic graph (DAG). In fact, GHOST already reaches consensus on a DAG as all forks are synchronized and validated as well. However, GHOST only takes the transactions on the main chain into account and discards all other transactions. Then, a natural question to ask is:
"What about we keep the transactions in forks as well? What if we have a ledger, which consists of all blocks in the DAG, rather than a chain?"
This is exactly the basic principle of a DAG-based "blockchain" system: all nodes simply mine their blocks appending to all tips, namely the blocks with no children blocks, according to the graph they locally observed. Then, as soon as they solve the POW puzzle, they publish the block, which will be confirmed if it is referred by other blocks and eventually gains a sufficiently large weight.
Comparing to a chain-structured blockchain, the major difference of DAG is that nodes are not required to always synchronize and mine on the newest blocks. Instead, they just validate and mine on all locally observed latest blocks and broadcast their new block when they find a POW nonce. Eventually, all blocks will be included in the DAG and confirmed if a sufficiently large number of blocks connects to it.
As shown in the figure above (here, we borrow the figure of Tangle to explain the idea of DAG), DAG allows multiple blocks to be proposed at the same height thus their mining power would not be wasted. Consequently, it potentially allows higher throughput since we can increase the block size or reduce the block interval without worrying about the degradation in security.
However, this naive extension of GHOST also results in many new problems. Some of them are still not solved by today. We discuss three of the major problems below.
The essence of DAG is that nodes do not need to synchronize all other blocks to propose their blocks. As a result, it is possible that a transaction is included in multiple blocks. It is even a default scenario if all miners are sharing a "mempool" for transactions like the setting of Bitcoin. If all miners proposed blocks with the same set of transactions, the bandwidth would still be wasted. Hence, it is essential that miners should pack different transactions in their blocks.
Tangle (IOTA)  tries to solve this problem by discarding the role of miners. Instead, all users solve a simple POW puzzle and propose their own transactions. As a result, there will not be any duplicated transactions wasting the bandwidth. However, it in fact introduces more security and efficiency problems. For instance, as there are no professional miners, the security of the system is very unstable since it depends on the number of users who are making transactions in that exact moment. Moreover, in Tangle, nodes are encouraged to spam empty transactions appending to their own transactions to boost the confirmation, which is another waste of bandwidth.
Other DAG-based algorithms like Conflux  and Prism  let the miners use a random scheme to choose the transactions while creating the block, so that the probability of duplicated transactions will be small. However, this increases the latency of transactions. Moreover, it is not compatible with the transactions fee model currently used for most cryptocurrencies, i.e., rational nodes have incentives to pick the transactions with higher transaction fees instead of following the random scheme.
In general, it is crucial that there are as few duplicated transactions as possible so that the bandwidth efficiency and throughput are optimized. However, the system is then more exposed to single-point failure as transactions should only be proposed by few miners.
Another problem in DAG is the conflicting transactions. In DAG, since the consensus is reached after they have synchronized a ledger, two conflicting transactions could both end up in the ledger. For two transactions spending the same money, it is then crucial to determine which one comes first and invalidate the later one. In case these two transactions are in blocks which are directly or indirectly connected, it is easy to determine the order of the transactions. However, it is also possible that the blocks including the two transactions are not connected but coincidentally have the same height as well as other parameters according to the graph previous to these two blocks. In such a case, we have to use the properties and topology of the graph following these two blocks to make decision, e.g., using the weight of these two blocks to determine the order.
In Spectre , all blocks following these two blocks are virtually voting on the order of these two blocks and the voting approach is made such that the result quickly converges. However, there is no hard guarantee on the convergence, which gives no guarantee on the liveness of transactions. Spectre bypassed this problem by stating that in cryptocurrencies, conflicting transactions have to be proposed by malicious nodes, and thus it is unnecessary to guarantee their liveness.
If we want to use blockchain for general purposes rather than just a cryptocurrency, we will need the total order of transactions, i.e., all nodes can see transactions (messages) confirmed in the ledger with a consistent order. Then, the argument in Spectre is not applicable anymore and the above-mentioned algorithms can not guarantee a total order of transactions.
There seems to be a contradiction (it's just our personal conjecture, we have no theory for it) for a "pure DAG" here: if there is no total order in the confirmed part of the DAG and requires the information from the unconfirmed part, e.g., the weight of the blocks, to achieve total order, then, we could not simultaneously achieve liveness and total order. Here, by "pure DAG" we mean a DAG that follows the most straightforward rule as stated above: all nodes just try their best to synchronize with the network, and simply mine their blocks on all locally observed latest blocks. Eventually the consensus could be reached on a DAG which cannot be forked with less than 50% of mining power.
As a result, some latest DAG based consensus algorithms choose less "pure" approaches to keeping the concept of "chain" in DAG to achieve total order. In other words, instead of "first synchronization then consensus" for all blocks, nodes should at least reach consensus on blocks on some more important branches. Then, the transactions in the rest parts of the DAG could be totally ordered with these blocks. The main chain concept is explicitly mentioned in Conflux  (called pivot chain in the paper) and implicitly mentioned in Prism . In Phantom , instead of a main chain, the concept of the "main cluster" is used, which plays a similar role as the main chain.
Now, we have introduced some of the most important POW-based blockchain consensus algorithms that improve the scalability of Bitcoin POW. In particular, the main principle is to parallelize the block synchronization with the consensus process, which is the mining for POW.
We call the first category "first consensus then synchronization" algorithms, which uses POW to select a leader or committee instead of a block. Then, the mining could be done in the same fashion while the transactions in the block are synchronizing. This idea is pioneered by Bitcoin-NG, Byzcoin, and Hybrid consensus. Many POS algorithms could also be seen as successors to this idea. (See Scaling Bitcoin’s POW (Part 1/2) for a detailed discussion)
The second category, named the "first synchronization then consensus" algorithms, let nodes try their best to synchronize with the network, do mining upon all locally observed blocks, and broadcast their blocks as soon as they solve a POW puzzle. As a result, instead of a globally agreed chain of blocks, we have a DAG of blocks. The "heaviest branch rule" is then used, instead of the "longest chain rule", to determine the valid blocks. A block accumulating enough weight (blocks that connected to it) will be inevitable in the ledger with less than 50% of mining power. This approach is pioneered by GHOST  and followed by many algorithms like Tangle (IOTA) , Spectre , Phantom , Conflux , and Prism .
In term of throughput, both categories can utilize the network capacity better than the Bitcoin POW. However, there is no clear and fair performance comparison between these algorithms as far as we know.
In the next article, we will discuss another type of consensus algorithms used for blockchain, namely the Byzantine Fault Tolerance (BFT) based consensus algorithms. We will start with the basics about the Byzantine Generals Problem, BFT, and Asynchronous BFT. We will then introduce some important BFT algorithms before the blockchain era, like PBFT and Zyzzyva. In the end, we will talk about some important BFT-based consensus algorithms, such as Byzcoin, Honeybadger BFT, Algorand, and Hotstuff.
 Sompolinsky, Yonatan, and Aviv Zohar. “Secure high-rate transaction processing in bitcoin.” International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2015.