ZKVM 回路の設計方法

カスタマイズされたゲート

zkvm 回路を設計するとき、多くのカスタム ゲートが決定されるため、多数のバイナリ セレクターが導入されます。

（フィールド）分割ゲートを例にとると、q、x、y の 3 つの要素間で q = x/y の関係が機能することを検証するゲートを設計する予定です。

便宜上、回路レベルでのフィールド除算操作は実行しません。代わりに、次の論理関係を検証して作成します。

x * inv_y = q

inv_y∗y=1 //y≠0であることを確認

2 つの要素の間には、対等な関係があります。したがって、次の Trace テーブルがあります。

列w_0,w_1,w_2,w_3に対して多項式w_0(x), w_1(x), w_2(x), w_3(x)を定義すると、除算演算に対応する行は次を満たす必要があります：

w_0(x) . w_3(x) - w_2(x) = 0 w_1(x) . w_3(x) - 1 = 0

上記の関係が対応する行で確実に満たされるようにするには、対応する分割を行って検証を制約するためのセレクターが必要です。

したがって、新しい列 s_{div} = {0,0,...1,...0}$ を導入しました。多項式 s_{div}(x) に変換すると、上記の式は次のようになります。

s_{div}(x) ⋅ (w_0(x) ⋅ w_3(x) - w_2(x)) = 0

s_{div}(x) ⋅ (w_1(x) ⋅ w_3(x) - 1) = 0

複合セレクター

上記の例から、新しいカスタマイズされたゲートを定義する場合、ゲートに対応するためにセレクタ列 s* を導入する必要があることがわかります。

対応するゲートの制約多項式を t∗(x) で表すと、最終的に次の制約が得られます。

s_{追加}(x) ⋅ t_{追加}(x) = 0

s_{div}(x) ⋅ t_{add}(x) = 0

s_{cube}(x) ⋅ t_{cube}(x) = 0

s_{sqrt}(x) ⋅ t_{sqrt}(x) = 0

...

証明者は、証明の生成中にすべての多項式に対するコミットメントを行う必要があるため、過剰な選択多項式が導入されると、証明者と検証者の作業負荷が増加します。

したがって、次の 2 つの条件を満たしながらセレクタ数を最適化する必要があります。

1. セレクター多項式の意味が失われることはありません。つまり、特定のゲートのみを使用できます。

   
   

2. 少ないセレクター多項式

「Plonky2: Fast Recursive Arguments with PLONK and FRI」( https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf ) に、最適化手法「Binary-Tree Based Selector」があります。 、選択多項式の数を log(k) に減らします。k はカスタマイズされたゲートの数です。

Halo2 の論文で、zcash チームは新しい最適化手法を提唱しました。これにより、(制約多項式 t∗(x) および制約多項式 max_degree に設定されたパラメーターと相関して) より少ない数の多項式を実現できる可能性があります。

簡単に理解できるように、簡単な例を見てみましょう (特定のアルゴリズムについては、セレクターの結合 - The halo2 Bookを参照してください)。

4 種類のカスタマイズされたゲートに対して 4 つのセレクター列を設定したことがわかりますが、これは前述のように必要なものではありません。

したがって、これは証明者と検証者の作業負荷を増大させます。ここで、次を満たす新しい列 q を定義します。

セレクター s_{add} に対してセット {s_{add}, s_{div}, s_{cube}, s_{sqrt}} (disjoint と呼ばれ、可能な行間に共通点がないようにするため) を定義すると、 、s_{div}、s_{cube}、s_{sqrt} 列 q の定義に基づいて、次のようになります。

ここで、列 q に基づいて新しいセレクター多項式を定義します。k 番目のセレクター多項式については、次のようになります。

たとえば、制約: s_add ⋅ t_add(x) = 0 の場合、次のように書き換えることができます。

上記の式は次のように展開できます。

設定

次に、真の値の数値が得られます。

元のセレクターと同じことを行うことがわかります。したがって、制約の場合:

s_{追加}(x) ⋅ t_{追加}(x) = 0

s_{div}(x) ⋅ t_{add}(x) = 0

s_{cube}(x) ⋅ t_{cube}(x) = 0

s_{sqrt}(x) ⋅ t_{sqrt}(x) = 0

...

制約を次のように書き換えることができます。

上記の制約については、多項式 q(x) へのコミットのみを行う必要があります。ただし、この方法では制約の度合いも大きくなったことに注意してください。

これまでのところ、上記の 2 点を達成しています。

1. セレクター多項式の意味が失われることはありません。つまり、特定のゲートのみを使用できます。

   
   

2. 少ないセレクター多項式

もちろん、プロトコルの制約付きの次数には制限があるため、結合に参加するセレクターの数は制限されます。つまり、単一の結合されたセレクターの数は、Degree の境界値と制約多項式 t の max_degree に依存します。 ∗(x)。

したがって、より多くの結合された列が必要ですが、とにかく、数は元の列よりもはるかに少なくなっています。

処理ケースとアルゴリズムの詳細については、セレクターの結合 - The halo2 Bookを参照してください。

参考文献

1. 「ハロー2ブック」、

   https://zcash.github.io/halo2/design/implementation/selector-combining.html

   
   

2. Polygon Zero チーム、「Plonky2: PLONK と FRI を使用した高速再帰引数」、 https ://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf、アクセス: 2022-02-06