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は整数のフィールド上で使われるため、このずれの問題は発生しない。