FPGA と GPU で高速化されたゼロ知識証明コンピューティングの長所と短所を理解するための記事
原作者: スター・リー
出典: IOSG Ventures
プライバシー証明、計算証明、コンセンサス証明など、ゼロ知識証明技術はますます広く使用されています。より優れたアプリケーション シナリオを模索するうちに、多くの人が徐々に、ゼロ知識証明によってパフォーマンスがボトルネックになっていることが判明しました。 Trapdoor Tech チームは、2019 年からゼロ知識証明テクノロジーを深く研究し、効率的なゼロ知識証明アクセラレーション ソリューションを模索してきました。 GPU または FPGA は、現在市場で比較的一般的なアクセラレーション プラットフォームです。このペーパーでは、MSM の計算から開始し、FPGA と GPU で高速化されたゼロ知識証明計算の長所と短所を分析します。
TL;DR
ZKP は将来性の高い技術です。ゼロ知識証明テクノロジーを採用するアプリケーションがますます増えています。ただし、ZKP アルゴリズムは多数あり、さまざまなプロジェクトで異なる ZKP アルゴリズムが使用されています。同時に、ZKP 証明の計算パフォーマンスは比較的劣ります。本稿では、MSMアルゴリズム、楕円曲線点加算アルゴリズム、モンゴメリ乗算アルゴリズムなどを詳細に分析し、BLS 12_381曲線点加算におけるGPUとFPGAの性能差を比較します。一般に、ZKP 証明コンピューティングの観点からは、短期 GPU には、高スループット、高コストパフォーマンス、プログラマビリティなどの明らかな利点があります。相対的に言えば、FPGA には消費電力の点で一定の利点があります。長期的には、ZKP 計算に適した FPGA チップ、または ZKP 用にカスタマイズされた ASIC チップが登場する可能性があります。
ZKP アルゴリズムは複雑です
ZKPとは、Zero Knowledge Proof技術（Zero Knowledge Proof）の総称です。主に zk-SNARK と zk-STARK の 2 つの分類があります。 zk-SNARK の現在の一般的なアルゴリズムは、Groth 16、PLONK、PLOOKUP、Marlin、Halo/Halo 2 です。 zk-SNARK アルゴリズムの反復は主に 2 つの方向に沿って行われます: 1/信頼できるセットアップが必要かどうか 2/回路構造のパフォーマンス。 zk-STARK アルゴリズムの利点は、信頼できるセットアップが必要ないにもかかわらず、検証計算の量が対数線形であることです。
zk-SNARK/zk-STARK アルゴリズムのアプリケーションに関する限り、さまざまなプロジェクトで使用されるゼロ知識証明アルゴリズムは比較的分散しています。 zk-SNARK アルゴリズムのアプリケーションでは、PLONK/Halo 2 アルゴリズムはユニバーサルであるため (信頼できるセットアップは必要ありません)、アプリケーションはますます増える可能性があります。
PLONKは計算量を証明する
PLONK アルゴリズムを例として、PLONK 証明の計算量を分析します。
PLONK 証明部分の計算量は 4 つの部分で構成されます。
1/ MSM - 複数のスカラー乗算。 MSM は、多項式コミットメントを計算するためによく使用されます。
2/ NTT Computation - ポイント値と係数表現の間の多項式変換。
3/ 多項式の計算 - 多項式の加算、減算、乗算、除算。多項式評価(Evaluation)など。
4/ 回路合成 - 回路合成。この部分の計算は回路の規模/複雑さに関係します。
一般的に、回路合成部分の計算量は判定やループロジックが多く、並列度は比較的低いため、CPU による計算に適しています。一般に、ゼロ知識証明の高速化とは、最初の 3 つの部分の計算高速化を指します。このうち、比較的計算量が多いのは MSM で、次に NTT が続く。
What's MSM
MSM (Multiple Scalar Multiplication) は、楕円曲線上の与えられた一連の点とスカラーを参照し、これらの点を加算した結果に対応する点を計算します。
たとえば、楕円曲線上の一連の点が与えられたとします。
Given a fixed set of Elliptic curve points from one specified curve:
[G_ 1, G_ 2, G_ 3, ..., G_n]
ランダム係数:
and a randomly sampled finite field elements from specified scalar field:
[s_ 1, s_ 2, s_ 3, ..., s_n]
MSM is the calculation to get the Elliptic curve point Q:
Q = \sum_{i= 1 }^{n}s_i*G_i
業界では一般に、MSM 計算を最適化するためにピッペンジャー アルゴリズムを採用しています。ピッペンジャーのアルゴリズムのプロセスの概略図を詳しく見てみましょう。
ピッペンジャー アルゴリズムの計算プロセスは 2 つのステップに分かれています。
1/ スカラーは Windows に分割されます。スカラーが 256 ビット、ウィンドウが 8 ビットの場合、すべてのスカラーは 256/8 = 32 のウィンドウに分割されます。 Window の各層は「バケット」を使用して中間結果を一時的に保存します。 GW_x は 1 つのレイヤ上の累積結果のポイントです。 GW_x の計算も比較的単純で、1 つのレイヤ内の各スカラーを順番に走査し、インデックスとしてのスカラー レイヤの値に従って、対応する G_x を対応するバケットのビットに追加します。実際、原理は比較的単純で、2 点の加算係数が同じ場合、スカラーを加算する前に 2 点を 2 回加算するのではなく、最初に 2 点を加算してからスカラーを再度加算します。
2/ 各ウィンドウで計算されたポイントは二重加算によって累積され、最終結果が得られます。
ピッペンジャーのアルゴリズムには、多くの変形最適化アルゴリズムもあります。いずれの場合も、MSM アルゴリズムの基礎となる計算は、楕円曲線上の点の追加です。異なる最適化アルゴリズムは、異なる追加ポイント数に対応します。
楕円曲線点加算(Point Add)
このサイトでは、「ショートワイエルシュトラス」形式の楕円曲線上の点加算のさまざまなアルゴリズムをご覧いただけます。
http://www.hyperelliptic.org/EFD/g 1 p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
2 つの点の射影座標をそれぞれ (x 1, y 1, z 1) と (x 2, y 2, z 2) とすると、点加算の結果 (x 3, y 3) は次のように計算できます。下記計算式、z 3)．
計算プロセスを詳細に説明する理由は、計算プロセス全体がほとんど整数演算であることを示すためです。整数のビット幅は、楕円曲線のパラメータによって異なります。いくつかの一般的な楕円曲線のビット幅を与えます。
BN 256 - 256 bits
BLS 12 _ 381 - 381 bits
BLS 12 _ 377 - 377 bits
特に、これらの整数演算はモジュロフィールド上の演算であることに注意してください。剰余加算/剰余減算は比較的単純であり、剰余乗算の原理と実装に焦点を当てます。
剰余乗算
モジュロフィールドに対して 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 のパフォーマンスを比較できます。
観察して考える
このようなＦＰＧＡ設計の下では、ＶＵ９Ｐ全体がＢＬＳ１２＿３８１の楕円曲線点でのスループットを提供できると推定できる。点加算 (add_mix メソッド) には、約 12 回の剰余乗算が必要です。 FPGAのシステムクロックは450Mです。
同じモジュラー乗算/モジュラー加算アルゴリズムの下で、同じポイント加算アルゴリズムを使用すると、Nvidia 3090 のポイントプラス トループット (データ伝送係数を考慮) は 500 M/s を超えます。もちろん、計算全体にはさまざまなアルゴリズムが含まれており、FPGA に適したアルゴリズムもあれば、GPU に適したアルゴリズムもあります。同じアルゴリズム比較を使用する理由は、FPGA と GPU のコア コンピューティング能力を比較するためです。
要約する
要約する
ゼロ知識証明テクノロジーを採用するアプリケーションがますます増えています。ただし、ZKP アルゴリズムは多数あり、さまざまなプロジェクトで異なる ZKP アルゴリズムが使用されています。私たちの実践的なエンジニアリングの経験から、FPGA はオプションですが、現時点では GPU がコスト効率の高いオプションです。 FPGA は決定論的コンピューティングを好みます。これには、遅延と消費電力の利点があります。 GPU は高いプログラマビリティを備え、比較的成熟したハイパフォーマンス コンピューティング フレームワークを備え、開発反復サイクルが短く、スループット シナリオを好みます。
