ここで「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 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ビット | Babybear ドメイン | | 第4代 | 1bit | バイナリ領域 |
Goldilocks、BabyBear、Mersenne31など近年の新しい研究で発見された有限体と比較して、二進数体の研究は1980年代に遡ります。現在、二進数体は暗号学で広く使用されており、典型的な例には次のものがあります:
F28ドメインに基づくAdvanced Encryption Standard (AES)。
ガロワのメッセージ認証コード(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 +ブレーキダウン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の原理分析と最適化思考])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: バイナリドメイン用の適応 HyperPlonk プロダクトと PermutationCheck ------
BiniusプロトコルにおけるPIOPの設計はHyperPlonkを参考にしており、多項式と多変数集合の正確性を検証するための一連のコアチェックメカニズムを採用しています。これらのコアチェックには:
GateCheck: 秘密証明ωと公開入力xが回路演算関係C(x,ω)=0を満たしているかを検証し、回路が正しく動作することを確認します。
PermutationCheck:二つの多変数多項式fとgがブール超立方体上で評価された結果が置換関係であるかどうかを検証します。f###x( = f)π(x)(, 多項式の変数間の並びの一貫性を確保するために。
LookupCheck: 検証多項式の評価が指定されたルックアップテーブルに存在するか、つまり f(Bµ) ⊆ T)Bµ( の確保、特定の値が指定範囲内にあることを確認します。
MultisetCheck: 二つの多変数集合が等しいかどうかをチェックします。つまり、{)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プロトコルでは、仮想多