算术化

算术化

算术化是将计算编码为代数约束满足问题的过程。这将检验其正确性的复杂性降低到少量概率代数检查。在证明系统中，算术化的选择会影响IOP的选择范围

## 一、高效密码学运算

a.离散傅里叶变换

傅里叶变换可以将一个信号分 解成一系列正弦和余弦函数的叠加。

离散傅里叶变换(DFT)：

其中一个应用场景：每个约束都是一个多项式，可利用DFT做到整合成一个多项式且保证信息不丢失。

b. 单位根(Root of unity)

• 称 $𝑥^𝑛 = 1$ 在复数意义下的解是 𝑛 次复根。
• 这样的解有 𝑛 个，称这 𝑛 个解都是 𝑛 次 单位根 或 单位复根 （the 𝑛-th root of unity）。
• 根据复平面的知识，𝑛 次单位根把单位圆 𝑛 等分。

如复平面所示为 $x^3 -1$ 的三次单位根等分情况（ $x=1$ 旋转 $0$, $\frac{2π}{3}$, $\frac{4π}{3}$ ）

c.典型数学难问题类型

数学难问题知识补充：

P： 表示可以由确定性图灵机，确定在多项式时间内解决的判定问题，这也是目前经典计算机的运算能力。

NP：由非确定性图灵机可以在多项式时间内解决的判定问题，不确定有没有多项式解决算法，但可以通过验证的方法得出正确解，所有的P问题都是NP问题。

NP-Hard：如果所有 NP 类问题都可以在多项式时间内规约到问题 H，那么问题 H 是 NP-hard 的。NP-Complete：如果一个问题，既是NP类问题，又是NP-hard问题，这是零知识证明的基础。

难度：DLP > CDH > DDH

1.离散对数问题（The Discrete Logarithm Problem, DLP）

离散：有限域而非实数域，但需要注意，不是所有的离散对数问题都是困难的。

应用：

• 椭圆曲线

• DH密钥交换协议，在不安全的通道，通过 shared secret 建立安全的传输。

• Schnorr Protocol

  符合完美零知识(见下文区别中介绍)，最后的 $z$ 中， $r$ 的随机性保护了 $s$ 。Schnorr的签名方案是一个经典的Sigma协议，具有Special Honest-Verifier Zero-knowledge property。

2.计算性DH问题（The Computational Diffie-Hellman Problem, CDH）

属于功能性问题，功能性问题的回答不止 YES/NO，可以是一个数或是其它。如「求两个数的和」就是一个功能性问题。

3.判定性DH问题（The Decisional Diffie-Hellman Problem, DDH）

只能用 YES/NO 回答的问题，本质上是判断是否属于某一种语言(是一个抽象的概念，通常意义上的字符串是语言，所有的有向无环图也可以是一个语言)。

二、例1：R1CS到QAP


a.一阶约束系统 (Rank-1 Constraint System, R1CS)

本质是一个方程组，由一个 R1CS 是一个由三个向量构成的向量组 $(\vec{a},\vec{b},\vec{c})$ ，假设 R1CS 的解也是一个向量，记为 $\vec{x}$ ，其中 $·$ 表示向量内积， $∗$ 表示算数乘法： $$ (\vec{x}·\vec{a}) * (\vec{x}·\vec{b}) =(\vec{x}·\vec{c}) $$

b.二次算术程序（Quadratic Arithmetic Program，QAP)

是一种将语句转换为多项式上二次方程组的方式，它们可以通过线性交互式证明LIPs、代数IOPs、多线性IOPs 等不同信息论协议进行检验。

QAP 实现了与 R1CS 完全相同的逻辑，只不过使用的是多项式而不是向量内积。任何具有乘性复杂度 $n$ 的电路都可以转换为一个 $n$ 次多项式的QAP。通过QAP 转换，可以将算术电路（计算问题）转换为二次多项式形式，等式中的每个变量至多为二次，形式为： $$\sum_{k}{A_{𝑖k}z^k} * \sum_{k}{B_{𝑖k}z^k} = \sum_{k}{C_{𝑖k}z^k}$$ QAP判定：

一个度数（多项式最高次）为 $d$ 、大小为 $m$ 的二次算术程序 $Q$ 由多项式， 和一个目标多项式 $T(X):=\prod_{i = 0}^{d-1}{(x-i)}$ 组成。当赋值 $(1,x_1,…,x_{m−1})$ 满足 $Q$ 时，有 $$𝑃(𝑋）:= 𝐿(𝑋) · 𝑅(𝑋) − 𝑂(𝑋)$$，其中

丨：整除

$$ 𝑇(𝑋) ∣ 𝑃(𝑋) $$

此外，在转换的同时会构建一个对应于代码输入的解（又称为 QAP 的 Wit­ness），之后再基于这个 Wit­ness 构建一个实际的零知识证明系统

c.实现步骤

以IsZero()判零函数（见算术点路应用章节a.①）为例，或从comparators.circom中获取的IsZero电路。

1.Flattening扁平化（通过代码构建树，将算术点路扁平化）

out <== −in * inv + 1

in * out === 0

“展平” 为四个约束条件(在算术电路表示中，每个约束条件对应于一个加法或乘法门)，每个都采用 左侧 · 右侧 = output 的形式：

g：门gate

• $𝑔_0： 𝑤_1 · −1 = 𝑤_2$
• $𝑔_1：𝑤_2 · 𝑤_3 = 𝑤_4$
• $𝑔_2： (𝑤_4 + 1) · 1 = 𝑤_5$
• $𝑔_3： 𝑤_1 ⋅ 𝑤_5 = 𝑤_6$

2.结果转换为R1CS（从计算问题转为矩阵式）

为满足 $L\vec{x}·R\vec{x}=O\vec{x}$ 形式，创建三个线路向量 $\vec{l_i}$、 $\vec{r_i}$ 、 $\vec{o_i}$ ，其中包含门中每个变量 $\vec{w_i}$ 的系数，线路向量还包括一个常数项 $\vec{w_0}$ ，即算上常数项共七列 $(w_0,w_1, w_2,w_3, w_4,w_5, w_6)$

分别收集三个线路向量到矩阵 $L$， $R$ ， $O$ ，与见证向量(Witness，证明人声称知道一些合法的赋) $\vec{x} = (1,x_1, x_2, x_3, x_4, x_5, x_6)$ 一起，构成了判零电路的R1CS形式。

$$ L= \left( \begin{matrix} \vec{l_0}:0 & 1 & 0 & 0 & 0 & 0 & 0\\ \vec{l_1}:0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \vec{l_2}:1 & 0 & 0 & 0 & 1 & 0 & 0\\ \vec{l_3}:0 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} \right) $$

$$ R= \left( \begin{matrix} \vec{r_0}:-1 & 0 & 0 & 0 & 0 & 0 & 0\\ \vec{r_1}:0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \vec{r_2}:1 & 0 & 0 & 0 & 0 & 0 & 0\\ \vec{r_3}:0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix} \right) $$

$$ O= \left( \begin{matrix} \vec{o_0}:0 & 0 & 1 & 0 & 0 & 0 & 0\\ \vec{o_1}:0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \vec{o_2}:0 & 0 & 0 & 0 & 0 & 1 & 0\\ \vec{o_3}:0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} \right) $$

3.R1CS转为QAP（矩阵式转为多项式）

不管结果多简单，过程是复杂的，要验算的东西即组成的多项式也很复杂，所有的中间变量都会成为输入。

注：circom是从代码到R1CS，他下面还有个 snarkjs工具框架，将R1CS生成QAP

将度数 $d$ 视为约束的数量，将规模 $m$ 视为变量的数量。在我们的例子中，有 $d=4$, $m=7$ 。通过将R1CS形式转换为QAP形式，从三次矩阵乘法降低到单项式恒等式。

在每个变量 $j$ 和门 $i$ 处，我们希望 $L_j(i)$ 选择门 $g_i$ 的左导线的变量 $w_j$ 的系数；$R_j(i)$ 和 $O_j(i)$ 同理，根据QAP判定式判断是否成立。

$L_j(i) = L_{ij} = \vec{l}_i[j]$

$R_j(i) = R_{ij} = \vec{r}_i[j]$

$O_j(i) = O_{ij} = \vec{o}_i[j]$

其中，在构造 $L_j$ 时，我们将每个 $L_j$ 设置为在评估点 $(0,…,d−1)$ 列 $L[j]$ 中的值的插值多项式； $R_j$， $O_j$ 同理。

拉格朗日插值：

注意实际运行时有限域，无小数

1. 找到一个多项式，经过四个关键点
2. 当处在某个控制点 $x_i$ 的情况下，除了该点有值，其他的控制点值为0

实际是多个多项式相加而得，$y_i$ 为缩放系数，给定点和评估 ${(x_i,y_i)}_{i=0}^{d−1}$ ，我们可以构造一个插值多项式 $L(X)$，使 $L(x_i)=y_i$ :

$$L(X):=\sum_{i=0}^{d-1}{y_i·L_i(X)}$$ 其中， $L_i(X)$ 是穿过评估点{ ${x_0,…,x_{d−1}}$ } 的拉格朗日基本多项式：

注：得出一个多项式，就成了上节承诺方案的输入

三、例2：代数中间表示AIR

R1CS生成不一定是QAP，根据不同框架，这里是到AIR，相当于分别是不同的算术化方法

代数中间表示（Algebraic Intermediate Representation, AIR），是由一组均匀计算（uniform computations，均匀性是指数据或分布的相似程度。在统计学中，均匀性的计算通常是指方差或标准差）组成的程序表示，是 StarkWare 在其虚拟机 Cairo 中使用的算术化过程。

a.特点

AIR框架数学上实现简单，构建出那么一个表格（轨迹矩阵，像机器语言底层系统，故也有的称AIR为机器计算），所有多项式乘在一起就得出唯一多项式。

1. 计算执行轨迹。表示为执行迹矩阵 T ，行表示在给定时间点的计算状态，列对应于一个代数寄存器在所有计算步骤中的状态变化。
2. 转换程序。约束了迹矩阵 T 两行或多行之间的关系。
3. 边界约束。确保了执行中某些单元格和特定常量之间的相等关系。

b.以Fibonacci为例论证过程

1.执行轨迹Table

表格高度是固定的，像circom在运行时不可变更（树的高度固定）

Step	a	b
i=1	1	1
i=2	2	3
i=3	5	8
i=4	13	21

2.转换程序

我们可以使用两个状态转换多项式来指定 Fibonacci 数列的 AIR 程序：

$f_1(X_1,X_2,X_1^{next} ,X_2^{next})=A^{next}-(B+A)$

$f_1(X_1,X_2,X_1^{next} ,X_2^{next})=B^{next}-(B+A^{next})$

3.边界约束（结果应 = 0）

例如，我们可以检查在第 i=2 行状态转换是否成立：

$f_1(X_1,X_2,X_1^{next} ,X_2^{next})=5−(3+2)=0$

$f_2(X_1,X_2,X_1^{next} ,X_2^{next})=8−(5+3)=0$

c.PAIR, Preprocessed Algebraic Intermediate Representation

带预处理的AIR，以在转换程序中同时启用乘法和加法。

d. RAP, Randomized AIR with Preprocessing

带预处理的随机化AIR，以实现多重集合相等性检查。允许交互轮次引入验证器随机性 $γ$ ∈ 有限域 $F$。在稍后的轮次中，可以将较早轮次的随机性用作约束中的变量。这使得本地约束（相邻行之间）可以检查全局属性。

e.利用AIR构造ZKVM

针对AIR框架，STARK、SNARK（一开始NIZK用得最多，后面加的succint性质）是人为定义的schema，是一种性质，不是很具体的框架，STARK提出者(公司STARKNET)底层用的AIR，同时可以认为STARK也属于SNARK一种实现方式

通常见到AIR就是已经封进了ZKVM中，可以实现传统代码，像StarkNet的Cairo，开放给用户来写代码，不涉及到AIR底层

算术化步骤：

将待验证计算问题转换为检查某个多项式，分两步：

• 第一步

• 构建执行踪迹表格

• 用多项式描述表格中各行/列间的数学关系

• 第二步： 将这两个对象转换为一个低次多项式

  • 利用纠错码将执行轨迹转为多项式

    哪怕仅一处错误的执行轨迹，会被纠错码放大，以至于与原执行轨迹几乎完全不同

• 扩展至更大的域

• 用多项式约束将其转为低次多项式