Introducing Eaglesong, Nervos’s New Hash Function for CKB Proof-of-Work

by Alan Szepieniec, cryptography researcher at Nervos.

The full RFC is available here: https://github.com/nervosnetwork/rfcs/pull/129

Today we announce a new hash function for Nervos CKB, which we call Eaglesong. We believe this is the first hash function that successfully combines the three design imperatives of novelty, simplicity, and security. Later in this post we explain in detail the thinking behind its development and the benefits it conveys. First, a little background:

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, which 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 came later. A lot of the dedicated hardware developed to mine Bitcoin has now been rendered obsolete. 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 large and sudden 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. The first two design goals for a new cryptocurrency’s proof-of-work function should therefore be newness and simplicity; 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 those who discover the vulnerability with an advantage disproportionate to 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. It is also suitable in other use cases where a secure hash function is needed. The design criteria were exactly those described above — novelty, simplicity and security. We wanted a design that was novel enough to constitute a small step forward for science, but still 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).

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.

To the best of our knowledge, Eaglesong is the first hash function (or function of any kind, for that matter) that successfully combines all three design principles. 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 you to the full RFC: https://github.com/nervosnetwork/rfcs/pull/129 .

Stay updated on Nervos: Twitter, Reddit, Youtube, Telegram, Github