Biniusはどのようにバイナリドメインを利用してSTARKsの効率を最適化するのか 4つの主要技術を解析する

2025-07-25 02:47:25

Binius STARKsの原理分析と最適化思考

1. はじめに

STARKsの効率が低下する主な理由は、実際のプログラムの大多数の数値が小さいことです。例えば、forループのインデックス、真偽値、カウンターなどです。しかし、Merkleツリー証明の安全性を確保するために、Reed-Solomon符号化を使用してデータを拡張すると、多くの追加の冗長値が全域を占めることになります。原始的な値自体が非常に小さい場合でもです。この問題を解決するためには、域のサイズを縮小することが重要な戦略となります。

表1に示すように、第1世代STARKsのエンコードビット幅は252ビット、第2世代STARKsのエンコードビット幅は64ビット、第3世代STARKsのエンコードビット幅は32ビットですが、32ビットのエンコードビット幅には依然として大量の無駄なスペースが存在します。これに対して、バイナリフィールドはビットに直接操作を行うことを許可し、エンコードはコンパクトで効率的であり、無駄なスペースがありません。すなわち、第4世代STARKsです。

|代数|コーディングビット幅|典型的な実装| |------|----------|----------| | ジェネレーション1 | 252ビット | スタークウェア |
| ジェネレーション2 | 64ビット | プロンキー2 | | ジェネレーション3 | 32ビット | プロンキー3 | | ジェネレーション4 | 1ビット | ビニウス |

Goldilocks、BabyBear、Mersenne31など近年の新しい研究で発見された有限体と比較して、二進法体の研究は1980年代まで遡ることができます。現在、二進法体は暗号学に広く応用されており、典型的な例としては:

高度暗号化標準(AES)、F2^8域に基づいています
Galoisメッセージ認証コード(GMAC)、F2^128域に基づいて
QRコード、F2^8に基づくリード・ソロモン符号を使用
元のFRIおよびzk-STARKプロトコル、さらにSHA-3ファイナルに進出したGrøstlハッシュ関数は、F2^8体に基づいており、再帰に非常に適したハッシュアルゴリズムです。

小さな体を使用する場合、拡張体操作は安全性を確保するためにますます重要になります。Biniusが使用する二進法体は、安全性と実用性を保証するために完全に拡張体に依存する必要があります。ほとんどのProver計算に関与する多項式は、拡張体に入る必要がなく、基本体の下で操作するだけで、小さな体で高効率を実現しています。しかし、ランダムポイントチェックとFRI計算は、要求される安全性を確保するために、より大きな拡張体に深く入る必要があります。

二進制領域に基づいて証明システムを構築する際には、2つの実際の問題があります：STARKsの計算トレース表現において、使用する領域のサイズは多項式の次数より大きくなければならない；STARKsのMerkleツリーのコミットメントにおいて、Reed-Solomon符号化を行う必要があり、使用する領域のサイズは符号化された拡張サイズより大きくなければなりません。

Biniusは、これら2つの問題をそれぞれ処理する革新的なソリューションを提案し、同じデータを2つの異なる方法で表現することによって実現しています。まず、単変数多項式の代わりに多変数(を使用し、多線形)多項式を用いて、"超立方体"(hypercubes)上での値を通じて全計算軌跡を表現します。次に、超立方体の各次元の長さが2であるため、STARKsのように標準のReed-Solomon拡張を行うことはできませんが、超立方体を方形(square)として扱い、その方形に基づいてReed-Solomon拡張を行うことができます。この方法は、安全性を確保しながら、エンコーディング効率と計算性能を大幅に向上させます。

2. 原理分析

現在ほとんどのSNARKsシステムの構築は通常、以下の二つの部分を含みます:

情報理論的多項式インタラクティブオラクル証明(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で使用される)、Montgomery還元(がPOLYVALで使用される)、再帰的還元(がTower)で使用されます。論文「Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations」では、二進法領域は加算および乗算において持ち上がりを導入する必要がなく、二進法領域の平方演算は非常に効率的であることが指摘されています。なぜなら、(X + Y )^2 = X^2 + 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ビットサブフィールド)に分解して乗算、平方および逆運算を行う計算複雑度について探求されています。

! タワーバイナリドメイン

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とプロトコル設計において多くの類似点があるが、Biniusは以下の3つの点で改善を行った。

ProductCheckの最適化: HyperPlonkでは、ProductCheckは分母Uが超立方体上で常に非ゼロであり、積が特定の値に等しいことを要求します; Biniusはこの値を1に特化させることで、このチェックプロセスを簡素化し、計算の複雑さを軽減します。
ゼロ除算の処理: HyperPlonkはゼロ除算のケースを十分に処理できず、超立方体上のUの非ゼロ性の問題を主張できませんでした; Biniusはこの問題を正しく処理し、分母がゼロの場合でもBiniusのProductCheckは処理を続けることができ、任意の積値への拡張を許可します。
列を跨いだPermutationCheck:HyperPlonkにはこの機能はありません;Biniusは複数の列間でPermutationCheckをサポートしており、これによりBiniusはより複雑な多項式の排列状況を処理できるようになります。

そのため、Biniusは既存のPIOPSumCheckメカニズムを改良することで、プロトコルの柔軟性と効率を向上させ、特により複雑な多変数多項式検証を処理する際に、より強力な機能サポートを提供しました。これらの改良は、HyperPlonkの限界を解決するだけでなく、将来のバイナリフィールドに基づく証明システムの基盤を築くものです。