A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2p faster to 24p slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults. <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> We propose a new protocol for a cryptocurrency, that builds upon the Bitcoin protocol by combining its Proof of Work component with a Proof of Stake type of system. Our Proof of Activity protocol offers good security against possibly practical attacks on Bitcoin, and has a relatively low penalty in terms of network communication and storage space. <s> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> Bitcoin cryptocurrency demonstrated the utility of global consensus across thousands of nodes, changing the world of digital transactions forever. In the early days of Bitcoin, the performance of its probabilistic proof-of-work (PoW) based consensus fabric, also known as blockchain, was not a major issue. Bitcoin became a success story, despite its consensus latencies on the order of an hour and the theoretical peak throughput of only up to 7 transactions per second. <s> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two of its fundamental properties which we call common prefix and chain quality in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the adversary relative to network synchronicity; we show our results to be tight under high synchronization. <s> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> The Bitcoin system only provides eventual consistency. For everyday life, the time to confirm a Bitcoin transaction is prohibitively slow. In this paper we propose a new system, built on the Bitcoin blockchain, which enables strong consistency. Our system, PeerCensus, acts as a certification authority, manages peer identities in a peer-to-peer network, and ultimately enhances Bitcoin and similar systems with strong consistency. Our extensive analysis shows that PeerCensus is in a secure state with high probability. We also show how Discoin, a Bitcoin variant that decouples block creation and transaction confirmation, can be built on top of PeerCensus, enabling real-time payments. Unlike Bitcoin, once transactions in Discoin are committed, they stay committed. <s> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> Consensus, or state machine replication is a foundational building block of distributed systems and modern cryptography. Consensus in the classical, "permissioned" setting has been extensively studied in the 30 years of distributed systems literature. Recent developments in Bitcoin and other decentralized cryptocurrencies popularized a new form of consensus in a "permissionless" setting, where anyone can join and leave dynamically, and there is no a-priori knowledge of the number of consensus nodes. So far, however, all known permissionless consensus protocols assume network synchrony, i.e., the protocol must know an upper bound of the network's delay, and transactions confirm slower than this a-priori upper bound. ::: ::: We initiate the study of the feasibilities and infeasibilities of achieving responsiveness in permissionless consensus. In a responsive protocol, the transaction confirmation time depends only on the actual network delay, but not on any a-priori known upper bound such as a synchronous round. Classical protocols in the partial synchronous and asynchronous models naturally achieve responsiveness, since the protocol does not even know any delay upper bound. Unfortunately, we show that in the permissionless setting, consensus is impossible in the asynchronous or partially synchronous models. ::: ::: On the positive side, we construct a protocol called Hybrid Consensus by combining classical-style and blockchain-style consensus. Hybrid Consensus shows that responsiveness is nonetheless possible to achieve in permissionless consensus (assuming proof-of-work) when 1) the protocol knows an upper bound on the network delay; 2) we allow a non-responsive warmup period after which transaction confirmation can become responsive; 3) honesty has some stickiness, i.e., it takes a short while for an adversary to corrupt a node or put it to sleep; and 4) less than 1/3 of the nodes are corrupt. We show that all these conditions are in fact necessary - if only one of them is violated, responsiveness would have been impossible. Our work makes a step forward in our understanding of the permissionless model and its differences and relations to classical consensus. <s> BIB006 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds. ByzCoin achieves Byzantine consensus while preserving Bitcoin's open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin employs communication trees to optimize transaction commitment and verification under normal operation while guaranteeing safety and liveness under Byzantine faults, up to a near-optimal tolerance of f faulty group members among 3f + 2 total. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. Tree-structured communication further reduces this latency to less than 30 seconds. Due to these optimizations, ByzCoin achieves a throughput higher than PayPal currently handles, with a confirmation latency of 15-20 seconds. <s> BIB007 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> We introduce Casper, a proof of stake-based finality system which overlays an existing proof of work blockchain. Casper is a partial consensus mechanism combining proof of stake algorithm research and Byzantine fault tolerant consensus theory. We introduce our system, prove some desirable features, and show defenses against long range revisions and catastrophic crashes. The Casper overlay provides almost any proof of work chain with additional protections against block reversions. <s> BIB008 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Hybrid Consensus Protocols <s> Algorand is a new cryptocurrency that confirms transactions with latency on the order of a minute while scaling to many users. Algorand ensures that users never have divergent views of confirmed transactions, even if some of the users are malicious and the network is temporarily partitioned. In contrast, existing cryptocurrencies allow for temporary forks and therefore require a long time, on the order of an hour, to confirm transactions with high confidence. Algorand uses a new Byzantine Agreement (BA) protocol to reach consensus among users on the next set of transactions. To scale the consensus to many users, Algorand uses a novel mechanism based on Verifiable Random Functions that allows users to privately check whether they are selected to participate in the BA to agree on the next set of transactions, and to include a proof of their selection in their network messages. In Algorand's BA protocol, users do not keep any private state except for their private keys, which allows Algorand to replace participants immediately after they send a message. This mitigates targeted attacks on chosen participants after their identity is revealed. We implement Algorand and evaluate its performance on 1,000 EC2 virtual machines, simulating up to 500,000 users. Experimental results show that Algorand confirms transactions in under a minute, achieves 125x Bitcoin's throughput, and incurs almost no penalty for scaling to more users. <s> BIB009
Despite the unique characteristics of permissionless consensus protocols, public blockchain networks are known to be limited in performance (e.g., transaction throughput) due to the scalability-performance tradeoff BIB003 . To boost permissionless consensus without undermining the inherent features such as scalability, a plausible approach is to combine a permissionless consensus mechanism (e.g., Nakamoto protocol) with a fast permissioned consensus protocol (e.g., BFT). Following our previous discussion (cf. PoA BIB002 and Casper BIB008 ), we study in this subsection how a standard permissionless consensus protocol can be improved by incorporating (part of) another consensus protocol in the blockchain networks. In  , the protocol "Bitcoin-NG" is proposed to extend the PoW-based Nakamoto protocols. The prominent feature of Bitcoin-NG is to decouple the consensus process in a blockchain network (e.g., Bitcoin network) into two planes: leader election and transaction serialization. To bootstrap the transaction throughput, the protocol introduces two types of blocks, namely, the key blocks that require a PoW puzzle solution for leader election and the microblocks that require no puzzle solution and are used for transaction serialization. The time interval between two key blocks is known as an epoch. In an epoch, the same leader is allowed to publish microblocks with the limited rate and block size. Although operation decoupling in Bitcoin-NG does not ensure strong consistency, it paves the way for incorporating additional mechanisms on the basis of standard Nakamoto protocols. Following the methodology of  , hybrid consensus mechanisms atop Nakamoto protocols are proposed in BIB005 , BIB006 with the goal of providing strong consistency and immediate finality. In BIB005 , the "PeerCensus" protocol is proposed by decoupling block creation and transaction committing/confirmation. PeerCensus consists of two core components, namely, a PoW scheme named as BlockChain (BC) and a BFT-based scheme named as Chain Agreement (CA). With the proposed BC protocol, nodes acquire the voting right of the CA protocol when they propose new blocks through PoW and are approved by the committee of CA. The CA protocol is adapted from BFT protocols such as PBFT BIB001 and the Secure Group Membership Protocol (SGMP)  . Through the four stages of propose, pre-prepare, prepare, and commit of BFT protocols (cf. Figure 6) , CA designates the miner of the newest block in the chain as the leader for the next block proposal. The leader proposes one from the multiple candidate blocks obtained in BC. The peer nodes in the committee extend the pre-prepare stage with an operation of block validation. The design of PeerCensus ensures that committing transactions (i.e., CA) is independent of block generation (i.e., BC). Therefore, no forking occurs in the condition of honest majority and strong consistency is guaranteed. In BIB006 , a hybrid consensus protocol is proposed by combining the data framework of two-type blocks in Bitcoin-NG and the hybrid PoW-BFT design in PeerCensus. As in PeerCensus, the Nakamoto protocol is used to construct a "snailchain", which is allowed to commit transactions from a specific mempool of outstanding transactions known as the "snailpool". Following the quantitative analysis of the common prefix blocks in a chain in BIB004 , only a fixed number of miners whose recently minted blocks are a certain number of blocks deep in the chain can be used to form the committee for the BFT protocol. In contrast to PeerCensus, the BFT committee of miners in the proposed protocol has no influence on how the next block on the snailchain is determined. Instead, it is responsible for committing transactions from an independent mempool known as the "txpool". For this reason, the transactions approved by the BFT protocol are Figure 19 . Illustration of BFT-committee formation with weighted voting power. Valid weights are only credited to the miners of the blocks in the sliding window (adapted from BIB007 ). committed off the snailchain without relying on any mining mechanism. In this sense, these transactions can be considered similar to those in the microblocks of Bitcoin-NG. The hybrid consensus protocol in BIB006 explicitly addresses the problem of BFT-committee scalability in PeerCensus and provides a secured (with theoretical proof) consensus property of immediate finality. Namely, the transaction confirmation time from the txpool only depends on the network's actual propagation delay. The method of using Nakamoto protocols to select nodes into a BFT committee is also known as the proof of membership mechanism BIB007 . A sliding-window mechanism is proposed in BIB007 to generalize the mechanisms of dynamic BFT-committee selection in BIB005 , BIB006 . As illustrated in Figure 19 , the BFT committee is maintained by a fixed-size sliding window over the PoW-based blockchain. The sliding window moves forward along the blockchain as new blocks are appended/confirmed. Consensus nodes minting multiple blocks in the window are allowed to create the same number of pseudo-identities in the BFT consensus process to gain the proportional voting power. For hybrid consensus using BFT protocols to guarantee strong consistency, a natural thinking is to replace the Nakamoto protocols with virtual mining (e.g., PoS) for selecting the leader or committee in BFT-consensus processes. A typical example for such an approach can be found in the "Tendermint" protocol  , where a node joins the BFT committee of block validators by posting a bond-deposit transaction. The validator no longer needs to prove its membership by competing for the PoW-puzzle solution. Alternatively, its voting power is equal to the amount of stake measured in bonded tokens. Meanwhile, instead of randomly electing the leader of block proposal in the committee (cf.  ), Tendermint adopts a round-robin scheme to designate the leader in the committee. The similar design can be found in a number of recent proposals such as Proof of Authority (PoAu) [165] and Delegated Proof of Stake (DPoS)  . To generalize the mechanisms of BFT-committee selection based on virtual mining, the authors in BIB009 further propose a consensus protocol called "Algorand". Like the other hybrid protocols, Algorand relies on BFT algorithms for committing transactions. It assumes a verifiable random function to generate a publicly verifiable BFT-committee of random nodes, just as in BIB002 . The probability for a node to be selected in the committee is in proportion to the ratio between Figure 20 . Illustration of performance and scalability of different consensus protocol families (see also the discussion in BIB003 ). its own stake and the overall tokens in the network. For leader election, Algorand allows multiple nodes to propose new blocks. Subsequently, an order of the block proposals is obtained through hashing the random function output with the nodes' identities specified by their stake. Only the proposal with the highest priority will be propagated across the network. In Table V , we provide a summary of the virtual-mining mechanisms and the hybrid consensus protocols discussed in this section.