翻訳： zk-SNARKs 入門 （その1） （原題：Introduction to zk-SNARKs (Part 1)）
どうも、ぺろりんです。
TwitterのDMで怪しげな（笑）アカウントからオススメされたリンク先にあったzk-SNARKsの記事（Introduction to zk-SNARKs (Part 1)）、読んでみたらすごく面白かったｗ
というかこのブログめっちゃ良いぞ！！
……というわけで、自分の勉強がてら翻訳してみました。
皆さんの勉強のご参考になれば幸いです。
そんなに英語が得意なわけではないので、間違いなどあればメールフォームから教えていただけると助かります！
（ちなみに、怪しげなアカウントはdecentriqの公式アカウントですｗ）
この連載では、確率論的なプロトコルの1つで、Goldwasser、Micali、Rackoffにより1985年に初めて記述され、分散台帳技術（DLT）の盛り上がりとともに人気が出てきたゼロ知識証明(ZKPs)について見ていく。まずはこの画期的な仕事の背後にあるいつくかの理論の紹介と、その複雑な機構の種々の要素をどのように実行するのか示すことから始める。Pinocchioプロトコルに従いPythonで実行して、最終的には例題に関するエンドツーエンド[訳注1]のゼロ知識証明になる。主な目標はこのトピックのやさしい入門を提供することで、ZKPsに関する簡潔な数学をかみ砕いて、その背後にあるいくつかの直観的なことを議論する。これに沿って、この技術によって可能になる、いくつかのエキサイティングな応用についても触れる。
そもそも、ZKPとは何のことで、なぜこれを気にしないといけないの？
ZKPは、「証明者（彼女のことはPeggyと呼ぶことにしよう）がある秘密を知っている」ことを秘密の内容を明かさず、承認者（彼のことはVictorと呼ぶことにしよう）にどんな合理的な疑問も残さない証明を与える。たとえばPeggyは、具体的な素因子を明かすことなく非常に大きい合成数の素因数分解を知っていることだったり、解答自体は明かさずに与えられた数独パズルの答えを知っていることをVictorに証明したいのかもしれない。もっと一般的には、ZKPsは検証可能な計算の構成要素として使える：これは弱いクライアントからより計算力の高いワーカーに計算を押し付ける方法で、元のプログラムを実行するのに比べてかなり小さい労力の計算でワーカーが実行した計算の正しさを、クライアントが暗号的学的に証明することができるようなもの。これは、クラウドだけでなく、オンラインのプライバシー、DLTのスケーラビリティや携帯アプリ、その他諸々の応用に影響する非常に強力なパラダイムになっている。
ZKPsについて別の有望な応用は、機械学習の分野にある。この文脈でこの技術は、第三者がモデルのトレーニングや予測の過程で特定のデータが使われたことを証明できるだけでなく、すべてを開示する必要なく特定のデータを持っていることを証明するのに使える。OpenMined は、活発に動いているプライベートでセキュアな機械学習のエコシステムを作るための多重暗号プリミティブ（multiple cryptographic primitives）[訳注2]の先駆的プレジェクト。
だけど、実のところ、ZKPって何？
非常に簡単に言うと、コンピューター上で表現されるとZKPは、Peggyによって注意深く計算され、Victorが計算が正しいことの証明を検証するために実行するたくさんあるブール型のチェックと一緒にして数を並べたものでしかない。したがって、ゼロ知識証明のプロトコルはこれらの数から導かれ、検証の確認で定義される。
ゼロ知識分野での研究は増えていて、Goldwasser, Micali と Rackoff による初めの論文（１，２，３，４，５）が出版されてから色んなプロトコルも提案されている。
これらのプロトコルの主な違いの一つは対話性にある。対話的なゼロ知識プロトコルでは検証者が「証明者がある秘密を知っている」ということを信じられるまで、証明者と検証者がたくさんのメッセージをたがいに交換する。各やり取りのラウンドはVictorによって出された「Peggyが正しい解答を提出しないといけない」問題で、その解答はVictorに検証され、プロトコルによって特徴づけられるブール型のチェックを通過したときにだけ受理される。Peggyがその秘密を知らずにNラウンドすべてチェックに通貨してしまう確率は、Nについて指数関数的に減少する。したがって、Victorは内容については何も知ることがないにもかかわらず、「Peggyがその秘密を知っている」ことをVictorが確信できるまで好きなだけ長く、行ったり来たりするやり取りを続けられる。
逆に、非対話型のゼロ知識プロトコルでは、証明者と検証者の間でやり取りが繰り替えされることがない。代わりにただ1つの"ラウンド"があり、これは非同期的に実行される。公開されているデータ（続くセクションや投稿で議論される予定の内容）を使い、Peggyが証明を作り、Victorが利用できる場所に公開する（たとえば分散台帳上に置く）。これにより、Victorは"ラウンド"完了するため、いつでもその証明を検証できる。対話的な場合はたくさんの証明を作るのに対しPeggyはただ1つの証明を作るとしても、無視できる確率を除き、「彼女が、自分で主張する秘密を確かに知っている」ことを検証者は依然として確信できる。結果的に、非対話型アプローチの利点の1つとして、「検証者に依らない」ことがある。Peggyの証明は、手元にあるその問題の実例（たとえば数独パズル）について普遍的で、Victorだけでなくどんな検証者でも、Peggyの「私は解答を持っている」という主張を後から検証できる。
ゼロ知識プロトコルたちの別の違いは簡潔性にあって、Peggyによって生成される証明のサイズを扱う。簡潔性は、ストレージ容量と検証時間という2つの理由で、分散台帳上に発行されたZKPについて重要な役割を担う。ストレージは非常に高価で、たとえば現時点でビットコイン、イーサリアム、NEO、EOSで各台帳に1KBを保存するときの費用はそれぞれ、$3.83、$2.86、$19.38、$3.00となっていて、ピーク時の費用はもっと高い！変動価格と高価なストレージの効果は、1KBあたり$0.001であるファクトムなどの安価で低価格の分散台帳を使うことで相殺できる。にもかかわらず、証明のサイズはできるだけ小さく保つことが依然として望ましい。加えて証明は素早く検証できることが必要で、そうでないとサードパーティにオフロードする効果が薄れる。したがって、チェーンなしのアプリケーションにとって、検証時間が一定であるだけでなく、生成された証明ができるだけ短くて、理想的には問題の内容によらないことが非常に重要となる。
自然な疑問として、「対話型の証明が好まれる場合があるのか？」ということがある。多くの非対話型プロトコルは、一般に「信頼されたセットアップ」といううるさい問題に悩まされていることがわかるが、これは各々を対話型にした代替プロトコルには存在しない。信頼されたセットアップは、証明を計算するときPeggyに利用される公開データの一部を生成するプロセスにある。このセットアップの詳細は後で議論予定だが、簡単に言うと、このセットアップは、乱数源から発生するある数（一般に「有害廃棄物」と呼ばれる）を公開する集団や、集団が集まった大きな集団による。この乱数源にアクセスする誰もが、プロトコルに従って検証者が受け入れるような偽の証明を生成できる。このような理由で、公開された数を生成する集団によって「有害廃棄物」が破壊されることが重要で、これはこのような集団が信頼される必要があることを意味する。これは実質的に、いつくかの非対話型ゼロ知識プロトコルの適用可能性を扱いにくいものにする。
しかしながら多くの場合、非対話性や簡潔性では大して得をするわけではない。非対話性は、たくさんの独立な検証者が、与えられた証明を各々個別に証明者へ問い合わせを行わずに検証したいときにのみ有用となる。簡潔性は、証明を保存するために使われる中間物が非常に高価か、非常に短い検証時間を求めているときのどちらかまたはこの両方であるときにのみ必要となる。しかしながら、分散台帳は特段の例外として一般にストレージは安価で、パブリックブロックチェーン上のブロック間時間に強いられるような厳しい制約がなければ検証時間もまた柔軟であり得る。
これは、2つの対象がHTTPSのように安全なチャネルを使ってやり取りするようなB2Bアプリケーションでは、対話型の証明でやっていけることを意味する。検証者は信頼されたセットアップを実行する責任があるとして、ユースケースに応じて企業がPeggyかVictorの皮をかぶることができる。このやり取りは自然に1対1なので、検証者は偽の証明には興味がなく、オンチェーンに証明を保存する必要もなく、Victorは検証を実行する時間をより多く割く余裕があり、このようなアプリケーションは対話型の状況ではたらく。
このちょっとした遠回りに続いて、この連載で興味のある主題である、非対話型で簡潔な証明に戻る。特に、ここではゼロ知識（zero-knowledge）で、簡潔（Succinct）かつ非対話型（Non-interactive）の計算による知識証明、またの名を「zk-SNARKs」というものに興味がある。特筆すべきアーリーアダプターの中でも匿名暗号通貨のZcashと、スマートコントラクトのプラットフォームであるEthereumで使われており、zk-SNARKsはゼロ知識プロトコルで最も広く使われている。
zk-SNARKプロトコルをより厳密に説明する前に、いくつかの背景に言及しておかないといけない。
ゼロ知識プロトコル一般に言える複雑なことの1つとして、これらを適用可能にするために、元の問題を完全に変形してやらないといけない、ということがある。
PeggyがVictorに対して、「自分が方程式 x2-4=0 の解を知っている」ことを、この解が何かを明かすことなしに証明したい、という状況を考える。この場合解は自明で、誰でもこの解答を導けるので現実的にはこの問題にゼロ知識証明は不要だが。それもかかわらず、2次多項式に代わってこれを1万次の多項式に簡単に拡張できることを念頭に置きつつ、話を簡単にするために、この連載ではこの例を見る。
それで、この問題をどう読み替えていけば良いのだろうか？
この過程の詳細はVitalik Buterinによる素晴らしい投稿の2次算術プログラム（QAPs：Quadratic Arithmetic Programs）にあり、さらなる読みものとしてこれを強くおすすめする。ここでは、この「変形」の短いまとめを提供する。
まずはコードでこの問題を表すことから始める。すなわちPythonでは、計算を読み替える、次の簡単な関数を定義できる。
Peggyとしては「自分だけが知っているある秘密の値xにおいて上の関数を評価すると、yが0になる」ことが目標。明らかに、少なくとも2つの問題がある。
・xの値は知ることなく、関数を実行する最後にyの値の"ピーク"をVictorが得られる方法を見つける必要がある。
・Peggyはプログラムの実行者なので、コードの今の定式化では、VictorはPeggyが確かに実行したどんなコードも制御できない。たとえば、Peggyは条件を満たすy=0というだけのコードを走らせるズルをすることもできる。
これらの問題のどちらも、解決がとても難しいように見える。当然、この答えは上述した問題のかなり非自明な再定式化を必要とし、すなわちこれのQAPへの変換が必要となる。これは、コードの平坦化（code flattening）、rank 1の拘束系（R1CS： rank-1 constraint system）への変換、最後にQAPの定式化、という3つのステップを踏む。
コード平坦化のゴールは、任意の複雑な主張や表現を含むような元のコードを、次の2つの形からなる一続きの主張に変換することとなる。
・x=y（ここで、yは変数でもある数でも良い）
・x=y（op）z （ここで、op∈（+,-,*,/）であり、yとzは変数でも、ある数でも、部分式でも良い）
これらの主張を算術回路のゲートとして考えられる。ここで出している例のプログラムの回路は、次のように見られる。
（元記事の図も参照）
x -----┐
x ---------→ * ---(out_1)---┐
-4----------------------------→ + ---(y)---→
対応する「平坦化されたコード」は次のようなものになる。
次のステップでは、これをR1CSに変形する。R1CSというのははベクトル（ai, bi, ci）[訳注3]のトリプレットのリストで、この解は、任意の i について
〈ai, s〉 * 〈bi, s〉 - 〈ci, s〉 = 0
を満たすようなベクトル s となる。ここで、〈・,・〉は2つのベクトルのドット積（内積）を表す。このトリプレットは、この方程式を満たすような s を探して満たす必要のあるような拘束条件を定義していると解釈できる。
例に挙げているコードの平坦化したものをR1CSに変換する、自然な方法がある。まずプログラムの主張を満たすようなベクトル（すなわち、プログラム内で使われるすべての変数）を定義する。このベクトルの各成分は1つの変数で、その解 s は各変数を割り当てたものになる。
今のプログラムの変数ベクトルは、次のようなものになる。
s = (1, x, out_1, y)T
1つ目の成分として1を含むのは、後で簡単に見るように、これによって拘束条件を満たすようにするため。
このベクトルを定義して、平坦化したコードの各行を順次処理して適切なai、bi、ciを定義することで、今の行に含まれる計算の読み替えを続ける。
たとえば、この関数の中身で最初の行を読み替えるには、以下のように設定する。
a1 = (0, 1, 0, 0)T
b1 = (0, 1, 0, 0)T
c1 = (0, 0, 1, 0)T
2行目の読み替えには以下を使う。
a2 = (-4, 0, 1, 0)T
b2 = (1, 0, 0, 0)T
c2 = (0, 0, 0, 1)T
この2つの行について、読み替えを展開してチェックしてみる。2行目で-4という定数を表すために、aiの定義のところでsの第1成分で1をどう使うかも見る。
1行目：
〈a1, s〉 * 〈b1, s〉 - 〈c1, s〉
= Σni=1 a1 si * Σni=1 b1 si - Σni=1 c1 si
= x * x - out_1
=0
2行目：
〈a2, s〉 * 〈b2, s〉 - 〈c2, s〉
= Σni=1 a2 si * Σni=1 b2 si - Σni=1 c2 si
= out_1 - 4 - y
=0
上記によって、このPythonプログラムがコンピュータのコードから高速条件の集合へうまく変換された！コードのロジックは制限されたベクトル（ai, bi, ci）のトリプレットに"移送"された。このプログラムの実行は、R1CS方程式
〈ai, s〉 * 〈bi, s〉 - 〈ci, s〉 = 0 （ i は任意）
を満たすようなsの成分を見つけることと等価になっている。
QAPへの変形を完了するのに、ベクトルから多項式へ転換する必要がある。 i ∈ [1, N] として、多項式 Ai(x)、Bi(x)、Ci(x)を定義することから始める。ここで、Nは制限ベクトルの成分の数（今の場合は4）となっている。Ai(n) = an,i （Bi(n)、Ci(n)も同様）と要請し、これらの点に基づいたLagrange補完をすることでこれらの多項式を構成する。
今の例では次のように要請する（Bi、Ciも同様）。
A1(1) = 0
A1(2) = -4
A2(1) = 1
A2(2) = 0
Lagrange補完をすると、次の多項式に到達する。
A1(x) = - 4x + 4
A2(x) = - x + 2
A3(x) = x - 1
A4(x) = 0
B1(x) = x - 1
B2(x) = - x + 2
B3(x) = B4(x) = 0
C1(x) = C2(x) = 0
C3(x) = - x + 2
C4(x) = x - 1
これらの定義によって、今や1つの方程式として上記をR1CSで表現できる。
A(x) * B(x) - C(x) = H(x) * Z(x)
ここで、
A = (A1(x), A2(x), A3(x), A4(x))
B = (B1(x), B2(x), B3(x), B4(x))
C = (C1(x), C2(x), C3(x), C4(x))
A(x) = 〈A, s〉
B(x) = 〈B, s〉
C(x) = 〈C, s〉
Z(x) = (x - 1) (x - 2)
また、H(x)はすべてのxについてA(x) * B(x) - C(x) = H(x) * Z(x)を満たすようなものであると要求する。
まだここ？よろしい！ここで、次のようなことが疑問じゃないだろうか。
・なんでこんなことしたの？
・Z(x)ってなんやねん
・H(x)は何者で、誰が思いつくの？
これらの質問に答えるため、まず次のようなことを見る。定義により
A(1) = a1
A(2) = a2
として、B(x)とC(x)も同様とする。A(x)、B(x)、C(x)の定義も用いると、これは元のR1CS系が以下と等価であることを意味する。
A(x) * B(x) - C(x) = 0 （x∈{1, 2}）
これを満たす唯一の方法は、A(x) * B(x) - C(x)が (x - 1) (x - 2) で割り切れるとき、すなわち以下のような H(x) が存在するときとなる。
A(x) * B(x) - C(x) = H(x) (x - 1) (x - 2)
これはH(x)とZ(x)が何かを明らかにしてくれる。しかし、誰がH(x)を計算するのだろうか？H(x)を(A(x) * B(x) - C(x))/Z(x) として計算することにより、背後にあるR1CSを満たすsの成分を知っていることを示すので、H(x)を計算するのは証明者だろう。したがって大雑把に、QAPを（A, B, C, Z）という4-タプル[訳注4]、sをこのQAPの"解"と考えることができる。
最も大事な質問にまだ答えていない。なぜこんなことをする必要があるのだろうか？
Pythonのプログラムとして今の問題を表現していたことを思い出すと、次のような1組の大きな問題に突き当たる。
・Peggyが正しいプログラムを動かしていることを検証する方法が無い
・他のどのんな情報も明かさずに、プログラム実行の最後におけるyの値をどうやってVictorに観測させるかが明確でない
R1CSとして表現された計算だと、Victor妥当なsの割り当てを見るとすると、Peggyが対応するR1CSのプログラムを実行したことを確信できる！これは主な問題の1つをすでに解決している。
QAPを得るためにR1CSをさらに変形する理由は、多項式で説明する方がR1CSで説明するよりも有益だから。次のセクションではこの新しく提案された「問題の再定式化」を、zk-SNARKsを構成する中心となる1つの技術を説明するのに使うが、これは多項式の構造を利用する。
多項式を処理するうまいやり方の1つに、知らない点で多項式を評価するものがある。これは多項式の目隠し評価（？blind evaluation of polynomials）としても知られる。まってｗつまり……どういうことだってばよ？！そう、お分かりの通りこれは不可能に違いない。与えられた多項式
P(x) = a0 + a1 x + a2 x2 + ... + an xn
について、この多項式を評価したいとすれば、xを知らなければいけない。実際に今はこういう場合だけど、いつくかの追加情報を使えるとすれば、評価するときのその点xを知ることなく、多項式を評価できる！
次に、次のような性質を持つある関数 f(x) を使うことを考える。
１．1方向性：与えられた x について簡単に y = f(x) が計算できるが、与えられた y について y = f(x) となる x を見つけることは難しい
２．線形性： f(αx + βy) = αf(x) + βf(y)
３．x≠y ⇒ f(x)≠f(y)
このような関数がどのように目隠し評価する助けになるのか見てみよう。簡単に可視化するために、Peggyがこの問題においてその点で多項式を評価したとVictorが検証できるような方法で、VictorがPeggyに、どちらもが知っているPの目隠し評価を問い合わせるとする。さらに、fは存在して、PeggyもVictorも知っている知っているとする。
まずVictorは、その多項式を評価したいある点 x0 を選ぶ。そしてこの点 x0 を f に食わせて新たな点（zとする）を出して、この ｚ をPeggyに送る。fの1つ目の性質により、Peggyが z から x0 を得られないことに注意する。さらに、f の3つ目の性質から、f(x'0) = z となるような x'0（≠x0）を見つけることもできない。これら2つの事実から、ひとたびPeggyがVictorから z を受け取ると、Peggyが元の x0 を逆算する手段がないことを意味する。
P(x) = a1 x である場合を考える。与えられた z = f(x0) について、Peggyは簡単に P(z) = a1 z を計算できる。 f の線形性により、以下に注意する。
P(z) = P(f(x0)) = a1 f(x0) = f(a1x0) = f (P(x0))
これはまさしく欲しいもので、P(z) の計算により、x0については何も知らず、Peggyが実質的に f (P(x0)) を計算したことになっている！f、P、x0は知っているのでVictorは、ここでPeggyによって計算された P(z) を見て自分のところで f (P(x0)) と比べる。 もしこれら2つの結果が一致すれば、x'0（≠x0）での評価は別の結果になることを考慮すれば、VictorはP が x0 で評価されたことを確信できる。
上記のアプローチを任意の多項式に一般化するために必要な変更は1つで、Victorがより多くの情報をPeggyに送ればよい。特に、d を評価したい多項式の字数として、Victorは以下の情報をPeggyに送れば良い。
f(1), f(x0), f(x02), ..., f(x0d)
この情報を使い、今やPeggyは、x0 について何も知ることなく
f (P(x0))
= f(a0 + a1 x0 + ... + an x0d)
= f(a0) + f(a1 x0) + ... + f(an x0d)
= a0 f(1) + a1 f(x0) + ... + an f(x0d)
を計算でき、さらにVictorは、f、P、x0 を知っているので、この結果が正しいことをチェックできる。
この連載の1つ目の投稿では、簡潔性と対話性というような、ゼロ知識プロトコルのレベルの高い性質のいくつかを議論した。これらに基づいて、zk-SNARKsというこの連頼の主題を導入し、Pythonで書いた簡単なプログラムについてzk-SNARKを構成しようとしたときに生じつ問題のいくつかを紹介した。これはR1CSとQAPの導入に動機づけられていて、コンピュータのコードを、zk-SNARKの構成に親しませてくれて、より形式的で数学的に柔軟な方法でコンピュータのコードを理解させてくれるような、QAPに変形する例を挙げた。最後に、この連載の続編で中心となる予定の、多項式の目隠し評価という強力な道具を道具箱に加えた。
次回は、zk-SNARKという十徳ナイフ（Swiss army knife）[訳注4]を、隠れた点で多項式の評価に使った"魔法の"関数 f を構成するのに必要な道具に拡張し、Pythonでこの技術の実装を提供する。ではまた！
（原文）
・zk-SNARKs 入門 （その1）（decentriq）
（参考）
・増える開発者、増える破壊：Zcashの暗号セレモニーが進行中（COINPOST）
・イーサリアムに導入されたプライバシー保護技術「zk-SNARK」とは（ZOOM）
[訳注1] エンドツーエンド…以下を参考。
・エンドツーエンド原理（Wikipedia）
[訳注2] 暗号プリミティブ…以下を参考。
・公開鍵暗号方式の構成（シニアエンジニアの庵）
[訳注3] この訳では、ベクトルを太字で表現し、上付き添え字の「T」は転置を表す。（矢印表記とか縦ベクトルをブログで書くのがめんどくさかったのでｗ）
[訳注4] タプル…以下を参考。
・タプル（Wikipedia）
[訳注5] スイス・アーミーナイフ…以下を参考。
・アーミーナイフ（Wikipedia）
TwitterのDMで怪しげな（笑）アカウントからオススメされたリンク先にあったzk-SNARKsの記事（Introduction to zk-SNARKs (Part 1)）、読んでみたらすごく面白かったｗ
というかこのブログめっちゃ良いぞ！！
……というわけで、自分の勉強がてら翻訳してみました。
皆さんの勉強のご参考になれば幸いです。
そんなに英語が得意なわけではないので、間違いなどあればメールフォームから教えていただけると助かります！
（ちなみに、怪しげなアカウントはdecentriqの公式アカウントですｗ）
zk-SNARKs 入門 （その1）
概要
この連載では、確率論的なプロトコルの1つで、Goldwasser、Micali、Rackoffにより1985年に初めて記述され、分散台帳技術（DLT）の盛り上がりとともに人気が出てきたゼロ知識証明(ZKPs)について見ていく。まずはこの画期的な仕事の背後にあるいつくかの理論の紹介と、その複雑な機構の種々の要素をどのように実行するのか示すことから始める。Pinocchioプロトコルに従いPythonで実行して、最終的には例題に関するエンドツーエンド[訳注1]のゼロ知識証明になる。主な目標はこのトピックのやさしい入門を提供することで、ZKPsに関する簡潔な数学をかみ砕いて、その背後にあるいくつかの直観的なことを議論する。これに沿って、この技術によって可能になる、いくつかのエキサイティングな応用についても触れる。
そもそも、ZKPとは何のことで、なぜこれを気にしないといけないの？
ZKPは、「証明者（彼女のことはPeggyと呼ぶことにしよう）がある秘密を知っている」ことを秘密の内容を明かさず、承認者（彼のことはVictorと呼ぶことにしよう）にどんな合理的な疑問も残さない証明を与える。たとえばPeggyは、具体的な素因子を明かすことなく非常に大きい合成数の素因数分解を知っていることだったり、解答自体は明かさずに与えられた数独パズルの答えを知っていることをVictorに証明したいのかもしれない。もっと一般的には、ZKPsは検証可能な計算の構成要素として使える：これは弱いクライアントからより計算力の高いワーカーに計算を押し付ける方法で、元のプログラムを実行するのに比べてかなり小さい労力の計算でワーカーが実行した計算の正しさを、クライアントが暗号的学的に証明することができるようなもの。これは、クラウドだけでなく、オンラインのプライバシー、DLTのスケーラビリティや携帯アプリ、その他諸々の応用に影響する非常に強力なパラダイムになっている。
ZKPsについて別の有望な応用は、機械学習の分野にある。この文脈でこの技術は、第三者がモデルのトレーニングや予測の過程で特定のデータが使われたことを証明できるだけでなく、すべてを開示する必要なく特定のデータを持っていることを証明するのに使える。OpenMined は、活発に動いているプライベートでセキュアな機械学習のエコシステムを作るための多重暗号プリミティブ（multiple cryptographic primitives）[訳注2]の先駆的プレジェクト。
だけど、実のところ、ZKPって何？
非常に簡単に言うと、コンピューター上で表現されるとZKPは、Peggyによって注意深く計算され、Victorが計算が正しいことの証明を検証するために実行するたくさんあるブール型のチェックと一緒にして数を並べたものでしかない。したがって、ゼロ知識証明のプロトコルはこれらの数から導かれ、検証の確認で定義される。
非対話性と簡潔性
ゼロ知識分野での研究は増えていて、Goldwasser, Micali と Rackoff による初めの論文（１，２，３，４，５）が出版されてから色んなプロトコルも提案されている。
これらのプロトコルの主な違いの一つは対話性にある。対話的なゼロ知識プロトコルでは検証者が「証明者がある秘密を知っている」ということを信じられるまで、証明者と検証者がたくさんのメッセージをたがいに交換する。各やり取りのラウンドはVictorによって出された「Peggyが正しい解答を提出しないといけない」問題で、その解答はVictorに検証され、プロトコルによって特徴づけられるブール型のチェックを通過したときにだけ受理される。Peggyがその秘密を知らずにNラウンドすべてチェックに通貨してしまう確率は、Nについて指数関数的に減少する。したがって、Victorは内容については何も知ることがないにもかかわらず、「Peggyがその秘密を知っている」ことをVictorが確信できるまで好きなだけ長く、行ったり来たりするやり取りを続けられる。
逆に、非対話型のゼロ知識プロトコルでは、証明者と検証者の間でやり取りが繰り替えされることがない。代わりにただ1つの"ラウンド"があり、これは非同期的に実行される。公開されているデータ（続くセクションや投稿で議論される予定の内容）を使い、Peggyが証明を作り、Victorが利用できる場所に公開する（たとえば分散台帳上に置く）。これにより、Victorは"ラウンド"完了するため、いつでもその証明を検証できる。対話的な場合はたくさんの証明を作るのに対しPeggyはただ1つの証明を作るとしても、無視できる確率を除き、「彼女が、自分で主張する秘密を確かに知っている」ことを検証者は依然として確信できる。結果的に、非対話型アプローチの利点の1つとして、「検証者に依らない」ことがある。Peggyの証明は、手元にあるその問題の実例（たとえば数独パズル）について普遍的で、Victorだけでなくどんな検証者でも、Peggyの「私は解答を持っている」という主張を後から検証できる。
ゼロ知識プロトコルたちの別の違いは簡潔性にあって、Peggyによって生成される証明のサイズを扱う。簡潔性は、ストレージ容量と検証時間という2つの理由で、分散台帳上に発行されたZKPについて重要な役割を担う。ストレージは非常に高価で、たとえば現時点でビットコイン、イーサリアム、NEO、EOSで各台帳に1KBを保存するときの費用はそれぞれ、$3.83、$2.86、$19.38、$3.00となっていて、ピーク時の費用はもっと高い！変動価格と高価なストレージの効果は、1KBあたり$0.001であるファクトムなどの安価で低価格の分散台帳を使うことで相殺できる。にもかかわらず、証明のサイズはできるだけ小さく保つことが依然として望ましい。加えて証明は素早く検証できることが必要で、そうでないとサードパーティにオフロードする効果が薄れる。したがって、チェーンなしのアプリケーションにとって、検証時間が一定であるだけでなく、生成された証明ができるだけ短くて、理想的には問題の内容によらないことが非常に重要となる。
自然な疑問として、「対話型の証明が好まれる場合があるのか？」ということがある。多くの非対話型プロトコルは、一般に「信頼されたセットアップ」といううるさい問題に悩まされていることがわかるが、これは各々を対話型にした代替プロトコルには存在しない。信頼されたセットアップは、証明を計算するときPeggyに利用される公開データの一部を生成するプロセスにある。このセットアップの詳細は後で議論予定だが、簡単に言うと、このセットアップは、乱数源から発生するある数（一般に「有害廃棄物」と呼ばれる）を公開する集団や、集団が集まった大きな集団による。この乱数源にアクセスする誰もが、プロトコルに従って検証者が受け入れるような偽の証明を生成できる。このような理由で、公開された数を生成する集団によって「有害廃棄物」が破壊されることが重要で、これはこのような集団が信頼される必要があることを意味する。これは実質的に、いつくかの非対話型ゼロ知識プロトコルの適用可能性を扱いにくいものにする。
しかしながら多くの場合、非対話性や簡潔性では大して得をするわけではない。非対話性は、たくさんの独立な検証者が、与えられた証明を各々個別に証明者へ問い合わせを行わずに検証したいときにのみ有用となる。簡潔性は、証明を保存するために使われる中間物が非常に高価か、非常に短い検証時間を求めているときのどちらかまたはこの両方であるときにのみ必要となる。しかしながら、分散台帳は特段の例外として一般にストレージは安価で、パブリックブロックチェーン上のブロック間時間に強いられるような厳しい制約がなければ検証時間もまた柔軟であり得る。
これは、2つの対象がHTTPSのように安全なチャネルを使ってやり取りするようなB2Bアプリケーションでは、対話型の証明でやっていけることを意味する。検証者は信頼されたセットアップを実行する責任があるとして、ユースケースに応じて企業がPeggyかVictorの皮をかぶることができる。このやり取りは自然に1対1なので、検証者は偽の証明には興味がなく、オンチェーンに証明を保存する必要もなく、Victorは検証を実行する時間をより多く割く余裕があり、このようなアプリケーションは対話型の状況ではたらく。
このちょっとした遠回りに続いて、この連載で興味のある主題である、非対話型で簡潔な証明に戻る。特に、ここではゼロ知識（zero-knowledge）で、簡潔（Succinct）かつ非対話型（Non-interactive）の計算による知識証明、またの名を「zk-SNARKs」というものに興味がある。特筆すべきアーリーアダプターの中でも匿名暗号通貨のZcashと、スマートコントラクトのプラットフォームであるEthereumで使われており、zk-SNARKsはゼロ知識プロトコルで最も広く使われている。
QAP：計算から多項式へ
zk-SNARKプロトコルをより厳密に説明する前に、いくつかの背景に言及しておかないといけない。
ゼロ知識プロトコル一般に言える複雑なことの1つとして、これらを適用可能にするために、元の問題を完全に変形してやらないといけない、ということがある。
PeggyがVictorに対して、「自分が方程式 x2-4=0 の解を知っている」ことを、この解が何かを明かすことなしに証明したい、という状況を考える。この場合解は自明で、誰でもこの解答を導けるので現実的にはこの問題にゼロ知識証明は不要だが。それもかかわらず、2次多項式に代わってこれを1万次の多項式に簡単に拡張できることを念頭に置きつつ、話を簡単にするために、この連載ではこの例を見る。
それで、この問題をどう読み替えていけば良いのだろうか？
この過程の詳細はVitalik Buterinによる素晴らしい投稿の2次算術プログラム（QAPs：Quadratic Arithmetic Programs）にあり、さらなる読みものとしてこれを強くおすすめする。ここでは、この「変形」の短いまとめを提供する。
まずはコードでこの問題を表すことから始める。すなわちPythonでは、計算を読み替える、次の簡単な関数を定義できる。
def f(x):
y=x**2-4
Peggyとしては「自分だけが知っているある秘密の値xにおいて上の関数を評価すると、yが0になる」ことが目標。明らかに、少なくとも2つの問題がある。
・xの値は知ることなく、関数を実行する最後にyの値の"ピーク"をVictorが得られる方法を見つける必要がある。
・Peggyはプログラムの実行者なので、コードの今の定式化では、VictorはPeggyが確かに実行したどんなコードも制御できない。たとえば、Peggyは条件を満たすy=0というだけのコードを走らせるズルをすることもできる。
これらの問題のどちらも、解決がとても難しいように見える。当然、この答えは上述した問題のかなり非自明な再定式化を必要とし、すなわちこれのQAPへの変換が必要となる。これは、コードの平坦化（code flattening）、rank 1の拘束系（R1CS： rank-1 constraint system）への変換、最後にQAPの定式化、という3つのステップを踏む。
コード平坦化のゴールは、任意の複雑な主張や表現を含むような元のコードを、次の2つの形からなる一続きの主張に変換することとなる。
・x=y（ここで、yは変数でもある数でも良い）
・x=y（op）z （ここで、op∈（+,-,*,/）であり、yとzは変数でも、ある数でも、部分式でも良い）
これらの主張を算術回路のゲートとして考えられる。ここで出している例のプログラムの回路は、次のように見られる。
（元記事の図も参照）
x -----┐
x ---------→ * ---(out_1)---┐
-4----------------------------→ + ---(y)---→
対応する「平坦化されたコード」は次のようなものになる。
def f(x):
out_1 = x * x
y = out_1 - 4
次のステップでは、これをR1CSに変形する。R1CSというのははベクトル（ai, bi, ci）[訳注3]のトリプレットのリストで、この解は、任意の i について
〈ai, s〉 * 〈bi, s〉 - 〈ci, s〉 = 0
を満たすようなベクトル s となる。ここで、〈・,・〉は2つのベクトルのドット積（内積）を表す。このトリプレットは、この方程式を満たすような s を探して満たす必要のあるような拘束条件を定義していると解釈できる。
例に挙げているコードの平坦化したものをR1CSに変換する、自然な方法がある。まずプログラムの主張を満たすようなベクトル（すなわち、プログラム内で使われるすべての変数）を定義する。このベクトルの各成分は1つの変数で、その解 s は各変数を割り当てたものになる。
今のプログラムの変数ベクトルは、次のようなものになる。
s = (1, x, out_1, y)T
1つ目の成分として1を含むのは、後で簡単に見るように、これによって拘束条件を満たすようにするため。
このベクトルを定義して、平坦化したコードの各行を順次処理して適切なai、bi、ciを定義することで、今の行に含まれる計算の読み替えを続ける。
たとえば、この関数の中身で最初の行を読み替えるには、以下のように設定する。
a1 = (0, 1, 0, 0)T
b1 = (0, 1, 0, 0)T
c1 = (0, 0, 1, 0)T
2行目の読み替えには以下を使う。
a2 = (-4, 0, 1, 0)T
b2 = (1, 0, 0, 0)T
c2 = (0, 0, 0, 1)T
この2つの行について、読み替えを展開してチェックしてみる。2行目で-4という定数を表すために、aiの定義のところでsの第1成分で1をどう使うかも見る。
1行目：
〈a1, s〉 * 〈b1, s〉 - 〈c1, s〉
= Σni=1 a1 si * Σni=1 b1 si - Σni=1 c1 si
= x * x - out_1
=0
2行目：
〈a2, s〉 * 〈b2, s〉 - 〈c2, s〉
= Σni=1 a2 si * Σni=1 b2 si - Σni=1 c2 si
= out_1 - 4 - y
=0
上記によって、このPythonプログラムがコンピュータのコードから高速条件の集合へうまく変換された！コードのロジックは制限されたベクトル（ai, bi, ci）のトリプレットに"移送"された。このプログラムの実行は、R1CS方程式
〈ai, s〉 * 〈bi, s〉 - 〈ci, s〉 = 0 （ i は任意）
を満たすようなsの成分を見つけることと等価になっている。
QAPへの変形を完了するのに、ベクトルから多項式へ転換する必要がある。 i ∈ [1, N] として、多項式 Ai(x)、Bi(x)、Ci(x)を定義することから始める。ここで、Nは制限ベクトルの成分の数（今の場合は4）となっている。Ai(n) = an,i （Bi(n)、Ci(n)も同様）と要請し、これらの点に基づいたLagrange補完をすることでこれらの多項式を構成する。
今の例では次のように要請する（Bi、Ciも同様）。
A1(1) = 0
A1(2) = -4
A2(1) = 1
A2(2) = 0
Lagrange補完をすると、次の多項式に到達する。
A1(x) = - 4x + 4
A2(x) = - x + 2
A3(x) = x - 1
A4(x) = 0
B1(x) = x - 1
B2(x) = - x + 2
B3(x) = B4(x) = 0
C1(x) = C2(x) = 0
C3(x) = - x + 2
C4(x) = x - 1
これらの定義によって、今や1つの方程式として上記をR1CSで表現できる。
A(x) * B(x) - C(x) = H(x) * Z(x)
ここで、
A = (A1(x), A2(x), A3(x), A4(x))
B = (B1(x), B2(x), B3(x), B4(x))
C = (C1(x), C2(x), C3(x), C4(x))
A(x) = 〈A, s〉
B(x) = 〈B, s〉
C(x) = 〈C, s〉
Z(x) = (x - 1) (x - 2)
また、H(x)はすべてのxについてA(x) * B(x) - C(x) = H(x) * Z(x)を満たすようなものであると要求する。
まだここ？よろしい！ここで、次のようなことが疑問じゃないだろうか。
・なんでこんなことしたの？
・Z(x)ってなんやねん
・H(x)は何者で、誰が思いつくの？
これらの質問に答えるため、まず次のようなことを見る。定義により
A(1) = a1
A(2) = a2
として、B(x)とC(x)も同様とする。A(x)、B(x)、C(x)の定義も用いると、これは元のR1CS系が以下と等価であることを意味する。
A(x) * B(x) - C(x) = 0 （x∈{1, 2}）
これを満たす唯一の方法は、A(x) * B(x) - C(x)が (x - 1) (x - 2) で割り切れるとき、すなわち以下のような H(x) が存在するときとなる。
A(x) * B(x) - C(x) = H(x) (x - 1) (x - 2)
これはH(x)とZ(x)が何かを明らかにしてくれる。しかし、誰がH(x)を計算するのだろうか？H(x)を(A(x) * B(x) - C(x))/Z(x) として計算することにより、背後にあるR1CSを満たすsの成分を知っていることを示すので、H(x)を計算するのは証明者だろう。したがって大雑把に、QAPを（A, B, C, Z）という4-タプル[訳注4]、sをこのQAPの"解"と考えることができる。
最も大事な質問にまだ答えていない。なぜこんなことをする必要があるのだろうか？
Pythonのプログラムとして今の問題を表現していたことを思い出すと、次のような1組の大きな問題に突き当たる。
・Peggyが正しいプログラムを動かしていることを検証する方法が無い
・他のどのんな情報も明かさずに、プログラム実行の最後におけるyの値をどうやってVictorに観測させるかが明確でない
R1CSとして表現された計算だと、Victor妥当なsの割り当てを見るとすると、Peggyが対応するR1CSのプログラムを実行したことを確信できる！これは主な問題の1つをすでに解決している。
QAPを得るためにR1CSをさらに変形する理由は、多項式で説明する方がR1CSで説明するよりも有益だから。次のセクションではこの新しく提案された「問題の再定式化」を、zk-SNARKsを構成する中心となる1つの技術を説明するのに使うが、これは多項式の構造を利用する。
隠れた点における多項式の評価
多項式を処理するうまいやり方の1つに、知らない点で多項式を評価するものがある。これは多項式の目隠し評価（？blind evaluation of polynomials）としても知られる。まってｗつまり……どういうことだってばよ？！そう、お分かりの通りこれは不可能に違いない。与えられた多項式
P(x) = a0 + a1 x + a2 x2 + ... + an xn
について、この多項式を評価したいとすれば、xを知らなければいけない。実際に今はこういう場合だけど、いつくかの追加情報を使えるとすれば、評価するときのその点xを知ることなく、多項式を評価できる！
次に、次のような性質を持つある関数 f(x) を使うことを考える。
１．1方向性：与えられた x について簡単に y = f(x) が計算できるが、与えられた y について y = f(x) となる x を見つけることは難しい
２．線形性： f(αx + βy) = αf(x) + βf(y)
３．x≠y ⇒ f(x)≠f(y)
このような関数がどのように目隠し評価する助けになるのか見てみよう。簡単に可視化するために、Peggyがこの問題においてその点で多項式を評価したとVictorが検証できるような方法で、VictorがPeggyに、どちらもが知っているPの目隠し評価を問い合わせるとする。さらに、fは存在して、PeggyもVictorも知っている知っているとする。
まずVictorは、その多項式を評価したいある点 x0 を選ぶ。そしてこの点 x0 を f に食わせて新たな点（zとする）を出して、この ｚ をPeggyに送る。fの1つ目の性質により、Peggyが z から x0 を得られないことに注意する。さらに、f の3つ目の性質から、f(x'0) = z となるような x'0（≠x0）を見つけることもできない。これら2つの事実から、ひとたびPeggyがVictorから z を受け取ると、Peggyが元の x0 を逆算する手段がないことを意味する。
P(x) = a1 x である場合を考える。与えられた z = f(x0) について、Peggyは簡単に P(z) = a1 z を計算できる。 f の線形性により、以下に注意する。
P(z) = P(f(x0)) = a1 f(x0) = f(a1x0) = f (P(x0))
これはまさしく欲しいもので、P(z) の計算により、x0については何も知らず、Peggyが実質的に f (P(x0)) を計算したことになっている！f、P、x0は知っているのでVictorは、ここでPeggyによって計算された P(z) を見て自分のところで f (P(x0)) と比べる。 もしこれら2つの結果が一致すれば、x'0（≠x0）での評価は別の結果になることを考慮すれば、VictorはP が x0 で評価されたことを確信できる。
上記のアプローチを任意の多項式に一般化するために必要な変更は1つで、Victorがより多くの情報をPeggyに送ればよい。特に、d を評価したい多項式の字数として、Victorは以下の情報をPeggyに送れば良い。
f(1), f(x0), f(x02), ..., f(x0d)
この情報を使い、今やPeggyは、x0 について何も知ることなく
f (P(x0))
= f(a0 + a1 x0 + ... + an x0d)
= f(a0) + f(a1 x0) + ... + f(an x0d)
= a0 f(1) + a1 f(x0) + ... + an f(x0d)
を計算でき、さらにVictorは、f、P、x0 を知っているので、この結果が正しいことをチェックできる。
結論
この連載の1つ目の投稿では、簡潔性と対話性というような、ゼロ知識プロトコルのレベルの高い性質のいくつかを議論した。これらに基づいて、zk-SNARKsというこの連頼の主題を導入し、Pythonで書いた簡単なプログラムについてzk-SNARKを構成しようとしたときに生じつ問題のいくつかを紹介した。これはR1CSとQAPの導入に動機づけられていて、コンピュータのコードを、zk-SNARKの構成に親しませてくれて、より形式的で数学的に柔軟な方法でコンピュータのコードを理解させてくれるような、QAPに変形する例を挙げた。最後に、この連載の続編で中心となる予定の、多項式の目隠し評価という強力な道具を道具箱に加えた。
次回は、zk-SNARKという十徳ナイフ（Swiss army knife）[訳注4]を、隠れた点で多項式の評価に使った"魔法の"関数 f を構成するのに必要な道具に拡張し、Pythonでこの技術の実装を提供する。ではまた！
（原文）
・zk-SNARKs 入門 （その1）（decentriq）
（参考）
・増える開発者、増える破壊：Zcashの暗号セレモニーが進行中（COINPOST）
・イーサリアムに導入されたプライバシー保護技術「zk-SNARK」とは（ZOOM）
[訳注1] エンドツーエンド…以下を参考。
・エンドツーエンド原理（Wikipedia）
[訳注2] 暗号プリミティブ…以下を参考。
・公開鍵暗号方式の構成（シニアエンジニアの庵）
[訳注3] この訳では、ベクトルを太字で表現し、上付き添え字の「T」は転置を表す。（矢印表記とか縦ベクトルをブログで書くのがめんどくさかったのでｗ）
[訳注4] タプル…以下を参考。
・タプル（Wikipedia）
[訳注5] スイス・アーミーナイフ…以下を参考。
・アーミーナイフ（Wikipedia）
