1. 主页
  2. 文档
  3. zk-SNARKS科普
  4. 多项式验证

多项式验证

以前面两篇短文为基础,将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$的基础上检查结果的正确性。

我们要如何帮助您?