Binius STARKsの原理解析:バイナリドメイン最適化と性能改善

2025-08-13 02:00:48

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

1 はじめに

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

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

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

高度な暗号化標準(AES)、F28フィールドに基づく；
Galoisメッセージ認証コード(GMAC)、F2128フィールドに基づいて；
QRコード、F28ベースのリード・ソロモン符号を使用；
原始FRIとzk-STARKプロトコル、そしてSHA-3ファイナルに進出したGrøstlハッシュ関数は、F28域に基づいており、再帰に非常に適したハッシュアルゴリズムです。

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

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

Biniusは、これら二つの問題をそれぞれ処理する革新的な解決策を提案し、同じデータを二つの異なる方法で表現することによって実現しています。まず、単変数多項式の代わりに多変数（具体的には多線形）多項式を使用し、その値を「超立方体」（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 有限体:二値体の塔に基づく算術

タワー型バイナリーフィールドは、迅速な検証可能計算を実現するための鍵であり、主に二つの側面に起因します：効率的な計算と効率的な算術化です。バイナリーフィールドは本質的に非常に効率的な算術操作をサポートしており、性能要求に敏感な暗号学的アプリケーションにとって理想的な選択肢となっています。さらに、バイナリーフィールドの構造は、簡素化された算術化プロセスをサポートしており、つまりバイナリーフィールド上で実行される演算は、コンパクトで検証が容易な代数形式で表現できます。これらの特性に加え、タワー構造を通じてその階層的な特性を十分に活用できるため、バイナリーフィールドは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ビットのバイナリフィールドにおけるユニークな要素と見なすことができるほか、2つの64ビットのタワーフィールド要素、4つの32ビットのタワーフィールド要素、16の8ビットのタワーフィールド要素、または128のF2フィールド要素として解析されることもあります。このような表現の柔軟性は、計算オーバーヘッドを必要とせず、単にビット文字列の型変換（typecast）であり、非常に興味深く有用な特性です。同時に、小さなフィールド要素は、追加の計算オーバーヘッドなしに、より大きなフィールド要素にパッケージ化することができます。Biniusプロトコルはこの特性を利用して計算効率を向上させています。さらに、論文「二項特性のタワーフィールドにおける効率的な逆演算について」では、nビットのタワー型バイナリフィールド（mビットのサブフィールドに分解可能）における乗算、平方、逆演算の計算の複雑性について探求しています。

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

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とプロトコル設計において多くの共通点があるにもかかわらず、以下の3つの点で改善を行っています：

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

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