ここで「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世代STARKsのエンコーディング幅は252ビット、第2世代STARKsのエンコーディング幅は64ビット、第3世代STARKsのエンコーディング幅は32ビットですが、32ビットのエンコーディング幅にはまだ大量の無駄なスペースがあります。それに対して、二進数フィールドはビットを直接操作することを許可し、エンコーディングはコンパクトで効率的であり、無駄なスペースはありません。つまり、第4世代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においてトレース表現を計算する際に使用するフィールドのサイズは多項式の次数より大きくする必要があります；STARKsにおけるマークルツリーのコミットメントでは、リード-ソロモン符号化を行う必要があり、使用するフィールドのサイズは符号化後の拡張サイズより大きくする必要があります。
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つの主要技術が含まれています。 まず第一に、バイナリフィールドのタワーに基づく算術がその計算の基礎を形成し、バイナリフィールドでの単純化された演算を実現できます。 次に、Biniusは、インタラクティブなOracle Proof Protocol(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で使用されるもの）、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ビットのサブフィールドに分解可能）における乗算、平方、および逆運算の計算の複雑さを探討しています。
! 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の制限を解決するだけでなく、将来のバイナリフィールドに基づく証明システムの基盤を築くものです。
! Bitlayer研究:Binius STARKsの原理分析と最適化思考
2.3 PIOP：新しいマルチラインシフト引数------ブールハイパーキューブに適用
Biniusプロトコルでは、仮想多項式の構築と処理が主要な技術の一つであり、入力ハンドルや他の仮想多項式から派生した多項式を効果的に生成・操作することができます。以下は2つの重要な方法です：