二次算術プログラム：ゼロ知識証明に関する論述
TechFlow厳選深潮セレクト
二次算術プログラム：ゼロ知識証明に関する論述
zk-SNARKの理解は確かに非常に難しく、特にシステム全体が機能するために組み立てる必要のある構成要素が多すぎるためです。
Web3業界の深掘り報道に専念し潮流を洞察執筆：Vitalik Buterin
公開日：2016年12月10日
最近、zk-SNARKs（ゼロ知識証明）の背後にある技術に対して強い関心が寄せられており、「月面数学」と呼ばれるほど複雑で理解困難だと多くの人々が感じているこの分野の神秘を解き明かそうとする試みがますます増えてきています。
zk-SNARKsの理解は確かにかなり難しく、特にシステム全体が正常に機能するためには多数の構成要素を組み合わせる必要があるためですが、こうした技術を一つひとつ分解していけば、理解はより簡単になります。
本記事の目的はzk-SNARKsの完全な紹介ではなく、以下の前提知識を持っていることを想定しています：
1- zk-SNARKsとその概略的な原理について知っていること；
2- 数学的素養があり、基本的な多項式に関する知識を持っていること。（たとえば P(x) + Q(x) = (P + Q)(x) という表記が理解できる。ここでPとQは多項式を表す。このような表現に十分に慣れ親しんでいるならば、読者の準備は整っています。）
zk-SNARK知識パイプライン図、Eran Tromer作
上図のように、このゼロ知識証明は上から下へ二つの段階に分けられます。まず、zk-SNARKは任意の計算問題に直接適用できるわけではありません。代わりに、問題を適切な「形式」に変換しなければなりません。この形式を「二次算術プログラム」（QAP）と呼び、関数のコードをこれに変換するプロセス自体も非常に重要です。関数コードをQAPに変換するプロセスと並行して、コードに対する入力があれば、それに対応する解（時としてQAPの「ワitness」と呼ばれるもの）を作成する別のプロセスも存在します。これが本稿で説明する内容です。
その後、このQAPに基づいて実際に「ゼロ知識証明」を生成するというさらに複雑なプロセスがあり、また他人から受け取った証拠を検証する別のプロセスもありますが、これらについては本稿の範囲外です。
以下では、非常に単純な問題を取り上げます：
三次方程式 x**3 + x + 5 == 35 の解を求めよ（ヒント：答えは3）。
この問題は単純ですが、重要なのは、この例を通じてすべての機能がどのように動作するかを確認できることです。
上記の方程式をプログラミング言語で記述すると次のようになります：
def qeval(x):
y = x**3
return x + y + 5
ここで使用しているシンプルなプログラミング言語は、基本的な算術演算（+、-、*、/）、定数べき乗（x^7など、ただしx*yは不可）、および変数代入をサポートしており、理論的には任意の計算が可能（ただし計算ステップ数が有限であることが条件；ループは不可）です。モジュロ（%）や比較演算子（<、>、≤、≥）はサポートされていません。なぜなら、有限巡回群のアルゴリズムにおいてモジュロや直接比較を行う効率的な方法が存在しないためです（注：もしそのような方法があれば、楕円曲線暗号は「二分探索」や「中国剰余定理」よりも早く破られるでしょう）。
ビット分解により言語を拡張してモジュロや比較を扱えるようにすることも可能です（例：13 = 2**3 + 2**2 + 1 = 8 + 4 + 1）。これを補助入力として提供し、その正しさを証明し、バイナリ回路内で数学的演算を行うことができます。有限体上で等値（==）チェックを行うことも可能であり、むしろより簡単ですが、これらの詳細についてはここでは触れません。条件分岐も言語に追加可能で、たとえば文「if x < 5: y = 7; else: y = 9;」を算術形式「y = 7 * (x < 5) + 9 * (x >= 5)」に変換できます。ただし、条件の両方の「パス」が実行されることに注意が必要で、多くの入れ子になった条件がある場合、これは大きなオーバーヘッドにつながります。
それでは、このプロセスを一歩ずつ進めていきましょう。自分でコードを実装したい場合は、私がPythonで教育用に実装したコードを参照してください（現時点では実用的なzk-SNARK用QAP生成には未対応です！）
ステップ1：フラット化
最初のステップは「フラット化」で、元のコード（任意に複雑な文や式を含んでいてもよい）を最も単純な式に分解します。この式は以下の2つの形式を持ちます：
1- x = y （yは変数または数値）
2- x = y(op)z （opは+,-,*,/のいずれか。yとzは変数、数値、または部分式）
これらを回路内の論理ゲートと考えることができます。上記の式 x**3 + x + 5 をフラット化すると、次のようになります：
sym_1 = x * x
y = sym_1 * x // つまり y = x**3 を実現
sym_2 = y + x
~out = sym_2 + 5
上記の各行の宣言はすべて回路内の論理ゲートと見なせます。元のコードと比べて、ここでは中間変数 sym_1 と sym_2、および出力を示す冗長変数 ~out を導入しています。しかし、「フラット化」後の宣言列は元のコードと等価であることは明らかです。
ステップ2：R1CSへの変換
次に、これをR1CS（Rank-1 Constraint System）と呼ばれる形式に変換します。R1CSは三つのベクトル（a, b, c）の列からなり、R1CSの解とはベクトル s であり、これは以下の式を満たさなければなりません：
s . a * s . b - s . c = 0
ここで、. は内積演算を表します。
例えば、以下は満たされるR1CSの一例です：
a = (5,0,0,0,0,1)，
b = (1,0,0,0,0,0)，
c = (0,0,1,0,0,0)，
s = (1,3,35,9,27,30)，
（訳者注：最初の35 = 1×5 + 30×1、2番目の35 = 35 × 1）
上記の例は単一の制約ですが、次に各論理ゲート（つまり「フラット化」後の各宣言文）をそれぞれ1つの制約（すなわち(a, b, c)の三つ組ベクトル）に変換します。変換方法は、宣言がどの演算（+, -, *, /）か、およびパラメータが変数か数値かによって異なります。本例では、「フラット化」後の5つの変数（'x', '~out', 'sym_1', 'y', 'sym_2'）に加え、数値1を表すために最初の成分位置に冗長変数~oneを導入します。このシステムでは、ベクトルに対応する6つの成分は（順序は他でも構いませんが一致していればよい）以下の通りです：
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'
最初のゲート
sym_1 = x * x すなわち x*x - sym_1 = 0
以下のようなベクトルを得ます：
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]
解ベクトル s の第2成分が3、第4成分が9であれば、他の成分が何であっても成立します。なぜなら a = 3 * 1、b = 3 * 1、c = 9 * 1 より a * b = c となるからです。同様に、s の第2成分が7、第4成分が49の場合も検査を通過します。この最初の検査は、最初のゲートの入出力の一貫性を検証するだけです。
2番目のゲート
y = sym_1 * x すなわち sym_1 * x - y = 0
以下のようなベクトルを得ます：
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]
3番目のゲート
sym_2 = y + x、加算ゲートは (x + y) * 1 - sym_2 = 0 に変換されます。
以下のようなベクトルを得ます：
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0] （定数1に対応、~oneの位置）
c = [0, 0, 0, 0, 0, 1]
4番目のゲート
~out = sym_2 + 5 すなわち (sym_2 + 5) * 1 - ~out = 0
以下のようなベクトルを得ます：
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]
ここで、x = 3 と仮定すると、最初のゲートから sym_1 = 9、2番目から y = 27、3番目から sym_2 = 30、4番目から ~out = 35 が得られます。したがって、'~one', 'x', '~out', 'sym_1', 'y', 'sym_2' の順に並べると：
s = [1, 3, 35, 9, 27, 30]
異なるxを仮定しても異なるsが得られますが、すべてのsは(a, b, c)の検証に利用できます。
以上により4つの制約を持つR1CSを得ました。完全なR1CSは以下の通りです：
A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]
ステップ3：R1CSからQAPへ
次に、このR1CSをQAP形式に変換します。QAPは内積ではなく多項式を使用する点を除けば、まったく同じ論理を実現します。変換方法は、6成分のベクトル4組から、3次多項式6組に変換します。各x座標での多項式の評価が、それぞれの制約条件を表します。つまり、x=1で多項式を評価すれば最初のベクトルが得られ、x=2であれば2番目のベクトルが得られ、以降同様です。
この変換にはラグランジュ補間を使います。ラグランジュ補間は、一連の点（(x, y)座標のペア）を与えられたとき、それらすべてを通る多項式を求める手法です。問題を分解し、各x座標に対して、そのxでのみ必要なy値を取り、他の関心あるx座標ではy=0となる多項式を作成し、最後にそれらをすべて足し合わせます。
具体例を見てみましょう。点(1,3), (2,2), (3,4)を通る多項式を求めたいとします。まず、(1,3), (2,0), (3,0)を通る多項式を作ります。実は、x=1で立ち上がり、他の関心点で0になる多項式は簡単に作れます：
y = (x - 2) * (x - 3)
下図の通り：
次に、y軸方向に「引き伸ばし」を行います：
y = (x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))
整理すると：
y = 1.5 * x**2 - 7.5 * x + 9
これは(1,3), (2,0), (3,0)の3点を通ります。下図：
(2,2)と(3,4)を代入することで：
y = 1.5 * x**2 - 5.5 * x + 7
これが求める多項式です。上記アルゴリズムはO(n³)時間が必要です。n個の点があり、各点ごとにO(n²)時間がかかるためです。少し工夫すればO(n²)に減らせ、さらに高速フーリエ変換などを用いればさらに削減できます。これは、zk-SNARKで使われる関数が数千以上のゲートを持つことが多い状況で極めて重要な最適化です。
ここではラグランジュ補間公式を直接示します：
n個の点(x₁,y₁),(x₂,y₂),...,(xₙ,yₙ)を通るn-1次多項式は：
例えば上記の(1,3), (2,2), (3,4)を通る多項式は：
この公式を使えるようになったら、次のステップに進みます。ここでは、6成分の三つ組ベクトル4組を、6組の多項式（各々3つの3次多項式）に変換します。各x点で異なる制約を評価します。ここでは4つの制約があるため、x = 1,2,3,4 の各点で多項式を評価します。
ここでラグランジュ補間を使ってR1CSをQAP形式に変換します。まず、4つの制約に対応する各aベクトルの第1成分の多項式を求めます。すなわち、点(1,0), (2,0), (3,0), (4,0)を通る多項式をラグランジュ補間で求めます。同様にして、各ベクトルの第i成分に対応する多項式をすべて求めます。
ここでは直接答えを示します：
A多項式
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B多項式
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C多項式
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
これらの係数は昇順に並んでいます。たとえば最初の多項式は 0.833 * x³ - 5 * x² + 9.166 * x - 5 です。x=1 を18個の多項式に代入すると、最初の制約の3つのベクトルが得られます：
(0, 1, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0),
...
同様にx=2,3,4を代入すれば、R1CSの残りの部分も復元できます。
ステップ4：QAPの検証
R1CSをQAPに変換することで、R1CSのように個別に各制約をチェックするのではなく、多項式の内積演算を使ってすべての制約を同時にチェックできます。下図の通り：
この場合、内積検査は一連の多項式の加算・乗算であり、結果自体も多項式になります。この多項式が、前述の各論理ゲートに対応するすべてのx座標で0になるならば、すべての検査を通過したことになります。もし結果の多項式が少なくとも一つの非零値を持つならば、それは論理ゲートの入出力が不整合であることを意味します。
得られた多項式自体がゼロである必要はないことに注意してください。ほとんどの場合、それはゼロではありません。論理ゲートに対応しない点では任意の振る舞いをしてよいのです。重要なのは、すべてのゲートに対応する点で値がゼロになることです。正しさを検証するために、t = A . s * B . s - C . s を各ゲートに対応する点で計算するのではなく、tを別の多項式Zで割り、Zがtを均等に割り切るか（つまり余りがないか）をチェックします。
Zは (x - 1) * (x - 2) * (x - 3) * ... で定義され、これはすべての論理ゲートに対応する点でゼロになる最も単純な多項式です。代数学の基本事実として、すべてのこれらの点でゼロになる多項式は必ずこの最小多項式の倍数でなければなりません。Zの倍数であれば、これらの点すべてでゼロになります。この等価性が私たちの作業を容易にしてくれます。
では、上記の多項式で内積検査を行いましょう。
まず、中間多項式を求めます：
A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]
（訳者注：計算過程：
43.0 = -5 * 1 + 8 * 3 + 0 * 35 - 6 * 9 + 4 * 27 - 1 * 30，
-73.333 = 9.166 * 1 - 11.333 * 3 + 0 * 35 + 9.5 * 9 - 7 * 27 + 1.833 * 30，
...
-3 = 3 * 1 - 2 * 3 + 0 * 35 + 0 * 9 + 0 * 27 + 0 * 30
...）
上記多項式を A . s * B . s - C . s で計算すると：
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
（訳者注：計算過程：
A . s = [43.0, -73.333, 38.5, -5.166] = -5.166 * x³ + 38.5 * x² - 73.333 * x + 43,
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x³ - 5 * x² + 10.333 * x - 3.0,
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x³ - 24.5 * x² + 71.666 * x - 41.0
A . s * B . s - C . s を計算し、低次から高次へ係数を並べて得られる）
最小多項式は：
Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)
すなわち：
Z = [24, -50, 35, -10, 1]
この計算はこちらで確認できます。
次に多項式の除算を計算します：
h = t / Z = [-3.666, 17.055, -3.444]
hは余りなしで割り切れなければなりません。
逆検証はこちらで確認できます。
これでQAPの解が得られました。もしR1CSの変数を偽造して（たとえばsの最後の数字を30ではなく31に設定して）QAPの解を導こうとしても、t多項式の検査は失敗します（この場合、x=3で1となり0にならない）。またZの倍数にもならず、t/Zは[-5.0, 8.833, -4.5, 0.666]という余りを生じます。
以上は非常に単純な例にすぎません。現実世界では、加減乗除は通常、非標準的な数体系で行われ、我々が知り愛する代数法則は依然として有効ですが、すべての答えは特定のサイズの有限体の要素、通常は0からn-1までの整数nの範囲内に収まります。たとえばn=13の場合、1/2=7（7*2=14≡1 mod 13）、3*5=15≡2 mod 13などとなります。有限体の算術を使うことで丸め誤差の心配がなくなり、楕円曲線との連携も可能になり、最終的にzk-SNARKプロトコルを真に安全なものにしています。
TechFlow公式コミュニティへようこそ
Telegram購読グループ：https://t.me/TechFlowDaily
Twitter公式アカウント：https://x.com/TechFlowPost
Twitter英語アカウント：https://x.com/BlockFlow_News
@VitalikButerin
