ProgPoW算法被曝漏洞，以太坊ASIC挖矿已不可阻挡？

ProgPoW的设计漏洞

ProgPow存在一个设计缺陷：

64位 seed 太小了，这允许ASIC无需存储访问即可计算哈希。

初步实现

感谢chfast提供了可读的实现！

ProgPoW 哈希函数被定义为：

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友好计算

假设给出了一个区块头
block_header 以及一个区块数
block_number

。

然后，执行以下3个步骤：

1. 将 seed 固定为任何64位值，然后计算 mix_hash = hash_mix(block_number, seed) ；
2. 搜索 extra_nonce ，以便 header_hash 满足难度条件；
3. 搜索 nonce ，以便 keccak_progpow_64(header_hash, nonce) == seed ；

第一步，为固定
seed 和
block_number 计算
mix_hash 。由于
mix_hash 被设计为
seed 和
block_number 的函数，所以我们得到一个有效的三元组
（seed，mix_hash，block_number） 。现在，我们的目标是找到满足以下两个条件的
header_hash 和
nonce

：

keccak_progpow_64(header_hash, nonce) == seed
keccak_progpow_256(header_hash, seed, mix_hash) <= boundary

记住，我们可以通过修改额外的随机数（在以太坊中使用ExtraData）来生成任意数量的header哈希。因此，条件（B）很容易在步骤2中完成。现在，我们有一个固定的
(header_hash, seed, mix_hash, block_number) ，但
nonce 是自由的。 最后，步骤3扫描
nonce 以查找条件（A）。由于
seed

只有64位长度，所以条件（A）仅提供64位安全性，并且可以由ASIC执行步骤3。

计算成本

有四个函数，
keccak_1600 ，
keccak_progpow_64 ，
hash_mix 以及
keccak_progpow_256 。成本的计算，可通过计算所需函数的调用来实现，这取决于网络难度
D

。

在正常的哈希计算中，需要一个 keccak_1600 调用，才能从 block_header 计算出 header_hash ，并针对每个 nonce 值依次调用其他函数。

而在ASIC哈希计算中，在步骤1中需要一个 hash_mix 调用，在步骤2中则要调用 keccak_1600 和 keccak_progpow_256 ，在步骤3中将调用 keccak_progpow_64 。

由于 hash_mix 在我们的ASIC计算中仅被调用一次，因此我们可以使用主机CPU来计算 hash_mix 。而其它函数都是keccak哈希函数，不需要memory存储，并且可以在ASIC上轻松计算。

我们需要比较 keccak_progpow_64 row中的 D 和 2^64 。简单地说，更大的 D 会使ASIC更有利可图。估计阈值门槛是困难的，但我认为目前的难度 (> 2^50)是足够大的。

Demo

演示位于此存储库中。

$ 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

在此演示中，seed被截断为24位宽度，以便在CPU上运行。参见代码。

测试代码是简单的。

这里定义了search_asic