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社の調査結果によると、新しい提案された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では、シーケンスの例と生成されたソースコードを見ることができます。

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

kiss99_t progPowInit(uint64_t prog_seed, int mix_seq_dst[PROGPOW_REGS], int mix_seq_src[PROGPOW_REGS])
{
    kiss99_t prog_rnd;
    prog_rnd.z = fnv1a(FNV_OFFSET_BASIS, prog_seed);
    prog_rnd.w = fnv1a(prog_rnd.z, prog_seed >> 32);
    prog_rnd.jsr = fnv1a(prog_rnd.w, prog_seed);
    prog_rnd.jcong = fnv1a(prog_rnd.jsr, prog_seed >> 32);
    // Create a random sequence of mix destinations for merge() and mix sources for cache reads
    // guarantees every destination merged once
    // guarantees no duplicate cache reads, which could be optimized away
    // Uses Fisher-Yates shuffle
    for (int i = 0; i < PROGPOW_REGS; i++)
    {
        mix_seq_dst[i] = i;
        mix_seq_src[i] = i;
    }
    for (int i = PROGPOW_REGS - 1; i > 0; i--)
    {
        int j;
        j = kiss99(prog_rnd) % (i + 1);
        swap(mix_seq_dst[i], mix_seq_dst[j]);
        j = kiss99(prog_rnd) % (i + 1);
        swap(mix_seq_src[i], mix_seq_src[j]);
    }
    return prog_rnd;
}
```

混合データに値をマージする演算は、エントロピーを維持するために選ばれたものです。

テストベクターは、[テストベクターファイル](https://github.com/ifdefelse/ProgPOW/blob/master/test-vectors.md#math)に記載されています。

```cpp
// Merge new data from b into the value in a
// Assuming A has high entropy only do ops that retain entropy
// even if B is low entropy
// (IE don't do A&B)
uint32_t merge(uint32_t a, uint32_t b, uint32_t r)
{
    switch (r % 4)
    {
    case 0: return (a * 33) + b;
    case 1: return (a ^ b) * 33;
    // prevent rotate by 0 which is a NOP
    case 2: return ROTL32(a, ((r >> 16) % 31) + 1) ^ b;
    case 3: return ROTR32(a, ((r >> 16) % 31) + 1) ^ b;
    }
}
```

ランダム演算には汎用GPUの2大プログラミング言語であるCUDAとOpenCLで実装しやすい演算が選ばれています．[mul_hi](https://www.khronos.org/registry/OpenCL/sdk/1.1/docs/man/xhtml/mul_hi.html)、[min](https://www.khronos.org/registry/OpenCL/sdk/2.0/docs/man/xhtml/integerMax.html)、[clz](https://www.khronos.org/registry/OpenCL/sdk/1.1/docs/man/xhtml/clz.html)、[popcount](https://www.khronos.org/registry/OpenCL/sdk/2.0/docs/man/xhtml/popcount.html)の各関数は対応するOpenCLの関数と適合しています。 ROTL32 は、OpenCL の [rotate](https://www.khronos.org/registry/OpenCL/sdk/1.0/docs/man/xhtml/rotate.html) 関数と適合します。 ROTR32 は右ローテートで、これは `rotate(i, 32-v)` と同じです。

テストベクターは[テストベクターファイル](https://github.com/ifdefelse/ProgPOW/blob/master/test-vectors.md#math)にあります。

```cpp
// Random math between two input values
uint32_t math(uint32_t a, uint32_t b, uint32_t r)
{
    switch (r % 11)
    {
    case 0: return a + b;
    case 1: return a * b;
    case 2: return mul_hi(a, b);
    case 3: return min(a, b);
    case 4: return ROTL32(a, b);
    case 5: return ROTR32(a, b);
    case 6: return a & b;
    case 7: return a | b;
    case 8: return a ^ b;
    case 9: return clz(a) + clz(b);
    case 10: return popcount(a) + popcount(b);
    }
}
```


内側のループの流れは

* レーン `(loop % LANES)` がそのループのイテレーションのリーダーとして選ばれます。
* リーダーの`mix[0]`に対する256バイトDAGエントリ数を法とする剰余がDAG全体からどこを読み出すか選択するために使われます。
* 各レーンはエントリ内の開始オフセットとして `(lane ^ loop) % LANES` を使用して`DAG_LOADS` 個のワードを連続して読み込みます。
* 演算とキャッシュアクセスのランダムなシーケンスが実行されます。
* ループの開始時に読み込まれたDAGデータは、ループの終了時にマージされます。

`prog_seed` と `loop` は外側のループから来ており、現在のプログラムシード（block_number/PROGPOW_PERIOD）とループのイテレーション番号に対応しています。`mix` は `fill_mix` によって最初に埋められた状態の配列です。`dag`はリトルエンディアン形式の32bit符号なし整数にグループ化されたEthash DAGのバイト数です。 リトルエンディアンのアーキテクチャではこれは既存のDAGへの通常のint32ポインタになります。

`DAG_BYTES`には現在のDAGのバイト数が設定され、既存のEthashアルゴリズムと同様に生成されます。 

テストベクターは[テストベクターファイル](https://github.com/ifdefelse/ProgPOW/blob/master/test-vectors.md#progPowLoop)にあります。

```cpp
void progPowLoop(
    const uint64_t prog_seed,
    const uint32_t loop,
    uint32_t mix[PROGPOW_LANES][PROGPOW_REGS],
    const uint32_t *dag)
{
    // dag_entry holds the 256 bytes of data loaded from the DAG
    uint32_t dag_entry[PROGPOW_LANES][PROGPOW_DAG_LOADS];
    // On each loop iteration rotate which lane is the source of the DAG address.
    // The source lane's mix[0] value is used to ensure the last loop's DAG data feeds into this loop's address.
    // dag_addr_base is which 256-byte entry within the DAG will be accessed
    uint32_t dag_addr_base = mix[loop%PROGPOW_LANES][0] %
        (DAG_BYTES / (PROGPOW_LANES*PROGPOW_DAG_LOADS*sizeof(uint32_t)));
    for (int l = 0; l < PROGPOW_LANES; l++)
    {
        // Lanes access DAG_LOADS sequential words from the dag entry
        // Shuffle which portion of the entry each lane accesses each iteration by XORing lane and loop.
        // This prevents multi-chip ASICs from each storing just a portion of the DAG
        size_t dag_addr_lane = dag_addr_base * PROGPOW_LANES + (l ^ loop) % PROGPOW_LANES;
        for (int i = 0; i < PROGPOW_DAG_LOADS; i++)
            dag_entry[l][i] = dag[dag_addr_lane * PROGPOW_DAG_LOADS + i];
    }

    // Initialize the program seed and sequences
    // When mining these are evaluated on the CPU and compiled away
    int mix_seq_dst[PROGPOW_REGS];
    int mix_seq_src[PROGPOW_REGS];
    int mix_seq_dst_cnt = 0;
    int mix_seq_src_cnt = 0;
    kiss99_t prog_rnd = progPowInit(prog_seed, mix_seq_dst, mix_seq_src);

    int max_i = max(PROGPOW_CNT_CACHE, PROGPOW_CNT_MATH);
    for (int i = 0; i < max_i; i++)
    {
        if (i < PROGPOW_CNT_CACHE)
        {
            // Cached memory access
            // lanes access random 32-bit locations within the first portion of the DAG
            int src = mix_seq_src[(mix_seq_src_cnt++)%PROGPOW_REGS];
            int dst = mix_seq_dst[(mix_seq_dst_cnt++)%PROGPOW_REGS];
            int sel = kiss99(prog_rnd);
            for (int l = 0; l < PROGPOW_LANES; l++)
            {
                uint32_t offset = mix[l][src] % (PROGPOW_CACHE_BYTES/sizeof(uint32_t));
                mix[l][dst] = merge(mix[l][dst], dag[offset], sel);
            }
        }
        if (i < PROGPOW_CNT_MATH)
        {
            // Random Math
            // Generate 2 unique sources 
            int src_rnd = kiss99(prog_rnd) % (PROGPOW_REGS * (PROGPOW_REGS-1));
            int src1 = src_rnd % PROGPOW_REGS; // 0 <= src1 < PROGPOW_REGS
            int src2 = src_rnd / PROGPOW_REGS; // 0 <= src2 < PROGPOW_REGS - 1
            if (src2 >= src1) ++src2; // src2 is now any reg other than src1
            int sel1 = kiss99(prog_rnd);
            int dst  = mix_seq_dst[(mix_seq_dst_cnt++)%PROGPOW_REGS];
            int sel2 = kiss99(prog_rnd);
            for (int l = 0; l < PROGPOW_LANES; l++)
            {
                uint32_t data = math(mix[l][src1], mix[l][src2], sel1);
                mix[l][dst] = merge(mix[l][dst], data, sel2);
            }
        }
    }
    // Consume the global load data at the very end of the loop to allow full latency hiding
    // Always merge into mix[0] to feed the offset calculation
    for (int i = 0; i < PROGPOW_DAG_LOADS; i++)
    {
        int dst = (i==0) ? 0 : mix_seq_dst[(mix_seq_dst_cnt++)%PROGPOW_REGS];
        int sel = kiss99(prog_rnd);
        for (int l = 0; l < PROGPOW_LANES; l++)
            mix[l][dst] = merge(mix[l][dst], dag_entry[l][i], sel);
    }
}
```

全体のアルゴリズムの流れは

* ヘッダのkeccakハッシュ＋nonceでkeccak_f800から256ビットのダイジェストを作成（パディングはethashカスタムと一致）
* ダイジェストの最初の2ワードをシードとして初期の混合データを生成
* 複数回ループし、その都度ランダムな負荷とランダムな計算を混合データにハッシュ化
* すべての混合データを単一の 256 ビットの値にハッシュ化
* 初期データから引き継いだダイジェスト＋mix_dataの最終256ビット値（パディングはethashカスタムと一致）を用いて最終的なkeccakハッシュを生成
* マイニング時にこの最終値を `hash32_t` ターゲットと比較

```cpp
hash32_t progPowHash(
    const uint64_t prog_seed,    // value is (block_number/PROGPOW_PERIOD)
    const uint64_t nonce,
    const hash32_t header,
    const uint32_t *dag          // gigabyte DAG located in framebuffer - the first portion gets cached
)
{
    hash32_t hash_init;
    hash32_t hash_final;

    uint32_t mix[PROGPOW_LANES][PROGPOW_REGS];

    /*  
        ========================================
        Absorb phase for initial keccak pass
        ========================================
    */

    {
        uint32_t state[25] = {0x0};
        // 1st fill with header data (8 words)
        for (int i = 0; i < 8; i++)
            state[i] = header.uint32s[i];

        // 2nd fill with nonce (2 words)
        state[8] = nonce;
        state[9] = nonce >> 32;

        // 3rd apply padding
        state[10] = 0x00000001;
        state[18] = 0x80008081;

        // keccak(header..nonce)
        hash_init = keccak_f800_progpow(state);

        // get the seed to initialize mix
        seed = ((uint64_t)hash_init.uint32s[1] << 32) | hash_init.uint32s[0]);
	}

    // initialize mix for all lanes
    for (int l = 0; l < PROGPOW_LANES; l++)
        fill_mix(seed, l, mix[l]);

    // execute the randomly generated inner loop
    for (int i = 0; i < PROGPOW_CNT_DAG; i++)
        progPowLoop(prog_seed, i, mix, dag);

    // Reduce mix data to a per-lane 32-bit digest
    uint32_t digest_lane[PROGPOW_LANES];
    for (int l = 0; l < PROGPOW_LANES; l++)
    {
        digest_lane[l] = FNV_OFFSET_BASIS;
        for (int i = 0; i < PROGPOW_REGS; i++)
            digest_lane[l] = fnv1a(digest_lane[l], mix[l][i]);
    }

    // Reduce all lanes to a single 256-bit digest
    for (int i = 0; i < 8; i++)
        digest.uint32s[i] = FNV_OFFSET_BASIS;
    for (int l = 0; l < PROGPOW_LANES; l++)
        digest.uint32s[l%8] = fnv1a(digest.uint32s[l%8], digest_lane[l]);

    /*  
        ========================================
        Absorb phase for final keccak pass
        ========================================
    */

    {
        uint32_t state[25] = {0x0};

        // 1st fill with hash_init (8 words)
        for (int i = 0; i < 8; i++)
            state[i] = hash_init.uint32s[i];

        // 2nd fill with digest from main loop
        for (int i = 8; i < 16; i++)
            state[i] = digest.uint32s[i - 8];

        // 3rd apply padding
        state[17] = 0x00000001;
        state[24] = 0x80008081;

        // keccak(header..nonce)
        hash_final = keccak_f800_progpow(state);
	}

    // Compare hash final to target
    [...]

}
```

## 例とテストケース

ProgPoW 0.9.4の場合。

ブロック 30,000（prog_seed 3,000）に対して生成された乱数列は、[kernel.cu](https://github.com/ifdefelse/ProgPOW/blob/master/test/kernel.cu)で確認できます。

ブロック30,000に対してアルゴリズムを実行すると、以下のようなダイジェストと結果が得られます。

```
Header     : 0xffeeddccbbaa9988776655443322110000112233445566778899aabbccddeeff
Nonce      : 0x123456789abcdef0
Hash init  : 0xee304846ddd0a47b98179e96b60ec5ceeae2727834367e593de780e3e6d1892f
Mix seed   : 0x7ba4d0dd464830ee
Mix hash   : 0x493c13e9807440571511b561132834bbd558dddaa3b70c09515080a6a1aff6d0
Hash final : 0x46b72b75f238bea3fcfd227e0027dc173dceaa1fb71744bd3d5e030ed2fed053
```

その他のテストベクターは[テストベクターファイル](https://github.com/ifdefelse/ProgPOW/blob/master/test-vectors.md#progPowHash)にあります。

##変更履歴

- 0.9.4 (最新) - [bypass memory hardness](https://github.com/ifdefelse/ProgPOW/issues/51)の脆弱性を修正しました。
- [0.9.3](https://github.com/ifdefelse/ProgPOW/tree/spec-0.9.3) - PERIOD, CNT_MATH, CNT_CACHE のパラメータを削減しました。詳細は [this medium post](https://medium.com/@ifdefelse/progpow-progress-da5bb31a651b) を参照してください。
- [0.9.2](https://github.com/ifdefelse/ProgPOW/tree/spec-0.9.2) - math() のソースを一意にし、merge() の 0 による回転を防止します。 [SChernykh](https://github.com/ifdefelse/ProgPOW/issues/19)提案。
- [0.9.1](https://github.com/ifdefelse/ProgPOW/tree/spec-0.9.1) - 各レーンがアクセスするDAGエントリのどの部分かをシャッフルします。[mbevand](https://github.com/ifdefelse/ProgPOW/pull/13)提案。
- [0.9.0](https://github.com/ifdefelse/ProgPOW/tree/spec-0.9.0) - ユニークなキャッシュアドレスソース、パラメータを再調整しました。
- [0.8.0](https://github.com/ifdefelse/ProgPOW/tree/spec-0.8.0) - オリジナルの仕様です。

## ライセンス
ProgPoWアルゴリズムと本仕様書は新しい作品です。 著作権および関連する権利は[CC0](https://creativecommons.org/publicdomain/zero/1.0/)によって放棄されています。

このリポジトリのリファレンスProgPoWマイニング実装はethminerの派生物でありGPLです。