basics.md

有限域

为什么ZK证明要求在有限域上运算

1. 计算机只能处理离散的数字，无法精确地处理无限连续的实数域（精确性）
2. Schwartz-Zippel 引理要求域的大小远远大于多项式次数，只有在大的有限域中才成立。（可靠性）
3. 现代ZK（starks，plonk）需要快速进行大量多项式插值与求和。工程实践依赖于有限域的FFT算法。（工程效率）
4. 有限域的模值运算有助于掩盖信息。（安全性）

为什么选取质数域

1. 只有在质数域内，才能保证所有的非零元素都有逆元。在构造代表轨迹的多项式时，为了支撑多项式插值，否则插值过程会直接崩溃。
2. 质数域不存在两个非零数相乘为0（无零因子），合数域存在零因子，多项式碰撞风险急剧上升。

Groth16

graph LR
    A[程序/电路] --> B[R1CS矩阵]
    B --> C[QAP多项式]
    C --> D[ZKG多项式承诺]
    D --> E[ZK证明]

R1CS

Rank-1 Constraint System，秩-1约束系统，意味着每个约束都是秩为1的二次方程（至多包含一个乘法项）

约束形势： $$ A_i \times B_i = C_i $$

R1CS的作用

1. R1CS是ZK证明中必要的中间过程，目的是把任意程序翻译成ZK系统能够理解的统一数学语言
2. 原始的程序可能包含各种复杂运算（包含与，或，位移，条件分支，循环等），ZK系统无法直接理解，需要R1CS将其展开成只包含乘法门和加法门的算术电路。

R1CS的构成

1. 公共输入（public inputs），验证者和证明者都知道的值
2. 私有输入（Private Inputs / Witness），只有证明者知道的值
3. 约束矩阵：三个矩阵 A, B, C，每个约束对应矩阵的一行

QAP

Quadratic Arithmetic Program，二次算术程序。

通过插值把R1CS的约束转化成三个多项式 A(x)，B(x)，C(x)

目标：A(x) * B(x) - C(x) 能否被所有约束点处为0的消失多项式 Z(x) 整除

$$ A(x) \cdot B(x) - C(x) = Z(x) \cdot H(x) $$

QAP的作用

1. 验证者需要检查R1CS的每个约束条件是否满足，有极高的复杂度
2. 经过QAP转变成，只需要检查一个多项式整除，采用随机点检查。从遍历所有门变成检查一个点。

ZKG (BN254)

ZKG 是一种多项式承诺方案（Polynomial Commitment）

ZKG的作用

1. QAP生成的多项式次数是一个极大的值，如果直接发送给证明者，数据量巨大。
2. 如果采用随机点检查的方式，又会遇到证明者看到随机点后可能作弊的问题
3. BN254 是配对友好的椭圆曲线。
   • 承诺压缩：证明者把巨额的系数压缩到椭圆曲线上的一个点发送给验证者
   • 求职证明：验证者随机选取一个点z，证明者给出A(z)，验证者使用配对运算确认A(z)确实来自于多项式
   • 零知识：验证者无法从承诺中反推任何系数

Trusted Setup

1. 第一阶段生成ptao文件：通过多方仪式，生成一组公共参考串CRS（Common Reference String）。证明者和验证者都依靠它来完成自己的工作，但是谁都无法反推出私密参数。必须相信至少一个贡献者是诚实的（销毁了自己的秘密）
2. 第二阶段生成ZKey文件：将通用CRS与具体电路绑定，生成电路特点的参数。