"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世代STARKsのエンコーディングビット幅は252ビット、第2世代STARKsのエンコーディングビット幅は64ビット、第3世代STARKsのエンコーディングビット幅は32ビットですが、32ビットエンコーディングビット幅には依然として大量の無駄なスペースが存在します。それに対して、バイナリフィールドはビットに直接操作することを許可し、エンコーディングはコンパクトで効率的であり、無駄なスペースがありません。つまり、第4世代STARKsです。
Goldilocks、BabyBear、Mersenne31など、近年の新たな研究で発見された有限体と比べて、二進法の研究は1980年代に遡ることができます。現在、二進法は暗号学に広く応用されており、典型的な例には次のようなものがあります:
高度な暗号化標準(AES)、F28フィールドに基づく;
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 +ブレーキダウンPCS +バイナリドメイン。 具体的には、Biniusには、その効率性と安全性を実現するための5つの主要技術が含まれています。 まず、バイナリfields)のタワーバイナリドメイン(towersに基づく演算がその計算の基礎を形成し、バイナリドメインでの簡略化された操作を実現できます。 次に、Biniusは、インタラクティブなOracleプルーフプロトコル)PIOP(で、HyperPlonk製品と順列チェックを適応させて、変数とその順列との間の安全で効率的な一貫性チェックを確保します。 第 3 に、このプロトコルでは、小さなドメインでのマルチリニア関係の検証効率を最適化するために、新しいマルチリニア シフト引数が導入されています。 第 4 に、Binius は Lasso ルックアップ引数の改良版を採用しており、ルックアップ メカニズムに柔軟性と強力なセキュリティを提供します。 最後に、このプロトコルは、スモールフィールド多項式コミットメントスキーム)スモールフィールドPCS(を使用しているため、バイナリドメインに効率的な証明システムを実装し、通常、大規模ドメインに関連するオーバーヘッドを削減することができます。
) 2.1 有限体:二値体の塔に基づく算術
タワー型二進数体は、高速かつ検証可能な計算を実現するための鍵であり、主に二つの側面に起因しています: 効率的な計算と効率的な算術化です。二進数体は本質的に非常に効率的な算術操作をサポートしており、性能要求に敏感な暗号学的アプリケーションにとって理想的な選択となります。また、二進数体の構造は簡素化された算術化プロセスをサポートしており、すなわち二進数体上で実行される演算は、コンパクトで検証しやすい代数形式で表現できます。これらの特性に加えて、タワー構造を通じてその階層的な特性を十分に活用できることにより、二進数体は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:ブールハイパーキューブ上の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とプロトコル設計において多くの類似点があるが、以下の3つの点で改善を行った:
ProductCheckの最適化: HyperPlonkでは、ProductCheckは分母Uが超立方体上で常に非ゼロであること、かつ積が特定の値に等しいことを要求します; Biniusはその値を1に特化することで、このチェックプロセスを簡素化し、計算の複雑さを軽減しました。
ゼロ除算の問題の処理: HyperPlonkはゼロのケースを十分に処理できず、超立方体上でのUの非ゼロ問題を断言できませんでした; Biniusはこの問題を正しく処理しており、分母がゼロの場合でもBiniusのProductCheckは処理を続けることができ、任意の積の値に拡張することを許可します。
列を跨ぐPermutationCheck:HyperPlonkにはこの機能がありません;Biniusは複数の列間でPermutationCheckをサポートしており、これによりBiniusはより複雑な多項式の排列状況を処理できるようになります。
そのため、Biniusは既存のPIOPSumCheckメカニズムを改良することにより、プロトコルの柔軟性と効率を向上させ、特により複雑な多変数多項式検証を処理する際に、より強力な機能サポートを提供しました。これらの改良は、HyperPlonkの制限を解決するだけでなく、将来のバイナリフィールドに基づく証明システムの基礎を築くものです。
! [Bitlayer研究:Binius STARKsの原理分析と最適化思考])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP:新しいマルチラインシフト引数------真偽ハイパーキューブに適用されます
Biniusプロトコルにおいて、仮想多項式の構築と処理は重要な技術の1つであり、入力ハンドルや他の仮想多項式から派生した多項式を効果的に生成および操作することができます。以下は2つの重要な方法です。
*パッキング:方法は合格です