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

1 はじめに

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

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

近年のGoldilocks、BabyBear、Mersenne31などの有限体に関する新しい研究と比較して、バイナリーフィールドの研究は1980年代に遡ります。現在、バイナリーフィールドは暗号学に広く利用されており、典型的な例には次のものがあります:

• F28ドメインに基づくAdvanced Encryption Standard (AES)
• Galoisメッセージ認証コード(GMAC)、F2128域に基づいて
• QRコード、F28に基づくリード・ソロモン符号を使用
• 原始FRIおよびzk-STARKプロトコル、そしてF28域に基づくSHA-3ファイナルに進出したGrøstlハッシュ関数は、再帰に非常に適したハッシュアルゴリズムです。

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

バイナリフィールドに基づいて証明システムを構築する際には、2つの実際的な問題があります：STARKsにおいてトレース表現を計算する際、使用するフィールドのサイズは多項式の階数よりも大きくなければなりません；STARKsにおけるマークルツリーのコミットメントでは、リード・ソロモン符号化を行う必要があり、使用するフィールドのサイズは符号化された拡張サイズよりも大きくなければなりません。

Biniusは、これら二つの問題をそれぞれ処理する革新的なソリューションを提案し、同じデータを二つの異なる方法で表現することを実現しました。まず、単一変数多項式の代わりに多変数(の具体的な多項式を使用し、"超立方体")のhypercubes(上でのその値を用いて全体の計算軌跡を表現します。次に、超立方体の各次元の長さが2であるため、STARKsのように標準のReed-Solomon拡張を行うことはできませんが、超立方体を方形)として扱い、その方形に基づいて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 有限体:二値体の塔に基づく算術

タワービナリーフィールドは、高速で検証可能な計算を実現するための鍵であり、主に二つの側面に起因しています：効率的な計算と効率的な算術化です。ビナリーフィールドは本質的に高度に効率的な算術操作をサポートしており、性能要件に敏感な暗号学的アプリケーションにとって理想的な選択肢となります。さらに、ビナリーフィールドの構造は簡略化された算術化プロセスをサポートしており、すなわちビナリーフィールド上で実行される演算はコンパクトで検証が容易な代数形式で表現できます。これらの特性に加え、タワー構造によってその階層的な特性を十分に活用できることから、ビナリーフィールドは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ビットの文字列：この文字列は、二進数体の文脈において様々な方法で解釈できます。それは128ビットの二進数体の中の一意の要素として見なされるか、または二つの64ビットタワー体の要素、四つの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: fとgという2つの多変数多項式がブール超立方体上で評価された結果が置換関係であるかを検証する。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の限界を解決するだけでなく、将来のバイナリフィールドに基づく証明システムの基盤を築くものです。

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

( 2.3 PIOP:新しいマルチラインシフト引数------ブールハイパーキューブに適用されます

Biniusプロトコルでは、仮想多項式の構築と処理が重要な技術の一つであり、入力ハンドルや他の仮想多項式から派生した多項式を効果的に生成し操作することができます。