Zk-SNARKs：エンジンフードの下
著者：Vitalik Buterin
原題：《Zk-SNARKs: Under the Hood》
発表日時：2017年2月1日
これは、zk-SNARKsの背後にある技術がどのように機能するかを説明する一連の記事の第3部です。以前の二次算術プログラムと楕円曲線ペアリングに関する記事は必読であり、この記事ではこれら2つの概念の知識が前提とされています。また、zk-SNARKが何であるか、そしてそれらが何をするのかの基本的な知識も前提とされています。さらに、こちらのChristian Reitwiessnerの記事も別の技術的な紹介として参照してください。
前回の記事では、任意の計算問題を多項式方程式で表現する方法である二次算術プログラムを紹介しました。これは、さまざまな形式の数学的テクニックに適しています。また、楕円曲線ペアリングも紹介しました。これは、非常に限られた一方向同態暗号形式を可能にし、等価性チェックを行うことができます。さて、前回の中断点から始め、楕円曲線ペアリングや他のいくつかの数学的テクニックを使用して、証明者が特定のQAPの解を知っていることを証明できるようにし、実際の解に関する情報を明らかにすることなく行います。
この記事では、Parno、Gentry、Howell、Raykovaが2013年に開始したPinocchioプロトコル（一般にPGHR13と呼ばれる）に焦点を当てます。基本的なメカニズムにはいくつかの変更があるため、実際に実装されるzk-SNARKスキームは若干異なる場合がありますが、基本原理は通常変わりません。
まず、私たちが使用するメカニズムの安全性の背後にある重要な暗号仮定を見てみましょう：指数知識仮定です。
基本的に、PとQの点のペアを取得し、P * k = Qであり、点Cを取得した場合、CがPから「派生」したものでない限り、C * kを知っていることは不可能です。これは直感的に見えるかもしれませんが、この仮定は実際には、私たちが通常、楕円曲線に基づくプロトコルの安全性を証明する際に使用する他の仮定（例えば、離散対数の難しさ）から導き出すことはできません。したがって、zk-SNARKは実際には楕円曲線暗号学よりも一般的で不安定な基盤に依存していますが、それでもほとんどの暗号学者が受け入れるには十分に堅牢です。
では、これをどのように使用するか見てみましょう。PとQの点のペアが空から降ってきたと仮定します。P * k = Qですが、誰もkの値を知らないとします。次に、私がRとSの点のペアを提示したと仮定します。R * k = Sです。ここで、KoE仮定は、私がこの点のペアを得る唯一の方法はPとQを取り、私が個人的に知っている因子rで両方を掛けることだと示しています。また、楕円曲線ペアリングの魔法により、R = k * Sを確認するためにkを知る必要はありません。逆に、e(R, Q) = e(P, S)を単純に確認できます。
もっと面白いことをしましょう。空から降ってきた10組の点があると仮定します：(P1, Q1), (P2, Q2)… (P10, Q10)。すべての場合において、Pi * k = Qiです。私がその後、RとSの点のペアを提供したと仮定します。R * k = Sです。あなたは今、何を知っていますか？あなたはRがP1 * i1 + P2 * i2 + … + P10 * i10のいくつかの線形結合であることを知っています。ここで、私は係数i1, i2 … i10を知っています。つまり、このような点のペア（R、S）を得る唯一の方法は、P1、P2…P10のいくつかの倍数を取り、それらを加算し、次にQ1、Q2…Q_10で同じ計算を行うことです。
特定のP1…P10点のセットに対して、あなたが線形結合をチェックしたい場合、実際にはkが何であるかを知らない限り、付随するQ1…Q10点を作成することはできません。もしあなたがkが何であるかを知っているなら、あなたはR * k = Sの任意のRに対して点のペア(R, S)を作成できますが、線形結合を作成する必要はありません。したがって、これを機能させるためには、これらの点を作成する人が信頼できることを確実にし、10の点を作成した後にkを実際に削除する必要があります。これが「信頼できる設定」概念の由来です。
QAPの解は、A(x) * B(x) - C(x) = H(x) * Z(x)となる多項式のセット(A, B, C)です。ここで：
- Aは多項式{A1…Am}の線形結合です
- Bは同じ係数を持つ{B1…Bm}の線形結合です
- Cは同じ係数を持つ{C1…Cm}の線形結合です
集合{A1…Am}、{B1…Bm}、{C1…Cm}および多項式Zは問題の記述の一部です。
しかし、ほとんどの実際のケースでは、A、B、Cは非常に大きいです。ハッシュ関数のような数千の回路ゲートを持つものでは、多項式（および線形結合の因子）は数千の項を持つ可能性があります。したがって、証明者に直接線形結合を提供させるのではなく、上記で紹介したテクニックを使用して、証明者が提供したものが線形結合であることを証明させますが、他の何も明らかにしないようにします。
あなたはすでに気づいているかもしれませんが、上記のテクニックは多項式ではなく楕円曲線点に適用されます。したがって、実際に行われるのは、次の値を信頼できる設定に追加することです：
G * A1(t), G * A1(t) * ka
G * A2(t), G * A2(t) * ka
…
G * B1(t), G * B1(t) * kb
G * B2(t), G * B2(t) * kb
…
G * C1(t), G * C1(t) * kc
G * C2(t), G * C2(t) * kc
…
tを計算多項式の「秘密の点」と見なすことができます。Gは「生成器」（プロトコルの一部として指定されたランダムな楕円曲線点）であり、t、ka、kb、kcは「有毒廃棄物」であり、あらゆる手段を使って削除しなければならない数字です。これらを持っている人は偽の証明を作成できるからです。今、誰かがP、Qの点のペアをあなたに与え、P * ka = Q（思い出してください：これを確認するためにkaを知る必要はありません。なぜなら、ペアリングチェックを行うことができるからです）を満たす場合、あなたは彼らが何を与えたかを知っています。あなたはtで評価されるAi多項式の線形結合を知っています。
したがって、これまでのところ、証明者は次のことを示さなければなりません：
πa = G * A(t), π'a = G * A(t) * ka
πb = G * B(t), π'b = G * B(t) * kb
πc = G * C(t), π'c = G * C(t) * k_c
証明者は、これらの値を計算するためにt、ka、kb、k_cを実際に知る必要はありません（また知るべきではありません！）。代わりに、証明者は信頼できる設定に追加された点に基づいてこれらの値を計算できる必要があります。
次のステップは、すべての3つの線形結合が同じ係数を持つことを確認することです。これを行うために、信頼できる設定に別の値のセットを追加します：G * (Ai(t) + Bi(t) + C_i(t)) * b、ここでbは別の「有毒廃棄物」と見なされるべき数字であり、信頼できる設定が完了した後にすぐに廃棄されます。次に、証明者がこれらの値を使用して同じ係数を持つ線形結合を作成し、上記と同じペアリングテクニックを使用して、その値が提供されたA + B + Cと一致するかどうかを検証できます。
最後に、A * B - C = H * Zを証明する必要があります。これを再度ペアリングチェックで実行します：
e( πa, πb) / e( πc, G) ?= e( πh, G * Z(t))
ここでπ_h = G * H(t)です。この方程式とA * B - C = H * Zとの関連が意味をなさない場合は、ペアリングに関する記事を再度読んでください。
私たちは上記でA、B、Cを楕円曲線点に変換する方法を見ました。Gは単なる生成器（すなわち、楕円曲線点は数字1に相当します）。私たちはG * Z(t)を信頼できる設定に追加できます。Hはより難しいです。Hは単なる多項式であり、私たちは各QAP解の係数を事前に予測することはほとんどありません。したがって、信頼できる設定にさらに多くのデータを追加する必要があります。具体的な順序は：
G, G * t, G * t², G * t³, G * t⁴ …。
Zcashの信頼できる設定では、ここでのシーケンスは約200万に達します。これは、特定のQAPインスタンスに関してH(t)を常に計算できるようにするために必要な累乗の数です。これにより、証明者は検証者に最終チェックのためのすべての情報を提供できます。
もう一つの詳細について話し合う必要があります。ほとんどの場合、私たちは特定の問題の解が存在することを抽象的に証明したいだけではありません。むしろ、特定の解の正しさを証明したいのです（例えば、「cow」という単語を使ってそれをSHA3ハッシュ化し、最終的な結果が0x73064fe5で始まることを証明する）か、解がいくつかのパラメータを持つことを制限したいのです。例えば、取引金額とアカウント残高が暗号化された暗号通貨のインスタンスでは、いくつかの復号鍵kを知っていることを証明したいのです。これにより：
暗号化されたoldbalance、txvalue、new_balanceは公開されるべきであり、これらは特定の時点で検証したい特定の値です。復号鍵のみが隠されるべきです。特定の入力に対応する「カスタム検証鍵」を作成するために、プロトコルにいくつかの微妙な修正が必要です。
さて、一歩引いてみましょう。まず、ここにben Sasson、Tromer、Virza、Chiesaによって提供された完全な検証アルゴリズムがあります：
最初の行はパラメータ化を処理します。本質的に、これは特定のパラメータを指定した問題の特定のインスタンスのための「カスタム検証鍵」を作成する機能と見なすことができます。2行目はA、B、Cの線形結合のチェックです。3行目は線形結合が同じ係数を持つかどうかのチェックであり、4行目はA * B - C = H * Zの積のチェックです。
要するに、検証プロセスは数回の楕円曲線乗算（各「公共」入力変数に1回）と5回のペアリングチェックで構成されており、そのうちの1回には追加のペアリング乗算が含まれています。証明には8つの楕円曲線点が含まれています：A(t)、B(t)、C(t)の各ペアの点、b * (A(t) + B(t) + C(t))の点πk、およびH(t)の点πhです。7つの点はFp曲線上にあり（各32バイト、y座標を1ビットに圧縮できるため）、Zcashの実装では、1つの点(πb)がF_p²のねじれ曲線上にあります（64バイト）。したがって、証明の総サイズは約288バイトです。
証明を作成する際の計算上最も難しい部分は次の2つです：
(A * B - C) / Zを除算してHを得る（これは高速フーリエ変換に基づくアルゴリズムで、二次時間内に完了できますが、計算量は依然として大きいです）
A(t)、B(t)、C(t)、H(t)の値とそれに対応するペアを作成するための楕円曲線乗算と加算を行う
証明がこれほど困難な基本的な理由は、ゼロ知識証明を作成するために、元の計算の単一のバイナリ論理ゲートが楕円曲線操作を通じて暗号処理される必要があるからです。この事実と、迅速なフーリエ変換の超線形性により、Zcash取引の証明作成には約20〜40秒かかります。
もう一つ非常に重要な問題は、信頼できる設定を少しでも……信頼を必要としないようにできるかどうかです。残念ながら、私たちはそれを完全に信頼しないようにすることはできません。KoE仮定自体がkが何であるかを知らないまま独立したペア(Pi, Pi * k)を作成することを排除しています。しかし、N-of-Nマルチパーティ計算を使用することで安全性を大幅に向上させることができます。つまり、N人の間で信頼できる設定を構築し、少なくとも1人の参加者が彼らの有毒廃棄物を削除すれば、あなたはそれを行うことができます。
これを実行する方法を少し理解するために、既存の集合（G、G * t、G * t²、G * t³…）を取得し、「あなた自身の秘密」を「追加」するための簡単なアルゴリズムを示します。これにより、あなたは秘密と以前の秘密（または以前の秘密のセット）を必要とすることになります。
出力セットは非常にシンプルです：
G, (G * t) * s, (G * t²) * s², (G * t³) * s³…
注意してください。あなたは元の集合とsを知っているだけでこの集合を生成でき、新しい集合の機能は古い集合と同じですが、今はt*sを「有毒廃棄物」として使用しています。あなたと前のセットを作成した人（または複数の人）があなたの有毒廃棄物を削除せず、その後共謀しなければ、そのセットは「安全」です。
完全な信頼できる設定を実行することははるかに困難です。なぜなら、複数の値が関与し、各パーティ間でアルゴリズムを数ラウンドに分けて完了する必要があるからです。これは積極的に研究されている分野であり、マルチパーティ計算アルゴリズムをさらに簡素化し、より少ないラウンドまたはより並行化可能にできるかどうかを調べています。できるだけ多くのことを行うほど、信頼できる設定プロセスに参加する参加者が増えます。相互に知り合いで一緒に働く6人の参加者間の信頼設定が不安を感じさせる理由がある一方で、数千人の参加者を持つ信頼設定は、完全に信頼しないこととほとんど違いがありません。もし本当に偏執的であれば、あなた自身で設定プロセスに参加し、自分の値を削除したことを確認できます。
もう一つの活発な研究分野は、ペアリングを使用せず、同じ信頼できる設定の例を使用して同じ目標を達成する方法です。別の選択肢についてはEli ben Sassonの最近のプレゼンテーションを参照してください（ただし、数学的にはSNARKと同じくらい複雑であることに注意してください！）
Ariel GabizonとChristian Reitwiessnerのレビューに特別な感謝を申し上げます。
