Scaling Bitcoin’s POW (Part 1/2)



  • This is the second article of the series that focuses on the problem of blockchain scalability. In our previous article titled “What does “scalability” really mean in Blockchain?”, we provided a comprehensive review on how the problem had been tackled so far and systematically defined the so-called “scalable blockchains”.

    Note that a few years back, the problem of blockchain scalability was all about answering the question “Can we achieve a higher TPS for Bitcoin?”. Its research has resulted in the studies of various problems in the domain of blockchain scalability as we can see today.

    This article goes deeper into the discussion of the topic of “Scaling Bitcoin” which is the first section of our last article. It is aimed to show readers why exactly is Bitcoin not scalable and explain the key ideas behind some of the remarkable work that attempted to scale Bitcoin.

    The proof-of-work chain is a solution to the Byzantine Generals’ Problem.
    ……
    They don’t particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.
    They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work is so difficult, it’s expected to take 10 minutes of them all working at once before one of them finds a solution.
    .……
    — — Satoshi Nakamoto [1]

    POW is not scalable, as it was not designed to be. As explained in the quotes that he used to explain POW to James A. Donald, Nakamoto was heavily focusing on solving the problem of Byzantine Generals Problem without really caring too much about throughput and scalability. However, as Bitcoin received more and more attention, its throughput limitation of 7tx/s has become a major obstacle for the massive adoption of Bitcoin as a real “currency”.

    Since then, we have seen numerous proposals of enlarging the block size, including Bitcoin XT, Bitcoin Unlimited, and Bitcoin ABC (which later became Bitcoin Cash and Bitcoin SV). Such proposals have caused heavy debate in the community. The debate was initially focused on the higher storage and bandwidth requirement as well as the possible centralization due to a larger block size but not the risk in security. In fact, although it is vaguely realized that larger blocks will result in more forks in the system, which will cause longer confirmation time and higher vulnerability to double spending attacks, rigorous analysis of the degradation only comes later in [2], [3]. In these researches, it is proven that the security of Bitcoin POW decreases as the throughput increases.

    Why is that so?

    POW is a race, which is used as a fair way to randomly select a block generator (a miner) in a certain period of time (the next cycle of POW). The chance of a miner being selected is proportional to some unforgeable resources spent on mining by the miner. In the case of BitCoin, it is the computational power of calculating a specific hash function. Note that the fairness is crucial as it determines the security of the system.

    Any unfairness in the race could be exploited by malicious nodes to attack the system. With a truly fair POW, malicious nodes could carry out double spending attacks only if they win the race over all other competitors, or in other words, they would need to control over 50% of the total mining power.

    To explain how the fairness is formed in BitCoin POW, we first need to understand its working mechanism. In each cycle of Bitcoin POW, the block synchronization and validation and POW racing are designed to be a cascade process as illustrated by the figure below. In other words, essentially, after a new block is generated, all miners should first synchronize and validate this block, then start the race of POW upon it, i.e., to mine on it.

    alt text

    Nakamoto used two tricks to assure the fairness of the POW race:

    1. An incentive mechanism with game theoretical arguments was introduced to motivate miners to try their best to synchronize with the newest block and immediately broadcast the block as soon as they found one.
    2. Each POW cycle (or the block interval) was set to be significantly larger than the time required for synchronization, so that most miners could be considered as starting the race relatively at the same time. In other words, the ratio r = sync time / block interval was kept small.

    Let’s now take a look at the ratio r. First, to achieve high throughput, we want r tending to 1 since a larger r means that more bandwidth of the network is used for the propagation of transactions. However, as r increases, two things will happen that decrease the fairness of POW:

    1. There will be a longer period that the network is not fully synced with the newest block. Consequently, some nodes can start the POW race substantially earlier than other nodes, resulting in the race becoming less fair.
    2. The probability of finding a correct hash follows a Poisson distribution, which will increase as r grows large. Then, there might be multiple valid blocks created during the sync time by different miners who are not aware of the others. As a result, the “forks” are created. The hash power put on mining a wrong fork can be considered as a waste since the resulting chain is likely to be discarded. The more forks exist, the more hash power would likely be wasted, resulting in less hash power put on the actual race. Therefore, it would be easier for an attacker to win the race to carry out the double-spending attack.

    It can be seen that a larger ratio r would result in the POW race being less fair, which implicates less security since the race is more likely to be manipulated. It is a dilemma for POW we cannot get around and that is why we claim that Bitcoin is not scalable.

    Hypothesis mining

    Let’s assume that we enlarge the block size to 1GB. Then, once a new block is published in the network, a miner would have to download the whole block and validate it and only after that he could safely mine on it. This process would cost the miner a few minutes. As we discussed earlier, the resulting blockchain system would become less secure due to the dramatic increase of the ratio r.

    Here is something that might pop up in your mind. “Wait a minute, I know the protocol of Bitcoin. A miner could start to mine on the new block once he/she gets and validates the header and doesn’t need to download the whole block!” Indeed, this kind of “hypothesis mining” has been widely used by miners in practice. It is based on the assumption that it be unlikely that a miner would publish a block with a valid header but containing invalid transactions. The assumption holds for the current setting of BitCoin due to the fact that publishing an invalid block to mislead other miners can only get the publisher a tiny advantage in the current POW race since the block size is small.

    If the block became bigger, the publisher would get a larger reward by misleading other miners (since they will waste more mining power on the wrong block) and the equilibrium might be broken. As invalid blocks will eventually be detected and discarded, “hypothesis mining” is not actually contributing to the mining power of the “longest valid chain” and the security of the system.

    Scaling POW

    In fact, the “hypothesis mining” we just described is very close to the solution to scaling POW. The key idea is to break the cascade process within each POW cycle so that the sync+validation and POW race can be carried out in parallel.

    In particular, miners first synchronize the header of the incoming new block and check whether the publisher has truly solved the puzzle. After that, they can start to run POW based on the block while keeping synchronizing and validating all the transactions. However, what if the block includes an invalid transaction? In this case, the hash power would be wasted on mining this invalid block. Well, how about we use some new mechanism so that the mining power wouldn’t be wasted?

    Leader/committee selection

    Bitcoin-NG [4] provided a solution to answer the above question. In the design, a miner first broadcasts a header containing the POW proof (called key blocks in the paper) to claim that he/she is the leader of this round of POW. The miner then packs transactions in some fixed sized micro blocks without POW, but with his signature and broadcasts the blocks. The micro blocks are synchronized and validated one by one by other miners, while they are mining and competing for the next POW puzzle.

    The problem here is that a malicious leader could produce two conflicting micro blocks to cause inconsistency in the network with no cost. To penalize such behaviour, the algorithm allows any node to collect the proof of this misbehavior and use a special type of transactions, called “poison transactions”, to take away the mining reward of the leader who signs two conflicting micro blocks.

    alt_text

    Image from https://www.coindesk.com/cornell-research-blockchain-problems-bitcoin-ng.

    Bitcoin-NG parallels POW and sync+validation by “reaching consensus on the leader and then letting leader decide the transactions”. Let’s call this approach “leader selection”. Then, there are other scalable POW algorithms based on leader selection, like Hybrid consensus [2] and Byzcoin [5], in which the leader is no longer a single node, but a group of nodes, called a committee.

    A committee can easily be selected via POW in the similar fashion as selecting one leader: while a miner solves the puzzle, instead of being the sole leader of this POW round, he joins a committee together with the previous k-1 miners who have also solved the puzzle. This committee then use a BFT algorithm to determine the blocks of this round. In the meantime, the POW race for the next committee proceeds.

    To deal with the invalid transactions proposed by malicious committees, we could play with the committee size, i.e., the value of k. Then, k should be chosen to be sufficiently large so that the probability of the majority of the committee being malicious is negligible. Then, the probability of a fork, i.e., wasted mining power, is negligible. The cost is the additional delay and communication complexity of the BFT algorithm, which will grow with the value of k.

    Why we have not seen any implementation?

    Although the leader/committee-selection based POW algorithms have drawn a lot of attention from academia, they have never been considered as popular candidates in the roadmap for scaling Bitcoin, at least not as popular as Segwit [6], large blocks, or Lightning Network [7]. It is mainly due to the fact that these algorithms alter the incentive mechanism and/or the security assumption of Bitcoin, which is not welcomed by the Bitcoin community.

    The incentive mechanism of Bitcoin-NG is different from that of Bitcoin in two parts. First, the “poison transaction” is used to punish the malicious leaders. To allow this mechanism, the block reward should be locked for some rounds, e.g., 100 rounds, until they can be safely spent. Second, in Bitcoin NG, the micro blocks are not considered in the longest chain rule. Hence, there is an incentive for the leader to not include the micro blocks from the previous leader. In that case, he could save his bandwidth and validation effort and later include those transactions himself to gain transaction fee. Hence, instead of giving the transaction fee to the leader who includes the transaction in the micro block, the fee should be split between him and the next round leader.

    For Hybrid Consensus and Byzcoin, as BFT is used for the committee to reach consensus, the security assumption then becomes “malicious nodes could not have more than 33% mining power”, which is different from the 50% assumption of Bitcoin. (Note that the real threshold is 25% due to the risk of selfish mining [8], which is even lower than 33%.)

    Relationship with POS Algorithms

    Leader/committee selection was also used in some recently proposed Proof-of-Stake (POS) algorithms. In these algorithms, some random number generator is used to select the leader and committee every round without a run-time like POW. Hence, there is no need to parallel the consensus with the synchronization and the bandwidth could be fully utilized.

    Some algorithms like Snow White [9] and Ouroboros [10] prefer a sole leader and some algorithms like Dfinity [11] and ALGORAND [12] prefer a committee. There is a trade-off in the communication complexity (within the committee) and confirmation time (due to a higher probability of forks). Then, in terms of throughput, these algorithms should be comparable to their counterparts in POW, e.g., Bitcoin-NG, Byzcoin, and Hybrid Consensus.

    In the next part of this article, we will introduce another family of algorithms that use DAG to parallel sync+validation and POW so as to scale POW.

    References

    [1] https://satoshi.nakamotoinstitute.org/emails/cryptography/11/

    [2] Pass, Rafael, and Elaine Shi. “Hybrid consensus: Efficient consensus in the permissionless model.” 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.

    [3] Sompolinsky, Yonatan, and Aviv Zohar. “Secure high-rate transaction processing in bitcoin.” International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2015.

    [4] Eyal, Ittay, et al. “Bitcoin-ng: A scalable blockchain protocol.” 13th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 16). 2016.

    [5] Kogias, Eleftherios Kokoris, et al. “Enhancing bitcoin security and performance with strong consistency via collective signing.” 25th {USENIX} Security Symposium ({USENIX} Security 16). 2016.

    [6] Segregated Witness (BIP-141)

    [7] Poon, Joseph, and Thaddeus Dryja. “The bitcoin lightning network: Scalable off-chain instant payments.” (2016).

    [8] Eyal, Ittay, and Emin Gün Sirer. “Majority is not enough: Bitcoin mining is vulnerable.” Communications of the ACM61.7 (2018): 95–102.

    [9] Daian, Phil, Rafael Pass, and Elaine Shi. “Snow white: Robustly reconfigurable consensus and applications to provably secure proofs of stake.”International Conference on Financial Cryptography and Data Security. Springer, St. Kitts, 2019.

    [10] Kiayias, Aggelos, et al. “Ouroboros: A provably secure proof-of-stake blockchain protocol.” Annual International Cryptology Conference. Springer, Cham, 2017.

    [11] https://dfinity.org/

    [12] Gilad, Yossi, et al. “Algorand: Scaling byzantine agreements for cryptocurrencies.” Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 2017.