Sumcheckプロトコルの概説

この記事は何？

sumcheckプロトコルを具体例で理解するための記事です、多項式がlow-degreeかどうかとか省いてます

今年のアドカレはsumcheck is all you need論文でも読むかと思ったけど、そもそもsumcheckプロトコルって何？という方のための記事

TL;DR

• sumcheckプロトコルとは？
  • n変数多項式gの全ブール値(0 or 1)上での和を効率的に証明・検証する方法
• How?
  • Prover(証明者)とVerifier(検証者)が、nラウンドやり取り(対話)し、ラウンドごとにVerifierが生成した乱数$r_i$で多項式を１変数ずつバインドしていき、最後に多項式$g(r_1, r_2, \ldots, r_n)$の値をVerifierが1回だけ計算する

Sumcheckプロトコルとは？

Proverが以下の主張をVerifierに証明する対話型証明プロトコル

$$H = \sum_{x \in \{0,1\}^n} g(x)$$

つまり、n変数多項式gの全ブール値(0 or 1)上での和を効率的に証明・検証する方法

Ref. https://dl.acm.org/doi/pdf/10.1145/146585.146605

この証明ができると何が嬉しいのか？
=> この形に帰着できれば色々証明できる（応用先の１つはSNARKの構成）
=> 例えば、GKRプロトコル（ref）

プロトコルの流れ（超ざっくり）

1. ラウンド$i$ ($i = 1, 2, \ldots, n$):

   • Proverは、変数$x_i$についての一変数多項式$s_i(X_i)$を送信する
   • Verifierは、前のラウンドとの整合性を確認する
   • Verifierは、ランダムな値$r_i$を選んでProverへ送信する

2. 最終検証:

   • Verifierは、全てのランダム値$(r_1, r_2, \ldots, r_n)$で多項式$g(r_1, r_2, \ldots, r_n)$を直接計算する
   • Verifierは、ラウンドnでProverから送られた多項式$s_n$から、$s_n(r_n)$を計算し、$g(r_1, r_2, \ldots, r_n)$と一致するか確認する

具体例で確認（3変数）

設定

以下の3変数多項式を考えます

$$g(x_1, x_2, x_3) = 2x_1x_2 + x_2x_3 + 3x_1$$

Proverは次の主張をVerifierに証明したいとします

$$H = \sum_{x \in \{0,1\}^3} g(x) = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \sum_{x_3 \in \{0,1\}} g(x_1, x_2, x_3)$$

あとで合ってるかの確認用に(この記事用に)、$H$の値を愚直に計算してみます

各項を計算：

• $g(0,0,0) = 0$
• $g(0,0,1) = 0$
• $g(0,1,0) = 0$
• $g(0,1,1) = 0 + 1 + 0 = 1$
• $g(1,0,0) = 0 + 0 + 3 = 3$
• $g(1,0,1) = 0 + 0 + 3 = 3$
• $g(1,1,0) = 2 + 0 + 3 = 5$
• $g(1,1,1) = 2 + 1 + 3 = 6$

したがって：

$$H = 0 + 0 + 0 + 1 + 3 + 3 + 5 + 6 = 18$$

sumcheckプロトコルではProverはVerifierに$H=18$だとどうやって証明するのでしょうか？
では、各ラウンド(3変数なのでラウンド3まで)を追っていきましょう

ラウンド1

Proverの計算：

多項式$g$に対して、$x_1$以外の変数に0,1を代入して和を取った、一変数多項式を計算する：

$$s_1(X_1) = \sum_{x_2 \in \{0,1\}} \sum_{x_3 \in \{0,1\}} g(X_1, x_2, x_3)$$

各項を展開：

• $x_2=0, x_3=0$: $g(X_1,0,0) = 3X_1$
• $x_2=0, x_3=1$: $g(X_1,0,1) = 3X_1$
• $x_2=1, x_3=0$: $g(X_1,1,0) = 2X_1 + 3X_1 = 5X_1$
• $x_2=1, x_3=1$: $g(X_1,1,1) = 2X_1 + 1 + 3X_1 = 5X_1 + 1$

したがって：

$$s_1(X_1) = 3X_1 + 3X_1 + 5X_1 + 5X_1 + 1 = 16X_1 + 1$$

ProverからVerifierへ$s_1(X_1)$を送信: $s_1(X_1) = 16X_1 + 1$

Verifierは以下を計算（自ら$X_1$へ0, 1を代入して足し合わせる）：

$$s_1(0) + s_1(1) = 1 + 17 = 18 (= H)$$
✓ （この記事用にあらかじめ計算しておいた）実際の値18と合致していますね

ポイント： Proverが渡してきた$s_1(X_1)$が、$x_1$以外の変数に0,1を代入して和を取って得られた正しい多項式であるならば、Verifierは$H=18$だと信じて良さそうです（$X_1$にはVerifierが自ら0, 1を代入して足し合わせたので）

では、次にVerifierが知りたいのは、本当に$s_1(X_1)$が、$x_1$以外の変数に0,1を代入して和を取って得られた多項式なのか？、です

Verifierは乱数$r_1 = 2$を振り、Proverへ送信し、ラウンド2に進みます

ラウンド2

Proverの計算：

多項式$g$に対して、$x_1$にはVerifierからもらった乱数$r_1=2$を代入し、$x_2$は変数のまま残し、$x_3$には0,1を代入してそれぞれ和を取った一変数多項式$s_2(X_2)$を計算する：

$$s_2(X_2) = \sum_{x_3 \in \{0,1\}} g(2, X_2, x_3)$$

各項を展開：

• $x_3=0$: $g(2,X_2,0) = 4X_2 + 6$
• $x_3=1$: $g(2,X_2,1) = 4X_2 + X_2 + 6 = 5X_2 + 6$

したがって：

$$s_2(X_2) = 4X_2 + 6 + 5X_2 + 6 = 9X_2 + 12$$

ProverからVerifierへ$s_2(X_2)$を送信: $s_2(X_2) = 9X_2 + 12$

Verifierは以下を検証（$s_1(r_1)$の計算と、$s_2(X_2)$へ0, 1を代入して足し合わせる）：

$$s_2(0) + s_2(1) = 12 + 21 = 33 \stackrel{?}{=} s_1(r_1) = 33$$

ポイント： Proverが渡してきた$s_2(X_2)$が、本当に$x_1$に乱数$r_1$を代入し、$x_2$を変数として、$x_3$に0,1を代入して和を取って得られた多項式であるならば、Verifierは前のラウンドでProverが送ってきた多項式$s_1(X_1)$が確かに正しく作られたと信じて良さそうです（$s_1(X_1)$が、$x_1$以外の変数に0,1を代入して和を取って得られた多項式と信じて良さそう、つまり$s_1(0) + s_1(1) = 1 + 17 = 18 = H$と信じて良さそう）

なぜか？： $s_2(X_2)$が正しく作られていると仮定すると、Verifierが確認した$s_2(0) + s_2(1)$は、$x_1​=r_1$, $x_2​ \in \{0,1\}$, $x_3​ \in \{0,1\}$での総和に等しい。これは、（正しく作られた場合の）$s_1(r_1)$の値そのものなので、もし不正な$s_1 \prime ​(X_1)$をProverが前ラウンドで送っていたら、ランダムな点$r_1$​で正しい値と一致する確率（$\text{Pr}[(s_2(0) + s_2(1) )=s_1 \prime ​(r_1)]$）は極めて低い（Verifierが作る乱数$r_1$が十分大きい有限体$\mathbb{F}$の要素として、$\frac{多項式の次数}{|\mathbb{F}|} \approx 0$の確率でしか一致しない）。

では、次にVerifierが知りたいのは、本当に$s_2(X_2)$が、$x_1$に乱数$r_1$を代入し、$x_2$を変数として、残りの変数に0,1を代入して和を取って得られた多項式なのか？、ですね

Verifierは乱数$r_2 = 3$を振り、Proverへ送信し、ラウンド3に進みます

ラウンド3：

Proverの計算：

多項式$g$に対して、$x_1=r_1=2, x_2=r_2=3$として、$x_3$についての一変数多項式を計算する：

$$s_3(X_3) = g(2, 3, X_3) = 2 \cdot 2 \cdot 3 + 3 \cdot X_3 + 3 \cdot 2 = 12 + 3X_3 + 6 = 3X_3 + 18$$

ProverからVerifierへ$s_3(X_3)$を送信: $s_3(X_3) = 3X_3 + 18$

Verifierは以下を検証（$s_2(r_2)$の計算と、$s_3(X_3)$へ0, 1を代入して足し合わせる）：

$$s_3(0) + s_3(1) = 18 + 21 = 39 \stackrel{?}{=} s_2(r_2) = 39$$

ポイント: $s_3(X_3)$が正しく作られているなら、$s_2(X_2)$も正しかったと信じて良さそう。連鎖的に$s_1(X_1)$​も正しく、結果として$H=18$という主張も正しいと信じて良さそう

なぜか？: $s_3(X_3)$​が正しければ、$s_3(0) + s_3(1)$は$x_1=r_1, x_2=r_2, x_3 \in \{0,1\}$での総和に等しく、これは、(正しく作られた場合の)$s_2(r_2)$の値と一致する。もし不正な$s_2 \prime ​ (X_2)$をProverが前ラウンドで送っていたら、ランダムな点$r_2$​で正しい値と一致する確率（$\text{Pr}[(s_3(0) + s_3(1) )=s_2 \prime ​(r_2)]$）はほぼゼロ

では、最後に、$s_3(X_3)$は正しく計算された多項式なのだろうか？
Verifierは乱数$r_3 = 5$を振り、最終検証に進む

最終検証

Verifierが以下２つを計算し、両者が一致するか確認する

$$s_3(r_3) = s_3(5) = 3 \cdot 5 + 18 = 33$$

$$g(r_1, r_2, r_3) = g(2, 3, 5) = 2 \cdot 2 \cdot 3 + 3 \cdot 5 + 3 \cdot 2 = 12 + 15 + 6 = 33$$ ✓ 両者が一致した

ポイント: ここで$g(r_1, r_2, r_3)$と$s_3(r_3)$が一致したということは、

• Proverが送ってきた多項式$s_3(X_3)$は、$x_1$へは$r_1$を代入し、$x_2$へは$r_2$を代入した、x_3についての正しい1変数多項式だったと信じてよさそう（d次元多項式同士は高々d点でしか交わらないので、ある点で値が一致したらおそらくそれらは同じ多項式だろう）
• ということは、今まで連鎖的に確認してきた$s_1, s_2, s_3$​もすべて正しく作られていたと信じてよさそう
• 結果として、最初の主張H=18が正しいと（高い確率で）信じてよさそう

すべてのラウンドで検証が成功したため、Verifierは主張$H=18$を受理する

この記事では対話型で具体例を説明したが、Fiat-Shamir変換で非対話型にできる
（つまり、適切なハッシュ関数などを使って、Prover側で乱数$r_i$を生成できる）

計算量とサイズ

$n$: 変数の数（例では$n=3$）
$d$: 各変数についての多項式の次数（例では$d=1$）

• Proverの計算量
  • 各ラウンドiで$2^{n-i}$回の多項式評価
  • ラウンドごとに半減する再帰的構造
• 通信量（証明サイズ）
  • $(d+1)⋅n$個の体要素（各ラウンドで次数dの一変数多項式を送信）
• Verifierの計算量
  • O(dn)回の体演算
• 総和の項数$N = 2^n$に対して、Verifierの時間と証明サイズは$O(\log N)$
  • 例：$N=2^{30}, d=2$
    • 256ビット体上で証明サイズは数KB

まとめ

１変数ずつ乱数でバインドしていき、最後に多項式gの値を1回だけ計算する

あと、Schwartz-Zippel Lemma大事

おまけ　GKRプロトコルの理解で大事なポイント

GKRプロトコルと呼ばれる、我々マグルでも計算委託ができる素晴らしい技術があるのだが、それにおいてsumcheckプロトコルの以下の性質が重要なので書いておく

sumcheckプロトコルでは、

• Verifierは、プロトコルの最後の最後で対象の多項式gの評価を１回だけ行う
• つまり、ラウンド中はProverから渡された多項式のs(0), s(1), s(r)を計算するだけ

GKRプロトコルの記事も書こうかなと思っているが、すでにわかりやすい記事があるので、こちらを読むとなぜsumcheckプロトコルで汎用的なVerifiable Computingが作れるかわかるだろう

記事はきっと書かないので、ざっくり言えば、証明したい計算fを加算ゲートと乗算ゲートからなる回路で表して、各層$i$の各ゲート値をエンコードした多項式を以下で表す(回路の層の深さを$d$として、入力層を$d$層目、中間層$d-1,\cdots 1$層目、出力層を$0$層目とする、気持ち悪い？)

\widetilde{W}_i(z) = \sum_{b,c \in \{0,1\}^{k_{i+1}}} \widetilde{\text{add}}_i(z,b,c) \left(\widetilde{W}_{i+1}(b) + \widetilde{W}_{i+1}(c)\right) + \widetilde{\text{mult}}_i(z,b,c) \left(\widetilde{W}_{i+1}(b) \cdot \widetilde{W}_{i+1}(c)\right)

• $\widetilde{W}_i$が、i層目の各ゲートの値がエンコードされた関数
• $\widetilde{\text{add}}_i(z,b,c)$は、ゲートzがゲートb,cの値を足し算した値であるなら1、それ以外は0となる関数
• $\widetilde{\text{mult}}_i(z,b,c) $は、ゲートzがゲートb,cの値を掛け算した値であるなら1、それ以外は0となる関数
• 上についてるチルダって何の意味かは別途記事などを参照（MLEとかはここでは触れません）

式からわかる通り、各層が正しく計算されているかの証明にsumcheckプロトコルをそれぞれ適用できる
（Proverは、入力$x$にこの回路$f$を適用した結果$\widetilde{W}_0(z)$は〇〇だ、と主張して、１回目のsumcheckプロトコルをスタートする）

sumcheckプロトコルでは、Verifierは、プロトコルの最後の最後で対象の多項式gの評価を１回だけ行うと先ほど言った

GKRプロトコルの場合、最後の評価には、$\widetilde{W}_{i+1}$に対するある乱数点での評価が必要だが、これはVerifierが評価できない（計算$f$を実行してないので）

したがって、Proverから教えてもらい、その教えてもらった値が正しいかどうかを次はチェックする（sumcheckに似ているな）

i回目のsumcheckでProverから教えてもらった最後の評価に必要な値 = \sum_{b,c \in \{0,1\}^{k_{i+2}}} \widetilde{\text{add}}_{i+1}(r,b,c) \left(\widetilde{W}_{i+2}(b) + \widetilde{W}_{i+2}(c)\right) + \widetilde{\text{mult}}_{i+1}(r,b,c) \left(\widetilde{W}_{i+2}(b) \cdot \widetilde{W}_{i+2}(c)\right)

sumcheckプロトコルを繰り返し適用していき、入力層までくれば、Verifierは入力$x$から$\widetilde{W}_d$が計算できるため、最終的に各層が正しく、計算結果$f(x)$がProverの主張する通りだとVerifierは確信できる（ゼロ知識性の付与、つまりVerifierには入力$x$を教えない条件のもとVerifiable Computingをどう実現するかは、きっといつか書きます）

参考

Thaler先生の資料が参考になります
https://people.cs.georgetown.edu/jthaler/sumcheck.pdf
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf