[Stark101] 3. 承诺（Commitments）

原文链接：https://www.zk101.io/stark101/3_commit 前往可获得更好的体验

导读

承诺（Commitments）是Stark中用于去除需要交互验证的步骤，通过将Trace的值进行默克尔树构建，从而获得虚拟的交互验证。

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

• Stark 101 - 2. LDE
• 知识库 - 乘法群
• 知识库 - 多项式
• 知识库 - 默克尔树

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

这章内容比较多，需要静下心来慢慢读。

承诺之前

在前两章，我们分别学习了Trace和LDE，我们这里复习一下他们的作用：

• Trace 是计算过程中所有的中间值，以及最终的执行结果。
• LDE 是用于将Trace的值拓展到更大的域，从而提高计算的安全性。

那么，很奇怪的是，我们获得的Trace值，X轴上的点有些是连续的，根本没法通过LDE来拓展！

这里我们就需要知道另外一个事情，Stark中，我们会把Trace的值按照顺序平铺，然后将所有的值映射到一个满足大小的乘法子群中。

📖 为什么不能用自然数类似（0,1,2,3,4,5,6,7,8,9,10），而是需要用乘法子群？ 根据0xhhh和郭老师的解释，大致上来说主要是两个原因：

1. FRI协议需要使用FFT（快速傅里叶变换）来高效地在大量点上评估多项式：

   • FFT需要在”单位根”上工作
   • 乘法子群的循环特性恰好提供了这些单位根
   • 这让验证过程变得非常高效，从O(n²)降到O(n log n)

2. 域的性质保证了所有必要的运算都能精确进行：

   • 每个非零元素都有乘法逆元
   • 所有的除法运算都能得到精确结果
   • 不会出现”除不尽”的情况

其中第一点是选择乘法子群的主要原因。

也就是说，确实可以选择一个任意的有限域，但是性能上并不好。

前两个章节，我们都在自然数上进行运算，但是Stark中，实际上LDE的过程会在乘法子群中进行。

因此，我们现在需要把我们Trace的值，映射到乘法子群中。

根据乘法群中的知识，我们知道，乘法子群的生成方式来源于对原群按照固定间隔进行取值的过程。\ 在Stark中，不同的实现方案会使用不同的域，也就是不同大小的乘法群。

为了方便，我们使用F97​作为接下来计算的域。他的生成元是5。（一般Stark中，不会使用这么小的域）

生成子群

首先，我们Trace的值只有 0,1,1,2,3,5,8,13,21,34,55,89,144,233,总共为14个值。

但是，我们并不能直接找一个大小只有14的子群，因为14不是2的幂，所以无法满足要求。所以，实际上来说，我们需要对Trace进行扩展，扩展到一个2k的子群上。比如24=16大小的群上，那么多出来的两个空位什么办？直接填0就可以了。

根据乘法群中的知识，我们知道，乘法子群的生成方式来源于对原群按照固定间隔进行取值的过程。

因此，我们需要取一个大小为16的群，那么就可以通过gnew​=g96/16mod97=8（g为生成元5）作为新的生成元进行生成。

于是根据我们新的生成元 8，可以计算出一个大小为16的子群。然后我们把这个子群作为X值，将Trace的值映射到这个子群上。

结果如下表：

构建多项式

根据多项式中的知识，我们使用拉格朗日插值法，构建多项式。其中X值为大小16的子群，Y的值为Trace的值，那么就可以轻松的构造出一个多项式了。

结果如下：

f(x)=66x15+94x14+55x13+5x12+42x11+83x10+28x9+86x8+4x7+62x6+20x5+94x4+94x3+29x2+79x+32

这个其实没必要过多关注，我们一般不会手动计算，而是使用代码来生成。

他的图像差不多是这样（你可以点击下方标签来隐藏多项式，只看点）：

前往 zk101.io 体验交互式演示。

LDE

来进行我们的LDE的计算吧！按照之前学的内容，我们可以轻松的构建出新的乘法子群，这里按照扩大到32个元素来计算。 根据公式轻松计算 g96/32=28。生成元就是28。从而得到新的乘法子群。

💡 新的乘法子群为：[1, 28, 8, 30, 64, 46, 27, 77, 22, 34, 79, 78, 50, 42, 12, 45, 96, 69, 89, 67, 33, 51, 70, 20, 75, 63, 18, 19, 47, 55, 85, 52]，order为32

感兴趣可以根据上面给出的生成方式验算一下。

很明显，曲线一样，但是多了更多的点。

承诺

完成了我们最终多项式的构建后，我们就要进入承诺的部分了！

在Stark中，承诺（Commitments）是用于去除需要交互验证的步骤，通过将Trace的值进行默克尔树构建，从而获得虚拟的交互验证。简单来说，承诺是为了通过大量数据的Hash创造一个可信随机数。

💡在Stark中的承诺是一个Hash链。

比如，你这一步骤发送了一些承诺值A，那么你下一步发送的承诺值如果是B，那么此时如果请求随机数，返回的则是Hash(A,B)的结果。同时，你获得的随机数会基于这个结果生成，而你通过随机数计算出来的新结果又会成为下一个承诺值。

比如： 现在有函数f(x)=x (是的，这个函数就是输入什么就输出什么 😂)，你发送了f(1)=1，那么此时如果请求随机数，返回的则是Hash(1)==A的结果。

然后你计算f(A)=A，那么此时如果请求随机数，返回的则是Hash(hash(1),hash(A))==B的结果。

如果继续计算f(B)=B，则是Hash(hash(1),hash(A),hash(B))的结果。以此类推。

以此类推。

我们将LDE拓展后的所有点的值构建成一个默克尔树，然后获得这个默克尔树的根，作为承诺值。

生成的图如下（其中，黄色表示原来的数据，绿色表示扩域后新增的数据，蓝色表示Hash节点，树最上面一个元素就是我们树的根）：

此时，我们就可以将这个根作为承诺值，发送给验证者。