wordpress的latex真是难用，下面的公式看起来不容易的话，可以跳到知乎看这个：https://zhuanlan.zhihu.com/p/2003525863535313231
零知识证明（Zero-Knowledge Proof，简称ZKP）是一种神奇的密码学方法，允许一个人（证明者）向另一个人（验证者）证明自己知道某个秘密、或者某个陈述是真的，却完全不透露这个秘密本身的任何信息。它常见的作用有两个：
隐私计算：例如使用zk做登录，只需要输入证明通过验证就可以进行登录，而不用透露密码。
计算压缩：例如计算一个复杂多项式的值，提供证明和结果，验证者通过就可以确认这个值是正确的，而不用重新计算。
本文将主要从计算压缩这个方向，通过zk-stark协议向读者说明零知识证明的原理。
### Trace (轨迹) 和约束
我们以 Fibonacci 函数为例： f(x)=f(x-1)+f(x-2) 。假设我们现在要计算 f(10) 的值，并令初始值 f(0)=1，f(1)=1 ，我们可以得到如下的表格：
| x | f(x) |
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
| 6 | 13 |
| 7 | 21 |
| 8 | 34 |
| 9 | 55 |
| 10 | 89 |
我们称这个表格中的数据为 Trace，也称为轨迹（主要指 f(x) 这一列），另外根据 Fibonacci 函数的要求，我们需要得到的 Trace 满足：
1. f(0)=1
2. f(1)=1
3. f(x)=f(x-1)+f(x-2)
也就是说 Trace 中的数据，必须满足以上三个条件，这些条件我们称之为约束（Constraints）。
据此引入一个问题：假如有一个证明者要向验证者证明自己知道在 Fibonacci 函数中 f(100)=573147844013817084101 ，但又不用验证者从头重新计算一遍得到 f(100) ，我们应该如何做？
#### 简单协议
这里给出一个最简单的协议：既然证明者已经知道了 f(100) 的确切值，那么说明证明者已经计算了Fibonacci 函数中 [f(0) ,f(100)] 的所有值。也就是说证明者已经有一个类似前文提到的 Trace (轨迹)表格，不过是从 f(0) 计算到 f(100) 。
那么验证者可以多次随机询问证明者 f(0) 到 f(100) 中对应的某个 f(x) 的值，同时要证明者提供 f(x-1) 以及 f(x-2) 的值。得到证明者提供的值之后，验证者验证其是否满足 Fibonacci Trace 对应的约束，来判断证明者是否撒谎。
例如验证者询问 f(10) 的值，那么证明者就需要提供 f(10)，f(9)，f(8) 的值，验证者计算 f(10) 是否等于 f(9)+f(8) 。或者询问 f(0) 或者 f(1) 的值看是否等于 1。
通过多次随机的询问，如果证明者每次都可以提供正确的 Trace 值，那么就可以判断证明者没有撒谎， f(100) 的值是可信的。
#### 简单协议的漏洞
很明显这个协议是有漏洞的，例如当验证者询问 f(10) 的值，证明者随机捏造 f(10)，f(9)，f(8) ，只要给出的值符合 f(10)=f(9)+f(8) 就行，因为验证者并不知道 Trace 的具体值是多少，只知道约束是怎样的。
虽然这个简单协议是不完备的，但是依然揭示了zk-stark协议的核心：**通过少量的查询trace值是否满足约束，判断证明者提供的证明+结果是否可信。**
接下来我们就顺着上面给出的简单协议一点一点来完善它。
这个简单的协议面列的第一个问题就是上面提到的，当验证者询问 f(x) 的值，证明者随机捏造 f(x)，f(x-1)，f(x-2) ，只要给出的值符合 f(x)=f(x-1)+f(x-2) 就行，因为验证者并不知道 trace 的具体值是多少，只知道约束。例如本来正确的值是 f(10)=89,f(9)=55,f(8)=34 ，符合 f(x)=f(x-1)+f(x-2) 。但证明者可以提供一个 f(10)=88,f(9)=55,f(8)=33 ，也符合 f(x)=f(x-1)+f(x-2) ，但显然并不正确。
#### 承诺（Commit）
对于以上问题很粗暴的一个简单的解决方案就是：验证者从 f(0) 开发询问，一直问到 f(100) ，如果所有数据都满足：
1. f(0)=1
2. f(1)=1
3. f(x)=f(x-1)+f(x-2)
那么就可以确定证明者提供的f(100)是正确的，但是这样做就等于验证者在验证时也做了全量的计算，不符合我们的初衷：验证者只需要少量的抽查，即可以确定证明者没有撒谎。
造成这个问题其中的一个原因是：证明者可以根据验证者的提问随时修改trace的值提供给验证者，以满足约束，从而欺骗验证者。我们需要证明者有一个 Trace 列表之后就不能再修改了，之后验证者的提问只能从这个 Trace 列表中取。
zk-stark协议中称之为“承诺“（commit），采用默克尔树来实现。证明者将trace中的值作为默克尔树的叶子，计算出默克尔 root 哈希，并提交给验证者。验证者有了这个 merkle root，其实就等于拥有了一个不能修改的 Trace 列表。每次验证者询问的时候，证明者不仅要提供对应的 f(x) 的值。还需要提供该值对应的 merkle path 是否可以正确归并到 merkle root。
好了，我们通过默克尔树承诺的方式，保证证明者不能在承诺之后还能随意修改 Trace 值。紧接着又面临一个新的问题：证明者可以提供一部分正确，一部分错误的 Trace，反正验证者只是抽查部分的点值是否正确，只要抽不到证明者造假的那个值不就行了。
要是有方法可以把trace中的这个错误放大就好了！这里就要引入多项式了。
### 多项式
多项式中次数最高项的次数被称为多项式阶。例如: f(x)=2x^4+3x^3+7 的阶就是4。多项式有两种表示方式，第一种是系数表达,例如: f(x)=2x^4+3x^3+7 的系数表达就是[2,3,0,0,7]，没有的次项记为0.还有一种就是点值表达法 [(x_0, f(x_0)), (x_1, f(x_1)) ……] 来表示一个多项式，点值的表示可以通过[插值法](https://zhuanlan.zhihu.com/p/64855561)转换为系数表达。
不难发现其实Fibonacci Trace序列就是一个多项式的点值表达，通过使用插值法可以得到一个多项式，记为 Trace(x)。
这里有两个重要的性质：
1. 插值多项式的唯一性：给定在有限域上n个不同点的函数值，有且只有一个次数不超过n−1的多项式完全通过这些点，这就是拉格朗日插值定理。
2. 多项式在有限域上的点差异下界（最小距离）：任意两个阶数不超过 d 的多项式，在有限域上最多能有d个点取值相同。换句话说，若两多项式不同，则它们在域中至少有 N−d 个点的取值不同，其中N是多项式定义域的大小。
**简单点理解，如果点值不同，插值出的多项式将不相同。而多项式不同，定义域（** x **的取值范围）越大，不同的点值就越多。**
#### LDE（Low-Degree Extension）
前面提到证明者可能会通过修改一两个 Trace 值来作恶，如果 Trace 值被修改，那么通过 Trace 插值出来的多项式将会不同。将未修改的 Trace 插值出的多项式我们记为 Trace_{true}(x) ，修改后的记为 Trace_{false}(x) 。
Trace_{true}(x) 和 Trace_{false}(x) 在 x \in [0, 100] 对应性质2中 N
就是100（定义域大小）， d 就是99(多项式的阶)，如果证明者只修改了一个值那么，也就是两个多项式在 x \in [0, 100] 定义域上对应的值只有一个不同。
明显在这样的情况下，验证者随机取到的值大概率是正确的值，很小的概率抽到错误的值。
如何解决这个问题呢？换个思路，既然 Trace_{true}(x) 和 Trace_{false}(x) 最多有 N-d 个值相同，那么我们就可以扩大 N 的值（即定义域的大小），这样就可以增加不同点的数量。
例如我们可以把 N 从原来的100扩大16倍到1600，那么在新的定义域下最少有1600-99个点不同。扩大定义域之后，验证者随机抽查抽到错误点的概率就变大了到 1-\frac{1}{1600-99} = 93.34\% 。如果验证者进行多次抽查，那么证明者欺骗成功的概率接近于0。
这种通过扩大定义域放大错误的方式，在zk-stark中称之为低度扩展LDE（_Low Degree Extension_）。在zk-stark协议中LDE并不仅有这么一个作用，还有为之后低度测试做准备，这个后文会讲述。
#### 改进后的协议
通过以上的查漏补缺，我们得出一个改进版协议：
**证明者首先通过原始 Trace 插值计算出多项式** Trace(x) ** ，并进行LDE之后，将其承诺 commit（也就是计算merkle树root） 提交给验证者。验证者在LDE中随机取值询问证明者，证明者提供对应的值与 merkle path，可以多询问几次，如果证明者提供的值满足约束，那么就可以大概率信任证明者。**
### 说明为什么 LDE 抽查还不圆满
你以为这样就结束了？并没有。证明者还有一招有可能会骗过验证者，根据插值法的定理，对于 d+1 个互不相同的节点 (=0,…,d) ，存在唯一的一个次数不超过 d 的多项式 () ，满足 (_)=_ 。
这里有一个关键的点是多项式的次数不超过 d 。但是证明者可能会构建一个大于 d 的高阶多项式来作恶。
举一个简单的例子说明下：
假设当前插值出来的多项式是： f(x) = x+5 阶为1，取 x\in[1,2,3] 则有点值对 [(1,6), (2 ,7), (3, 8)] 。我们扩域4倍取 x\in[4,5,6,7,8,9,10,11,12,13,14,15] ，则有点值对 [(4,9),(5,10),(6,11) ……(15,20)] 。
作恶者构建一个新的阶数更大的高阶多项式： f(x)=x+5+(x-4)(x-5)(x-6)…(x-15) 。在 x=[4,5,6,7,8,9,10,11,12,13,14,15] ，其对应的点值对也是 [(4,9),(5,10),(6,11) ……(15,20)] ，但多项式明显不同。
所以我们需要一个方法，来限制多项式的阶数。**这种校验多项式次数不能超过某一个限定值的方法，叫做：低度测试。**低度测试如何实现我们后面再说，这里先作为一个黑盒子来使用它。
#### 约束多项式
除此之外你可能已经忘记，我们的约束其实是构建在 Trace 之上的，同时为了避免复杂，我避免提及约束的定义域。我们再次回到Fibonacci的那个例子，其有三个约束：
1. f(0)=1
2. f(1)=1
3. f(x)=f(x-1)+f(x-2)
我们可以将这里的 f(x) 视为 Trace(x) ，但是你有没有发现，对于 f(0)=1 来说只有在 x=0 的时候才是有效的，对于 f(1)=1 ，只有在 x=1 的时候才生效，而对于 f(x)=f(x-1)+f(x+2) 是在 x \in [2, 100] 范围生效的。
那又该如何限制约束的作用范围呢？
约束多项式是基于 Trace 多项式生成的，但是我们又不知道具体的 Trace 多项式，但我们也可以通过低度测试保证约束多项式只有在指定范围是生效的。
其实约束也可以看做一个多项式，例如：对于 f(x)=f(x-1)+f(x-2) 我们可以得到一个约束多项式 C_0(x) = f(x)-f(x-1)+f(x-2) 。那么对于 C_0(x) 来说，当 x \in [2, 100] 时， C_0(x) = 0 。换句话说，多项式 C_0(x) 可以整除多项式 (x-2)(x-3)(x-4)(x-5)……(x-100) ，如果整除不了就会有余数，那就说明这个约束多项式是不合法的。基于此来限制约束的作用范围。
据此得到了一个新的多项式 Q_0(x) = \frac {C(x)} {(x-2)(x-3)(x-4)(x-5)……(x-100)} ，这样的多项式在zk-stark协议中，也被称为商多项式，而 (x-2)(x-3)(x-4)(x-5)……(x-100) 称之为零化多项式（vanish 多项式）。
对于 f(0)=1 ，按照上面的方法就可以写成 Q_1(x)=\frac{f(x)-f(0)}{x-f(0)} = \frac{f(x)-1}{x-1} 。
#### 商多项式的阶数要求
对于商多项式来说，也有阶数的要求，假设这里 f(x) 的阶 d=100 ，那么 C_0(x) 的阶也是100， Q_0(x) 的阶就是 2（因为除法）。同时又因为验证者并不知晓 Trace 的具体值，所以我们也需要对得到的商多项式也进行低度测试。
商多项式的意义在于，它将约束多项式的零点区间“剥离”出去，剩下的部分反映了约束多项式除去零点限制后的真实结构。验证者只需要对商多项式进行低度测试，来判断其是否确实是低度多项式。
为了方便计算，我们将所有的商多项式 Q(x) 通过随机线性组合结合为一个多项式，记为：
CP(x)={\alpha}_0Q_0(x)+{\alpha}_1Q_1(x)+{\alpha}_2Q_2(x).....
这下就不用为每一个 Q(x) 单独做低度测试了，只需要对 CP(x) 做低度测试就可以了。
#### 进化版协议
验证者随机抽查 Trace 中的值来查看是否满足约束判断证明者是否撒谎，但是证明者可能随机修改 Trace的值来作恶，采用 Commit 的方式可以避免证明者在提交证明之后还能修改 Trace。除此之外证明者还可以通过：
1. 修改少量 Trace 值躲避验证者的抽查
2. 通过构建一个高阶多项式来构建一个看似合法的多项式
对此我们则采用LDE低度扩展+低度测试来解决以上证明者可能作恶采取的手段，这样我们就构建起一个基础的、完备的zk-stark协议。
### DEEP 方法--使协议更加安全
有个方法可以让上面的协议更加的健壮与安全。
既然进行 LDE 扩域之后抽查已经可以大概率发现错误了，那么如果我在一个比扩域更大的域中随机取一个数那岂不是更更更加安全了。
这种在更大的域中随机取值以更加提升安全性的方式称为DEEP。
然而，将随机点扩展到更大的域也带来了新的挑战。之前在扩展域中进行承诺时，证明者会先计算多项式在扩展域所有点的取值，然后将这些值构建成 Merkle 树，提交根节点给验证者，实现高效且可信的承诺。
但如果域的规模进一步变大，直接枚举所有点并计算对应值显然不现实，这样会导致计算和存储成本过高，无法操作。
回想之前计算约束多项式时，我们采用了多项式除以“因子”（即零多项式）的方式来验证是否整除，从而判断约束是否成立。
DEEP 方法借鉴了这一思想，针对更大的域随机选取一个点 _ζ_，并构造多项式形式的组合多项式。例如，以 Fibonacci 轨迹为例：
假设从一个更大的域中随机选取 ζ，则定义多项式：
DEEP(x)=α⋅\frac{trace(x)−trace(ζ)}{x−ζ}+β\frac{CP(x)−CP(ζ)}{x−ζ}
其中：
+ Trace(x) 是轨迹多项式；
+ CP(x) 是约束组合多项式；
+ α,β 是随机系数，用于线性组合，增强安全性；
+ 分子部分通过减去在 _ζ_ 点的取值，分母是 (x−ζ) ，相当于检查 x=ζ 处的零点性质。
这种构造方式有效地将多项式的验证转化为对更大域中单点的验证，利用了多项式除法的性质保证了对 _ζ_ 点的强约束。
验证者执行以下步骤：
1. **验证 ζ点的取值** 验证者检查轨迹多项式在点 ζ_ _处的取值是否满足约束条件。借助 DEEP 组合多项式中除以 (x−ζ) 的结构，确保证明者无法伪造 Trace(ζ) 和 CP(ζ) 的值。
2. **对组合多项式 Composite(x)Composite(**_**x**_**) 进行低度测试** 验证者通过低度测试（如 FRI/DEEP-FRI）验证 DEEP(x) 是否是低度多项式，从而保证整体多项式的合法性和一致性。
DEEP 方法通过在更大域中随机抽点，结合多项式除法的零点特性，将多项式验证问题转化为对单点的强约束和低度测试，极大提升协议的安全性。
接下来就剩下最后一节了，低度测试是如何实现的？
### 低度测试（Low Degree Testing）
前文提到低度测试的目标是验证一个多项式的次数确实不超过某个预定的阈值。
假设我们有一个定义在大小为 N
的有限域上的多项式
\text{DEEP}(x) = \alpha_0 x^{N-1} + \alpha_1 x^{N-2} + \alpha_2 x^{N-3} + \cdots + \alpha_{N-1} x^0
我们的验证目标是确认其最高次数不超过 d ，通常 d \ll N 。
有一个简单的方法可以做低度测试，根据多项式的插值定律，对于 n 个点，我们插值出来的多项式，同 LDE之后点值插值出来的多项式应该是一致的。那么我们就可以每次从 LDE的点值中抽查 n 个点，插值出多项式，然后看每次插值出来的多项式系数是否相同，但是这样就有一个问题，那就是对验证者来说工作量太大，而 zk-stark 协议中采用的低度测试方法 FRI（<font style="color:rgb(71, 71, 71);">Fast Reed-Solomen Interactive Oracle Proofs of Proximity </font>）可以解决该问题。**采用了 DEEP 方法的 FRI 叫做 DEEP-FRI。（其实就是对 DEEP 多项式做 FRI）**
#### 多项式的奇偶分解
FRI 低度测试的核心技巧之一是对多项式按奇偶项进行分解：
\text{DEEP}{\text{even}}(x) = \alpha_0 x^{N/2 - 1} + \alpha_2 x^{N/2 - 2} + \alpha_4 x^{N/2 - 3} + \cdots
\text{DEEP}{\text{odd}}(x) = \alpha_1 x^{N/2 - 1} + \alpha_3 x^{N/2 - 2} + \alpha_5 x^{N/2 - 3} + \cdots
这样，原多项式可以写成：
\text{DEEP}(x) = \text{DEEP}{\text{even}}(x^2) + x \cdot \text{DEEP}{\text{odd}}(x^2)
这里的关键点是：
+ {DEEP}{\text{even}}(x) _和 _ \text{DEEP}{\text{odd}}(x) 都是次数大约为原来一半的多项式。
+ 通过替换变量 y = x^2 ，我们把多项式的次数“折半”，从而实现递归检测。
将变量替换为 y = x^2 后，我们得到：
\text{DEEP}(x) = \text{DEEP}{\text{even}}(y) + x \cdot \text{DEEP}{\text{odd}}(y)
此时，定义域 N 也因为变量的平方映射而减半。理由如下：
+ 对于任意 x ，都有 x^2 = (-x)^2 。这意味着两个不同的 x 值映射到了同一个 y 。
+ 因此，定义域大小从 N
缩减到大约 N/2 。
我们可以对新的多项式 \text{DEEP}{\text{even}}(y) 和 \text{DEEP}{\text{odd}}(y) 继续重复同样的折半操作。
通过不断折半多项式的次数和定义域，最终递归到多项式阶数为 0（即常数项）。此时验证者可以直接暴力检查多项式是否满足预期。
#### 承诺与查询阶段
验证者和证明者之间的交互过程如下：
1. **承诺阶段**
- 证明者计算每一层折半后的多项式在对应定义域上的所有点值。
- 对每一层的点值集合构建 Merkle 树，并提交 Merkle 根给验证者，作为该层多项式的“承诺”（commit）。
2. **抽样验证**
- 验证者随机选择一个点 \gamma 和其对应负点 -\gamma 。
- 证明者需要提供该点及其路径对应的多项式值和 Merkle 证明（Merkle path），证明这些值属于之前提交的 Merkle 树叶子，防止造假。
- 证明者还需给出下一层多项式在点 \gamma 和 (-\gamma)^2 = \gamma^2 相同点上的值及 Merkle 证明。
3. **一致性检查** 验证者检查以下几点：
- \gamma 和 -\gamma 对应的多项式值与上一层的 Merkle 根是否匹配。
- 利用折半分解公式验证： \text{DEEP}(\gamma) \stackrel{?}{=} \text{DEEP}{\text{even}}(\gamma^2) + \gamma \cdot \text{DEEP}{\text{odd}}(\gamma^2)
- 下一层多项式在 \gamma^2 点的 Merkle 证明是否正确。
4. **递归进行**
- 验证者重复对下层多项式执行相同的随机抽样和验证。
- 一直递归到多项式阶数为 0，即常数多项式，做最终验证。
为了增强安全性，验证者会在每一层抽查多个随机点，避免证明者通过偶然的“幸运”逃避检测。
随着递归层数的增加，每一次折半都缩减了多项式的次数和定义域大小，验证者只需少量的随机查询即可高概率地发现伪造。
#### 总结 FRI 低度测试流程
| 步骤 | 说明 |
| --- | --- |
| 多项式奇偶分解 | 将多项式拆成奇数项、偶数项，次数大约减半 |
| 变量替换折半定义域 | 通过 y = x^2 代换，定义域与多项式次数缩减 |
| Merkle树承诺 | 证明者对每层多项式的点值构建 Merkle 树，提交根节点，防止造假 |
| 随机抽样验证 | 验证者随机抽点，证明者提供对应值和 Merkle 路径，验证一致性 |
| 递归进行 | 持续折半和验证直到多项式为常数，最终确认低度 |
| 多次随机抽查 | 多点验证提高安全性，降低证明者造假的概率 |
这种低度测试策略既保证了协议的安全性，也极大地提高了验证效率，使得零知识证明在大规模计算上变得可行。
### 总结
1. 证明者首先获得 Trace 然后插值获得 Trace 多项式 Trace(x)
2. 接着计算约束多项式 C(x) 以及对应的商多项式 Q(x) ，并将所有商多项式组合起来获得 CP(x) 。
3. 采用 DEEP 方法，将 Trace(x) 与 CP(x) 结合起来，获得 DEEP(x)=α⋅\frac{trace(x)−trace(ζ)}{x−ζ}+β\frac{CP(x)−CP(ζ)}{x−ζ}
4. 最后验证者抽查 ζ 取值是否满足约束多项式+对 DEEP(x) 低度测试。
### 最后
敏锐的你可能已经发现，这里好像不是零知识的哦？如果验证者一直询问的话，那岂不是可以根据问到的所有值，反推出原始的T(x)，从而计算出基础域的Trace了么。你的观察是正确的，这样确实会暴露原始Trace中的值，从而非零知识。深入zk-stark协议的话，其会采用Trace偏移的方式来进行零知识化处理（即想法将原始Trace值进行偏移，从而不暴露原值）。但这个的讲述会比较绕，且并不是本文要讨论的重点，本文重点是想通过zk-stark协议说明整个零知识证明运行的原理，以使读者能够get到协议运行的关键。如果还有比较迷惑的地方，可以在评论区抛出来，大家一起讨论。
以上基本就是zk-stark协议的整体脉络，后面的文章会再理论性的完整呈现下整个zk-stark协议，但那个就会比较枯燥了，虽然现在就已经比较枯燥了！
文章评论