【New】Zk-SNARKs系列(part3)(科普)

以前面两篇短文为基础，将R1CS转换成QAP，需要将向量转换成多项式。
先定义多项式 $A_i(x),B_i(x),C_i(x)$,其中 i $\in$ [1,N], N表示的是约束向量中的元素数目，在本例中，N=4。
令 $A_i(n)=\vec a_{n,i}$,$B_i(n)=\vec b_{n,i}$,$C_i(n)=\vec c_{n,i}$,并基于这些点进行拉格朗日插值(Lagrange interpolation)

在本例中，$A_1(1)=0,A_1(2)=-4,A_2(1)=1,A_2(2)=0$
$B_i$和$C_i$同理可得
基于拉格朗日插值，可以得到下述多项式：
$A_1(x)=-4x+4$
$A_2(x)=-x+2$
$A_3(x)=x-1$
$A_4(x)=0$

$B_1(x)=x-1$
$B_2(x)=-x+2$
$B_3(x)=B_4(x)=0$

$C_1(x)=C_2(x)=0$
$C_3(x)=-x+2$
$C_4(x)=x-1$

基于此可将R1CS表达式用一个方程式表达出来：
$A(x)*B(x)-C(x)=H(x)*Z(x)$

其中 $\vec A(x)=(A_1(x) A_2(x) A_3(x) A_4(x))$
$\vec B(x)=(B_1(x) B_2(x) B_3(x) B_4(x))$
$\vec C(x)=(C_1(x) C_2(x) C_3(x) C_4(x))$
$A(x)=<\vec A,\vec s>$
$B(x)=<\vec B,\vec s>$
$C(x)=<\vec C,\vec s>$
$Z(x)=(x-1)(x-2)$

H(x)需要满足对于任意的x,等式$A(x)*B(x)-C(x)=H(x)*Z(x)$

在列出一堆不知所以的式子之后，读者会忍不住马上问：
1）这些式子究竟是用来干嘛的
2)什么是Z(x)
3)什么是H(x)

为了解答上面这三个问题，先来给出定义：
$\vec A(1)$ = $\vec a_1$
$\vec A(2)$ = $\vec a_2$
对$\vec B(x)$和$\vec C(x)$也给出类似的定义，再结合之前的A(x),B(x),C(x)，可以得出原始的 R1CS 系统相当于
A(x)*B(x)-C(x)=0 ,其中 x$\in${1,2}

而这也意味着多项式A(x)*B(x)-C(x)能够被(x-1)(x-2)整除，即：
$\exists H(x):A(x)*B(x)-C(x)=H(x)(x-1)(x-2)$

这解释了什么是H(x)和Z(x),但由谁计算并给出H(x)呢？

答案必须是证明人，因为基于计算过程(A(x)*B(x)-C(x))/Z(x),计算人可以知道 R1CS 下满足条件的解向量$\vec s$。

那么至此可以把 QAP 看成是由($\vec A(x),\vec B(x),\vec C(x),Z$)所构成的四元矢量组，并且QAP的解向量为$\vec s$

但是！我们需要这些来干嘛呢？

使用 Python 来构建程序会造成一些问题：
1）无法验证Alice运行了正确的程序
2）Bob如何在程序运行之后在不披露其它信息的请款小嘎得以窥见y值犹未可知。

基于将计算式转换成R1CS表达式，如果Bob看到有效的解向量$\vec s$,那么他就可以确定Alice所运行的程序是恰好对应的，而这已经解决了其中一个主要问题。

将R1CS转换成QAP，在数学层面上后者比前者推导多项式更富有成效。


一个巧妙的技巧是我们可以在未知点评估多项式，也叫做多项式的盲估，这在之前的文章中也有提及。
给定多项式：
$P(x)=a_0+a_1x+a_2x^2+...+a_nx^n$
假设有个函数$f(x)$,它具备如下属性：
1）单向：在给出x的情况下容易计算出对应的y值，但是在给出y的情况下，极难计算出满足条件的x值。
2）线性：$f(\alpha x+\beta y)=\alpha f(x)+\beta f(x)$
3)$x\neq y \to f(x) \neq f(y)$

假设Bob想让Alice对多项式P进行盲估，在这种情况下，Bob自然可以通过一个点来验证Alice对多项式的评估结果。
假设函数$f$存在并为双方所共知，首先Bob选择多项式上的点$x_0$,然后将这个点通过函数$f$映射到一个新的点，记作点z,然后将其发送给Alice,因为“单向”属性的存在，所以Alice无法通过点z来找回点$x_0$;再根据第三条性质，Alice无法获知$x_0' \neq x_0$,即$f(x_0')=z$
基于这两条性质，也就意味着Alice无法根据z来获取$x_0$

考虑当$P(x)=a_1x$时，给定$z=f(x_0)$,Alice可以基于$f$函数的线性性质，通过一定的方式计算出 $P(z)=a_1z$
$P(z)=P(f(x_0))=a_1f(x_0)=f(a_1x_0)=f(P(x_0))$

这也就意味着Alice可以在不知道$x_0$的情况下通过计算P(z)来迅速计算出$f(P(x_0))$,那么Bob可以自己比对Alice传回来的$f(P(x_0))$与自己掌握的值，如果比对成功，那么Bob可以确信Alice对多项式p在点$x_0$处的评估结果是准确的，因为如果$x_0' \neq x_0$，那么结果也会不一样。

为了泛化上面提及的方法，使其更具备普遍性，唯一需要作出改变的是Bob向Alice发送更多的信息，具体来说，Bob向Alice发送：
$f(1),f(x_0),f(x_0^2),...,f(x_0^d)$
其中d表示的是所评估多项式的阶数，那么基于此，Alice可以计算：
$f(P(x_0))=f(a_0+a_1x_0+....+a_nx_0^d)=f(a_0)+f(a_1x_0)+...+f(a_dx_0^d)$=$a_0f(1)+a_1f(x_0)+...+a_df(x_0^d)$
那么Bob可以在$f,P,x_0$的基础上检查结果的正确性。