零知识证明-ZK-SNARKs基础(七)

前言
这章主要讲述ZK-SNARKs 所用到的算术电路、R1CS、QAP等

1:算术电路
算术运算电路
1>半加器：实现半加运算的逻辑电路
2>全加器：能进行被加数，加数和来自低位的进位信号相加，并根据求和结果给出该位的进位信号
说明：2进制加，低位进位 相当于 结果S为 = A+B+C(地位进位)
高位进位 = A+B+C(地位进位) 三个中 有最少2个为1 高位就有进位了

【1】 方程转算术电路
电路实现参考 https://blog.csdn.net/qq_34793644/article/details/121146036
这里以程序角度去讲解
eg: x³ + x + 5 == 35

// Signal Definition:
// 1、所有的输入都是信号
// 2、每次将两个信号相乘时，都需要定义一个新的信号
// 3、一次只能占用两个信号来获取一个新的信号
// 4、所有的输出都是信号

sym1 = X * X
sym2 = sym1 * X
sym3 = sym2 + X
OUT = sym3 +5

约束 = 4 （上面共4条）

s={ONE,X,OUT,sym1,sym2,sym3} 一共6个 变量
m 为变量数（还需要加个ONE，所以为m+1）

【2】电路转换成R1CS（Rand-1 Constraint System）
表示计算式的电路转化为向量点积（内积）的形式，即一阶约束系统（Rank-1 Constraint System, R1CS）。R1CS是由三个向量(a, b, c)组成的序列，R1CS的解是一个向量s，其中s必须满足方程
s . a * s . b - s . c = 0

其中 . 代表内积运算。
对于每个门电路，需要定义一组向量(l, r, o)，通过向量内积运算使得s∙l×s∙r-s∙o=0，其中s代表全部输入组成的向量，即s=[one, x,y,sym1,C]（元素排列没有固定顺序），one表示值为1的虚拟变量
//有效的 R1CS 必须每个约束（在 R1CS 中的一行，在 Circom 中 <==）只有一个乘法。
//如果我们尝试做两个（或更多）乘法，
//这将失败。所有具有多个乘法的约束都需要拆分为两个约束
运算过程如下(手算步骤)



把一个解代入 得到 S 的列所有的值 这里 根是 3 ， one 固定值

演算过程参考了 https://blog.csdn.net/jambeau/article/details/121175433

最后 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]

【3】R1CS 到 QAP
拉格朗日插值法
参考 https://www.bilibili.com/read/cv22217905/
先说插值法。插值法是做什么用的？插值法是通过已知点，求过这些点的未知函数的数学方法。
所以我们输入的，是一堆点，也就是一堆x和一堆y。
我们想要得到的，是一个函数，这个函数能完美的通过这一堆x和这一堆y。
那你要怎么解决这个问题呢？说白了很简单，就是一个开开关的问题。
这就是拉格朗日插值法的想法。

基本公式

参考别人的 https://www.bilibili.com/read/cv22217905/

P(x) = P(x0)+P(x1)+P(x2) //X 下标从0 开始
L2(x)=l0(x)f(x0)+l1(x)f(x1)+l2(x)f(x2)

eg: 一个多项式经过(1,3),(2,2)和(3,4) ,求多项式

也可以用牛顿插值法 参考 https://www.bilibili.com/read/cv22217905/

现在我们要将四个长度为六的三向量组转化为六组多项式，每组多项式包括三个三阶多项式，我们在每个 x 点处来评估不同的约束，在这里，我们共有四个约束，因此我们分别用多项式在 x = 1,2,3,4 处来评估这四个向量组。
现在我们使用拉格朗日差值公式来将 R1CS 转化为 QAP 形式。我们先求出四个约束所对应的每个 a 向量的第一个值的多项式，也就是说使用拉格朗日插值定理求过点 (1,0), (2,0), (3,0), (4,0) 的多项式，类似的我们可以求出其余的四个约束所对应的每个向量的第i个值的多项式
结果如下
A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[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]

怎么算的呢，这里以A 为例（参考 https://blog.csdn.net/smilejiasmile/article/details/122664331）
多项式在 x = 1,2,3,4 处来评估这四个向量组 （这个就是假设 x 过1,2,3,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]
那么点就是 (1,y0), (2,y1), (3,y2), (4,y3) 因为 假设的 x 过1,2,3,4点
把A的第一列 4个数字带入 y 得
(1,0), (2,0), (3,0), (4,5)

再用拉格朗日插值法求多项式同理 可以算出 A得第2列…第N列
同理 也可以算出 B，C 的第1列 …第N列

0.833 * x³ - 5 * x² + 9.166 * x - 5 = -5 + 9.166 * x + 5 * x² + 0.833 * x³
[-5.0, 9.166, -5.0, 0.833] 系数是升序排序的即 a+b X+ c X² + d X³ （a b c d为系数）
最后得

A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[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]

抄下别人的

演示:
A1(x) * B1(x)-C1(x)= 0
A1(x) = [-5.0, 9.166, -5.0, 0.833] = -5 + 9.166 * X -5.0 * X² + 0.833 * X³
B1(x) = [3.0, -5.166, 2.5, -0.333] = 3.0 - 5.166 * X +2.5 * X² - 0.333 * X³
C1(x) = [0.0, 0.0, 0.0, 0.0] = 0 + 0 * X +0 * X² + 0* X³ = 0

当 X = 1 时
A1(x) = -5 + 9.166 * X -5.0 * X² + 0.833 * X³ = -5+9.166 -5+0.833 = 0
B1(x) = 3.0 - 5.166 * X +2.5 * X² - 0.333 * X³ = 3.0 -5.166 +2.5 -0.333 = 0
当x = 2时
A1(x) = -5 + 9.166 * X -5.0 * X² + 0.833 * X³ = -5+9.166 * 2 -5 * 2²+0.833 * 2³ = -5+18.332-20+6.664 = 0
B1(x) = 3.0 - 5.166 * X +2.5 * X² - 0.333 * X³ =3.0- 5.166 * 2+2.5 * 2² -0.333 * 2³ = 3.0 -10.332+10-2.664 = 0

同理 X=2 也可以计算出来
最后返现 A(x) * B(x) - C(x) = 0 #当X =（1,2,3,4）j就是假设 X通过的点

最后也抄下别人的，难打字画图了（参考 https://blog.csdn.net/smilejiasmile/article/details/122664331）

Circom snarkjs 都有相应的程序库，有空讲述下用程序实现

如果觉得有用，麻烦点个赞，加个收藏