A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <s> We study a k-dimensional generalization of the birthday problem: given k lists of n-bit values, find some way to choose one element from each list so that the resulting k values XOR to zero. For k = 2, this is just the extremely well-known birthday problem, which has a square-root time algorithm with many applications in cryptography. In this paper, we show new algorithms for the case k > 2: we show a cube-root time algorithm for the case of k = 4 lists, and we give an algorithm with subexponential running time when k is unrestricted.We also give several applications to cryptanalysis, describing new subexponential algorithms for constructing one-more forgeries for certain blind signature schemes, for breaking certain incremental hash functions, and for finding low-weight parity check equations for fast correlation attacks on stream ciphers. In these applications, our algorithm runs in O(22?n) time for an n-bit modulus, demonstrating that moduli may need to be at least 1600 bits long for security against these new attacks. As an example, we describe the first-known attack with subexponential complexity on Schnorr and Okamoto-Schnorr blind signatures over elliptic curve groups. <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <s> We introduce CAPTCHA, an automated test that humans can pass, but current computer programs can't pass: any program that has high success over a CAPTCHA can be used to solve an unsolved Artificial Intelligence (AI) problem. We provide several novel constructions of CAPTCHAS. Since CAPTCHAs have many applications in practical security, our approach introduces a new class of hard problems that can be exploited for security purposes. Much like research in cryptography has had a positive impact on algorithms for factoring and discrete log, we hope that the use of hard AI problems for security purposes allows us to advance the field of Artificial Intelligence. We introduce two families of Al problems that can be used to construct CAPTCHAS and we show that solutions to such problems can be used for steganographic communication. CAPTCHAS based on these AI problem families, then, imply a win-win situation: either the problems remain unsolved and there is a way to differentiate humans from computers, or the problems are solved and there is a way to communicate covertly on some channels. <s> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <s> Bit coin is widely regarded as the first broadly successful e-cash system. An oft-cited concern, though, is that mining Bit coins wastes computational resources. Indeed, Bit coin's underlying mining mechanism, which we call a scratch-off puzzle (SOP), involves continuously attempting to solve computational puzzles that have no intrinsic utility. We propose a modification to Bit coin that repurposes its mining resources to achieve a more broadly useful goal: distributed storage of archival data. We call our new scheme Perm coin. Unlike Bit coin and its proposed alternatives, Perm coin requires clients to invest not just computational resources, but also storage. Our scheme involves an alternative scratch-off puzzle for Bit coin based on Proofs-of-Retrievability (PORs). Successfully minting money with this SOP requires local, random access to a copy of a file. Given the competition among mining clients in Bit coin, this modified SOP gives rise to highly decentralized file storage, thus reducing the overall waste of Bit coin. Using a model of rational economic agents we show that our modified SOP preserves the essential properties of the original Bit coin puzzle. We also provide parameterizations and calculations based on realistic hardware constraints to demonstrate the practicality of Perm coin as a whole. <s> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <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> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <s> An implicit goal of Bitcoin's reward structure is to diffuse network influence over a diverse, decentralized population of individual participants. Indeed, Bitcoin's security claims rely on no single entity wielding a sufficiently large portion of the network's overall computational power. Unfortunately, rather than participating independently, most Bitcoin miners join coalitions called mining pools in which a central pool administrator largely directs the pool's activity, leading to a consolidation of power. Recently, the largest mining pool has accounted for more than half of network's total mining capacity. Relatedly, "hosted mining" service providers offer their clients the benefit of economies-of-scale, tempting them away from independent participation. We argue that the prevalence of mining coalitions is due to a limitation of the Bitcoin proof-of-work puzzle -- specifically, that it affords an effective mechanism for enforcing cooperation in a coalition. We present several definitions and constructions for "nonoutsourceable" puzzles that thwart such enforcement mechanisms, thereby deterring coalitions. We also provide an implementation and benchmark results for our schemes to show they are practical. <s> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <s> Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system. <s> BIB006 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <s> We introduce the novel notion of a Proof of Human-work PoH and present the first distributed consensus protocol from hard Artificial Intelligence problems. As the name suggests, a PoH is a proof that a human invested a moderate amount of effort to solve some challenge. A PoH puzzle should be moderately hard for a human to solve. However, a PoH puzzle must be hard for a computer to solve, including the computer that generated the puzzle, without sufficient assistance from a human. By contrast, CAPTCHAs are only difficult for other computers to solve -- not for the computer that generated the puzzle. We also require that a PoH be publicly verifiable by a computer without any human assistance and without ever interacting with the agent who generated the proof of human-work. We show how to construct PoH puzzles from indistinguishability obfuscation and from CAPTCHAs. We motivate our ideas with two applications: HumanCoin and passwords. We use PoH puzzles to construct HumanCoin, the first cryptocurrency system with human miners. Second, we use proofs of human work to develop a password authentication scheme which provably protects users against offline attacks. <s> BIB007 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> D. Proof of Concepts for Performance Improvement <s> A random oracle is an idealization that allows us to model a hash function as an oracle that will output a uniformly random string given any input. We introduce the notion of a universal sampler scheme that extends the notion of a random oracle, to a method of sampling securely from arbitrary distributions. ::: ::: We describe several applications that provide a natural motivation for this notion; these include generating the trusted parameters for many schemes from just a single trusted setup. We further demonstrate the versatility of universal samplers by showing how they give rise to simple constructions of identity-based encryption and multiparty key exchange. In particular, we construct adaptively secure non-interactive multiparty key exchange in the random oracle model based on indistinguishability obfuscation; obtaining the first known construction of adaptively secure NIKE without complexity leveraging. ::: ::: We give a solution that shows how to transform any random oracle into a universal sampler scheme, based on indistinguishability obfuscation. At the heart of our construction and proof is a new technique we call "delayed backdoor programming" that we believe will have other applications. <s> BIB008
Alternative PoX schemes have also been designed with the emphasis on improving the performance of PoW in the aspects such as security, fairness and sustainability. To alleviate the problem of computation power centralization due to the massive adoption of ASICs, memory-hard PoW, also known as the Proof of Memory (PoM), is adopted by ZCash  and Ethereum [36] networks. In the ZCash network, the Equihash scheme  is adopted based on the generalized birthday problem BIB001 . The study in  has pointed out that any identified NP-complete problem can be the natural candidate for the PoX puzzle due to their proved hardness, as long as the solution verification can be completed in polynomial time. However, a puzzle design only satisfying the hardness requirement may not be able to combat the botnet or ASIC-based manipulation of hashrate. Thus, a suitable PoX is expected to be "optimization-free" and "parallelism-constraint". Namely, the solution searching process cannot be sped up by using alternative algorithms or through parallelization. An ideal approach of imposing parallelism constraint is to ensure that the PoW scheme is inherently sequential. However, an inherently sequential NP problem that is known to be verified in short time is yet to be found  . Therefore, the study in  adopts an alternative approach by imposing enormous memory bandwidth to the parallel solution of the puzzle. According to BIB001 , the generalized k-dimensional birthday problem is to find k strings of n bits from k sets of strings, such that their XOR operation leads to zero. Equihash employs the hash function H(·) to randomly generate the k strings using the block payload data x and a nonce (as in (9)), such that both the XOR-based birthday problem solution and a PoW preimage of a given difficulty are found. It is shown in BIB001 that the best solution algorithm to this problem presents O(2 n/k ) complexity in both time and space and thus is memory-intensive. More importantly, for a k-dimensional problem, a discounting factor 1/q in memory usage leads to O(q k/2 ) times more queries to the hash function. Due to the physical memory bandwidth limit, the computation advantage of parallelization is limited. These properties guarantee the ASIC-resistance of Equihash. With the same purpose of preventing the "super-linear" profit through hashrate accumulation, Ethereum currently adopts a different puzzle design known as Ethash for ASIC resistance  . Ethash requires the consensus nodes to search for the PoW puzzle solution based on a big pseudorandom dataset, which increases linearly over time. The dataset is organized as the adjacency matrix of a DAG, where each vertex represents a randomly generated data field of 128 bits. In the execution stage of Ethash, the node starts a onetime search of the solution with a hash query, and uses the concatenation of the block payload and a nonce to seed the hash function for locating a random vertex in the DAG. Then, the search is completed in a fixed-iteration loop of queries to the hash function, for which the output of the last iteration, i.e., the data field of the last vertex in the path is used as the input to determine the position of the next vertex in the DAG. The final output of the loop is used to check against the preimage condition as in  . As illustrated in Figure 10 , the designed puzzle of Ethash makes the searching algorithm inherently sequential. With Ethash, the rate of data field fetching from the DAG is limited by the memory bandwidth. Then, paralleling the hash queries with ASICs cannot lead to much performance improvement in a single search of the puzzle solution. Ethash  only makes the puzzle solution partially sequential within a single attempt of preimage search. Therefore, Ethash still faces the problem of PoW outsourcing since a consensus node can divide the puzzle solution search into multiple sub-problems and outsource them to different "mining workers" (i.e., puzzle solvers). Such a problem is also known as the formation of mining coalition (pool)  and may result in a serious problem of consensus manipulation by a handful of full nodes BIB004 . In BIB005 , a nonoutsourceable "scratch-off puzzle" is proposed to disincentivize the tendency of mining task Figure 10 . One query to the random oracle in Ethash for a given nonce based on the iterative mixed hash operation for vertex searching. outsourcing. Intuitively, when a node effectively outsources its puzzle-solving work to some mining machines, we call the puzzle nonoutsourceable if these miners can steal the block proposal reward of that node without producing any evidence to implicate themselves. The study in BIB005 employs Merkle proofs for puzzle design, which can be considered as a generalization of the PoR BIB003 . In BIB005 , a Merkle tree is created based on a number of random strings. To generate a fresh puzzle, a node queries the hash function for the first time with a random nonce and the constructed Merkle root. The output of this query is used to select a random subset of distinct leaves on the Merkle tree. Then, the concatenation of the Merkle proofs for each leaf in subset and the same nonce is used as the input to the second query of the hash function. The output is used to compare with the preimage condition as given in  . If a solution (nonce) is found, the payload of the proposed block is used as the input of the third query to the hash function, and the output is used to select another subset of random leaves on the Merkle tree. The corresponding Merkle proofs are treated as the "signature" of the payload of the proposed block. With such puzzle design, mining workers only need to know a sufficiently large fraction of the Merkle tree leaves to "steal" the reward by replacing the Merkle proofbased signature with their own proofs. It is worth noting that the nonoutsourceable puzzle in BIB005 is generated in such a way to make the preimage search for (1) independent of the payload of the proposed block, i.e., using the randomly generated Merkle tree. Then, a mining worker is able to replace the original payload including the public keys from the outsourcer by its own payload without being detected. A similar proposal of nonoutsourceable puzzle can be found in  , where a nonoutsourceable puzzle is designed based on two-fold puzzle. Namely, an inner puzzle is solved as a typical PoW puzzle, whose solution is used as the input of an additional PoW puzzle known as the outer puzzle. To prevent outsourcing the work load, a mining worker's signature is required for the inner puzzle solution to be used by the outer puzzle. However, it is pointed out in  that such design can only be considered heuristic and is not guaranteed to have the formal properties of weak outsourceability BIB005 . Apart from the manipulation-resistant puzzles, other puzzles are proposed in  , BIB007 with the emphasis on ecofriendliness. Therein, the major goal is to reduce/remove the repeated hash queries to curb energy consumption due to hash queries. In  , the SpaceMint network is proposed based Figure 11 . An example of DAG formation based on the hash of the parent vertices: for miner i adopting a public key pk i , the value v j of the j's vertex in its DAG with m parent vertices {p1, . . . , pm} is obtained as v j = H(pk i , j, v p1 , . . . , vpm). on Proof of SPace (PoSP) BIB006 . Similar to PoR BIB003 , PoSP requires the consensus nodes to provide non-interactive proofs of storage dedication during puzzle solution searching. The major difference from PoR lies in that PoSP does not need the prover to store useful data (from the verifiers), and the proof is based on a large volume of random data stored on the provers' hard drive. As in Ethash  , the committed space is also organized as a DAG, where the value of each vertex is determined based on the hash of its parent vertices (see Figure 11 ). A consensus node is required to use the hash of an earlier block as the seed to sample a random set of vertex values. The set of the vertex values forms the challenge of the node's local PoSP puzzle. If the node is able to provide the Merkle proofs for all the vertices in the challenge set, namely, the sibling vertices that lie on the path between each challenge vertex and the end vertex in the DAG with no outgoing edge, the proposed block is considered a valid block candidate. SpaceMint also proposes to measure the quality of a set of Merkle proofs based on the hash value of the concatenated vertex in a Merkle tree. Then, the blockchain network is able to select the block with the best quality of proof from the candidate blocks when a fork occurs. The study in BIB007 proposes to introduce a human-inthe-loop puzzle, i.e., the Proof of Human-work (PoH) into the Nakamoto protocol. The designing goal of PoH is to guarantee the properties of eco-friendliness, usefulness and centralization-resistance at the same time. It is proposed in BIB007 that PoH should be able to provide non-interactive, computer-generated puzzles which are moderately hard for a human but hard for a computer to solve, even for the computer that generates the puzzles. PoH is inspired by the widelyadopted systems of Completely Automated Public Turing-Test to tell Computers and Humans Apart (CAPTCHA) BIB002 . Traditional CAPTCHA systems usually take human-efficient input (e.g., images) with a known solution and generate the puzzle based on distortion to the solution. For PoH, a universal sampler BIB008 is assumed to be available to generate a random CAPTCHA instance for the consensus node such that the puzzle-generating machine is not able to directly obtain the puzzle solution. Then, the node (i.e., miner) needs human work to obtain the corresponding solution of the CAPTCHA puzzle. A two-challenge puzzle design is adopted and the solution of the CAPTCHA puzzle is used as the input of a small PoW puzzle as defined in  . A complete PoH solution includes a CAPTCHA solution and a nonce such that they together satisfy the preimage condition in  . PoH implicitly assumes that some Artificial Intelligence (AI) problems (e.g., recognition of distorted audios or images) are human-efficient but difficult for machines. Then, by selecting a proper underlying CAPTCHA scheme, it is possible to extend the PoH with a variety of meaningful human activities ranging from that educational purposes to a number of socially beneficial programs BIB008 . For a progressive summary, we summarize in Table III the major properties of the PoX schemes reviewed in this section.