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

1 はじめに

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

第1世代STARKsのコーディングビット幅は252bit、第2世代STARKsのコーディングビット幅は64bit、第3世代STARKsのコーディングビット幅は32bitですが、32bitのコーディングビット幅には依然として大量の無駄なスペースが存在します。それに比べて、バイナリ領域はビットを直接操作することを許可し、コーディングはコンパクトで効率的であり、無駄なスペースがありません。これが第4世代STARKsです。

Goldilocks、BabyBear、Mersenne31など最近数年に発見された有限体と比べて、二進法体の研究は1980年代にさかのぼります。現在、二進法体は暗号学に広く応用されており、典型的な例には次のものが含まれます：

• F28ドメインに基づくAdvanced Encryption Standard (AES)。

• Galoisメッセージ認証コード(GMAC)、F2128フィールドに基づいて；

• QRコード、F28に基づくリード・ソロモン符号を使用；

• 原初FRIおよびzk-STARKプロトコル、ならびにSHA-3ファイナルに進出したGrøstlハッシュ関数は、F28体に基づいており、再帰に非常に適したハッシュアルゴリズムです。

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

バイナリーフィールドに基づいて証明システムを構築する際、2つの実際的な問題があります。STARKsでトレースを表現する際に使用するフィールドのサイズは多項式の次数より大きくする必要があります。STARKsでMerkleツリーをコミットする際には、Reed-Solomonエンコードを行う必要があり、使用するフィールドのサイズはエンコード拡張後のサイズより大きくする必要があります。

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つの主要技術が含まれています。 まず第一に、バイナリフィールドのタワーに基づく算術がその計算の基礎を形成し、バイナリフィールドでの単純化された演算を実現できます。 次に、Biniusは、インタラクティブなOracle Proof Protocol(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 = X2 + Y 2 の簡略化ルールに従うからです。

! Bitlayer研究:Binius STARKsの原理分析と最適化思考

図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を参考にしており、多項式と多変数集合の正確性を検証するための一連のコアチェックメカニズムを採用しています。これらのコアチェックには、次のものが含まれます：

1. GateCheck：秘密証明ωと公開入力xが回路演算関係C(x,ω)=0を満たしているかどうかを検証し、回路が正しく動作することを保証します。

2. PermutationCheck:ブールハイパーキューブ上の2つの多変量多項式fとgの評価結果が順列関係であることを確認しますf(x) = 多項式変数間の配置の一貫性を確保するためのf(π(x))。

3. LookupCheck：多項式の評価が指定されたルックアップテーブルに存在するかどうかを検証します。すなわち、f(Bµ) ⊆ T(Bµ) であり、特定の値が指定された範囲内にあることを確認します。

4. MultisetCheck：2つの多変数集合が等しいかどうかをチェックします。すなわち、{(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H、複数の集合間の一貫性を保証します。

5. ProductCheck：有理多項式がブール超立方体上での評価がある声明された値∏x∈Hµ f(x) = sに等しいかどうかを検出し、多項式の積の正確性を確保します。

6. ZeroCheck：任意の点がブール超立方体上でゼロであるかどうかを検証する多変数多項式∏x∈Hµ f(x) = 0,∀x ∈ Bµを用いて、多項式のゼロ点の分布を確認します。

7. SumCheck：多変数多項式の和が声明された値∑x∈Hµ f(x) = sであるかどうかを検出します。多変数多項式の評価問題を単一変数多項式の評価に変換することで、検証者の計算複雑度を低減します。さらに、SumCheckはバッチ処理を許可し、ランダム数を導入することで、複数の和検証インスタンスに対するバッチ処理を構築します。

8. 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プロトコルにおいて、仮想多項式の構築と処理は重要な技術の一つであり、入力ハンドルや他の仮想多項式から派生した多項式を効果的に生成し操作することができます。以下は二つの重要な方法です：

• Packing：この方法は、辞書順で隣接する位置の小さい要素をより大きな要素にパッキングすることによって操作を最適化します。Pack演算子はサイズが2κのブロック操作を対象とし、それらをグループ化します。