Advantages and Disadvantages of the Longest Chain Rule
By Conflux Development Department
In this article, the discussion will be focusing on the Longest Chain Rule adopted by Bitcoin, namely the “Satoshi Nakamoto consensus algorithm” .
Conflux adopts the Heaviest Chain Rule, which is different from the Longest Chain Rule. Previously, we often talked about why Conflux did not choose the Longest Chain Rule, but barely mentioned any advantages of such. Therefore, a more comprehensive discussion that covers both strengths and weakness is shared here.
Firstly, let’s take a look at the advantages.
Starting from the Bitcoin, followed by the Litecoin — which only altered a couple of parameters of Bitcoin, the later proposed Bitcoin-NG[1], and the OHIE[2] using the DAG structure, the core concept of many public chain consensus algorithms is the Longest Chain Rule.
Favored by so many public chain projects, what is the biggest advantage of the Longest Chain Rule?
OHIE’s paper[2] mentioned a key point: for a blockchain system, one crucial point is an “end-to-end” security proof, that is, a security proof only work for a few specific attacks is far from enough, as there is no way to avoid smarter people to design smarter attack strategies in the future.
As for the end-to-end security proof, the Longest Chain Rule advances much more than others. As the core rule of Bitcoin, the first of cryptocurrencies, the most extensive and in-depth study has been carried out for the Longest Chain Rule.
In fact, even though it was the most studied, the full proof of its safety was not completed until September 2016 by Rafael Pass, a cryptography professor at Cornell University[3]. (Satoshi Nakamoto’s proof in the Bitcoin white paper only considered the specific attack. Other earlier works only proved the security of the Longest Chain Rule under certain conditions.) Rafael’s proof can be directly extended to any reasonably designed public chain systems based on the Longest Chain Rule.
In contrast, other consensus algorithms, including the Heaviest Chain Rule, did not have complete security proof until 2019, and some consensus algorithms did not even have a security proof under defined conditions. We will leave the questions related with the Heaviest Chain Rule and how Conflux will cope with them in the following issues, here I will expand no further.
So why doesn’t Conflux employ the Longest Chain Rule?
The main reason is that the Longest Chain Rule is very sensitive to “orphan blocks”.
“Orphan block” refers to blocks that are formally legal but are not eventually included by the main chain (the longest chain). In the ideal case, the honest node will increase the length of the longest chain by one each time a block is generated. However, if two honest nodes mine two blocks almost at the same time and do not yet refer to each other as the parent block, then the two blocks will form a competitive relationship. At best, only one of the competing blocks will be included in the longest chain, and the rest will become “orphan blocks” that do not contribute to the longest chain.
Once there are too many orphan blocks in the system, the growth rate of the longest chain will be affected, which will increase the chances of being attacked. For example, in the case where 50% of the honest blocks become orphans, the average growth rate of the longest chain is only half of the block-generating speed of the honest nodes. At this time, the attacker only needs 34% of the total computing power (more than half of the computing power of the honest node) to initiate a double-spend attack on any previous transactions.
The frequency of the occurrence of orphan blocks is related to a ratio: Average block-generating time/ Block broadcasting time in a peer-to-peer network. We will refer this ratio as the security factor for the time being. The higher the ratio is, the less frequently the orphan blocks will appear, and the safer the main chain will be. According to the analysis in the article [3], when the ratio is larger than 7, the theoretical threshold of the computational power required for the double-spend attack is about 45%; when the ratio is greater than 60, the theoretical threshold is about 49.5%. At present, the ratio of Bitcoin is around 60.
Therefore, we have the following four formulas:
1. Security Factor = Average Block-generating Time/ Block Broadcast Time
2. Network Bandwidth Factor = Block Size/ Block Broadcast Time
3. Payload per Transaction = Block Size / Number of Transactions per block
4. TPS = Number of Transactions per block/ Average Block-generating Time
That is, Security Factor * Payload per Transaction * TPS = Network Bandwidth factor
Each item, besides TPS itself, in the above equations, corresponds to an entry point to improve the TPS under the Longest Chain Rule:
1. Lower the Security Factor: simply change the parameters of Bitcoin and sacrifice part of the security in exchange for higher efficiency. For example, shorten the block generation time or increase the block size (equivalent to increase the block broadcast time).
2. Lower the Payload per Transaction: apply the Compact Block Technology to convert the complete transmission of each transaction (appx. several hundred KB) into the short transaction ID (4~6B).
3. Increase the Network Bandwidth Factor: increase the threshold for joining the consensus nodes and sacrifice a degree of decentralization in exchange for higher efficiency. In extreme cases, keep only a small number of supernodes (such as 21) that are directly connected to the network.
The approaches above are very direct and effective, but the performance improvement that they can bring is limited, and the sacrifices caused by the overuse of them is also significant. For example, increasing the size of a block to hundreds of MBs or reducing the number of consensus nodes to 20 is probably not worth the effort.
In fact, Bitcoin-NG and OHIE adopt some special designs to bypass the above limitations. On the other hand, if the Tree Graph and the Longest Chain Rule are combined, a high TPS consensus mechanism can be designed easily. In this regard, we will address in another article to discuss it thoroughly.
All in all, on the road to improve the TPS, although the Longest Chain Rule is subject to the above analysis, the ceiling can be bypassed by a reasonable design.
The biggest weakness of the Longest Chain Rule is the Block Confirmation Time.
If the Security Factor is set to 10, the average waiting time to confirm 6 blocks is 60 * Block Broadcast Time; if a transaction needs to be confirmed within two minutes, the Block Broadcast Time needs to be controlled within 2 seconds.
In fact, in each hop of the block broadcasting, every node needs to perform a series of operations such as signature verification and transaction execution before forwarding toward the next hop. When the number of nodes is large, it is very difficult to broadcast even a small/medium size block to all (or most) nodes in the whole network within 2 seconds. For the current network environment, a confirmation time of 3 to 5 minutes is basically the limit of the Longest Chain Rule.
The prototype of Conflux (also known as the current public version, the new version of the article and technical specifications has not been publicly released) has a confirmation time of 4 to 7 minutes, which does not seem to do a better job. In fact, as we conduct more in-depth research on the Heaviest Chain Rule and further explore its unique potential, we have made amazing breakthroughs in the confirmation time of the PoW chain, and have achieved a confirmation speed way above that in the Longest Chain Rule.
What is the most attractive feature of the Heaviest Chain Rule? We will discuss further in the next issue.
[1] Eyal I, Gencer A E, Sirer E G, et al. “Bitcoin-NG: A Scalable Blockchain Protocol.” USENIX 2016.
[2] Haifeng Yu, et al. “OHIE: Blockchain Scaling Made Simple.” arXiv:1811.12628 (2018).
[3] Rafael Pass, Lior Seeman, and Abhi Shelat. “Analysis of the Blockchain Protocol in Asynchronous Networks.” EUROCRYPT 2017.
[4] Yonatan Sompolinsky and Aviv Zohar. “Secure High-Rate Transaction Processing in Bitcoin.” International Conference on Financial Cryptography and Data Security, FC 2015.
