A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> We formalize the notion of a proof of work (POW). In many cryptographic protocols, a prover seeks to convince a verifier that she possesses knowledge of a secret or that a certain mathematical relation holds true. By contrast, in a POW, a prover demonstrates to a verifier that she has performed a certain amount of computational work in a specified interval of time. POWs have served as the basis of a number of security protocols in the literature, but have hitherto lacked careful characterization. In this paper, we offer definitions treating the notion of a POW and related concepts. <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> We efficiently combine unpredictability and verifiability by extending the Goldreich-Goldwasser-Micali (1986) construction of pseudorandom functions f/sub s/ from a secret seed s, so that knowledge of s not only enables one to evaluate f/sub s/ at any point x, but also to provide an NP-proof that the value f/sub s/(x) is indeed correct without compromising the unpredictability of f/sub s/ at any other point for which no such a proof was provided. <s> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <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> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> An argument system for NP is a proof system that allows efficient verification of NP statements, given proofs produced by an untrusted yet computationally-bounded prover. Such a system is non-interactive and publicly-verifiable if, after a trusted party publishes a proving key and a verification key, anyone can use the proving key to generate non-interactive proofs for adaptively-chosen NP statements, and proofs can be verified by anyone by using the verification key. <s> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <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> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> One of the current problems of peer-to-peer-based file storage systems like Freenet is missing participation, especially of storage providers. Users are expected to contribute storage resources but may have little incentive to do so. In this paper we propose KopperCoin, a token system inspired by Bitcoin’s blockchain which can be integrated into a peer-to-peer file storage system. In contrast to Bitcoin, KopperCoin does not rely on a proof of work (PoW) but instead on a proof of retrievability (PoR). Thus it is not computationally expensive and instead requires participants to contribute file storage to maintain the network. Participants can earn digital tokens by providing storage to other users, and by allowing other participants in the network to download files. These tokens serve as a payment mechanism. Thus we provide direct reward to participants contributing storage resources. <s> BIB006 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> Besides attracting a billion dollar economy, Bitcoin revolutionized the field of digital currencies and influenced many adjacent areas. This also induced significant scientific interest. In this survey, we unroll and structure the manyfold results and research directions. We start by introducing the Bitcoin protocol and its building blocks. From there we continue to explore the design space by discussing existing contributions and results. In the process, we deduce the fundamental structures and insights at the core of the Bitcoin protocol and its applications. As we show and discuss, many key ideas are likewise applicable in various other fields, so that their impact reaches far beyond Bitcoin itself. <s> BIB007 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> We introduce a new class of protocols called Proofs of Work or Knowledge PoWorKs. In a PoWorK, a prover can convince a verifier that she has either performed work or that she possesses knowledge of a witness to a public statement without the verifier being able to distinguish which of the two has taken place. We formalize PoWorK in terms of three properties, completeness, f-soundness and indistinguishability where f is a function that determines the tightness of the proof of work aspect and present a construction that transforms 3-move HVZK protocols into 3-move public-coin PoWorKs. To formalize the work aspect in a PoWorKi¾?protocol we define cryptographic puzzles that adhere to certain uniformity conditions, which may also be of independent interest. We instantiate our puzzles in the random oracle RO model as well as via constructing "dense" versions of suitably hard one-way functions. ::: ::: We then showcase PoWorKi¾?protocols by presenting a number of applications. We first show how non-interactive PoWorKs can be used to reduce spam email by forcing users sending an e-mail to either prove to the mail server they are approved contacts of the recipient or to perform computational work. As opposed to previous approaches that applied proofs of work to this problem, our proposal of using PoWorKs is privacy-preserving as it hides the list of the receiver's approved contacts from the mail server. Our second application, shows how PoWorK can be used to compose cryptocurrencies that are based on proofs of work "Bitcoin-like" with cryptocurrencies that are based on knowledge relations these include cryptocurrencies that are based on "proof of stake", and others. The resulting PoWorK-based cryptocurrency inherits the robustness properties of the underlying two systems while PoWorK-indistinguishability ensures a uniform population of miners. Finally, we show that PoWorKi¾?protocols imply straight-line quasi-polynomial simulatable arguments of knowledge and based on our construction we obtain an efficient straight-line concurrent 3-move statistically quasi-polynomial simulatable argument of knowledge. <s> BIB008 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two. <s> BIB009 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Permissionless Consensus via Zero-Knowledge Proofs <s> Blockchain technologies are gaining massive momentum in the last few years. Blockchains are distributed ledgers that enable parties who do not fully trust each other to maintain a set of global states. The parties agree on the existence, values and histories of the states. As the technology landscape is expanding rapidly, it is both important and challenging to have a firm grasp of what the core technologies have to offer, especially with respect to their data processing capabilities. In this paper, we first survey the state of the art, focusing on private blockchains (in which parties are authenticated). We analyze both in-production and research systems in four dimensions: distributed ledger, cryptography, consensus protocol and smart contract. We then present BLOCKBENCH, a benchmarking framework for understanding performance of private blockchains against data processing workloads. We conduct a comprehensive evaluation of three major blockchain systems based on BLOCKBENCH, namely Ethereum, Parity and Hyperledger Fabric. The results demonstrate several trade-offs in the design space, as well as big performance gaps between blockchain and database systems. Drawing from design principles of database systems, we discuss several research directions for bringing blockchain performance closer to the realm of databases. <s> BIB010
For traditional BFT consensus protocols, e.g., Byzantine Paxos  and PBFT BIB003 , it is generally necessary to assume a fully connected topology among the consensus nodes as well as a leader-peer hierarchy for block proposal. The BFT consensus process is organized explicitly in rounds of threeway handshakes, thus synchronization between nodes with bounded execution time and message latency is also required. As illustrated in Figure 6 , only the leader is responsible for proposing new blocks to a consortium of peer nodes at the proposal (pre-prepare) phase. This is followed by two all-to-all messaging phases, where a peer node only accepts the proposal (i.e., commit) when it receives more than a certain number of proposal approvals from the other peers (e.g., ⌊ n+f +1 3 ⌋ with PBFT for a network of n honest nodes and f Byzantine nodes). These classical state-machine replication approaches guarantee the properties of deterministic agreement and liveness in Byzantine environment, and are well-known for their low processing latency BIB005 . However, the characteristics of leader-peer hierarchy and high communication complexity in Θ(n 2 ) [69] naturally require the BFT-based blockchain consensus protocols to be implemented in a small-scale permissioned network with centralized admission control. In order to achieve full decentralization and high consensus scalability, alternative approaches such as Nakamoto protocols become critical in the design of blockchain's consensus layer. According to our discussion in Section II-E, the primary functionality of PoW in the Nakamoto protocol is to simulate the leader election in the traditional BFT protocols. The PoW process abstracted by Definition 1 is essentially a verifiable process of weighted random coin-tossing, where the probability of winning is no longer uniformly associated with the nodes' identities but in proportion to the resources, e.g., hashrate casted by the nodes. Then, we can consider that each new block is generated by a time-independent "lottery", where the probability of being elected as the leader for block proposal depends on the ratio between the casted resource of a node (or a node coalition) and the total resources presented in the entire network. Let w i denote the resource held by node i in a network of node set N , then, the probability of node i winning the leader-election in a PoW-like process should follow: where w i generalizes the share of any verifiable resource such as computational power  , memory  , storage BIB006 , etc. In contrast to the BFT protocols, the peer nodes accept the received block proposal following the longest-chain-rule after they verify the validity of the block and the transactions therein. Since no all-to-all messaging phase is needed, the Nakamoto protocol may have a much smaller message complexity Ω(n) when the majority of the peers are honest  . As the core component of the Nakamoto protocol, the PoW scheme originates from the idea of indirectly validating nodes' identities in pseudonymous P2P networks through an identity pricing mechanism BIB001 ,  . More specifically, the PoW scheme described by Definition 1 is originally designed to measure the voting power or the trustworthiness of a node according to the constrained resources presented by the node in the P2P network. Thus, the tolerable fraction of Byzantine nodes in BFT protocols is replaced by a limited fraction of the total computational power of the network  . Compared with the original design, the PoW scheme in blockchain networks is no longer used for direct identity verification between peers. Instead, the PoW processes of all the nodes in a blockchain network are expected to collectively simulate a publicly verifiable random function to elect the leader of block proposal following the distribution given by BIB010 . Based on such a design paradigm, PoW can be generalized into the framework of Proof-of-Concepts (PoX) (cf. BIB007 ). With PoX, the nodes in the network are required to non-interactively prove the possession or commitment of certain measurable resources beyond hashrates in PoW. Furthermore, their collective behavior should also yield a stochastic process for leader assignment following the distribution given in BIB010 . From a network-level perspective, PoX generally relies on a pseudorandom oracle to provide the property of verifiable unpredictability. It also needs to implement a oneway cryptographic puzzle for the proof of resource devoting in the framework of non-interactive ZK Proofs (ZKPs). A conventional ZKP system consists of two parties, namely, the prover executing a computationally unbounded strategy to generate the proof of an assertion without releasing it and the verifier executing a probabilistic polynomial-time strategy to verify it. A party is non-interactive when it can only choose between publishing messages to the network and remaining passive. Otherwise it is interactive. In the context of blockchain consensus protocols, the ZKP framework is extended from proving a private input (i.e., knowledge) to proving possession/consumption of a minimum amount of resource (e.g., computational work). Recent studies haven shown that with specific puzzle design, proof of knowledge and proof of work can be incorporate into a single framework of indistinguishable Proofs of Work or Knowledge (PoWorK) BIB008 , where the prover of work makes calls to a certain puzzle solving algorithm instead of sampling from a non-polynomial language witness relation distribution. In general, the adopted puzzle has to satisfy the basic soundness and completeness properties  ,  . Namely, an invalid proof should always be rejected by nonfaulty verifying nodes while a valid proof should always be accepted by nonfaulty verifiers. A complexity gap is expected such that the puzzle is easy to verify (in polynomialtime) but (moderately) hard for adversaries to invert/solve BIB009 . Furthermore, in permissionless blockchain networks, any node is able to publish arbitrary block proposals. In this situation, a 3-step interactive prover-verifier ZK scheme with verifierdesignated challenges will lead to excessive message overhead. This is the critical reason for requiring a non-interactive puzzle design. Following the generation-computation-verification paradigm of non-interactive puzzles (cf. the verifiable random function defined in BIB002 ), we can abstract a PoX process into the three stages described in Table I . The initialization stage provides the prover and the verifier the necessary information to run in subsequent stages according to the PoX specifications. Typical non-interactive ZKP systems, e.g., zk-SNARK BIB004 have to query a trusted third-party key/random seed generation protocol to produce a common reference string for both the prover and the verifier.