ProgPoW algorithm exposed a vulnerability, is Ethereum ASIC mining unstoppable?

Regarding the controversial ProgPoW algorithm, independent developer kikx disclosed today a vulnerability in the algorithm, which makes it impossible to truly achieve the goal of anti-ASIC. Kikx also added that this vulnerability is newly discovered and will not pose a threat to the Ethash algorithm currently used by Ethereum.

In response, Ethereum developer Philippe Castonguay commented:

“It looks like the current implementation of ProgPoW may not be that ASIC resistant. Basically, the ProgPoW hash function uses a 64-bit seed that ASICs can “easily” brute-force instead of mining as intended. This needs more attention to be officially confirmed.”

Ethereum hard fork coordinator James Hancock later confirmed the existence of the vulnerability and expressed his gratitude.

So what exactly is this loophole about?

Let's take a look at the details disclosed by Kikx:

Design flaws in ProgPoW

ProgPow has a design flaw:

A 64-bit seed is too small, which allows an ASIC to calculate the hash without memory access.

Initial Implementation

Thanks to chfast for the readable implementation!

The ProgPoW hash function is defined as:

 result hash(const epoch_context& context, int block_number, const hash256& header_hash,
uint64_t nonce) noexcept
{
const uint64_t seed = keccak_progpow_64(header_hash, nonce);
const hash256 mix_hash = hash_mix(context, block_number, seed, calculate_dataset_item_2048);
const hash256 final_hash = keccak_progpow_256(header_hash, seed, mix_hash);
return {final_hash, mix_hash};
}

ASIC-friendly computing

Assume that a block header block_header and a block number block_number are given.

Then, follow these 3 steps:

1. Fix seed to any 64-bit value, then calculate mix_hash = hash_mix(block_number, seed);

2. Search extra_nonce so that header_hash satisfies the difficulty condition;

3. Search for nonce so that keccak_progpow_64(header_hash, nonce) == seed;

The first step is to calculate mix_hash for a fixed seed and block_number. Since mix_hash is designed as a function of seed and block_number, we get a valid triple (seed, mix_hash, block_number). Now, our goal is to find a header_hash and nonce that satisfy the following two conditions:

1. (A) keccak_progpow_64(header_hash, nonce) == seed;

2. (B) keccak_progpow_256(header_hash, seed, mix_hash) <= boundary;

Remember, we can generate any number of header hashes by modifying the extra random number (using ExtraData in Ethereum). Therefore, condition (B) is easily accomplished in step 2. Now, we have a fixed (header_hash, seed, mix_hash, block_number), but the nonce is free. Finally, step 3 scans the nonces to find condition (A). Since the seed is only 64 bits long, condition (A) only provides 64 bits of security and step 3 can be performed by ASICs.

Calculate costs

There are four functions, keccak_1600, keccak_progpow_64, hash_mix, and keccak_progpow_256. The cost is calculated by calculating the number of calls to the required function, which depends on the network difficulty D.

In a normal hash calculation, a keccak_1600 call is required to calculate header_hash from block_header, and other functions are called in sequence for each nonce value.

In the ASIC hash calculation, a hash_mix call is required in step 1, keccak_1600 and keccak_progpow_256 are called in step 2, and keccak_progpow_64 is called in step 3.

Since hash_mix is ​​only called once in our ASIC calculation, we can use the host CPU to calculate hash_mix. The other functions are all keccak hash functions, which do not require memory storage and can be easily calculated on the ASIC.

We need to compare D in the keccak_progpow_64 row to 2^64. Simply put, a larger D makes ASICs more profitable. Estimating the threshold is difficult, but I think the current difficulty (> 2^50) is large enough.

Demo

The demo is located in this repository.

 $ git clone https://github.com/kik/progpow-exploit.git
$ cd progpow-exploit
$ mkdir build
$ cd build
$ cmake ..
$ make
$ ./test/ethash-test --gtest_filter=asic.search

In this demo, the seed is truncated to 24 bits in width to run on the CPU. See the code.

The test code is simple.

search_asic is defined here

Given the existence of this vulnerability, can Ethereum mining machine manufacturers breathe a sigh of relief?