A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Nakamoto Protocol Based on Primitive Proof of Work <s> Recent years have witnessed an exceptional research interest in cryptographic hash functions, especially after the popular attacks against MD5 and SHA-1 in 2005. In 2007, the U.S. National Institute of Standards and Technology (NIST) has also signicantly boosted this interest by announcing a public competition to select the next hash function standard, to be named SHA-3. Not surprisingly, the hash function literature has since been rapidly growing in an extremely fast pace. In this paper, we provide a comprehensive, up-to-date discussion of the current state of the art of cryptographic hash functions security and design. We rst discuss the various hash functions security properties and notions, then proceed to give an overview of how (and why) hash functions evolved over the years giving raise to the current diverse hash functions design approaches. <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Nakamoto Protocol Based on Primitive Proof of Work <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> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Nakamoto Protocol Based on Primitive Proof of Work <s> Bit coin has emerged as the most successful cryptographic currency in history. Within two years of its quiet launch in 2009, Bit coin grew to comprise billions of dollars of economic value despite only cursory analysis of the system's design. Since then a growing literature has identified hidden-but-important properties of the system, discovered attacks, proposed promising alternatives, and singled out difficult future challenges. Meanwhile a large and vibrant open-source community has proposed and deployed numerous modifications and extensions. We provide the first systematic exposition Bit coin and the many related crypto currencies or 'altcoins.' Drawing from a scattered body of knowledge, we identify three key components of Bit coin's design that can be decoupled. This enables a more insightful analysis of Bit coin's properties and future stability. We map the design space for numerous proposed modifications, providing comparative analyses for alternative consensus mechanisms, currency allocation mechanisms, computational puzzles, and key management tools. We survey anonymity issues in Bit coin and provide an evaluation framework for analyzing a variety of privacy-enhancing proposals. Finally we provide new insights on what we term disinter mediation protocols, which absolve the need for trusted intermediaries in an interesting set of applications. We identify three general disinter mediation strategies and provide a detailed comparison. <s> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Nakamoto Protocol Based on Primitive Proof of Work <s> Crypto-currencies like Bitcoin have recently attracted a lot of interest. A crucial ingredient into such systems is the “mining” of a Nakamoto blockchain. We model mining as a Poisson process with time-dependent intensity and use this model to derive predictions about block times for various hash-rate scenarios (exponentially rising hash rate being the most important). We also analyse Bitcoin’s method to update the “network difficulty” as a mechanism to keep block times stable. Since it yields systematically too fast blocks for exponential hash-rate growth, we propose a new method to update difficulty. Our proposed method performs much better at ensuring stable average block times over longer periods of time, which we verify both in simulations of artificial growth scenarios and with real-world data. Besides Bitcoin itself, this has practical benefits particularly for systems like Namecoin. It can be used to make name expiration times more predictable, preventing accidental loss of names. <s> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Nakamoto Protocol Based on Primitive Proof of Work <s> Blockchain is a distributed timestamp server technology introduced for realization of Bitcoin, a digital cash system. It has been attracting much attention especially in the areas of financial and legal applications. But such applications would fail if they are designed without knowledge of the fundamental differences in blockchain from existing technology. We show that blockchain is a probabilistic state machine in which participants can never commit on decisions, we also show that this probabilistic nature is necessarily deduced from the condition where the number of participants remains unknown. This work provides useful abstractions to think about blockchain, and raises discussion for promoting the better use of the technology. <s> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Nakamoto Protocol Based on Primitive Proof of Work <s> Bitcoin’s innovative and distributedly maintained blockchain data structure hinges on the adequate degree of difficulty of so-called “proofs of work,” which miners have to produce in order for transactions to be inserted. Importantly, these proofs of work have to be hard enough so that miners have an opportunity to unify their views in the presence of an adversary who interferes but has bounded computational power, but easy enough to be solvable regularly and enable the miners to make progress. As such, as the miners’ population evolves over time, so should the difficulty of these proofs. Bitcoin provides this adjustment mechanism, with empirical evidence of a constant block generation rate against such population changes. <s> BIB006 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> B. Nakamoto Protocol Based on Primitive Proof of Work <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> BIB007
As we have reviewed in the previous discussion, the primitive PoW scheme proposed in  works to financially disincentivize the Sybil attacks on block proposal and maintains a biased random leader election process in proportion to the hashrate casted by each node. Recall that the input string x to the PoW puzzle is a concatenation of the previous block's hash pointer and the payload data of the proposed block. For the puzzle design of PoW, the reason of choosing the hash function H(·) in (1), e.g., SHA-256 in practice lies in the fact that a hash function is computationally indistinguishable from a pseudorandom function, if it preserves the properties of collision resistance 10 and pre-image resistance BIB001 . Since the random output of H(·) is time-independent and only determined by the input string, it plays the role of an uncompromisable random oracle and outputs a unique, unpredictable result every time when it is queried with a different x  . This means that a node in the blockchain network is able to construct a fresh random challenge solely based on its block proposal without referring to any designated verifier or third-party initializer. Meanwhile, it is well-known that with a proper cryptographic hash function, the search for a preimage (x, nonce) satisfying the condition H(x nonce) ≤ 2 L−h in (1) cannot be more efficient than exhaustively querying the random oracle for all nonce ∈ [0, 2 L ]. This leads to a puzzle time complexity of O(2 h )  . On the other hand, verifying the puzzle only requires a single hash query. Therefore, the properties of noninvertibility, completeness, soundness and freshness are all satisfied by the PoW puzzle given by Definition 1. For a given difficulty level D(h) in (1), each single query to H(·) is an i.i.d. Bernoulli trial with a success probability We adopt the typical assumption of loosely network synchronization for analyzing PoW-based blockchains BIB002 ,  . Namely, all messages are delivered with bounded delay in one round. Then, (3) indicates that the frequency for a node to obtain the puzzle solutions during a certain number of loosely synchronized rounds is a Bernoulli process. Since the probability given in (3) is negligible for a sufficiently large h with cryptographic hash functions H(·), the Bernoulli process of node i converges to a Poisson process as the time interval between queries/trails shrinks  . To analyze the PoW scheme, let w i in (2) refer to the number of queries that node i can make to H(·) in a single round. Then, we can approximate the rate of the Poisson process for node i's puzzle solution by λ i = w i /2 h BIB004 . Note that every node in the network is running an independent puzzle-solving process. Since a combination of N independent Poisson processes is still a Poisson process, then, the collective PoW process of a network with N nodes has a rate The property of the combined Poisson processes in (4) leads to the probability distribution for leader election in BIB007 . From a single node's perspective, the repeated PoW puzzle-solving processes take the form of a block-proposal competition across the network. From the perspective of the network, for a given difficulty level D(h), this puzzle-solving race simulates a verifiable random function for leader election and guarantees to follow the distribution in BIB007 . Most importantly, it tolerates any fraction of the Byzantine nodes in the network. Nevertheless, the PoW by itself cannot guarantee any of the principle Byzantine consensus properties as described in Section II-D. On top of the designed PoW puzzle and the P2P information diffusion functionality, three external functions are abstracted in BIB002 to describe the Nakamoto consensus protocol from a single node's perspective. These functions are 1) the chain reading function that receives as input a blockchain and outputs an interpretation for later use; 2) the content validation function that validates a blockchain replica and checks the data consistency with the applications (e.g., Bitcoin) on top of the blockchain; 3) the input contribution function that compares the local and the received views of the blockchain and adopts the "best" one following the rule of longest chain. The input contribution function realizes the puzzle execution stage and the content validation function realizes the puzzle verification stage in Table I . Due to the independent Poisson processes in the block-proposal competition, more than one node may propose to extend the blockchain using different blocks with corresponding valid PoW solutions at the same time. As a result, the nodes may read from the network multiple valid views of the blockchain and choose different forks as their "best" local views (see also Figure 5 ). Theoretically, it has been shown in BIB005 that deterministic consensus in permissionless blockchain networks cannot be guaranteed unless all non-faulty nodes are reachable from one to another and the number of consensus nodes is known. For this reason, in BIB002 ,  , BIB006 , Garay et al. propose to capture the properties of validity, agreement and liveness of the Nakamoto consensus protocol by the three chain-based properties in Table II . Then, the PoW-based Nakamoto protocol can be modeled as a probabilistic Byzantine agreement protocol. In order to quantify the Byzantine agreement properties for blockchains, three conditions, i.e., the upper-bounded information diffusion delay, a "flat network" with equal and limited hashrates and the upper-bounded number of Byzantine nodes are assumed in BIB002 ,  , BIB006 . It is shown in BIB002 that the three properties in Table II are quantified by three parameters, namely, the collective hashrates of the honest nodes, the hashrate controlled by the adversaries and the expected block arrival rate of the network-level Poisson process given in BIB003 . It has been further proved in BIB002 that under the condition of honest majority, the basic properties of validity and agreement In the condition of multiple local blockchain views due to forking, the common-prefix property indicates that after cutting off (pruning) a certain number of block from the end (header) of the local chain, an honest node will always obtain a sub-chain that is a prefix of another honest node's local view of the blockchain.