この記事を理解するためのノート。まず、元の記事を読むことを勧める。
zk-SNARKは、どんな計算問題にも直接適用できるわけではなく、問題を適切な「形式」に変換して演算する必要がある。
→ この形式は「quadratic arithmetic program」（QAP）と呼ばれる。
関数のコードをこれに変換すること自体、簡単なことではない。
ステップは2つに分けることができる。今回の記事のカバーする範囲は前者のみ.
- 関数のコードをQAPに変換する処理と同時に、コードの入力があればそれに対応する解（QAPの「Witness」と呼ばれる）を作成するためのプロセス
- witnessに対応する実際の「ゼロ知識証明」を作成するための複雑なプロセスと、他者から渡された証明を検証するためのプロセス
簡単な方程式の例を考えていく。
以下の3次方程式の解を知っていることを証明する。
x**3 + x + 5 == 35 この方程式の解は3。
ここで、基本的な算術（+,-,*,/）、定数乗指数（x**7, x**yは不可）、変数代入をサポートしており、理論的にはその中であらゆる計算ができる（計算ステップ数が一定であれば、ループは不可）ただし、モジュロ演算子(%)と比較演算子(<, >, ≤, ≥)はサポートされていない。
Flattening
“Flattening”は最初の処理で、任意に複雑な文や式を含む元のコードを、次の2つの形式に変換する。
x = y（yは変数または数値）x = y (op) z（opは+,-,*,/で、yとzは変数、数値、またはそれ自身の部分式）
これらの式は、回路における論理ゲートのようなものだと考えることができる。
Flatteningした結果は次のようになる。元のコードとこのコードは等価である。
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5Flatteningには任意性があるので、上記の形以外もありうる。
zCashの記事では、Computation → Arithmetic Circuitのステップを次のように書いている。
論理ステップを可能な限り小さな演算に分解し、「算術回路」を作成することである。ブーリアン回路がAND、OR、NOTのような個別の単一ステップにコンパイルされるのと同様に、プログラムが算術回路に変換されるときは、加算、減算、乗算、除算（ただし、今回のケースでは除算は使わない）の基本演算から成る単一ステップに分解される。
Gates to R1CS
これをrank-1 constraint system（R1CS）と呼ばれるものに変換する。R1CSは3つのベクトル(a,b,c)のグループの列で、R1CSの解はベクトルsで、sは方程式s.a * s.b — s.c = 0を満たす必要がある。.は内積を表す。例えば、これはR1CSを満たす。
- 一つの論理ゲートごとに制約は1つずつある。*
- 論理ゲートを演算が何であるか(+,-,*,/)、引数が変数か数値かによって、
(a,b,c)に変換する標準的な方法がある。
ベクトルsは最初のインデックスに1を表すダミー変数とFlatteningで使われた変数(中間変数を含む)の合計6つの変数を使って
s = ['~one', 'x', '~out', 'sym_1', 'y', 'sym_2']とする。解のベクトルは、これらすべての変数に対する代入をこの順番で並べたものになる。
s = [1, 3, 35, 9, 27, 30]最初のゲートsym_1 = x * x についてs.a * s.b — s.c = 0を満たす(a,b,c)探してみる。
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]とすると、解ベクトルの2番目と4番目の内積が残り 3 * 3 — 9 = 0となるのでs.a * s.b — s.c = 0を満たしていることがわかる。
ここで気づくこと
- 解のベクトルの2番目と4番目以外の要素がどんな値で
3 * 3 = 9になるからs.a * s.b — s.c = 0をパスする。例：s = [1, 3, 1, 9, 27, 1] - 解のベクトルの2番目と4番目の要素が打ち消し合えば
s.a * s.b — s.c = 0をパスする。例：2番目と4番目がそれぞれ7と9のときs = [1, 7, 35, 9, 49, 30]
この最初のチェックの目的は、最初のゲートの入出力の整合性のみを確認すること。
計算のトレースを小さなステップに分割して各ステップでの計算の整合性を確認することに対応する.
2つ目のゲートも同様にして、
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]3つ目のゲート:
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]4つ目のゲート:
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]4つをまとめると、4つの制約を持つR1CSは次のようになる。
A // 4つの制約の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 // 4つの制約の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 // 4つの制約の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]
witnessは、入力、出力、内部変数を含むすべての変数への単純な代入である。
[1, 3, 35, 9, 27, 30]R1CS to QAP
次のステップは、このR1CSをQAP形式に変換することである。
QAPは、ドット積の代わりに多項式を用いる以外は、全く同じロジックを実装している。これは次のように行う。長さ6の3つのベクトルからなる4つのグループのR1CSから、次数3の多項式からなる6つのグループへ変換する。各x座標で多項式を評価することで制約の1つを表す。x = 1で多項式を評価すると、最初のベクトル群が得られ、 x = 2で多項式を評価すると、2番目のベクトル群が得られ、以下同様である。
元の記事では例を挙げてラグランジュ補完の説明があるが、ここでは省略
k個の点を通るk-1次多項式は一意に定めることができる。ラグランジェ補完を使ってR1CSを変換する。
手順：
- すべての
aベクトルから最初の値を取り出し、ラグランジュ補間を使ってその中から3次の多項式を作る。 - このプロセスをすべての
aベクトルの最初の値に対して繰り返す。つまり、x = iで多項式を評価するとi番目のaベクトルの最初の値を得られる。 aベクトルの2番目の値、3番目の値、・・・と繰り返していく。- これを
bとcのベクトルに対しても行う。
具体的には、
A // aベクトルの集まり
[0, 1, 0, 0, 0, 0] // 1番目のゲートのaベクトル
[0, 0, 0, 1, 0, 0] // 2番目の...
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]を転置して、
[0, 0, 0, 5] // すべてのaベクトルの1番目の要素
[1, 0, 1, 0] // ...2番目の要素
[0, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 1]全てのaベクトルの1番目の要素(転置した行列の最初の行)[0,0,0,5]を使って、P(1) = 0, P(2) = 0, P(3) = 0, P(4) = 5となるような多項式Pをラグランジュ補完を使って求めると、Pは
0.833 *x**3 — 5 *x**2 + 9.166*x — 5である。求めた多項式の係数を次数の昇順にベクトルに並べると,
[-5.0, 9.166, -5.0, 0.833] // [Pのx^0の係数, Pのx^1の係数,....][0,0,0,5]に対応する多項式が得られた。次に、ベクトルaの2番目、3番目…のように行い、同様にしてb,cについて行う。すると、答えは次のように得られる。
A polynomials
[-5.0, 9.166, -5.0, 0.833] // [0, 0, 0, 5] に対応
[8.0, -11.333, 5.0, -0.666] // [1, 0, 1, 0]に対応
[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 polynomials
[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 polynomials
[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]
QAPからR1CSと同じ情報を引き出せるか確かめてみる。例えば、Aの多項式をx = 1で評価すると、R1CS のAの一つ目のベクトル(最初の論理ゲートのベクトルa)と一致していることが確認できる。
一行目[-5.0, 9.166, -5, 0.833]は
同様にして、各行にx = 1を代入して、計算結果を縦に並べればいい。
A results at x=1
0
1
0
0
0
0ラグランジュ補完を使って多項式の係数を求めたが、高速フーリエ変換アルゴリズムなどを用いることで、計算量を大幅に減らせる。zk-SNARKで実際に使用される関数が何千ものゲートを持つことが多いため、このような最適化は非常に重要。
zCashの記事では、R1CS → QAPのステップを次のように書いている。
2012年の論文で、Gennaro、Gentry、Parno、Raykovaは、「これらすべての制約を1つに束ねる」優れた方法を紹介しました。この方法では、QAP（Quadratic Arithmetic Program）と呼ばれる回路の表現が用いられる。チェックする必要のある1つの制約が、数値間ではなく多項式間になりました。多項式はかなり大きなものになりますが、多項式間で恒等式が成立しない場合、ほとんどの点で恒等式が成立しないので、これで問題ありません。したがって、ランダムに選んだ1点で2つの多項式が一致することを確認するだけで、高い確率で正しく証明することができる。
Checking the QAP
R1CSからQAP変換のポイント:
R1CSの制約を個別にチェックするのではなく、多項式の内積チェックをすることで、すべての制約を同時にチェックすることができるようになった。
- 論理ゲートを表す各x座標で評価した結果の多項式が0に等しければ、すべてのチェックが通過したことになる。 (論理ゲートを表すx座標の少なくとも1つで評価した結果の多項式が0以外の値を与える場合、その論理ゲートへの入出力値が矛盾していることになる。)
- ゲートに対応するすべての点で多項式の結果がゼロになればいい
正しさを確認するために、ゲートに対応するすべての点で実際に多項式 t = A.s * B.s — C.sがゼロになることを計算する代わりに、次のように確認する。
tを別の多項式Z((x-1)*(x-2)*(x-3)... — 論理ゲートに対応するすべての点で0に等しい最も簡単な多項式)で割り切れることを確認する。
ミニマルな多項式Zは
Z = (x — 1) * (x — 2) * (x — 3) * (x — 4)
= x^4 - 10 x^3 + 35 x^2 - 50 x + 24Z = [24, -50, 35, -10, 1]
まず、A.sは次のようになる。
A.s = [43.0, -73.333, 38.5, -5.166]例えば、A.sのindexの最初の値は次のように内積を計算すればいい。
1 * (-5) + 3 * 8 + 35 * 0 + 9 * (-5) + 27 * 4 + 30 * (-1) = 43.0同様に計算して、t = A.s * B.s — C.sは次のように得られ、
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]Zで割ると割り切れて、QAPの解hを得る。多項式がx = 1, 2, 3, 4 で 0 になることになり、制約が全て満たされている。
h = t / Z = [-3.666, 17.055, -3.444]もし、間違ったsだと多項式tのx = 1, 2, 3, 4結果が0にならない。
参考
計算に便利 https://www.wolframalpha.com/
Week 2の火曜日のセッションで解説している。
さらに詳しく
この記事も解説してる(自分が書き終えた後に見つけた…)
Arithmetic CircuitからQAPへの変換を詳しく説明している。
PLONK
途中に、同様の説明があるので参考になるかも。
https://medium.com/@souiti488/explaining-snarks%E3%81%AE%E8%A7%A3%E8%AA%AC-b1bce7b04c2f
