ProgPoW アルゴリズムに脆弱性が露呈、Ethereum ASIC マイニングは止められないのか?

物議を醸している ProgPoW アルゴリズムに関して、独立系開発者の kikx は本日、このアルゴリズムの脆弱性を公開しました。この脆弱性により、ASIC 対策の目標を真に達成することは不可能になります。 Kikx 氏はまた、この脆弱性は新たに発見されたもので、現在 Ethereum で使用されている Ethash アルゴリズムに脅威を与えるものではないとも付け加えた。

これに対して、イーサリアム開発者のフィリップ・カストンガイ氏は次のようにコメントした。

「ProgPoW の現在の実装は、ASIC 耐性がそれほど高くないようです。基本的に、ProgPoW ハッシュ関数は 64 ビットのシードを使用しますが、ASIC は、意図したとおりにマイニングするのではなく、これを「簡単に」ブルートフォース攻撃することができます。これを公式に確認するには、さらに注意が必要です。」

イーサリアムのハードフォークコーディネーターのジェームズ・ハンコック氏は後に脆弱性の存在を確認し、感謝の意を表した。

では、この抜け穴とは一体何なのでしょうか?

Kikx が公開した詳細を見てみましょう。

ProgPoWの設計上の欠陥
ProgPow には設計上の欠陥があります。
64 ビットのシードは小さすぎるため、ASIC はメモリにアクセスせずにハッシュを計算できます。
初期実装
読みやすい実装を提供してくれた chfast に感謝します。
ProgPoW ハッシュ関数は次のように定義されます。
結果ハッシュ(const epoch_context& context, int block_number, const hash256& header_hash,
uint64_t nonce) 例外なし
{
const uint64_t シード = keccak_progpow_64(header_hash、nonce);
const hash256 mix_hash = hash_mix(コンテキスト、ブロック番号、シード、calculate_dataset_item_2048);
定数hash256 final_hash = keccak_progpow_256(header_hash、seed、mix_hash);
{final_hash, mix_hash} を返します。
}
ASICフレンドリーなコンピューティング
ブロックヘッダー block_header とブロック番号 block_number が指定されていると仮定します。
次に、次の 3 つの手順に従います。
シードを任意の 64 ビット値に固定し、 mix_hash = hash_mix(block_number, seed); を計算します。
header_hash が難易度条件を満たすように extra_nonce を検索します。
keccak_progpow_64(header_hash, nonce) == seed となるように nonce を検索します。
最初のステップは、固定のシードとブロック番号の mix_hash を計算することです。 mix_hash は seed と block_number の関数として設計されているため、有効な 3 つの要素 (seed、mix_hash、block_number) が得られます。ここでの目標は、次の 2 つの条件を満たす header_hash と nonce を見つけることです。
(A) keccak_progpow_64(header_hash、nonce) == シード;
(B) keccak_progpow_256(header_hash、seed、mix_hash) <= 境界;
覚えておいてください、追加の乱数を変更することで、任意の数のヘッダーハッシュを生成できます (Ethereum の ExtraData を使用)。したがって、条件 (B) はステップ 2 で簡単に達成できます。これで、(header_hash、seed、mix_hash、block_number) は固定されますが、nonce は自由になります。最後に、ステップ 3 では条件 (A) の nonce をスキャンします。シードの長さは 64 ビットしかないため、条件 (A) では 64 ビットのセキュリティしか提供されず、ステップ 3 は ASIC によって実行できます。
コストを計算する
関数は keccak_1600、keccak_progpow_64、hash_mix、keccak_progpow_256 の 4 つです。コストは、ネットワーク難易度 D に応じて必要な関数の呼び出しを計算することによって計算できます。
通常のハッシュ計算では、block_header から header_hash を計算するために keccak_1600 呼び出しが必要であり、その他の関数は nonce 値ごとに順番に呼び出されます。
ASIC ハッシュ計算では、ステップ 1 で hash_mix 呼び出しが必要であり、ステップ 2 で keccak_1600 と keccak_progpow_256 が呼び出され、ステップ 3 で keccak_progpow_64 が呼び出されます。
hash_mix は ASIC 計算で 1 回だけ呼び出されるため、ホスト CPU を使用して hash_mix を計算できます。その他の関数はすべて keccak ハッシュ関数であり、メモリストレージを必要とせず、ASIC 上で簡単に計算できます。
keccak_progpow_64 行の D を 2^64 と比較する必要があります。簡単に言えば、D が大きいほど ASIC の収益性が高まります。閾値を見積もることは困難ですが、現在の難易度 (> 2^50) は十分に大きいと思います。
デモ
デモはこのリポジトリにあります。
 $ git クローン https://github.com/kik/progpow-exploit.git
$ cd progpow-exploit
$ mkdir ビルド
$ cd ビルド
$ cmake ..
$ 作る
$ ./test/ethash-test --gtest_filter=asic.search
このデモでは、CPU 上で実行するためにシードは 24 ビット幅に切り捨てられます。コードを参照してください。
テストコードはシンプルです。
search_asicはここで定義されます