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

1 はじめに

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

第1世代STARKsのエンコーディング幅は252ビット、第2世代STARKsのエンコーディング幅は64ビット、第3世代STARKsのエンコーディング幅は32ビットですが、32ビットのエンコーディング幅には依然として大量の無駄なスペースが存在します。それに対して、二進法の領域はビットを直接操作することを許可し、エンコーディングはコンパクトで効率的であり、無駄なスペースがありません。つまり、第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 + Brakedown PCS + 二進制域。具体而言,Binius包括五项关键技术,以实现其高效性和安全性。首先,基于タワー型二進制域(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で使用される特殊還元(、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の原理分析と最適化思考

( 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とプロトコル設計において多くの類似点があるにもかかわらず、以下の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κのブロック操作に対して動作し、それらを高次元の領域に組み合わせます。