フフロンクの概要

2019 年に導入された Plonk 証明システムは、回路多項式の完全なセットを抽象化します。その後、カスタム ゲートとルックアップ テーブルが Plonk システムに追加されます。これらの手法は本質的に、より多くの多項式を抽象化します。これらの多項式の表現能力はより強力であり、比較的複雑な計算プロセスを低位の多項式に抽象化できるため、多くの Plonk ゲートを節約できます。カスタム ゲート テクノロジとルックアップ テーブルの使用が増えるにつれて、Plonk システムではより多くの多項式とより多くの開点が表示されます。

まず、ブロックチェーン システムは検証の複雑さに非常に敏感です。一方、多項式コミットメント システムが異なると、多項式の数とオープン ポイントの数の検証の複雑さが異なります。したがって、多項式コミットメント システムを比較する必要があります。

(1) KZG コミットメントの検証の複雑さは、多項式の数と開点の数に線形関係があります。カスタム ゲートとルックアップ テーブルがない場合、Plonk システムは KZG コミットメントを使用して、2 つの双線形マップと 18 の多点演算の複雑さを検証します。

(2) Dan コミットメントの検証の複雑さは多項式の数にのみ関係し、開点の数には関係しません。カスタム ゲートとルックアップ テーブルがない場合、Plonk システムは KZG コミットメントを使用して、2 つの双線形マップと 16 の多点演算の複雑さを検証します。

KZG コミットメントと Dan コミットメントの場合、ルックアップ テーブルとカスタム ゲート手法を使用すると、複数ポイントの計算がさらに増加し​​ます。

(3) Fflonk を使用して複数の多項式を 1 つの多項式に結合し、その後 Dan コミットメントを使用します。Plonk システムでは、2 つの双線形マップと 5 つの多点演算のみが必要です。さらに、ルックアップ テーブルとカスタム ゲートを使用すると、検証の複雑さは増加せず、一定になります。したがって、Fflonk テクノロジーと Dan の取り組みを組み合わせることが、Plonk システムの最適なソリューションとなります。

使い方

Fflonk は、n 点 a1,…,an を開く m 多項式 f1(X),…,fm(X) を、m*n 点 b1,…,b_n*m を開く 1 つの多項式 F(X) と等価に変換します。

原理は次のとおりです。演算子を定義し、「FFT スタイル」で多項式をグループ化し、分解します。

これらは単射演算と逆演算であることに注意してください。つまり、どんなものに対しても、

ルートに関する表記

次の単純な補題が私たちのスキームの基礎です。

次に、n*m 点 b1,…,b_n*m を開く 1 つの多項式 F(X) を変換します。1 点 a を開く 1 つの多項式 L(X) に等価です。

原則は次のとおりです。

要約すると、最終的に、1 点 a を開く 1 つの多項式 L(X) に単純化されます。これは、KZG コミットメント システムを使用してコミットできます。

詳細については、元の論文とビデオをお読みください。ここでの議論も歓迎です。