💡

zk-SNARKsの原理

2022/08/03に公開約21,200字

はじめに

前提知識

  • 群、体に関する初歩的な知識(準同型、単射全射、巡回群、生成元など)

扱う内容

  • zk-SNARKsとは?
  • Pinocchio(最も基本的なzk-SNARKs)の解説

zk-SNARKsとは

zk-SNARKはZero Knowledge Succinct Non-interactive Argument of Knowledgeの省略形です。それぞれの単語を日本語訳しますと

Zero Knowledge:ゼロ知識の
Succinct: 簡潔な
Non-interactive: 非対話の
Argument of Knowledge: 知識の根拠[1]

という意味になります。zk-SNARKの具体的なプロトコルは複数知られているので、それらを総称してzk-SNARKsと呼びます。

次の図はzk-SNARKの一例を表しています。

zk-SNARKの概要

Proverは、ある関数fに対して、f(x, y) = zが成り立つx, y, zを知っているとします。目的は、Verifierに、yを秘密にしたままf(x, y) = zが成り立つことを納得してもらうことです。Prover、Verifierは事前にfがどのような関数であるか共有しているとします。

Proverはf(x, y) = zが成り立っていることの「証明」proofを作成します。proofにはyに関する情報は含まれていません。Verifierはproofを用いて検証を行い、ステートメント「x, zに対してyが存在しf(x, y) = zが成り立つ」を受理するか拒否するかを決定します。

驚くべきことに、proofのサイズは、f(x, y)の計算量と無関係、あるいは対数程度に小さくできます。一般的なzk-SNARKプロトコルでは、Verifierの検証時間はproofのサイズと同程度なので、Verifierはf(x, y)を直接計算するよりも遥かに効率的にf(x, y) = zを検証することができます[2]

この例をzk-SNARKの定義に対応させると

Zero Knowledge(ゼロ知識の):Verifierに与えるyの知識はゼロ
Succinct(簡潔な): proofのサイズはf(x, y)の計算量に対して非常に小さい(対数程度に小さい、または一定サイズ)
Non-interactive(非対話の): ProverからVerifierへの一回きりの通信のみ行う
Argument of Knowledge(知識の根拠): f(x, y) = zが成り立つことの根拠(証明)

となります。Proverはどのような証明をどうやって作るか、Verifierは証明をどう検証するか、というところがzk-SNARKプロトコルの肝であり、これまでに様々なzk-SNARKプロトコルが提案されてきました。

Pinocchioとは

Pinocchioとは、2013年にBryan Parno, Jon Howell, Craig Gentry, Mariana Raykovaの4人が"Pinocchio: Nearly Practical Verifiable Computation"という論文で発表したzk-SNARKプロトコルです。

原論文

https://eprint.iacr.org/2013/279

zk-SNARKsの中ではかなりシンプルで基本的なプロトコルです。

状況設定

前のセクションでは、公開引数xと秘密引数yを持つ関数f(x, y)を扱いましたが、ここでは関数y = F(u)を扱います。ただしun個の変数の組u:=(u_1, u_2, \ldots, u_n)で、yn'個の変数の組y:=(y_1, y_2, \ldots, y_{n'})とします。最初にuが公開引数の場合を論じ、次にuの一部を秘匿化する(ゼロ知識化する)方法について述べます。

プロトコルの流れ

Pinocchioでは信頼できる第三者による事前のセットアップ(トラステッドセットアップ)が必要です。信頼できる第三者は証明の作成に使う評価鍵(Evaluation Key)EKと、検証に使う検証鍵(Verification Key)VKを生成して公開します。ProverはEKを用いて証明\piを作成しu, yとともにVerifierに送ります。VerifierはVKu,y, \piを用いて証明を検証します。

トラステッドセットアップが必要なzk-SNARK

図中の\lambdaはセキュリティの程度を表す整数で、大きくすれば証明が偽造しにくくなる一方で、EK,VKのサイズは大きくなります。

Proverはy=F(u)というステートメントを多項式の割り算の問題へ変換し、それを元に証明\piを作成します。証明\piは群の元の組であり、Verifierはペアリングを用いてy=F(u)を検証します。

多項式へのエンコード(QAP)

PinocchioではFを算術回路で表し、それを多項式の割り算の問題へ変換します。算術回路がエンコードされた多項式をQAP(Quadratic Arithmetic Program)と言います。この節では、どのようにFをQAPに変換するかを解説します。

y_1 = (u_1 + u_2)u_3u_4という関数を考えてみましょう。これは下図のような算術回路で表すことができます。

例えばu_1=2,u_2=1,u_3=2,u_4=3を代入すると下図のようになります。

u_1=c_1, u_2=c_2,u_3=c_3,u_4=c_4のとき、新たにワイヤに割り当てられる数値をd,e,fとすると(図)、

それぞれのゲートにおいて次のような制約が課せられます。

\begin{align*} c_1 + c_2 = d\\ c_3 \times c_4 = e\\ d\times e = f \end{align*}

ただし、制約はなるべく少ないほうが良いので、足し算のゲートに関しては制約を課さずに、その次の掛け算のゲートにおいて制約を課すことにします。

\begin{align*} c_3 \times c_4 = e\\ (c_1+c_2)\times e = f \end{align*}

すなわち、c_1 + c_2 = dというような足し算ゲートの制約に関しては、その値を入力として利用する掛け算ゲートの制約に代入することで制約の数を減らすということです。結局、制約は掛け算ゲートにおいてのみ発生し、またそのゲート出力として新たにワイヤの値が割り当てられることになります。新たに割り当てられるワイヤの値e,fc_5, c_6と書き直すことにします。また、c_5, c_6が割り当てられる掛け算ゲートをそれぞれゲート5, ゲート6と呼ぶことにします。すると制約は次のように書けます。

\begin{align*} c_3 \times c_4 = c_5\qquad(gate5)\\ (c_1+c_2)\times c_5 = c_6\qquad(gate6) \end{align*}

これらの制約を体\mathbb{F}_p上の多項式v_k(x), w_k(x), y_k(x) (k=1,2,3,4,5,6)を使って表します。\mathbb{F}_pから適当に2点r_5, r_6を選んでおきます。r_5がゲート5、r_6がゲート6における多項式の評価点となります(後で意味を解説します)。

ゲートの制約の式は(c_iの和)\times(c_iの和)=c_jの形になることに注意してください。ゲートの制約の式の左辺について、\timesに対して左の項を「左項」、右の項を「右項」と呼ぶことにします。例えばゲート5の制約c_3\times c_4 = c_5において、「左項」はc_3、「右項」はc_4になります。

v_k(x)は「左項」に、w_k(x)は「右項」に、y_k(x)は右辺にc_kが含まれるかどうかを表す多項式です。

ゲート5の制約において、もし「左項」にc_kが含まれていればv_k(r_5)=1、含まれていなければv_k(r_5)=0、ゲート6の制約において、もし「左項」にc_kが含まれていればv_k(r_6)=1、含まれていなければv_k(r_6)=0となるようにv_k(x)を構成します。w_k(x)は「右項」に対して、y_k(x)は右辺に対して同様に構成します(表)。

v_k(x), w_k(x), y_k(x)の構成(Parno et al. 2013からの引用)

例えばv_1(x)は次のように構成できます。ゲート5の制約はc_3\times c_4 = c_5で、「左項」はc_3であり、c_1は含まれません。従ってv_1(r_5) = 0です。ゲート6の制約は(c_1 + c_2)\times c_5 = c_6で、「左項」はc_1+c_2であり、c_1が含まれます。従ってv_1(r_6) = 1です。もし仮にr_5=1, r_6=2を選ぶなら、v_1(x) = x-1と表すことができます。

このように多項式v_k(x), w_k(x), y_k(x)を構成すると、制約の式は

\left( \sum_{k=1}^{6} c_k v_k(x) \right)\left( \sum_{k=1}^{6} c_k w_k(x) \right) = \sum_{k=1}^{6} c_k y_k(x) \quad \text{where } x=r_5, r_6

とまとめることができます。

右辺を左辺に移項し、p(x)と置いてみます。

\begin{align*} p(x):= \left( \sum_{k=1}^{6} c_k v_k(x) \right)\left( \sum_{k=1}^{6} c_k w_k(x) \right) - \sum_{k=1}^{6} c_k y_k(x) \end{align*}

p(x)x=r_5, r_6を根に持つので、t(x):=(x-r_5)(x - r_6)で割り切ることができます。逆にp(x)t(x)で割り切るならば、p(x)x=r_5, r_6を根に持ち、掛け算ゲートの正しい制約式が得られるので\{c_k\}が正しく割り当てられていることがわかります。

以上により、\{c_k\}は回路の正しい値の割り当てか」という問題を、「p(x)t(x)で割り切れるか」という問題に変換することができました。

今回は、定数入力を含まない回路を取り上げましたが、一般的には回路にはc_kだけでなく定数が入力されることもあります。その場合、定数を表す多項式v_0(x), w_0(x), y_0(x)を加える必要があります。例えばゲート6の制約が(c_3 + 2)\times c_5 = c_6ならば、v_0(r_6)=2となるようにv_0(x)を構成します。

以上をまとめると、次のようになります。

定理
関数Fと評価点の集合\mathcal{M}、それに対応する\{v_k(x)\}_{k=0,\ldots,m}, \{w_k(x)\}_{k=0,\ldots,m}, \{y_k(x)\}_{k=0,\ldots,m}が与えられているとき、c_1,\ldots, c_{m}\in \mathbb{F}_pが関数Fに対応する算術回路の正しい値の割り当てであることは、t(x) := \prod_{r_g \in \mathcal{M}} (x -r_g)

\begin{align} p(x):= \left( v_0(x) + \sum_{k=1}^{m} c_k v_k(x) \right)\left( w_0(x) +\sum_{k=1}^{m} c_k w_k(x) \right) -y_0(x) - \sum_{k=1}^{m} c_k y_k(x) \end{align}

を割り切ることの必要十分条件。ただしN:=n+n'は入力/出力変数の合計数で、c_{1}, \ldots, c_{N}Fの入出力に対応するワイヤに割り当てられる値であり、c_{N+1}, \ldots, c_{m}は入出力には直接関係ないワイヤに割り当てられる値。

素朴な証明プロトコル

y=F(u)を多項式にエンコードできたので、それを用いてステートメント「y,uy=F(u)を満たす」を証明するプロトコルを考えてみましょう。

はじめに、\sum_i c_i v_i(x)などを入出力に関係する部分(i/o)とそうでない部分(mid)に分けておきます。

\begin{align} &v_{\mathrm{i/o}}(x):=\sum_{i=1}^{N} c_i v_i(x)\\ &v_{\mathrm{mid}}(x):=\sum_{i=N+1}^{m} c_i v_i(x)\\ &w_{\mathrm{i/o}}(x):=\sum_{i=1}^{N} c_i w_i(x)\\ &w_{\mathrm{mid}}(x):=\sum_{i=N+1}^{m} c_i w_i(x)\\ &y_{\mathrm{i/o}}(x):=\sum_{i=1}^{N} c_i y_i(x)\\ &y_{\mathrm{mid}}(x):=\sum_{i=N+1}^{m} c_i y_i(x) \end{align}

セットアップ
ProverとVerifierは\{v_k(x)\}_{k=0,\ldots,m}, \{w_k(x)\}_{k=0,\ldots,m}, \{y_k(x)\}_{k=0,\ldots,m}を共有しておきます。これらの値はFに依存しますが、Fの入出力u, yとは関係がないことに注意してください。

証明の作成
Proverはy=F(u)を元にh(x):=p(x)/t(x), v_{\mathrm{mid}}(x), w_{\mathrm{mid}}(x), y_{\mathrm{mid}}(x)を計算して、u, yとともにVerifierに送ります。

検証
Verifierは次の検証を行います。

  1. h(x)が多項式であること
  2. v_{\mathrm{mid}}(x)\{v_i(x)\}_{i=N+1,\dots,m}の線形結合であること
  3. w_{\mathrm{mid}}(x)\{w_i(x)\}_{i=N+1,\dots,m}の線形結合であること
  4. y_{\mathrm{mid}}(x)\{y_i(x)\}_{i=N+1,\dots,m}の線形結合であること

つぎにu, yの値からv_{\mathrm{i/o}}(x), w_{\mathrm{i/o}}(x), y_{\mathrm{i/o}}(x)を計算し、

p(x) = (v_0(x) + v_{\mathrm{i/o}}(x) + v_{\mathrm{mid}}(x))(w_0(x) + w_{\mathrm{i/o}}(x) + w_{\mathrm{mid}}(x)) - y_0(x) - y_{\mathrm{i/o}}(x) - y_{\mathrm{mid}}(x)

を構成します。最終的に

  1. p(x)=h(x)t(x)であること

を検証します。

これら5つのテスト全てに合格すれば、ステートメント「y,uy=F(u)を満たす」を受理します。

1の検証は、p(x)/t(x)が割り切れないケースを弾きます。2,3,4はp(x)を正しく構成する為に行います。v_0(x),v_{\mathrm{i/o}}(x)はVerifierが用意するので問題ありませんが、v_{\mathrm{mid}}(x)はProverが提供するので正しく構成されているか確認する必要があるのです。

上記のプロトコルはゼロ知識でも簡潔でもありません。次の節で導入する群やペアリングといった道具を用いて、このプロトコルを簡潔化し、その後にゼロ知識化します。このプロトコルは多項式の恒等式を検証する必要があり、コストが高くなっています。zk-SNARKでは、多項式を扱う代わりに、変数xにあるランダムな値sを代入し、値として扱うという手法を用います。その手法の正当性を与えるのがSchwartz–Zippelの補題です。また、2,3,4の線形結合かどうかの検証はKC(Knowledge of Coefficient) と呼ばれるテクニックで効率的に行なえます。いずれも、次の節で解説します。

数学的背景

離散対数問題とDH問題

Gを巡回群、gをその生成元とします。gは生成元なので、群Gの任意の元は、ある自然数nを用いてg^nの形で書くことができます。g^nからnを求める問題は離散対数問題と呼ばれ、離散対数問題を解く効率的な(\log n程度の時間の)アルゴリズムは存在しないと考えられています[3]

なお、gn乗は効率的に(\log n程度の時間で)計算することができます。例えばg^{1024}を計算したい場合、g^2をまず計算して, g^4=(g^2)^2, g^{16}=(g^4)^2...のように2乗を繰り返せば10回の計算で済みます。2のべき乗以外の値も2進数表記すると2のべき乗の組み合わせで書けるので効率的に計算できます。

離散対数問題と同様に、効率的に解けないと考えられている問題としてDH(Diffie-Hellman)問題があります。これはg^ag^bからg^{ab}を求める問題です。離散対数問題が解けるならa, bを求めg^{ab}を計算することができるので、離散対数問題よりも弱い問題ですが、離散対数問題同様に簡単に解けないと考えられています。

準同型ハイディング

g^ag^bからg^{ab}を作るのは難しい一方で、g^{a+b}を作るのは簡単で、単に掛け合わせればいいだけです。E(x):=g^xと定義すると、Eは次の性質を持ちます

  • 一方向性
    E(x)からxを求めることは難しい(離散対数問題の困難性から)

  • 単射性
    E(x)=E(y)ならばx=y

  • 準同型性
    E(x)E(y) = E(x+y)が成り立つ

E準同型ハイディング(Homomorphic Hiding) と呼ばれます。

多項式の未知の点における評価

いま未知のsに対してE(1), E(s^1), \ldots, E(s^n)が与えられているとします。Eの一方向性からsを求めることはできません。しかしながら、多項式P(x):=\sum_i c_i x^iに対しE(P(s))は次のように求めることができます。

\begin{align*} E(P(s)) & = g^{P(s)} = g^{\sum_i c_i s^i}= \prod_i (g^{s^i})^{c_i} = \prod_i E(s^i)^{c_i} \end{align*}

すなわち、sは未知でもsにおけるP(x)の評価(にEを作用させたもの)は求めることができるのです。

ペアリング

G_1, G_2, G_3が群であるとき、双線形性を持つ非自明な写像e:G_1 \times G_2 \rightarrow G_3ペアリングと言います。

双線形性[4]

\begin{align*} e(p_1 p_2, q) = e(p_1, q)e(p_2, q)\\ e(p,q_1q_2) = e(p,q_1)e(p, q_2) \end{align*}

Pinocchioでは、G_1=G_2が巡回群の場合を扱います。gG_1=G_2の生成元とすると、

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

が成り立ちます。この関係式はよく見るとDH問題に似ています。同じ群の上ではabを掛け合わせることはDH問題の困難性によりできませんが、別の群G_3上においては可能なのです。

準同型ハイディングE(x)に関して、次の式が成り立ちます。

e(E(ax), E(y)) = e(g^{ax}, g^y) = e(g,g)^{axy}=e(g^x, g^{ay})=e(E(x), E(ay))

すなわち、積の係数を左右どちらにも動かすことができます。この性質は、この後紹介するKnowledge of Coefficientと呼ばれるテクニックで重要な役割を果たします。

Schwartz–Zippelの補題

\mathbb{F}_p上の未知のn次多項式f(x)g(x)が同じか違うかを判定したいとします[5]。ただし、p \gg nとします。正確に判定しようと思うと、全てのx\in\mathbb{F}_pに対してf(x)=g(x)かどうか調べる必要がありますが、確率的な判定で良いのなら、非常にシンプルでかつ信頼性の高い方法が知られています: ランダムに値sを選びf(s) - g(s)=0なら「同じ」、f(s) - g(s)\neq0なら「違う」と判定するのです。

後者は良いとして、何故前者で「同じ」と判定しても良いのでしょうか?理由は次の通りです。f(x)-g(x)は高々n次の多項式なので、高々n個しか根を持ちません。\mathbb{F}_pから運悪くf(x)-g(x)の根を引き当てる確率はn/|\mathbb{F}_p|ほどで、p \gg nのとき無視できるほど小さく、したがって、f(s) - g(s)=0なのにf(x) \neq g(x)である確率は無視できるほど小さいのです。これをSchwartz–Zippelの補題と言います。

すでに、未知の点sにおいて多項式P(x)の評価の準同型ハイディングE(P(s))について述べました。信頼できる第三者が秘密のsをランダムに選び、E(1), E(s^1), \ldots, E(s^n)を提供するなら、多項式P(x)Q(x)が同じであることの証明は、Schwartz–Zippelの補題を使って次のように行えそうです。

  1. ProverはE(P(s))E(Q(s))を計算し、Verifierに送る。
  2. VerifierはE(P(s)) = E(Q(s))かどうかを判定する。

ただし、この方法はProverが正直にE(P(s))E(Q(s))を計算したのか判定しようがないのでうまくいきません。次の節で述べるKCのテクニックなどと組み合わせる必要があります。

KC(Knowledge of Coefficient)

E(s)E(\alpha s)のように、Eの中身が\alpha倍になっている関係を、「\alphaの関係」と呼ぶことにします。

  • E(1)E(\alpha)
  • E(s)E(\alpha s)
  • E(s^2)E(\alpha s^2)

はいずれも「\alphaの関係」を持ったペアです。
これら3つのペアから、別の「\alphaの関係」を持ったペアを作ることはできるでしょうか?

例えばE(2)=E(1)E(1)E(2 \alpha)=E(\alpha)E(\alpha)や、E(1 + s + s^2)=E(1)E(s)E(s^2)と、E(\alpha+\alpha s+\alpha s^2)=E(\alpha)E(\alpha s)E(\alpha s^2)などは作ることができます。

しかしながらE(s^3)E(\alpha s^3)のペアなどは作ることができません。E(s^3)=E(s^2 \cdot s)E(\alpha s^3)=E(\alpha s^2 \cdot s)を求めるのは、DH問題の困難性から難しいのです。

以上の考察から、次のことが言えそうです。

主張
E(1), E(s), E(s^2), E(\alpha),E(\alpha s),E(\alpha s^2)が既知のとき、あるpに対して「\alphaの関係」を持ったペアE(p), E(\alpha p)を作ることができるなら、そのpは、あるc_0, c_1, c_2を用いてp = c_0 + c_1 s + c_2 s^2と書ける。

すなわち別の「\alphaの関係」を持ったペアは、既存の「\alphaの関係」を持ったペアの線形結合でしか作れないのです。

あるペアE(x), E(y)が「\alphaの関係」を持っているかどうかはペアリングを用いて検証することができます。

e(E(x), E(\alpha)) \overset{?}{=} e(E(y), E(1))

このテストに合格すればy = \alpha x、すなわちE(x), E(y)は「\alphaの関係」を持っていることが分かります。

これらを一般化してProver-Verifierの形で言い直してみます。

主張
v_1,v_2,\ldots,v_nE(v_1),E(v_2), \ldots,E(v_n), E(\alpha), E(\alpha v_1),E(\alpha v_2), \ldots,E(\alpha v_n)が既知であるとする[6]。Proverが「\alphaの関係」を持ったペアE(p), E(\alpha p)をVerifierに送り、Verifierがe(E(p), E(\alpha)) \overset{?}{=} e(E(\alpha p), E(1))を確認したなら、Verifierはpp = c_0 + \sum_i c_i v_iの形で書けることを確証できる。

pc_0が入っていますが、これはE(c_0)E(\alpha c_0)=E(\alpha)^{c_0}が作れることに由来します。E(\alpha)が提供されなければこのようなペアを作ることはできませんが、今度はペアリングのテストが行えなくなってしまいます。これは、もう一つの未知値\betaを導入して、ペアリングテストで使うものと分離することで解決できます。

主張(改良版)
v_1,v_2,\ldots,v_nE(v_1),E(v_2), \ldots,E(v_n), E(\beta), E(\alpha \beta), E(\alpha v_1),E(\alpha v_2), \ldots,E(\alpha v_n)が既知であるとする。Proverが「\alphaの関係」を持ったペアE(p), E(\alpha p)をVerifierに送り、Verifierがe(E(p), E(\alpha \beta)) \overset{?}{=} e(E(\alpha p), E(\beta))を確認したなら、Verifierはpp = \sum_i c_i v_iの形で書けることを確証できる。

以上のテクニックをKC(Knowledge of Coefficient)、またこの主張が成り立つという暗号学的な仮定を**KCA(Knowledge of Coefficient Assumption)**と言います。

Pinocchioプロトコルの詳細

Schwartz–Zippelの補題を用いて、先程の「素朴な証明プロトコル」における多項式を、ランダムな点sで評価しましょう。すると、最初の4つの検証は次のようになります。

  1. h(s)sの多項式であること
  2. v_{\mathrm{mid}}(s)\{v_i(s)\}_{i=N+1,\dots,m}の線形結合であること
  3. w_{\mathrm{mid}}(s)\{w_i(s)\}_{i=N+1,\dots,m}の線形結合であること
  4. y_{\mathrm{mid}}(s)\{y_i(s)\}_{i=N+1,\dots,m}の線形結合であること

h(s)が多項式であるとは、h(s)1, s, s^2, \ldotsの線形結合であることと同値であり、KCのテクニックで証明することができます。2,3,4も同様にKCのテクニックで証明することができます。

p(s)=h(s)t(s)であることの検証もSchwartz–Zippelの補題とペアリングを用いて、

e(E(p(s)), E(1)) \overset{?}{=} e(E(h(s)), E(t(s)))

とすれば良いことが分かります。以上より、次のようなPinocchioプロトコルを構成することができます。

Pinocchioプロトコルの流れ(再掲)

トラステッドセットアップ

dv_k(x),w_k(x),y_k(x)の最高の次元とします。 I_{\mathrm{i/o}}:=\{1,\ldots,N\}, I_{\mathrm{mid}}:=\{N,\ldots,m\}, [d]:=\{1,2,\ldots,d\}と表記します。

信頼できる第三者は、s, \alpha, \beta_v, \beta_w, \beta_y, \gammaをランダムに選び、

評価鍵

EK = \{\{E(s^i)\}_{i\in [d]}, \{E(\alpha s^i)\}_{i\in [d]}, \{E(v_i(s))\}_{i\in I_{\mathrm{mid}}}, \{E(w_i(s))\}_{i\in I_{\mathrm{mid}}}, \{E(y_i(s))\}_{i\in I_{\mathrm{mid}}}, \{E(\beta_v v_i(s))\}_{i\in I_{\mathrm{mid}}}, \{E(\beta_w w_i(s))\}_{i\in I_{\mathrm{mid}}}, \{E(\beta_y y_i(s))\}_{i\in I_{\mathrm{mid}}} \}

検証鍵

VK = \{E(1), E(\alpha), E(\gamma),E(\beta_v \gamma),E(\beta_w \gamma),E(\beta_y \gamma), E(t(s)), E(v_0(s)),E(w_0(s)),E(y_0(s)), \{E(v_i(s))\}_{i\in I_{\mathrm{i/o}}}, \{E(w_i(s))\}_{i\in I_{\mathrm{i/o}}}, \{E(y_i(s))\}_{i \in I_{\mathrm{i/o}}} \}

を作成し公表します。s, \alpha, \beta_v, \beta_w, \beta_y, \gammaは破棄します。

プルーフの作成

Proverはy=F(u)に対応する回路の値割り当て\{c_i\}を作成し、
E(v_{\mathrm{mid}}(s)), E(\beta_v v_{\mathrm{mid}}(s))を次のように構成します。

\begin{align*} &E(v_{\mathrm{mid}}(s)) = \prod_{i \in I_{\mathrm{mid}}} E(v_i(s))^{c_i}\\ &E(\beta_v v_{\mathrm{mid}}(s)) = \prod_{i \in I_{\mathrm{mid}}} E(\beta_v v_i(s))^{c_i} \end{align*}

E(w_{\mathrm{mid}}(s)), E(\beta_w w_{\mathrm{mid}}(s)), E(y_{\mathrm{mid}}(s)), E(\beta_y y_{\mathrm{mid}}(s))についても同様に構成します。

次に、

\begin{align*} & p(x) := \left(v_0(x) + \sum_{i=1}^{m} c_i v_i(x) \right)\left(w_0(x) +\sum_{i=1}^{m} c_i w_i(x) \right) -y_0 - \sum_{i=1}^{m} c_i y_i(x)\\ & h(x) := p(x)/t(x) \end{align*}

を計算します。多項式h(x)の係数を\{h_i\}とすると、E(h(s))E(\alpha h(s))は次のように構成できます。

\begin{align*} &E(h(s)) = \prod_{i \in [d]} E(s^i)^{h_i}\\ &E(\alpha h(s)) = \prod_{i \in [d]} E(\alpha s^i)^{h_i}\\ \end{align*}

これらをまとめてプルーフ

\pi = \{ E(v_{\mathrm{mid}}(s)),E(w_{\mathrm{mid}}(s)),E(y_{\mathrm{mid}}(s)),E(h(s)), E(\alpha h(s)), E(\beta_v v_{\mathrm{mid}}(s)),E(\beta_w w_{\mathrm{mid}}(s)),E(\beta_y y_{\mathrm{mid}}(s)) \}

を作成しu, yとともにVerifierに送ります。

検証

Verifierは検証鍵VKを用いてプルーフ\piを次のように検証します。

\begin{align*} &e(E(\alpha h(s)), E(1)) \overset{?}{=} e(E(h(s)), E(\alpha))\\ &e(E(\beta_v v_{\mathrm{mid}}(s)), E(\gamma)) \overset{?}{=} e(E(v_{\mathrm{mid}}(s)), E(\beta_v \gamma))\\ &e(E(\beta_w w_{\mathrm{mid}}(s)), E(\gamma)) \overset{?}{=} e(E(w_{\mathrm{mid}}(s)), E(\beta_w \gamma))\\ &e(E(\beta_y v_{\mathrm{mid}}(s)), E(\gamma)) \overset{?}{=} e(E(y_{\mathrm{mid}}(s)), E(\beta_y \gamma)) \end{align*}

第1式によってh(s)が多項式であることが分かり、第2,3,4式によってv_{\mathrm{mid}}(s), w_{\mathrm{mid}}(s), y_{\mathrm{mid}}(s)がそれぞれ\{v_i(s)\}_{i \in I_{\mathrm{mid}}}, \{w_i(s)\}_{i \in I_{\mathrm{mid}}}, \{y_i(s)\}_{i \in I_{\mathrm{mid}}}の線形結合であることが分かります。

u,y(=\{c_i\}_{i \in I_{\mathrm{i/o}}})を用いて、

\begin{align*} E(v_{\mathrm{i/o}}(s)) = \prod_{i \in I_{\mathrm{i/o}}} E(v_i(s))^{c_i}\\ E(w_{\mathrm{i/o}}(s)) = \prod_{i \in I_{\mathrm{i/o}}} E(w_i(s))^{c_i}\\ E(y_{\mathrm{i/o}}(s)) = \prod_{i \in I_{\mathrm{i/o}}} E(y_i(s))^{c_i}\\ \end{align*}

を計算し、p(s) \overset{?}{=} h(s)t(s)の検証を行います。

\begin{align*} &v_e := E(v_0(s))E(v_{\mathrm{i/o}}(s))E(v_{\mathrm{mid}}(s))\\ &w_e := E(w_0(s))E(w_{\mathrm{i/o}}(s))E(w_{\mathrm{mid}}(s))\\ &y_e := E(y_0(s))E(y_{\mathrm{i/o}}(s))E(y_{\mathrm{mid}}(s))\\ &\frac{e(v_e,w_e)}{e(y_e, E(1))} \overset{?}{=} e(E(h(s)), E(t(s))) \end{align*}

以上のテスト全てに合格すれば、ステートメント「u, yy=F(u)を満たす」を受理します。

このプロトコルはsuccinctです。プルーフは8個のGの元であり、定数サイズです。また、検証に必要な計算量も、N(Fの入力変数、出力変数の合計数)のオーダーであり[7]F(u)の計算量に依存しません。

ゼロ知識化

入力変数c_iを秘密にしたい場合、インデックスiI_{\mathrm{i/o}}からI_{\mathrm{mid}}へ移すだけで、ある程度秘匿化されます(プルーフからc_iを求めることが難しくなります)。

しかしながら、少し手を加えるだけで、完全にゼロ知識化することもできます。

Proverはランダムな\delta_v, \delta_w, \delta_yを選び、

\begin{align*} &v_{\mathrm{mid}}(x):=\sum_{i\in I_{\mathrm{mid}}} c_i v_i(x) + \delta_v t(s) \\ &w_{\mathrm{mid}}(x):=\sum_{i\in I_{\mathrm{mid}}} c_i w_i(x) + \delta_w t(s)\\ &y_{\mathrm{mid}}(x):=\sum_{i\in I_{\mathrm{mid}}} c_i y_i(x) + \delta_y t(s) \end{align*}

と変更します(それに合わせてp(x), h(x)も変更します)。

このように変更しても、やはりp(s)t(s)で割り切れるのでVerifier側の手順は全く変わりません。\delta_v, \delta_w, \delta_yを完全にランダムに選べば、v_{\mathrm{mid}}(s)などは\{c_i\}_{i\in I_{\mathrm{mid}}}と相関しなくなります。

以上よりzk-SNARKなプロトコルを構成することができました。

最後に

この記事の内容はPinocchioプロトコルの原論文のセクション2までに対応します(わかりやすさを優先して、少し変更した部分もあります)。セクション3以降では更に工夫を加えて効率化したバージョンも紹介されていますが、今回は取り上げませんでした。

この記事の間違い等にお気づきになった方や、ご質問がある方は、twitterのDMまでお気軽にご連絡ください。

もしよければ投げ銭ください!
zkSync:0xa2E8Eb6E89Df3D533b28DbeA3e27D478533a9f87

参考にした記事

https://eprint.iacr.org/2013/279

https://zenn.dev/kyosuke/articles/a1854b9be26c01df13eb

https://leonahioki.medium.com/楕円曲線の夢の国に住もう-12dcc675995a

Why and How zk-SNARK Works:

Electric Coin blog series:

脚注
  1. argument(論拠, 根拠)の類義語にproof(証明)があります。ゼロ知識証明の文脈では、proofは偽造しようのない証拠、argumentは非常に長い計算時間(例えば、指数関数時間)をかければ偽造できる証拠を意味します。すなわち、argumentは計算量的仮定が必要なproofという意味で使われています。ただし、Pinocchioの原論文でもargumentの意味でproofが使われている箇所があるので、あまり厳密に区別するものでもないのかもしれません。この記事でも以降はargumentとproofは同一の意味で使っています。 ↩︎

  2. ただし、proofの作成はf(x, y)の計算より多くの計算が必要なので、Proverも含めた全体の計算コストはむしろ増えます。 ↩︎

  3. 量子コンピューターを使うと離散対数問題が効率的に解けることが知られています。 ↩︎

  4. 今回はG_1, G_2の演算を積として表記したので、「双線形」っぽくないですが、本来の文脈ではG_1,G_2は楕円曲線上の点の和に関する群なのでe(p_1+p_2, q) = e(p_1, q)e(p_2, q)などとなり、「双線形」がしっくりきます。 ↩︎

  5. f(x),g(x)は未知なので直接係数を比較したりはできませんが、xを入力するとf(x),g(x)を出力するクエリは利用できるものとします ↩︎

  6. v_iからE(v_i)が作れるのでE(v_i)は不要ですが、わかりやすさの為に残しています ↩︎

  7. このプロコトルではv_{\mathrm{i/o}}(s), w_{\mathrm{i/o}}(s), y_{\mathrm{i/o}}(s)を計算するのに3N回の計算が必要ですが、入出力を全て左ワイヤ、すなわちv_{\mathrm{i/o}}(s)に押し付けるとN回の計算で済みます(原論文ではそちらの手法が取られています)。 ↩︎

Discussion

ログインするとコメントできます