Sumcheck Protocol
polynomial IOPの文脈で登場する効率的な検証プロトコル
雰囲気理解のためにまずはこの動画をお勧めする
https://www.youtube.com/watch?v=XV62OB022tU
この記事では効率性と仕組みの理解にフォーカスし、Soundness & Correctnessの議論はこちらに譲る MLE:multiliner extention
multilinerとは各変数の次数が高々1である多項式のこと。
関数 $ f: \{0,1\}^{\ell} \to \mathbb{F} に対して、$ \mathbb{F} 上の$ \ell 変数多項式 g が f を拡張すると言うのは、すべての $ x \in \{0,1\}^{\ell} に対して f(x) = g(x) が成り立つときである。
そして $ f: \{0,1\}^{\ell} \to \mathbb{F} は、一意の多重線形拡張 (MLE) $ \tilde{f} を持つ。
例えば、左図のようなfを考える。(0,0)にfield element1がmapされ、(0,1)に2がmapされるといった具合
これは右図のようにMLEできる。
https://scrapbox.io/files/6718a1eecc0711e0caeabf8a.pnghttps://scrapbox.io/files/6718a1f6e9cbed0e3e173430.png
この時、x_1とx_2を用いて緑の部分だけはMLE$ \tilde{f}からcheckできる。
他の要素も検証したいのでnon-multilinearなf~(x_1,x_2)を導入することで検証できるようにする。
この時gは緑の部分も検証できる
https://scrapbox.io/files/6718a1ff5b65da9f1fa2d57b.pnghttps://scrapbox.io/files/6718a2059549f02ea2613a91.png
モチベーション
ランダムな点での検証が計算全体を完全に再計算するよりもはるかに少ないコストで正確性を高確率で保証したい
これを直接行う場合は多変数多項式の各変数に対して {0, 1} のすべての組み合わせで評価を行う必要があり、たとえば、$ \ell 個の変数があると、評価する項数は $ 2^\ell となり、検証コストが指数的に増加する
以下の工夫を持って効率化させることができる
1次多項式の評価に変換する：
Sum-Checkプロトコルでは、各ラウンドでの多項式は1次多項式として構成される。この1次多項式を評価するコストは、総和を直接計算する場合と比べて非常に低く、線形時間で処理できる。
再帰的なアプローチ：
各ラウンドで1つずつ変数を固定していき、ランダムな点での評価を進めることで、1つの変数についてランダムにチェックし次の変数に進む。これにより多項式全体の正しさを少ない回数のチェックで保証することが可能になる
仕組み
証明者はある多変数多項式gを各変数ごと分割してsumを計算し、その過程で得られた部分合計を検証者に提示する。
検証者は、証明者が提示した部分合計に対してランダムなポイントを選び、そのポイントに対する多項式の値が正しいかを確認する。このステップを全ての変数に対して行うことで、元々の多変数多項式の合計が検証できる。
最終的に得られる合計値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)
ここでは各変数がbooleanをとっているように、先述のMLEにおける検証プロトコルを使っている。
全体としては以下のようになっている。
https://scrapbox.io/files/6718ea581ec2322e93a81609.png
ぱっと見では分かりづらいので、例を持って示す
sample
例として$ g=(x,y,z)=2x^3+xz+yzというHypercubeが有限体上にある時このsumはH(=12)と等価になることを検証する
このように3変数からなるbinary hypercubeを応用したzerocheck protocolをhyperplonkでは採用している
まずは、最初の変数xについてみていく。
$ 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をベースとした単変数多項式(sum)$ sを$ s_0(x)= (8x^3)+2x+1とおく。
証明者はこの$ s_0を検証者に送り、検証者は$ s_0(0)+s_0(1)=12となることを確認する。
次にyのsumcheckを実行する。
検証者はランダムな値$ r_1を選択し、証明者に$ s_1におけるxの値として使わせる。ここでは$ r_1=2 とする。
ラウンド1ではランダムチェックは実行できないことに注意
証明者は以下の$ s_1を構築する
$ 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に関しては前のラウンドですでに証明者から送られている
$ b_2,,,b_{v-1}までのラウンドについてこの方式でsumcheckしていく
最終ラウンドvでは最後の変数まで進んで、多項式の全体の正しさを証明する。
検証者は g(r_0, r_1, r_2) という形で評価を行い、その結果が前のラウンドの s_2(r_3) と一致していることを確認する。
ここでの確認が成り立てば、検証者は前のラウンドからの全ての計算結果が正しかったことを確信できる
プロトコル全体をまとめると以下のようになる
ラウンド1:
x_1 に対して部分和 S_1(x_1) を計算。
検証者はランダムなサンプル r_1 を選び、次のラウンドに進む。
ラウンド2:
x_2 に対して部分和 S_2(x_2) を計算（ただし、前のラウンドで選ばれた r_1 を使用）。
検証者はランダムなサンプル r_2 を選び、次のラウンドに進む。
ラウンド3:
x_3 に対して部分和 S_3(x_3) を計算し、最終的な総和を確認。
参考
https://www.youtube.com/watch?v=gfy8rotcas4