ZK101 - 零知识学习零知识

导读

组合多项式（Composition Polynomial）是Stark中用于将多个约束多项式组合在一起，从而形成一个最终的多项式。

但是在章节开始之前，你需要必须 🚨掌握以下前置知识：

Stark 101 - 5. Composition Polynomial

以上内容均为超级精简版，强烈推荐看一遍。

神奇的FRI

FRI是一个单纯为了证明多项式次数的一个方法，他可以保证一个多项式的次数是期望的数值，因为我们知道，当你希望只修改某一个点的值的时候，插值出的多项式的次数相比于原始多项式的次数会更高。所以，FRI通过检测多项式次数的方式来防止多项式的评估值被修改。在最后配合约束多项式，我们就可以保证两个点。

提交的Trace满足约束
要求所有多项式都满足原来的次数，防止查询阶段使用其他高次多项式构建值符合约束的结果进行欺骗，也就是需要保证所有查询多项式次数的统一。

FRI的理论实现

在讲FRI之前，我认为有必要好好了解一下理论实现，工程实现其实是对理论实现的一种简化。但是如果不理解理论实现，这反而有可能成为一种复杂的思维陷阱。

FRI的核心基于一个非常简单的数学逻辑，主要分为3个步骤。

折叠多项式和评估域 - 将原来的多项式次数降低了一半
构建承诺 - 承诺的值比较重要，因为后续verifer可以根据这个值，验证折叠值
验证 - 根据承诺的值，验证折叠值

我相信你肯定对这里的内容有点疑惑，不过没关系，我会用一个非常简单的例子让你先有一个印象。

上面这张图涵盖了一个简单的完成流程，后续我们的内容将会通过解释这张图的内容来帮助你理解FRI的实现。

大致上来说分为4个步骤：

多项式分解
折叠多项式和评估域
模拟交互式验证，生成idx和sib idx值，计算结果
验证（这个验证就是ZK流程中在verifier端做的）

详细的实现步骤

在了解了 FRI 的基本步骤后，让我们理解一下其背后的原理。

多项式分解

在计算折叠之前，我们先要搞清楚一些前置的知识内容。对于任意多项式 $f(x)$ ，我们都可以将其表示为：

P(x) = g_e(x^2) + x \cdot g_o(x^2)

其中：

$g_e(x)$ 是偶次项组成的多项式
$g_o(x)$ 是奇次项去掉 x 后组成的多项式（即将所有奇次项除以 x 后的结果）

💡

假设我们有一个7次多项式：

P(x) = \overbrace{\color{red}{x^7}}^{\text{奇次项}} + \underbrace{\color{blue}{2x^6}}_{\text{偶次项}} + \overbrace{\color{red}{3x^5}}^{\text{奇次项}} + \underbrace{\color{blue}{x^4}}_{\text{偶次项}} + \overbrace{\color{red}{4x^3}}^{\text{奇次项}} + \underbrace{\color{blue}{2x^2}}_{\text{偶次项}} + \overbrace{\color{red}{x}}^{\text{奇次项}} + \underbrace{\color{blue}{5}}_{\text{偶次项}}

我们可以将其重写为：

P(x) = (\color{blue}{2x^6 + x^4 + 2x^2 + 5}) + \color{red}{x}(\color{red}{x^6 + 3x^4 + 4x^2 + 1})

这样，我们就得到了：

$g_e(y) = \color{blue}{2y^3 + y^2 + 2y + 5}$
$g_o(y) = \color{red}{y^3 + 3y^2 + 4y + 1}$

其中 $y = x^2$

折叠多项式和评估域

知道如何拆分奇偶后，我们就可以开始按照折叠公式进行折叠，折叠公式为

P_{next}(x) = g_e(x) + \beta \cdot g_o(x)

其中， $\beta$ 是根据Hash链计算出的随机数。

💡

继续我们上面的那个例子。

$g_e(y) = \color{blue}{2y^3 + y^2 + 2y + 5}$
$g_o(y) = \color{red}{y^3 + 3y^2 + 4y + 1}$

根据这两个，然后设 $\beta = 6$ 我们可以得到一个折叠后的新公式为

\begin{align*} P_{next}(x) &= \color{blue}{2x^3 + x^2 + 2x + 5} + \color{black}{6}\color{red}(x^3 + 3x^2 + 4x + 1) \color{black} \\ &= 8x^3 + 19x^2 + 26x + 11 \end{align*}

这样我们就得到了一个3次多项式。

而评估域的折叠方式为取偶次项，比如。

例如，对于评估域：

\begin{array}{cccccccccccccccc} g^0 & g^1 & g^2 & g^3 & g^4 & g^5 & g^6 & g^7 & g^8 & g^9 & g^{10} & g^{11} & g^{12} & g^{13} & g^{14} & g^{15} \\ w^0 & w^1 & w^2 & w^3 & w^4 & w^5 & w^6 & w^7 & w^8 & w^9 & w^{10} & w^{11} & w^{12} & w^{13} & w^{14} & w^{15} \end{array}

第一次折叠后变为：

\begin{array}{cccccccc} g^0 & g^2 & g^4 & g^6 & g^8 & g^{10} & g^{12} & g^{14} \\ w^0 & w^1 & w^2 & w^3 & w^4 & w^5 & w^6 & w^7 \end{array}

注意，当我们取idx的时候，实际上是根据 $w$ 来取。

模拟交互式验证，生成idx和sib idx，计算结果

为什么要进行这一个步骤？实际上这里是取决于3个公式（此处的 $f(x)$ 为上面的 $P(x)$ ）

f_{even} = \frac{f(x) + f(-x)}{2}

f_{odd} = \frac{f(x) - f(-x)}{2x}

f_{fold} = f_{even} + \alpha \cdot f_{odd}

💡

这里其实是一个简单的数学计算，我们来构建一个简单的例子。

还是以上面的例子为例，我们的公式为

f(x) = x^7 + 2x^6 + 3x^5 + x^4 + 4x^3 + 2x^2 + 5 + x

当我们计算 $f_{even} = \frac{f(x) + f(-x)}{2}$ 时，如果x为正数，那么公式其实结果没变。但是当我们传入负数的时候，那么结果就会变成

\begin{align*} f(-x) &= (-x)^7 + 2(-x)^6 + 3(-x)^5 + (-x)^4 + 4(-x)^3 + 2(-x)^2 + 5 + (- x) \\ &= -x^7 + 2x^6 - 3x^5 + x^4 - 4x^3 + 2x^2 - 5 - x \end{align*}

于是和原始公式相加，则就可以获得完全偶数的结果了，同理其他部分的也是这样。

💡

$x$ 的 $-x$ 是怎么计算的？因为我们现在是在有限域中计算，不可能说直接就是加一个负号那么简单。

$x$ 的 $-x$ 我们称之为 $sib\_idx$ 。假设 $g^{2n}=1$ ，转换一下就是 $(g^n)^2=1$ ，所以 $g^n = 1$ 或者 $-1$ 。由于 $g^n$ 不可能为 $1$ ，所以一定为 $-1$ 。因此，任何数乘以 $g^n$ 会变成原来的负数。根据 $g^{idx} \times g^n$ ，所以 $g^{idx+n}$ 的结果就是 $-g^{idx}$ 。因为 $2n$ 为群的大小，所以 $n$ 为 $length/2$ 。在我们这个例子中，当 $n=8$ 时， $g^{2n}$ 刚好是 $1$ ，构成一个循环群。

于是可以用下面这个公式轻松计算。

\begin{align*} len &= \text{域的大小} \\[0.5em] idx &= \text{Hash链计算出的idx} \\[0.5em] sib\_idx &= (idx + len \div 2) \bmod len \end{align*}

此时可以开始计算我们刚刚提到的3个公式。

假设我们idx随机到2，那么sib idx就是 2+(16/2) mod 16 = 10。

\begin{align*} \text{当 } idx &= 2 \text{ 时：} \\[0.5em] w^2 &= g^2 \bmod 97 = 8^2 \bmod 97 = 64 \\[0.5em] f(w^2) &= (64)^7 + 2(64)^6 + 3(64)^5 + 4(64)^4 + 2(64)^2 + 64 + 5 \bmod 97 \\ &= 47 + 2 \cdot 75 + 3 \cdot 33 + 96 + 4 \cdot 50 + 2 \cdot 22 + 64 + 5 \bmod 97 \\ &= 26 \\[1em] \text{当 } sib\_idx &= 10 \text{ 时：} \\[0.5em] w^{10} &= g^{10} \bmod 97 = 8^{10} \bmod 97 = 33 \\[0.5em] f(w^{10}) &= (33)^7 + 2(33)^6 + 3(33)^5 + 4(33)^4 + 2(33)^2 + 33 + 5 \bmod 97 \\ &= 50 + 2 \cdot 75 + 3 \cdot 64 + 96 + 4 \cdot 47 + 2 \cdot 22 + 33 + 5 \bmod 97 \\ &= 79 \\[1em] \text{在折叠域中计算} P_{fold}\text{，当} idx=2 \text{时对应的是} g^4\text{：} \\[0.5em] w^4 &= g^4 \bmod 97 = 8^4 \bmod 97 = 22 \\[0.5em] P_{fold}(w^4) &= 8(22)^3 + 19(22)^2 + 26(22) + 11 \bmod 97 \\ &= 8 \cdot 75 + 19 \cdot 96 + 26 \cdot 22 + 11 \bmod 97 \\ &= 0 \end{align*}

验证

接着我们验证一下折叠后的结果，也就是 $f_{fold}$ ，假设 $\alpha = 6$

\begin{align*} f_{even} &= \frac{(26 + 79) \mod 97}{2} = 4 \\[0.5em] f_{odd} &= \frac{26 - 79}{2} \times 8^{14} = 22*47 \bmod 97 = 64 \\[0.5em] f_{fold} &= (4 + 6 \cdot 64) \bmod 97 \\ &= 388 \bmod 97 \\ &= 0 \end{align*}

验证通过！

工程实现

在工程实现中，我们需要注意几个点。

计算时，我们没有办法获得Trace的多项式，只有约束多项式，所以我们在计算的时候，需要Prover传入约束多项式的所有参数。这才能计算出来值，并且传入的时候，约束多项式会计算结果，只有传入的值满足约束，才能计算出一个结果，因此，如果约束多项式可以成功计算出值，那么约束也必然满足。
Prover在证明的时候，无法避免的会暴露一些Trace，但是因为这些Trace是在LDE后的域上的，所以并不一定会暴露真正的Trace值。
Prover需要公开给Verifier的值有：
- 构建约束多项式的参数
- 每次折叠都需要使用的IDX
- 域的大小以及对应的IDX和SIB_IDX对应的值
实现时，我们有两次对域上的值进行了查询，第一次是为了构建约束多项式的计算结果，需要对所有的参数进行查询。第二次是为了进行折叠的计算，需要对IDX和SIB_IDX进行查询。这两次查询我们都需要构建一条路径，可以从我们一开始构建的merkle tree中找到要查询的值。这里的结果也是需要进入Hash链进行储存的，因为verifier需要进行验证。

查询阶段

工程实现中，查询阶段实际是通过查询Hash链中的值来还原，传入Hash链中所有的值都是明文可查的，所以，根据Hash链获取验证过程中所有需要的数据即可验证多项式的次数。

但是，验证肯定不是一次的，需要多次查询才能保证安全性，但是因为扩域后，错误的数据会被放大，所以更加容易被查询到。比如：

假设原来的Trace为16个值，如果此时攻击者修改了1个值，那么验证者查询一次后，查到错误的概率为 1/16, 如果进行多次查询，概率也只是 n/16（全部查询是不现实的，一般的实际情况下Trace的数量可能成千上万个）。

那么假设进行了4倍扩域，错误概率就非常大了，因为扩域后的值全是错误，因为虽然是错了一个点，但是整个多项式都发生了改变，扩域后的值一般情况下都是错误的值。此时错误的点其实就变成了 扩域部分 + 1，查到的错误的概率就变成了 49/64 （ $49 = 64-15$ ,64为LDE后的大小，15为原来LDE之前正确值的数量），这个概率就非常大了，如果扩域到8倍，那么查到错误的概率就变成了 240/256 约等于 94%。

因此，为了保证安全，需要进行更多的查询，这个过程是在验证者端完成的，验证者需要进行多次查询，从而保证了安全性。

那么此时，攻击者可能为了保证约束正确，就构建了新的多项式来完成查询，但是FRI会验证你的多项式，如果你使用不同次数的多项式来构建，那么FRI很容易查询出你的真实次数，并且比对后拒绝通过验证。

5. 组合多项式（Composition Polynomial）7. 总结