zkSNARKs - vol.2 ~さまざまなプロトコルについて(Pinocchio ProtocolとGroth16)~

Ethereum foundationが主催するPSE’s Summer Contribution Programに、この度参加しました。そこでZKPについて、どのような学びがあったかを書いていきます。全体感についてはこちらです。
https://zenn.dev/mameta29/articles/0cb3b96dadcf92

今回は Module4 で学んだ zkSNARKs についての2番目の記事です。全部で3部構成です。概要から数学的にどのような仕組みでゼロ知識証明を実現しているかまで体系的に記述していきたいと思います。正直このモジュールが一番学びごたえのある難しいものでした。

• 1つ目の記事

• 3つ目の記事

zkSNARKs とは

zkSNARKsは「Zero-Knowledge Succinct Non-Interactive Argument of Knowledge」の略で、特定の計算が正しく行われたことを証明する方法のことです。
主な特徴としては下記のようなものがあります。

• Zero-Knowledge（ゼロ知識）：証明者は、ある命題が真であることを証明するが、それ以外の情報（命題の内容など）を明らかにする必要はない。
• Succinct（簡潔）：証明は非常に小さいサイズで、迅速に検証可能。
• Non-Interactive（非対話型）：一度生成された証明は、証明者と検証者の間で対話なしに検証できる。

つまり、非対話的にゼロ知識証明を構築でき、ブロックチェーンでのトランザクションの秘匿化やイーサリアムのスケーリング問題のソリューションとして応用することができます。

このzkSNARKsの構築は複雑で以降下記のトピックにて2回に分けて説明します。この2番目の記事では「3. Pinocchio Protocolとは？」「4. Groth16」についてです。今回も主に「PSE’s Summer Contribution Program」に参加した人たちの発表内容を要約する形で書いていこうと思います。

1. Homomorphic Hiding(HH，準同型ハイディング)とは？
2. 算術回路からQAPへ
3. Pinocchio Protocolとは？
4. Groth16
5. PLONK

3. The Pinocchio Protocolとは？

The Pinocchio Protocolは、zkSNARKsを実現するための具体的な方法の一つとして実装されたものでその特徴を下記の順序で説明していきます。

1. KEAとは？
2. KEAをQAPに適用する
3. The Pinocchio Protocolで検証したいこと

1. KEAとは？

KEAはThe Pinocchio Protocolで使用される数学的な仮定です。具体的には、ある数Qが基数Pの指数kによって生成された場合（Q=P^k）、そのQを生成した者は指数kを「知っている」と見なされる、という仮定。KEAは、証明者が特定の計算の結果を知っていることを前提としており、この仮定はzkSNARKsのようなゼロ知識証明システムの設計において重要な役割を果たす。離散対数問題の計算上の困難さを利用し、特定の状況での知識や情報の存在を仮定するものといえる。

KEAでできること：上記の点PとQのiを係数とした線形結合であるRとSがあった時、またS=R^kが成り立つようなRとSをkを知らずに求めることができる。
→つまり線型結合を成り立たせる係数iを知っているということになる。

PSE発表者資料より

2. KEAをQAPに適用する

上述したKEAの仮定をQAPに適用するということをしていく。

PSE発表者資料より

この図にあるω1...ω6を先ほどの係数iとし、A1~A6の線型結合として考えていくことでKEAをQAPに適用していく。

PSE発表者資料より

A(x)において正しいR * k = Sを証明できれば係数となっているω1...ωmの値を知っていることの証明になる。そしてその係数が他のB(x), C(X)でもなり立つことが証明できたらよい。

PSE発表者資料より

3. The Pinocchio Protocolで検証したいこと

The Pinocchio Protocolで検証したいことは主に3つです。

PSE発表者資料より

こちらの図で示したA(x), B(x)そしてC(x)において下記が成り立つことです。

• A(x), B(x), C(x)がそれぞれ線形和かどうか調べる
• A(x), B(x), C(x)が同じ係数の線形和になっているか調べる
  (ここまでは上述2で記載したところです。)
• A(x) * B(x) - C(x) = H(x) * Z(x)
  (最後に使用したwitnessの値が正しいかどうかを検証)

4. Groth16

Groth16はThe Pinocchio Protocolと同様zk-SNARKsの実装の1つですが、The Pinocchio Protocolとの大きな違いは、証明(Proof)サイズを大幅に小さくしたところにあります。なのでブロックチェーンではよくこのプロトコルが使用されます。
下記の順序に従って説明していきます。(詳細な部分には踏み込まないのでご了承ください。)

1. Groth16の基本的な仕組み
2. Pinocchio との違い
3. 検証の準備
4. 検証

1. Groth16の基本的な仕組み

1. Trusted Setup

計算の有効性を検証するためのパラメータを生成します。詳細はここでは省きますが、zk-SNARKsを使用するために必要な公開パラメータを生成するプロセスのことをTrusted Setupといいます。この公開パラメータには、ランダム値や暗号学的なセキュリティに関する値が含まれる。Ceremonyというので複数人が参加可能で、ロジック的には信頼できる人が1人でもいれば、そのTrusted Setupは信頼できるものとなる。

2. 計算の多項式への変換

この仮定は前半で概要を説明したQAPやR1CSのこと。

3. 証明の生成（Prover）:

計算を実行し、その結果を多項式方程式として表現する。
Trusted Setupで生成したパラメータを用いて、この計算が正しいことを示す証明を生成する。この証明は、多項式の特定の点における評価と、それに対応する楕円曲線上の点を含む。

4. 証明の検証（Verifier）:

楕円曲線上のペアリング演算を使用して、証明が正しいことを検証する。
ペアリング演算は、証明が正しい計算の結果に基づいているかどうかを確認するために、Trusted Setupで生成したパラメータと証明(Proof)から得られる情報を組み合わせる。

2. Pinocchio との違い

Pinocchioプロトコルとの大きな違いを2点挙げる。まず1つ目の違いが証明(Proof)サイズがPinocchioと比べて小さいことである。

前述したPinocchioプロトコルを参照していただきたいが、8個の証明が必要になる。一方Groth16の方は3つで済む。

PSE発表者資料より

またもう1つの違いが検証時のペアリングの実行回数である。明らかにGroth16の方が少なくて済む。下記図参照。

PSE発表者資料より

3. 検証の準備

この記事では証明生成プロセスについては言及せず検証について記述していく。
Pinocchioプロトコルでは下記のように3つの工程が必要だったがそれを1つの式にまとめたというところがGroth16の特徴である。

Pinocchioプロトコル

• A(x), B(x), C(x)がそれぞれ線形和かどうか調べる
• A(x), B(x), C(x)が同じ係数の線形和になっているか調べる
• A(x) * B(x) - C(x) = H(x) * Z(x)

PSE発表者資料より

また、検証の時に必要となる変数や値については下記図のようなものがある。L_inputとL_auxはそれぞれ公開入力値とプライベートな値のことである。

PSE発表者資料より

4. 検証

式をそれぞれ左辺と右辺で検証していくと下記図のようになる。
左辺：

PSE発表者資料より

右辺：

PSE発表者資料より

変数を入れながら検証していくと最後には左辺と右辺の計算結果が等しくなることで検証することができる。

---

「5. PLONK」はこちらです。
https://zenn.dev/mameta29/articles/c129259be644d1

第1部で扱った「1. Homomorphic Hiding(HH，準同型ハイディング)とは？」と「2. 算術回路からQAPへ」はこちらです。
https://zenn.dev/mameta29/articles/1b4f99b17aefaa