RandomX

RandomXは仮想通貨Moneroで2021/5/5現在使われているプログラマティックプルーフ・オブ・ワーク(Programmatic Proof-of-Work, ProgPoW)のアルゴリズムです。

RandomXの開発者tevador氏によるRandomXの設計と分析に関する『RandomX design』を翻訳してみました。RandomXの詳細な仕様書はこちらになります。

ProgPoWは、ASICマイナーのようなマイニング特化ハードウェアの効率性を減少させ、標準的なCPUでも劣らない処理効率になるように設計された、ブロックチェイン合意プロトコルアルゴリズムです。RandomXでは、Javaの仮想マシンとは異なり、x86_64やArmv8などの一般的なレジスタベースのCPUに似た独自設計のCPUの仮想マシン上でコードを実行させることでProgPoWを実装しています。

ブロックチェーンのプルーフ・オブ・ワークという特定の処理領域なのに、ビットコインに対するSHA256 ASICマイナーのような特化したハードウェアを作りにくくしたという意味で、RandomXは領域特化アーキテクチャ(Domain Specific Architectures, DSA)の視点から面白いアプローチではないかと思います。

この翻訳はDeepLの翻訳結果を下訳にしています。

RandomXの設計を読む上での参考資料

ブロックチェーンとProof of Work(PoW)
イーサリアムでのProgPoWの提案の解説
ProgPoWアルゴリズム文書の翻訳 (2021/5/12追記)
RandomXのCPU/GPUベンチマーク
Computer Architecture第６版のDomain Specific Architecturesのまとめ
Avalanche effect (入力のわずかな変化に対して出力が大きく変化する性質を示すAvalancheはどう訳すべき?とりあえずアバランシェと表記) (2021/5/7追記)
中間一致攻撃時間と空間のトレードオフを利用した攻撃

RandomXの設計

特化ハードウェアの性能上の優位性を最小限に抑えるために、プルーフ・オブ・ワーク（PoW）アルゴリズムは、既存の汎用ハードウェアの特定の機能をターゲットにすることで、『デバイスバインディング(device binding)』を実現しなければなりません。これは、異なるメーカーの異なるアーキテクチャからなる大規模なクラスのデバイスを対象としなければならないため、複雑な作業となります。

一般的な処理装置には、CPU（Central Processing Unit）とGPU（Graphics Processing Unit）という2つの異なるクラスがあります。RandomXがCPUをターゲットにしているのは次のような理由からです。

CPUは特化型のデバイスではないため、広く普及し広く利用されています。CPUを対象としたアルゴリズムは、より平等性が高く、より多くの参加者がネットワークに参加することができます。これはオリジナルのCryptoNoteホワイトペーパー[1]に記載されている目標の1つです。
異なるCPUアーキテクチャ間にはネイティブハードウェア命令の大きな共通サブセットが存在します。しかし、GPUの場合はそうはいきません。例えば、NVIDIAとAMDのGPUには共通の整数乗算命令はありません[2]。
主要なCPUの命令セットはすべてよく文書化されており、複数のオープンソース・コンパイラが提供されています。それに対して、GPUの命令セットは通常プロプライエタリであり、最大の性能を得るためにはベンダー固有のクローズドソースのドライバが必要となる場合があります。

1. 設計上の考慮点

CPU拘束(CPU-bound)のプルーフ・オブ・ワークの最も基本的な考え方は、『作業』が『動的』でなければならないということです。これは、CPUが2種類の入力、『データ』（メイン入力）と『コード』（データに対して何を実行するかを指定)を受け付けるという事実を利用しています。

逆に、典型的な暗号ハッシュ関数[3]は、入力が『データ』のみで、演算の順序が固定されており、専用の集積回路でより効率的に実行できるため、CPUに適した仕事ではありません。

1.1 動的プルーフ・オブ・ワーク

動的プルーフ・オブ・ワークのアルゴリズムは、一般的に以下の4つのステップで構成されます。

1) ランダムなプログラムを生成
2) CPUのネイティブマシンコードに変換
3) プログラムを実行
4) プログラムの出力を暗号的に安全な値に変換

実際の「有用な」CPU拘束作業はステップ3で実行されるため、残りのステップのオーバーヘッドを最小限に抑えるようにアルゴリズムを調整する必要があります。

1.1.1 ランダムなプログラムの生成

動的プルーフ・オブ・ワークの設計の初期の試みは、CやJavascriptなどの高レベル言語でプログラムを生成することに基づいていました[4, 5]。しかしこれは主に2つの理由から非常に非効率的です。

高級言語は複雑な構文を持っているため、有効なプログラムの生成には抽象構文木（Abstract Syntax Tree, AST）を作成する必要があり、比較的時間がかかります。
プログラムのソースコードが生成されるとコンパイラは通常テキスト表現を解析してASTに戻すため、ソースコード生成のプロセス全体が冗長になります。

ランダムなプログラムを生成する最も早い方法は、『論理なし』の生成器を使用することであり、単にバッファをランダムなデータで満たすことです。これにはもちろんすべてのランダムなビット文字列が有効なプログラムを表すような構文のないプログラミング言語（または命令セット）を設計する必要があります。

1.1.2 プログラムの機械語への変換

アルゴリズムを特定のCPUアーキテクチャに限定したくないため、このステップは必然的に行われます。機械語をできるだけ高速に生成するために、命令セットをできるだけネイティブなハードウェアに近づけつつ、異なるアーキテクチャに対応できる汎用性を持たせる必要があります。コードのコンパイル時に高度な最適化を行うための十分な時間はありません。

1.1.3 プログラムの実行

実際のプログラム実行では、可能な限り多くのCPUコンポーネントを利用する必要があります。プログラムで利用すべき機能には次のようなものがあります。

複数レベルのキャッシュ (L1, L2, L3)
μopキャッシュ [6]
算術論理演算装置（ALU)
浮動小数点演算装置(FPU)
メモリコントローラ
命令レベルの並列性 [7]
- スーパースカラ実行 [8]
- アウトオブオーダ実行 [9]
- 投機的実行 [10]
- レジスタリネーミング [11]

第2章では、RandomX VMがこれらの機能をどのように活用しているかを説明します。

1.1.4 最終結果の計算

Blake2b [12] は暗号的に安全なハッシュ関数で、ソフトウェアで高速に動作するように特別に設計されており、特に最近の64ビット・プロセッサでは、SHA-3の約3倍の速度、入力1バイトあたり約3クロック・サイクルの速度で実行できます。この関数はCPUフレンドリーなプルーフ・オブ・ワークで使用するのに理想的な候補です。

より大量のデータを暗号的に安全に処理するのにAdvanced Encryption Standard (AES) [13]が最速の処理速度を提供できます。最近の多くのCPUがこれらの演算のハードウェアアクセラレーションに対応しているためです。RandomXでのAESの使用については、第3章を参照してください。

1.2 『やさしいプログラム問題』

ランダムなプログラムが生成されたときに、有利なときだけ実行するという選択をすることがあります。この戦略が成り立つのには、主に2つの理由があります。

ランダムに生成されたプログラムの実行時間は、通常、対数正規分布[14]に従います。(付録Cも参照)。生成されたプログラムを素早く分析し、平均以上の実行時間になりそうな場合はプログラムの実行をスキップして、代わりに新しいプログラムを生成することができます。これにより、実行時間が裾の重い分布(heavy tail, 長時間実行される外れ値が多数)の場合や、プログラムの生成が安価な場合には、特に性能が大幅に向上します。
プログラムの実行に必要な機能のうち、一部の機能を最適化するように実装することができます。例えば、一部の演算（除算など）のサポートをやめたり、一部の命令列をより効率的に実装したりすることができます。生成されたプログラムは、解析され、最適化された実装の特定の要件に一致する場合にのみ実行されることになります。

このような、特定の性質を持つプログラムを探す戦略は、今回のプルーフ・オブ・ワークの目的から外れているため、排除しなければなりません。これは、『N』個のランダムなプログラムを連続して実行させ、各プログラムが前のプログラムの出力から生成されるようにすることで実現できます。そして、最後のプログラムの出力が結果として使われます。

     +---------------+ +---------------+     +---------------+ +---------------+
     |               | |               |     |               | |               |
入力→ |プログラム1     |→|プログラム2      |→...→｜プログラム(N-1) |→｜プログラムN     |→結果
     |               | |               |     |               | |               |
     +---------------+ +---------------+     +---------------+ +---------------+

原理的には、最初のプログラムが実行された後、採掘者はチェーン全体（好ましくないプログラムを含む可能性がある）を終わらせることを約束するか、あるいはやり直して未完成のチェーンに費やした労力を無駄にしなければならないということです。これが異なるマイニング戦略のハッシュレートにどのような影響を与えるかの例は、付録Aに記載されています。

また、このようにプログラムを連鎖的に実行することで、同一の分布を持つランタイムの合計の相対的な偏差が減少するため、チェーン全体のランタイムが均等になるという利点があります。

1.3 検証時間

プルーフ・オブ・ワークの目的は、信頼性の高いピア・ツー・ピア・ネットワークで使用されることであるため、ネットワーク参加者は、プルーフが有効であるかどうかを迅速に検証できなければなりません。これにより、プルーフ・オブ・ワーク・アルゴリズムの複雑さに上限が設定されます。特に、RandomXの目標は、置き換えを目指しているCryptoNightハッシュ関数[15]と少なくとも同等の検証速度に設定しています。

1.4 メモリ困難性(Memory-hardness)

ALU や FPU などの純粋な計算資源に加え、CPU は通常DRAM という大容量のメモリを利用します [16]。メモリサブシステムの性能は、通常、計算能力に合わせて調整されており、例えば[17]のようになっています。

組込みや低消費電力のCPU用のシングルチャネルメモリ
デスクトップCPU用のデュアルチャネルメモリ
ワークステーションCPU用のトリプルまたはクアッドチャネルメモリ
ハイエンドサーバーCPU用の6チャンネルまたは8チャンネルメモリ

外部メモリとオンチップ・メモリ・コントローラを利用するために、プルーフ・オブ・ワークアルゴリズムは、大きなメモリ・バッファ（『データセット』と呼ばれる）にアクセスする必要があります。データセットは以下の条件を満たす必要があります。

オンチップに格納できるものより大容量（外部メモリが必要)
動的（書き込み可能なメモリが必要）

1つのチップに搭載できるSRAMの最大量は、16nmプロセスでは512MiB以上、7nmプロセスでは2GiB以上です[18]。理想的には、データセットのサイズは少なくとも4GiBでなければなりません。しかし、検証時間に制約があるため（後述），RandomX で使用するサイズを 2080 MiB としました。現在の技術（2019年には7nm）を用いれば、理論的にはこの量のSRAMで1つのチップを作ることができますが、少なくとも近い将来では、このようなソリューションの実現性には疑問が残ります。

1.4.1 軽量クライアントでの検証

プルーフ・オブ・ワークを解く専用のマイニングシステムに2GiB以上を要求するのは合理的ですが、軽量クライアントにはもっと少ないメモリ量で証明を検証するオプションを提供しなければなりません。

『高速』モードと『軽量』モードに必要なメモリの比率は、軽量モードがマイニングに適したものにならないよう、慎重に選択する必要があります。特に、軽量モードの空間時間（area-time, AT）積は、高速モードのAT積よりも小さくしてはいけません。AT積の削減はトレードオフ攻撃を測定する一般的な方法です[19]。

前の章で述べた制約を考慮して、高速検証モードと軽量検証モードの間で可能な最大の性能比は経験的に8と決定しました。これは以下の理由によるものです。

軽量検証時間をこれ以上長くすると、1.3章で述べた制約に違反
高速モードの実行時間をこれ以上短縮すると、1.1章の制約に抵触し、特にプログラム生成と結果算出のオーバーヘッド時間が大きくなりすぎる

また、軽量クライアントモードで必要となる最大メモリ量として256MiBを選択しました。これはRaspberry Piのような小型のシングルボードコンピュータでも許容できる量です。

メモリ時間積を一定に保つために、高速モードの最大必要メモリ量は

8 * 256 MiB = 2048 MiB

軽量モードでは、SuperscalarHash関数のために追加のチップ領域が必要になるため、この値はさらに大きくなります（仕様書の3.4章および6章を参照）。SuperscalarHashコアあたり0.2mm²、DRAM密度0.149Gb/mm² [20]と保守的に見積もっても、追加メモリは以下の通りです。

8 * 0.2 * 0.149 * 1024 / 8 = 30.5 MiB

高速モードで必要なメモリの合計は、ほぼ一定のAT積で2080MiBになります。

2. 仮想マシンのアーキテクチャ

本節では、RandomX の仮想マシン (virtual machine, VM) の設計について説明します。

2.1 命令セット

RandomX は1 命令あたり 8 バイトの固定長命令エンコーディングを採用しています。これにより命令語の中に32ビットの即値を含めることができます。また、命令語のビットの解釈は、8バイトのワードであればどのような命令でも有効となるようにしています。これにより非常に効率的にランダムプログラムを生成することができます（1.1.1章参照）。

2.1.1 命令の複雑性

VMはレジスタアドレスとメモリアドレスの両方のオペランドを使用できる複合命令セットマシンです。しかし、RandomXの各命令はわずか1～7個のx86命令（平均1.8個）にしか変換されません。命令セットをカスタマイズした特化ハードウェアの効率的な利点を最小限にするためには、命令の複雑さを比較的低く抑えることが重要となります。

2.2 プログラム

VM が実行するプログラムは，256 個のランダムな命令からなるループの形をしています．

256命令という長さは、プログラムの種類が多く、分岐のためのスペースも十分に確保できます。生成可能なプログラムの数は、ランダム・ジェネレータのシード値の可能数である2⁵¹² = 1.3e+154に制限されます。
256命令は高性能なCPUがDRAMからデータを取得するのと同じ時間で1つの反復を実行できるほど十分に短いものです。これはデータセットへのアクセスを同期させ完全にプリフェッチできるという点で有利です（2.9章参照）。
このプログラムはループなので、一部のx86 CPUに搭載されているμopキャッシュ[6]を利用することができます。μopキャッシュからループを実行することで、CPUはx86の命令デコーダをパワーダウンさせることができ、x86と単純な命令デコーダを持つアーキテクチャとの電力効率を同等にすることができます。

2.3 レジスタ

VMでは8本の整数レジスタと12本の浮動小数点レジスタを使用しています。これは、一般的な64ビットCPUアーキテクチャの中でアーキテクチャレジスタの数が最も少ないx86-64において、物理レジスタとして割り当てられる最大値です。これ以上のレジスタを使用すると、VMレジスタの内容を格納するためにメモリを使用しなければならないため、x86 CPUは不利になります。

2.4 整数演算

RandomX では高い出力エントロピーを持つ次のすべての整数演算を使用します。加算(IADD_RS, IADD_M)、減算(ISUB_R, ISUB_M, INEG_R)、乗算(IMUL_R, IMUL_M, IMULH_R, IMULH_M, ISMULH_R, ISMULH_M, IMUL_RCP)、排他的論理和(IXOR_R, IXOR_M)、ローテーション(IROR_R, IROL_R)です。

2.4.1 IADD_RS

IADD_RS命令はCPUのアドレス計算ロジックを利用しており、ほとんどのCPUで1つのハードウェア命令で実行することができます（x86のlea、armのadd）。

2.4.2 IMUL_RCP

整数の除算はCPUでは完全にパイプライン化されておらずASICでは高速化できるため、IMUL_RCP命令では逆数を計算するためにプログラムごとに除算を１回だけ必要とします。これによりASICはプログラム実行時の性能面での優位性を得ることなくハードウェアの除算器を搭載せざるを得なくなります。

2.4.3 IROR_R/IROL_R

ローテーション命令は右ローテートと左ローテートに4:1の割合で分かれています。右ローテートの方が頻度が高いのは、ARMのように左ローテートをネイティブにサポートしていないアーキテクチャがあるからです（右ローテートを使ってエミュレートする必要があります）。

2.4.4 ISWAP_R

2.4.4 ISWAP_R 命令はレジスタリネーム/ムーブエリミネーション(Move Elimination)に対応している CPU で効率的に実行できます。

2.5 浮動小数点演算

RandomX は倍精度浮動小数点演算を使用します。倍精度浮動小数点演算は大半の CPU でサポートされており、単精度浮動小数点演算よりも複雑なハードウェアを必要とします。すべての演算は 128 ビットのベクトル演算で行われ、主要な CPU アーキテクチャでサポートされています。

RandomXは、IEEE 754規格で正しく丸められることが保証されている5つの演算（加算、減算、乗算、除算、平方根）を使用します。また、規格で定められた4つの丸めモードがすべて使用されます。

2.5.1 浮動小数点レジスタ群

浮動小数点演算の領域は、レジスタ・グループFを使用する「加算」演算と、レジスタ・グループEを使用する「乗算」演算に分けられます。Fグループのレジスタの範囲は約±3.0e+14に限られているため、絶対値が1より大きい浮動小数点数の加減算は、常に少なくとも5つの小数部ビットを変化させることになります。

Fグループ・レジスタの範囲が限られているため、より効率的な固定小数点表現（80ビットの数値）を使用することができますが、FSCAL命令が浮動小数点フォーマットのバイナリ表現を操作してこの最適化をより困難にします。

グループEレジスタは正の値に制限されているため、NaNの結果（負の数の平方根や0 * ∞など）を避けることができます。割り算はメモリソースオペランドのみを使用し、定数逆数による乗算に最適化されるのを防ぎます。グループEのメモリ・オペランドの指数は、0による除算や乗算を避け、得られる数値の範囲を広げるために、-255から0の間の値に設定されます。グループEのレジスタ値の取り得るの範囲の目安は、1.7E-77～無限大になります。

各プログラムループ終了時の浮動小数点レジスタ値のおおよその分布を以下の図に示します（左：グループF、右：グループE）。

(注：階級は区間の左側の値でマークされています。例えば、1e-40とマークされた階級には1e-40から1e-20までの値が含まれています。)

1e+14にあるFレジスタの値の数が少ないのは、FSCAL命令によってレジスタの値の範囲が大幅に広がったためです。

グループEのレジスタは非常に大きな値の範囲をカバーしています。約2%のプログラムが少なくとも1つのinfinity値を生成します。

エントロピーを最大化し64バイトのキャッシュラインに収めるために、浮動小数点レジスタはスクラッチパッドに格納される前に、各イテレーションの終わりにXOR演算を用いて結合されます。

2.6 分岐

現代の CPU は分岐を処理するために多くのダイエリアとエネルギーを費やしています。これには以下が含まれます。

分岐予測ユニット [21]
分岐予測が外れた場合にCPUが回復するためのチェックポイント/ロールバックステート

投機的なデザインを活用するためにランダムプログラムには分岐が含まれている必要があります。しかし、分岐予測が失敗すると投機的に実行された命令が捨てられてしまうため、予測ミスのたびに一定のエネルギーが浪費されてしまいます。そのため、予測ミスの数を最小限に抑えることを目指します。

さらに、コード内の分岐は静的な最適化の量を大幅に減らすために必要不可欠です。例えば、次のようなx86の命令列を考えてみましょう。

    ...
branch_target_00:
    ...
    xor r8, r9
    test r10, 2088960
    je branch_target_00
    xor r8, r9
    ...

XOR演算は通常は相殺されますが、分岐した場合は結果が異なるため、分岐による最適化を取り除くことはできません。同様に、ISWAP_R命令も、分岐がなければ常に静的に最適化されてしまう可能性があります。

一般的にはランダムな分岐は以下のように設計しなければなりません。

無限ループは不可能
予測違いの分岐の数が少ない
分岐条件がランタイム値に依存し静的な分岐最適化が無効となるようにする

2.6.1 分岐予測

残念ながらRandomXで分岐予測を利用する方法は見つかっていません。RandomXは合意プロトコルなので、すべてのルールを事前に設定する必要があり、その中には分岐のルールも含まれています。完全に予測可能な分岐は、VMレジスタのランタイム値に依存することができないため（レジスタ値は疑似ランダムで予測できないため）、静的なものでなければならず、そのため特殊なハードウェアによって容易に最適化することができます。

2.6.2 CBRANCH命令

RandomXでは、ジャンプ確率が1/256、分岐条件が整数のレジスタ値に依存するランダム分岐を使用します。これらの分岐はCPUによって『分岐しない』と予測されます。このような分岐はほとんどのCPU設計では分岐しない限り『自由』です。これは分岐予測機能を利用したものではありませんが、投機的な設計では非投機的な分岐処理に比べて大幅に性能が向上します（詳細は付録Bを参照）。

分岐条件とジャンプ先はRandomXコードの無限ループが発生しないように選択されています。これは分岐を制御するレジスタが、繰り返されるコードブロック内で変更されることがないためです。各CBRANCH命令は最大で2回連続してジャンプすることができます。分岐予測 [22]を使用して CBRANCH を処理することは、ほとんどの場合分岐が行われないため実用的ではありません。

2.7 命令レベルの並列性

CPU は実行コードの命令レベルの並列性を利用して性能を向上させています。これらの技術には以下のようなものがあります。

並列実行可能な複数の演算装置を持つ（スーパースカラ実行)
プログラム順ではなくオペランドが利用可能な順に命令を実行（アウトオブオーダー実行）
スーパースカラ実行とアウトオブオーダー実行の両方の利点を活かすために分岐の方向を予測

RandomXはこれらの最適化の恩恵を受けています。詳細な分析は付録Bを参照してください。

2.8 スクラッチパッド

スクラッチパッドは読み書き可能なメモリとして使用されます。スクラッチパッドは読み書き可能なメモリとして使用され、そのサイズは CPU キャッシュに完全に収まるように選択されています。

2.8.1 スクラッチパッドのレベル

スクラッチパッドは典型的なCPUキャッシュ階層を模して3つのレベルに分割されています[23]。ほとんどのVM命令は「L1」と「L2」のスクラッチパッドにアクセスします。これは、L1とL2のCPUキャッシュがCPU実行ユニットの近くにあり、ランダムアクセスのレイテンシーが最も優れているためです。L1とL2からの読み出しの比率は3:1で、一般的なレイテンシーの逆の比率と一致します（下表参照）。

CPU マイクロアーキテクチャー	L1レイテンシー	L2レイテンシー	L3レイテンシー	ソース
ARM Cortex A55	2	6	-	[24]
AMD Zen+	4	12	40	[25]
Intel Skylake	4	12	42	[26]

L3キャッシュはより大きくCPUコアから離れた位置にあります。そのため、アクセスレイテンシーが非常に高く、プログラムの実行が滞る原因となります。

そのため、RandomXはプログラムのイテレーションごとに「L3」スクラッチパッドへのランダムアクセスを2回のみ実行します（仕様書の4.6.2章のステップ2および3）。ある反復時のレジスタ値は、ロードされたときと同じ場所に書き込まれます。これにより必要なキャッシュラインがより高速なL1またはL2キャッシュに移動したことが保証されます。

さらに、固定アドレスから読み出す整数命令では、「L3」スクラッチパッド全体が使用されます（仕様書の表5.1.4）。これは、繰り返しアクセスすることで、そのキャッシュラインがCPUのL1キャッシュに確実に配置されるためです。このようにスクラッチパッドのレベルは必ずしも同じCPUのキャッシュレベルに直接対応していないことがわかります。

2.8.2 スクラッチパッドの書き込み

VM の実行中にスクラッチパッドが変更される方法は 2 つあります。

各プログラムの反復の終わりにすべてのレジスタ値が「L3」スクラッチパッドに書き込まれます（仕様書の4.6.2章、ステップ9および11を参照）。これにより2つの64バイトのブロックに分けて1回の反復で合計128バイトが書き込まれます。
ISTORE命令は明示的なストアを行います。1つのプログラムには平均して16個のストアがあり、そのうち2個は「L3」レベルへのストアです。ISTORE命令は1回につき8バイトの書き込みを行います。

下の図はスクラッチパッドへの書き込みの分布の例です。画像の各ピクセルはスクラッチパッドの8バイトを表しています。赤いピクセルはハッシュ計算中に少なくとも一度は上書きされたスクラッチパッドの部分を表しています。『L1』と『L2』のレベルが左側にあります（ほとんど完全に上書きされています）。スクラッチパッドの右側は、下部の1792KiBを表しています。上書きされているのは約66%ですが、書き込みは一様にランダムに広がっています。

スクラッチパッドのエントロピーの分析については付録Dを参照してください。

2.8.3 読み書きの比率

プログラムは、プログラムの反復ごとに、平均して39回の読み取り（命令IADD_M、ISUB_M、IMUL_M、IMULH_M、ISMULH_M、IXOR_M、FADD_M、FSUB_M、FDIV_M）と16回の書き込み（命令ISTORE）をスクラッチパッドに行います。追加の128バイトはレジスタ値の初期化と保存のために暗黙的に読み書きされます。イテレーションごとにデータセットから64バイトのデータが読み込まれます。合計すると

プログラムの繰り返しごとにメモリから読み出されるデータの平均量は、39 * 8 + 128 + 64 = 504 bytes
プログラムの繰り返しごとにメモリに書き込まれるデータの平均マウントは、16 * 8 + 128 = 256 bytes

これはCPUが最適化されている2:1の読み書きの比率に近いものです。

2.9 データセット

スクラッチパッドは通常 CPU のキャッシュに格納されているため、メモリコントローラを使用するのはデータセットへのアクセスのみです。

RandomX はプログラムの反復ごとに 1 回（ハッシュ結果ごとに 16384 回）データセットからランダムに読み出します。データセットはDRAMに格納する必要があるため、DRAMではバンクグループごとに毎秒約2,500万回以上のランダムアクセスを行うことができず、自然な並列化の限界となっています。個別にアドレス指定可能な各バンクグループでは、約1500H/sのスループットが可能です。

すべてのデータセットアクセスは、1つのCPUキャッシュライン（64バイト）を読み込み、完全にプリフェッチされます。本仕様書の4.6.2章に記載されている1つのプログラム反復の実行時間は、一般的なDRAMアクセスレイテンシー（50～100ns）とほぼ同じです。

2.9.1 キャッシュ

軽量検証やデータセットの構築に使用されるキャッシュはデータセットの約8分の1の大きさです。面積と時間の積を一定に保つために、各データセットアイテムは8 回のランダムなキャッシュアクセスから構築されます。

256MiBはオンチップに搭載するのに十分なサイズであるため、RandomXは高レイテンシー、高消費電力のカスタム混合関数（『SuperscalarHash』）を使用しています。これは低レイテンシーのメモリを使用するメリットを損なうものであり、SuperscalarHashの計算に必要なエネルギーにより、軽量モードはマイニングには非常に非効率なものとなっています（3.4章参照）。

トレードオフ耐性のあるArgon2dを3回反復して使用するため256MiB以下のメモリを使用することはできません。3 回の反復（パス）を使用する場合、メモリ使用量を半分にすると、最良のトレードオフ攻撃 [27]の計算コストが 3423 倍になります。

3. カスタム関数

3.1 AesGenerator1R

AesGenerator1R はスクラッチパッドを埋める疑似乱数データを可能な限り高速に生成するために設計されました。最新の CPU でハードウェアアクセラレーションされた AES を利用しています。16バイトの出力につき1回のAESラウンドが実行されるだけなので、ほとんどの最新CPUで20GB/sを超えるスループットが得られます。

AesGenerator1R は、十分に「ランダム」な初期状態で初期化されていれば、良好な出力分布が得られます (付録 F 参照)。

3.2 AesGenerator4R

AesGenerator4R はAES を 4 ラウンド使用して Program Buffer 初期化用の疑似乱数データを生成します。AesGenerator4Rは全入力ビットの完全なアバランシェにはAES2ラウンドで十分であるため[28]、非常に優れた性能を維持しつつ、優れた統計的特性(付録F参照)を有しています。

このジェネレーターの可逆性はジェネレーターの状態が常に非可逆ハッシュ関数の出力を用いて初期化されるため問題とはなりません(Blake2b)。

3.3 AesHash1R

AesHash はスクラッチパッドのフィンガープリントを可能な限り高速に計算するために設計されました。スクラッチパッドを AES のラウンドキーのセットとして解釈しているため、32768 ラウンドの AES 暗号化と同じになります。各レーンのすべてのスクラッチパッドのビットのアバランシェを保証するように、最後に2つの追加ラウンドが実行されます。

AesHash1Rの可逆性は主に2つの理由で問題とはなりません。

AesHash1Rの入力を直接制御することはできません
AesHash1R の出力は可逆ではない Blake2b ハッシュ関数に渡されます

3.4 SuperscalarHash

SuperscalarHashはCPUがDRAMからのデータのロードを待っている間にできるだけ多くの電力を消費するように設計されています。目標としたレイテンシー170サイクルは通常のDRAMレイテンシー40～80ns、クロック周波数2～4GHzに相当します。軽量モードマイニング用に設計された低レイテンシーのメモリを搭載したASICデバイスは、データセットアイテムを計算する際にSuperscalarHashがボトルネックとなり、SuperscalarHashの高い消費電力によって効率が損なわれてしまいます。

平均的な SuperscalarHash 関数には合計 450 の命令があり、そのうち 155 は 64 ビットの乗算です。平均して最も長い依存関係の連鎖は95命令です。軽量モードマイニング用のASICデザインは256MiBのオンダイメモリを持ちすべてのオペレーションに1サイクルのレイテンシを持つため、無制限の並列化を仮定した場合、データセットアイテムの構築に平均95 * 8 = 760サイクルが必要になります。アイテムごとに 155 * 8 = 1240 個の 64 ビット乗算を実行しなければならず、これは DRAM から 64 バイトをロードするのに匹敵するエネルギーを消費します。

付録

A. VM 実行のチェーンの効果

1.2章ではN個のランダムプログラムをチェーンさせて『簡単な』プログラムを探すマイニング戦略を防ぐ理由を説明しました。RandomX は N = 8 という値を使っています。

ここでQをフィルタリングを用いた戦略における許容範囲のプログラムの比率と定義します。例えば、Q = 0.75は25%のプログラムが拒否されることを意味します。

N = 1の場合、無駄なプログラムの実行はなく、コストはプログラムの生成とフィルタリング自体だけです。以下の計算ではこれらのコストはゼロであり、実際のコストはプログラムの実行のみであると仮定しています。しかし、RandomXでのプログラム生成は自由ではないため（最初のプログラム生成にはスクラッチパッドの完全な初期化が必要）、これは単純化されたものですが、攻撃者にとっての最良のシナリオを説明しています。

N > 1の場合、最初のプログラムは通常通りフィルタリングできますが、プログラムが実行された後、次のプログラムが拒否される可能性は 1-Q であり、プログラムの実行を1回無駄にしたことになります。

N個のチェーン実行ではチェーン内のすべてのプログラムが受け入れられる可能性はQ^Nしかありません。しかし、そのようなチェーンを見つけようとするたびに、いくつかのプログラムの実行を無駄にすることになります。N = 8の場合、1回の試行で無駄になるプログラムの数は、(1-Q)*(1+2*Q+3*Q²+4*Q³+5*Q⁴+6ften*Q⁵+7*Q⁶)になります（Q = 0.75の場合は約2.5）。

3つの採掘戦略を考えてみましょう。

戦略I

プログラムを一切拒否しない誠実なマイナー（Q = 1）。

戦略II

プログラムの25%を実行できないが(Q = 0.75)、サポートされているプログラムは50%速く実行できる、最適化されたカスタムハードウェアを使用するマイナー。

戦略III

すべてのプログラムを実行できるが、チェーンの最初のプログラムのために、最も遅いプログラムの25％を拒否するマイナー。これによりチェーンの最初のプログラムのパフォーマンスが5%向上します（これは付録Cのランタイム分布と一致します）。

結果

以下の表は、上記の3つの戦略と、異なるNの値に対する結果を示しています。列N(I)、N(II)、N(III)には、各戦略が1つの有効なハッシュ結果を得るために平均的に実行しなければならないプログラム数が記載されています（これには拒否されたチェーンで無駄になったプログラムも含まれます）。列Speed(I)、Speed(II)、Speed(III)は、戦略Iに対する平均採掘性能を示している。

N	N(I)	N(II)	N(III)	Speed(I)	Speed(II)	Speed(III)
1	1	1	1	1.00	1.50	1.05
2	2	2.3	2	1.00	1.28	1.02
4	4	6.5	4	1.00	0.92	1.01
8	8	27.0	8	1.00	0.44	1.00

N = 8の場合、戦略IIは、特定のプログラムでは50%のパフォーマンスの優位性があるにもかかわらず、正直なマイナーの半分以下のスピードで実行されます。ストラテジーIIIの統計的な優位性は、N = 8では無視できるほど小さくなります。

B. 性能シミュレーション

2.7章で説明したように、RandomXは現代の高性能CPUの複雑な設計を利用することを目的としています。スーパースカラやアウトオブオーダーや投機的実行の影響を評価するために簡略化したCPUシミュレーションを行いました。ソースコードはperf-simulation.cppにあります。

CPUモデル

モデルCPUは3段のパイプラインを使用して、理想的なスループットである1命令/サイクルを実現しています。

        (1) (2) (3)
+------------------+ 　　　 +----------------+       +----------------+
| 命令フェッチ 　　　　| 　　　|　　　　　　　　　  |      |                |
|  ＋      　　　 　　| ---> | メモリアクセス    | ---> |    実行        |
| デコード 　　  　　 |      |                 |      |                |
+------------------+       +----------------+       +----------------+

の3つのステージがあります。

命令フェッチとデコード。このステージでは、プログラムバッファから命令をロードし、命令操作とオペランドをデコードします。
メモリアクセス。この命令がメモリ・オペランドを使用する場合は、このステージでスクラッチパッドからロードされます。これには、メモリアドレスの計算も含まれます。ストアもこの段階で行われます。アドレス・レジスタの値は、このステージで利用可能でなければなりません。
実行。このステージでは、前のステージで取得したオペランドを使用して命令を実行し、その結果をレジスタファイルに書き込みます。

なお、これは最適な短さのパイプラインであり、あまり高いクロックスピードは期待できません。より長いパイプラインを使用した設計では、投機的実行のメリットが大幅に増加します。

スーパースカラ実行

今回のモデルCPUには2種類のコンポーネントがあります。

実行ユニット (EXU) - 実際の整数演算や浮動小数点演算を行うためのものです。ISTOREを除くすべてのRandomX命令は、第3パイプラインステージの実行ユニットを使用する必要があります。すべての演算は1クロック・サイクルしかかからないと考えられています。
メモリユニット（MEM） - スクラッチパッドへのロードとストアに使用されます。ISTOREを含むすべてのメモリ命令は、第2パイプラインステージのメモリユニットを使用します。

スーパースカラ設計では性能を向上させるために複数の実行ユニットやメモリユニットを使用します。

アウトオブオーダー実行

シミュレーションモデルは2つのデザインをサポートしています。

インオーダー - すべての命令がプログラムバッファに表示された順に実行されます。このデザインは依存関係が発生した場合や必要なEXU/MEMユニットが利用できない場合にストールします。
アウトオブオーダー - プログラム順に命令を実行せずオペランドの準備が整い必要なEXU/MEMユニットが利用可能になったときに命令を実行することができます。

分岐処理

シミュレーションモデルでは2種類の分岐処理をサポートしています。

非投機的 - 分岐が発生すると、パイプラインが停止します。通常、分岐ごとに3サイクルのペナルティが課せられます。
投機的 - すべての分岐は実行されないと予測され、予測ミスが発生した場合はパイプラインがフラッシュされます（確率は1/256）．

結果

以下の10デザインをシミュレーションし、RandomXプログラム（256命令）の実行にかかる平均クロックサイクル数を測定しました。

デザイン	スーパースカラコンフィグ	並び替え	分岐処理	実行時間 [サイクル]	IPC
#1	1 EXU + 1 MEM	インオーダー	非投機的	293	0.87
#2	1 EXU + 1 MEM	インオーダー	投機的	262	0.98
#3	2 EXU + 1 MEM	インオーダー	非投機的	197	1.3
#4	2 EXU + 1 MEM	インオーダー	投機的	161	1.6
#5	2 EXU + 1 MEM	アウトオブオーダー	非投機的	144	1.8
#6	2 EXU + 1 MEM	アウトオブオーダー	投機的	122	2.1
#7	4 EXU + 2 MEM	インオーダー	非投機的	135	1.9
#8	4 EXU + 2 MEM	インオーダー	投機的	99	2.6
#9	4 EXU + 2 MEM	アウトオブオーダー	非投機的	89	2.9
#10	4 EXU + 2 MEM	アウトオブオーダー	投機的	64	4.0

スーパースカラ設計、アウトオブオーダー設計、投機的設計のメリットが明確に示されています。

C. RandomX のランタイム分布

ランタイム数は1コアを使用して3.0GHzで動作するAMD Ryzen 7 1700で測定しました。プログラムの実行時間と検証時間を測定するソースコードは、runtime-distr.cppで公開しています。x86 JITコンパイラの性能を測定するソースコードは、jit-performance.cppにあります。

高速モード-プログラムの実行

次の図は、1つのVMプログラム（高速モード）のランタイムの分布を示しています。これには、プログラムの生成、JITコンパイル、VMの実行、レジスタ・ファイルのBlake2bハッシュが含まれます。プログラムの生成とJITコンパイルには1つのプログラムにつき3.6μsかかることが計測されました。

AMD Ryzen 7 1700は、高速モード（1スレッド使用）で1秒間に625個のハッシュを計算することができ、1つのハッシュ結果に1600μs（1.6ms）かかることになります。これは（およそ）次のような構成になっています。

VM実行(8プログラム)に1480μs
スクラッチパッドの初期入力（AesGenerator1R）に45μs。
スクラッチパッドの最終ハッシュ（AesHash1R）に45μs。
プログラムの生成とJITコンパイルに30μs（8つのプログラム）。

これにより全体のオーバーヘッドは7.5%となります（ハッシュごとにVMを実行していない時間）。

軽量モード-検証時間

次の図は、軽量モードを使って1つのハッシュ結果を計算する時間の分布を示しています。ほとんどの時間はデータセットアイテムを計算するためのSuperscalarHashの実行に費やされています（14.8msのうち13.2ms）。この平均検証時間はCryptoNightアルゴリズムの性能と完全に一致しています。

D. スクラッチパッドのエントロピー分析

プログラムを8回実行した後のスクラッチパッドの平均エントロピーを、LZMA圧縮アルゴリズムを用いて近似しました。

ハッシュ結果を計算し、最終的なスクラッチパッドを '.spad' 拡張子のファイルとしてディスクに書き込みました (ソースコード: scratchpad-entropy.cpp)
7-Zip [29]のUltra圧縮モードで圧縮しています．7z.exe a -t7z -m0=lzma2 -mx=9 scratchpads.7z *.spad`.

得られたアーカイブのサイズはスクラッチパッドファイルの圧縮されていないサイズの約99.98%です。これはスクラッチパッドがVM実行中に高いエントロピーを保持していることを示しています。

E. SuperscalarHash の分析

SuperscalarHash はRandomX がデータセットアイテムを生成するために使用するカスタム関数です。8個の整数レジスタで動作しランダムな命令列を使用します。命令の約1/3は乗算です。

次の図は入力レジスタの1ビットの変更に対するSuperscalarHashの感度を示しています。

これを見ると、SuperscalaHashは高次ビットに対する感度がかなり低く、低次ビットに対する感度がやや低いことがわかります。感度が最も高いのは、第3～53ビットです。

データセットアイテムを計算する際、最初のSuperscalarHashの入力はアイテム番号にのみ依存します。結果の分布を良好にするために、仕様書の7.3節に記載されている定数は、0～34078718の範囲内の『すべての』項目番号に対して、第3～53ビットの一意の値を提供するように選択されています（データセットには34078719の項目が含まれています）。すべてのデータセットアイテム番号のすべての初期レジスタ値をチェックし、各レジスタの第3～53ビットが一意であり、衝突がないことを確認しました（ソースコード：superscalar-init.cpp)。SuperscalarHashからユニークな出力を得るために厳密には必要ありませんが、ランダムに生成されるSuperscalarHashインスタンスの非完全なアバランシェ特性を緩和するセキュリティ上の予防措置です。

F. RNGの統計的テスト

AesGenerator1RとAesGenerator4Rの両方を乱数生成器の経験的なテストを目的としたTestU01ライブラリ[30]を用いてテストしました。ソースコードはrng-tests.cppにあります。

このテストでは、各ジェネレータから約200MB（『SmallCrush』テスト）、500GB（『Crush 』テスト）、または4TB（『BigCrush 』テスト）の出力がサンプリングされます。これはRandomXで生成された量（AesGenerator4Rで2176バイト、AesGenerator1Rで2MiB）よりもかなり多いので、テストで失敗しても必ずしもジェネレータがユースケースに適していないことを意味するわけではありません。

AesGenerator4R

このジェネレータはBlake2b ハッシュ関数を使って初期化すると『BigCrush』スイートのすべてのテストに合格します。

$ bin/rng-tests 1
state0 = 67e8bbe567a1c18c91a316faf19fab73
state1 = 39f7c0e0a8d96512c525852124fdc9fe
state2 = 7abb07b2c90e04f098261e323eee8159
state3 = 3df534c34cdfbb4e70f8c0e1826f4cf7

...

========= Summary results of BigCrush =========

 Version:          TestU01 1.2.3
 Generator:        AesGenerator4R
 Number of statistics:  160
 Total CPU time:   02:50:18.34

 All tests were passed

このジェネレーターは初期状態がすべてゼロに設定されていても『Crush』スイートのすべてのテストに合格します。

$ bin/rng-tests 0
state0 = 00000000000000000000000000000000
state1 = 00000000000000000000000000000000
state2 = 00000000000000000000000000000000
state3 = 00000000000000000000000000000000

...

========= Summary results of Crush =========

 Version:          TestU01 1.2.3
 Generator:        AesGenerator4R
 Number of statistics:  144
 Total CPU time:   00:25:17.95

 All tests were passed

AesGenerator1R

このジェネレータはBlake2b ハッシュ関数を使用して初期化した場合『Crush』スイートのすべてのテストに合格します。

$ bin/rng-tests 1
state0 = 67e8bbe567a1c18c91a316faf19fab73
state1 = 39f7c0e0a8d96512c525852124fdc9fe
state2 = 7abb07b2c90e04f098261e323eee8159
state3 = 3df534c34cdfbb4e70f8c0e1826f4cf7

...

========= Summary results of Crush =========

 Version:          TestU01 1.2.3
 Generator:        AesGenerator1R
 Number of statistics:  144
 Total CPU time:   00:25:06.07

 All tests were passed

初期状態がすべてゼロに初期化されている場合、『Crush』スイートの144のテストのうちジェネレーターは1つのテストに失敗します。

$ bin/rng-tests 0
state0 = 00000000000000000000000000000000
state1 = 00000000000000000000000000000000
state2 = 00000000000000000000000000000000
state3 = 00000000000000000000000000000000

...

========= Summary results of Crush =========

 Version:          TestU01 1.2.3
 Generator:        AesGenerator1R
 Number of statistics:  144
 Total CPU time:   00:26:12.75
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
 12  BirthdaySpacings, t = 3        1 -  4.4e-5
 ----------------------------------------------
 All other tests were passed

参考文献

[1] CryptoNoteホワイトペーパー - https://cryptonote.org/whitepaper.pdf

[2] ProgPoW: Inefficient integer multiplications - https://github.com/ifdefelse/ProgPOW/issues/16

[3] 暗号学的ハッシュ関数 - https://en.wikipedia.org/wiki/Cryptographic_hash_function

[4] randprog - https://github.com/hyc/randprog

[5] RandomJS - https://github.com/tevador/RandomJS

[6] μop cache - https://en.wikipedia.org/wiki/CPU_cache#Micro-operation_(%CE%BCop_or_uop)_cache

[7] 命令レベルの並列性 - https://en.wikipedia.org/wiki/Instruction-level_parallelism

[8] スーパースカラ・プロセッサ - https://en.wikipedia.org/wiki/Superscalar_processor

[9] アウトオブオーダー実行 - https://en.wikipedia.org/wiki/Out-of-order_execution

[10] 投機的実行 - https://en.wikipedia.org/wiki/Speculative_execution

[11] レジスタリネーミング - https://en.wikipedia.org/wiki/Register_renaming

[12] Blake2ハッシュ関数 - https://blake2.net/

[13] Advanced Encryption Standard - https://en.wikipedia.org/wiki/Advanced_Encryption_Standard

[14] 対数正規分布 - https://en.wikipedia.org/wiki/Log-normal_distribution

[15] CryptoNight ハッシュ関数 - https://cryptonote.org/cns/cns008.txt

[16] ダイナミックランダムアクセスメモリ(DRAM) - https://en.wikipedia.org/wiki/Dynamic_random-access_memory

[17] マルチチャネルメモリアーキテクチャ - https://en.wikipedia.org/wiki/Multi-channel_memory_architecture

[18] Obelisk GRN1チップの詳細 - https://www.grin-forum.org/t/obelisk-grn1-chip-details/4571

[19] Biryukov et al: Tradeoff Cryptanalysis of Memory-Hard Functions - https://eprint.iacr.org/2015/227.pdf

[20] SK Hynix 20nm DRAM density - http://en.thelec.kr/news/articleView.html?idxno=20

[21] 分岐予測器- https://en.wikipedia.org/wiki/Branch_predictor

[22] 分岐予測 - https://en.wikipedia.org/wiki/Predication_(computer_architecture)

[23] CPUキャッシュ - https://en.wikipedia.org/wiki/CPU_cache

[24] Cortex-A55 マイクロアーキテクチャ - https://www.anandtech.com/show/11441/dynamiq-and-arms-new-cpus-cortex-a75-a55/4

[25] AMD Zen+ マイクロアーキテクチャー - https://en.wikichip.org/wiki/amd/microarchitectures/zen%2B#Memory_Hierarchy

[26] Intel Skylake Microarchitecture - https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(client)#Memory_Hierarchy

[27] Biryukov et al: Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing - https://eprint.iacr.org/2015/430.pdf Table 2, page 8

[28] J. Daemen, V. Rijmen: AES Proposal: Rijndael - https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guidelines/documents/aes-development/rijndael-ammended.pdf 28ページ

[29] 7-Zip ファイルアーカイバ - https://www.7-zip.org/

[30] TestU01 library - http://simul.iro.umontreal.ca/testu01/tu01.html

ASIC耐性を持つProgPoW RandomX設計の翻訳