In the first installment of our series, we’ll talk about the longest chain rule, or “Satoshi Consensus algorithm,” used by Bitcoin.
Since Conflux uses the heaviest chain rule which is different from the longest chain rule, in previous articles, we often explained the reason why Conflux does not choose the longest chain rule, but introduced the advantages of the longest chain rule itself. This time we will discuss the advantages and disadvantages of the longest chain rule from a more comprehensive perspective.
First let’s talk about the advantages of the longest chain rule.
From the beginning of Bitcoin, whether litecoin which only changed parameters at the beginning, bitcoin-ng [1] which was proposed later, or OHIE [2] which adopted DAG structure, the core idea of many common chain consensus algorithms is the longest chain rule.
Can get the favor of so many public chain projects, the longest chain rule in what place?
OHIE’s paper [2] makes an important point: the most important thing for a blockchain system is an “end-to-end” proof of security — proving security against only a few specific types of attack is not enough, because there is no way to avoid smarter people designing smarter attack strategies in the future.
The longest chain rule has sufficient first-mover advantage in end-to-end security proof. As the core rule of Bitcoin, the precursor to cryptocurrency, the longest chain rule has been the most widely and deeply studied.
In fact, the complete proof of the security of even the longest chain rule, which has been studied the most, was not completed until September 2016 by Rafael Pass et al., professor of cryptography at Cornell University [3]. (Mr. Nakamoto’s proof in the Bitcoin white paper only considered specific attacks, and some earlier work 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 system based on the longest chain rule.
In contrast, other consensus algorithms, including the heaviest chain rule, did not have a complete security proof before 2019, and some consensus algorithms did not even have a security proof under limited conditions. We will leave questions about the heaviest chain rule and dealing with Conflux for a few more issues and won’t expand on them here.
So why didn’t Conflux adopt the longest chain rule?
The main reason is that the longest chain rule is very sensitive to “solitary blocks”.
Isolated blocks are those that are formally legal but do not end up in the main chain (the longest chain). In an ideal world, an honest node increases the length of the longest chain by one each time it generates a block. However, if two honest nodes dig up two blocks at nearly the same time, and neither of them references the other as a parent block, then the two blocks are in competition. Only one of the competing blocks ends up in the longest chain, and the rest become “lone blocks” that contribute nothing to the longest chain.
If there are too many “lone blocks” in the system, the growth rate of the longest chain will be affected, giving an attacker an advantage. For example, with 50% of the honest blocks being “lone blocks”, the average growth rate of the longest chain is only half as fast as that of the honest nodes, and the attacker only needs 34% of the total force (more than half of the honest force) to launch a double-flower attack on any early transaction.
The frequency of “isolated blocks” is related to a ratio: the average time it takes to generate a block/the time it takes for a block to broadcast over a peer-to-peer network, which we’ll call the security factor. The higher the ratio, the less frequent solitary blocks are and the safer they are. According to the analysis in article [3], when the ratio is greater than 7, the theoretical threshold value of computing force required by double-flower attack is about 45%. When the ratio is greater than 60, the theoretical threshold of computing power required for double flower attack is about 49.5%. The current bitcoin ratio is around 60.
So we have the following four formulas:
- Safety factor = average time to generate a block/block broadcast time
- Network bandwidth coefficient = block size/block broadcast time
- Single transaction load = block size/number of transactions per block
- TPS = Number of transactions per block/average time to generate a block
In other words, security ratio * load per transaction * TPS = network bandwidth coefficient
Each item in the above formula except TPS corresponds to a pointcut that improves TPS under the longest chain rule:
- Reduced security: Simply change bitcoin’s parameters, sacrificing some security in exchange for greater efficiency. Such as shortening the block generation time or increasing the block size (equivalent to increasing the block broadcast time).
- Reduce the load per transaction: Use compact block technology to transfer each transaction in its entirety (about hundreds of KB) into a short ID (4 to 6 B) of the transfer transaction.
- Improve network bandwidth coefficient: increase the threshold of joining consensus nodes, sacrifice the degree of decentralization for higher efficiency. In extreme cases, only a small number of supernodes (say 21) with direct fiber connections can be retained.
These changes are straightforward, but the performance gains are limited, and the cost of overuse is high. For example, increasing the block size to hundreds of MB or reducing the number of consensus nodes to 20 is probably not worth the cost.
In fact, Bitcoin-ng and OHIE use some special designs to get around these limitations. On the other hand, if the tree graph structure is combined with the longest chain rule, it is actually very easy to design a high TPS consensus mechanism. We’ll write an article about this in detail, but we won’t go into it here.
In conclusion, the ceiling can be avoided with proper design, although the longest chain rule is subject to the above analysis on the way to improving TPS.
The biggest weakness of the longest chain rule is the block confirmation time.
If the safety factor is set to 10, the average time to wait for six confirmation blocks is the time required for 60 * blocks to broadcast; If you need to confirm a transaction in two minutes, you need to limit the block broadcast time to two seconds.
In fact, for each hop in a block broadcast, each node needs to validate and perform a series of operations before it can forward to the next hop. When there are many nodes, it is very difficult for even a small block to spread across all (or most) nodes of the network in 2 seconds. From the current network environment, 3 to 5 minutes of confirmation time is basically the limit of the longest chain rule.
The prototype version of Conflux (that is, the current public version, the new version of the articles and technical specifications have not yet been publicly released) has a block confirmation time of 4 to 7 minutes and doesn’t seem to be doing much better. In fact, as we have further studied the heaviest chain rule and further explored its unique potential, we have made amazing breakthroughs in the confirmation time of THE PoW chain, which is far faster than the confirmation speed of the longest chain rule…
What is the appeal of the heaviest chain rule? And to be decomposed in the next period. Man man man man
[1] Eyal I, Gencer A E, Sirer E G, et al. “Bitcoin-ng: A Scalable Scalable Blockchain Protocol. “USENIX 2016. [2] Haifeng Yu, et al.” For OHIE: Blockchain Scaling Made Simple. “arXiv:1811.12628 (2018). [3] Rafael Pass, Lior Seeman, “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.