导读
承诺(Commitments)是Stark中用于去除需要交互验证的步骤,通过将Trace的值进行默克尔树构建,从而获得虚拟的交互验证。
但是在章节开始之前,你需要必须 🚨掌握以下前置知识:
以上内容均为超级精简版,强烈推荐看一遍。
这章内容比较多,需要静下心来慢慢读。
承诺之前
在前两章,我们分别学习了Trace和LDE,我们这里复习一下他们的作用:
- Trace 是计算过程中所有的中间值,以及最终的执行结果。
- LDE 是用于将Trace的值拓展到更大的域,从而提高计算的安全性。
那么,很奇怪的是,我们获得的Trace值,X轴上的点有些是连续的,根本没法通过LDE来拓展!
这里我们就需要知道另外一个事情,Stark中,我们会把Trace的值按照顺序平铺,然后将所有的值映射到一个满足大小的乘法子群中。
为什么不能用自然数类似(0,1,2,3,4,5,6,7,8,9,10),而是需要用乘法子群? 根据0xhhh和郭老师的解释,大致上来说主要是两个原因:
-
FRI协议需要使用FFT(快速傅里叶变换)来高效地在大量点上评估多项式:
- FFT需要在”单位根”上工作
- 乘法子群的循环特性恰好提供了这些单位根
- 这让验证过程变得非常高效,从O(n²)降到O(n log n)
-
域的性质保证了所有必要的运算都能精确进行:
- 每个非零元素都有乘法逆元
- 所有的除法运算都能得到精确结果
- 不会出现”除不尽”的情况
其中第一点是选择乘法子群的主要原因。
也就是说,确实可以选择一个任意的有限域,但是性能上并不好。
前两个章节,我们都在自然数上进行运算,但是Stark中,实际上LDE的过程会在乘法子群中进行。
因此,我们现在需要把我们Trace的值,映射到乘法子群中。
根据乘法群中的知识,我们知道,乘法子群的生成方式来源于对原群按照固定间隔进行取值的过程。
在Stark中,不同的实现方案会使用不同的域,也就是不同大小的乘法群。
为了方便,我们使用作为接下来计算的域。他的生成元是5。(一般Stark中,不会使用这么小的域)
生成子群
首先,我们Trace的值只有 0,1,1,2,3,5,8,13,21,34,55,89,144,233
,总共为14个值。
但是,我们并不能直接找一个大小只有14的子群,因为14不是2的幂,所以无法满足要求。所以,实际上来说,我们需要对Trace进行扩展,扩展到一个的子群上。比如大小的群上,那么多出来的两个空位什么办?直接填0就可以了。
根据乘法群中的知识,我们知道,乘法子群的生成方式来源于对原群按照固定间隔进行取值的过程。
因此,我们需要取一个大小为16的群,那么就可以通过(g为生成元5)作为新的生成元进行生成。
于是根据我们新的生成元 8,可以计算出一个大小为16的子群。然后我们把这个子群作为X值,将Trace的值映射到这个子群上。
结果如下表:
原序列 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 0 | 0 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
计算式 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
结果 | 1 | 8 | 12 | 18 | 22 | 27 | 33 | 47 | 50 | 64 | 70 | 75 | 79 | 85 | 89 | 96 |
构建多项式
根据多项式中的知识,我们使用拉格朗日插值法,构建多项式。其中X值为大小16的子群,Y的值为Trace的值,那么就可以轻松的构造出一个多项式了。
结果如下:
这个其实没必要过多关注,我们一般不会手动计算,而是使用代码来生成。
他的图像差不多是这样(你可以点击下方标签来隐藏多项式,只看点):
LDE
来进行我们的LDE的计算吧!按照之前学的内容,我们可以轻松的构建出新的乘法子群,这里按照扩大到32个元素来计算。 根据公式轻松计算 。生成元就是。从而得到新的乘法子群。
新的乘法子群为:[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
感兴趣可以根据上面给出的生成方式验算一下。
很明显,曲线一样,但是多了更多的点。
承诺(Commitments)
完成了我们最终多项式的构建后,我们就要进入承诺的部分了!
在Stark中,承诺(Commitments)是用于去除需要交互验证的步骤,通过将Trace的值进行默克尔树构建,从而获得虚拟的交互验证。简单来说,承诺是为了通过大量数据的Hash创造一个可信随机数。
在Stark中的承诺是一个Hash链。
比如,你这一步骤发送了一些承诺值A,那么你下一步发送的承诺值如果是B,那么此时如果请求随机数,返回的则是的结果。同时,你获得的随机数会基于这个结果生成,而你通过随机数计算出来的新结果又会成为下一个承诺值。
比如: 现在有函数 (是的,这个函数就是输入什么就输出什么 😂),你发送了,那么此时如果请求随机数,返回的则是的结果。
然后你计算,那么此时如果请求随机数,返回的则是的结果。
如果继续计算,则是的结果。以此类推。
以此类推。
我们将LDE拓展后的所有点的值构建成一个默克尔树,然后获得这个默克尔树的根,作为承诺值。
生成的图如下(其中,黄色表示原来的数据,绿色表示扩域后新增的数据,蓝色表示Hash节点,树最上面一个元素就是我们树的根):
此时,我们就可以将这个根作为承诺值,发送给验证者。