The Proof-of-Work Function of Nervos CKB – Nervos Network
Nervos CKB uses a variant of Bitcoin’s Nakamoto Consensus to achieve consensus about the spending rights of network participants. With this mechanism, updates to the system state, called blocks, can be proposed by any node, provided that a) the block is valid; and b) the proposer has solved a computationally difficult puzzle called the proof-of-work. Nodes that continuously try to solve the puzzle to propose the next block are called miners, and are rewarded when successful. Nakamoto Consensus reduces the security of the network against attacks involving re-writing the history, to an assumption about the distribution of computational power, namely that more than 50% of it is in the hands of honest miners.
The proof-of-work puzzle is defined in terms of the block that is being proposed; this guarantees that the solution to the puzzle uniquely identifies a block. Specifically, every block has a unique block_header, that authenticates a selection of transactions and witnesses in the queue to be confirmed. Traditionally, the proof-of-work puzzle consists of finding a valid nonce such that
H(nonce || block_header) <= t .
In this expression,
- t is the difficulty parameter, which is periodically adjusted so as to regulate the average time until the next block;
- || represents concatenation of bit strings;
- nonce is a string of random bits;
- H is a cryptographic one-way hash function.
This hash function H serves several uses.
- Since H is public, any node on the network can verify whether a proposed node is valid simply by evaluating the inequality. Moreover, any node can choose to become a miner without authoritarian permission.
- Since H is difficult to predict, the miner’s best strategy is to guess random nonces and to try again with a new one until the inequality is satisfied. The effect is that the miner’s rewards are linked to his share in the computational power dedicated to securing the network.
For Bitcoin, the hash function H is twice-iterated SHA2–256. In hindsight, the choice to iterate this function twice seems a little paranoid: nearly two decades of cryptanalysis has failed to produce meaningful attacks. Nevertheless, at the time when Bitcoin was proposed, it was clear that SHA1 was cracking and about to be broken, SHA2 was much newer, and the SHA3 competition was underway to replace it if it should be broken as well.
While defining the proof-of-work puzzle in terms of SHA2 was a good choice for Bitcoin, the same is not true for cryptocurrencies that come later. A lot of dedicated hardware was developed to mine Bitcoin, and has since been rendered obsolete by improved hardware. A new cryptocurrency using the same proof-of-work puzzle will make the deprecated hardware useful once again. Even hardware that is not obsolete can be rented and repurposed to mine the new coin. As a result, the distribution of mining power is very difficult to predict, and susceptible to sudden and large changes. The same argument applies to algorithmic optimizations tailored to SHA2 that can make software computation of the function cheaper, as opposed to hardware-based solutions to make hardware-based evaluation cheaper.
For a new cryptocurrency, it makes sense to define the proof-of-work puzzle in terms of a proof-of-work function that has not yet been used by other cryptocurrencies. For Nervos CKB, we went a step further and chose to define it in terms of a proof-of-work function that could not have been the subject of premature optimization because it is new.
The intended unavailability of mining hardware should only describe the initial situation. In the long run, the presence of dedicated mining hardware is a good thing because it helps to make a network attack harder. A good proof-of-work function for a new cryptocurrency is therefore both new and simple; the second property lowers the barrier for hardware development.
Security is the obvious third design goal. While a known vulnerability could be exploited by all miners equally and would merely result in a higher difficulty, an undisclosed vulnerability could lead to a mining optimization providing the vulnerability’s discoverers with an advantage in excess of their contributed mining power share. The best way to avoid this situation is to make a strong argument for invulnerability.
This is where Eaglesong comes in.
Eaglesong is a new hash function developed specifically for Nervos CKB proof-of-work, but also suitable in other use cases where a secure hash function is needed. The design criteria were exactly these — novelty, simplicity and security. We wanted a design that was simultaneously novel enough to constitute a small step forward for science, as well as close enough to existing designs to make a strong security argument possible and palatable. To this end, we chose to instantiate the sponge construction (same as Keccak/SHA3) with a permutation built from ARX operations (addition, rotation, and xor — simple!), and make an argument for its security based on the wide trail strategy (same argument underlying the AES). To the best of our knowledge, Eaglesong is the first hash function (or function, for that matter) that successfully combines all three design principles. For more details on the design and design choices of Eaglesong we refer to the paper, which will be out soon. Note that the specifications for Eaglesong as the proof-of-work function for Nervos CKB differ slightly (in a way that does not impact the function’s security analysis); for these specs we refer to the RFC.
What does security mean, exactly? The property that makes a hash function suitable for a proof-of-work puzzle such as the one described here is called multi-target one-wayness. This property is defined with respect to a game in which the adversary is given a list of targets, and he wins if he can produce a single preimage under H to any one of the targets. A function H has this property if no adversary can do better than trial and error. However, hash functions generally possess other properties, such as second preimage resistance, collision resistance, and correlation intractability. An attack on one property does not automatically translate to an attack on another property. As a result, it is methodologically sound to instantiate a proof-of-work puzzle with a function that is only multi-target one-way. Nevertheless, in the design of Eaglesong we set the number of rounds such that the resulting permutation would be indistinguishable from a random permutation given the allowed amount of work. A consequence of the sponge framework is that the resulting function possesses all security properties typically associated with hash functions.
For more details, please check the full RFC: https://github.com/nervosnetwork/rfcs/pull/129
Capturing the majestic call of an eagle, this mystical horn brings limitless dexterity to those who hear it.
Published at Sat, 20 Jul 2019 01:41:51 +0000
Bitcoin Pic Of The Moment
If you enjoy my photos, you are welcome to #donate #bitcoin to me at: 1Q2LV3bsxZjRBQoRXAXikpUGPCrNeGSUWc
By antwerpenR on 2013-07-22 16:56:10
