Binius STARKsの原理とその最適化思考の解析

1 はじめに

STARKsの効率が低下する主な理由は、実際のプログラム内のほとんどの数値が小さいことです。例えば、forループ内のインデックス、真偽値、カウンターなどです。しかし、Merkleツリー証明の安全性を確保するために、Reed-Solomon符号化を使用してデータを拡張すると、多くの追加の冗長値が全体の領域を占有します。これは、元の値自体が非常に小さい場合でも同様です。この問題を解決するために、領域のサイズを小さくすることが重要な戦略となりました。

表1に示すように、第1世代STARKsのエンコードビット幅は252ビット、第2世代STARKsのエンコードビット幅は64ビット、第3世代STARKsのエンコードビット幅は32ビットですが、32ビットのエンコードビット幅には依然として大量の無駄なスペースが存在します。これに対して、二進数域はビットを直接操作することを許可し、エンコードはコンパクトで効率的であり、無駄なスペースがありません。つまり、第4世代STARKsです。

| 時間 | STARKs | コーディングビット幅 | |------|--------|----------| | 2018年度 | ジェネレーション1 | 252ビット | | 2021年度 | ジェネレーション2 | 64ビット | | 2022年度 | ジェネレーション3 | 32ビット | | 2023年度 | ジェネレーション4 | 1ビット |

表1:STARKsの進化経路

Goldilocks、BabyBear、Mersenne31など、近年の新しい研究で発見された有限体に比べて、二進法体の研究は1980年代に遡ることができます。現在、二進法体は暗号学に広く使用されており、典型的な例には次のものがあります:

• F28ドメインに基づくAdvanced Encryption Standard (AES)。

• Galoisメッセージ認証コード(GMAC)、F2128フィールドに基づく;

• QRコード、F28ベースのリード・ソロモン符号を使用;

• 原始FRIとzk-STARKプロトコル、およびSHA-3ファイナルに進出したGrøstlハッシュ関数。この関数はF28体に基づいており、再帰に非常に適したハッシュアルゴリズムです。

小さな体を採用する場合、拡張体の操作はセキュリティを確保するためにますます重要になります。そして、Biniusが使用する二進法体は、そのセキュリティと実際の可用性を保証するために拡張体に完全に依存する必要があります。ほとんどのProver計算に関与する多項式は、拡張体に入る必要はなく、基本体の下で操作するだけで、小さな体で高効率を実現します。しかし、ランダムポイントチェックとFRI計算は、必要なセキュリティを確保するために、より大きな拡張体に深く入る必要があります。

バイナリ領域に基づいて証明システムを構築する際に、2つの実際の問題があります。STARKsにおいてtrace表現を計算する際、使用する領域のサイズは多項式の階よりも大きくする必要があります。STARKsにおいてMerkleツリーのコミットを行う際、Reed-Solomon符号化を行う必要があり、使用する領域のサイズは符号化後のサイズよりも大きくする必要があります。

Biniusは、これら二つの問題をそれぞれ処理する革新的なソリューションを提案し、同じデータを二つの異なる方法で表現することを実現しました。まず、単変数多項式の代わりに多変数(多項式を使用し、その"超立方体")hypercubes(上での値を通じて全体の計算軌跡を表現します。次に、超立方体の各次元の長さが2であるため、STARKsのように標準のReed-Solomon拡張を行うことはできませんが、超立方体を四角)square(として捉え、その四角に基づいてReed-Solomon拡張を行うことができます。この方法は、安全性を確保しながら、コーディング効率と計算性能を大幅に向上させます。

2 原理分析

現在、大多数のSNARKsシステムの構築は通常、以下の2つの部分を含みます:

• 情報理論的多項式インタラクティブオラクル証明)Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(:PIOPは証明システムの核心として、入力された計算関係を検証可能な多項式等式に変換します。異なるPIOPプロトコルは検証者とのインタラクションを通じて、証明者が段階的に多項式を送信できるようにし、検証者は少数の多項式の評価結果をクエリすることで計算が正しいかどうかを検証できます。既存のPIOPプロトコルには、PLONK PIOP、Spartan PIOP、HyperPlonk PIOPなどがあり、それぞれ多項式表現の処理方法が異なり、SNARKシステム全体の性能と効率に影響を与えます。

• 多項式コミットメントスキーム)Polynomial Commitment Scheme, PCS(:多項式コミットメントスキームは、PIOPによって生成された多項式等式が成立しているかどうかを証明するために使用されます。PCSは暗号学的ツールの一種で、これにより証明者は特定の多項式にコミットし、後でその多項式の評価結果を検証できると同時に、多項式の他の情報を隠すことができます。一般的な多項式コミットメントスキームにはKZG、Bulletproofs、FRI)Fast Reed-Solomon IOPP(、Brakedownなどがあります。異なるPCSは異なる性能、安全性、および適用シーンを持っています。

具体的な要件に応じて、異なるPIOPとPCSを選択し、適切な有限体または楕円曲線と組み合わせることで、異なる属性を持つ証明システムを構築できます。例えば:

• Halo2: PLONK PIOP と Bulletproofs PCS の組み合わせで、Pasta 曲線に基づいています。Halo2 の設計は、スケーラビリティに重点を置き、ZCash プロトコルの trusted setup を排除しています。

• Plonky2: PLONK PIOPとFRI PCSを組み合わせ、Goldilocks域に基づいています。Plonky2は効率的な再帰を実現するために設計されています。これらのシステムを設計する際に選択されるPIOPとPCSは、使用される有限体または楕円曲線と一致する必要があり、システムの正確性、性能、安全性を確保します。これらの組み合わせの選択は、SNARKの証明サイズや検証効率に影響を与えるだけでなく、信頼できる設定なしで透明性を実現できるかどうか、再帰証明や集約証明などの拡張機能をサポートできるかどうかも決定します。

Binius:HyperPlonk PIOP +ブレーキダウンPCS +バイナリドメイン。 具体的には、Biniusには、その効率性と安全性を実現するための5つの主要技術が含まれています。 まず、バイナリfields)のタワーバイナリドメイン(towersに基づく演算がその計算の基礎を形成し、バイナリドメインでの簡略化された操作を実現できます。 次に、Biniusは、インタラクティブなOracleプルーフプロトコル)PIOP(で、HyperPlonk製品と順列チェックを適応させて、変数とその順列との間の安全で効率的な一貫性チェックを確保します。 第 3 に、このプロトコルでは、小さなドメインでのマルチリニア関係の検証効率を最適化するために、新しいマルチリニア シフト引数が導入されています。 第 4 に、Binius は Lasso ルックアップ引数の改良版を採用しており、ルックアップ メカニズムに柔軟性と強力なセキュリティを提供します。 最後に、このプロトコルは、スモールフィールド多項式コミットメントスキーム)スモールフィールドPCS(を使用しているため、バイナリドメインに効率的な証明システムを実装し、通常、大規模ドメインに関連するオーバーヘッドを削減することができます。

) 2.1 有限体:二値体の塔に基づく算術

タワー型二進数体は、高速かつ検証可能な計算を実現するための鍵であり、主に2つの側面に起因します: 効率的な計算と効率的な算術化です。二進数体は本質的に非常に効率的な算術操作をサポートしており、パフォーマンス要求が厳しい暗号学アプリケーションに最適な選択肢となります。さらに、二進数体の構造は簡素化された算術化プロセスをサポートしており、二進数体上で実行される演算はコンパクトで検証しやすい代数形式で表現できます。これらの特性に加え、タワー構造を通じて階層的な特性を十分に活用できることから、二進数体はBiniusのようなスケーラブルな証明システムに特に適しています。

その中で「canonical」は、バイナリフィールドにおける要素の唯一かつ直接的な表現方法を指します。例えば、最も基本的なバイナリフィールドF2においては、任意のkビットの文字列は直接kビットのバイナリフィールド要素にマッピングできます。これは素数フィールドとは異なり、素数フィールドは指定されたビット数内でこのような規範的な表現を提供できません。32ビットの素数フィールドは32ビットに収めることができますが、すべての32ビットの文字列が唯一のフィールド要素に対応するわけではなく、バイナリフィールドはこの一対一のマッピングの利便性を持っています。素数フィールドFpにおいて一般的な還元方法には、Barrett還元、Montgomery還元、Mersenne-31やGoldilocks-64など特定の有限フィールドに対する特別な還元方法が含まれます。バイナリフィールドF2kにおいて一般的な還元方法には、AESで使用される特別な還元###、POLYVALで使用されるMontgomery還元(、およびTower)のような再帰的還元(が含まれます。論文『Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations』によれば、バイナリフィールドでは加算および乗算において繰り上がりを導入する必要がなく、バイナリフィールドの平方運算は非常に効率的で、)X + Y (2 = X2 + Y 2の簡略化ルールに従います。

図1に示すように、128ビットの文字列：この文字列は、バイナリフィールドの文脈でさまざまな方法で解釈できます。それは128ビットのバイナリフィールドの中のユニークな要素と見なすことができるか、または2つの64ビットタワーフィールド要素、4つの32ビットタワーフィールド要素、16の8ビットタワーフィールド要素、または128のF2フィールド要素として解析できます。この表現の柔軟性は、計算オーバーヘッドを必要とせず、ビット文字列の型変換)typecast(に過ぎず、非常に興味深く有用な特性です。同時に、小さなフィールド要素は、追加の計算オーバーヘッドなしにより大きなフィールド要素にパッケージ化できます。Biniusプロトコルは、この特性を利用して計算効率を向上させています。さらに、論文『On Efficient Inversion in Tower Fields of Characteristic Two』は、nビットタワー型バイナリフィールドにおける)、mビットサブフィールド(への分解における乗算、平方、逆数演算の計算の複雑さを探ります。

! [タワーバイナリドメイン])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(

図 1: タワー型バイナリフィールド

) 2.2 PIOP: バイナリドメイン用の適応 HyperPlonk プロダクトと PermutationCheck ------

BiniusプロトコルのPIOP設計はHyperPlonkを参考にし、一連のコアチェックメカニズムを採用して、多項式と多変数集合の正確性を検証します。これらのコアチェックには以下が含まれます:

1. GateCheck: 検証秘密証明ωと公開入力xが回路演算関係C(x,ω)=0を満たしているかどうかを確認し、回路が正しく機能することを保証します。

2. PermutationCheck:ブールハイパーキューブ上の2つの多変量多項式fとgの評価結果が順列関係であることを確認しますf###x( = 多項式変数間の配置の一貫性を確保するためのf)π(x)(。

3. LookupCheck: 多項式の評価が指定されたルックアップテーブルにあるかどうかを検証します。すなわち、f(Bµ) ⊆ T)Bµ(であり、特定の値が指定された範囲内にあることを確認します。

4. MultisetCheck: 2つの多変数集合が等しいかどうかをチェックします。すなわち、{)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H、複数の集合間の一貫性を保証します。

5. ProductCheck:有理多項式がブール超立方体上での評価がある宣言された値∏x∈Hµ f)x( = sに等しいかどうかを検査し、多項式の積の正しさを確保します。

6. ZeroCheck: ブール超立方体上の任意の点が多変数多項式がゼロであるかどうかを検証する∏x∈Hµ f)x( = 0,∀x ∈ Bµ, 多項式の零点分布を保証するため。

7. SumCheck: 多変数多項式の和が宣言された値∑x∈Hµ f)x( = s であるかどうかを検査します。多変数多項式の評価問題を単変数多項式の評価に変換することで、検証者の計算の複雑さを低減します。さらに、SumCheckはバッチ処理を可能にし、ランダム数を導入することで、複数の和の検証インスタンスのバッチ処理を実現します。

8. BatchCheck:SumCheckに基づいて、複数の多変量多項式評価の正確性を検証し、プロトコールの効率を向上させます。

BiniusはHyperPlonkとプロトコル設計において多くの類似点があるにもかかわらず、以下の3つの点で改善を行っています:

• ProductCheckの最適化: HyperPlonkにおいて、ProductCheckは分母Uが超立方体上で常に非零であり、かつ積が特定の値に等しいことを要求する。Biniusはこの値を1に特化することにより、このチェックプロセスを簡素化し、計算の複雑さを低減した。

• ゼロ除算問題の処理: HyperPlonkはゼロ除算の状況を十分に処理できず、超立方体上のUの非ゼロ性を断言できなかった; Biniusはこの問題を正しく処理し、分母がゼロの場合でもBiniusのProductCheckは引き続き処理でき、任意の積の値への拡張を可能にした。

• 列を跨いだPermutationCheck: HyperPlonkにはこの機能がありません; Biniusは複数の列間でPermutationCheckをサポートしており、これによりBiniusはより複雑な多項式の排列状況を処理できるようになります。

したがって、Biniusは既存のPIOPSumCheckメカニズムの改善を通じて、プロトコルの柔軟性と効率を向上させ、特により複雑な多変数多項式検証を処理する際に、より強力な機能サポートを提供しました。これらの改善は、HyperPlonkの限界を解決するだけでなく、将来のバイナリフィールドに基づく証明システムの基盤を築くものです。

) 2.3 PIOP:新しいマルチラインシフト引数------ブールハイパーキューブに適用

Biniusプロトコルでは、仮想多項式の構築と処理が重要です。