著者: スター・リー
この記事は業界の学習と交流のみを目的としており、投資の参考となるものではありません。引用する必要がある場合は、出典を明記してください。転載については、IOSG チームに連絡して許可と転載の指示を取得してください。コンテンツを提供してくれた著者の Star Li に感謝します。
ゼロ知識証明技術は、プライバシー証明、計算証明、コンセンサス証明などにますます使用されています。より優れたアプリケーション シナリオを模索する中で、多くの人が徐々にゼロ知識証明のパフォーマンスがボトルネックであることに気づきました。 Trapdoor Tech チームは 2019 年にゼロ知識証明テクノロジーに関する詳細な研究を開始し、効率的なゼロ知識証明アクセラレーション ソリューションを模索してきました。 GPU または FPGA は、現在市場に出ている一般的なアクセラレーション プラットフォームです。この記事では、MSM の計算から始めて、FPGA と GPU で高速化されたゼロ知識証明計算の長所と短所を分析します。
TL;DR
ZKP は将来性の高い技術です。ゼロ知識証明テクノロジーを採用するアプリケーションがますます増えています。ただし、ZKP アルゴリズムは多数あり、さまざまなプロジェクトで異なる ZKP アルゴリズムが使用されています。同時に、ZKP 証明の計算パフォーマンスは比較的劣ります。この記事では、MSM アルゴリズム、楕円曲線点加算アルゴリズム、モンゴメリ乗算アルゴリズムなどを詳細に分析し、BLS12_381 曲線点加算における GPU と FPGA の性能差を比較します。一般に、ZKP 証明計算に関しては、高スループット、高コストパフォーマンス、プログラマビリティなど、GPU の短期的な利点は比較的明白です。 FPGA には消費電力の点で一定の利点があります。長期的には、ZKP 計算に適した FPGA チップ、または ZKP 用にカスタマイズされた ASIC チップが登場する可能性があります。
ZKPアルゴリズムは複雑です
ZKPとは、ゼロ知識証明技術（Zero Knowledge Proof）の総称です。 zk-SNARK と zk-STARK の 2 つの主要なカテゴリがあります。 zk-SNARK の現在一般的なアルゴリズムは、Groth16、PLONK、PLOOKUP、Marlin、Halo/Halo2 です。 zk-SNARK アルゴリズムの反復は主に 2 つの方向に沿って行われます: 1/信頼できるセットアップが必要かどうか 2/回路構造のパフォーマンス。 zk-STARK アルゴリズムの利点は、信頼できる設定を必要としないが、検証計算量が対数線形であることです。
zk-SNARK/zk-STARK アルゴリズムのアプリケーションに関する限り、さまざまなプロジェクトで使用されるゼロ知識証明アルゴリズムは比較的分散しています。 zk-SNARK アルゴリズムのアプリケーションでは、PLONK/Halo2 アルゴリズムはユニバーサルであるため (信頼できるセットアップは必要ありません)、アプリケーションはますます増える可能性があります。
PLONK は計算量を証明します
PLONK アルゴリズムを例として、PLONK 証明の計算量を分析します。
PLONK 証明部分の計算量は 4 つの部分で構成されます。
1/ MSM - 複数のスカラー乗算。 MSM は、多項式コミットメントの計算によく使用されます。
2/ NTT 計算 - ポイント値と係数表現間の多項式変換。
3/ 多項式の計算 - 多項式の加算、減算、乗算、除算。多項式評価(Evaluation)など。
4/ 回路合成 - 回路合成。計算のこの部分は、回路のサイズ/複雑さに関係します。
一般に、回路合成部分の計算量は判定やループロジックが多く、並列度は比較的低く、CPU による計算に適しています。一般に、ゼロ知識証明の高速化とは、最初の 3 つの部分の計算高速化を指します。このうち、比較的計算量が多いのは MSM で、次に NTT が続きます。
MSMとは何か
MSM (Multiple Scalar Multiplication) は、楕円曲線上の与えられた一連の点とスカラーを参照し、これらの点を加算した結果に対応する点を計算します。
たとえば、楕円曲線上の一連の点が与えられたとします。
指定された 1 つの曲線からの楕円曲線点の固定セットが与えられた場合:
[G_1、G_2、G_3、...、G_n]
そしてランダム係数:
指定されたスカラー場からランダムにサンプリングされた有限体要素:
[s_1、s_2、s_3、...、s_n]
MSM は楕円曲線の点 Q を取得するための計算です。
Q = \sum_{i=1}^{n}s_i*G_i
業界では通常、ピッペンジャー アルゴリズムを使用して MSM 計算を最適化します。ピッペンジャー アルゴリズムのプロセスの概略図を詳しく見てみましょう。
ピッペンジャー アルゴリズムの計算プロセスは 2 つのステップに分かれています。
1/ Scalar は Windows に分割されます。スカラーが 256 ビットでウィンドウが 8 ビットの場合、すべてのスカラーは 256/8=32 のウィンドウに分割されます。 Window の各層は「バケット」を使用して中間結果を一時的に保存します。 GW_x は、1 つのレイヤー上の累積結果のポイントです。 GW_x の計算も比較的簡単です。層内の各スカラーが順番に探索され、スカラー層の値がインデックスとして使用され、対応する G_x が対応するバケット ビットに追加されます。実際、原理は比較的単純です。2 つの点の加算の係数が同じである場合は、最初に 2 つの点を加算してからスカラー加算を実行します。2 つの点に対して 2 つのスカラー加算を実行してから加算する必要はありません。それらをアップします。
2/ 各ウィンドウで計算されたポイントは二重加算によって累積され、最終結果が得られます。
ピッペンジャー アルゴリズムには、多くの変形最適化アルゴリズムもあります。いずれの場合も、MSM アルゴリズムの基礎となる計算は、楕円曲線上の点の加算です。異なる最適化アルゴリズムは、異なる加点数に対応します。
楕円曲線点の追加
このウェブサイトでは、「短いワイエルシュトラス」形式の楕円曲線上での点加算のさまざまなアルゴリズムをご覧いただけます。
http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
2点の射影座標をそれぞれ(x1, y1, z1)、(x2, y2, z2)とすると、点加算結果(x3, y3, z3)は以下の計算式で計算できます。
計算プロセスを詳細に説明する理由は、計算プロセス全体がほとんどが整数演算であることを示すためです。整数のビット幅は、楕円曲線のパラメータによって異なります。いくつかの一般的な楕円曲線のビット幅を与えます。
BN256 - 256ビット BLS12_381 - 381ビット BLS12_377 - 377ビット
特に、これらの整数演算はモジュロフィールド上の演算であることに注意してください。剰余加算/剰余減算は比較的単純です。剰余乗算の原理と実装に焦点を当てましょう。
モジュラー乗算
モジュラー ドメインに 2 つの値 x と y が与えられます。剰余乗算の計算は、x*y mod p を参照します。これらの整数のビット幅は楕円曲線のビット幅であることに注意してください。剰余乗算の古典的なアルゴリズムはモンゴメリ乗算です。モンゴメリ乗算を実行する前に、被乗数をモンゴメリ表現に変換する必要があります。
モンゴメリ乗算の公式は次のとおりです。
モンゴメリ乗算の実装アルゴリズムには、CIOS (Coarsely Integrated Operand Scanning)、FIOS (Finely Integrated Operand Scanning)、FIPS (Finely Integrated Product Scanning) など、数多くあります。この記事では、さまざまなアルゴリズムの実装の詳細については説明しません。興味のある読者は自分で学習してください。
FPGA と GPU のパフォーマンスの違いを比較するために、最も基本的なアルゴリズム実装方法が選択されます。
簡単に言えば、剰余乗算アルゴリズムは、大数乗算と大数加算の 2 つの計算にさらに分割できます。 MSM の計算ロジックを理解した後、モジュラー乗算のパフォーマンス (スループット) を選択して、FPGA と GPU のパフォーマンスを比較できます。
観察して考える
このような FPGA 設計では、VU9P 全体が BLS12_381 楕円曲線点でのスループットを提供できると推定できます。 1 点加算 (add_mix メソッド) には、約 12 回の剰余乗算が必要です。 FPGAのシステムクロックは450Mです。
同じモジュラー乗算/モジュロ加算アルゴリズムの下で、同じ点加算アルゴリズムを使用すると、Nvidia 3090 の点加算トラフプット (データ伝送係数を考慮) は 500M/s を超えます。もちろん、計算全体にはさまざまなアルゴリズムが含まれます。FPGA に適したアルゴリズムもあれば、GPU に適したアルゴリズムもあるでしょう。同じアルゴリズム比較を使用する理由は、FPGA と GPU のコア コンピューティング能力を比較するためです。
上記の結果に基づいて、ZKP プルーフ パフォーマンスの観点から GPU と FPGA の比較をまとめてみましょう。
要約する
ゼロ知識証明テクノロジーを採用するアプリケーションがますます増えています。ただし、ZKP アルゴリズムは多数あり、さまざまなプロジェクトで異なる ZKP アルゴリズムが使用されています。私たちの実際のエンジニアリング経験から判断すると、FPGA も選択肢の 1 つですが、現時点では GPU が費用対効果の高い選択肢です。 FPGA は決定論的コンピューティングを好み、レイテンシーと消費電力の点で利点があります。 GPU は高度にプログラム可能で、比較的成熟したハイパフォーマンス コンピューティング フレームワークを備え、開発反復サイクルが短く、スループット シナリオを好みます。