ProgPoW algorithm is leaked, Ethereum ASIC mining is unstoppable?

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.

• Bitcoin's biggest loyal fan, Twitter CEO Jack Dorsey again funding Bitcoin developers
• Market analysis: BTC stabilizes and rebounds, is expected to build a curved bottom
• Bitcoin Secret History: What did Satoshi Nakamoto and BM chat in Bitcointalk

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:

1. Fix the seed to any 64-bit value, then calculate mix_hash = hash_mix(block_number, seed) ;
2. Search extra_nonce so that header_hash meets the difficulty criteria;
3. 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:

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 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?

We will continue to update Blocking; if you have any questions or suggestions, please contact us!