分解等式多项式优化sumcheck

原文：https://blog.lambdaclass.com/how-factoring-equality-polynomials-optimizes-sumcheck/

译者：Kurt Pan

在本文中，我们将继续研究和分析 Bagad、Dao、Domb 和 Thaler 的论文《加速 SUMCHECK》，该论文讨论了应用于多线性多项式乘积的 SUMCHECK 协议的优化。现在是深入探讨具体细节的时候了：由于等式多项式在密码学环境中被广泛使用，因此引起了极大的关注。

从前...

读者肯定遇到过等式多项式（也称为"eq 多项式"）——这些多项式在其定义域的所有点上都求值为零，除了一个点求值为一。在通常的实分析术语中，它们也被称为笛卡尔空间中点的示性函数。回顾一元和多元多线性多项式的作用，等式多项式可以通过将"较小的"多项式相乘得到。具体来说，假设  是一个域，令 ：即

其中 。现在假设我们将  分成块；例如，假设我们想将其分成三块，即

其中  是  的一个划分，使得 

对于 。

点的块划分的好处是它与等式多项式的因式分解兼容：

对于 ，变量  的块划分。

这当然与多线性多项式插值基的张量性质完全兼容，并不令人惊讶。另一个观察结果很有用并将发挥关键作用，特别是在对有限域上定义的多项式的求值求和时。每当多项式  可以如上所示进行块因式分解时，其积分（即其求值之和）可以顺序进行，换句话说：有一种聪明的方式来重新排序求值域以供我们利用。具体来说，假设  并且

那么对所有  的求和可以根据其任何块进行索引：

其中通过固定外层求和中的索引，涉及该索引的因子可以从内层求和中提取出来（即反向分配律），所以

这类想法将是我们讨论和利用的：固定  将允许预计算关于  的和，其中  被视为参数：在这个意义上，后者的和被预计算，然后在调用参数  时被重用。

如果读者想知道这个游戏的名字：那就是累积、累积、累积（但要巧妙地）。

想法

我们现在准备深入研究 BDDT 提出的优化。起点是对以下形式的多项式进行 sum-check 协议 

作者们在 Angus Gruen 的工作基础上进一步发展。简而言之，Gruen 的关键想法是利用等式多项式  的特殊结构。这个多项式可以分解为乘积：

这种分解的效果是，轮多项式  原本定义为对  的求和，现在看起来像一个乘积：

轮多项式现在是一个线性因子  的乘积，即

它依赖于前几轮的挑战 () 和当前变量 ()，以及一个次数为  的因子 ：

其中包含实际的求和，包括  多项式的乘积和  多项式的剩余部分。证明者在第  轮要计算的多项式是

读者可能会问以这种方式思考  有什么好处。

证明者现在不需要计算复杂多项式 （次数 ）的  个求值，而只需要计算更简单的多项式 （次数 ）的  个求值。其中一个求值  可以从协议的一致性检查（）导出，因此实际上只需要显式计算  个和。

总之，Gruen 降低了证明者必须执行最多工作的多项式的次数，在协议的每一轮中节省了一个完整求值的成本。BDDT 的关键想法是重新应用  多项式的可分离性，但这次是在被求和的剩余变量（）上，结合他们之前提出的将  在随机挑战处的求值偏转到拉格朗日插值多项式求值的提议。大体上，这项新工作的流程如下：

1. 变量分割： 他们将剩余变量集  分成两个适当长度的部分，我们暂时称之为 （左）和 （右）。
2. 嵌套求和： 由于这种分割，计算  的和可以重写为嵌套和：

这种重写是优化的核心。证明者现在可以先计算内层和（对 ），然后将这些结果用于外层和（对 ）。

这种"和分割"技术在时间和特别是内存方面产生了非常显著的好处。

• 内存大幅减少： 标准方法需要预计算并存储所有  的  求值表——大小为  的表。BDDT 的优化消除了对这个巨大表的需求。相反，证明者只需要预计算变量的一半（ 和 ）上  求值的表，大小约为 。从  的内存需求到  是指数级的改进，使得更大的问题变得可行。
• 降低计算成本（时间）： 通过避免与大型  表的乘法，证明者节省了相当多的操作。论文估计这种优化减少了大约  次大域元素之间的乘法成本，其中  是求和域的大小。和在较小的域上迭代处理，这改善了内存局部性和计算效率。

这种优化在协议的前  轮中应用。对于剩余的轮次，好处减少，算法切换回标准方法。

组织胜过时间

作者提出 Gruen 策略和他们自己的 SmallValues 优化想法的组合，这意味着在求值多项式  和  时需要特别注意。在轮 ，发送给验证者的数据

有一个计算要求更高的部分：在适当大的集合中计算  对于 。到目前为止，这个多项式的唯一可用定义由下式给出

仍需要一些澄清。 的部分是如何定义的？这个和是如何执行的？它与作者之前制定的 SmallValues 优化有什么关系？

需要强调的是，这个描述在概念上是合理的，包含了这种优化中涉及的关键思想。此外，必须提到的是，在这个层面上，剩余向量  的块划分和等式多项式的因式分解是一个动态因素： 的长度在轮  时是 ，因此从绝对角度来看， 和  的长度将随轮次变化。

虽然这对于咖啡桌谈话来说已经足够，但从算法角度来看还有些不足，特别是如果要期望获得一些收益。

需要一个最优参数

为了在概念清晰度和高效计算之间取得平衡，作者定义了一个名为  的最优参数——仔细选择以最小化证明者的总时间。其选择基于成本权衡：

• 优化轮次的成本（）：这个成本（主要是 sl 乘法）随  呈指数增长，因为累加器的大小约为 。
• 标准轮次的成本（）：这个成本（主要是 ll 乘法）随着  的增加而减少，因为要执行的"昂贵"轮次更少。

 的最优值是这两个成本平衡的点。论文提供了一个公式来估计算法 4 的这个最优点，它取决于多项式的结构（因子数 ）和硬件操作的相对成本（ll 和 ss 乘法成本之间的比率 ）。最优切换点  可以通过以下公式估计：

其中：

•  是多线性因子的数量。
•  是大-大（ll）和小-小（ss）乘法之间的成本差异因子。作者使用  进行估计，并为这个选择提供了更深入的背景（鼓励读者在原文中寻找详细信息！）

这个参数严格控制 SUMCHECK 协议在任何给定阶段的工作机制：

• 如果   ：你处于"优化阶段"。协议使用预计算的累加器非常快速地计算证明者的消息。
• 如果  ：你已经越过阈值。协议切换到更标准的算法（如算法 5）用于剩余的轮次，因为预计算的好处已经结束。

现在我们能够进一步研究  的块划分。作者优化的实现基于这些点在优化参数  和变量数  方面的静态划分。这个划分被命名为

以与动态划分相同的方式工作，但由于长度现在是常数，因此允许高效计算。它们表示不在  轮前缀中的变量的固定分割。

•  是计算"内层和"的变量集。
•  是"外层和"迭代的变量集。

多项式的  个总变量被分成三个不相交的组，其并集构成完整的变量集：

1. 预计算前缀 ：前  个变量。
2. 集合 ：接下来的  个变量
3. 集合 ：最后的  个变量

因此， 和 共同形成不属于预计算前缀（即预计算后缀）的变量集的划分。它们的大小之和是 ，大约是 ，预计算后缀的总大小。

现在我们已经确定了涉及的符号和参数，让我们看看他们的算法在轮  中如何实际计算所需的值。

块描述在预计算阶段的效果

为了计算  - 作者使用 SmallValue 优化 - 它允许计算验证者发送的随机挑战处的多线性多项式乘积的求值。正如我们在早期文章中提到的，这是通过将求值负担转移到在基域中具有系数的点网格上定义的多变量拉格朗日多项式来完成的——并求值这些多项式。所需的求值现在是由称为累加器的预计算系数加权的和，这些系数取决于网格和乘积。

为了具体化，回顾  的定义

SmallValues 优化允许将其重写为

其中

1.  是基域中点的适当插值网格。具体来说，如果  是不包括 eq 因子的  个多线性多项式的乘积，设置  则 
2. 多项式  是与网格  相关的  变量拉格朗日插值多项式 - 正是这些多项式最终在挑战  处被求值。对于 ，我们设置 。
3. 作者喜欢将多项式  的  个值收集在一个按网格中的点索引的单个  长向量中，在一个单一的挑战向量  中
4. 最后一行括号中的和是累加器  的定义——简单地说是用拉格朗日插值多项式表示  值所需的系数。作者将此表示为挑战向量和累加器向量之间的"内积"，也按  索引：

现在是让块划分的力量发光并发挥其魔力的时候了：对  的求和现在可以分两步进行：

别慌，我们已经到了。现在考虑前缀  并调用 。最后的内层和现在由  和  参数化，应称为临时累加器 。

现在我们已经命名了适当的对象，我们可以描述算法的工作原理。

逻辑和算法步骤：

核心思想是一种记忆化形式。算法不是为每个累加器计算整个和，而是计算一次最内层的和并重用结果：真正的块划分效果。

1. 对  的外层迭代：算法有一个主循环，遍历  段中变量的所有可能赋值。
2. 内层和计算：在该循环内，对于固定的  值，算法计算最内层的和。这个和是对  的所有赋值，并取决于前缀 （推广 ）和当前的 。
   a. 对于每个前缀 ，它计算 。
   b. 每个  的这个内层和的结果存储在称为  的临时累加器中。
3. 分配到最终累加器：一旦为当前  计算了所有  值，算法将它们分配到最终累加器 。这是通过以下方式完成的：
   a. 它遍历每个前缀  及其在  中的相应值。
   b. 使用映射函数 idx4（在 A.5 中定义），它确定这个前缀  贡献给哪些最终累加器 。
   c. 它将  的值添加到适当的最终累加器，由外层 eq-poly 因子  加权。

分类和分配机制

当我们研究 BDDT 的 SmallValue 优化时，我们讨论过这种方法，但很高兴提醒读者这是如何执行的。idx4 分类算法的作用是在预计算阶段充当智能"调度器"或"路由器"。它的功能是确定哪些最终累加器 （可能来自不同的轮次）应该用刚刚计算的中间结果更新。

过程 9（算法 6 的预计算引擎）是为高效率设计的。它不是分别计算每个累加器 ，而是遍历长度为  的所有可能前缀 ，并为每个前缀计算单个值：临时累加器 。

问题是单个值 （例如，为前缀  计算）可以是以下计算的一部分：

• 第 1 轮的累加器：。
• 第 2 轮的累加器：。
• 第 3 轮的累加器：。

idx4 回答的问题是：给定一个 ，这个  必须发送到的最终累加器的所有"地址"  是什么？

它的逻辑包括为每一轮 （从 1 到 ）"分解"前缀  并检查它是否满足所需的结构。对于前缀  要对轮  的累加器有效，对应于未来变量的前缀部分（向量 ）必须是二进制的（仅包含 0 和 1）。多项式  具有  因子的事实最终大大简化了这个分配步骤，因为在构建累加器时涉及的预计算乘积/和非常少。

直观示例

想象  且计算的前缀是 。idx4 将执行以下操作：

1. 它是否贡献给第 1 轮（）？
   a. 。
   b. 余数是 。
   c. 由于  是二进制的，是。idx4 生成元组 __。
2. 它是否贡献给第 2 轮（）？
   a. 。
   b. 。
   c. 余数是 。
   d. 由于  是二进制的，是。idx4 生成元组 。
3. 它是否贡献给第 3 轮（）？
   a. 。
   b. 。
   c. 余数  为空。
   d. 是。idx4 生成元组 。

相反，如果 ，它只会贡献给第 1 轮。对于第 2 轮和第 3 轮，前缀的  部分将包含 2，这不是二进制值，因此不是定义这些轮次累加器的布尔超立方体上的和的一部分。

在你从椅子上摔下来之前的一个小例子

为了固定想法，我们现在将通过一个具有小的、具体数字的例子。如果你愿意，拿一张纸和一些咖啡，在我们进行初始轮次时仔细检查计算。

设置

我们将使用一个 6 个变量的多项式，同时将优化轮次保持在 ****。这个改变允许我们在第 2 轮有一个非空的 ，从而显示临时和最终累加器之间的完整交互。

考虑多项式

 是向量  的等式多项式。考虑 ，则只有第 1 轮和第 2 轮被优化。作为作者的插值集选择，我们将坚持使用 。证明者需要为  计算 。

明确划分

由于 ，6 个变量按如下划分：

• 预计算前缀 及其"eq"伴侣 
• 预计算后缀 然后分为
  a. （大小 ）：。其 eq 向量是 。
  b. （大小 ）：。其 eq 向量是 。

第一轮

证明者需要计算

在  和  处的值。记住线性因子  定义为：

所以在第 1 轮 ，过去挑战集  为空。按照惯例，空集上的乘积是 1。因此，公式的第一个因子简单地是 1。这意味着

这意味着  和 ，所以好消息是我们不需要计算 。让我们开始工作，看看  的首项系数是如何计算的。

根据算法 6，

因此，任务简化为计算最终累加器 ，这就是临时累加器发挥作用的地方。由于优化参数是 ，则

• 对于第一轮，我们将考虑的前缀  是 
• 然后后缀分为  和 ，由于 eq 向量是  和 ，我们有 

   所以我们不会计算  的临时累加器（它乘以零）。

为了完整性，我们在这里包含一个预计算的小表：

 的临时累加器

所以让我们计算  的外层循环。现在乘积的内部权重由