比较 Ligerito 和 WHIR

原文：https://nmohnblatt.github.io/ligerito-and-whir/

作者：Nicolas Mohnblatt

译者：Kurt Pan

Ligerito 是一个新发布的多线性多项式承诺方案，它将 Ligero 的思想与 Sumcheck 协议相结合。它基于纠错码，并在纯随机预言模型（纯 ROM）下被证明是安全的。(    我们说“纯 ROM”是指协议除了 ROM 之外不需要其他假设。)

• https://angeris.github.io/papers/ligerito.pdf
• https://eprint.iacr.org/2022/1608

这些特性与 WHIR 非常相似：纠错码、纯 ROM、部分Sumcheck轮次。自然有人会问：Ligerito 与 WHIR 相比如何？

• https://eprint.iacr.org/2024/1586

我会列举一些相似之处，解释为什么许多人认为这些协议紧密相关；然后讨论它们的主要区别以及我们可以从中学到什么。在此过程中，我会指出一些已知的概念，例如code-switching，已经隐性地融入了 Ligerito 。

• https://eprint.iacr.org/2019/1062

本文假设你对 Reed-Solomon 码和邻近性测试（例如 FRI、BaseFold、STIR 或 WHIR）有一定的了解。

• https://eccc.weizmann.ac.il/report/2017/134/
• https://eprint.iacr.org/2023/1705
• https://eprint.iacr.org/2024/390

相似之处

递归修复变量。 Ligerito 和 WHIR 的第一个相似之处是它们都遵循递归结构。在第  次迭代中，两个协议都将  个变量的问题简化为  个变量的问题。然后，该协议继续执行  次迭代。

WHIR 在其基准测试中将所有迭代设置为  。然而，Ligerito 运行了网格搜索，以找到  个参数和迭代次数的最优值。例如，对于一个包含 28 个变量的多项式，其参数设置为：

• https://github.com/bcc-research/Ligerito.jl/blob/864746fd1cc13c14877fab1b1b5973556b9a65fd/src/configs.jl#L77-L122

这些迭代将问题简化为一个包含 10 个变量的多线性多项式，并将其完整发送给验证者。

Sumcheck约束。第二个相似之处是，两个协议都会包括一个正在运行的Sumcheck实例。在 WHIR 或 Ligerito 的迭代中，验证者需要断言向量的随机线性组合已正确执行。验证者不是检查整个向量，而是执行抽样检查：它会打开随机位置并检查和是否在局部满足。由于与这些抽样检查相关的约束会验证和，因此两个协议都会自然地将此约束批量添加到正在运行的Sumcheck实例中。

如下一节所述，正在运行的 Sumcheck 实例也是这两个协议的一个不同点。

不同之处

WHIR 和 Ligerito 的主要区别在于它们所使用的编码。WHIR 仅针对 Reed-Solomon 码定义，而 Ligerito 则针对同一域上任意线性码序列定义。这种差异体现在运行 Sumcheck 实例的方式以及验证者复杂度上，我们将在下文中看到。

WHIR：可折叠码及码率提升。 WHIR 是为 Reed-Solomon 码定义的，并充分利用了其特性。首先，WHIR 利用了 RS 码“可折叠”的特性。这种码具有以下特点：

1. 一个码字可以分解成几个组成部分，每个部分都是一个较小 RS 码的码字，并且
2. 应用随机码字线性组合可以保持它们与相关 RS 码的距离。

这种“分裂和折叠”操作的存在使得问题规模能够递归减少。

其次，WHIR 采用了 STIR 中引入的码率提升技术的变体。虽然 WHIR 迭代将  个变量的问题简化为  个变量的问题，但证明者人为地扩大了 RS 码求值域的规模。这会导致码率降低，从而允许验证者在协议执行过程中进行更少的查询。为了确保此操作正确执行，验证者会请求一个域外样本，从而有效地将证明者绑定到一个唯一的多项式，无论它在哪个域上求值（或者用 RS 码的语言来说，一条唯一的消息）。最后，通过将新的约束批量添加到正在运行的 Sumcheck 中，来确保域外样本的有效性。

Ligerito：交错码和code switching。 相比之下，Ligerito 允许在不同的迭代之间使用不相关的码，并且不要求它们可折叠。

Ligerito 不使用可折叠码，而是使用交错码。根据定义，交织码  中的码字  是较小码  中  个码字  的集合。这会产生与性质1类似的效果： 可以分解为多个组成部分。各个部分 也可以通过随机线性组合，组合成  中的单个码字  。与折叠算子一样，此运算也保持距离（性质 2）。

Ligerito 验证者使用正在运行的 Sumcheck 实例来强制验证  确实是与  对应的唯一消息的线性组合的有效编码（参见 Ligerito 验证者算法第 4.1 ，第二点）。在这里，唯一性是通过运行多次查询来保证的，而不是像 WHIR 那样依赖于域外样本。

这种在迭代之间切换码并在协议本身内确保一致性的方法被称为code-switching。虽然论文中没有提到，但我发现从这个角度来理解 Ligerito 更容易。

为了确保code-switching的正确性，Ligerito 验证者必须对每个代码生成矩阵的几行进行随机求值。对于大小为 的初始向量和第一个折叠参数 （这意味着我们将初始向量拆分为  个组成部分），Ligerito 验证者无需证明者协助即可求值大小为  的多线性扩展。对于常数  ，此运算在初始多项式的大小上是渐近线性的，但严格意义上来说并不简洁。

• https://zkjargon.github.io/definitions/succinct.html

在论文的最新更新中，Guillermo 和 Andrija 证明，当求值点也具有结构时，某些多线性扩展可以在对数时间内计算出来。这并不完全令人惊讶：我们在基于  多项式的多线性协议中一直使用这种方法。他们进一步证明了 Reed-Solomon 码能够满足所需的性质。

比较

总结： WHIR 和 Ligerito 依赖于相同的核心元素。两者都通过递归地减少问题的规模（即自由变量的数量）来验证多线性多项式的性质。在减少规模的过程中，证明者和验证者会追踪正在运行的 Sumcheck 实例，该实例会对证明者的 IOP 消息施加额外的约束。

码。 在这两种情况下，约束都允许某种形式的code-switching：在 WHIR 中，我们从一个 RS 码切换到另一个定义在较小域上且速率较小的 RS 码；在 Ligerito 中，我们在任意线性码之间切换。从这个意义上讲，我们可以将 WHIR 和 Ligerito（以及 BaseFold 折叠那些熟悉的协议）视为来自同一家族的协议，其中 WHIR 使用 RS 码及其相关技巧，而 Ligerito 几乎完全是通用的。

验证者。 WHIR 中使用的码彼此紧密相关，这使得code-switching操作几乎可以免费进行。另一方面，Ligerito 验证者必须自行强制执行“正确编码”约束。虽然在一般情况下，此操作几乎是线性时间的，但在某些特殊情况下（例如 RS 码），它可以很简洁。在这两种情况下，我认为 Ligerito 验证者比 WHIR 验证者做了更多实际工作。

证明者。 正如我们所见，使用任意码都需要 Ligerito 验证者比 WHIR 验证者做更多的工作。另一方面，对编码的通用性意味着 Ligerito 与线性时间可编码码兼容，因此可以用线性时间证明者来实现。

证明大小。 两篇论文在使用 RS 码时，在其已验证的安全参数机制内，证明大小的数值相似。Ligerito 使用优化的折叠参数，而 WHIR 使用逐步递减的码率。由于 Ligerito 是为通用码定义的，因此它也可以像 WHIR 一样以逐步减小的码率进行实例化。同样，WHIR 也可以受益于 Ligerito 的折叠参数选择技术。主要区别在于 WHIR 可能在其码的唯一解码域之外工作，这应该可以实现更小的证明大小（以及更快的验证者）。

加餐：与 Blaze 的比较

既然我们提到了code-switching，我认为比较一下 Ligerito、WHIR 和 Blaze 也很有趣。Blaze 的初始版本类似于 Ligerito：使用较大的折叠因子和任意编码。然后，该协议进行code-switching，转换为 RS 码，并使用 BaseFold（或可选的 WHIR）继续执行。某种程度上，我们可以将 Blaze 视为 WHIR-Ligerito 谱上的混合协议，有可能在证明者-验证者权衡曲线上找到最佳平衡点。

• https://eprint.iacr.org/2024/1609

重要的是，Blaze 引入了一个简洁的 IOP 用于code-switching，以避免我们在 Ligerito 中看到的线性（近乎线性）验证者渐近复杂度。这是可能的，因为 Blaze 是针对具体编码描述的，而不是 Ligerito 的完整通用性。

感谢 Andrija Novakovic、Guillermo Angeris 和 Ron Rothblum 就该话题进行的许多启发性对话。