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

In this regard, Ethereum developer Philippe Castonguay commented:

"It looks like the current implementation of ProgPoW may not be as resistant to ASICs. Basically, the ProgPoW hash function uses a 64-bit seed, and ASICs can be" easily "enforced instead of mining as expected. This requires More attention to formal confirmation. "

Since then, James Hancock, the Ethereum hard fork coordinator, confirmed the existence of this vulnerability and thanked him.

So is this loophole swollen?

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

## ProgPoW Design Vulnerability

ProgPow has a design flaw:

The 64-bit

`seed`

too small, which allows the ASIC to calculate the hash without memory access.

#### Preliminary realization

Thanks chfast for providing a 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`

.

Then, perform the following 3 steps:

- Fix the
`seed`

to any 64-bit value, then calculate`mix_hash = hash_mix(block_number, seed)`

; - Search
`extra_nonce`

so that`header_hash`

meets the difficulty criteria; - Search for
`nonce`

so that`keccak_progpow_64(header_hash, nonce) == seed`

;

The first step is to calculate the `mix_hash`

for the fixed `seed`

and `mix_hash`

. 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 `header_hash`

and `nonce`

that satisfy the following two conditions:

- (A)
`keccak_progpow_64(header_hash, nonce) == seed`

; - (B)
`keccak_progpow_256(header_hash, seed, mix_hash) <= boundary`

;

Remember, we can generate any number of header hashes by modifying additional random numbers (using ExtraData in Ethereum). Therefore, condition (B) is easily completed in step 2. Now we have a fixed `(header_hash, seed, mix_hash, block_number)`

but `nonce`

is free. Finally, step 3 scans the `nonce`

for the condition (A). Since the `seed`

only 64 bits long, condition (A) only provides 64-bit security, and step 3 can be performed by the ASIC.

#### Computing costs

There are four functions, `keccak_1600`

, `keccak_progpow_64`

, `hash_mix`

and `keccak_progpow_256`

. The cost can be calculated by calling the required function, which depends on the network difficulty `D`

In normal hash calculation, a `keccak_1600`

call is required to calculate the `header_hash`

from the `block_header`

and call other functions in turn for each `nonce`

value.

In ASIC hash calculation, a `hash_mix`

call is required in step 1, `hash_mix`

called in step 2, and `keccak_progpow_256`

called in step 3.

Since `hash_mix`

is called only once in our ASIC calculation, we can use the host CPU to calculate `hash_mix`

. The other functions are keccak hash functions, do not require memory storage, and can be easily calculated on the ASIC.

We need to compare `D`

and `2^64`

`keccak_progpow_64`

row. Simply put, a larger `D`

makes the ASIC more profitable. Estimating the threshold threshold is difficult, but I think the current difficulty (> 2 ^ 50) is large enough.

#### Demo

The demo is 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 a 24-bit width to run on the CPU. See code.

The test code is simple.

Search_asic is defined here Due to this loophole, can Ethereum miners be relieved?