A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> 85, Definition 1]): <s> In this paper we describe simple identification and signature schemes which enable any user to prove his identity and the authenticity of his messages to any other user without shared or public keys. The schemes are provably secure against any known or chosen message attack if factoring is difficult, and typical implementations require only 1% to 4% of the number of modular multiplications required by the RSA scheme. Due to their simplicity, security and speed, these schemes are ideally suited for microprocessor-based devices such as smart cards, personal computers, and remote control systems. <s> BIB001 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> 85, Definition 1]): <s> A new digital signature based only on a conventional encryption function (such as DES) is described which is as secure as the underlying encryption function -- the security does not depend on the difficulty of factoring and the high computational costs of modular arithmetic are avoided. The signature system can sign an unlimited number of messages, and the signature size increases logarithmically as a function of the number of messages signed. Signature size in a 'typical' system might range from a few hundred bytes to a few kilobytes, and generation of a signature might require a few hundred to a few thousand computations of the underlying conventional encryption function. <s> BIB002 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> 85, Definition 1]): <s> In this paper, we define and explore proofs of retrievability (PORs). A POR scheme enables an archive or back-up service (prover) to produce a concise proof that a user (verifier) can retrieve a target file F, that is, that the archive retains and reliably transmits file data sufficient for the user to recover F in its entirety. A POR may be viewed as a kind of cryptographic proof of knowledge (POK), but one specially designed to handle a large file (or bitstring) F. We explore POR protocols here in which the communication costs, number of memory accesses for the prover, and storage requirements of the user (verifier) are small parameters essentially independent of the length of F. In addition to proposing new, practical POR constructions, we explore implementation considerations and optimizations that bear on previously explored, related schemes. In a POR, unlike a POK, neither the prover nor the verifier need actually have knowledge of F. PORs give rise to a new and unusual security definition whose formulation is another contribution of our work. We view PORs as an important tool for semi-trusted online archives. Existing cryptographic techniques help users ensure the privacy and integrity of files they retrieve. It is also natural, however, for users to want to verify that archives do not delete or modify files prior to retrieval. The goal of a POR is to accomplish these checks without users having to download the files themselves. A POR can also provide quality-of-service guarantees, i.e., show that a file is retrievable within a certain time bound. <s> BIB003 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> 85, Definition 1]): <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> BIB004 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> 85, Definition 1]): <s> Abstract : The Tor network relies on volunteer relay operators for relay bandwidth, which may limit its growth and scaling potential. We propose an incentive scheme for Tor relying on two novel concepts. We introduce TorCoin, an altcoin that uses the Bitcoin protocol to reward relays for contributing bandwidth. Relays mine TorCoins, then sell them for cash on any existing altcoin exchange. To verify that a given TorCoin represents actual bandwidth transferred, we introduce TorPath a decentralized protocol for forming Tor circuits such that each circuit is privately-addressable but publicly veriable. Each circuit's participants may then collectively mine a limited number of TorCoins, in proportion to the end-to-end transmission goodput they measure on that circuit. <s> BIB005 </s> A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks <s> 85, Definition 1]): <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> 85, Definition 1]): <s> The blockchain technology is gaining momentum because of its possible application to other systems than the cryptocurrency one. Indeed, blockchain, as a de-centralized system based on a distributed digital ledger, can be utilized to securely manage any kind of assets, constructing a system that is independent of any authorization entity. In this paper, we briefly present blockchain and our work in progress, the VMOA blockchain, to secure virtual machine orchestration operations for cloud computing and network functions virtualization systems. Using tutorial examples, we describe our design choices and draw implementation plans. <s> BIB007
Definition 2 (Usefulness). Suppose that a challenge c x and an accompanying puzzle solution (proof) s are generated from an input string x. If there exists an algorithm Recon(c x , s) such that for a target function F (·) its output satisfies Recon(c x , s) = F (x), the challenge is known to be useful for delegating the computation of F (x). The study in  proposes to replace preimage searching in (1) with a family of one-way functions satisfying the property of fine-grained hardness  for uPoW puzzle design. Namely, the PoW puzzle is proposed to be replaced by the problem of known worst-case-to-average-case complexity reduction. A special case of uPoW puzzles based on the problem of k-Orthogonal Vectors (k-OV) is discussed. In brief, the solution to k-OV performs an exhaustive search over k sets of identical-dimension vectors and determines whether for each set there exists a vector such that these k vectors are k-orthogonal. In order to construct non-interactive proofs, uPoW in  employs the hash function H(·) as a random oracle. Simply put, given the number of vectors in each set, non-interactive uPoW treats the elements of each vector as the random coefficients of polynomials with the identical order. uPoW initializes the first element of each vector, i.e., the lowest order coefficient with a publicly known input string x and then uses it as the input to H(·) for generating the next-order coefficient. The output of H(x) will then be iteratively used as the input for generating the next-order coefficient. This can be considered as a typical example of applying the Fiat-Shamir scheme BIB002 to construct non-interactive PoW out of interactive ZKP schemes. With such an approach, uPoW does not need to explicitly define the vector sets. It also guarantees that the solutions of k-OV found by each prover follow a Bernoulli distribution. Therefore, the uPoW scheme fits well in the existing Nakamoto protocols by simulating a provable random function. As stated in  , besides k-OV, uPoW is compatible with computation delegation for other problems such as 3SUM  , all-pairs shortest path  , and any problem that reduces to them 12 . Schemes that are similar to uPoW can also be found in  . In  , the problem of untrusted computational work assignment is addressed in a Trusted Execution Environment (TEE). The TEE can be constructed using Intel Software Guard Extensions (SGX), which is a set of new instructions available on certain Intel CPUs to protect user-level codes from attacks by hardware and other processes on the same host machine. In the permissionless network, the clients supply their workloads in the form of tasks that can be run in an SGXprotected enclave (i.e., protected address space). The study in  exploits the truthfulness-guaranteeing feature of the Intel attestation service  in the SGX-protected platform to verify and measure the software running in an enclave. With the designed puzzle, the work of each consensus node is metered on a per-instruction basis, and the SGX enclave randomly determines whether the work results in a valid block proof by treating each instruction as a Bernoulli trial. Based on the TEE, each executed useful-work instruction is analogous to one hash query in the primitive PoW, and the enclave module works as a trusted random oracle. Apart from delegation of useful computation, PoX can also be designed to incentivize distributed storage provision. For example, Permacoin BIB004 proposes a scheme of Proof of Retrievability (PoR) in order to distributively store an extremely large size of data provided by an authoritative file dealer. The file dealer divides the data into a number of sequential segments and publishes the corresponding Merkle root using the segments as the leaves. A consensus node uses its public key and the hash function to select a random group of segment indices for local storage. For each locally stored segment, the node also stores the corresponding Merkle proof derived from querying the Merkle tree. The challengeproof pair is generated based on a subset of the locally stored segments and the corresponding Merkle proof. To ensure the non-interactiveness and freshness of the puzzle (cf. interactive PoR in BIB003 ), the node needs a publicly known and nonprecomputable puzzle ID to seed the process of segment selection called "scratch-off". To help the readers understand the puzzle generation process, we present a simplified execution stage of PoR as follows (see also [110, Figure 1 ]): • The execution stage of PoR: suppose a node is given the key pair (sk, pk), the puzzle ID id puz , the vector of locally stored segment indices v, the required number of Merkle proofs k, the vectors of all the file segments U and the corresponding Merkle proof vector π. The random IDs of the local segments for challenge generation can be determined by: where nonce is a random value chosen by the node. For each segment U(v(r j )) in the challenge, the proof is in the form of (pk i , nonce, U(v(r j )), π(v(r j ))). The execution stage of PoR in BIB004 is composed of a fixed number of queries to the random oracle H. Thereby, although PoR satisfies the principle properties of non-interactive ZKP, it does not simulate the random leader election process. In this sense, the proposed PoR scheme may not be able to achieve the claimed goal of "repurposing PoW" in BIB004 . Instead, it is more similar to the existing systems such as Stoj  , Sia  and TorCoin BIB005 , where PoX is only used to audit the execution of the smart contracts or script-based transactions instead of facilitating the consensus mechanism. Further improvement to PoR can be found in the proposals of KopperCoin BIB006 and Filecoin [37] . In BIB006 , KopperCoin adopts the same framework of distributed storage for a single file as in Permacoin BIB004 . Compared with Permacoin, the main improvement of the puzzle design in KopperCoin is to simulate the random leader election process for block proposal. KopperCoin introduces a bitwise XOR-based distance metric between the index of a locally stored data segment and a random, publicly known challenge c. A node needs to provide the valid Merkle proof (PoR) of a segment, of which the index (denoted by j) should satisfy the following condition: where the block payload x and the difficulty threshold D(h) are defined in the same way as in Definition 1. Compared with (1), the solution searching for (10) is now performed within the range of the locally-stored segment indices. The more segments a node offers to store, the better chance the node has to find a solution to BIB007 . Again, the generation of the public, unpredictable random challenge c can be derived based on hashing the header of the most recent block. This approach presents another example of applying the Fiat-Shamir transformation to realize non-interactiveness BIB001 . In the Filecoin network [37], the concept of "spacetime" is introduced to allow metering the data stored in the network with an expiry time. Filecoin aims to provide the functionality of recycling and re-allocating the storage on the provider (miner) side as well as easing the files retrieval process on the client side. Like in the proof-of-exercise scheme, Filecoin designs the market for storage and retrieval of multiple files based on smart contracts. A new puzzle, i.e., Proof of SpaceTime (PoST)  , is adopted based on the intuition of generating a PoR sequence during a certain period to prove the holding time of useful storage. As illustrated by Figure 9 , the major difference of PoST from PoR lies in the repeated execution phases for challenge updating without rerunning the initialization stage. Namely, a consensus node is required by the Filecoin network to submit PoR (e.g., in a similar way to Permacoin BIB004 ) every time when the blockchain is extended by a certain number of blocks. Instead of simulating random leader election based on adjustable difficulty BIB006 , the Filecoin network uses the following mechanism to determine whether a node i is elected for block proposal: where t is the index of consensus round (i.e., block index), L is the output string length of the hash function (see (1)), rand(·) is an assumed random oracle, and w i represents the storage power of node i (see also (2)). It is worth noting that the evaluation of w i in (11) can only be done through PoST. Thus, the Filecoin network admits a double-challenge scheme, where the leader election is performed based on a second challenge, i.e., BIB002 . The nodes with the better quality of PoST proofs (storage power) are more likely to win the second challenge. Under the framework of double challenges, a similar approach of puzzle design can also be found in the proof of space-based cryptocurrency proposal known as SpaceMint  ,  .