ここで、「canonical」は、バイナリドメイン内の要素の一意で直接的な表現を指します。 たとえば、最も基本的なバイナリ ドメイン F2 では、任意の k ビット文字列を k ビット バイナリ ドメイン要素に直接マップできます。 これは、指定された位置内でそのような正規表現を提供できない素数フィールドとは対照的です。 32 ビットの素数フィールドは 32 ビット内に含めることができますが、すべての 32 ビット文字列がドメイン要素に一意に対応するわけではなく、バイナリ フィールドにはこの 1 対 1 のマッピングの便利さがあります。 プライムドメイン Fp では、一般的な縮小法には、バレット還元、モンゴメリー還元、およびメルセンヌ-31 や Goldilocks-64 などの特定の有限体に対する特別な還元法が含まれます。 バイナリ領域F2kでは、一般的に使用される削減方法には、AESの###などの特別な削減(、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. はじめに
楕円曲線に基づくSNARKsとは異なり、STARKsはハッシュに基づくSNARKsと見なすことができます。現在、STARKsの効率が低い主な理由の一つは、実際のプログラムにおける大多数の数値が小さいことです。例えば、forループのインデックス、ブール値、カウンターなどです。しかし、Merkleツリー証明の安全性を確保するために、Reed-Solomon符号化を使用してデータを拡張する際に、多くの追加の冗長値が全体の領域を占有します。元の値自体が非常に小さい場合でもです。この問題を解決するために、領域のサイズを小さくすることが重要な戦略となりました。
第1世代STARKsのエンコーディングビット幅は252bit、第2世代STARKsのエンコーディングビット幅は64bit、第3世代STARKsのエンコーディングビット幅は32bitですが、32bitエンコーディングビット幅には依然として大量の無駄なスペースが存在します。それに対して、バイナリフィールドはビットに直接操作を行うことを許可し、エンコーディングがコンパクトで効率的であり、無駄なスペースがありません。つまり、第4世代STARKsです。
Goldilocks、BabyBear、Mersenne31 などの近年の新しい研究で発見された有限体と比較して、二進数体の研究は1980年代に遡ることができます。現在、二進数体は暗号学に広く応用されており、典型的な例には次のものがあります:
高度暗号化標準(AES)、F28フィールドに基づく;
F2128ドメインに基づくガロアメッセージ認証コード(GMAC)。
QRコード、F28に基づくリード・ソロモン符号を使用;
元の FRI と zk-STARK プロトコル、および SHA-3 最終選考に進出した Grøstl ハッシュ関数は、F28 フィールドに基づいており、再帰に非常に適したハッシュアルゴリズムです。
小さな体を採用する場合、拡張体操作はセキュリティを確保するためにますます重要になります。Biniusが使用する二進数体は、そのセキュリティと実際の有用性を保証するために完全に拡張体に依存する必要があります。ほとんどのProver計算に関連する多項式は、拡張体に入る必要はなく、基本体の下で操作するだけで済むため、小さな体で高い効率を実現しています。しかし、ランダム点の検査とFRI計算は、必要なセキュリティを確保するために、より大きな拡張体に深く入る必要があります。
バイナリーフィールドに基づいて証明システムを構築する際、2つの実際的な問題があります。STARKsにおけるトレース表現を計算する際、使用するフィールドのサイズは多項式の次数よりも大きくする必要があります。また、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 lookup 引数の改良版を使用して、ルックアップ メカニズムに柔軟性と強力なセキュリティを提供します。 最後に、このプロトコルは、スモールフィールド多項式コミットメントスキーム)スモールフィールドPCS(を使用しているため、バイナリドメインに効率的な証明システムを実装し、通常、大規模ドメインに関連するオーバーヘッドを削減することができます。
) 2.1 有限体:二値体の塔に基づく算術
タワー型二進数体は、高速で検証可能な計算を実現するための重要な要素であり、主に2つの側面によるものです: 効率的な計算と効率的な算術化です。二進数体は本質的に非常に効率的な算術操作をサポートしており、性能要求に敏感な暗号学的アプリケーションに理想的な選択肢となっています。さらに、二進数体の構造は簡素化された算術化プロセスをサポートしており、二進数体上で実行される演算は、コンパクトで検証しやすい代数形式で表現できます。これらの特性に加え、タワー構造を通じてその階層的な特性を十分に活用できる能力により、二進数体は Binius のような拡張可能な証明システムに特に適しています。
ここで、「canonical」は、バイナリドメイン内の要素の一意で直接的な表現を指します。 たとえば、最も基本的なバイナリ ドメイン F2 では、任意の k ビット文字列を k ビット バイナリ ドメイン要素に直接マップできます。 これは、指定された位置内でそのような正規表現を提供できない素数フィールドとは対照的です。 32 ビットの素数フィールドは 32 ビット内に含めることができますが、すべての 32 ビット文字列がドメイン要素に一意に対応するわけではなく、バイナリ フィールドにはこの 1 対 1 のマッピングの便利さがあります。 プライムドメイン Fp では、一般的な縮小法には、バレット還元、モンゴメリー還元、およびメルセンヌ-31 や Goldilocks-64 などの特定の有限体に対する特別な還元法が含まれます。 バイナリ領域F2kでは、一般的に使用される削減方法には、AESの###などの特別な削減(、POLYVALの)などのモンゴメリ削減(、および再帰的削減) Tower(。 論文「Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations」では、バイナリ領域は加算と乗算の両方でキャリーを導入する必要がなく、バイナリ領域の二乗演算は )X + Y に従うため非常に効率的であると指摘しています (2 = X2 + Y 2です。
! [Bitlayer研究:Binius STARKsの原理分析と最適化思考])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
図1に示すように、128ビットの文字列: この文字列は、バイナリフィールドの文脈でさまざまな方法で解釈できます。128ビットのバイナリフィールド内のユニークな要素として見ることも、2つの64ビットタワーフィールド要素、4つの32ビットタワーフィールド要素、16の8ビットタワーフィールド要素、または128のF2フィールド要素として解釈することもできます。この表現の柔軟性は計算コストを必要とせず、単にビット文字列の型変換)typecast(であり、非常に興味深く有用な属性です。同時に、小さなフィールド要素は追加の計算コストなしにより大きなフィールド要素にパッケージ化できます。Biniusプロトコルは、この特性を利用して計算効率を向上させています。さらに、論文『On Efficient Inversion in Tower Fields of Characteristic Two』では、nビットのタワー型バイナリフィールド)がmビットの部分フィールド(に分解されて、乗算、平方、逆演算の計算複雑度が探討されています。
) 2.2 PIOP: バイナリドメイン用の HyperPlonk Product と PermutationCheck------ の適応バージョン
Binius プロトコルの PIOP 設計は HyperPlonk を参考にしており、多項式と多変数集合の正確性を検証するための一連のコアチェックメカニズムを採用しています。これらのコアチェックには次のものが含まれます:
GateCheck: 秘密証明ωと公開入力xが回路計算関係C###x,ω(=0を満たしているかを検証し、回路が正しく動作することを確認します。
PermutationCheck:ブールハイパーキューブ上の2つの多変量多項式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はによって