ZKSwap 团队解读零知识证明算法之 Zk-STARK

撰文： ZKSwap 小白

Concept：zk-stark vs zk-snark

谈到 ZKP 算法，大伙可能听过一些，比如 zk-snark、zk-stark、bulletproof、aztec、 plonk 等等。今天，ZKSwap 团队就和大伙聊聊这一对“表面兄弟”，zk-stark 和 zk-snark 算法的异同之处。

首先，先从名字说起。

如下图所示，我们将名称 zk-stark 和 zk-snark 根据功能特点分别分成四个部分，然后逐个比较分析。

ZKSwap 团队解读零知识证明算法之 Zk-STARK

Zk-stark =gt; zk – s t ark

zk：零知识，表明隐私的输入将会被隐藏，除了证明者，其他任何人不会看见；
s：可扩展的，和 Replay Computation 的验证耗时相比，zk-stark 的证明和验证耗时分别与之呈拟线性关系和对数关系；
t：透明的，zk-stark 算法没有 CRS setup by Trusted party；
arg：知识论证，只有知道 private input 的 prover，才能生成有效的 proof；

Zk-snark =gt; zk – s n ark

zk：零知识，表明隐私的输入将会被隐藏，除了证明者，其他任何人不会看见；
s：简洁的，指的是生成的 proof 足够小和验证时间足够短；
n：非交互式的，Prover 生成证明的过程中和 verifier 没有交互；
arg：知识论证，只有知道 private input 的 prover，才能生成有效的 proof；

Compare 相同点

1. 都实现了将隐私的输入可靠隐藏；

2. 都是基于知识论证，不知道 private input 的 prover 生成不了有效的 proof；

3. 都可以实现交互式与非交互式式的算法，只是取决于 randomness 是由谁来生成的；

不同点

1. zk-stark 具有可扩展性，即证明和验证的耗时与原始计算的耗时分别呈拟线性关系（且线性因子为常量）和对数关系，这意味这，如果原始输入的数据集增大 1000000 倍，zk-stark 的证明耗时增加线性倍数的时间，但验证时间仅仅增加 21 * log1000000 =~ 420 倍。证明耗时呈线性关系基本满足所有的 ZKP 算法，但是验证时间呈对数关系，仅此一家，因此在扩展性上，zk-stark 要胜一筹。

2. zk-stark 同样具有简洁性，但是是验证简洁性。所谓简洁性，通常是指即使验证程序很大，生成的 proof size 也不会很大，同时又能很快的完成验证（比 native computation 快很多）。相比对 zk-snark，zk-stark 的 proof size 要大的多，因此在简洁性上，zk-snark 要胜一筹。

ALG compare

前面从概念上对 zk-stark 和 zk-snark 算法做了比较，其异同点可以笼统的概括为：

都是基于知识论证的 ZKP 算法；
zk-stark 不需要 zk-snark 的 Trusted party 设置 CRS，因此是 Transparent；
zk-stark 的验证耗时与 native computation 耗时呈对数关系，因此是 Scalable；

下面，我们将从算法层面，去做相对更深入一些的比较分析：

zk-snark ALG 【4】

1. 算法思想：将证明 CI statement 成立问题转换成证明多项式等式成立问题，转换过程用到了算术环路和 QAP 方法；

2. 多项式等式成立意味着什么？（图中黄色部分） a. 等式两边可以看作两个度相等的多项式，假设为 n，其交点最多有 n 个，假如在一个很大的域范围内随机选一个点，如果的两个多项式在此点的值相等，则证明两个多项式是相等的。 b. 我们可以看到，等式右边的多项式因子 Z 是目标多项式，它的零点就是右边整体多项式的零点，也就是等式左边整体多项式的零点，而等式左边的多项式在这些零点的取值，就转换成了一个个的算术电路里每个乘法门对应的一阶线性约束等式（R1CS）成立，即原始计算等式成立（注：R1CS 由原始计算等式分解得到）；

3. 算法分为三个步骤：CRS 生成；证明者证明；验证者验证；

4. 可以看到 prover 生成证明过程中，没有与验证者交互，因此是 non-interative;

5. 如何保证 prover 用于生成证明的 A/B/C/H 是多项式且是小于某个度数呢？ a. 通过 trusted party 来保证，因为它是可信任的，因此它生成 pk，vk 用到的 A/B/C 等肯定是多项式并且是小于某个度的； b. 如果证明者作恶，那么验证者将会很大概率验证失败； c. 主要用到了同态加密 HH 和系数知识假设 KCA 和椭圆曲线双线性配对等数学知识；

ZKSwap 团队解读零知识证明算法之 Zk-STARK1

zk-stark ALG 【1】【2】【3】

1. 算法思想：将证明 CI statement 成立问题转化成证明多项式小于某个度的问题，转换过程用到了多项式插值方法；

2. 多项式等式成立意味着什么？（图中黄色部分）

思想与 zk-snark 一样，T 同样为目标多项式，其零点已知且公开，也是等式左侧多项式 Q 的零点，多项式 Q 在每一个零点的取值都对应了一个 execute trace 的成立（没错，在 zk-stark 中，原始计算语句转化成了多个 execute trace，这类似与 zk-snark 中的 R1CS）。因此多项式相等，意味着 execute trace 正确，说明原始 CI 成立。

3. 多项式小于某个度意味着什么？

和 zk-snark 类似的是，两者都把 CI statement 转换成了证明多项式等式成立的问题（可以这么抽象的认为，zk-stark 不仅要证明多项式相等，还要证明相应多项式是小于某个度的，这是 zk-stark 算法的核心，所以才有了第一点的描述）。为了防止验证者作恶，必须要保证多项式是低于某个度的（存在这样一种可能，攻击者可以特意生成满足证等式的一些点，这些点并不是真正的多项式上的点，但是根据这些点生成的证据也能通过验证者验证）。不同的是，zk-snark 使用了 trusted party 机制和同态加密等数学方法，而 zk-stark 使用了低度测试等数学方法。当且仅当多项式真正的小于某个度时，多项式的相等才是真实意义上的相等，说明生成轨迹多项式的 execute trace 是正确的，即原始 CI 成立。

4. 算法分为两大步骤，算术化和低度测试； a. 算术化：是把问题转化为多项式形式 b. 低度测试：是证明组合多项式 (图中黄色) 和轨迹多项式（图中绿色）小于某个固定的度–gt;FRI 算法

5. 在生成证明的过程中，有交互（图中红线所示），所以图中描述的是交互式的零知识证明算法；

ZKSwap 团队解读零知识证明算法之 Zk-STARK2