More than 3 years have passed since last update.

KawPowで使われているProgPoWアルゴリズム文書の翻訳

Posted at 2021-05-07

ProgPoW

ifdefelse氏のプログラマティックプルーフ・オブ・ワーク(Programatic Proof-of-Work, ProgPow)の文書を翻訳してみました。イーサリアムでEIP-1057として提案され、RavencoinでKAWPOWとして採用されているアルゴリズムです。Moneroはこれとは別にRandomXをアルゴリズムとして採用しています。RandomXの設計の翻訳はこちらです。

このProgPoWでは加減乗算や論理演算やローテート等のランダムな数学的処理の追加等によりASICでの特化回路の実装を困難にさせているようです。

以下の翻訳はDeepLの翻訳結果を下訳として使用しています。

ProgPoW - プログラマティックプルーフ・オブ・ワーク

ProgPoWは特化ASICが持つ効率性のギャップを埋めるために設計されたプルーフ・オブ・ワークアルゴリズムです。ProgPoWは、汎用ハードウェア（GPU）のほぼすべての部分を利用し、Ethereumネットワークで利用される最も一般的なハードウェアに合わせてあらかじめ調整されています。

最初のビットコインマイニングASICがリリースされて以来多くの新しいプルーフ・オブ・ワークアルゴリズムが『ASIC耐性(ASIC-resistance)』を意識して作られてきました。『ASIC耐性』の目的は、PoWマイニングパワーの中央集権化に抵抗し、少数のプレイヤーによってコインが簡単に操作されないようにすることです。

このドキュメントではアルゴリズムの概要を説明し『ASIC耐性』とは何かを検証します。次に、各アルゴリズムがハードウェアでどのように実行されるかを分析し、既存のPoWデザインと比較します。最後にコードを見ながら詳細な実装を紹介します。

ビルドとテストの手順

このリポジトリを ProgPOW にクローンした後、以下のようなコマンドでビルドできます。

cd ProgPOW
git submodule update --init --recursive
mkdir build
cd build
cmake .. -DETHASHCUDA=ON
make -sj8

次のコマンドでベンチマークを行いました。

ethminer/ethminer -U -M 10000000
ethminer/ethminer -G -M 10000000

それぞれCUDAやOpenCLを使用します。

ProgPoW の概要

ProgPoWの設計目標はアルゴリズムの要件を汎用GPUで利用可能なものと一致させることです。アルゴリズムをカスタムASICに実装した場合、汎用GPUと比較して効率化する機会はほとんどないでしょう。

このアルゴリズムの主な要素は以下の通りです。

keccak_f1600（64ビットワード）をkeccak_f800（32ビットワード）に変更し、総電力への影響を低減
混合状態を増加
メインループにランダムな数学的演算列を追加
ランダムアドレスに対応する小さく低レイテンシーなキャッシュからの読み出しを追加
DRAMの読み出しを128バイトから256バイトに変更

ランダムシーケンスはPROGPOW_PERIOD（50ブロックまたは約12.5分）ごとに変化します。マイニング時にランダムシーケンスに対応したソースコードを生成しホストCPU上でコンパイルします。 GPUはどのような計算を行いどのような混合状態を使用するか解決済みのコンパイルされたコードを実行します。

このアルゴリズムを実装するためにカスタムASICを使用することは可能ですが、得られる効率の向上はわずかです。上記の要素をサポートするには汎用GPUの大部分が必要です。利用可能な最適化は次のとおりです。

グラフィックスパイプライン（ディスプレイ、ジオメトリエンジン、テクスチャリングなど）の削除
浮動小数点演算の削除
ISA の調整（merge()関数と完全に一致する命令など）

これらによって得られる効率の向上はおよそ1.1〜1.2倍というわずかなものです。これはEthashの2倍やCryptonightの50倍に比べるとはるかに少ないです。

汎用ハードウェアでのPoWの合理性

大規模なマイニングプールの成長に伴い、小規模なマイナーに安定した経済的リターンを提供するのはハッシュパワーの制御は上位数社のプールに委ねられています。大規模な中央集権型のプールは『ASIC耐性』の目的に反するという意見もありますが、ASICベースのコインはいくつかの理由でさらに中央集権的であることに注意する必要があります。

自然な分配なし：マイニング以外の経済的な目的がないため、ほとんどの人が超特殊なハードウェアを持つ理由がありません。
リザーブグループなし：コインの価格が変動して操作しやすくなったときにハードウェアのリザーブグループや利害関係者のリザーブグループが存在しません。
参入障壁大：初期の採掘者は新しいコインがどうなるかわからないという未知の実験に資本や生態系資源を投資できるお金持ちです。そのため、マイニングによる初期コインの流通は非常に限られたものとなり、中央集権的な経済の偏りを引き起こします。
委任型中央集権と実装型中央集権：プールの集中化は委任されているがハードウェアの独占化は委任されていません。このハードウェアのリミッター購入者だけが参加できるので、急にコントロールを放棄する可能性すらありません。
マイニングが分散化されても明らかなコントロールの分散化なし：大規模なカスタムASICメーカーがこのゲームに参入すれば、バックドア型のハードウェアを設計することは簡単です。ASICメーカーには市場参加において透明性や公平性を保つインセンティブがありません。

『ASIC耐性』という目標は貴重ですが、『ASIC耐性』という概念全体が少し間違っています。 CPUやGPUはそれ自体がASICです。汎用ASIC（CPUやGPU）で動作するどんなアルゴリズムでもそのアルゴリズム用にカスタマイズされたASICを作成することができますが、そのASICの機能は若干劣ります。アルゴリズムの中には意図的に『ASICフレンドリー(ASIC friendly)』に作られているものもあります。つまり、ASICで実装した方が同じアルゴリズムを汎用ハードウェアで実行した場合よりもはるかに効率的なのです。コインが未知のものであるときに『ASIC耐性』が保護を提供するからこそ、コインが有用になるとすぐに専用のマイニングASIC企業には魅力的なターゲットになります。

したがって、『ASIC耐性』とは『特化したハードウェアと広く普及しているハードウェアの効率の差』ということになります。カスタムハードウェアと汎用ハードウェアの効率の差が小さいほど耐性が高く優れたアルゴリズムであることを意味します。この効率の差がPoWアルゴリズムの品質を比較する際の適切な指標となります。効率とは絶対的な性能・ワットあたりの性能・ドルあたりの性能などを意味しますが、これらはいずれも高い相関関係があります。もし単一の企業が飛躍的に効率的なASICを作成して制御すれば、ネットワークのハッシュレートの51％を獲得し攻撃を仕掛けることができます。

既存のPoWアルゴリズムの批評

SHA256

ASICの効率化の可能性1000倍

SHAアルゴリズムは加算・論理演算・ローテートなどの単純な数学演算の連続です。

CPUやGPUで1つの演算を処理するためには命令のフェッチとデコード・レジスタファイルからのデータの読み込み・命令の実行・結果のレジスタファイルへの書き戻しなどが必要となります。これには膨大な時間と電力がかかります。

一方、ASICでは1つの演算に必要なトランジスタや配線の数はわずかです。つまり、1つ1つの演算にかかる電力・面積・時間はごくわずかなのです。ハッシュコア(hashing core)は必要な演算の列を並べて作ります。

ハッシュコアは必要な一連の処理をCPUやGPUで行うよりもはるかに短い時間や少ない電力や面積で実行することができます。ビットコインASICは複数の同一のハッシュコアと最小限のオフチップ通信で構成されます。

ScryptとNeoScrypt

ASICの効率化の可能性は1000倍

ScryptとNeoScryptは使用する算術演算やビット演算がSHAと似ています。残念ながらLitecoinなどの人気コインはPoWマイニングアルゴリズムに32kbから128kbの間のスクラッチパッドサイズしか使用していません。このスクラッチパッドはASIC上で演算コアの隣に些細に収まる程度の大きさです。数学コアの実装はSHAと非常に似ており同様の効率化が図れます。

X11およびX16R

ASICの効率化の可能性は1000倍

X11（および類似の X##）では11 個の独自のハッシュコアを一定の順序でパイプライン化した ASIC が必要です。個々のハッシュコアは個々のSHAコアと同様の効率を持つため、全体的な設計では同じ効率が得られることになります。

X16Rでは複数のハッシュコアがシンプルなシーケンスステートマシンを介して相互に作用する必要があります。個々のコアは同様の効率を得ることができ、シーケンシングロジックは最小限の電力・面積・時間で済みます。

Baikal BK-Xは複数のハッシュコアとプログラマブルシーケンサを備えた既存のASICです。これをアップグレードすることで異なる順序でハッシュを並べる新しいアルゴリズムが可能になりました。

Equihash

ASICの効率化の可能性は100倍

150MBの状態は大きいがASICで可能です。ビット列の前処理(binning)・ソート・比較をASICで超高速に実装できます。

Cuckoo Cycle

ASICの効率化の可能性は100倍

時間とメモリのトレードオフ攻撃があるため、オンチップで必要なステートの量は明確ではありません。グラフ探索に特化したコアであればSHA計算コアと同様の効率化が可能です。

CryptoNight

ASICの効率化の可能性は50倍

CryptoNight は Scrypt と比較して計算量が非常に少なく、2MB のスクラッチパッドを必要とします（時間/メモリのトレードオフ攻撃は知られていません）。大きなスクラッチパッドはASICの実装を支配しハッシュコアの数を制限するため、ASICの絶対的な性能を制限することになります。 ASIC はほとんどオンダイ SRAM のみで構成されます。

Ethash

ASICの効率化の可能性は2倍

EthashはDAGのサイズが大きいため外部メモリが必要です。しかし、必要なのはそれだけであり、メモリから読み込まれた結果に対して行われる計算は最小限です。その結果、カスタムASICはGPUの複雑さとパワーのほとんどを取り除き、小さな計算エンジンに接続されたメモリインターフェースにすることができます。

ProgPoW アルゴリズムの実地検証

release 0.9.3までは、DAGはEthashと全く同じように生成されます。すべてのパラメータ（エポック長、DAGサイズなど）は変更されていません。 DAGの生成に関する詳細はオリジナルのEthashの仕様を参照してください。

release 0.9.3は次のソフトウェアおよびハードウェアの監査を受けています。

Least Authority - ProgPoW Software Audit PDF (訳注: リンク切れ。おそらくこれです)
Bob Rao - ProgPoW Hardware Audit PDF

Least Authority社の調査結果によると、新しい提案されたrelease 0.9.4では『Light Evaluation』攻撃の可能性を軽減するためにDAGの生成に微調整を行っています。
この変更によりETHASH_DATASET_PARENTSの値が256から512に変更されました。これにより、ProgPoWで使用されるDAGメモリファイルはEthashで使用されるものと互換性がなくなりました（エポック長とサイズ増加率は変わりません）。

監査リリース後、Kikによる巧みな発見により、ProgPoWメモリの硬直性をバイパスする悪用可能な条件が開示されました。この問題を解決するにはマイナーが修正したブロックヘッダを受け入れることができるカスタマイズされたノードが必要です。今回の新仕様リリースの目的は、最後のkeccakパスの入力状態を変更する条件にパッチを当て、以下のように変更することです。

ヘッダー（256ビット）＋
ミックス・イニシエータのシード（64ビット）＋
メインループからのミックス(256ビット)
パディングなし
初期keccak（256ビット）からのダイジェスト＋
メインループからの混合（256ビット）＋
パディング、結果keccakのbrute force keccak linear searchesの対象となる制約が64ビットから256ビットに拡大

ProgPoWは以下のパラメータで調整できます。提案されている設定は既存の様々な汎用GPU向けに調整されています。

PROGPOW_PERIOD: ランダムプログラムを変更するまでのブロック数
PROGPOW_LANES: 1つのハッシュインスタンスを計算するために調整する並列レーンの数
PROGPOW_REGS: レジスタファイルの使用サイズ
PROGPOW_DAG_LOADS: レーンあたりのDAGからのuint32ロードの数
PROGPOW_CACHE_BYTES: キャッシュのサイズ
PROGPOW_CNT_DAG:アルゴリズムの外側のループとして定義されるDAGアクセスの数(64はEthashと同じ)
PROGPOW_CNT_CACHE: ループごとのキャッシュアクセスの回数
PROGPOW_CNT_MATH: ループあたりの数学的操作の回数

これらのパラメータの値はバージョン0.9.2（Gangnam testnetでのライブ）と0.9.3（Ethereum adoptionへの提案）の間で微調整されています。詳しくはこのmediumへの投稿をご覧ください。release 0.9.4では、0.9.3の調整項目はそのままに、DAG生成のための調整項目を追加しています。

パラメータ	0.9.2	0.9.3	0.9.4
`PROGPOW_PERIOD`	`50`	`10`	`10`
`PROGPOW_LANES`	`16`	`16`	`16`
`PROGPOW_REGS`	`32`	`32`	`32`
`PROGPOW_DAG_LOADS`	`4`	`4`	`4`
`PROGPOW_CACHE_BYTES`	`16x1024`	`16x1024`	`16x1024`
`PROGPOW_CNT_DAG`	`64`	`64`	`64`
`PROGPOW_CNT_CACHE`	`12`	`11`	`11`
`PROGPOW_CNT_MATH`	`20`	`18`	`18`

DAG パラメータ	0.9.2	0.9.3	0.9.4
`ETHASH_DATASET_PARENTS`	`256`	`256`	`512`

ランダムプログラムは、アルゴリズムを実行するハードウェアが完全にプログラム可能であることを保証するために、PROGPOW_PERIODブロック（デフォルトでは10、約2分）ごとに変更されます。プログラムがDAGエポック（約5日）ごとにしか変更されない場合、特定のマイナーがランダムシーケンスを手作業で最適化したバージョンを開発する時間ができてしまい、不当に有利になってしまいます。

サンプルコードはC++で書かれていますが、仕様書のコードを評価する際にはこれに注意してください。

すべての数値は符号なしの32ビット整数で計算されています。オーバーフローは次の計算に移る前に切り捨てられます。固定ビット長でない数値を使用する言語（PythonやJavaScriptなど）や符号付き整数のみを使用する言語（Javaなど）では、その言語の特徴を考慮する必要があります。 32ビットのデータ値を多用することは最新のGPUの内部データアーキテクチャと一致しています。

ProgPoWではデータのマージに32ビット版のFNV1aを使用しています。既存のEthashはマージにFNV1の同様の派生を使用していますが、FNV1aの方が優れた分散特性を持っています。

テストベクターはテストベクターファイルに収録されています。

const uint32_t FNV_PRIME = 0x1000193;
const uint32_t FNV_OFFSET_BASIS = 0x811c9dc5;

uint32_t fnv1a(uint32_t h, uint32_t d)
{
    return (h ^ d) * FNV_PRIME;
}

ProgPowでは乱数生成にKISS99を使用しています。これは、TestU01統計テストスイートを通過する最も単純な(最も命令の少ない)乱数生成器です。メルセンヌ・ツイスタのようなより複雑な乱数生成器は、特化ASICに効率的に実装することができ、効率化の機会を提供します。

テストベクターはテストベクターファイルに記載されています。

typedef struct {
    uint32_t z, w, jsr, jcong;
} kiss99_t;

// KISS99 is simple, fast, and passes the TestU01 suite
// https://en.wikipedia.org/wiki/KISS_(algorithm)
// http://www.cse.yorku.ca/~oz/marsaglia-rng.html
uint32_t kiss99(kiss99_t &st)
{
    st.z = 36969 * (st.z & 65535) + (st.z >> 16);
    st.w = 18000 * (st.w & 65535) + (st.w >> 16);
    uint32_t MWC = ((st.z << 16) + st.w);
    st.jsr ^= (st.jsr << 17);
    st.jsr ^= (st.jsr >> 13);
    st.jsr ^= (st.jsr << 5);
    st.jcong = 69069 * st.jcong + 1234567;
    return ((MWC^st.jcong) + st.jsr);
}

fill_mix関数はハッシュ計算で各レーンが使用する int32 値の配列を生成します。

テストベクターはテストベクターファイルにあります。

void fill_mix(
    uint64_t seed,
    uint32_t lane_id,
    uint32_t mix[PROGPOW_REGS]
)
{
    // Use FNV to expand the per-warp seed to per-lane
    // Use KISS to expand the per-lane seed to fill mix
    uint32_t fnv_hash = FNV_OFFSET_BASIS;
    kiss99_t st;
    st.z = fnv1a(fnv_hash, seed);
    st.w = fnv1a(fnv_hash, seed >> 32);
    st.jsr = fnv1a(fnv_hash, lane_id);
    st.jcong = fnv1a(fnv_hash, lane_id);
    for (int i = 0; i < PROGPOW_REGS; i++)
        mix[i] = kiss99(st);
}

Ethashと同様に、Keccakは一回ごとのシーケンスのシードと最終的な結果を出すのに使われます。 keccak-f800派生を使用しています。これは32ビットのワードサイズが最新のGPUのネイティブワードサイズと一致するためです。この実装はSHAKE派生で、幅=800・ビットレート=576・容量=224・出力=256・パディングなしです。 keccakの結果は256ビットのビッグエンディアンの数値として扱われます。つまり、結果バイト0は値の最上位ビットとなります。

Ethashと同様に、keccak関数の入力と出力は固定されており、比較的小さくなっています。つまり、『absorb』と『squeeze』のフェーズが1つだけ必要です。 keccak_f800_round 関数の疑似コード実装については、official Keccak specs の "Pseudo-code description of the permutations" セクションにある Round[b](A,RC) 関数を参照してください。

hash32_t keccak_f800_progpow(uint32_t* state)
{
    // keccak_f800 call for the single absorb pass
    for (int r = 0; r < 22; r++)
        keccak_f800_round(st, r);

    // Squeeze phase for fixed 8 words of output
    hash32_t ret;
    for (int i=0; i<8; i++)
        ret.uint32s[i] = st[i];

    return ret;
}

内側のループではFNVとKISS99を用いて，prog_seedからランダムなシーケンスを生成しています。このランダムなシーケンスによって、どのミックスステートにアクセスするかどのようなランダムな演算を行うかが決まります。

prog_seedは PROGPOW_PERIODごと（10ブロックまたは約2分）に一度だけ変化するので、マイニング中にその期間のシーケンスのソースコードが生成するためにprogPowLoopがCPUで評価されると予想されます。このソースコードはCPUでコンパイルされた後GPUで実行されます。 kernel.cuでは、シーケンスの例と生成されたソースコードを見ることができます。