A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <s> The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor. It is shown that the problem is solvable for, and only for, n ≥ 3 m + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods. <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <s> Since the introduction of Bitcoin[Nak09] in 2009, and the multiple computer science and electronic cash innovations it brought, there has been great interest in the potential of decentralised cryptocurrencies. At the same time, implementation changes to the consensuscritical parts of Bitcoin must necessarily be handled very conservatively. As a result, Bitcoin has greater difficulty than other Internet protocols in adapting to new demands and accommodating new innovation. We propose a new technology, pegged sidechains, which enables bitcoins and other ledger assets to be transferred between multiple blockchains. This gives users access to new and innovative cryptocurrency systems using the assets they already own. By reusing Bitcoin’s currency, these systems can more easily interoperate with each other and with Bitcoin, avoiding the liquidity shortages and market fluctuations associated with new currencies. Since sidechains are separate systems, technical and economic innovation is not hindered. Despite bidirectional transferability between Bitcoin and pegged sidechains, they are isolated: in the case of a cryptographic break (or malicious design) in a sidechain, the damage is entirely confined to the sidechain itself. This paper lays out pegged sidechains, their implementation requirements, and the work needed to fully benefit from the future of interconnected blockchains. <s> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <s> The increasing popularity of blockchain-based cryptocurrencies has made scalability a primary and urgent concern. We analyze how fundamental and circumstantial bottlenecks in Bitcoin limit the ability of its current peer-to-peer overlay network to support substantially higher throughputs and lower latencies. Our results suggest that reparameterization of block size and intervals should be viewed only as a first increment toward achieving next-generation, high-load blockchain protocols, and major advances will additionally require a basic rethinking of technical approaches. We offer a structured perspective on the design space for such approaches. Within this perspective, we enumerate and briefly discuss a number of recently proposed protocol ideas and offer several new ideas and open challenges. <s> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <s> Cryptocurrencies, such as Bitcoin and 250 similar alt-coins, embody at their core a blockchain protocol --- a mechanism for a distributed network of computational nodes to periodically agree on a set of new transactions. Designing a secure blockchain protocol relies on an open challenge in security, that of designing a highly-scalable agreement protocol open to manipulation by byzantine or arbitrarily malicious nodes. Bitcoin's blockchain agreement protocol exhibits security, but does not scale: it processes 3--7 transactions per second at present, irrespective of the available computation capacity at hand. In this paper, we propose a new distributed agreement protocol for permission-less blockchains called ELASTICO. ELASTICO scales transaction rates almost linearly with available computation for mining: the more the computation power in the network, the higher the number of transaction blocks selected per unit time. ELASTICO is efficient in its network messages and tolerates byzantine adversaries of up to one-fourth of the total computational power. Technically, ELASTICO uniformly partitions or parallelizes the mining network (securely) into smaller committees, each of which processes a disjoint set of transactions (or "shards"). While sharding is common in non-byzantine settings, ELASTICO is the first candidate for a secure sharding protocol with presence of byzantine adversaries. Our scalability experiments on Amazon EC2 with up to $1, 600$ nodes confirm ELASTICO's theoretical scaling properties. <s> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <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> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <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> BIB006 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <s> Bias-resistant public randomness is a critical component in many (distributed) protocols. Generating public randomness is hard, however, because active adversaries may behave dishonestly to bias public random choices toward their advantage. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary. <s> BIB007 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <s> Blockchain technology, sometimes known by its applications like cryptocurrencies, suffers from the scalability problem mainly due to the unideal throughput of Byzantine fault tolerance consensus algorithms. Recently, many blockchains have been proposed to achieve scale-out throughput, i.e., the throughput of the system grows with the number of nodes. In this paper, we propose a novel scale-out blockchain system for the most considered type of ledgers, we call Value Transferring Ledgers, in which a transaction is a transfer of positive value from one node to another. In our system, nodes commonly agree on a main chain and individually generate their own chains. We propose a locally executable validation scheme with uncompromised validity and scalable throughput. Furthermore, a smart transacting algorithm is introduced so that the system is spontaneously sharded for individual transactions and achieves scale-out throughput. <s> BIB008 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Sharding for Scale-out Throughput <s> A major approach to overcoming the performance and scalability limitations of current blockchain protocols is to use sharding which is to split the overheads of processing transactions among multiple, smaller groups of nodes. These groups work in parallel to maximize performance while requiring significantly smaller communication, computation, and storage per node, allowing the system to scale to large networks. However, existing sharding-based blockchain protocols still require a linear amount of communication (in the number of participants) per transaction, and hence, attain only partially the potential benefits of sharding. We show that this introduces a major bottleneck to the throughput and latency of these protocols. Aside from the limited scalability, these protocols achieve weak security guarantees due to either a small fault resiliency (e.g., 1/8 and 1/4) or high failure probability, or they rely on strong assumptions (e.g., trusted setup) that limit their applicability to mainstream payment systems. We propose RapidChain, the first sharding-based public blockchain protocol that is resilient to Byzantine faults from up to a 1/3 fraction of its participants, and achieves complete sharding of the communication, computation, and storage overhead of processing transactions without assuming any trusted setup. RapidChain employs an optimal intra-committee consensus algorithm that can achieve very high throughputs via block pipelining, a novel gossiping protocol for large blocks, and a provably-secure reconfiguration mechanism to ensure robustness. Using an efficient cross-shard transaction verification technique, our protocol avoids gossiping transactions to the entire network. Our empirical evaluations suggest that RapidChain can process (and confirm) more than 7,300 tx/sec with an expected confirmation latency of roughly 8.7 seconds in a network of 4,000 nodes with an overwhelming time-to-failure of more than 4,500 years. <s> BIB009
Inspired by the infrastructures of distributed database and cloud, the concept of "sharding" BIB003 is also applied to the blockchain networks. As in side-chain networks, the approach of sharding partitions the global blockchain state into parallel subsets (i.e., shards), and each shard is maintained by a subgroup (i.e., committee) of nodes instead of the entire network. To improve the transaction throughput as well as retain the open-membership nature of permissionless blockchains, multiple BFT committees can be constructed following a similar procedure of the hybrid protocols (cf. Section V-C). As a result, the sharding protocols generally face the same challenges as in side-chain networks and hybrid consensus protocols, i.e., in providing secured shard formation to guarantee permissionless decentralization and in providing crossshard synchronization to guarantee atomic transactions. The study in BIB008 adopts the UTXO structure from Bitcoin and proposes the "spontaneous sharding" mechanism specifically for value transfer networks. Spontaneous sharding introduces a level of individual (spontaneous) chains for each node to maintain its own transactions of interest in a firstin-first-out fashion. It keeps a globally shared main chain, which only records the signed abstracts (i.e., header) of the blocks on each individual chain using a BFT-based consensus protocol. In this sense, spontaneous sharding is considered to be a transitional design from micro-payment channels to Figure 22 . Service oriented sharding with multi-chain structure (adapted from  ). PoW solution is required for generating a checkpoint. Users are able to propose new services by posting transactions to register the corresponding channels in a checkpoint block (see the sub-blockchain for the "intellectual property" service). sharding, since it admits only the transaction-sharding process but not the validator-sharding process. The validity of the proposed mechanism is built upon the assumption that all nodes in the network are rational. Namely, a node is interested in inspecting a transaction only if it needs that transaction to validate a subsequent transaction output that it receives. Only the rational owner of an unspent transaction is responsible for providing the proof to the validators (i.e., receivers). However, due to the existence of sharded individual chain, the protocol in BIB008 faces an unresolved problem of lacking compact proof (cf.  ), since for every proof, the validators have to trace back to the genesis block of each related individual chain. In  , a different approach of transaction sharding is proposed under the name of "Aspen". Instead of maintaining an individual chain for each node, Aspens organizes transactions into sub-blockchains (see Figure 22 ) based on the type of services related to each transaction. It introduces periodic checkpoint blocks for synchronizing sub-blockchains (cf. the anchor points in Casper BIB006 ). Aspen is instantiated on Bitcoin-NG  and only requires the checkpoint blocks to be generated upon PoW-puzzle solution to determine the proposal leaders of micro-blocks in each service channel (i.e., sub-blockchain). To avoid designing complex proofs of crosschain transactions (cf. BIB002 , BIB008 ), Aspen does not allow two-way transfer between channels and requires that each fund is only spendable in a specific channel. In BIB004 , a different sharding protocol named "Elastico" is proposed with the emphasis on the process of validator sharding through dynamically forming multiple BFTcommittees. Elastico organizes the transaction approving process by epochs, and in each epoch a number of committees are formed in parallel based on the PoW-puzzle solution in a similar way to the proof of membership in BIB005 . The study in BIB004 proposes a mechanism of generating distributive epoch randomness by using one network-level BFT committee, which determines a subset of hash values randomly provided by its members. The committee can run any non-leader interactive consistency protocol, e.g., BIB001 to reach an agreement on such a single set to generate the public random number. In an epoch, the candidates of the committees have to solve the PoW puzzle based on the public random number. Elastico also uses the least-significant bits of the PoW solution (i.e., the hash value) to group the candidate nodes into different committees. Thus, this procedure guarantees that the committees are randomly formed and unpredictable. Meanwhile, to avoid designing complex proofs of cross-shard transactions (cf. BIB008 ), Elastico relies on the network-level committee to merge the locally agreed values in each committee into a single chain. The network-level committee first checks whether the values received from each local committee are signed by their majority members. If so, it merges the received values into an ordered union and runs a similar BFT protocol to approve the final result with signatures by the committee majority. By limiting the burden of quadratic message complexity within shard committees of small size, Elastico is able to achieve roughly O(n) message complexity and provide almost linear throughput scalability in terms of the hash power in the network. Also, compared with the aforementioned throughputscalable protocols, e.g.,  , BIB002 , BIB008 , Elastico does not limit itself to value transfer networks and can be applied to generic data services with non-spendable transactions. By enabling parallelization of both data storage and network consensus, protocols aiming at "full sharding" are proposed in  , BIB009 . In  , a protocol named "OmniLedger" is designed to provide "statistically representative" shards for permissionless transaction processing. As in BIB004 , Om-niLedger is built upon two levels of epoch-based Byzantine agreement processes, with the network level being responsible for epoch randomness generation and the shard level for intra-committee consensus. In the network level, a global identity blockchain is adopted and can only be extended by the network-level leaders. Any node that wants to join a committee has to register to this global blockchain through a Sybilproof identity establishment mechanism. Especially, such a mechanism is not limited to PoW and can be replaced by other means, e.g., PoS. At the beginning of an epoch, all the nodes with established identities are required to run an interactive consistency protocol by sharing with each other a "ticket" based on a gossip protocol. The ticket is generated as the hash value of the node's address and the header of the identity blockchain. The node that generates the smallest ticket will be elected as the network-level leader. The leader is expected to run a verifiable random function (e.g., RandHound BIB007 ) and generate a global random string with a valid proof. Upon reception of this random string, other registered nodes are able to compute a permutation based on this string as well as their own identity, and then finish the assignment of shard committees by subdividing their results into equally-sized buckets. In addition, OmniLedger proposes to swap gradually in-and-out committee members per epoch. This design not only allows bootstrapping new nodes joining the network, but also avoids excessive message overhead and latency due to complete shard reconstruction (cf. Elastico). In the shard level, a committee can employ any leader-based BFT protocol (e.g., ByzCoin BIB005 ) to provide intra-shard consensus. In BIB009 , another epoch-based, two-level-BFT protocol for full sharding is proposed under the name "RapidChain". In the network level, RapidChain requires a reference BFTcommittee to run a distributed randomness generation protocol similar to BIB004 and generate a public random string to initialize the formation of shard-level committees. As in  , the shard-level committee reconfiguration in RapidChain only reorganizes a subset of committee members at each epoch to ensure operability during committee transition. At the bootstrapping stage in a network of n nodes, the established identity of a node is mapped to a random position in the range [0, 1) by using the hash function. Then, with some constant k (i.e., committee size), the range is partitioned into n/k regions, and the shard-level committees are consequently formed based on this region partition. At the reconfiguration stage, Rapid-Chain defines the set of the first half shard-level committees with more active members as the "active committee set". The network-level committee is responsible for assigning new nodes into the active shard-level committees uniformly at random. After that, it shuffles a constant number of members from every existing committee and randomly reassign them to other committees. On the shard level, RapidChain requires the members of each BFT-committee to run also the distributed randomness generation protocol and generate a local random string. Then, the committee members compete for the leader election through solving the standard PoW puzzle based on the local random string. The members elect a node with the smallest PoW solution by gossiping their votes with signatures to each other. Then, the BFT protocol will be led by that node to reach the intra-shard consensus for transaction commitment. As in BIB008 ,  , full sharding also partitions the storage of the blockchain state into multiple shards (e.g., local ledgers). Then, the full sharding protocols  , BIB009 are characterized by their ways of handling cross-shard transactions to guarantee atomic transaction commitment. In  , OmniLedger uses UTXO to represent the client's balance state. Therefore, a cross-shard transaction is always associated with at least an input shard as well as an output shard (see Figure 23(a) ). Om-niLedger adopts a lock-unlock-abort mechanism by requiring the input shard of a cross-shard transaction to "lock" the input first. Namely, the leader of the input shard has to provide a proof-of-acceptance in the form of Merkel proof before the corresponding transaction can be committed. If the transaction is found to be invalid, the input shard creates a proof-ofrejection in a similar form by using a designated bit to indicate an acceptance or rejection. Even with a proof-of-acceptance, the receiving client still cannot freely spend the UTXO. The receiver is required to send an unlock-to-commit transaction with that proof to the output-shard committee. Until the output shard validates this special transaction and includes it into the new block, the receiver is able to spend the UTXO of the original transaction. In BIB009 , RapidChain proposes a different approach of committing cross-shard transaction, which does not require a receiver to collect proofs from the input shards. Instead, for any input value of a transaction from a different shard, the output-shard leader is required to create a single-in-singleout transaction where the output is equal to the input of the original transaction. By doing so, the output committee tries to create a local record of the input and holds the input value in escrow. To confirm the escrow, the output-shard leader is responsible for sending this new transaction back to the input-shard committee for approval. After the input committee adds this transaction into its ledger, the output-shard leader will create a final transaction, with the UTXO of the escrow transaction being the input and the same outputs of the original Input shard Output shard  Move the inpu ts to the output shard (b) Figure 23 . Atomic cross-shard transaction protocols in (a) OmniLedger  and (b) RapidChain BIB009 . In the two protocols, different parties are responsible for collecting input-shard approvals for committing transactions. transaction. After the output-shard committee adds the final transaction to its ledger, the transfer process is finished and the corresponding UTXO becomes spendable by the receivers. An illustrative comparison between the protocols of crossshard transactions in OmniLedger and RapidChain is given by Figure 23 .