ZK101 - 零知识学习零知识

导读

约束（Constraints）是Stark中用于将Trace的值进行约束，从而保证计算结果满足预期。

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

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

约束是什么

约束实际上就是创建多项式来限定Trace的值，比如限定多项式开头必须是什么数字，结尾必须是什么数字，并且每一个数字之前的关系是什么，通过这些约束就可以创建出很多小的，单独的多项式来约束Trace的值。

回顾一下我们前几章创建的Trace。

我们之前说过，所有的Trace在计算时会展开成一维数组，也就是

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 0, 0]

不知道为什么有两个0的请看上一章节开头部分

并且将其设定为 $a$ 。

所以，我们可以创建几个约束。这里很重要！ 首先是第一个值必须等于0，也就是

$f(a[0]) = 0$

接下来是对最后一个值的约束，最后一个值必须为233，也就是

$f(a[13]) = 233$

接着是对整体Trace的约束，斐波纳契满足前两个元素之和等于第三个元素，所以 ,从Trace的第一个元素开始，当前元素相加后一个元素，应该等于后第二个元素，也就是

$x \leq 11$ 时， $f(a[x]) + f(a[x+1]) = f(a[x+2])$

💡

为什么是小于等于11？因为在12和13号元素后面已经没有两个有效元素了。

构建约束多项式

上面的内容只是说明了什么地方需要约束，应该怎么约束，在实际使用中，我们还需要构建约束多项式。

首先看第一个约束， $f(a[0]) = 0$ ，也就是， $x=1$ 时， $f(x) = 0$ ，此时多项式 $p_0(x)$ 应该为 $p_0(x) = \frac{f(x) - 0}{x - 1}$ 。

别着急，我猜你会有一些困惑。但是接下的内容会为你解答。

💡

在构建约束多项式的时候，需要包含实际的Trace多项式，这里很重要。但是更重要的是，在验证的时候，并没有提供Trace多项式，而是提供了 $f(x)$ 的值，也就是说，约束多项式的约束是公开的，但是验证时会用 $f(x)$ 的实际计算结果代入约束多项式，而不是提供真正的Trace多项式。

p_0(x) = \frac{f(x) - 0}{x - 1}

我相信你的第一个疑问是，这个 $x-1$ 是怎么来的？
还记得我们上一章承诺-生成子群中，我们创建的子群吗？
在子群中， $g$ 是生成元， $g^1$ 是子群中的第一个元素结果是1。实际上，这里的 $x-1$ 中，x其实是 $g^0$ 。因为我们的取值范围是在乘法子群上，所以这个公式展开了写其实是这样。

p_0(x) = \frac{f(x) - 0}{x - g^0}

x取值于乘法子群， $g^0$ 就是1。

同样的，这里说 $x=1$ 时，实际上就是 $x=g^0$ 时。

第二个疑问可能在于，当 $x=1$ 时，这个多项式会出现0分母的情况。

实际上，这个多项式并不会保持除法形式，而是会展开。在知识库 - 多项式 # 多项式的因式分解中，我们提到过，多项式一定可以整除(x - a)，a为多项式的根。所以这个多项式在计算的时候，已经把分母消除了。

第三个疑问可能在于，这个约束在表达什么。

这个约束其实表达是，当 $x=1$ 时，应该有 $p_0(x) = 0$ 。所以，需要 $f(x) - 0 = 0$ 。

这里的数字可能有点巧合，我们看一下第二个约束。

p_1(x) = \frac{f(x) - 233}{x - g^{13}}

这个例子会很好解释

根据计算当 $x=g^{13}$ 时， $f(x)=233$
$x=g^{13}$ 是多项式 $p_1(x)$ 的根。（因式分解消除）

带入一计算，这个约束就可以表达，在 $x=g^{13}$ 时， $p_1(x) = 0$ 。

因此我们可以推断第三个约束。

p_2(x) = \frac{f(x) - f(x+1) - f(x+2)}{(x - g^0)(x - g^1)(x - g^2)...(x - g^{11})}

当然，计算 $(x - g^0)(x - g^1)(x - g^2)...(x - g^{11})$ 时，可以利用一个小小的优化手段。

根据知识库 - 乘法群 # 附加内容：特殊多项式乘积，我们知道

\prod\limits_{i=0}^{12} (x-g^i) = x^{13} - 1

因此， $p_2(x)$ 可以写成

p_2(x) = \frac{f(x) - f(x+1) - f(x+2)}{\frac{x^{13} - 1}{x - g^{12}}}

整理约束

此时，我们成功构建了三个多项式约束，分别是

关乎第一个元素的约束

p_0(x) = \frac{f(x) - 0}{x - g^0}

关乎最后一个元素的约束

p_1(x) = \frac{f(x) - 233}{x - g^{13}}

关乎整体Trace的约束

p_2(x) = \frac{f(x) - f(x+1) - f(x+2)}{\frac{x^{13} - 1}{x - g^{12}}}

小结

约束的构建是Stark中非常重要的一步，通过约束，我们可以将Trace的值限定在一定的范围内，从而保证计算结果的正确性。

下一章节，我们将会把多项式组合，获得一个最终多项式。

3. 承诺（Commitments）5. 组合多项式（Composition Polynomial）