[Stark101] 2.低度拓展 (LDE)

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

导读

低度拓展(LDE)是Stark中用于提高安全性的一个步骤，通过把多项式的域拓展到更大的域，从而提高计算的安全性。

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

• 乘法群
• 多项式
• 1. 计算轨迹

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

低度拓展

LDE，全称Low Degree Extension，是Stark中用于提高安全性的一个步骤，通过把多项式的域拓展到更大的域，从而提高计算的安全性。\ 别被他的定义吓到，实际上他是一个很简单的东西，他其实就是把多项式映射到一个更大的域，但是不修改多项式的次数的方法。

📖 LDE保持多项式的次数不变，只是扩大了定义域。这就像是：

• 原来只能在小范围内画图
• 现在可以在更大的范围内画同样的曲线

我们来看一下下面这个可视化例子, 尝试拖动滑块来看看不同拓展下值的变化。

⚠️ 图标中的线，虚线，均为为了可视化而显示的线，并不代表多项式在某个位置的具体取值,只有具体的点表示实际取值

Sin函数

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

随着拖动滑块，你可以发现一个有趣的现象，随着拓展域的增大，拓展域下计算的评估值依然经过了原本域的评估值。

此时，我们将扩域后的每一个点记录下来，得到的结果就是经过LDE后的值。扩大多少倍，点就会多多少个。

为什么需要LDE

我们可以很明显的看到，在扩域后，多项式的曲线并没有发生改变，只是点的数量变多了。也就是采样的数量变多了。

如果说攻击者重现构建了一个多项式，只有最后一个点不同，其他点都一样，那么在攻击时，验证者进行抽样检查命中的概率就非常小。比如我们在对10个点做多项式承诺，攻击者只修改了一个点，那么验证者抽样检查时，查出攻击的修改点的概率就是1/10。

但是我们通过LDE后，采样的点变多了，假设我们扩域了10倍， 那么现在100个点中，只有9个点是对的，那么找到攻击的修改点的概率就变成了91/100。

💡 LDE的本质就是通过增加采样点，从而降低攻击者修改一个点通过验证的概率。