Vitalik の QAP についての記事についてのメモ。
証明する対象になる式
$x^3 + x + 5 = 35$
この式の解は $3$ 。
式からロジックゲート
上の式を、以下の ２ つの式の組み合わせに変換する
- $x = y$ ( $x$ は変数。$y$ は変数か数字)
- $x = y;(op);z$ ( $x$ は変数。$op$ は $+, -, *, /$ 。$y$ と $z$ は、変数、数字、式のいずれか)
すると、このようになる。
- $ sym_1 = x * x $ // $x^2$
- $ y = sym_1 * x $ // $x^3$
- $ sym_2 = y + x $ // $x^3 + x$
- $ ~out = sym_2 + 5 $ // $x^3 + x + 5$
この各行がロジックゲートになる。
ロジックゲートからR1CS (Rank-1 Constraint System)
ロジックゲート群で使われている変数に、式の解も含めて、値を割りあてる。
具体的には、式の解は $3$ なので $x=3$、$33=9$ なので $sym_1=9$、$93=27$ なので $y=27$、$27+3=30$ なので $sym_2=30$、$30+5=25$ なので $out=35$ とする。また、それに加えて、$one=1$ を追加する。
結果、以下のようになる。
| 変数 | 値 |
|---|---|
| $one$ | 1 |
| $x$ | 3 |
| $out$ | 35 |
| $sym_1$ | 9 |
| $y$ | 27 |
| $sym_2$ | 30 |
この値ベクターを $ s=[1,3,35,9,27,30] $ とする。
ここで、各ゲートを $ a.s \cdot b.s - c.s = 0$ の形の変換する（ $a.b$ は、$a$ と $b$ の内積）。変換した結果できた $(a,b,c)$ の組を制約と呼ぶ。
$sym_1 = x * x $ は、$9 = 3 * 3$なので、$3 * 3 - 9 = 0$とかける。これをsとの内積で表すと、
$3=[0,1,0,0,0,0].s$ で、$9=[0,0,0,1,0,0].s$ なので、
a=[0, 1, 0, 0, 0, 0] \\
b=[0, 1, 0, 0, 0, 0] \\
c=[0,0,0,1,0,0]
になる。
$y = sym_1 * x$ は、$9 * 3 - 27 = 0$ で、
a = [0, 0, 0, 1, 0, 0] \\
b = [0, 1, 0, 0, 0, 0] \\
c = [0, 0, 0, 0, 1, 0]
$sym_2 = y + x$ は、$27 + 3 - 30 = 0$ で、掛け算がないので、$(27 + 3) * 1 - 30 = 0$ のように考えて、
a = [0, 1, 0, 0, 1, 0] \\
b = [1, 0, 0, 0, 0, 0] \\
c = [0, 0, 0, 0, 0, 1]
$~out = sym_2 + 5$ は、$30 + 5 - 35 = 0$ で同じく掛け算がないので、$(30 + 5) * 1 - 35 = 0$ と考えて、
a = [5, 0, 0, 0, 0, 1] \\
b = [1, 0, 0, 0, 0, 0] \\
c = [0, 0, 1, 0, 0, 0]
各ロジックゲートの $a, b, c$ を、$A,B,C$ としてまとめると、
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。式の変数への値の割り当てである $s$ をこの R1CS の Witness と呼ぶ。
R1CSからQAP
ここで、R1CS の行列を転置する。例えば $A$ を、
A // R1CS
[0, 1, 0, 0, 0, 0] // constraint 1 for A
[0, 0, 0, 1, 0, 0] // constraint 2 for A
[0, 1, 0, 0, 1, 0] // constraint 3 for A
[5, 0, 0, 0, 0, 1] // constraint 4 for A
から、
[0, 0, 0, 5] // 1st element of constraint 1,2,3,4 of A
[1, 0, 1, 0] // 2nd element of constraint 1,2,3,4 of A
[0, 0, 0, 0] // 3rd element of constraint 1,2,3,4 of A
[0, 1, 0, 0] // 4th element of constraint 1,2,3,4 of A
[0, 0, 1, 0] // 5th element of constraint 1,2,3,4 of A
[0, 0, 0, 1] // 6th element of constraint 1,2,3,4 of A
として、各行について、3 次の多項式 $P$ を作って、$[P(1), P(2), P(3), P(4)]$ が、各行になるように、ラグランジェ補完を使って、$P$ の係数を調整する。言い換えると、$P$ を、$ x={1,2,3,4} $ で行の各点を通るような曲線を描く多項式にする。
例えば、 $[0, 0, 0, 5]$ の場合、$P(1)=0, P(2)=0, P(3)=0, P(4)=5$ のようにする。
そして、そのように計算した係数を次数の低い順に並べたベクターを、$ [x^0の係数, x^1の係数, x^2の係数, x^3の係数]$ のように、各行に対して作る。
こうすると、各行について、以下のような同じサイズの係数のベクターができる。
A
[-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] // [0, 0, 0, 0] に対応
[-6.0, 9.5, -4.0, 0.5] // [0, 1, 0, 0] に対応
[4.0, -7.0, 3.5, -0.5] // [0, 0, 1, 0] に対応
[-1.0, 1.833, -1.0, 0.166] // [0, 0, 0, 1] に対応
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]
これが QAP のインスタンスになる。
ここから R1CS と同じ情報を引き出すことができる。例えば、$A$ を $x=1$ で評価すると、R1CS の $A$ の一つ目のベクター $[0, 1, 0, 0, 0, 0]$ になる。以下、計算の詳細。
\begin{align}
[-5.0, 9.166, -5.0, 0.833] &= 0.833x^3 -5x^2 + 9.166x - 5 = 0.833 - 5 + 9.166 - 5 \fallingdotseq 0 \\
[8.0, -11.333, 5.0, -0.666] &= -0.666x^3 + 5x^2 - 11.333x + 8 = -0.666 + 5 - 11.333 + 8 \fallingdotseq 1 \\
[0.0, 0.0, 0.0, 0.0] &= 0 \\
[-6.0, 9.5, -4.0, 0.5] &= 0.5^3 - 4^2 + 9.5x - 6 = 0.5 - 4 - 9.5 - 6 = 0 \\
[4.0, -7.0, 3.5, -0.5] &= -0.5^3 + 3.5x^2 - 7x + 4 = -0.5 + 3.5 - 7 + 4 = 0 \\
[-1.0, 1.833, -1.0, 0.166] &= 0.166x^3 - x^2 + 1.833x - 1 = 0.166 - 1 + 1.833 - 1 \fallingdotseq 0
\end{align}
QAPの正しさの検証
R1CSの制約1~4は、多項式の $x={1,2,3,4}$ の計算結果に対応しているので、$A, B, C$ の係数のベクター群に、対応する $s$ をあらかじめ掛けておいて、更に、$A,B,C$ それぞれについて、全行を足し合わせたものを作っておくと、その多項式を足し合わせたものを評価して０になるかどうかをチェックすることで、対応する制約を満たしているかを確認できる。
例えば、$A$ の係数ベクターに $ s=[1,3,35,9,27,30] $ を掛け合わせて、
\begin{align}
1 \cdot [-5.0, 9.166, -5.0, 0.833] &= 1 \cdot (0.833x^3 -5x^2 + 9.166x - 5) \\
3 \cdot [8.0, -11.333, 5.0, -0.666] &= 3 \cdot (-0.666x^3 + 5x^2 - 11.333x + 8) \\
35 \cdot [0.0, 0.0, 0.0, 0.0] &= 35 \cdot 0 \\
9 \cdot [-6.0, 9.5, -4.0, 0.5] &= 9 \cdot (0.5^3 - 4^2 + 9.5x - 6) \\
27 \cdot [4.0, -7.0, 3.5, -0.5] &= 27 \cdot (-0.5^3 + 3.5x^2 - 7x + 4) \\
30 \cdot [-1.0, 1.833, -1.0, 0.166] &= 30 \cdot (0.166x^3 - x^2 + 1.833x - 1)
\end{align}
全ての多項式を足して、
\begin{align}
A(x) = \\
1*(0.833x^3 -5x^2 + 9.166x - 5) \\
+ 3*(-0.666x^3 + 5x^2 - 11.333x + 8) \\
+ 35*0 \\
+ 9*(0.5^3 - 4^2 + 9.5x - 6) \\
+ 27*(-0.5^3 + 3.5x^2 - 7x + 4) \\
+ 30*(0.166x^3 - x^2 + 1.833x - 1)
\end{align}
と定義する。$B, C$ も同じように定義すると、
$ A(x) * B(x) - C(x) = 0 $
を $ x=1,2,3,4 $ について計算して満たされてるかを確認することで、すべての制約が満たされていることを確認できる。
より効率的なQAPの正しさの検証方法
$x={1,2,3,4}$ で $0$ になるミニマムな多項式は、$(x-4)(x-3)(x-2)(x-1)$ で、これを $Z$ と呼ぶ。
多項式が $x={1,2,3,4}$ で $0$ になることと、多項式が $Z$ の倍数になることは同値なので、これを利用する (1)。
$s$ と $A,B,C$ の内積を計算して、縦方向に足し上げる。例えば、$A$ の１列目を足し上げると、
-5.0 * 1
+ 8.0 * 3
+ 0.0 * 35
+ -6.0 * 9
+ 4.0 * 27
+ -1.0 * 30
= 43.0
になる、このように $A.s, B.s, C.s$ を計算すると、
\begin{align}
A.s &= [43.0, -73.333, 38.5, -5.166]\;//\;-5.166x^3 + 38.5x^2 -73.333x + 43.0 \\
B.s &= [-3.0, 10.333, -5.0, 0.666]\;//\;0.666x^3 - 5.0x^2 + 10.333x - 3.0 \\
C.s &= [-41.0, 71.666, -24.5, 2.833]\;//\;2.833x^3 - 24.5x^2 + 71.666x - 41.0
\end{align}
ここで $ A.s \cdot B.s $ 計算すると、
$ A.s \cdot B.s = -3.44056 x^6 + 51.471 x^5 - 294.72 x^4 + 808.621 x^3 - 1088.25 x^2 + 664.318 x - 129 $
ここから、$C.s$ を引いて $t$ として、
$ t = -3.444x^6 + 51.5x^5 - 294.777x^4 + 805.833x^3 -1063.777x^2 + 592.666x - 88.0 $
（係数のベクターで表すと、$ t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444] $）
ができる。これが、Zの倍数になっている。$Z$を展開すると、
$ Z = x^4 - 10x^3 + 35x^2 - 50x + 24 $
（係数のベクターで表すと、$ Z = [24, -50, 35, -10, 1] $）
$t$を$Z$で割ると、結果が余りなしの$ [-3.666, 17.055, -3.444] $になり、$t$ が $Z$ の倍数であることわかるので、(1) から、多項式が $x={1,2,3,4}$ で $0$ になることになり、制約が全て満たされる。
多項式の割り算
Polynomial Long Division で検索するとやり方が見つかる。
注意点
この例にでてくる数字は、正確な数字ではなくて、小数点４桁以降が削られている。なので、実際に Wolfram Alpha などで割り算をしてみると余りが出る。例えば、計算結果の $ [-3.666, 17.055, -3.444] $ に $Z$ を掛けると、$t$ に近い若干ずれた数字がでてくることからも確認できる；
を、Wolfram Alphaで計算した結果は、
で、$ t = -3.444x^6 + 51.5x^5 - 294.777x^4 + 805.833x^3 -1063.777x^2 + 592.666x - 88.0 $ と比べると若干ずれている。
なお、実際にはQAPは整数のフィールド上で使われるため、このずれの問題は発生しない。
参考ページ