# 深入理解zk-STARK证明系统

By [BCG Labs](https://paragraph.com/@bcg-labs) · 2023-02-13

---

转自：

[https://trapdoor-tech.github.io/zkstark-book/AIR/air.html](https://trapdoor-tech.github.io/zkstark-book/AIR/air.html)

算术化
---

许多零知识证明系统都使用算术化的方法，将计算类问题简化成涉及有限域`F`上的多项式的代数问题。zk-STARK对计算完整性（ Computational Integrity， CI）声明，“输出结果`α`是程序`C`根据输入`x`经过`T`步执行所得”，进行证明的第一步是算术化。

zk-STARK算术化的方法包括2个重要方法，首先，构建程序`C`的代数中间表达(Algebraic Intermediate Representation, AIR)，用`s`个多项式描述当前执行状态与下一步状态的转化约束；其次，为降低证明者的时间复杂度和空间复杂度，将上述多项式进行链接合并形成1个多项式，该方法称为ALI（Algebraic Linking Interactive Oracle Proof）。 详细说明如下。

### AIR

对计算完整性进一步深入理解下，实际上需要通过AIR将这一约束表达出来，即从输入`x`到输出`α`的程序执行过程中的中间计算状态转换，中间计算状态则是一堆寄存器数值。因此，给出AIR的定义，是一个低度多项式的集合

_P_\={_P_1​(_X_,_Y_),...,_Ps_​(_X_,_Y_)}

1.  低度多项式的系数在域 _F_内
    
2.  _X_\=(_X_1​,...,_Xw_​) 代表当前计算状态
    
3.  _Y_\=(_X_1​,...,_Xw_​) 代表下一步计算状态
    
4.  _w_ 是证明系统所中某一个计算状态的变量数量
    
5.  _Pi_​ 代表转换关系的多项式
    
6.  有一对解(_x_,_y_​)使得转换关系成立，当且仅当 (_x_,_y_​)是_P_的共同的解，即 _P_1​(_x_,_y_​)=...=_Ps_​(_x_,_y_​)=0
    
7.  AIR的多项式的度是 所有_Pi_​中的最大值
    
8.  s 是所有约束的数量
    

通过上述定义，可以看出，AIR将程序`C`执行过程中寄存器数值前后变化关系转化成了约束多项式，以便验证者能信任输入`x`到输出`y`的完整过程，而不是随便得出的结果或者是伪造的输出结果。

### ALI协议

由于多项式的插值计算及验证计算需要耗费大量的计算资源，因此，ALI协议将`s`个多项式约束化简为单一约束，例如，可以使用随机线性组合。

实际上，采用ALI协议后，具有更好的可靠性(soundness)。如果对证明过程感兴趣，可以参考 Eli Ben Sasson 的文章\*\*[Scalable, transparent, and post-quantum secure computational integrity附录D](https://eprint.iacr.org/2018/046.pdf)\*\*

执行轨迹
----

执行轨迹是由执行某个计算时，一组机器状态序列构成。说得直白点，就是为了执行某个程序`C`，申请了`W`个寄存器，执行了`N`个步骤，那么执行轨迹可以用一张大小为_N_×_W_表来描述。

以斐波那契数列计算为例，可参考\*\*[ZKHack Mini2 Can you turn up the heat?](https://www.zkhack.dev/puzzleM2.html)\*\*

    fn fib(start: (Felt, Felt), n: usize) -> Felt {
        let mut t0 = start.0;
        let mut t1 = start.1;
    
        for _ in 0..(n - 1) {
            t1 = t0 + t1;
            core::mem::swap(&mut t0, &mut t1);
        }
        t1
    }
    

可以看到这里使用了2个寄存器，`s0`、`s1`分别存放每一个中间状态下的数据。模拟`n = 10`的时候，生成的执行轨迹是一个数组，包含了5对中间状态数据`(state[0],state[1])`。这里的执行轨迹是由prover定义并生成的，源码如下：

    pub fn build_trace(start: (Felt, Felt), n: usize) -> TraceTable<Felt> {
            
            let mut trace = TraceTable::new(2, n / 2);
            trace.fill(
                |state| {
                    state[0] = start.0;
                    state[1] = start.1;
                },
                |_, state| {
                    state[0] += state[1];
                    state[1] += state[0];
                },
            );
    
            trace
        }
    

执行轨迹中的数据如下图所示。

![](https://storage.googleapis.com/papyrus_images/16b807c5905b8a21e053c050d8b82d20ede4b816bd458d19f82e8102347c26d6.png)

这样定义出来的执行轨迹只有2列，状态转换的具体约束条件如下：

            result[0] = next_state[0] - (current_state[0] + current_state[1]);
        result[1] = next_state[1] - (current_state[1] + next_state[0]);
    

也就是说，每一次状态转换必须满足这2个约束：

1.  `s_{0, i+1} = s_{0, i} + s_{1, i}`
    
2.  `s_{1, i+1} = s_{1, i} + s_{0, i+1}`
    

相应的约束多项式的度最大为1。因此，创建AIR时，定义状态转换的约束多项式的度为1。

            let degrees = vec![
                TransitionConstraintDegree::new(1),
                TransitionConstraintDegree::new(1),
            ];
    

此外，AIR中还需要对输入、输出进行约束，参考如下：

            vec![
                Assertion::single(0, 0, self.start.0),       // input contraint
                Assertion::single(1, 0, self.start.1),       // input contraint
                Assertion::single(0, last_step, self.end),   // output contraint
            ]
    

至此，我们就构建了执行轨迹，并根据执行轨迹构建了对应的约束。

实际上，构建一个合理执行轨迹，并据此设计无懈可击的约束系统是学习并使用ZK-Stark非常重要的一步。如果感兴趣，可以参考[\*\*ZKHack Mini1: There’s something in the AIR \*\*](https://www.zkhack.dev/puzzleM1.html) ，帮助更深入地理解AIR。

STARK中的多项式承诺
------------

### 两种类型的多项式

从算术化的约束系统中，我们会得到两种类型的witness，第一是整个待证明程序的执行轨迹，也叫做execution trace，第二是在执行过程中需要满足的约束条件，称为 constraint。

执行轨迹可以看成是一组寄存器的状态转换过程。这里我们仍以斐波那契数列的计算为例，假设我们要求出 `fib(10)`，且用两个寄存器 `s0`, `s1` 来保存计算的中间状态，那么在程序正确执行5步后，`s0[5]` 就是我们需要的计算结果。

![](https://storage.googleapis.com/papyrus_images/16b807c5905b8a21e053c050d8b82d20ede4b816bd458d19f82e8102347c26d6.png)

有了程序的执行轨迹，我们还需要额外的约束来保证执行轨迹确实是程序按照我们给出的计算方式来生成的。约束分为两部分：

1.  在边界处，寄存器的状态必须和指定的寄存器状态一致。例如 `s0`, `s1` 的初始状态要满足 `s0[0] = 0` 且 `s1[0] = 1`。另外，我们得到的计算结果必须是程序执行到第5步后 `s0` 寄存器的状态，即 `result = s0[5]`。
    
2.  寄存器每一次的状态转换必须满足如下计算规则：
    
    1.  `s0[i] + s1[i] = s0[i+1]`
        
    2.  `s1[i] + s0[i+1] = s1[i+1]`
        

有了这些约束，我们就能够信任程序的执行结果，即 `fib(10) = result = s0[5]` 了。接下来我们需要对执行轨迹和约束条件做多项式承诺。

### 承诺一个多项式

在讲具体的实现之前，我们先来了解 STARK 中是如何对一个多项式进行承诺的。我们知道一个多项式承诺方案（polynomial commitment scheme）需要满足如下使用场景：

1.  设置：能够生成特定的代数结构 G，以及公私钥对 ⟨_PK_,_SK_⟩ ，用于承诺一个度数小于 _t_ 的多项式
    
2.  承诺：输出多项式 _ϕ_(_x_) 的承诺 C
    
3.  打开：对于验证者给定的 _i_，证明者给出多项式在该点处的值 _ϕ_(_i_)，以及关于该求值的一个证明。验证者能够利用之前的承诺 C 验证其求值是正确的
    

在常见的 _KZG_ 多项式承诺方案中，证明者首先使用椭圆曲线点乘的方式，对多项式进行承诺，随后在打开时构造一个新的商多项式，使得验证者可以通过椭圆曲线配对，验证该商多项式正是原始的 _ϕ_(_x_) 在挑战点处构造出的多项式。具体的步骤可以参考 _KZG_ 的论文，这里不再赘述。

STARK 使用默克尔树进行多项式承诺，实现方式如下：

1.  设置：STARK不需要额外的可信设置，但需要事先确定用于构造默克尔树的哈希函数
    
2.  承诺：首先求出多项式 _ϕ_(_x_) 在其求值域上所有单位根处的值，_ϕ_(_ω_0),_ϕ_(_ω_1),_ϕ_(_ωi_),...，以这些值为叶子节点，组成一颗默克尔树，最后公开得到的默克尔树树根，即是该多项式的承诺。
    
3.  打开：验证者选定随机挑战点，证明者提供多项式在该点处的值，以及一条默克尔树路径。验证者检查该默克尔树路径合法。
    

### 轨迹多项式的承诺

对于任何一个 STARK 寄存器的执行轨迹，我们可以将它的每一行看作是其对应的轨迹多项式在某个单位根处的取值。因此，对于示例中的 _s_0(_x_),_s_1(_x_)，我们有：

![](https://storage.googleapis.com/papyrus_images/e08f450eb54d17962a55dbfecc42a586b7b43bd54e391dab6c1343b3502116bf.png)

因为默克尔树要求叶子节点个数必须是2的幂次，这里我们需要补上程序继续按约束条件运行的结果：

![](https://storage.googleapis.com/papyrus_images/009144af7580131ed409018b12bebf94d2671864d0870924f6854c7ac9b48fd8.png)

这样就可以为 _s_0(_x_),_s_1(_x_) 分别生成默克尔树承诺了。不过请稍等，为了协议的安全性，我们还需要进行扩展。

### 低度多项式扩展

从程序的执行轨迹中，我们得到了数个长度为 _N_ 的轨迹多项式。实际的使用场景里，出于安全性的考虑，我们需要在一个更大的求值域上承诺该多项式，一般需要将求值域扩大 2_k_ 倍，扩大的倍数称为爆炸倍数（ `blowup factor`），该求值域称为 _LDE_ 域。

我们会在 _DEEP-FRI_ 章节讨论安全性的问题。现在来看如何将长度为 _N_ 的轨迹多项式扩展到 2_kN_ 。我们先利用拉格朗日插值法，求出该轨迹多项式的各项系数 _a_0​,_a_1​,_a_2​,..,_an_−1​ （注意其单位根需要使用 2_kN_ 求值域上的单位根），然后我们在 2_kN_ 的求值域上用系数求出其他单位根处的多项式值。这种利用一个低次多项式生成更大的求值域上单位根处值的方法称为低度多项式扩展。

下图是 `blowup factor = 2` 时， _s_0(_x_) 的低度多项式扩展示例，黄色的节点是多项式在原始的求值域上对应单位根处的值（它们也是在 _LDE_ 域上所有单位根处值的一部分，因为 _ωorigini_​=_ωLDE_2_k_∗_i_​ ），蓝色为 _LDE_ 扩展后新的单位根处的求值：

![](https://storage.googleapis.com/papyrus_images/03d1c4643b475209b3ca3259c6ecbfc3340c95da59c52c6e89ccde3f1fc1c265.png)

### 约束多项式的承诺

程序在执行过程中需要满足的约束条件，同样也可以转换为多项式来表示。例如，我们要约束 _s_0(_ω_5)=55，可以按如下的方式构造约束多项式：

![](https://storage.googleapis.com/papyrus_images/1f18d256cd2ae7485acfdef9f511d4dd70106a7ad414bd045bbcbaf10b69f74b.png)

根据多项式基本定理，_s_0(_x_)−55 可以被 _x_−_ω_5 整除当且仅当 _s_0(_ω_5)=55。也就是说，当约束条件满足的时候， _c_(_x_) 的次数小于 _s_0(_x_)。我们利用这种方法，将所有的约束条件写成多项式的形式：

![](https://storage.googleapis.com/papyrus_images/c6e8f20b569cbf0ee40c22aa5aaaa30341cd5a1e9944196b159b5ad1bef829ff.png)

### 将约束多项式组合起来

如果一个个检查约束多项式的次数，代价会很大，也没有必要。我们可以将所有的约束多项式组合到一起，形成一个**组合多项式（Composition Polynomial）**，对该组合多项式的检查即是对所有约束多项式的检查。

在组合之前，有一点要注意：上述的约束多项式的次数不是相同的。需要先将约束多项式补齐到相同的次数，然后再组合。补齐的方法是将它乘上一个随机的 _D_−_Dj_​ 次多项式，该随机多项式的系数是验证者在证明者承诺完轨迹多项式后随机产生的。

![](https://storage.googleapis.com/papyrus_images/00f170d972991b84c28fcb936387833e5710600f6d1504d27b1edd5f8519a1b2.png)

最后我们得到 组合多项式 _CP_(_x_)，别忘了我们需要在 _LDE_ 域上承诺它，因此也要像之前的轨迹多项式那样，使用低度多项式扩展的方式进行承诺。

### DEEP-FRI

得到轨迹多项式和组合多项式后，其实我们已经可以进行证明了。只要把轨迹多项式和组合多项式再做一次随机的线性组合，然后证明最终的多项式度数小于 _D_ ，就能证明所有的约束条件满足，且程序的执行过程和被承诺的Trace一致。

但是，从安全性角度出发，还需要做一些调整。STARK 使用称为 **Domain Extension for Eliminating Pretenders (DEEP)** 的方法进行检查。我们需要从基域上随机选一个点，然后检查在这个点上，各多项式的值是否满足约束。基域是自变量 _x_ 的取值范围 F ，是一个比 _LDE_ 域大得多的域。

设我们挑选了随机点 _z_∈F ，则 _DEEP_ 多项式可以构造为：

![](https://storage.googleapis.com/papyrus_images/26af15343608214c339c541e0b9a65d6aa0fed548dff055384a35f2950a697c2.png)

在实际应用中，_CP_(_x_) 的度数一般比轨迹多项式要高，取决于约束条件。如果约束条件有两列相乘（即二次的约束），则 _CP_(_x_) 的度数就为 2_D_ 。这种情况下，需要将 _CP_(_x_) 拆分为多个次数小于 _D_ 的多项式。本文中因为约束是一次的，因此 _CP_(_x_) 的次数和轨迹多项式的次数一致。另外，上面构造的 _DEEP_(_x_) 多项式，正常来说其次数应该小于 _D_−2 （因为分子均为次数小于 _D_−1 次的多项式，而分母为 1 次多项式）。但为了后面做 FRI 承诺的时候计算方便，我们仍然通过乘上一个多项式的方式，将其次数升高一次，这样它的次数应该小于 _D_−1 。

关于构造 _DEEP_(_x_) 多项式的必要性，可以参考 Eli Ben Sasson 的文章 [**DEEP-FRI: Sampling Outside the Box Improves Soundness**](https://eprint.iacr.org/2019/336)

构造完 _DEEP_(_x_) 后，如果能够证明 _DEEP_(_x_) 是一个次数小于 _D_−1 的多项式，就可以证明所有的多项式在 _z_ 点处的取值即是所预期的值，进而证明程序的执行结果正确，且所有的约束条件都满足。

### FRI低度多项式测试

怎样证明一个多项式 _f_(_x_) 的次数小于特定的 _D_ 次呢？低度多项式测试提供了一种方法，即：从 _f_(_x_) 上任意挑选 _D_+1 个点值对 (_xi_​,_f_(_xi_​))，使用其中的 _D_ 个点值对构造一个 _D_−1 次多项式 _f_′(_x_) 。若 _f_′(_x_) 和 _f_(_x_) 在第 _D_+1 个点处的求值相等，则有较大的概率 _f_(_x_) 是一个次数小于 _D_ 的多项式。

![](https://storage.googleapis.com/papyrus_images/5d0af3ebf1ae3ced777637b7f440bdc9f19d05b1d024f6272ac3248beb82d952.png)

出于安全性的考虑，可以将这个过程重复 _k_ 次。若进行一次测试，证明者作弊成功的概率为 _p_，那么挑选 _D_+_k_ 个点值对，证明者成功的概率就是 _p^k_ 。

### 使用折叠减少开销

上述低度多项式测试的方法有一个缺点，即构造 _f_′(_x_) 需要 _D_+_k_,_k_≥1 个点值对，在多项式度数非常大的前提下，测试需要的时间和通信量也会变得无法承受。FRI 通过一种称为“折叠”的方法，降低了通信开销。具体做法是：

![](https://storage.googleapis.com/papyrus_images/55c99ca20b3bfbed4afdc36c4caf1f2044a59cdb474ebda4542920deb96294a0.png)

第4步的解释：

![](https://storage.googleapis.com/papyrus_images/bb4d9e540191a146fed67c44861b95af7f9f7023d5f8ee55c884a5c4592d793d.png)

### 验证者的检查

### 检查FRI步骤的正确性

![](https://storage.googleapis.com/papyrus_images/9d894b286d91f636dcca30268ed88f87a01bec512ab7684689b121215880c6ca.png)

### 检查多项式是否匹配

![](https://storage.googleapis.com/papyrus_images/df9255f03dffb289a77f09271f7031bc2b1c328091933635a1b886a7ac318e2a.png)

### 磨损因子

因为上述的验证手段均为概率的，为防止证明者靠庞大的计算能力进行反复重试，可以要求证明者在提供 STARK 证明的同时也提交一个工作量证明 （PoW），使得重试的代价变大。

---

*Originally published on [BCG Labs](https://paragraph.com/@bcg-labs/zk-stark)*