ここで「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ビットのサブフィールド)に分解して乗算、平方、逆数演算の計算複雑性について探求しています。
Binius:バイナリドメインSTARKの画期的な最適化
Binius STARKsの原理とその最適化思考の解析
1 はじめに
STARKsの効率が低下する主な理由は、実際のプログラムでのほとんどの数値が小さいことです。例えば、forループのインデックスや真偽値、カウンターなどです。しかし、Merkleツリー証明の安全性を確保するために、Reed-Solomon符号化を使用してデータを拡張する際、多くの追加の冗長値が全体の領域を占めてしまい、元の値自体が非常に小さくてもそうなります。この問題を解決するためには、領域のサイズを縮小することが重要な戦略となります。
表1に示すように、第1世代STARKsのエンコーディングビット幅は252ビット、第2世代STARKsのエンコーディングビット幅は64ビット、第3世代STARKsのエンコーディングビット幅は32ビットですが、32ビットのエンコーディングビット幅には依然として大量の無駄なスペースがあります。それに対して、二進数領域はビットを直接操作することを可能にし、エンコーディングはコンパクトで効率的であり、無駄なスペースがありません。つまり第4世代STARKsです。
表1:STARKsの進化経路
| 代数 | コーディングビット幅 | 例 | |------|----------|------| | 第1世代 | 252ビット | イーサリアムSTARKs | | ジェネレーション2 | 64ビット | プロンキー2 | | ジェネレーション3 | 32ビット | ベビーベア | | ジェネレーション4 | 1ビット | ビニウス |
Goldilocks、BabyBear、Mersenne31など、近年の新しい研究で発見された有限体と比較して、二進法体の研究は1980年代まで遡ることができます。現在、二進法体は暗号学に広く応用されており、典型的な例には以下が含まれます:
より小さな体を使用する場合、拡張体操作は安全性を確保するためにますます重要になります。Biniusが使用する二進数体は、その安全性と実用性を保証するために完全に拡張体に依存する必要があります。ほとんどのProver計算に関与する多項式は拡張体に入る必要はなく、基本体の下で操作するだけで、小さな体で高効率を実現しています。ただし、ランダムポイントチェックとFRI計算は、必要な安全性を確保するために、より大きな拡張体に深入りする必要があります。
バイナリフィールドに基づいて証明システムを構築する際に、2つの実際の問題が存在します：STARKsにおいてトレース表現を計算する際に使用されるフィールドのサイズは多項式の次数よりも大きくなければならない；STARKsにおいてメルクルツリーのコミットメントを行う際には、リード・ソロモン符号化を行う必要があり、使用されるフィールドのサイズは符号化拡張後のサイズよりも大きくなければなりません。
Biniusは、これらの2つの問題をそれぞれ処理する革新的なソリューションを提案し、同じデータを2つの異なる方法で表現することによって実現しています：まず、単変数多項式の代わりに多変量(具体的には多線形)多項式を使用し、"超立方体"(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ビットのサブフィールド)に分解して乗算、平方、逆数演算の計算複雑性について探求しています。
! Bitlayer研究:Binius STARKsの原理分析と最適化思考
( 2.2 PIOP: バイナリドメイン用の適応 HyperPlonk プロダクトと PermutationCheck ------
BiniusプロトコルのPIOP設計はHyperPlonkを参考にしており、多項式と多変数集合の正確性を検証するための一連のコアチェックメカニズムを採用しています。これらのコアチェックには次のものが含まれます:
GateCheck: 秘密証人ωと公開入力xが回路演算関係C)x,ω###=0を満たすかどうかを検証し、回路が正しく動作することを保証します。
PermutationCheck:ブールハイパーキューブ上の2つの多変量多項式fとgの評価結果が順列関係であることを確認しますf(x) = 多項式変数間の配置の一貫性を確保するためのf(π)x((。
LookupCheck: 多項式の評価が指定されたルックアップテーブルにあるかどうかを検証します。つまり、f)Bµ) ⊆ T(Bµ)であり、特定の値が指定された範囲内にあることを確認します。
MultisetCheck: 2つの多変数集合が等しいかどうかをチェックします。すなわち、{(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈Hであり、複数の集合間の一貫性を保証します。
ProductCheck: 有理多項式がブール超立方体上での評価がある声明された値∏x∈Hµ f(x) = sに等しいかどうかを検出し、多項式の積の正確性を保証します。
ZeroCheck: ブール超立方体上の任意の点がゼロであるかどうかを検証する多変数多項式 ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ を確認して、多項式のゼロ点分布を保証します。
SumCheck: 多変数多項式の総和が声明された値∑x∈Hµ f(x) = s であるかどうかを検出します。多変数多項式の評価問題を単変数多項式評価に変換することで、検証者の計算複雑度を低減します。さらに、SumCheckはランダム数を導入することで複数の和チェックインスタンスのバッチ処理を実現することも可能です。
BatchCheck:SumCheckに基づいて、複数の多変量多項式評価の正確性を検証し、プロトコールの効率を向上させます。
BiniusはHyperPlonkとプロトコル設計において多くの類似点がありますが、Biniusは以下の3つの点で改善を行っています:
ProductCheckの最適化: HyperPlonkにおいて、ProductCheckは分母Uが超立方体上で常に非零であること、かつ積が特定の値に等しいことを要求します。Biniusはこの値を1に特化することで、このチェックプロセスを簡素化し、計算の複雑さを低減しました。
ゼロ除算の処理: HyperPlonkはゼロ除算の状況を十分に処理できず、超立方体上のUの非ゼロ性に関する主張ができなくなりました; Biniusはこの問題を正しく処理し、分母がゼロであってもBiniusのProductCheckは処理を続け、任意の積の値に拡張できるようにしました。
列を跨ぐPermutationCheck: HyperPlonkにはこの機能がありません; Biniusは複数の列間でPermutationCheckをサポートしており、これによりBiniusはより複雑な多項式の排列状況を処理できるようになります。
したがって、Biniusは既存のPIOPSumCheckメカニズムを改善することによって、プロトコルの柔軟性と効率を向上させ、特により複雑な多変数多項式の検証を処理する際に、より強力な機能サポートを提供しました。これらの改善は、HyperPlonkの限界を解決するだけでなく、将来のバイナリーフィールドに基づく証明システムの基盤を築きました。
( 2.3 PIOP:新しいマルチラインシフト引数------ブールハイパーキューブに適用
Biniusプロトコルでは、仮想多項