Develop with pleasure!

福岡でCloudとかBlockchainとか。

Sumcheckプロトコル

Cryptography

今回は、zk-SNARKs/STARKsなどゼロ知識証明系のプロトコルでよく登場するSumcheckプロトコルについて。

Sumcheckプロトコルは1992年に発表された多変数多項式を利用したプロトコル。多変数多項式は複数の変数で構成される多項式で、例えば2つの変数xとyで構成される2変数多項式であれば {g(x, y) = 3x^{2}y + 2xy + 5y^{2} + 1}のような式で、3変数多項式であれば {g(x, y, z) = 2x^{2}yz + 3xy^{2}z^{2} + 5z + 7}だったり。n個の変数で構成されるn変数多項式を {g(x_1, ..., x_n)}と表記する。

Sumcheckは、各変数に0か1を代入して多項式を評価し、すべての変数の組み合わせに対して評価した値の合計を効率的に検証するプロトコル。検証者は実際にすべての組み合わせで多項式を評価することなく、その合計値が正しいことを検証できるというもの。どうして変数に代入する値は0と1なのかといううと（実際には任意のセットを用いることもできるが）、多くの暗号や計算問題はブール値で定式化でき、計算も簡単になるため。

証明プロセス

証明者があるn変数多項式 {g(x_1, ..., x_n)}のすべての変数の組み合わせの総和がHであることを証明したい場合（検証者は多項式については既知）、

① 証明者は、まず {x_1}について和を計算する1変数多項式 {g_1(X_1)}を送信する。これは、たとえばn = 3、 {g(x_1, x_2, x_3) = x_1x_2 + x_2x_3 + x_1x_3}という多項式の場合、 {x_2}と {x_3}のすべての組み合わせに対して多項式を評価し、

  • {g(X_1, 0, 0) = X_1 \cdot 0 + 0 \cdot 0 + X_1 \cdot 0 = 0}
  • {g(X_1, 0, 1) = X_1 \cdot 0 + 0 \cdot 1 + X_1 \cdot 1 = X_1}
  • {g(X_1, 1, 0) = X_1 \cdot 1 + 1 \cdot 0 + X_1 \cdot 0 = X_1}
  • {g(X_1, 1, 1) = X_1 \cdot 1 + 1 \cdot 1 + X_1 \cdot 1 = 2X_1 + 1}

その和 {g_1(X_1) = 0 + X_1 + X_1 + 2X_1 + 1 = 4X_1 + 1}を求めることを意味する。

② 証明者から1変数多項式 {g_1(X_1)}を受け取った検証者は、その多項式を評価してその和を計算する。つまり {g_1(0) + g_1(1)}を計算し、それが証明者が主張するn変数多項式の和Hと等しいか検証する。上記の例だと {g(x_1, x_2, x_3)}のすべての組み合わせの和は、

  • {g(0, 0, 0) = 0 \cdot 0 + 0 \cdot 0 + 0 \cdot 0 = 0}
  • {g(0, 0, 1) = 0 \cdot 0 + 0 \cdot 1 + 0 \cdot 1 = 0}
  • {g(0, 1, 0) = 0 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 = 0}
  • {g(0, 1, 1) = 0 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 = 1}
  • {g(1, 0, 0) = 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 = 0}
  • {g(1, 0, 1) = 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 = 1}
  • {g(1, 1, 0) = 1 \cdot 1 + 1 \cdot 0 + 1 \cdot 0 = 1}
  • {g(1, 1, 1) = 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 = 3}

で合計すると6。これに対し、 {g_1(0) + g_1(1)}は {g_1(0) + g_1(1) = (4 \cdot 0 + 1) + (4 \cdot 1 + 1) = 6}となり一致する。結果が一致するということは、 {g_1(X_1)}が実際に {x_1}について和を取った多項式であることが、高い確率で確信できる。

③ 次に検証者は有限体 {\mathbb F}からランダムな値 {r_1 \in \mathbb F}を選択し、それを証明者に送信する。

④ 証明者は、次に {g_2(X_2)}を計算するが、この時 {x_1}には0と1ではなく検証者から受け取った {r_1}を代入する。そして計算結果の {g_2(X_2)}を検証者に送信する。たとえば、 {r_1 = 3}だとすると上記の例は、

  • {g(3, X_2, 0) = 3 \cdot X_2 + X_2 \cdot 0 + 3 \cdot 0 = 3X_2}
  • {g(3, X_2, 1) = 3\cdot X_2 + X_2 \cdot 1 + 3 \cdot 1 = 4X_2 + 3}

で、その和 {g_2(X_2) = 7X_2 + 3}を検証者に送信する。

⑤ 検証者は、 {g_1(r_1) = g_2(0) + g_2(1)}が成立するか検証する。上記の例では {g_1(r_1) = g_1(3) = 4 \cdot 3 + 1 = 13}と {g_2(0) + g_2(1) = (7 \cdot 0 + 3) + (7 \cdot 1 + 3) = 13}が一致するかどうかを検証する。

⑥ 検証が成功したら、検証者は再度 {r_2 \in \mathbb F}を選択し、証明者に送信する。

⑦ 証明者は次に {g_3(X_3)}を計算するが、 {x_1, x_2}はそれぞれ {r_1, r_2}を用いる。 {r_2 = 5}とした場合、 {g_3(X_3) = g(3, 5, X_3) = 3 \cdot 5 + 5 \cdot X_3 + 3 \cdot X_3 =8X_3 + 15}。

これを合計n回繰り返す。

⑧ 最終的に検証者は {r_n \in \mathbb F}を選択し、 {g_n(r_n) = g(r_1, ..., r_n)}が成立するか検証する。

このようにSumcheckプロトコルは、証明者は各ステップで1つだけ変数を残して他の変数の組み合わせに対して和をとる1変数多項式を送信し、それを検証者に検証させ、最終的にn個の変数を用いて元の多項式を評価させることで、 {O(2^{n})}の計算ではなくO(n)の計算で多項式の評価値の総和を検証できるようにしている。

Fiat-Shamir変換

上記は証明者と検証者の対話型のプロトコルになっているけど、Fiat-Shamir変換で非対話型にすることができる。証明者が最初の多項式 {g_1(X_1)}を計算したら、 {g_1}のハッシュ値を {r_1 = H(g_1)}とし、その次は {r_2 = H(g_1, g_2, r_1)}と計算していくことで非対話型にできる。

zk-SNARKs/STARKsなどでは、ある多項式の総和が0になることを検証する仕組みとしてこのSumcheckプロトコルを利用してるみたい。