A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Nonlinear Block Organization <s> Distributed systems: an algorithmic approach is an important addition to the distributed computing literature. The book offers a broad overview of important distributed computing topics, and, where relevant, a touch of networking topics as well. <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Nonlinear Block Organization <s> Bitcoin is a disruptive new crypto-currency based on a decentralized open-source protocol which has been gradually gaining momentum. Perhaps the most important question that will affect Bitcoin’s success, is whether or not it will be able to scale to support the high volume of transactions required from a global currency system. We investigate the implications of having a higher transaction throughput on Bitcoin’s security against double-spend attacks. We show that at high throughput, substantially weaker attackers are able to reverse payments they have made, even well after they were considered accepted by recipients. We address this security concern through the GHOST rule, a modification to the way Bitcoin nodes construct and re-organize the block chain, Bitcoin’s core distributed data-structure. GHOST has been adopted and a variant of it has been implemented as part of the Ethereum project, a second generation distributed applications platform. <s> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Nonlinear Block Organization <s> Distributed cryptographic protocols such as Bitcoin and Ethereum use a data structure known as the block chain to synchronize a global log of events between nodes in their network. Blocks, which are batches of updates to the log, reference the parent they are extending, and thus form the structure of a chain. Previous research has shown that the mechanics of the block chain and block propagation are constrained: if blocks are created at a high rate compared to their propagation time in the network, many conflicting blocks are created and performance suffers greatly. As a result of the low block creation rate required to keep the system within safe parameters, transactions take long to securely confirm, and their throughput is greatly limited. <s> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Nonlinear Block Organization <s> Several new services incentivize clients to compete in solving large computation tasks in exchange for financial rewards. This model of competitive distributed computation enables every user connected to the Internet to participate in a game in which he splits his computational power among a set of competing pools -- the game is called a computational power splitting game. We formally model this game and show its utility in analyzing the security of pool protocols that dictate how financial rewards are shared among the members of a pool. As a case study, we analyze the Bitcoin crypto currency which attracts computing power roughly equivalent to billions of desktop machines, over 70% of which is organized into public pools. We show that existing pool reward sharing protocols are insecure in our game-theoretic analysis under an attack strategy called the "block withholding attack". This attack is a topic of debate, initially thought to be ill-incentivized in today's pool protocols: i.e., causing a net loss to the attacker, and later argued to be always profitable. Our analysis shows that the attack is always well-incentivized in the long-run, but may not be so for a short duration. This implies that existing pool protocols are insecure, and if the attack is conducted systematically, Bitcoin pools could lose millions of dollars worth in months. The equilibrium state is a mixed strategy -- that is -- in equilibrium all clients are incentivized to probabilistically attack to maximize their payoffs rather than participate honestly. As a result, the Bitcoin network is incentivized to waste a part of its resources simply to compete. <s> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Nonlinear Block Organization <s> Nakamoto’s famous blockchain protocol enables achieving consensus in a so-called permissionless setting—anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents “sybil attacks” (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. “moderately hard functions”) introduced by Dwork and Naor (Crypto’92). <s> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Nonlinear Block Organization <s> Abstract We analyse the Tangle — a DAG-valued stochastic process where new vertices get attached to the graph at Poissonian times, and the attachment’s locations are chosen by means of random walks on that graph. These new vertices, also thought of as “transactions”, are issued by many players (which are the nodes of the network), independently. The main application of this model is that it is used as a base for the IOTA cryptocurrency system. 1 We prove existence of “almost symmetric” Nash equilibria for the system where a part of players tries to optimize their attachment strategies. Then, we also present simulations that show that the “selfish” players will nevertheless cooperate with the network by choosing attachment strategies that are similar to the “recommended” one. <s> BIB006 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> C. Nonlinear Block Organization <s> This paper presents Conflux, a fast, scalable and decentralized blockchain system that optimistically process concurrent blocks without discarding any as forks. The Conflux consensus protocol represents relationships between blocks as a direct acyclic graph and achieves consensus on a total order of the blocks. Conflux then, from the block order, deterministically derives a transaction total order as the blockchain ledger. We evaluated Con- flux on Amazon EC2 clusters with up to 20k full nodes. Conflux achieves a transaction throughput of 5.76GB/h while confirming transactions in 4.5-7.4 minutes. The throughput is equivalent to 6400 transactions per second for typical Bitcoin transactions. Our results also indicate that when running Conflux, the consensus protocol is no longer the throughput bottleneck. The bottleneck is instead at the processing capability of individual nodes. <s> BIB007
Another approach aimed at improving the network throughput focuses on the design of transaction data organization. As we briefly introduce in Section II-B, instead of organizing block in a linear list, the approaches of nonlinear block organization are able to (partially) address the scalability problem by changing the mechanism of transaction validation in the consensus layer. The earliest scheme of nonlinear block organization can be found in BIB002 as the protocol of Greedy Heaviest-Observed Sub-Tree (GHOST). In a GHOST-based network, nodes store all the locally observed valid blocks and consequently maintain a tree of their respective forks. As an alternative to the longest-chain rule, GHOST extends the canonical chain of PoW-generated blocks by the block with the heaviest subtree, i.e., the subtree with the largest number of tree-nodes (see Figure 24 ). In  , a unified security description of GHOST and the Nakamoto protocol is established by slightly modifying the K-consistency property in BIB005 (see also Section III-B) into a new property of Kdominance, which measures the discrepancy in the weights between sibling subtrees. As pointed out in BIB002 , the rate of main-chain growth of GHOST is lower than that of the longestchain rule when the block generation rate and the network delay are the same. However, since GHOST relaxes the blockgeneration constraint for the same level of security requirement Figure 24 . A tree of blocks. Instead of choosing the longest chain (Blocks 1A to 5A), Block 1B with a subtree weight 11 is selected into the main chain. Consequently, Blocks 2C (with a subtree weight 5) and 3D (with a subtree weight 2) are selected into the main chain of the current view. against 51% attacks, it is able to shorten safely the waiting time for block confirmation and thus has a limited ability of improving the network throughput. A further step toward nonlinear block organization is proposed in BIB003 , where blocks are ordered in a DAG and each block is allowed to have multiple predecessors (cf. single parent block in GHOST BIB002 ). Namely, the header of each block may contain more than one pointer to the precedent blocks to indicate the pairwise order. The DAG-based protocol in BIB003 also selects a main chain (cf. GHOST) of linear order from the DAG. To form such a linear order on the blocks at the current view, a node runs for each block a postorder traversal algorithm on the DAG and checks if the transactions in the current block are consistent with the visited one. Compared with the longest-chain rule or GHOST, the DAG-based rule of chain expansion allows the non-conflicting, off-chain blocks to be selectively included into the ledger view. For example, from the perspective of a main-chain block, its off-chain descendant blocks can still be included into the ledger as long as they are not far away from the main chain as both predecessors and descendants. Then, by including the discarded (i.e., off-chain) blocks, the proposed protocol possesses a limited ability of increasing the network throughput. To further improve the network throughput, the protocol proposed in BIB003 is later extended to the protocol "SPEC-TRE" in  . SPECTRE relaxes the requirement on node synchronization, and allows blocks to concurrently grow on the ledger without specifying a main branch. To define the rule of ledger extension, SPECTRE introduces a virtual pairwise voting mechanism to determine the order of any pairwise blocks in the DAG. In brief, each block in the DAG contributes to the vote on the relative order of not only its preceding blocks but also its descendant blocks according to the topology of the DAG. Compared with the main chain-based rules, SPECTRE is shown to be robust to block-withholding attacks (cf. BIB004 ). The reason is that with vote-based pairwise ordering, secret chains published by the attackers cannot win the votes by existing blocks from the honest nodes due to the lack of connections in the DAG (see Figure 25 ). Without undermining the network security, i.e., increasing the transaction reversal probability, SPECTRE admits faster commitment time as the block creation process is accelerated. By (4), the more nodes in the network, the higher the expected block generation rate is Figure 25 . An example of the virtual voting procedure on the order of blocks X and Y in a DAG with block withholding attacks. Blocks (voters) in the descendant set of X will vote X < Y (i.e., X preceding Y ) since they only see X. Blocks 0-4 will vote X < Y since they see more X < Y votes in their sets of descendant block. Blocks 8-10 which have both X and Y as the ancestors run an recursive query to their predecessor sets and use the majority voting results as their own votes. given a fixed PoW difficulty. As indicated by  , for a target transaction-reversal probability, a known propagation delay and a fixed PoW-difficulty level, SPECTRE is able to increase the transaction throughput as the network size increases. Based on the aforementioned protocols, a number of DAGbased schemes have been proposed with a variety of emphasis on different performance indeces. For example, Byteball  adopts the concept of main chain/tree (see also BIB002 ,  , BIB003 ) but uses authenticated witnessing nodes to determine the partial order of blocks at each user's view. Another DAG-based protocol, i.e., Conflux BIB007 modifies GHOST by adding in each new block the reference pointers to all existing blocks without descendants at the current DAG view. Compared with BIB002 , BIB003 , Conflux is claimed to provide 100% utilization of the off-chain blocks and thus is able to improve the network scalability. Furthermore, a similar protocol to SPECTRE is proposed in  , BIB006 as IoTA Tangle. The major difference of IoTA Tangle lies in that it discards the data structure of block as a package of transactions. Instead, it requires nodes to publish directly transactions onto the transaction DAG. A node is enforced by the protocol to approve/reference more than two transactions by linking their hash values in the header of its new transaction to expand the DAG. By doing so, the node expects to accumulate sufficient weight (cf. votes on the partial orders in SPECTRE) for this transaction from the future transactions BIB001 by other nodes to finally confirm it. So far, complete theoretical proof of the liveness property of IoTA Tangle is still an open issue  , BIB006 . However, the study in BIB006 implies that, if self-interested nodes have the same capability of information acquisition and transaction generation as the other nodes, they will possibly reach an "almost symmetric" Nash equilibrium. Namely, they will be forced to cooperate with the network by choosing the default parent-selection strategy followed by the honest nodes.