ZK-STARK（2）：算术化

zk-STARK算法主要分为两步，第一步是算术化（Arithmetization），第二步是低度测试（Low Degree Testing），这里先介绍本篇文章先介绍算术化

算术化将验证计算的问题转化为（约化为）检查某个特定多项式的度是否为低度的，这个过程可以在Verifier端有效的计算，从而构成了协议的简洁性

算术化的用处很大，因为其可以使用纠错码的部分理论来有效的验证多项式的低度性，但是算术化本身只是将CI Statement转换为了多项式，从而可以在协议的后续步骤中进一步处理

算术化本身由两个步骤构成，首先是生成执行轨迹（Execution Trace）和多项式约束（Polynomial Constraints），然后将这两个生成对象转化为内一个低度多项式，从而实际上Prover和Verifier之间的验证就转化为了Prover和Verifier在某个被约束的多项式上达成一致，之后由Prover生成一个执行轨迹，在之后的交互过程中由Prover来说服Verifier在该执行轨迹上满足多项式约束，同时需要确保零知识性

Recap：CI

在之前的简介文章中简单提了一下计算完整性的概念，简单来说就是确保某个计算的输出是正确的，接下来举个例子

假设我们在超市购物，我们需要确认结账账单上的每一项之和等于总价，比如说我们有如下账单

此时CI Statement为：该账单的合计正确

为了验证这个CI Statement是否正确，Verifier可以直接查看这个账单，并按顺序计算合计金额并与最底部的合计进行比较，但是如果这个账单很大，比如说有$10^9$条数据，依此检查并计算就不符合我们需要的简洁性，因此需要算术化

Arithmezation

算术化的第一步是生成CI Statement，这么做的目的有两个

1. 以简洁的方式定义一个明确的声明
2. 将这个声明嵌入到代数域上，从而可以将CI简化为关于特定多项式次数的声明

算术化主要由两部分组成，也即前面提到的执行轨迹（Execution Trace）和多项式约束（Polynomial Constraints），其中执行轨迹实际上是一个列表，列表的每一行都表示一个计算步骤，而多项式约束确保当且仅当执行轨迹表示有效计算时，所有的多项式约束都会被满足

执行轨迹可能会很大（比如账单有$10^9$条数据），但是多项式约束会很简洁

Execution Trace

回到账单的例子，在这个列表中，我们加入一列数据，称之为运行和

当前行的运行和等于上一行的价格加上上一行的运行和，并记第一行的运行和为$0$

Polynomial Constraints

此时需要添加约束，确保每一行的运行和都是正确计算的

比如说，检查牛奶和面包这一行，意味着检查$16.41=12.96+3.45$，也即约束确保运行和被正确计算

接下来把表头去掉，得到一个二元数组，记为$A_{ij}(i,j=0,1,...,5)$

然后把执行轨迹和多项式约束归纳整理一下，我们得到三个约束

1. $A_{0,2}=0$：确保第一行的运行和为$0$
2. $\forall 1\leq i\leq 5,A_{i,2}-A_{i-1,2}-A_{i-1,1}=0$：确保每一行的运行和计算正确
3. $A_{5,1}-A_{5,2}=0$：确保最后的运行和等于合计

可以看到，这个例子中账单一共有六行（算上合计就是七行），但是多项式约束只有三个（第二个约束计算了五次），因此称多项式约束是简洁的，即便是账单有$10^9$行，多项式约束还是只有三个，只不过第二个约束要计算$10^9$次

Collatz Conjecture

接下来看一个更复杂的例子，称为Collatz猜想

1937年，德国数学家Lothar Collatz提出了数论领域的一个猜想

对于任意正整数，其根据下列规则派生一个数列

• 若前一个元素为偶数，则将其除以2，得到下一个数
• 若前一个元素为奇数，则将其乘以3再加1，得到下一个数
• 若当前数为1，结束

Collatz猜想表示，任意正整数经过这样的派生，总会得到1

比如举个例子，以52举例

接下来为以52生成的Collatz序列生成一个CI Statement及其执行轨迹

• CI Statement：以52生成的序列，在11次迭代后以1结束
• Execution Trace：将每次计算后的数字以二进制表示，并将低位排列到左侧，得到下列列表

注意到整个执行轨迹中最大的数为52，因此六个二进制位就可以表示了，也即我们得到了一个12行*6列的数组（如果以51开始，则最大的数为154，需要8个二进制位）

接下来是对这个CI Statement生成对应的多项式约束，具体如下

1. $\sum_{j=0}^52^jA_{0,j}-firstTerm=0$：对于本例，$firstTerm=52$
2. $\sum_{j=0}^52^jA_{n-1,j}-1=0$：确保最后一行为1
3. $\forall i<12,\forall j<5:A^2_{i,j}-A_{i,j}=0$：确保表格中的每一个单元都是二进制位（只有0和1满足这一约束）
4. $\forall i<11:A_{i,0}\cdot [3\cdot(\sum_{j=0}^52^j\cdot A_{i,j}+1-\sum^5_{j=0}2^j\cdot A_{i+1,j}]+(1-A_{i,0})\cdot[\sum_{j=0}^52^j\cdot A_{i,j}-2\cdot \sum^5_{j=0}2^j\cdot A_{i+1,j}]=0$：Collatz猜想的计算过程

重点观察第四个约束，其确保相邻两行之间的计算正确，具体如下

对于$\forall i<11$，记两个临时变量$P^{odd}_i,P^{even}_i$，分别表示前一个数为奇数和偶数，从而有

$$ \begin{aligned}P^{odd}_i&=3\cdot(\sum_{j=0}^52^j\cdot A_{i,j}+1-\sum^5_{j=0}2^j\cdot A_{i+1,j}) \ \ \ (A_i为奇数)\\ P^{even}_i&=\sum_{j=0}^52^j\cdot A_{i,j}-2\cdot \sum^5_{j=0}2^j\cdot A_{i+1,j}\ \ \ (A_i为偶数)\end{aligned} $$

注意到对于所有的$i<11$，都有

$$ A_{i,0}\cdot P^{odd}_i+(1-A_{i,0})\cdot P^{even}_i=0 $$

其中$A_{i,0}$表示列表中每行中最左边的位（该行数字的二进制表示的最低位），因此上述约束代表了Collatz序列的约束

因此，当且仅当所有的执行轨迹满足上述四个约束时，该执行轨迹表示一个合法的Collatz序列

注意到，Collatz序列有n行，若序列中最大的数需要m位二进制位表示，则Collatz序列生成的列表共有$n*m$位二进制位，由于约束不会随着Collatz序列的增长而变大，因此整个约束的表示是简洁的

Error Correction Codes

回顾一下之前提到的简洁性，我们希望Verifier仅向Prover提出很少的请求就可以以一个很高的概率来决定接受或拒绝

理想情况下，Verifier希望Prover提供执行轨迹中若干个随机位置的值，并检查这些执行轨迹是否满足多项式约束，若执行轨迹正确则一定会通过验证，但是恶意的Prover不难构造一个完全错误的执行轨迹，其只在某个点上不满足多项式约束，但是自该点以后的所有执行轨迹与正确的执行轨迹完全不同（因为Verifier只检查了随机的点，且仅检查这些点是否满足多项式约束，并没有检查整个执行轨迹）

举个例子，下面这个图，假如说从0开始（$2^0$）计算2的次幂，第21个数应该是$2^{20}$，如果此时多项式约束为：当前数字为前一个数字的2倍，若Prover修改了某个中间结果（图中红色方块），本来应该为16384，恶意的Prover修改为了15625，若按照依此乘2执行，第21个数为$10^6$而非$2^{20}$，但是若Verifier的随机检查并没有检查到15625，而是检查15625前面或后面的数，这些检查都会满足多项式约束，但是对于15625及其之后的数，都不是一个正确的执行轨迹

因此为了避免这种情况，引入纠错码的技术==编码真的噩梦==，纠错码可以通过在原始字符串中加入冗余，以生成一个完全不同的新的字符串，从而添加纠错的性质

好巧不巧，多项式可以用于构造良好的纠错码，因为在一个比$d$大得多的域上计算两个度为$d$的多项式时，这两个多项式几乎在任何地方都是不相等的，此类性质构成的码称为里德-所罗门码（Reed-Solomon Code），根据这一性质，我们可以将执行轨迹扩展为在某个域上对多项式求值，并在另一个更大的域上对相同的多项式求值（扩域求值），以类似的方式进行扩域后，对于不正确的执行轨迹会得到不同的字符串，且此类方式仍然会保留Verifier只需要少量的检查就可以以一个很高的概率来决定接受或拒绝

因此接下来有三个新的任务需要完成

1. 将执行轨迹重新表述为多项式
2. 将多项式扩展到一个较大的域
3. 使用多项式约束将其转换为另一个多项式，使得当且仅当新的多项式的执行轨迹有效时，其为一个低度多项式

Boolean Execution Trace

接下来介绍一个新的例子，布尔执行轨迹，首先CI Statement如下

CI Statement：Prover有512个数字，这些数字都是0或1

根据简洁性，Verifier希望以远小于512次查询来验证这个CI Statment

和之前提到的一样，首先是生成执行轨迹，其包含512行，每行都有一个单比特来表述，然后构造多项式约束为$A_i^2-A_i=0$，$A_i$表示第$i$行的比特，该约束确保每行的比特都是0或1

为了将执行轨迹重新构造为多项式，这里用一个比512大得多的域$Z_{96769}=\{0,1,...,96768\}$，域上所有的加法和乘法都是模$96796$的计算，然后我们选择这个域的乘法群的一个子群$G\in Z^*_{96769}$，满足$|G|=512$，然后选择生成元$g\in G$，

接下来将执行轨迹中的元素视为对度小于512的多项式$f(x)$的求值，具体如下

$$ \forall 0 \leq i < 512,f(g^i)=A_i $$

意思是对于第$i$个数，将其表示为$g^i$，并令多项式在$g^i$处的值为$A_i$，也即$f(g^i)=A_i$，这样的多项式$f(x)$可以用拉格朗日插值法得到，其度最高为512，若在一个更大的域上计算这个多项式，就会得到我们需要的里德-所罗门码

有了这个多项式之后，还需要做一件事，使用该多项式派生出另一个多项式，使得派生的多项式的低度性取决于在执行轨迹满足多项式约束，这个方法通过多项式的根来做到

Root of Polynomial

多项式的根不难理解，对于多项式$p(x)$，若存在一个$a$，使得$p(a)=0$，则称$a$为多项式的一个根

除此之外，对于根为$a$的多项式$p(x)$，还满足一个性质，也即存在一个多项式$p'(x)$，满足$p(x)=(x-a)p'(x)$，若记多项式的度为$deg()$，则有$deg(p)=deg(p')+1$

不难看出，对于所有的$x\neq a$，我们有$p'(x)=\frac{p(x)}{(x-a)}$

将这个性质推广一下，假设多项式$p(x)$有$k$个根，分别记为$a_0,a_1,...,a_{k-1}$，则不难得到一个多项式$p'(x)=\frac{p(x)}{\prod_{i=0}^{k-1}(x-a_i)}$，且有$deg(p)=deg(p')+k$

Putting It Together

把之前提到的所有东西缝合一下

首先是多项式约束，根据$A_i^2-A_i=0$，我们可以得

$$ f^2(x)-f(x)=0 $$

然后我们定义了当$x=1,g,g^2,...,g^{511}$时为$f(x)$的根，此时表明执行轨迹的结果为0或1，因此我们可以得到

$$ p(x)=\frac{f^2(x)-f(x)}{\prod_{i=0}^{511}(x-g^i)} $$

根据之前提到的，存在一个多项式，其度至多为$2\cdot deg(f)-512$，当且仅当对于所有的$x\notin\{1,g,g^2,...,g^{511}\}$时其执行轨迹为512个单比特

因为Prover需要将执行轨迹扩展到一个更大的域，所以在扩展后的域中检查这些多项式是否满足约束更好，如果Prover可以让Verifier认为该多项式的度数是低的，此时Verifier只需要检查那些不在执行轨迹上的值即可，因为若CI Statement为真时，Verifier请求的值才会通过验证

Fibonacci

这么说还是有些乱，再举一个直观的例子：斐波那契数列

假设我们需要在域$Z_{96769}$上计算斐波那契数列的前512项，根据域上加法和乘法需要模96769，我们有如下定义

• $a_0=1$
• $a_1=1$
• $a_{n+2}=(a_{n+1}+a_n) \ mod \ 96769$

对应的CI Statement如下

• CI Statement：$a_{511}=62215$

根据上面的定义，不难计算出执行轨迹

根据斐波那契数列的特性，我们可以得到下列四个约束

1. $A_0-1=0$：确保$A_0=1$
2. $A_1-1=0$：确保$A_1=1$
3. $\forall 0\leq i\leq 509:A_{i+2}-A_{i+1}-A_i=0$：确保执行轨迹满足斐波那契递归关系$f(g^{i+2})-f(g^{i+1})-f(g^{i})=0$
4. $A_{511}-62215=0$：确保满足CI Statement：$a_{511}=62215$

Translate to Polynomials

和之前一样，我们对子群中的生成元$g$进行拉格朗日插值法，得到

$$ \forall 0\leq i\leq 511:f(g^i)=A_i $$

然后得到对应的多项式约束

1. $f(1)-1=0$：确保第一个元素为1
2. $f(g)-1=0$：确保第二个元素为1
3. $\forall 0\leq i\leq 509:f(g^{i+2})-f(g^{i+1})-f(g^{i})=0$：确保执行轨迹满足斐波那契递归关系
4. $f(g^{511})-62215=0$：确保满足CI Statement：$a_{511}=62215$

由于多项式的组合仍然是多项式，因此用约束$f(g^i)$替换$A_i$仍然代表对应的约束

观察第1、2、4个约束，其只是针对单个$f$的约束，因此又称为边界约束，对于第三个约束，其由斐波那契数列的关系定义，实际上第三个约束可以重新描述如下

$$ \forall x\in \{1,g,g^2,...,g^{509}\}:f(g^2x)-f(gx)-f(x)=0 $$

这样表述的目的实际上就是利用生成元来对执行轨迹的行进行索引，若$x$表示执行轨迹的某一行，则$gx$表示下一行，$g^2x$表示再下一行，$g^{-1}x$则表示前一行，根据约束，执行轨迹中的每一行（除了最后两行），都需要满足这个关系，这意味着$1,g,g^2,...,g^{509}$都是斐波那契递归关系构成的多项式的根（且这个多项式的度最高为510）

根据之前的知识点，我们可以构建多项式$p'$如下

$$ p'(x)=\frac{f(g^2x)-f(gx)-f(x)}{\prod_{i=0}^{509}(x-g^i)} $$

若执行轨迹中的全部（512个）数字都符合斐波那契递归关系，则得到的多项式$p'$的度应该为2（因为多项式$f$由512个斐波那契数通过拉格朗日插值法得到，因此$deg(f)=512$，故有$deg(p')=512-510=2$），至此我们将检查执行轨迹是否满足多项式约束转换为了检查多项式$p'$是否为低度多项式

Succinctness

接下来还有一项工作没有完成，就是STARK中的S，简洁性，简洁性由下列两部分组成

1. 只使用少量的查询
2. 对于每次查询仅完成很少的计算量

在之前的内容中，我们通过纠错码的方式实现了第一个要求，利用纠错码可以使得Verifier只需要检查若干个地方就可以判断是否接受CI Statement，对于第二个要求，通过检查多项式是否为低度的来完成，因此，Verifier的工作主要有两项

1. 在一个随机的位置查询合成多项式
2. 基于这些查询，检查多项式是否是低度的

关于什么是低度测试，将在后续的文章中介绍

先来看Verifier的第一项工作：在一个随机位置查询合成多项式，在这个过程中Prover很有可能是恶意的，例如Verifier请求在点$x$处评估合成多项式，Prover完全有能力构造一个低度多项式进行评估，使得这个低度多项式可以通过低度测试，但不是合成多项式

先回到斐波那契数列的例子，假设Verifier请求检查第$w$行的斐波那契递归关系$f(w),f(gw),f(g^2w)$，此时Verifier可以在点$w$处得到合成多项式的值

$$ p'(w)=\frac{f(g^2w)-f(gw)-f(w)}{\prod_{i=0}^{509}(w-g^i)} $$

不难看出，对于确定的$w$而言，分母$\prod_{i=0}^{509}(w-g^i)$完全独立于执行轨迹，因此Verifier可以在与Prover交互之前就把分母计算好，但是如果说执行轨迹很大（比如有$10^6$个），此时的计算量对于Verifier来说仍然不小，注意到

$$ x^{|G|}-1=\prod_{g\in G}(x-g) $$

实际上这个等式是群的性质之一（具体可以看数论相关的知识），而此时等号两侧都是度为$|G|$的多项式，而这两个多项式的根都是群$G$中的元素，如果按照朴素的方法计算等式右侧的多项式，我们需要的计算次数和群的大小是线性相关的，但是计算等号左侧的多项式，我们可以利用快速幂算法来加速，此时需要的计算次数是群的大小的对数（$\log |G|$），从而我们可以将斐波那契递归关系的约束改写为如下

$$ \frac{f(g^2w)-f(gw)-f(w)}{\prod_{i=0}^{509}(w-g^i)}=\frac{(w-g^{510})\cdot(w-g^{511})\cdot(f(g^2w)-f(gw)-f(w))}{w^{512}-1} $$

因为原始的约束中分母的多项式的$w$的幂次最高为509，且$|G|=512$，所以分子需要乘以$(w-g^{510})\cdot(w-g^{511})$来将分母中$w$的幂凑齐到512

利用这个群的特性，我们将执行轨迹视为域上某一子群上的多项式的求值，且求值的多项式约束是关于该子群的，从而使得Verifier的验证时间降低到了对数阶，利用这一特性，我们可以构建更为复杂的执行轨迹，但是约束必须与域上的某个子群一致