二次算術プログラム：ゼロ知識証明に関する論述

著者：Vitalik Buterin

原題：《Quadratic Arithmetic Programs: from Zero to Hero》

発表日：2016年12月10日

最近、zk-SNARKs（ゼロ知識証明）に関する技術に多くの関心が寄せられており、多くの人々が「月の数学」と呼ぶものの神秘的なベールを明らかにしようとしています。これは、その複雑さが非常に理解しにくいと考えられているからです。zk-SNARKsの理解は確かにかなりの挑戦を伴いますが、全体のシステムが機能するために組み立てる必要がある移動部品が多すぎるためです。しかし、この技術を一つ一つ分解していけば、理解が容易になります。

この記事の目的は、zk-SNARKsの完全な紹介ではなく、以下の背景知識を持っていることを前提としています：

1- あなたはzk-SNARKsとその大まかな原理を知っている； 2- あなたは十分な数学の知識を持ち、基本的な多項式の知識を理解できる。（例えば、if P(x)+ Q(x)=(P + Q)(x)のように、PとQが多項式を表す場合、このような多項式の表現方法に非常に慣れているなら、あなたは読み続ける資格があります）。

zk-SNARK知識パイプライン図、Eran Tromer作成

上の図のように、ゼロ知識証明は上から下に二つの段階に分けることができます。まず、zk-SNARKは任意の計算問題に直接適用できません。逆に、問題を操作の正しい「形式」に変換する必要があります。この形式は「二次算術プログラム」（QAP）と呼ばれ、関数のコードをこれらのコードに変換すること自体が非常に重要です。関数コードをQAPに変換するプロセスと一緒に実行される別のプロセスがあり、コードに入力があれば、対応する解決策（時にはQAPの「証明」と呼ばれる）を作成できます。これがこの記事で説明する内容です。

その後、QAPの実際の「ゼロ知識証明」を作成するためのかなり複雑なプロセスがあり、他の人から送られてきた証拠を検証するための別のプロセスがありますが、これらの詳細はこの記事の範囲を超えています。

以下の例では、非常にシンプルな問題を選びます：

三次方程式の解を求める：x**3 + x + 5 == 35（ヒント：答えは3です）。

この問題は簡単ですが、重要なのは、このケースからすべての機能がどのように機能するかを見ることができることです。

プログラミング言語で上記の方程式を次のように表現します：

def qeval(x):  
    y = x\*\*3  
    return x + y + 5  

ここで使用しているシンプルなプログラミング言語は、基本的な算術（+、-、*、/）、恒等幂指数（x7、ただし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- 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

上記の各行の宣言は回路内の論理ゲートであり、元のコードと比較して、ここでは二つの中間変数sym1とsym2、そして出力を表す冗長変数~outを導入しています。「フラット化」された宣言の系列と元のコードは等価であることが明らかです。

第二步：R1CSへの変換

次に、これをR1CS（Rand-1制約システム）と呼ばれるものに変換します。R1CSは三つのベクトル(a, b, c)からなる系列であり、R1CSの解はベクトルsであり、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、二つ目の35=35 * 1）

上記の例は一つの制約に過ぎません。次に、各論理ゲート（すなわち「フラット化」された各宣言文）を制約（すなわち(a, b, c)三つのベクトルグループ）に変換します。変換の方法は、宣言が何の演算（+、-、*、/）であり、宣言のパラメータが変数か数字かによって異なります。この例では、「フラット化」された五つの変数（'x', '~out', 'sym1', 'y', 'sym2'）に加えて、最初の成分位置に冗長変数~oneを導入して数字1を表現する必要があります。このシステムにおいて、一つのベクトルが対応する6つの成分は（他の順序でも構いませんが、対応さえすればよい）：

'~one', 'x', '~out', 'sym1', 'y', 'sym2'

第一のゲート

sym1 = x * x、すなわち x*x - sym1 = 0

次のようなベクトルグループを得ることができます：

a = [0, 1, 0, 0, 0, 0]  
b = [0, 1, 0, 0, 0, 0]  
c = [0, 0, 0, 1, 0, 0]

解ベクトルsの第二のスカラーが3で、第四のスカラーが9であれば、他のスカラーが何であっても成立します。なぜなら：a = 3 * 1, b = 3 * 1, c = 9 * 1、すなわちa * b = cです。同様に、sの第二のスカラーが7で、第四のスカラーが49であっても、チェックを通過します。最初のチェックは、最初のゲートの入力と出力の一貫性を確認するためだけです。

第二のゲート

y = sym1 * x、すなわち sym1 * x - y = 0
次のようなベクトルグループを得ることができます：

a = [0, 0, 0, 1, 0, 0]  
b = [0, 1, 0, 0, 0, 0]  
c = [0, 0, 0, 0, 1, 0]

第三のゲート

sym2 = y + x、加法ゲートは次のように変換する必要があります：(x + y) * 1 - sym2 = 0
次のようなベクトルグループを得ることができます：

a = [0, 1, 0, 0, 1, 0]  
b = [1, 0, 0, 0, 0, 0] //定数1に対応し、~oneを使用  
c = [0, 0, 0, 0, 0, 1]

第四のゲート

~out = sym2 + 5、すなわち (sym2 + 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と仮定すると、最初のゲートからsym1 = 9を得て、第二のゲートからy = 27を得て、第三のゲートからsym2 = 30を得て、第四のゲートから~out = 35を得ます。したがって、'~one', 'x', '~out', 'sym1', 'y', 'sym2'に基づいて：

s = [1, 3, 35, 9, 27, 30]

異なるxを仮定すれば、異なるsを得ることができますが、すべてのsは(a, b, c)を検証するために使用できます。

現在、四つの制約の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]

第三步：R1CSからQAPへ

次のステップは、このR1CSをQAP形式に変換することです。これは、内積の代わりに多項式を使用して完全に同じロジックを実現します。私たちはこうします：4組の長さ6の3つのベクトルから6組の長さ3の多項式に変換し、各x座標で多項式が一つの制約条件を表すようにします。つまり、x=1で多項式を求めると、最初のベクトルグループが得られ、x=2で多項式を求めると、第二のベクトルグループが得られ、以下同様です。

ラグランジュ補間を使用してこの変換を行うことができます。ラグランジュ補間法が解決する問題は、もしあなたが一組の点（すなわち(x, y)座標対）を持っているなら、これらの点を通る多項式をラグランジュ補間で得ることができます。私たちは問題を分解します：各x座標に対して、多項式を作成し、必要なy座標のx座標とy座標0を他のすべてのx座標で興味を持ち、最終結果としてすべての多項式を一緒に追加します。

例を見てみましょう。例えば、(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)の三つの点を同時に通ることができます。以下の図のように：

(2,2)と(3,4)の二点を上記の式に代入すると、次のようになります：

y = 1.5 * x**2 - 5.5 * x + 7

これが私たちが欲しい座標方程式です。上記のアルゴリズムはO(n3)の時間を必要とします。なぜなら、n個の点があり、各点に対してO(n2)の時間が必要だからです。少し考えると、これをO(n**2)の時間に減らすことができ、さらに考えると、迅速なフーリエ変換アルゴリズムなどを使用して、さらに減少させることができます------これは重要な最適化です。zk-SNARKsで使用される関数は通常、数千のゲートを持つためです。

ここで、ラグランジュ補間の公式を直接示します：

n個の点(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)を通るn-1次の多項式は：

例えば、上の例で点(1,3)、(2,2)、(3,4)を通る多項式は：

この公式を使いこなすことができれば、私たちのステップを続けることができます。今、四つの長さ6の三つのベクトルグループを六つの多項式に変換します。各グループの多項式は三つの三次多項式を含み、各x点で異なる制約を評価します。ここでは、四つの制約があるため、各多項式をx = 1,2,3,4で評価します。

今、ラグランジュ補間公式を使用してR1CSをQAP形式に変換します。まず、四つの制約に対応する各aベクトルの最初の値の多項式を求めます。つまり、ラグランジュ補間定理を使用して点(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**3 - 5 * x**2 + 9.166 * x - 5です。もしx=1を上記の十八の多項式に代入すると、最初の制約の三つのベクトルが得られます。

(0, 1, 0, 0, 0, 0)、
(0, 1, 0, 0, 0, 0)、
(0, 0, 0, 1, 0, 0)、
…
同様に、x = 2, 3, 4を上記の多項式に代入すると、R1CSの残りの部分を復元できます。

第四步：QAPの検証

R1CSをQAPに変換することで、私たちは多項式の内積演算を通じてすべての制約を同時に検証することができます。R1CSのように各制約を個別に検証するのではなく、次の図のように：

この場合、内積検証は一連の多項式の加算と乗算であり、結果自体が多項式です。得られた多項式が、上記で論理ゲートを表すために使用した各x座標での値が0であれば、すべての検証が通過したことを意味します。もし結果の多項式が少なくとも一つの非ゼロ値を持っている場合、それは論理ゲートの出入りの値が一致しないことを意味します。

得られた多項式自体が必ずしもゼロである必要はなく、実際にはほとんどの場合そうではありません。特定の論理ゲートの点でゼロである限り、他の点でどのような振る舞いをしても構いません。正確性を検証するために、私たちは多項式t = A . s * B . s - C . sを各点で対応するゲートに対して計算しません。代わりに、tを別の多項式Zで割り、Zがtを均等に割り切るかどうかを確認します。つまり、除算t / Zに余りがないことを確認します。

Zは(x - 1) * (x - 2) * (x - 3)…最も単純な多項式であり、すべての対応する論理ゲートの点で0になります。これは代数の基本的な事実であり、すべてのこれらの点でゼロである多項式は、この最小多項式の倍数でなければなりません。もし多項式が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 * x3 + 38.5 * x2 - 73.333 * x + 43、
B . s = [-3.0, 10.333, -5.0, 0.666] = 0.666 * x3 - 5 * x2 + 10.333 * x - 3.0、
C . s = [-41.0, 71.666, -24.5, 2.833] = 2.833 * x3 - 24.5 * x2 + 71.666 * x - 41.0
A . s * B . s - C . sは上記の多項式の計算であり、計算後、幂の低い順に係数を並べると、次のようになります： [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

最小多項式は：

Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)

すなわち：

Z = [24, -50, 35, -10, 1]

上記の計算過程こちらで確認できます%20%5Ccdot%20%5Cleft(x%20-%203%5Cright)%20%5Ccdot%20%5Cleft(x%20-%204%5Cright))。

今、多項式の除算を計算します：

h = t / Z = [-3.666, 17.055, -3.444]

hは余りのない整数除算でなければなりません。

こちらで確認できます%20%5Ccdot%5Cleft(x%20-%203%5Cright)%20%5Ccdot%5Cleft(x%20-%204%5Cright)%5Ccdot%5Cleft(-3.444x%5E%7B2%7D%2B17.055x-3.666%5Cright))。

私たちはQAPの解を得ました。もしR1CS内の変数を偽造し、このR1CSがQAP解を導出した場合------例えば、sの最後の数字を30ではなく31に設定すると、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 = 1）、3 * 5 = 2などです。有限体アルゴリズムを使用することで、丸め誤差の懸念が排除され、システムが楕円曲線と良好に機能することが可能になり、最終的にzk-SNARKプロトコルを本当に安全にすることができます。