zk-SNARKsの理論

ゼロ知識証明

ゼロ知識証明とは証明者が検証者に対して、ある情報が正しいことを、それが正しいこと以外の情報を明らかにせずに証明できる手法のことです。

例えば、運転免許証や保険証を提示して相手に自分の身元を明らかにしたい時に、免許証に含まれる住所や、生年月日等の個人情報を隠蔽しつつ、持っているその免許証が本当に自分のものあり、正しい情報が含まれていることを証明する場合にゼロ知識証明が使われます。

ゼロ知識証明はいくつかの性質を持ちます。

ゼロ知識証明が持つ3つの性質

• 完全性（Completeness）
  • 証明者の主張が真であるならば、検証者は真であることが必ずわかること。
• 健全性（Soundness）
  • 証明者の主張が偽であれば、検証者はかなり高い確率でそれが偽であること見抜けること。
• ゼロ知識証明（Zero Knowledge）
  • あらゆる場合において、検証者が証明者から何らかの知識（情報）を盗もうとしても、証明者の主張が真であること以上の知識は得られない

対話型と非対話型のゼロ知識証明

ゼロ知識証明には対話型と非対話型の２通りの構築方法があります。

名前の通り対話型は有名な洞窟の例のように証明者と検証者がやりとりを繰り返し、証明者が本当に正しい情報を持っているかを確率的に検証する方です。

一方、非対話型のゼロ知識証明は証明者と検証者はやりとりをせずに証明することが可能です。対話を行う代わりに証明者と検証者の間に第三者を置き、CRSと呼ばれる事前に公開される情報を証明者と検証者に送ります。証明者はそのCRSを用いて正しい情報を持っているという証明を生成し、それを検証者に一回だけ送ります。受け取った検証者はそれを検証するだけで非対話なゼロ知識証明が実現できます。事前にCRSを生成することを一般的に信頼されたセットアップといい、第三者は証明者、検証者にとって信頼される存在となります。

zk-SNARKsとは

zk-SNARKsとは非対話なゼロ知識証明を構築し、ブロックチェーンでのトランザクションの秘匿化やイーサリアムのスケーリング問題のソリューションとして応用されています。ゼロ知識証明が持つ3つの性質に加えてさらにSNARKを示す4つの性質を追加します。

• Succinct（簡潔）
  • 証明のサイズがステートメントのサイズと比べて非常に小さい
• Non-interactive（非対話型）
  • 証明者と検証者の間で何度も対話をする必要がない
• ARgument
  • 証明者の計算能力には限りがある
• Knowledge
  • 証明者は、知識なしでは証明を生成することは不可能である。

zk-SNARKsは簡潔な性質を持つので、ゼロ知識証明だけではなく、検証プロセスにおけるコストの削減にも大きな利点を持ちます。zk-Rollupは複数のトランザクションを一つにまとめることで、コストを大幅に削減し、そこに含まれるトランザクション全てを検証せずに検証することができます。

一般に、zk-SNARKsは次のように動作する3つのアルゴリズム（Key Generator、Prover、Verifier）によって構成されています。

• Key Generator $Gen(1^{\lambda}, \mathcal{R})$
  • セットアップアルゴリズムであり、信頼されるサードパーティによって証明者と検証者に事前に渡されるCRSを生成します。このCRSには証明者に渡す評価鍵と呼ばれる$pk$と検証者に渡す検証鍵$vk$が含まれています。
• Prover $P(pk, x, w)$
  • 証明者は$pk$と、ステートメント$x$、証拠$w$を入力として受け取り、証明$\pi$を出力する証明アルゴリズム
• Verifier $V(vk, \pi, x)$
  • 検証者は$vk$、ステートメント$x$、証明$\pi$を入力として受け取り、その証明が正しいものであれば１、そうでなければ０を返す検証アルゴリズム

非対話型ゼロ知識証明について

ゼロ知識の標準的なモデルである対話型ゼロ知識証明は第三者のような信頼の仮定を一切行わずに強力なセキュリティ保証を持つ対話型プロトコルに依存しています。この計算モデルでは、攻撃者は利用可能な時間と計算能力によってのみ制限されています。

しかし、何も信頼する存在がいない場合、対話型のゼロ知識証明には安全性や効率性の限界があります。対話回数が多いほどそれにかかる計算量が多く、検証に時間がかかってしまいます。

先ほど触れたように、簡潔な非対話型ゼロ知識証明の構築には信頼された第三者を介して証明プロセスが行われます。これをCRSモデルと呼びます。

CRSモデルとは全ての関係者が、一様分布などの分布から取得した文字列（CRS）にアクセスすることができる信頼されたセットアップが存在するという仮定に基づいたモデルである。このCRSモデルは、強力なセキュリティを持ち、効率的な証明プロセスを構築することができます。

証明者と検証者にそのCRSを提供することで、証明者と検証者は一切対話を行わずにゼロ知識証明が可能になります。

zk-SNARKsの理論

zk-SNARKsは楕円曲線暗号、NP完全、確率的検証性などの数学的手法を用い、離散対数問題などの暗号的仮定に依拠しながら、簡素で非対話なゼロ知識証明を構築しています。zk-SNARKsの理論を理解するには、まずクラスPやクラスNPなどの複雑性クラスを理解する必要があります。

クラスPとクラスNP

複雑性クラスにはNPやPというクラスが存在します。クラスPとは「ある判定問題が多項式時間で計算するアルゴリズムを持つ時、その問題はクラスPに属する」ということです。つまり、効率的に解くことができる問題のクラスです。

一方で、クラスNPとは「ある判定問題の解となる入力が問題の条件を満たすかどうかを多項式時間で判定することができるようなアルゴリズムを持つ時、その問題はクラスNPに属する」ということです。つまり、アルゴリズムは条件を満たす解を教えてもらえると、多項式時間でその解が正しいか確かめることができるが、自分で条件を満たす解を見つけるには指数時間かかる可能性があるという性質を持ちます。

NP問題の例として、「電車に乗っている時間が与えられた時間$t$以下になるようなルートが存在するか？」（巡回セールスマン問題）や「全ての頂点を３通りの色で、辺で結ばれた2つの頂点も同じ色にならないように塗り分けることができるか？」（３彩色問題）といった問題があり、これらも解となる候補が与えられれば、多項式時間で判定ができます。

一般的に、効率的に計算可能な関係（多項式時間アルゴリズム）$\mathcal{R}$が存在する場合、言語$\mathcal{L}$はクラスNPに属するという

$$\mathcal{L} = \lbrace x| \exist w, |w| \leq {poly(|{x}|) \wedge \mathcal{R}(x, w)} \rbrace$$

• 効率的に計算可能な関係$\mathcal{R} = \lbrace(\bm{x}, \bm{w}) \in \Bbb{F^n \times F^h}\rbrace$
• NP言語$\mathcal{L} = \lbrace x \in \Bbb{F^n} | \exists w \in \Bbb{F^h}, (x, w) \in \mathcal{R} \rbrace$
• $x \in \mathcal{L}$をステートメントといい、$w$を$(x, w ) \in \mathcal{R}$となる$x \in \mathcal{L}$を証明するための知識(witness)という

NP完全問題

クラスNPに属する問題のうち、解くのが最も難しい問題をNP完全問題と呼びます。NP完全問題の一つとして命題論理式の充足可能問題（SAT）という問題が知られています。その例として、「次のような論理式の出力を１とするような入力$x_1, x_2 \in \lbrace 0, 1 \rbrace$が存在するか？」という問題を考えます。

$$(x_1 \vee x_2)\wedge(x_1 ∨ \neg x_2)\wedge(\neg x_1 \vee \neg x_2)$$

上式の入力を$x_1= 1, x_2 = 0$とすることでこの論理式の解は１となり、条件を満たす入力が存在することの判定ができます。

Circuit-SAT

上記のような命題論理式を演算回路へと変換した回路の充足性問題（Circuit-SAT）を考えます。Circuit-SATとは、「演算回路$C$が与えられた時、回路の出力を１とする入力が存在するか？」というNP完全性を持つ問題である。イメージとしては、命題論理式から加算や乗算ゲートから成る回路へと変換された充足性問題です。

正式には、関係$\mathcal{R} : = \lbrace (x, w) \in \Bbb{F}^n \times \Bbb{F}^h\rbrace$は、$x$をステートメント、$w$を証拠とします。この関係$\mathcal{R}$は演算回路$C$で検証できるので、$(x, w) \in \mathcal{R}$となるとき、$f(x, w) = 1$となる算術関数$f$があり、入力が関数$f$を満たす場合には演算回路の出力が$1$、そうでない場合は出力が$0$となることを意味します。

$$f(x, w) = \begin{cases} 1 &\quad \forall (x, w)\in \mathcal{R} \\ 0 &\quad \forall (x, w)\notin \mathcal{R} \end{cases}$$

証明者はCircuit-SATに対する証拠$w$を検証者に渡すことで、検証者はそれが関数$f$の出力が１となるかどうかを多項式時間で判定することができます。

しかし実際には、$w$のサイズは非常に大きく、検証者とやりとりするにはとても効率性が悪いです。なので、Circuit-SATを用いて別の形に変換します。

Circuit-SATからQAP（quadratic arithmetic programs）を構築します。QAPとは、関数$f$の入出力が正しいかどうかを「ある多項式を知っていること」に変換します。

上図では演算回路から$m+1$個の多項式集合$\mathcal{V}, \mathcal{W}, \mathcal{Y}$と各乗算ゲートに関する根を持つ多項式$t(x)$を生成します。$\mathcal{V}, \mathcal{W}, \mathcal{Y}$は各ゲートへの左入力、右入力、出力を表す多項式の集合になっています。

$\lbrace c_i\rbrace_{i \in [m]}$は回路への入力によって得られる各乗算ゲートの出力、単に回路への入力などの値になっています。各ゲートの演算を表す多項式$\mathcal{V}, \mathcal{W}, \mathcal{Y}$とゲートへの入出力を表す$\lbrace c_i \rbrace_{i \in [m]}$で回路全体の計算が行えることになります。

$p(x)$は、正しく各ゲートの演算が行われれば、$t(x)$と同様の根を持つことがわかっています。なので、正しい入力によって得られる$p(x)$から$h(x)t(x) = p(x)$を満たすような$h(x)$が存在することがわかります。

したがって、$h(x)$が存在することが関数$f$の出力が正しくなるような入力を持つことを意味します。$p(x)$についてはあとで言及し、$h(x)$について先に考えます。

（QAPの詳細については別途記事を出そうかなと思います）

つまり、Circuit-SATを$h(x)t(x) = p(x)$を満たすような多項式$h(x)$を知っているという形式に変えます。ここで大事なのが$p(x)$は$t(x)$で割り切れるという関係にあることです。関数$f$に対する入力が間違った値であれば割り切れることができません。

上図のように、証明者が検証者に生成した多項式自体を渡すことは非常に効率性を悪くさせます。実際には対象となる多項式が非常に多いため、SNARKsの性質である簡潔さを失うことになります。

検証者に多項式自体を渡さずにそれが正しいか判断する方法がもう一つあります。

証明者の持っている証拠$w$が正しければ$h(x)t(x) - p(x) = 0$という式が常に成り立ちます。なので、多項式$P(x) = h(x)t(x) - p(x)$が恒等的に零か（$P(x) = 0$か）どうかをを示すことができればそれが正しいかどうかの判断ができそうです。

しかし、単純に式を展開し、全ての係数が０であることを確認するには計算コストがかかり、指数関数的な時間が必要になります。

ここで、多項式が「正しくない」ものであった場合、ランダムに選択された点$s$で多項式を評価すると、高い確率で誤った答えが出されることを示したSchwartz-Zippleの補題というものがあります。

この補題に依拠し、検証者はランダムに選んだ評価点$s$を証明者に送り、それを受けとった証明者はその点で多項式を評価し、検証者に渡します。これで簡素な証明を行うことが可能になりました。

エンコーディング方式

ゼロ知識証明を構築するために検証者に渡す多項式をの詳細や、検証者が渡す評価点などは明らかにしてはいけません。なので多項式、評価点をブラインド化し、ブラインドしたまま証明プロセスを行う必要があります。

次のようなエンコード関数を定義します。

$$E(x) = g^x$$

1. ほとんどの$x$に関して、$g^x$から$x$を特定することが難しい
2. 入力が異なると出力も異なる$(x \not = y \to E(x) \not = E(y))$
3. $E(x)$と$E(y)$が与えられたとき、$E(x+ y)$が計算可能

$$E(x + y) = g^{x +y} = g^x \cdot g^y = E(x) \cdot E(y)$$

証明者は$E(x)$でエンコードされた$\lbrace g^{s^i}\rbrace_{i \in [d]}$が与えられたとき、係数$\lbrace h_i \rbrace_{i=1}^d$を用いてある点$s$における多項式の評価$h(s) = \sum_{i=0}^dh_is^i$を$s$を知ることなく計算することができます。

$$\prod_{i=0}^d(g^{s^{i}})^{h_i} = g^{\sum_{i=1}^d h_is^i} = g^{h(s)}$$

また、$h(x)$は$\lbrace g^{s^i} \rbrace_{i \in [d]}$の線形結合に縛られているので、証明者の計算能力にも制限をかけることができます。

次に、$p(x)$について考えてみます。

各ゲートの演算を表す多項式$\lbrace g^{v_k(s)} \rbrace_{k \in [m]}, \lbrace g^{w_k(s)} \rbrace_{k \in [m]} ,\lbrace g^{y_k(s)} \rbrace_{k \in [m]}$と各乗算ゲートの出力、単に回路への入力値を表す$\lbrace c_i \rbrace_{i \in [m]}$から以下のような多項式を作ることができます。

$$\begin{aligned} p(x) &= \Big(v_0 + \displaystyle\sum_{k=1}^{m} c_k \cdot v_k(x) \Big) \cdot \Big(w_0 + \displaystyle\sum_{k=1}^{m} c_k \cdot w_k(x) \Big) \\ &- \Big(y_0 + \displaystyle\sum_{k=1}^{m} c_k \cdot y_k(x) \Big) \end{aligned}$$

この多項式は回路全体の計算になっています。

したがって、証明者は$\lbrace c_i \rbrace_{i \in [m]}$を係数とした多項式をそれぞれ作り$g^{v(s)}, g^{w(s)}, g^{y(s)}$を検証者に送ります。もちろんこの時、検証者は$\lbrace c_i \rbrace_{i\in [m]}$を知ることはできません。

では、検証者はどのように多項式を評価するか。先ほど定義した$E(x)$を以下のように考えます。

$p$を大きな素数として、有限体$\Bbb{F}_p$の元$g, y, x$に対して

$$y \equiv g^x \pmod p$$

とする。この時、$x$は$y$の$g$に対する離散対数と呼ばれ、$g^x$から$x$を求めることが難しいという離散対数問題になります。また、$E(x)$が持つ3つの性質も成り立ちます。

ペアリング

検証者は双線形ペアリング写像で検証を行います。

双線形写像とは、ヴェイユペアリングやテイトペアリングなどの楕円曲線上の２点をある有限体の元に変換する写像です。このペアリングは双線形性をもち、以下の式が成り立ちます。

$$e(g^a, g^b) = e(g, g)^{ab}$$

例えば、証明者は$x_1x_2 + x_3^2 = 0$を満たす$(a_1, a_2, a_3)$を知っていることをその値を明らかにせずに双線形写像ペアリングを用いて証明することができます。

$$e(g, g)^{a_1a_2 + a_3^2} = e(g^{a_1}, g^{a_2}) \cdot e(g^{a_3}, g^{a_3}) \stackrel{?}{=} e(g, g)^0$$

このように$(a_1, a_2, a_3)$の値を知らずそれらが正しいかどうかを評価することができます。

したがって、検証者はブラインドされた$p(s) = v(s)w(s) - y(s)$となる多項式$v(s), w(s), y(s)$と$h(s)$を受け取り、$h(s)t(s) = p(s)$が成立するかどうかを検証します。

$$e(g^{h(s)}, g^{t(s)}) = e(g^{v(s)}, g^{w(s)})/e(g^{y(s)}, g)$$

q-PKE仮定

しかし、これではまだ完全に証明者が正しい多項式を持っていることを証明できていません。

自分の持っている正しい情報から多項式を作成し、$g^{h(s)}$という値を評価することができることは、証明者が実際に$g^{h(s)}$を送ることを保証できていません。$p(x)$が$t(x)$で割り切れるような任意の多項式を作ることができてしまいます。

したがって、証明者に強い線形性の制限をかけ、正しく実行させる方法を考えます。

$\lbrace g^{s^d}\rbrace_{i \in d}$に加えてランダムな$\alpha$を選び、$\lbrace g^{\alpha s^d}\rbrace_{i \in d}$も送り、$g^{h(s)} g^{\alpha h(s)}$のようなペアを返すことを要求します。このようなペアが返すことができれば、証明者は受け取った値を使って評価したことを保証することができます。これはq-PKEという暗号仮定に基づいています。

例えば、有限体$\Bbb{F}$上の楕円曲線上の点$P_i, \alpha P_i$を与えた時に、$\alpha$を知らずに点$Q, \alpha Q$を作ることを考えます。

もし、$\alpha$の値を知っていたとすると、適当な点$S$から$\alpha S$を作ることが可能であるが、証明者には$\alpha$に関して$\alpha P$しか情報が与えられていません。したがって、有限巡回群上の離散対数問題により点$S, \alpha S$を作ることは困難であることがわかります。

$\alpha$を知らずに点$Q, \alpha Q$を作る方法が一つだけ存在します。

それは、$P_i, \alpha P_i$の線形結合からなる点$Q, \alpha Q$を作ることです。$a_i \in \Bbb{F}$を用いて、$Q = a_1P_1 + a_2P_2 + \dots + a_qP_q$となる線形結合を作り、これより、

$$\begin{aligned} \hat{Q} &= a_1(\alpha P_1) + a_2(\alpha P_2) + \dots + a_q(\alpha P_q) \\ &= \alpha(a_1P_1 + a_2P_2 + \dots + a_qP_q) = \alpha Q \end{aligned}$$

が得られます。したがって$\alpha$を知らずに点$Q, \alpha Q$を作ることができました。つまり、点$Q, \alpha Q$を作るには、与えられた点$P_i, \alpha P_i$の線形結合で作ることに制限されます。

以上がq-PKEの満たす仮定であり、この仮定の下で多項式評価の検証を行います。

ペアリングによって証明者が与えられた$\lbrace g^{s^i} \rbrace_{i\in [d]}, \lbrace g^{\alpha s^i}\rbrace_{i \in [d]}$から多項式を評価したしたことを検証することができます。

$$e(g^{h(s)}, g^{\alpha}) = e(g^{\alpha h(s)}, g)$$

対話型から非対話型へ

これまでの構築は証明者と検証者の対話によるゼロ知識証明を構築してきました。第三者をおき、非対話なゼロ知識証明の構築を行います。

今までで、検証者が渡していた、評価点や多項式を事前のセットアップとして生成し、検証者も不正ができないようにブラインドされたままそれらを$vk$として受け取ります。証明者は$pk$を受け取り、それを用いて証拠$w$の証明$\pi$を生成し、検証者に渡します。受け取った検証者はペアリングによる検証を行います。（以下の証明は省きます）

• 抽出可能性

$$\begin{aligned} &e(g^{v(s)}, g^{\alpha}) = e(g^{\alpha v(s)}, g) \quad &e(g^{w(s)}, g^{\alpha}) = e(g^{\alpha w(s)}, g) \\ &e(g^{y(s)}, g^{\alpha}) = e(g^{\alpha y(s)}, g) \quad &e(g^{h(s)}, g^{\alpha}) = e(g^{\alpha h(s)}, g) \end{aligned}$$

• QAPの条件を満たす多項式であるか

$$e(g^{h(s)}, g^{t(s)}) = e(g^{v_0(s)}g^{v(s)}, g^{w_0(s)}g^{w(s)}) /e(g^{y_0(s)} g^{y(s)}, g)$$

このzk-SNARKsの構築が4つの性質を満たしていることを確認します。

• Succinct
  • 証明者に評価点を与えることで多項式を評価した結果のみ返すだけで済む
• Non-interactive
  • 対話を行わずに証明者が一回だけ検証者に証明を送るだけで検証を可能にしている
• ARgument
  • 線形結合の制限をかけることで不正が難しくなっている
• Knowledge
  • 証拠$w$でQAPによる多項式を作る必要がある

以上で簡潔で非対話なゼロ知識証明であるzk-SNARKsの構築をすることができました。

Pinocchio Protocol

Pinocchioプロトコルと呼ばれる「暗号の仮定だけに頼りながら一般的な計算を効率的に検証するために構築されたプロトコル」の下でzk-SNARKsの構築を行いました。

このプロトコルでは、使われるq-PDHやq-SDH、q-PKEはそれぞれDH、SDH、KEA仮定を一般化した離散対数問題です。q-SDHは現代のペアリングベース暗号の基礎になっており、qによってパラメータ化されたこれらの仮定は解くことがより難しいと知られています。これらの暗号学的仮定に依拠しながらzk-SNARKsを構築することで、安全かつ効率的な証明プロセスを実現することができます。

$q$型仮定

Pinocchioプロトコルはq型仮定の暗号学的仮定を用いています。従来の標準的な仮定（DDH、CDHなど）はパラメーター化されておらず、常に一定のサイズ（静的）です。

一方、非静的な$q$型仮定は$q$によってパラメーター化されています。証明が非静的なものに依存している場合、$q$は通常、攻撃者が行うクエリの数、入力サイズ、またはプロトコルに必要な計算ステップの数に関連します。クエリの数が多ければ多いほど仮定が強くなり、攻撃者がその仮定を破ることがより難しいと言われてるからです。

zk-SNARKsの厳密な構成（Zcash）

今回は、zk-SNARKsのざっくりした概念や、構築方法を説明を行いましたが、実際にはまだ全ての説明をしきれていません。

実際には上図のような鍵生成者と証明者、検証者が存在します。説明できていない部分としては、多項式集合$\mathcal{V}, \mathcal{W}, \mathcal{Y}$がQAPから抽出されたものかどうかの検証、完全なゼロ知識証明構築のための多項式の乱数化、確率的検査可能証明、検証者が多項式の欠損部分を計算することでより不正が難しくなるような設計、QAPの厳密な定義など。。

また、zk-SNARKsの構築における$vk$と$pk$のサイズや全体の計算量などの効率性におけるものは考慮できていません。

色々省いて説明を行ったので、説明不足な部分や、間違っている箇所もあると思いますので、訂正箇所ございましたらコメント等くださると嬉しいです。

ご閲覧ありがとうございました！

参考論文

Succinct Non-Interactive Arguments via Linear Interactive Proofs

Pinocchio: Nearly Practical Verifiable Computation

Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture

Quadratic Span Programs and Succinct NIZKs without PCPs

The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols

Succinct Non-Interactive Arguments from Quadratic Arithmetic Programs