ここで「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ビットの文字列：この文字列は、2進数の領域の文脈でさまざまな方法で解釈できます。それは、128ビットの2進数領域のユニークな要素と見なすことができるか、または2つの64ビットタワー領域の要素、4つの32ビットタワー領域の要素、16の8ビットタワー領域の要素、または128のF2領域の要素として解析できます。この表現の柔軟性は、(のビット文字列の型変換)によって、計算オーバーヘッドを必要とせず、非常に興味深く有用な特性です。同時に、小さな領域の要素は、追加の計算オーバーヘッドなしにより大きな領域の要素にパッケージ化できます。Biniusプロトコルは、この特性を利用して計算効率を向上させています。さらに、論文「On Efficient Inversion in Tower Fields of Characteristic Two」では、nビットタワー型2進数領域において(がmビットサブフィールド)に分解され、乗算、平方、逆算の計算複雑性が探討されています。
Binius:バイナリ領域における最適化されたSTARKs
Binius STARKsの原理とその最適化思考の解析
1 はじめに
STARKsの効率が低下する主な理由の一つは、実際のプログラムにおいて多数の数値が小さいことです。例えば、forループ内のインデックスや真偽値、カウンターなどです。しかし、Merkleツリー証明の安全性を確保するために、Reed-Solomon符号を用いてデータを拡張する際には、多くの追加の冗長値が全体の領域を占めることになります。たとえ元の値自体が非常に小さくてもです。この問題を解決するためには、領域のサイズを小さくすることが重要な戦略となります。
表1に示すように、第1世代STARKsのエンコードビット幅は252ビット、第2世代STARKsのエンコードビット幅は64ビット、第3世代STARKsのエンコードビット幅は32ビットですが、32ビットのエンコードビット幅には依然として大量の無駄なスペースが存在します。それに対して、2進数フィールドではビットに直接操作を行うことができ、エンコードはコンパクトで効率的であり、無駄なスペースはありません。すなわち、第4世代STARKsです。
表1:STARKsの進化経路
| 代数 | コーディングビット幅 | 代表的な実装 | |------|----------|------------| | ジェネレーション1 | 252ビット | スタークウェア | | ジェネレーション2 | 64ビット | プロンキー2 | | ジェネレーション3 | 32ビット | ベビーベア |
| ジェネレーション4 | 1ビット | ビニウス |
Goldilocks、BabyBear、Mersenne31など近年の新しい研究で発見された有限体と比較して、二進数体の研究は1980年代に遡ります。現在、二進数体は暗号学に広く応用されており、典型的な例には次のものがあります:
小さい体を使用する場合、拡張体操作はセキュリティを確保するためにますます重要になります。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はその効率性と安全性を実現するために5つの重要な技術を含んでいます。まず、タワー型バイナリーフィールド(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ビットの文字列：この文字列は、2進数の領域の文脈でさまざまな方法で解釈できます。それは、128ビットの2進数領域のユニークな要素と見なすことができるか、または2つの64ビットタワー領域の要素、4つの32ビットタワー領域の要素、16の8ビットタワー領域の要素、または128のF2領域の要素として解析できます。この表現の柔軟性は、(のビット文字列の型変換)によって、計算オーバーヘッドを必要とせず、非常に興味深く有用な特性です。同時に、小さな領域の要素は、追加の計算オーバーヘッドなしにより大きな領域の要素にパッケージ化できます。Biniusプロトコルは、この特性を利用して計算効率を向上させています。さらに、論文「On Efficient Inversion in Tower Fields of Characteristic Two」では、nビットタワー型2進数領域において(がmビットサブフィールド)に分解され、乗算、平方、逆算の計算複雑性が探討されています。
! Bitlayer研究:Binius STARKsの原理分析と最適化思考
( 2.2 PIOP: バイナリドメイン用の適応 HyperPlonk プロダクトと PermutationCheck ------
BiniusプロトコルのPIOP設計はHyperPlonkを参考にしており、多項式と多変数集合の正確性を検証するための一連のコアチェックメカニズムを採用しています。これらのコアチェックには次のものが含まれます:
GateCheck:ωと公開入力xが回路演算関係C)x,ω###=0を満たしているかどうかを検証し、回路が正しく動作することを確認します。
PermutationCheck: fとgの2つの多変数多項式がブール超立方体上で評価された結果が置換関係であるかどうかを検証します。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メカニズムを改良することにより、プロトコルの柔軟性と効率を向上させました。
! Bitlayer研究:Binius STARKsの原理分析と最適化思考
! Bitlayer研究:Binius STARKsの原理分析と最適化思考
! [ビトル