Ethash verification in contracts

To implement trustless bridges between Beam and other blockchains there's a need to verify the headers of the appropriate blockchains in the contract. For a PoW-based blockchain there's a need to verify the appropriate header PoW.

Ethereum mined according to Ethash PoW algorithm. Turns out not only mining, but even the verification of Ethash is a complex task for a contract.

Ethash

Ethash is designed to be memory-hard. Its hi-level design:

• Mining parameters (a.k.a. Epoch) are changed each 30K blocks (roughly 5.2 days)
• For the current Epoch a Cache is generated, which as a pseudo-random opaque data set.
  • Its size is gradually increased with each Epoch, as of today its size is roughly 70MB.
  • The cache generation is deliberately complex. Each element depends on the previous (so that it can't be parallelized), and CPU-intensive hash function is used.
  • As for today it takes several seconds to calculate on a typical desktop machine.
• There is a much larger Dataset that can be calculated from the cache.
  • As for today the cache size is roughly 4GB
  • Each element calculation is deliberately complex. Involves CPU-intensive hash functions, and pseudo-random access of cache.
  • Elements however are independent

The PoW puzzle is to find a nonce, from which a 64-element-long pseudo-random path is derived (so-called DAG), whose last element together with the nonce reaches the difficulty target. It is assumed that effective miner should have the Dataset in memory, and probe different pseudo-random DAGs until the needed difficulty target is reached. To verify the PoW only the cache is needed. The chosen DAG elements can effectively be calculated from the cache (since they are independent).

So that, unlike most of the other blockchains, Ethash verification demands significant memory. Once the cache is prepared, the PoW verification is reasonably fast, but still may be considerable if many headers should be verified at once.

For native Ethereum clients this is not a problem. Normally they interpret blocks/headers sequentially (perhaps with slight reorgs), so that the cache can be generated once and kept in memory for ~5 days. The complexity of verification of a header (tens of milliseconds) is also acceptable.

Why Ethash verification is hard in contract

First of, the cache is needed. As we mentioned it has size roughly 70MB (as for today), and computation time of several seconds, even if done natively. This is totally unrealistic for contracts, which are deliberately restricted in both available memory and running time.

One strategy to solve this problem (that we tried) is to provide contracts a special bvm function. It would be like this:

hash256 get_EthashPathEndpoint(int epochNumber, hash512 seed);

The bvm implementation would generate and keep the cache for the specified Epoch in memory, and interpret the needed DAG for the contract. The rest of the header verification (seed derivation, difficulty test, etc.) can be done inside the contract.

This strategy however has the following drawbacks:

• Adding very specialized functions to the bvm is a drawback. We prefer to keep the functions very generic, and avoid specialized functions unless there's no other option.
• Unlike native Ethereum clients, it's not possible to assume that only the current Epoch would be needed. Contracts might need to process headers from the past, as well as headers from different sidechains with different heights.
• Calculating the cache for each requested Epoch is heavy. Pre-calculating and keeping many of them in the local storage is unrealistic too for most of the clients, because of the considerable cache size of each Epoch.
• Since the contract may want to process many Ethereum headers at once, the performance may be complex even with prepared cache.

Our strategy

First let's study the pseudo-code of the supposed get_EthashPathEndpoint is the following:

hash256 get_EthashPathEndpoint(int epochNumber, hash512 seed)
{
    Init MyState from seed;
    loop 64 times:
    {
        derive Index from MyState;
        get hash1024 Element from Dataset of the specified epoch at position Index;
        mutate MyState by Element
    }

    derive Hash256 MixHash from MyState;
    return  MixHash;
}

Note that this code can basically be implemented in the contract. The MyState mutation and consequent Index derivation are pretty simple (use fast hash function). The problem of course is getting the element from the Dataset at the requested Index.