3,593 測定値

Binius がバイナリフィールドのタワーを使用して計算の複雑さを軽減する方法

に Sin7Y3m2024/09/13

長すぎる; 読むには

Ulvetanna (IRREDUCIBLE) チームは、バイナリフィールドのタワーに関する簡潔な議論というタイトルの研究論文でこの問題に取り組みました。彼らは、プロジェクト Binius: a Hardware-Optimized SNARK でこれを Rust で実装しました。Binius では、バイナリフィールドはフィールド拡張のタワーを使用して構築されます。

featured image - Binius がバイナリフィールドのタワーを使用して計算の複雑さを軽減する方法

計算の複雑さを軽減することは、常にブロックチェーン技術の主要な目標の 1 つです。これを実現するための効果的なアプローチの 1 つは、計算フィールドのビット幅を削減することです。たとえば、楕円曲線に基づく SNARK は、256 ビット以上のフィールドで算術演算を実行しますが、STARK は 64 ビットの Goldilocks フィールドから 31 ビットの Mersenne31 フィールドと BabyBear フィールドを使用するように進化しました。モジュラー演算中の素数の効率性を超えて、ビット幅が大幅に削減されたことで、Plonky2 は前身の Plonky よりも数百倍高速になりました。この軌跡をたどると、フィールド幅を 1、具体的には ${\mathbb{F}}_{2}$ に設定することは可能だろうかと疑問に思うかもしれません。Ulvetanna (IRREDUCIBLE) チームは、Succinct Arguments over Towers of Binary Fields というタイトルの研究論文でこの疑問に取り組みました。 [1] 、そして彼らのプロジェクトであるBinius: ハードウェア最適化SNARKでRustで実装しました。 [2] [3] 。

Biniusはリリース以来、ZK（ゼロ知識）コミュニティで大きな注目を集めています。LambdaClassチームはいくつかの技術的分析を提供してきました[4][5][6]、Vitalik Buterinはよりわかりやすい説明を提供しました。 [7]この記事では、バイナリフィールドのタワーに焦点を当てて、技術的観点と実装的観点の両方から Binius の基礎を探ります。

バイナリフィールド

Binius の実装はバイナリフィールドに基づいています。Binius では、バイナリフィールドはフィールド拡張のタワーを使用して構築されます。

最も単純なバイナリフィールドは ${{\mathbb{F}}{2}}$ で、2 つの要素 ${0,1}$ のみを含み、演算は 2 を法として実行されます。つまり、加算はビット単位の XOR に対応し、乗算はビット単位の AND に対応します。 $m(x) = x^{2} + x + 1$ over ${{\mathbb{F}}{2}}$選択すると、フィールド ${{\mathbb{F}}_{{2^{2}}}}$ を形成できます。ここで、要素は最大で次数 1 の多項式の剰余、 $r(x) = ax + b$ (with $a, b \in {0, 1}$ ) です。

体を拡大する方法の 1 つに既約多項式を使用して剰余を取る方法がありますが、Binius はより効率的なアプローチ、つまりタワー拡大の基礎として多重線型ラグランジュ多項式を使用する方法を採用しています。この方法では、各拡大体が前の拡大体の中にネストされる再帰的な体拡大が可能です。

タワー拡張の具体的な実装は次のとおりです。まず、 ${{\tau }{0}} = {{\mathbb{F}}{2}}$ 、次に、 ${{\tau }{1}} = \frac{{{\mathbb{F}}{2}}[{{x}{0}}]}{(x{0}^{2} + {{x}_{0}} + 1)}$ 、次に、 ${{\tau }{k}} = \frac{{{\mathbb{F}}{2}}[{{x}{k-1}}]}{(x{k-1}^{2} + {{x}{k-1}}{{x}{k-2}} + 1)}$.

体の拡張の構築プロセスから、拡張が次の関係を満たすことは明らかです: ${{\tau }{0}} \subset {{\tau }{1}} \subset {{\tau }{2}} \subset \cdots \subset {{\tau }{m}}$ 。 $k \ge 0$ の場合、体の拡張は次のように環の直接形式で表現することもできます: ${{\tau }{k}}={{{\mathbb{F}}{2}}[{{x}{0,}}\ldots ,{{x}{k-1}}]}/{\left( x_{0}^{2}+{{x}{0}}+1,\ldots ,x{k-1}^{2}+{{x}{k-2}}{{x}{k-1}}+1 \right)}$.

この実装に基づいて、次のようにさまざまな拡張機能を取得できます。

${{\tau }_{0}}=\left{ 0,1 \right}$
${{\tau }{1}}=\left{ 0+0{{x}{0}},1+0{{x}{0}},0+1{{x}{0}},1+1{{x}{0}} \right}$, or ${{\tau }{1}}=\left{ {{\tau }{0}},0+1{{x}{0}},1+1{{x}_{0}} \right}$
$${{\tau }{2}}=\left{ \begin{align} & 0+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},1+0{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},0+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}}, \ & 1+1{{x}{0}}+0{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}x \ \end{align} \right}$$, Or ${{\tau }{2}}=\left{ {{\tau }{1}},0+0{{x}{0}}+1{{x}{1}}+0{{x}{0}}{{x}{1}},\ldots ,1+1{{x}{0}}+1{{x}{1}}+1{{x}{0}}{{x}{1}} \right}$

拡張体に含まれる要素から ${{b}{0}}{{b}{1}}{{b}{2}}\ldots {{b}{{{2}^{k}}-1}}$ は、2 つの部分の合計、 ${{\tau }{k}}$ ${{b}{lo}} + {{x}{k-1}}{{b}{hi}}$ (where ${{b}{lo}}, {{b}{hi}} \in {{\tau }{k-1}}$) 。たとえば、 $1100101010001111 = 11001010 + 1000111 \times {{x}{3}}$, where $11001010, 10001111 \in {{\tau }{2}}$ 。

繰り返し分解することで、最終的に次のように表現できます。 $$1100101010001111=1+{{x}{0}}+{{x}{2}}+{{x}{2}}{{x}{1}}+{{x}{3}}+{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{2}}{{x}{3}}+{{x}{1}}{{x}{2}}{{x}{3}}+{{x}{0}}{{x}{1}}{{x}{2}}{{x}{3}}$$

さらに、 $k > 0$ の場合、 $x_{k}^{2} = {{x}{k}}{{x}{k-1}} + 1$ であるため、加算と乗算は2進拡張体で効率的に実装できます。