Vitalik：zk-SNARKの内部仕組み
TechFlow厳選深潮セレクト
Vitalik：zk-SNARKの内部仕組み
本稿では、読者がこれらの2つの概念をすでに理解しており、zk-SNARKの基本的な知識とその機能についても把握していることを前提とする。
Web3業界の深掘り報道に専念し潮流を洞察*注：この記事は2017年2月に執筆されました
本稿では、zk-SNARKの背後にある技術がどのように機能するかを説明します。二次演算プログラムおよび楕円曲線ペアリングに関する以前の記事は必読です。ここでは、それら2つの概念について既に理解しており、zk-SNARKの基本知識とその目的についても把握していることを前提とします。また、Christian Reitwiessnerによるzk-SNARKの紹介記事「zksnarks in a nutshell」も併せて参照してください。
以前の記事では、任意の計算問題を多項式方程式で表現する方法である「二次演算プログラム（QAP）」を紹介しました。また、「楕円曲線ペアリング」についても解説し、非常に限定された形態の準同型暗号化を可能にすることで、等価性の検証を実現できることを示しました。ここからは、前回の内容を引き継ぎ、楕円曲線ペアリングと他の数学的手法を用いて、特定のQAPの解を知っていることを、実際の解に関する情報を一切開示せずに証明する方法について見ていきます。
本稿では、2013年にParno、Gentry、Howell、Raykovaによって提案されたピノキオプロトコル（通常はPGHR13と呼ばれる）に焦点を当てます。実際のzk-SNARK実装では、基本的なメカニズムにいくつかの変更が加えられているため、若干異なる場合もありますが、基本原理はほぼ同じままです。
まず、重要な前提となる仮定について説明します。それは「指数知識仮定（KEA: Knowledge of Exponent Assumption）」であり、セキュリティ基盤の説明において必要になります。
KEA1：ある攻撃者Aが入力q, g, g^aを受け取り、(C, Y)を出力してY = C^aを満たすとする。このとき、同じ入力を得る「抽出者（extractor）」A'が存在し、g^c = Cを満たすcを出力できる。
この仮定は、基本的に次のようなことを意味しています。つまり、点PとQのペアがあり、P * k = Qを満たすものの、kの値は誰も知らないとします。ここで、別のペア(R, S)を考え、R * k = Sが成り立つとします。KEAによれば、このようなペアを得る唯一の方法は、PとQを自分自身が知っている何らかの係数rでスカラー倍することのみです。さらに、楕円曲線ペアリングの優れた特性により、kを知らなくてもR * k = Sかどうかを検証できることに注意してください。具体的には、e(R, Q) = e(P, S)をチェックすれば十分です。
さらに興味深いことに、空から10組のペア (P_1, Q_1), (P_2, Q_2), ..., (P_10, Q_10) が降ってきたとしましょう。すべてのiについて、P_i * k = Q_iが成り立っています。ここで、R * k = S を満たすペア (R, S) を提示したとします。このとき、あなたは何を知ることができるでしょうか？Rは、私が知っている係数i_1, i_2, ..., i_10を使って、R = i_1 * P_1 + i_2 * P_2 + ... + i_10 * P_10という線形結合になっていることがわかります。言い換えると、このようなペア(R, S)を得る唯一の方法は、P_1〜P_10の各点を適当な倍数でスカラー倍して足し合わせ、Q_1〜Q_10に対しても同じ操作を行うことです。
なお、特定のP_1〜P_10に対して、対応するQ_1〜Q_10を作成することは、kを知らなければ実質的に不可能です。逆にkを知ってしまえば、線形結合を使わずとも、任意のRに対してR * k = Sとなる(S)を作成できます。したがって、このような設定を実現するには、これらの点を作成する者が信頼できる必要があります。そして、10組の点が作成された後は、kを確実に破棄しなければなりません。これがいわゆる「信頼できるセットアップ（trusted setup）」の概念の起源です。（訳者注：信頼できるセットアップとは、zkSNARKシステム起動時に一度だけ行われる初期設定のことです。）
ここで、QAPの解とは何かを思い出しましょう。QAPの解とは、次の式を満たす多項式の組(A, B, C)です：
A(x) * B(x) - C(x) = H(x) * Z(x)
ただし、
Aは多項式{A_1, ..., A_m}の線形結合
Bは同じ係数を持つ{B_1, ..., B_m}の線形結合
Cは同じ係数を持つ{C_1, ..., C_m}の線形結合
集合{A_1, ..., A_m}、{B_1, ..., B_m}、{C_1, ..., C_m}および多項式Zは、問題文の一部として与えられます。
しかし、現実世界の多くのケースでは、A、B、Cは非常に巨大になります。数千個の回路ゲートを持つハッシュ関数などでは、多項式自体や線形結合の係数が数千項にもなることがあります。そこで、証明者が直接線形結合を提示する代わりに、先ほど紹介したテクニックを使って、「提示されたものが確かに線形結合である」ことだけを証明し、それ以外の情報は一切開示しないようにします。
おそらく気づいたかもしれませんが、上記のテクニックは多項式ではなく、楕円曲線上の点に適用されます。したがって、実際には以下の値を信頼できるセットアップに追加します：
G * A_1(t), G * A_1(t) * k_a
G * A_2(t), G * A_2(t) * k_a
...
G * B_1(t), G * B_1(t) * k_b
G * B_2(t), G * B_2(t) * k_b
...
G * C_1(t), G * C_1(t) * k_c
G * C_2(t), G * C_2(t) * k_c
...
ここでtは、多項式を評価するための「秘密の点」とみなせます。Gは「生成元」（あるランダムな楕円曲線上の点で、一旦決まればプロトコルの一部として固定される）であり、t、k_a、k_b、k_cは「毒性廃棄物（toxic waste）」と呼ばれ、これらは絶対に破棄されなければならず、もし誰かがこれらを保持すれば偽の証明を作成できてしまいます。さて、ある人がペア(P, Q)を提示し、P * k_a = Qを満たすとします（確認：k_aを知らなくても、ペアリングチェックによりこれを検証できます）。このとき、その人はtにおけるA_i多項式の線形結合を計算した結果を提示していることがわかります。
したがって、現時点で証明者は以下の値を提示する必要があります：
π_a = G * A(t), π'_a = G * A(t) * k_a
π_b = G * B(t), π'_b = G * B(t) * k_b
π_c = G * C(t), π'_c = G * C(t) * k_c
証明者がこれらの値を計算するために、t、k_a、k_b、k_cを知っている必要はない（むしろ知ってはいけない！）ことに注意してください。証明者は、信頼できるセットアップに追加された点から、これらの値を計算できるはずです。
次に、3つの線形結合が同じ係数を持っていることを保証する必要があります。これには、信頼できるセットアップに次の値を追加します：
G * (A_i(t) + B_i(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は単なる生成元です（つまり、この楕円曲線点Gは、数値における1に相当します）。G * Z(t)は信頼できるセットアップに追加できます。一方、Hの計算はより困難です。Hは単なる多項式であり、各QAPの解ごとにその係数を事前に予測するのは難しいからです。そのため、信頼できるセットアップにさらなるデータを追加する必要があります。特に次の列です：
G, G * t, G * t², G * t³, G * t⁴, ...
Zcashの信頼できるセットアップでは、この系列は約200万項あります。H(t)を計算するためにどれほどの計算量が必要か想像してください。こうして、証明者は検証者に最終チェックに必要なすべての情報を提供できます。
まだ議論すべき詳細があります。多くの場合、我々が本当にしたいのは、ある特定の問題に解が存在することを抽象的に証明することではありません。むしろ、特定の解の正しさを証明したいのです（例：「cow」という単語をSHA3で100万回ハッシュすると、結果の先頭が0x73064fe5になる）。あるいは、あるパラメータに制限を加えたときに解が存在することを証明したい場合もあります。例えば、暗号通貨の実装では、取引金額やアカウント残高が暗号化されており、ある復号鍵kを知っていることを証明する必要があります：
decrypt(old_balance, k) ≥ decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
暗号化されたold_balance、tx_value、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)それぞれ1点、b*(A(t)+B(t)+C(t))に対応する点π_k、H(t)に対応する点π_h。このうち7点はF_p上の曲線にあり（y座標は1ビットに圧縮できるため、各32バイト）、Zcashの実装ではもう1点（π_b）がF_p²上の歪曲曲線にあり（64バイト）、したがって証明の合計サイズは約288バイトです。
証明作成において最も計算負荷が高い2つの部分は以下の通りです：
- （A * B - C）/ Z を計算してHを得る（FFTベースのアルゴリズムで準二次時間内に可能だが、それでも計算量は大きい）
- A(t)、B(t)、C(t)、H(t)の値と対応するペアリングを生成するために、楕円曲線の乗算および加算を行う
証明の作成が困難な理由は、ゼロ知識証明を行うために、元の計算における単一の論理ゲートが、楕円曲線を用いた暗号操作に置き換えられるからです。この事実とFFTの超線形性により、Zcashでの取引証明作成には約20〜40秒かかります。
もう一つ非常に重要な課題は、「信頼できるセットアップ」を少しでも……信頼度の依存を減らせるかということです。残念ながら、完全に信頼不要にすることはできません。KoE仮定自体が、kを知らずに独立したペア(P_i, P_i * k)を作成することを排除しているからです。しかし、N者間のマルチパーティ計算（MPC）を用いることで安全性を大幅に向上させることは可能です。つまり、N人の参加者間で信頼できるセットアップを行い、そのうち少なくとも1人以上が「毒性廃棄物」を確実に削除していれば安全という方式です。
それがどのように可能かの感覚を得るために、既存の集合(G, G*t, G*t², G*t³, ...)に独自の秘密sを「追加」して、もとの秘密tとsの両方がなければ不正ができないようにする簡単なアルゴリズムを紹介します。
出力集合は次の通りです：
G, (G * t) * s, (G * t²) * s², (G * t³) * s³, ...
元の集合とsさえ知っていれば、新しい集合は元の集合と同じ機能を持ちますが、「毒性廃棄物」として使われるのは今やt * sであることに注意してください。あなた自身と、前の集合を作成した人物（たち）が、全員が「毒性廃棄物」の削除に失敗して後に共謀しない限り、このグループは「安全」です。
完全な信頼できるセットアップに対してこの操作を行うのは、複数の値が関与し、アルゴリズムが複数ラウンドにわたって参加者間でやり取りされる必要があるため、はるかに困難です。これは活発な研究分野であり、マルチパーティ計算アルゴリズムをさらに簡素化し、ラウンド数を減らしたり、並列化しやすくすることで、より多くの参加者をセットアッププロセスに参加させられるようにしようとしています。6人の参加者によるセットアップに不安を感じる人もいるでしょうが、数千人の参加者がいるセットアップは、ほぼ信頼不要に近くなります。もしあなたが偏執的であれば、自分で参加してセットアップに貢献し、自分の「毒性廃棄物」を個人的に確実に削除すればよいのです。
もう一つの活発な研究分野は、ペアリングや信頼できるセットアップを使わずに同じ目的を達成する他の手法の探索です。Eli Ben Sassonの最近のプレゼンテーションを参照してください（ただし、数学的にはSNARKsと同等以上に複雑であることに注意！）
TechFlow公式コミュニティへようこそ
Telegram購読グループ：https://t.me/TechFlowDaily
Twitter公式アカウント：https://x.com/TechFlowPost
Twitter英語アカウント：https://x.com/BlockFlow_News
@VitalikButerin
