"canonical"は、バイナリーフィールドにおける要素の唯一かつ直接的な表現方法を指します。例えば、最も基本的なバイナリーフィールドF2では、任意のkビットの文字列は直接kビットのバイナリーフィールド要素にマッピングできます。これは素数フィールドとは異なり、素数フィールドは指定されたビット数内でこのような標準的な表現を提供することができません。32ビットの素数フィールドは32ビット内に含むことができますが、すべての32ビットの文字列が一意にフィールド要素に対応するわけではなく、バイナリーフィールドはこの一対一のマッピングの利便性を備えています。素数フィールドFpにおいて、一般的な還元方法にはBarrett還元、Montgomery還元、特定の有限体であるMersenne-31やGoldilocks-64などに対する特殊な還元方法が含まれます。バイナリーフィールドF2kにおいて、一般的な還元方法には特殊還元###（AESで使用される(）、Montgomery還元)（POLYVALで使用される(）、および再帰的還元)（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: バイナリ領域における効率的なSTARKsの新しいソリューションの探索
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ビット | 素数フィールド |
| 第2世代 | 64ビット | ゴルディロックス | | ジェネレーション3 | 32ビット | 素数フィールド | | 第4代 | 1bit | バイナリドメイン |
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においてトレース表現を計算する際に使用するフィールドのサイズは多項式の次数よりも大きくする必要があります；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 + Brakedown PCS + 二進制域。具体而言,Binius包括五项关键技术,以实现其高效性和安全性。首先,基于タワー型バイナリーフィールド)towers of binary fields(の算術化構成がその計算の基礎を形成し,バイナリーフィールド内で簡略化された演算を実現できる。次に,Biniusはそのインタラクティブオラクル証明プロトコル)PIOP(において,HyperPlonkの積と置換チェックを適応させ,変数とその置換間の安全で効率的な整合性チェックを保証している。第三に,プロトコルは新しい多項式シフト証明を導入し,小さなフィールド上での多項式関係の検証効率を最適化している。第四に,Biniusは改良版のLasso検索証明を採用し,検索メカニズムに柔軟性と強力な安全性を提供している。最後に,プロトコルは小さなフィールド多項式コミットメントスキーム)Small-Field PCS(を使用し,バイナリーフィールド上で効率的な証明システムを実現し,通常大きなフィールドに関連するオーバーヘッドを削減している。
) 2.1 有限体:二値体の塔に基づく算術
塔型バイナリーフィールドは、高速で検証可能な計算を実現するための鍵であり、主に2つの側面に起因しています: 効率的な計算と効率的な算術化。バイナリーフィールドは本質的に非常に効率的な算術操作をサポートしており、性能要求に敏感な暗号学的アプリケーションにとって理想的な選択肢です。さらに、バイナリーフィールドの構造は、バイナリーフィールド上で実行される演算をコンパクトで検証しやすい代数形式で表現できる簡素化された算術化プロセスをサポートしています。これらの特性に加え、塔構造を通じてその階層的な特性を十分に活用できる能力は、バイナリーフィールドをBiniusのようなスケーラブルな証明システムに特に適したものにしています。
"canonical"は、バイナリーフィールドにおける要素の唯一かつ直接的な表現方法を指します。例えば、最も基本的なバイナリーフィールドF2では、任意のkビットの文字列は直接kビットのバイナリーフィールド要素にマッピングできます。これは素数フィールドとは異なり、素数フィールドは指定されたビット数内でこのような標準的な表現を提供することができません。32ビットの素数フィールドは32ビット内に含むことができますが、すべての32ビットの文字列が一意にフィールド要素に対応するわけではなく、バイナリーフィールドはこの一対一のマッピングの利便性を備えています。素数フィールドFpにおいて、一般的な還元方法にはBarrett還元、Montgomery還元、特定の有限体であるMersenne-31やGoldilocks-64などに対する特殊な還元方法が含まれます。バイナリーフィールドF2kにおいて、一般的な還元方法には特殊還元###（AESで使用される(）、Montgomery還元)（POLYVALで使用される(）、および再帰的還元)（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: Tower バイナリードメイン
) 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プロトコルにおいて、仮想多項式の構築と処理は重要です。