Binius STARKsの革新:バイナリドメインの最適化による効率の向上

2025-07-27 09:20:40

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

1 はじめに

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

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

ゴルディロックス、ベイビー・ベア、マーズン31など、近年の新しい研究で発見された有限体と比べて、二進数体の研究は1980年代に遡ります。現在、二進数体は暗号学に広く応用されており、典型的な例は次のとおりです：

F28ドメインに基づくAdvanced Encryption Standard (AES)。
F2128ドメインに基づくガロアメッセージ認証コード(GMAC)。
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つの部分を含みます：

PIOP(Information-Theoretic Polynomial Interactive Oracle Proof)は、証明システムの中核としてIOP:P、入力の計算関係を検証可能な多項式に変換します。さまざまな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 の簡略化された規則に従うからです。

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

GateCheck：秘密証明ωと公開入力xが回路計算関係C(x,ω)=0を満たしているかどうかを検証し、回路が正しく動作することを確認します。
PermutationCheck:ブールハイパーキューブ上の2つの多変量多項式fとgの評価結果が順列関係であることを確認しますf(x) = 多項式変数間の配置の一貫性を確保するためのf(π(x))。
LookupCheck：多項式の評価が指定されたルックアップテーブルに存在するかどうかを検証します。すなわち、f(Bµ) ⊆ T(Bµ)、特定の値が指定された範囲内にあることを確認します。
MultisetCheck：2つのマルチバリエット集合が等しいかどうかをチェックします。つまり、{(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の限界を解決するだけでなく、将来の二進法領域に基づく証明システムの基盤を築くものです。