Sum-check Protocol

Sum-check ProtocolはzkVMにおけるexecution traceなどで使用されるMultilinear IOPsです

この記事では効率性と仕組みの理解にフォーカスしますので、Soundness & Correctnessの議論はこちらを参照ください。

モチベーション

ある多変数多項式gの総和が

H := ∑ _{b_1∈\{0,1\}} ∑ _{b_2∈\{0,1\}} . . . ∑_{ b_v∈\{0,1\}} g(b_1, . . . , b_v)

となることを検証したい場合があります。しかしこのような計算は検証者にとって負担となります。

これを直接行う場合は多変数多項式の各変数に対して {0, 1} のすべての組み合わせで評価を行う必要があり、たとえば$\ell$個の変数があると、評価する項数は [$ 2^\ell ]l となり、検証コストが指数的に増加します。

以下2点のテクニックを使うことで検証効率を上げることができます。

多変数多項式を複数の1次多項式に分割します。この1次多項式をの総和を計算するコストは、多変数多項式の総和を直接計算する場合に比べて非常に低く、線形時間で処理できます。

つまり変数ごとに評価ラウンドを設け、各ラウンドで部分合計を検証することができれば元の多変数多項式の総和を検証したことになるというアイデアです。

検証者は証明者が提示した部分合計に対してランダムなポイントを選び、そのポイントに対する多項式の値が正しいかを確認します。

各ラウンドで1つずつ変数を固定してランダムな点での評価を進めることで、1つの変数についてランダムにチェックし次の変数のラウンドに進みます。これにより多項式全体の正しさを少ない回数のチェックで保証することが可能になります。

最終的に得られる合計値Hは以下のように表現できます。

H := \sum_{b_1 \in {0,1}} \sum_{b_2 \in {0,1}} \dots \sum_{b_\ell \in {0,1}} g(b_1, \dots)

全体としては以下のようになっている。

ぱっと見では分かりづらいので、例を持って示します。

g=(x,y,z)=2x^3+xz+yzという3変数からなるHypercubeが有限体上にあり、この総和がH(=12)と等価になることを検証する場合を考えましょう。

まず最初の変数xについてみていきます。x以外の変数y,zがとり得る値の組み合わせは4パターンあるのでそれぞれ計算していくと以下のようになります。

g(x,0,0)+g(x,0,1)+g(x,1,0)+g(x,1,1)

= (2x^3)+(2x^3+x)+(2x^3)+(2x^3+x+1)

= (8x^3)+2x+1

ここでgをベースとした単変数多項式[$ s]を[$ s_0(x)= (8x^3)+2x+1]とおきます。

証明者はこの[$ s_0]を検証者に送り、検証者は[$ s_0(0)+s_0(1)=12]となることを確認します。

[$ b_2,,,b_{v-1}]までの1変数多項式をランダムな点の評価で検証していきます。

この例ではyのsum-checkについて見ていきます。

xの時とは違い、まず検証者はランダムな値[$ r_1]を選択して証明者に送ります。ここでは[$ r_1=2] としましょう。

証明者はxの時と同様に以下のs_1を構築します。ここで先ほど検証者から受け取ったランダムな値r_1=2を[$ s_1]におけるxの値として使っている点がポイントです。

s_1(y)=g(2,y,0)+g(2,y,1)=16+(16+2+y)=34+y

そしてこの[$ s_1]を検証者に送り検証者は[$ r_1]とyで以下の式が成り立つことを検証します。

s_1(0)+s_1(1)=s_0(r_1)

右辺の[$ s_0]に関しては前のラウンドですでに証明者から送られています。

このように前のラウンドの多項式を次のラウンドでもランダムポイントの評価に再利用することで効率的に検証ができます。ラウンド1ではランダムチェックは実行できないことに注意です。

最終ラウンドvでは最後の変数まで進んでおり、多項式全体の正しさを証明する必要が出てきます。

検証者は g(r_0, r_1, r_2) という形で評価を行い、その結果が前のラウンドの s_2(r_3) と一致していることを確認します。これが成り立てば検証者は前のラウンドからの全ての計算結果が正しかったことを確信できます。

Last updated 9 months ago