zk-SNARKsを構成する4つの技術を解説する

はじめに

vitalikが自身のブログでも言及していたzkSNARKs in a nutshell | Ethereum Foundation Blogを読み、日本語の翻訳がなかったので和訳してまとめました。

zk-SNARKsとは

非対話型ゼロ知識証明の一種。暗号資産ZCashはトランザクションの記録にこれを利用しています。

第三者にとって、「トランザクションが正当に行われたことは確かめられるが、送金者や受取人、送金額などそれ以外の情報はわからない」となるような手続きを実現するプロトコルです。

zk-SNARKsはJ.P. MorganのQuorumなどで実装されており、イーサリアムでもMetropolisアップデートで実装されました。

それでは解説を見ていきましょう。

zkSNARKs in a nutshell

• zkSNARK は難解
• しかしざっくり 4 つの単純な技術に還元することができる

A) 多項式問題としてのエンコード

• 検査対象のプログラムは, $t(x) h(x) = w(x) v(x)$ という多項式の二次式に編纂される
• 証明者は, この等式が成り立つことを検証者に納得させたいと考えている

B) ランダムサンプリングによる簡約化

• 検証者は秘密の評価点$s$を選び, 多項式の乗算と多項式関数の等式検証から, 単純な乗算と数の等式検証へと問題を縮小する: $t(s)h(s) = w(s)v(s)$
• これにより, 証明サイズと検証時間の両方が大幅に短縮される

C) 同型符号化・暗号化

• 同型性を持つ符号化・暗号化関数$E$を用いる (ただし, 完全な同型ではない, まだ実用化されていないもの)
• これにより証明者は, $E(s)$といくつかの暗号化された値のみを知り, $s$を知らなくても $E(t(s)), E(h(s)), E(w(s)), E(v(s))$ を計算することができるようになる

D) ゼロ知識

• 検証者が真の暗号化された値を知らなくても, その正しい構造(structure)をチェックできるように, 証明者は値 $E(t(s)), E(h(s)), E(w(s)), E(v(s))$ にある数を掛けて変更(permutes)する
• 大雑把に言うと, ランダムな秘密数$k \neq 0$に対して, $t(s)h(s) = w(s)v(s)$の評価と$t(s)h(s)k = w(s)v(s)k$の評価は同じで, ただし, $(t(s)h(s) k)$ と $(w(s)v(s) k)$ だけ送られると, $t(s)h(s)$ も $w(s)v(s)$ も導出できず, その点で異なる.

RSA とゼロ知識証明

• RSA の仕組みについて簡単に復習
• 整数全体ではなく, ある数の剰余を扱う
• ここでは「$a + b ≡ c \ \pmod n$」と表記し, 「$(a + b) \ \% \ n = c \ \% \ n$」を意味する
  • なお, 「$\pmod n$」の部分は右辺の「$c$」ではなく, 実際には同じ式中の「$\equiv$」と「$\equiv$」以外に適用される

証明者は次のような数字を用意する.

• $p, q$: 2 つのランダムな秘密の素数
• $n \coloneqq p q$
• $d: 1 < d < n - 1$ となるような乱数
• $e: d e \equiv 1 \pmod {(p-1)(q-1)}$ となるような数

公開鍵は $(e, n)$ であり, 秘密鍵は $d$ . 素数 $p$ と $q$ は捨ててもよいが, 明らかにしてはならない.

暗号化: メッセージ$m$に対して $E(m) \coloneqq m^e \ \% \ n$
復号化: $c = E(m)$ に対して $D(c) \coloneqq c^d \ \% \ n$

$c^d \equiv (m^e \ \% \ n)^d \equiv m^{ed} \pmod n$であることと, $m$ の指数における乗算は $(p-1)(q-1)$ の乗法群における乗算と同様に振る舞うことから, $m^{ed} \equiv m \pmod n$ が得られる. さらに, RSA の安全性は, $n$ が効率的に因数分解できないこと, したがって $e$ から $d$ が計算できないこと ($p$ と $q$ がわかっていれば簡単なこと) に依存している.

• RSA の顕著な特徴の 1 つは, 乗法的に同型であること
  • 一般に, 2 つの演算の順序を入れ替えても結果に影響がない場合, 同型と呼ぶ
  • 同型暗号の場合は, 暗号化されたデータに対して計算を行うことができるという性質がある
  • 存在するがまだ実用化されていない, 完全な同型暗号は, 暗号化されたデータに対して任意のプログラムを評価できるようになる
  • ここでは RSA の場合で, 群間乗算の話だけをしている
  • よりフォーマルには $E(x) E(y) \equiv x^e y^e \equiv (xy)^e \equiv E(x y) \pmod n$
  • 要するに, 2 つのメッセージの暗号化の積は, メッセージの積の暗号化に等しい.
• この同型性により, 既にある種のゼロ知識による乗算の証明が可能
  • 証明者はある秘密の数 $x$ と $y$ を知っていて, それらの積を計算するが, 暗号化されたバージョン $a = E(x)$, $b = E(y)$ and $c = E(x y)$のみを検証者に送る
  • ここで検証者は, $(a b) \ \% \ n \equiv c \ \% \ n$ をチェックし, 検証者が知るのは積の暗号化されたバージョンと, 積が正しく計算されたことだけで, 2 つの因数も実際の積も知らない
  • 積を足し算に置き換えると, これはもう, 残高を足すことがメインの操作であるブロックチェーンの方向に行ってしまう

対話型検証

• ゼロ知識の次に zkSNARKs のもう一つの主要な特徴である簡潔性に焦点を当てる
• zkSNARKs の特筆すべき点はその簡潔さ
  • なぜなら, ゼロ知識パートは, 限定された形の同型符号化を可能にするある符号化によって「無料で」提供されることになるから

SNARKs とは, succinct non-interactive arguments of knowledge の略称. この一般的な対話型プロトコルでは, 証明者 (prover) と 検証者 (verifier) がいて, メッセージを交換することによって, 証明者は検証者にある文(statement)[例: $f(x)=y$]を納得させたい. 一般に望まれる特性は, 間違った文について検証者を説得できないこと（健全性, soundness）と, 任意の真の文について検証者を説得するための一定の戦略が存在すること（完全性, completeness）. 頭字語の各部分は次のような意味:

• Succient: 実際の計算の長さに比べて, メッセージのサイズが小さい.
• Non-interactive: 対話が全くないか, あってもごくわずか. zkSNARK の場合, 通常はセットアップ段階があり, その後, 証明者から検証者へのメッセージが 1 つだけある. さらに, SNARK はいわゆる「公開検証者」の性質を持つことが多い. これは, 誰もが新たに対話することなく検証できることを意味し, ブロックチェーンにとって重要.
• ARguments: 検証者は, 計算能力の限られた証明者からは守られる. 十分な計算能力を持つ証明者は, 間違った文についての証明・論証を作ることができる（十分な計算能力があれば, どんな公開鍵暗号も破ることができる）. これは, 「完全な健全性」に対して「計算上の健全性」とも呼ばれる.
• of Knowladge: 証明者は, ある種の witness（例えば, 使いたいアドレス, ハッシュ関数の preimage, あるマークルツリーのノードへのパス）を知らないと証明・論証を構成することができない.

ゼロ知識という接頭辞をつけると, 検証者は対話の間, 文の正当性以外には何も知らなくてよい という性質も必要になる(大雑把に言えば). 特に, 検証者は witness-string を知らない. それが具体的にどのようなものかは後述する.

• 例として, 次のようなトランザクション検証計算を考える: $f(\sigma_1, \sigma_2, s, r, v, p_s, p_r, v) = 1$
  • $\sigma_1$, $\sigma_2$: アカウントのマークルツリーの前状態および後状態のルートハッシュ
  • $s$, $r$: 送信者および受信者のアカウント
  • $p_s$, $p_r$: $s$の残高が$\sigma_1$において少なくとも$v$であることを証明するマークルツリーの証明, そして$v$が$s$の残高から$r$の残高へ移動した場合, それらは$\sigma_1$のかわりに$\sigma_2$へハッシュする
• すべての入力が既知であれば, $f$の計算を検証することは比較的容易である.
• そのため, $f$を$\sigma_1$と$\sigma_2$だけが公知で, $(s, r, v, p_s, p_r, v)$が witness-string である zkSNARK にすることができる
• ゼロ知識のプロパティにより, 検証者は, 正しい取引に関するいかなる要件にも違反しない方法でルートハッシュを$\sigma_1$から$\sigma_2$に変えるある witness を知っているが, 誰が誰にいくら送金したか分からない
• ゼロ知識の正式な定義（詳細は割愛）は, 設定文字列を生成し, 秘密の witness を知らないシミュレータが存在し, 検証者と対話することができるが, 外部の観測者はこの対話を本物の証明者との対話と区別することができない, というもの

NP と複雑系理論に基づく漸近法

zkSNARK がどのような問題や計算に使用できるかを確認するために, 複雑性理論からいくつかの概念を定義する. witness とは何か, ゼロ知識証明を「読ん」でもわからないことは何か, 多項式に関する特定の問題にのみ zkSNARK があってもよい理由は何か, などについては気にしないのであれば, このセクションは読み飛ばしてかまわない.

P と NP

まず, 0 か 1 しか出力しない関数に限定して, そのような関数を問題 (probrems)と呼ぶことにする. 長い結果の各ビットを個別にクエリできるので, これは現実的な制限ではないが, 理論的にはかなり楽になる. さて, 与えられた問題を解く(関数を計算する)ことがどれだけ「複雑」かを測りたい. 数学関数 $f$ の特定の機械実装 $M$ について, 特定の入力 $x$ に対して $f$ を計算するのにかかるステップの数を常に数えることができる. これを $x$ に対する $M$ の実行時間と呼ぶ. 通常, プログラムは大きな入力に対してより長い時間を要するので, この実行時間は常に入力のサイズまたは長さ(ビット数)で測定される. ここで, 例えば「$n^2$ アルゴリズム」という概念が生まれる. これは, サイズ $n$ の入力に対して最大 $n^2$ のステップを要するアルゴリズムのことである.

ある $k$ に対して実行時間が最大 $n^k$ であるプログラムは, 「多項式時間プログラム」とも呼ばれる.

複雑さ理論の主要な問題のクラスは P と NP の 2 つ:

• P は多項式時間プログラムを持つ問題 L のクラスである.

指数 $k$ がかなり大きくなる問題もあるが, P は「実現可能な」問題のクラスと考えられており, 実際, 人工的でない問題では, $k$ は通常 4 より大きくはない. ビットコイン取引の検証は, 多項式を評価（そして値を $0$ か $1$ に制限）している, P の問題である. 大雑把に言うと, 値を計算するだけで, 何かを「探索」する必要がない場合, その問題はほとんど P の問題である.

クラス NP

NP クラスの全ての問題に対して zkSNARK が存在し, 実際, 現在存在する実用的な zkSNARK は NP の全ての問題に汎用的に適用することができる. NP 以外の問題に対する zkSNARK が存在するかは不明である.

NP 内のすべての問題は, NP の定義に由来するある種の構造を常に持っている:

• NP とは, ある事実を検証するための多項式時間プログラム V を持つ問題 L のクラスであり, そのプログラムは, その事実に対する多項式サイズのいわゆる witness が与えられたときに, その事実を検証するために使用することができる.
• More formally: $V(x, w) = 1$ となるような多項式サイズの文字列 $w$ (witness と呼ぶ) が存在する場合, かつその場合に限り, $L(x) = 1$.

NP の問題の例として, ブール式の充足可能性 (SAT) の問題を考えてみよう. そのために, 帰納的な定義でブール式を定義する.

• 変数 $x_1, x_2, x_3,...$はブール式である (変数を表す文字として他の文字も用いる) .
• $f$ がブール式なら, $\neg f$ はブール式 (negation) である.
• $f$ と $g$ がブール式なら, ($f\land g$) と ($f \lor g$) はブール式 (conjunction / and, disjunction / or) である.

文字列 "$((x_1 \land x_2) ∧ \neg x_2)$" はブール式となる.

論理式は, 式が真と評価されるように変数に真理値を割り当てる方法があれば, 充足可能である（ここで, $\neg true$ は偽, $\neg false$ は真, $true \land false$ は偽, などの規則が存在する）. 充足可能問題 SAT は, 充足可能なすべてのブール式の集合である.

• $SAT(f) \coloneqq f$ が充足可能なブール式なら 1, そうでなければ 0

上の例 "$((x_1 \land x_2) ∧ \neg x_2)$" は充足可能ではないので, SAT に入らない. 与えられた式の witness はその満足な代入であり, 変数の代入が満足であることを検証することは, 多項式時間で解くことができる作業である.

P = NP ?

• NP の定義を長さ 0 の witness string に限定すると, P の問題と同じ問題を捉えることになる
  • そのため, P 問題はすべて NP に属する
• 複雑系理論の研究の主要な課題の 1 つは, この 2 つのクラスが実際には異なること, つまり NP には P にない問題があることを示すこと
  • これは当たり前っぽいが, もし正式に証明できれば 100 万米ドルを獲得できる
• その逆, P と NP が等しいことを証明できれば, その金額もさることながら, 暗号通貨がある日突然存在しなくなる可能性が大きい (余談)
  • なぜなら, Proof of work のパズル, ハッシュ関数の衝突, アドレスに対応する秘密鍵の解を見つけるのがずっと簡単になるから
  • それらはすべて NP の問題であり, P = NP だとすれば多項式時間プログラムが存在するはず
  • ただ実際はほとんどの研究者は P と NP はイコールではないと考えている

NP 完全

SAT に話を戻す. この一見単純な問題の興味深い性質は, NP に属するだけでなく, NP 完全であることだ. ここでいう「完全」とは, 「チューリング完全」と同じ完全である. これは, NP の中で最も難しい問題の一つであるという意味だが, より重要なのは, -これが NP 完全の定義だが-, NP のあらゆる問題の入力は, 次の意味で SAT の等価入力に変換できること.

任意の NP 問題 L に対して, いわゆる簡約関数 (reduction function) $f$ が存在し, それは多項式時間で計算可能であり, 次のようなもの:

$$L(x) = SAT(f(x))$$

このような reduction function は, コンパイラと見なすことができる: あるプログラミング言語で書かれたソースコードを, ある意味での振る舞いを持つ別のプログラミング言語（通常は機械語）で書かれた同等のプログラムに変換するのである. SAT は NP 完全であるため, このような reduction は NP のあらゆる問題に対して存在し, 例えば, ビットコインの取引が適切なブロックハッシュを与えられたときに有効かどうかをチェックする問題にも存在する. 取引を論理式に変換する reduction function があり, その式は取引が有効である場合にのみ満たすことができる.

簡約式 (Reduction) の例

このような reduction を見るために, 多項式の評価の問題を考える. まず, 多項式を, 整数の定数, 変数, 加算, 減算, 乗算, 括弧からなる式と定義する. さて, 考えたい問題は

• $f$ が $0$ を持つ多項式であり, その変数が集合 $\{0, 1\}$ から取られる場合, $PolyZero(f) \coloneqq 1$

SAT から $PolyZero$ への reduction を構築し, $PolyZero$ も NP 完全であることを示す.

ブール式の構造要素に reduction 関数 $r$ を定義すればよい. これは, 任意のブール式 $f$ に対して, 値 $r(f)$ は同じ数の変数を持つ多項式で, $f(a_1, ..., a_k)$ は, $r(f)(a_1, ..., a_k)$ が $0$ の場合, かつその場合に限り真となり, 真は $1$ に, 偽は $0$ に対応し, $r(f)$ は $\{0, 1\}$ からの変数でのみ $0$ または $1$ を想定していることである.

$$\begin{align*} r\left(x_{i}\right) &:= \left(1-x_{i}\right) \\ r(\neg f) &:= (1-r(f)) \\ r((f \wedge g)) &:= (1-(1-r(f))(1-r(g))) \\ r((f \vee g)) &:= r(f) r(g) \end{align*}$$

$r((f \wedge g))$ が $r(f) + r(g)$ という定義でないのは, 多項式の値が $\{0, 1\}$ の集合から外れてしまうから.

$r$ を用いて, $((x \wedge y) \vee \neg x)$ という式は, $(1 - (1 - x))(1 - (1 - y)(1 - (1 - x))$ と変換される.

なお, $r$ の各置換ルールは上記の目標を満たすので, $r$ は正しく reduction を実行する:

• $r(f)$ が $\{0, 1\}$ に $0$ を持つ場合, またその場合に限り, $SAT(f) = PolyZero(r(f))$ または, $f$ は満足される.

Witness Preservation

• この例から, reduction 関数は入力をどのように変換するかを定義しているに過ぎないことがわかる
• しかしより詳しく見てみると (あるいは, reduction が有効であることの証明を読んでみると), 入力と一緒に有効な witness を変換する方法も見えてくる
• 今回の例では, 数式を多項式に変換する方法だけを定義したが, 証明と共に, witness を, 充足する割り当てに変換する方法を説明した
• この witness の同時変換はトランザクションでは必要ないが, 普通は行われる
  • これは zkSNARK にとって非常に重要なことで, 証明者の唯一の仕事は, そのような witness が存在することを, witness に関する情報を明かすことなく, 検証者に納得させることだから

Quadratic Span Programs (QSP)

QAP (Quadratic arithmetic Programs) は, 大きな体の算術回路を「自然に」計算することができる QSP の変形. QAP は QSP よりも性能的に有利な場合が多い. QSP は 2 組の多項式をブール回路で解くが, QAP は 3 組以上の多項式を算術回路で解く. (Gennaro, R., Gentry, C., Parno, B. & Raykova, M., (2012), Quadratic Span Programs and Succinct NIZKs without PCPs より)

前節では, NP 内の計算問題がどのように互いに還元 (reduce) できるか, 特に, NP 内の他のすべての問題（トランザクション検証問題を含む）の基本的に再定式化に過ぎない NP 完全問題が存在することを見た. このことは, NP のすべての問題に対する一般的な zkSNARK を見つけることを容易にする: 我々は適切な NP 完全問題を選ぶだけである. つまり, zkSNARK を使ってどのように取引を検証するかを示したい場合, NP 完全で, おそらく理論的にはるかに取り組みやすい特定の問題に対してそれを行う方法を示せば十分.

この章と次の章は, 論文GGPR12（リンク先の技術報告には論文より多くの情報がある）に基づいており, 著者らは Quadratic Span Programs（QSP）という問題が zkSNARKs に特に適していることを発見した. Quadratic Span Programs は, 多項式の集合からなり, 与えられた別の多項式の倍数であるそれらの線形結合を見つけることが課題である. さらに, 入力文字列の個々のビットによって, 使用できる多項式が制限される. 詳しくは（一般的な QSP はもう少し緩やかだが, 後で使うので強いバージョンを既に定義している）:

長さ $n$ の入力に対する体 F 上の QSP は次のように構成される.

• この体 F 上の多項式 $v_0,...,v_m, w_0,...,w_m$ の集合
• F 上の多項式 $t$（目的多項式）
• 射影関数 $f: \{(i, j) | 1 ≤ i ≤ n, j \in \{0, 1\}\}. → \{1, ..., m\}$

ここでの作業を大まかにいうと, 多項式に係数を掛けて, その和（線形結合）が $t$ の倍数になるように足し合わせること. 各 2 値入力文字列 $u$ に対して, 関数 $f$ は線形結合で使用できる多項式, より具体的にはその係数を制限している. 形式的には,

入力 $u$ は, 以下のような体 F 上のタプル $a = (a_1,...,a_m), b = (b_1,...,b_m)$ がある場合にのみ, QSP に accept される（認証される）.

• $i$ に対して, もし $k=f(i, u[i])$ ならば $a_{k}, b_{k}=1$
• $i$ に対して, もし $k=f(i, 1-u[i])$ ならば $a_{k}, b_{k}=0$
• ターゲット多項式 $t$ は $v_{a} w_{b}$ を割り切る
  • ただし $v_{a}=v_{0}+a_{1} v_{0}+\ldots+a_{m} v_{m}, w_{b}=w_{0}+b_{1} w_{0}+\ldots+b_{m} w_{m}$

$u[i]$ は $u$ の $i$ 番目の bit

$2n$ が $m$ より小さい場合, タプル $a$ と $b$ の選択にはまだ自由があることに注意. これは QSP があるサイズまでの入力に対してしか意味をなさないことを意味する.

$n$ でなく $2n$ なのは $j$ が $\{0 ,1\}$ を取れるので入力パターンが $2n$ 個あるから

ブール式の充足可能性に例えると, 係数 $a_1,...,a_m, b_1,...,b_m$ は変数への代入, つまり一般的には NP の witness と見ることができる. QSP が NP であることを確認するには次のことに注意する. 検証者がしなければならないのは（彼女が係数を知っていれば）, 多項式 $t$ が $v_a w_b$ を除算することをチェックすることだけで, これは多項式時間問題.

一般的な計算や回路から QSP への reduction については, 一般的な概念の理解に寄与しないのでここでは触れまない. 従って, QSP は NP 完全（いやむしろ, NP/poly のような非一様なアナログでは完全）であることを信じてもらわなければならない. 実際には, reduction は実際の「エンジニアリング」な部分である. それは, 結果として得られる QSP ができるだけ小さくなるように, また, 他のいくつかの良い特徴を持つように, 巧妙な方法で行われなければならない.

QSP について, すでに見えていることの 1 つは, より効率的に検証する方法である: 検証作業は, ある多項式が別の多項式を割り切るかどうかを調べることからなる. これは, 証明者が $t h = v_a w_b$ となるような別の多項式 $h$ を与えることで, このタスクが多項式の恒等式をチェックすることになり, 言い換えれば, $t h - v_a w_b = 0$, つまり, ある多項式がゼロ多項式であることをチェックすることになる. これは簡単そうに見えるが, 後で使う多項式は非常に大きく（次数は元の回路のゲート数の約 100 倍）, 2 つの多項式の掛け算は簡単な作業ではない.

そこで検証者は, $v_a, w_b$ とその積を実際に計算する代わりに, 秘密のランダムな点 $s$ (この点は zCash の "toxic waste" の一部) を選び, すべての $k$ について数 $t(s), v_k(s), w_k(s)$ とそこから $v_a(s), w_b(s)$ を計算して, $t(s) h(s) = v_a(s) w_b (s)$ をチェックするだけとする. つまり, たくさんの, 多項式の加算, スカラーとの乗算, 多項式の積が, 体の乗算と加算に単純化される.

toxic waste = 有害廃棄物: Zcash がセットアップでパラメータの作成に使用するランダムサンプリングされた乱数

多項式の同一性を全点ではなく一点のみでチェックすると, もちろん安全性は低下するが, $t h - v_a w_b$ がゼロ多項式でない場合に, 証明者が不正を行えるのは, その多項式のゼロを当てることに成功した場合のみである. しかし, 彼女は $s$ を知らないので, $s$ の可能性（フィールド要素の数）に比べてゼロの数はごくわずか（多項式の次数）であり, これは実際には非常に安全である.

Schwartz-Zippel の補題 (近日加筆予定) について言っていると思われる

zkSNARK の詳細

ここで, QSP の zkSNARK を詳細に説明する. これは, QSP ごとに実行されなければならないセットアップ段階から始まる. zCash では, 回路（トランザクション検証者）が固定されているため, QSP の多項式は固定されており, セットアップは一度だけ実行され, 入力 $u$ を変化させるだけのすべてのトランザクションに再利用される. 共通参照文字列（CRS）を生成するセットアップでは, 検証者はランダムかつ秘密のフィールド要素 $s$ を選び, その点で多項式の値を暗号化する. 検証者は何らかの特定の暗号 $E$ を用い, $E(v_k(s))$ と $E(w_k(s))$ を CRS で公開する. CRS には他にもいくつかの値が含まれていて, 検証を効率化し, またゼロ知識特性を付加している. そこで使われる暗号 $E$ はある種の同型性を持っており, これによって証明者は $v_k(s)$ を実際に知らなくても $E(v(s))$ を計算することができる.

多項式を簡潔かつゼロ知識で評価する方法

まず, より単純なケース, つまり, QSP 問題全体ではなく, 秘密の点における多項式の暗号化された評価について見てみる.

ここで，群（通常は楕円曲線）と生成元 $g$ を固定する．群の要素を生成元と呼ぶのは, リスト $g^0, g^1, g^2, ..., g^{n-1}$ に群のすべての要素が含まれる数 $n$（群の位数）が存在する場合である．暗号化は, 単に $E(x) := g^x$ となる. さて, 検証者は秘密の体要素 $s$ を選び, (CRS の一部として)次のものを公開する.

• $E(s^0), E(s^1), ..., E(s^d)$, $d$ は全ての多項式の最大次数

その後, $s$ は忘れることができる（忘れる必要がある）. これはまさに zCash における toxic waste であり, もし誰かがこの値や後で選んだ他の秘密値を復元することができれば, 多項式にゼロを見つけることによって任意に証明を詐称することができるからである.

これらの値を用いれば, 証明者は $s$ を知らなくても任意の多項式 $f$ について $E(f(s))$ を計算することができる. 多項式を

$$f(x) = 4x^2 + 2x + 4$$

と仮定して

$$E(f(s))$$

を計算したい場合,

$$E(f(s)) = E(4s^2 + 2s + 4) = g^{4s^2 + 2s + 4} = E(s^2)^4 E(s^1)^2 E(s^0)^4$$

が得られ, これは公開されている CRS から $s$ を知ることなく計算することができる.

ここで唯一の問題は, $s$ が破棄されたため, 検証者は, 証明者が多項式を正しく評価したことを確認できないことである. そのため, 別の秘密場要素 $\alpha$ も選び, 以下のような「ずらした」("shifted") 値を公開する.

$$E( \alpha s^0), E( \alpha s^1), ..., E( \alpha s^d).$$

$s$ と同様に, 値 $\alpha$ もセットアップ段階の後に破棄され, 証明者も検証者も知ることはできない. これらの暗号化された値を用いて, 証明者は同様に $E( \alpha f(s))$ を計算することができる. この例では,

$$E(4 \alpha s^2 + 2 \alpha s + 4 \alpha ) = E( \alpha s^2)^4 E( \alpha s^1)^2 E( \alpha s^0)^4.$$

そこで証明者は $A := E(f(s))$ と $B := E( \alpha f(s)))$ を公開し, 検証者はこれらの値が一致しているかチェックしなければならない. 検証者は, もう一つの主要な要素を用いてこれを行う. 楕円曲線とペアリング関数は, すべての $x, y$ に対して以下の性質が成り立つように, 一緒に選ばなければならない.

$$e(g^x, g^y) = e(g, g)^{xy}.$$

このペアリング関数を用いて, 検証者は $e(A, g^α) = e(B, g)$ をチェックする - $g^α$ は $E(αs^0)$ として CRS の一部であるため検証者には既知であることに注意. このチェックが, 証明者が不正をしていない場合に有効であることを確認するために, 以下の等式を見てみる:

$$\begin{aligned} &e\left(A, g^{\alpha}\right)=e\left(g^{f(s)}, g^{\alpha}\right)=e(g, g)^{\alpha f(s)} \\ &e(B, g)=e\left(g^{\alpha f(s)}, g\right)=e(g, g)^{\alpha f(s)} \end{aligned}$$

しかし, より重要なのは, $e\left(A, g^{\alpha}\right)=$ $e(B, g)$ のチェックを満たすが, それぞれ $E(f(s))$, $E(a f(s)))$ でない値 $A$, $B$ を何とかして証明者が思いつけるかという問題である. この問いに対する答えは, 「そうでないことを望む」である. 真面目な話, これは「d-power knowledge of exponent assumption」と呼ばれ, 不正を働いた証明者がそのようなことをできるかどうかは未知数である. この仮定は, 他の公開鍵暗号方式の安全性を証明するために行われる, 同様に真偽が不明な仮定の延長線上にあるものである.

実際, 上記のプロトコルでは, 検証者が多項式 $f(x)= 4x^2 + 2x + 4$ を評価したことを検証者が確認することはできない. 検証者は, 証明者が点 $s$ で多項式を評価したことのみを確認できる. QSP の zkSNARK には, 証明者が実際に正しい多項式を評価したことを検証者が確認できるようにする別の値が含まれる.

この例からわかることは, 検証者はこれを確認するために多項式をすべて評価する必要はなく, ペアリング関数を評価すれば十分であるということです. 次のステップでは, ゼロ知識部分を追加し, 検証者は $f(s)$ はおろか, 暗号化された値である $E(f(s))$ からでさえ何も再構成できないようにする.

そのために, 証明者はランダムな $\delta$ を選び, $A:=E(f(s))$ と $B:=E(\alpha f(s))$ の代わりに $A^{\prime}:=E(\delta+f(s))$ と $\left.B:=E(a(\delta+f(s))\right)$ を送り返す. 暗号が破られないと仮定すれば, ゼロ知識性は極めて明白である. ここで, 2 つのことを確認しなければならない.

1. 証明者が実際にこれらの値を計算できること
2. 検証者によるチェックが依然として真であること.

1.について,

$$\begin{aligned} A^{\prime}&=E(\delta+f(s)) \\ &=g^{\delta+f(s)} \\ &=g^{\delta} g^{f(s)} \\ &=E(\delta) E(f(s)) \\ &=E(\delta) A \end{aligned}$$

であることに注意し, 同様に

$$\begin{aligned} B^{\prime}&=E(\alpha(\delta+f(s))) \\ &=E(\alpha \delta+\alpha f(s)) \\ &=g^{\alpha \delta+\alpha f(s)} \\ &=g^{\alpha \delta}g^{\alpha f(s)} \\ &=E(\alpha)^{\delta} E(\alpha f(s)) \\ &=E(\alpha)^{\delta} B. \end{aligned}$$

2.について, 検証者が確認するのは, 受け取った値 $A$ と $B$ が, ある値 $a$ に対して $A=E(a)$ と $B=E(\alpha a)$ の式を満たすことだけであり, これは明らかに $a=f(s)$ と同じような, $a=\delta+f(s)$の場合であることに注意.

QSP 問題に対する SNARK

QSP では, 多項式 $v_0,...,v_m, w_0,...,w_m,$ 目標多項式 $t$ (次数は最大 $d$) および 2 進の入力文字列 $u$ が与えられることを思い出す. 証明者は, $a_1,...,a_m, b_1,...,b_m$ ($u$ に依存して多少制限される)と, 次のような多項式 $h$ を見つける.

$$t h = (v_0 + a_1v_1 + ... + a_mv_m) (w_0 + b_1w_1 + ... + b_mw_m).$$

前節で, 共通参照文字列 (CRS) の設定方法を既に説明した. 秘密の値 $s$ と $α$ を選び, 次の

$E(s^0), E(s^1), ..., E(s^d)$ 及び $E(αs^0), E(αs^1), ..., E(αs^d).$

を公開する.

多項式は一つではなく, 問題に対して固定された多項式の集合であるため, 評価した多項式もすぐに公開する:

• $E(t(s)), E(\alpha t(s))$,
• $E\left(v_{0}(s)\right), \ldots, E\left(v_{m}(s)\right), E\left(\alpha v_{0}(s)\right), \ldots, E\left(\alpha v_{m}(s)\right)$,
• $E\left(w_{0}(s)\right), \ldots, E\left(w_{m}(s)\right), E\left(\alpha w_{0}(s)\right), \ldots, E\left(\alpha w_{m}(s)\right)$

そしてさらに秘密の値 $\beta_{v}, \beta_{w}, \gamma$ が必要であり(これらはこれらの多項式が評価され, 任意の多項式ではないことを検証するために使用される),

• $E(\gamma), E\left(\beta_{v} \gamma\right), E\left(\beta_{w} \gamma\right)$,
• $E\left(\beta_{v} v_{1}(s)\right), \ldots, E\left(\beta_{v} v_{m}(s)\right)$
• $E\left(\beta_{w} w_{1}(s)\right), \ldots, E\left(\beta_{w} w_{m}(s)\right)$
• $E\left(\beta_{v} t(s)\right), E\left(\beta_{w} t(s)\right)$

を公開する.

これは完全な共通参照文字列である. 実際の実装では, CRS の一部の要素は必要ないが, そうすると表現が複雑になる.

さて, 証明者はどうするのか？上で説明した reduction (還元, 簡約) を用いて, 多項式 $h$ と値 $a_{1}, \ldots, a_{m}, b_{1}, \ldots, b_{m}$ を求める. ここで, witness-preserving reduction を用いることが重要(上記参照). なぜなら, reduction を使って初めて, 値 $a_{1}, \ldots, a_{m}, b_{1}, \ldots, b_{m}$ を計算でき, そうしなければ見つけることは非常に困難だからである. 証明者が検証者に何を証明として送るかを説明するために, QSP の定義に戻る必要がある.

$a_{1}, \ldots, a_{m}, b_{1}, \ldots, b_{m}$ の値を制限する射影関数 $f:\{(i, j) \mid 1 \leq i \leq n, j \in\{0,1\}\} \rightarrow\{1, \ldots, m\}$ が存在した. $m$は比較的大きいので, どの入力に対しても$f$の出力に現れない数字が存在する. これらのインデックスは制限されないので, $I_{free}$ と呼び, $v_{free}(x)=\Sigma_{k} a_{k} v_{k}(x)$ と定義する. ただし $k$ は $I_{free}$のすべてのインデックスの範囲. $w(x)=b_{1} w_{1}(x)+\ldots+b_{m} w_{m}(x)$について, 証明は以下のようになる:

• $V_{{free }}:=E\left(v_{{free }}(s)\right), W:=E(w(s)), H:=E(h(s))$,
• $V_{{free }}^{\prime}:=E\left(\alpha v_{{free }}(s)\right), W^{\prime}:=E(\alpha w(s)), H^{\prime}:=E(a h(s))$,
• $Y:=E\left(\beta_{v} v_{{free }}(s)+\beta_{w} w(s)\right)$

ここで, $Y$ は正しい多項式が使われたことを確認するために使われる (これは他の例でまだ取り上げていない). これらの暗号化された値はすべて, 証明者が CRS だけを知っていれば生成できることに注意.

検証者の仕事は次のようなもの:

$k$ が「free」インデックスではない $a_k$ の値は入力 $u$ から直接計算できるので (これも検証者は知っている. これが検証されるものである), 検証者は $v$ の完全な和の足りない部分を計算することができる:

• $I_{free}$ に含まれない全てのインデックスを網羅する $k$ に対し $E(v_{in}(s))=\Sigma_{k} a_{k} v_{k}(s)$

これで検証者は, ペアリング関数 $e$ を用いて, 以下の等式を確認することになる:

1. $e\left(V_{{free}}^{\prime}, g\right)=e\left(V_{{free}}, g^{\alpha}\right), \quad e\left(W^{\prime}, E(1)\right)=e(W, E(\alpha)), \quad e\left(H^{\prime}, E(1)\right)=e(H, E(\alpha))$
2. $e(E(γ), Y) = e(E(β_v γ), V_{free}) e(E(β_w γ), W)$
3. $e\left(E\left(v_{0}(s)\right) E\left(v_{ {in }}(s)\right) V_{{free}}, E\left(w_{0}(s)\right) W\right)=e(H, E(t(s)))$

ここで一般的な概念を理解するためには, ペアリング関数によって, 暗号化された値に対して限られた計算を行うことができることを理解する必要がある: 任意の足し算はできるが, 掛け算は 1 回だけである. これは足し算は, 暗号化自体が既に加法的同型であり, 掛け算はペアリング関数が持つ 2 つの引数によって実現されるから. つまり, $(W', E(1)) = e(W, E(\alpha))$ は基本的に暗号化空間において $W'$に 1 を掛け, それを暗号化空間において $\alpha$ を掛けた $W$ と比較する. $W$ と $W'$ が持つはずの値, $E(w(s))$ と $E(\alpha w(s))$ を調べれば, 証明者が正しい証明を行ったかどうか確認できる.

シークレットポイントでの多項式の評価についてのセクションを思い出すと, これらの 3 つの最初のチェックは, 基本的に, 証明者が CRS 内のパーツから作り上げた多項式を評価したことを確認するもの. 2 番目の項目は, 証明者が任意の多項式ではなく, 正しい多項式 $v$ と $w$ を使用したことを確認するために使用される. これは, 暗号化された組み合わせ $E\left(\beta_{v} v_{{free }}(s)+\beta_{w} w(s)\right)$ を $E\left(v_{{free }}(s)\right)$ と $E(w(s))$ の正確な値以外から計算する方法がないことを意味する. なぜなら, 値 $\beta_{v}$ は単独では CRS の一部ではなく, 値 $v_{k}(s)$ との組み合わせでのみ, $\beta_{w}$ は多項式 $w_{k}(s)$ との組み合わせでのみ知られているからである. これらを「ミックス」する唯一の方法は, 等しく暗号化された $γ$ を経由することである.

証明者が正しい証明をしたと仮定して, 等式がうまくいくことを確認しよう. 左辺と右辺はそれぞれ

• $e(E(\gamma), Y)=e\left(E(\gamma), E\left(\beta_{v} v_{{free}}(s)+\beta_{w} w(s)\right)\right)=e(g, g)^{\gamma\left(\beta_{v} v_{free}(s)+\beta_{w} w(s)\right)}$
• $e(E(β_v γ), V_{free}) e(E(β_w γ), W) = e(E(β_v γ), E(v_{free}(s))) e(E(β_w γ), E(w(s))) = e(g, g)^{(β_v γ) v_{free}(s)} e(g, g)^{(β_w γ) w(s)} = e(g, g)^{γ(β_v v_{free}(s) + β_w w(s))}$

3 番目の項目は, QSP 問題の主要条件である, $\left(v_{0}(s)+a_{1} v_{1}(s)+\ldots+a_{m} v_{m}(s)\right)\left(w_{0}(s)+b_{1} w_{1}(s)+\ldots+b_{m} w_{m}(s)\right)=h(s) t(s)$ を本質的にチェックするものである. $E(x) E(y)=g^{x} g^{y}=$ $g^{x+y}=E(x+y)$ なので, 暗号化された値に対する乗算は, 暗号化されていない値に対する加算に変換されることに注意されたい.

ゼロ知識の追加

• 冒頭で述べたように, zkSNARKS の特長は, ゼロ知識よりもむしろその簡潔さにある
• ゼロ知識の追加方法についてはここから説明し
  • 次章ではその簡潔さについてもう少し説明
• このアイデアは, 証明者がいくつかの値をランダムな秘密の量で「シフト」し, 方程式の反対側でシフトのバランスをとるというもの
• 証明者は, ランダムな$\delta_{free}, \delta_w$を選び, 証明の中で次のような置換を行う

$v_{free}(s)$ -> $v_{free}(s) + \delta_{free} t(s)$
$w(s)$ -> $w(s)$ + $\delta_w t(s)$.

• これらの置き換えにより, witness の因子をエンコードした値 $V_{free}$ と $W$ は基本的にランダムと区別がつかなくなり, witness の抽出が不可能になる
• ほとんどの等式検査は修正に対して「免疫 (immune)」があり, 唯一修正しなければならないのは $H$ または $h(s)$

次の式がまだ成立することを確かめなければならない:

$$\left(v_{0}(s)+a_{1} v_{1}(s)+\ldots+a_{m} v_{m}(s)\right)\left(w_{0}(s)+b_{1} w_{1}(s)+\ldots+b_{m} w_{m}(s)\right)=h(s) t(s)$$

言い換えると

$$\left(v_{0}(s)+v_{i n}(s)+v_{f r e e}(s)\right)\left(w_{0}(s)+w(s)\right)=h(s) t(s)$$

この修正により, 次のようになる:

$$\left(v_{0}(s)+v_{in}(s)+v_{free}(s)+\delta_{free} t(s)\right)\left(w_{0}(s)+w(s)+\delta_{w} t(s)\right)$$

積を展開すると, $h(s)$ を次のように置き換えることができることがわかる:

$$h(s)+\delta_{free}\left(w_{0}(s)+w(s)\right)+\delta_{w}\left(v_{0}(s)+v_{i n}(s)+v_{free}(s)\right)+\left(\delta_{free} \delta_{w}\right) t(s)$$

これを実行すればよい.

入力サイズと Witness サイズのトレードオフ

前節で見たように, witness は群（典型的には楕円曲線）の 7 要素のみからなる. さらに, 検証者がしなければならない作業は, ペアリング関数を含むいくつかの等式をチェックし, $E(v_{in}(s))$ を計算することであり, これは入力サイズに線形な作業である. 驚くべきことに, witness の文字列のサイズも, QSP の検証 (SNARK なし) に必要な計算量も, 検証には何の役にも立たない. つまり, SNARK による極めて複雑な問題の検証も, 非常に単純な問題の検証も, すべて同じ労力を要するということ. その主な理由は, 多項式全体をチェックするのではなく, 1 つのポイントについて多項式の恒等式をチェックするだけだから. 多項式はどんどん複雑になっていくが, 点は常に点. 検証作業に影響を与えるパラメータは, セキュリティのレベル (すなわち群の位数) と入力の最大サイズだけ.

第 2 パラメータである入力サイズについては, 一部を witness にシフトさせることで小さくすることが可能.

$u$ を入力, $w$ を witness とする関数 $f(u, w)$ を検証する代わりに, ハッシュ関数 $h$ を取り出し, 検証する.

$$f^{\prime}(H, (u, w)) \coloneqq f(u, w) \wedge h(u) = H.$$

つまり, 入力 $u$ をそれよりはるかに短いと思われるハッシュ $h(u)$ で置き換え, $f(x, w)$ のチェックに加えて, $H(u)$ とハッシュする (つまり $u$ と非常に等しい可能性が高い) 何らかの値 $x$ が存在することを確認することを意味する. これは基本的に, 元の入力 $u$ を witness の文字列に移動させるので, witness のサイズは大きくなるが, 入力のサイズは一定に減少する.

イーサリアムとの関連

任意計算 (arbitrary computations) の検証はイーサリアムブロックチェーンの中核であるため, zkSNARKs はもちろんイーサリアムと非常に関係が深い. zkSNARKs を使えば, 誰でも検証可能な秘密の任意計算を実行できるだけでなく, これを効率的に実行することも可能になる.

Ethereum はチューリング完全仮想マシンを使用しているが, 現在のところ Ethereum に zkSNARK 検証器 (verifier) を実装することはまだ不可能. verifier のタスクは概念的には単純に見えるかもしれないが, ペアリング関数は実際には計算が非常に難しいため, 現在 1 ブロックに利用できる量よりも多くのガスを使用することになる. 楕円曲線の乗算はすでに比較的複雑で, ペアリングはそれをさらにレベルアップさせる.

zCash のような既存の zkSNARK システムは, すべてのタスクに同じ問題/回路/計算を使用している. zCash の場合, それは取引検証器 (transaction verifier) である. イーサリアムでは, zkSNARK は単一の計算問題に限定されることなく, しかし代わりに, 誰もが新しいブロックチェーンを立ち上げることなく, 自分の専門的な計算問題のための zkSNARK システムを立ち上げることができるようになる. イーサリアムに新しく zkSNARK システムを追加するたびに, 新しい秘密信頼設定フェーズ (一部は再利用可能だが, 全てではない), つまり新しい CRS を生成する必要がある. また, 「一般的な仮想マシン」用の zkSNARK システムを追加するようなことも可能である. これは, Ethereum で新しいスマートコントラクトのために新しいブロックチェーンをブートストラップする必要がないのと同じように, 新しいユースケースのために新しいセットアップを必要としないだろう.

zkSNARK をイーサリアムに取り込む

イーサリアムで zkSNARKs を有効にする方法は複数ある. いずれもペアリング関数と楕円曲線演算の実費を削減し（他の必要な演算はすでに十分安価）, その結果, これらの演算にかかるガスコストも削減することが可能.

1. EVM の(保証された)性能を向上させる
2. 特定のペアリング関数と楕円曲線乗算のみ EVM の性能を向上させる

もちろん, 最初の選択肢は, 長期的にはより良い結果をもたらすものだが, 実現は困難. 私たちは現在, EVM に機能や制限を追加することで, 既存の実装をあまり変更せずに, より良いジャストインタイムコンパイルと解釈を可能にすることに取り組んでいる. もう一つの可能性は, EVM を完全に取り替えて, eWASM のようなものを使用すること.

2 つ目の選択肢は, すべてのイーサリアムクライアントに, 特定の楕円曲線上の特定のペアリング関数と乗算を, いわゆるプリコンパイルコントラクトとして強制的に実装させることで実現できる. メリットは, おそらくこの方がはるかに簡単かつ迅速に実現できること. 一方欠点は, あるペアリング関数とある楕円曲線に固定されてしまうこと. イーサリアム用の新しいクライアントは, これらのプリコンパイルされたコントラクトを再実装しなければならない. さらに, 進化してよりよい zkSNARK やペアリング関数, 楕円曲線が見つかったり, 楕円曲線やペアリング関数, zkSNARK に欠陥が見つかったりすると, 新たにプリコンパイルされたコントラクトを追加しなければならなくなる.

おわりに

いかがでしたでしょうか。zk-SNARKsの記事というとELECTRIC COIN CO. の一連の解説記事やその翻訳記事(こちらのシリーズやこちら)を読まれる方も多いと思います。私はそちらも読みましたが、技術的な解説はこちらの方が簡潔で分かりやすいなと思いました。その後にELECTRIC COIN CO.の記事を読むとさらに理解が深まるかと思います。

マサカリ・質問等お待ちしています。

参考文献

• zkSNARKs in a nutshell | Ethereum Foundation Blog