ProgPoW exploit

ASIC friendly computation method of ProgPoW

Design flaw

ProgPow has a design flaw:

64 bit seed is too small,

This allows ASICs compute hash without memory access.

Preliminary

Thanks chfast for providing a readable implementation!

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 Computation

Suppose a block header block_header and a block number block_number are given.

Then, run 3 steps below:

1. fix a seed to any 64 bit value and compute mix_hash = hash_mix(block_number, seed).
2. search extra_nonce so that header_hash meets diffculty condition.
3. search nonce so that keccak_progpow_64(header_hash, nonce) == seed.

In first step, a mix_hash is computed for a fixed seed and block_number. Because mix_hash is designed to be a function of seed and block_number, we get a valid triple (seed, mix_hash, block_number). Now, our goal is find a header_hash and a nonce satisfy 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 hash by modifying extra nonce (use ExtraData in Ethereum). Thus, condition (B) is easily acomplished by step 2. Now, we have a fixed (header_hash, seed, mix_hash, block_number) but nonce is free yet.

Finally, step 3 scans nonce for condition (A). Because seed has only 64 bit length, condition (A) provides only 64 bit security and step 3 can be executed by ASICs.

Computation cost

There are four functions keccak_1600, keccak_progpow_64, hash_mix and keccak_progpow_256. Computation cost can be evaluated by counting these function calls needed before getting an answer. This depends on network difficulty D.

	avg # of calls in normal	avg # of calls in ASIC
keccak_1600	1	D
keccak_progpow_64	D	2^64
hash_mix	D	1
keccak_progpow_256	D	D

In normal hash computation, one keccak_1600 call is needed to compute header_hash from block_header and other functions are sequencially called for each nonce value.

In ASIC hash computation, one hash_mix call is needed 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 called only once in our ASIC computation, we can use host CPU to compute hash_mix. Other functions are all keccak hash function, need no memory, and are easily computed on ASICs.

We need compare D and 2^64 in keccak_progpow_64 row. Simply, larger D makes ASIC more profitable. Estimating profitable threshold is hard, but I think current difficulty (> 2^50) is large enough.

Demo

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, seed is truncated to 24 bit width to run on CPU. See code.

Test code is simple.

search_asic is defined here.

Donations

I beleave disclosing a PoW vulnerability is more profitable than secret mining 😍

ETH: 0xcFc9751Bc71e412c19D877e6401c92d74d8e4344