A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> Understanding distributed computing is not an easy task. This is due to the many facets of uncertainty one has to cope with and master in order to produce correct distributed software. Considering the uncertainty created by asynchrony and process crash failures in the context of message-passing systems, the book focuses on the main abstractions that one has to understand and master in order to be able to produce software with guaranteed properties. These fundamental abstractions are communication abstractions that allow the processes to communicate consistently (namely the register abstraction and the reliable broadcast abstraction), and the consensus agreement abstractions that allows them to cooperate despite failures. As they give a precise meaning to the words "communicate" and "agree" despite asynchrony and failures, these abstractions allow distributed programs to be designed with properties that can be stated and proved. Impossibility results are associated with these abstractions. Hence, in order to circumvent these impossibilities, the book relies on the failure detector approach, and, consequently, that approach to fault-tolerance is central to the book. Table of Contents: List of Figures / The Atomic Register Abstraction / Implementing an Atomic Register in a Crash-Prone Asynchronous System / The Uniform Reliable Broadcast Abstraction / Uniform Reliable Broadcast Abstraction Despite Unreliable Channels / The Consensus Abstraction / Consensus Algorithms for Asynchronous Systems Enriched with Various Failure Detectors / Constructing Failure Detectors <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> In this paper we describe the various scoring systems used to calculate rewards of participants in Bitcoin pooled mining, explain the problems each were designed to solve and analyze their respective advantages and disadvantages. <s> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> Many large decentralized systems rely on information propagation to ensure their proper function. We examine a common scenario in which only participants that are aware of the information can compete for some reward, and thus informed participants have an incentive not to propagate information to others. One recent example in which such tension arises is the 2009 DARPA Network Challenge (finding red balloons). We focus on another prominent example: Bitcoin, a decentralized electronic currency system. Bitcoin represents a radical new approach to monetary systems. It has been getting a large amount of public attention over the last year, both in policy discussions and in the popular press. Its cryptographic fundamentals have largely held up even as its usage has become increasingly widespread. We find, however, that it exhibits a fundamental problem of a different nature, based on how its incentives are structured. We propose a modification to the protocol that can eliminate this problem. Bitcoin relies on a peer-to-peer network to track transactions that are performed with the currency. For this purpose, every transaction a node learns about should be transmitted to its neighbors in the network. As the protocol is currently defined and implemented, it does not provide an incentive for nodes to broadcast transactions they are aware of. In fact, it provides an incentive not to do so. Our solution is to augment the protocol with a scheme that rewards information propagation. Since clones are easy to create in the Bitcoin system, an important feature of our scheme is Sybil-proofness. We show that our proposed scheme succeeds in setting the correct incentives, that it is Sybil-proof, and that it requires only a small payment overhead, all this is achieved with iterated elimination of dominated strategies. We complement this result by showing that there are no reward schemes in which information propagation and no self-cloning is a dominant strategy. <s> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> The Bitcoin digital currency depends for its correctness and stability on a combination of cryptography, distributed algorithms, and incentivedriven behavior. We examine Bitcoin as a consensus game and determine that it relies on separate consensus about the rules and about game state. An important aspect of Bitcoin’s design is the mining mechanism, in which participants expend resources on solving computational puzzles in order to collect rewards. This mechanism purportedly protects Bitcoin against certain technical problems such as inconsistencies in the system’s distributed log data structure. We consider the economics of Bitcoin mining, and whether the Bitcoin protocol can survive attacks, assuming that participants behave according to their incentives. We show that there is a Nash equilibrium in which all players behave consistently with Bitcoin’s reference implementation, along with innitely many equilibria in which they behave otherwise. We also show how a motivated adversary might be able to disrupt the Bitcoin system and \crash" the currency. Finally, we argue that Bitcoin will require the emergence of governance structures, contrary to the commonly held view in the Bitcoin community that the currency is ungovernable. <s> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> Bitcoin has achieved popularity by promising users a fully decentralized, low-cost virtual currency system. However, a limited set of entities controls Bitcoin's services, decision-making, mining, and incident resolution processes. These entities can decide Bitcoin's fate, bypassing the will of the multitude of users that populate the network. <s> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> In this paper we revisit some major orthodoxies which lie at the heart of the bitcoin crypto currency and its numerous clones. In particular we look at The Longest Chain Rule, the monetary supply policies and the exact mechanisms which implement them. We claim that these built-in properties are not as brilliant as they are sometimes claimed. A closer examination reveals that they are closer to being... engineering mistakes which other crypto currencies have copied rather blindly. More precisely we show that the capacity of current crypto currencies to resist double spending attacks is poor and most current crypto currencies are highly vulnerable. Satoshi did not implement a timestamp for bitcoin transactions and the bitcoin software does not attempt to monitor double spending events. As a result major attacks involving hundreds of millions of dollars can occur and would not even be recorded. Hundreds of millions have been invested to pay for ASIC hashing infrastructure yet insufficient attention was paid to network neutrality and to insure that the protection layer it promises is effective and cannot be abused. In this paper we develop a theory of Programmed Self-Destruction of crypto currencies. We observe that most crypto currencies have mandated abrupt and sudden transitions. These affect their hash rate and therefore their protection against double spending attacks which we do not limit the to the notion of 51% attacks which is highly misleading. In addition we show that smaller bitcoin competitors are substantially more vulnerable. In addition to small hash rate, many bitcoin competitors mandate incredibly important adjustments in miner reward. We exhibit examples of 'alt-coins' which validate our theory and for which the process of programmed decline and rapid self-destruction has clearly already started. <s> BIB006 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <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> BIB007 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> The Bitcoin protocol supports optional direct payments from transaction partners to miners. These “fees” are supposed to substitute miners’ minting rewards in the long run. Acknowledging their role for the stability of the system, the right level of transaction fees is a hot topic of normative debates. This paper contributes empirical evidence from a historical analysis of agents’ revealed behavior concerning their payment of transaction fees. We identify several regime shifts, which can be largely explained by changes in the default client software or actions of big intermediaries in the ecosystem. Overall, it seems that rules dominate ratio, a state that is sustainable only if fees remain negligible. <s> BIB008 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time and low transaction throughput. Another challenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solidus, a decentralized cryptocurrency based on permissionless Byzantine consensus. A core technique in Solidus is to use proof of work for leader election to adapt the Practical Byzantine Fault Tolerance (PBFT) protocol to a permissionless setting. We also design Solidus to be incentive compatible and to mitigate selfish mining. Solidus improves on Bitcoin in confirmation time and provides safety and liveness assuming Byzantine players and the largest coalition of rational players collectively control less than one-third of the computation power. <s> BIB009 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> In this paper, we present an empirical study of a recent spam campaign (a “stress test”) that resulted in a DoS attack on Bitcoin. The goal of our investigation being to understand the methods spammers used and impact on Bitcoin users. To this end, we used a clustering based method to detect spam transactions. We then validate the clustering results and generate a conservative estimate that 385,256 (23.41 %) out of 1,645,667 total transactions were spam during the 10 day period at the peak of the campaign. We show the impact of increasing non-spam transaction fees from 45 to 68 Satoshis/byte (from $0.11 to $0.17 USD per kilobyte of transaction) on average, and increasing delays in processing non-spam transactions from 0.33 to 2.67 h on average, as well as estimate the cost of this spam attack at 201 BTC (or $49,000 USD). We conclude by pointing out changes that could be made to Bitcoin transaction fees that would mitigate some of the spam techniques used to effectively DoS Bitcoin. <s> BIB010 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> Stratum, the de-facto mining communication protocol used by blockchain based cryptocurrency systems, enables miners to reliably and efficiently fetch jobs from mining pool servers. In this paper we exploit Stratum's lack of encryption to develop passive and active attacks on Bitcoin's mining protocol, with important implications on the privacy, security and even safety of mining equipment owners. We introduce StraTap and ISP Log attacks, that infer miner earnings if given access to miner communications, or even their logs. We develop BiteCoin, an active attack that hijacks shares submitted by miners, and their associated payouts. We build BiteCoin on WireGhost, a tool we developed to hijack and surreptitiously maintain Stratum connections. Our attacks reveal that securing Stratum through pervasive encryption is not only undesirable (due to large overheads), but also ineffective: an adversary can predict miner earnings even when given access to only packet timestamps. Instead, we devise Bedrock, a minimalistic Stratum extension that protects the privacy and security of mining participants. We introduce and leverage the mining cookie concept, a secret that each miner shares with the pool and includes in its puzzle computations, and that prevents attackers from reconstructing or hijacking the puzzles. We have implemented our attacks and collected 138MB of Stratum protocol traffic from mining equipment in the US and Venezuela. We show that Bedrock is resilient to active attacks even when an adversary breaks the crypto constructs it uses. Bedrock imposes a daily overhead of 12.03s on a single pool server that handles mining traffic from 16,000 miners. <s> BIB011 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> Blockchain technology, as a decentralized and non-hierarchical platform, has the potential to replace centralized systems. Yet, there are several challenges inherent in the blockchain structure. One of the deficiencies of the existing blockchains is a convenient information propagation technique enhancing incentive-compatibility and bandwidth efficiency. The transition from a centralized system into distributed one brings along game theoretical concerns. Especially for the permissionless blockchains, information propagation should be incentive-compatible just like any other communication or computational costly operation. Another important issue is that information is relayed via gossip-like protocols causing excessive bandwidth usage. Each information is propagated at least twice: first to advertise its existence, second to announce that it is final and validated, i.e., added to the block. ::: In this work, we investigate two distinct aspects of the information propagation of the blockchains: incentive and routing mechanisms. For the former part, we analyze the necessary and sufficient conditions of the Sybil-proof incentive-compatible propagation methodology. We show the impossibility result of the Sybil-proofness in 1-connected network model. For the rest, we prove that the propagation decision is independent of the capabilities of the receiving side. Then, we formulate the generic fee sharing function which encourages rational participants to propagate information. Regarding the bandwidth efficiency, we study a special type of consensus protocols where the block owner (round leader) is validated before the block is created. We present a smart routing mechanism which the redundant communication cost from the size of the network to the scale of average shortest path length. Finally, we combine the incentive and routing mechanisms in a storage-efficient way. <s> BIB012 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> We investigate Bitcoin network observing transactions broadcasted into the network during a week from 04/05/2016 and then monitoring their inclusion into the blockchain during the following seven months.We unveil that 42% of the transactions are still not included in the Blockchain after 1 h from their appearance and 20% of the transactions are still not included in the Blockchain after 30 days, therefore revealing a great inefficiency in the Bitcoin system. However, we observe that most of these “forgotten” transactions have low values and in terms of transferred value the system is less inefficient with 93% of the transactions value being included into the Blockchain within 3 h and 98.8% within a day. The fact that a sizeable fraction of transactions is not processed timely casts serious doubts on the usability of the Bitcoin Blockchain for reliable time-stamping purposes. It also calls for a debate about the right systems of incentives which a peer-to-peer unintermediated system should introduce to promote efficient transaction recording <s> BIB013 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> A. Incentive Compatibility of Nakamoto Protocols <s> Open-access blockchains based on proof-of-work protocols have gained tremendous popularity for their capabilities of providing decentralized tamper-proof ledgers and platforms for data-driven autonomous organization. Nevertheless, the proof-of-work based consensus protocols are vulnerable to cyber-attacks such as double-spending. In this paper, we propose a novel approach of cyber risk management for blockchain-based service. In particular, we adopt the cyber-insurance as an economic tool for neutralizing cyber risks due to attacks in blockchain networks. We consider a blockchain service market, which is composed of the infrastructure provider, the blockchain provider, the cyber-insurer, and the users. The blockchain provider purchases from the infrastructure provider, e.g., a cloud, the computing resources to maintain the blockchain consensus, and then offers blockchain services to the users. The blockchain provider strategizes its investment in the infrastructure and the service price charged to the users, in order to improve the security of the blockchain and thus optimize its profit. Meanwhile, the blockchain provider also purchases a cyber-insurance from the cyber-insurer to protect itself from the potential damage due to the attacks. In return, the cyber-insurer adjusts the insurance premium according to the perceived risk level of the blockchain service. Based on the assumption of rationality for the market entities, we model the interaction among the blockchain provider, the users, and the cyber-insurer as a two-level Stackelberg game. Namely, the blockchain provider and the cyber-insurer lead to set their pricing/investment strategies, and then the users follow to determine their demand of the blockchain service. Specifically, we consider the scenario of double-spending attacks and provide a series of analytical results about the Stackelberg equilibrium in the market game. <s> BIB014
For Nakamoto protocols, monetary incentive plays the key role to ensure that most of the consensus nodes/miners follow the rules of blockchain state transition during the puzzle solution competition. In permissionless blockchain networks, the incentive mechanism is built upon the embedded digital token issuing and transferring schemes. In a typical PoWbased blockchain network, the leader/winner in the block proposal competition not only collects transaction fees from the approved transactions in the new block, but also gets token issuing reward, e.g., the "coinbase reward" in Bitcoin, for expanding the blockchain with the new block. For this reason, the puzzle competition process is compared to the process of "gold mining", since by casting resources into the competition, the nodes expect to receive monetary rewards carried by the tokens. As a result, the consensus participant nodes are better known as block "miners" to the public. In BIB004 the consensus in blockchain networks is divided into three folds, namely, the consensus about the rules, e.g., about transaction dissemination and validation, the universality of the blockchain state and financial value that the digital token carries. Then, the studies on the Nakamoto protocol's incentive compatibility can also be categorized according to these three aspects. Since the introduction of ASIC devices and pool mining for PoW-based blockchain networks, concerns have been raised about the nodes' incentive to fully abide by the protocol BIB005 ,  , BIB004 , BIB006 . Due to the explosion of network-level hashrates (see Figure 7 (a)), most of the practical blockchain networks, i.e., cryptocurrency networks, are nowadays dominated by the proxies of mining pools BIB002 Figure 12 ). An individual node in a mining pool is known as a mining worker, since it no longer performs the tasks of transaction validation or propagation and does not even keep any blockchain data. On the contrary, only the proxy of the pool, i.e., the pool server/task operator maintains the replica of the blockchain. The pool server divides the exhaustive preimage search for PoW solution into a number of subtasks and outsources them to the mining workers  . In this sense, only the pool server can be considered as a node in the blockchain network. Studies have shown that joining a mining pool has become the more plausible strategy than working as an individual consensus node, since such a strategy reduces the income variance and secures stable profits BIB007 ,  . However, this leads to the formation of mining-pool Cartel  and is against the design goal of Nakamoto consensus in  , that "the network is robust in its unstructured simplicity". A further study in BIB003 reveals that under the current framework of Nakamoto protocols, no incentive is provided for nodes to propagate the transactions that they are aware of. The study considers the situation when transaction fees dominate the block rewards  . The analysis in BIB003 models the paths of transaction dissemination as a forest of d-ary directed  According to the Stratum mining protocol BIB011 , the pool server only needs to send a miner the Merkle root of the transactions in the block (see Figure 2 ) and a difficulty level to complete the puzzle solving sub-task. trees, where each transaction issuer considers its peer nodes as the tree roots and the nodes on the far end of the network as the leafs. During transaction dissemination, a consensus node can add any number of pseudo-identities (a.k.a., fake identities) before selectively relaying the transaction to any of its neighbors. It is shown that a consensus node tends to not broadcast any transaction that offers a fee. By doing so, it reduces the number of nodes that are aware of the transaction and hence the competition of mining that transaction. An improved protocol is proposed in BIB003 by introducing a broadcasting incentive mechanism. More specifically, the proposed mechanism requires that each relaying node in the path of transaction propagation shares a uniform portion of reward with the root (i.e., mining) node, when the height of the relaying node is small than a predetermined threshold in the directed tree. The analysis of the new protocol is based on the formulation of a normal-form game [123] , and thus the equilibrium strategy of each node can be obtained through iterative removal of dominated strategies. The designed incentive mechanism is shown to guarantee that only the non-Sybil and information propagating strategies survive in the iterated removal of weakly dominated strategies, as long as the miners are connected to sufficient many peers. Similar studies to enforce honest block/transaction propagation can also be found in BIB012 , BIB009 . The study in BIB012 casts the problem of incentivizing block propagation into the framework of routing in k-connected networks, where each rational node can freely choose between relaying and mining (or both). A protocol of transaction fee-sharing is designed therein to guarantee that the rational strategy of honest nodes in the network is to propagate the received transactions. It is required that a mining node shares the reward of a new transaction with the relaying nodes in one path between itself and the client which issues that transaction. According to BIB003 , creating pseudo-identities does not increase the connectivity of a node. From such an observation, it is proved in BIB012 that assigning the propagation reward of each relaying node as a decreasing function of the hop count guarantees transaction propagation, as long as the computing power (or other resources for mining) controlled by each node does not dominate the network. Comparatively, the study in BIB009 ensures that the payment made to the transaction-relaying nodes cannot be denied by the miners of the new blocks. With the proposed propagation protocol in BIB009 , each intermediate hop adds its own signature to the transaction before sending it to the next hop. While working on their own PoW-puzzle solution, the relaying nodes freely charge their descendants at least a minimum fee for propagation. The miner whose block finally gets confirmed by the blockchain will pay for the propagation fees to one selected path of nodes. As in BIB003 the process of transaction propagation and relaying price competition is modeled as a non-cooperative game in BIB009 . It is proved that with the proposed propagation protocol based on the chain of signatures, a rational miner's equilibrium strategy is to always choose the shortest path, and a rational intermediate node' equilibrium strategy is to always charge its descendants the minimum fees for relaying transactions. When block creation reward dominates the mining reward, incentive incompatibility may appear in different forms. Intuitively, it is plausible for a rational miner to pack up a proper number of transactions with decent fees in the new block for profit maximization. However, empty blocks with only coinbase transaction or blocks with a tiny number of transactions can be frequently observed in the practical blockchain networks BIB001 . An informal game theoretic analysis in  indicates that the consensus nodes tend to ignore the received blocks of large size in a flat network and relay the smaller competing blocks instead. The reason is that large blocks result in longer delay due to transaction validation, hence increasing the probability of orphaning any blocks that are mined based on them. Although mining empty block does not violate the BIB001 See Blocks #492972 in Bitcoin and #3908809 in Ethereum for examples. current Nakamoto protocol, it results in the same situation as a Distributed Denial of Service (DDoS) attack BIB010 by blocking the confirmation of normal transactions. Furthermore, the statistical studies in BIB013 , BIB008 have shown that the consensus nodes behave rationally and are prone to prioritize the transactions with higher transaction fees during block packing. However, when the coinbase reward dominates the block mining reward, the miners are yet not incentivized to enforce strictly positive fees BIB008 . In the case study of Bitcoin network, extra delays for the small-value transactions are identified ranging from 20 minutes BIB008 to as long as 30 days BIB013 . Also, it is observed in BIB008 that most of the lightweight nodes still set an arbitrary transaction fee in the real-world scenarios. It is unclear whether the miners or the transaction issuers adopt best-response strategies systematically. The study in  simplifies the consensus process as a supply game subject to the trade of a specific type of physical goods. In the considered scenario, the miners essentially become the follower players in a two-level hierarchical/Stackelberg game 15 led by the blockchain network, which is assumed to be able to set the transaction prices. Then, they are expected to have an incentive for including all transactions if there exists no block-size limit. On the other hand, it is pointed out in  that, since the block orphaning probability exponentially grows with the block size, a healthy transaction fee market does not exist for unlimited block size due to the physical constraint of link capacity in the network. Finally, it is worth noting that most of the existing studies are based on the presumption that the tokens carried by a blockchain have monetary value and their exchange rate volatility is small. An optimistic prediction is provided in  based on an assumption excluding any state variables on the user sider except the belief in "proper functioning of a cryptocurrency". In the absence of investors and when the blockchain is used only for the purpose of remittance, it is shown in  that the tokens of a blockchain network admit a unique equilibrium exchange rate in each period of the belief evolution. Conditioned on the survival of a cryptocurrency, the equilibrium state depends on the excess in users' valuation of the blockchain over the other payment options as well as the supply of the tokens in the market. Together with the Stackelberg game-based interpretation in  , it is reasonable to consider that the equilibrium price of a blockchain token is determined by the demand-supply relation in the market. It is worth noting that the data security is only guaranteed by sufficient PoW computation power in the blockchain network. Currently, except for a few studies such as BIB014 , it is generally unclear how the impact of security issues is reflected in the users' valuation of the blockchain. As a result, whether the security requirement of the Nakamoto protocol is compatible with the market clearing price remains an open question.