GKRFold：基于 SumFold 的 GKR 证明压缩

Ethereum Research

02-19

本文为机器翻译

展示原文

以下是文章的中文翻译:

辻见正人 (早稻田大学) (X: grandchildrice)

免责声明: 本文处于早期构想阶段,逻辑和数学公式可能并未完全严谨。我们欢迎任何对于这一想法本身的评论或反馈,以及关于逻辑结构的建议。

摘要

在本文中,我们介绍了GKRFold,一种用于压缩 n 个GKR基SNARK证明的证明大小和验证成本的协议。GKRFold采用了最初在NeutronNova[KS24]中提出的SumFold组件来实现这种压缩。最终,压缩过程产生了一个Sumcheck实例和一个承诺。因此,验证者只需执行一次Sumcheck和两次随机多项式评估。此外,该协议适用于GKR协议的统一和非统一实例。

1. 引言

1.1. GKR协议

GKR证明系统[GKR15,XZZ19]是一种著名的SNARK(简洁非交互式知识论证),因其高效的证明者时间而被用于诸如Expander和Ceno等系统。它的设计基于将每个电路层表示为相应的层多项式。从输出开始,该协议通过在随机选择的点上执行Sumcheck协议,将一层的声明顺序传递到下一层的声明。

更准确地说,层多项式(V_i)被定义为

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ add_{i+1}(z,x,y)\bigl(V_{i+1}(x)+V_{i+1}(y)\bigr) + mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr) \Bigr\},

Vi(z)=∑x,y∈{0,1}Si{addi+1(z,x,y)(Vi+1(x)+Vi+1(y))+multi+1(z,x,y)(Vi+1(x)⋅Vi+1(y))},

其中函数 add_i(z,x,y)addi(z,x,y) 和 mult_i(z,x,y)multi(z,x,y) 如果层 ii 中的门 (z,x,y)(z,x,y) 分别是加法或乘法门,则返回1,否则返回0。

GKR协议的概述如下:

证明者将电路评估 C(x,w)=yC(x,w)=y 发送给验证者。
对于每一层 i = 1,\dots,d-1i=1,…,d−1 (不包括输入层),验证者通过选择一个随机点 r_iri 发出挑战,然后在 V_i(r_i)Vi(ri) 上启动Sumcheck协议。
验证者直接评估输入层 V_d(r_d)Vd(rd)。

尽管证明者可以在 O(N)O(N) 时间内生成证明,而无需提交中间结果或依赖FFT,但验证时间和证明大小的复杂度仍为 O(D\log N)O(DlogN)。因此,实现高效的证明压缩仍然是一个重要的挑战。

1.2. NeutronNova和SumFold

正如在NeutronNova[KS24]中介绍的,SumFold是一种技术,它可以将任意数量的Sumcheck实例折叠成一个实例。通过将SumFold应用于GKR协议,可以压缩GKR证明中固有的多个Sumcheck实例,从而减少整体证明大小和验证时间。

1.3. 贡献

在这项工作中,我们提出了GKRFold,这是一种新的方法,它将SumFold应用于有效压缩nn个GKR证明。本研究的主要贡献如下:

我们证明了SumFold可以有效地用于压缩GKR实例,从而大大提高了证明大小和验证效率。
我们表明GKRFold可以压缩nn个GKR证明,每个证明包含dd层(总共6 \times n \times d6×n×d个Sumcheck实例),压缩为单个Sumcheck实例。

这一结果大大减少了验证多个GKR证明的开销,使该协议在需要简洁高效验证的应用中更加实用。

2. SumFold:高层次思想

这里省略了对MLE、Sumcheck和GKR的解释。如果想了解详细信息,请参考以下文档。

假设我们希望通过Sumcheck证明一个由组合定义的函数

F(\vec{g}(x)),

F(→g(x)),

其中FF是tt个变量的多项式,\vec{g}→g是tt个ll个变量的多项式向量。例如,可以考虑以下情况

F(\vec{g}(x)) = g_0(x) \cdot g_1(x) \cdots g_{t-1}(x),

F(→g(x))=g0(x)⋅g1(x)⋯gt−1(x),

它表示\vec{g}(x)→g(x)各个分量的乘积。

SumFold的目标是将nn个Sumcheck实例

[T_i = \sum_x F(\vec{g}(x))]_{i \in [n]}

[Ti=∑xF(→g(x))]i∈[n]

压缩为单个Sumcheck证明。

我们定义一个Sumcheck实例\mathsf{SC}SC,它包含Sumcheck证明所需的所有信息:

Screenshot from 2025-02-16 11-17-05

SumFold将nn个\mathsf{SC}SC实例折叠成一个。SumFold的主要思想包括以下步骤:

以下是文章内容的中文翻译:

对于所有 i = 1,\ldots,n, 给定
T_i = \sum_x F(\vec{g}_i(x)),
通过插值构造一个多项式 Q(b), 使得对于任意输入 b,
Q(b) = T_b.
这是通过以下方式实现的:
- (a) 通过多项式插值构造 t 个多项式 f_j(b,x), 其中每个多项式输出对应于第 $b$ 个实例的 g_{bj}(x)。
- (b) 通过将函数 F 应用于集合 \{f_1(b,x), \dots, f_t(b,x)\} 来重构 Q(b)。
提交多项式 Q(b)。这个承诺有效地聚合了所有 n 个 Sumcheck 实例的承诺。
验证者选择一个随机挑战 r_b 并将第 $r_b$ 个 Sumcheck 实例指定为折叠实例。

已验证 (参见 NeutronNova 论文[KS24]附录 B) 有

Q(r_b) = T_{r_b}.

协议 (引自[KS24]):

3. GKRFold

3.0. Linear GKR Protocol (Libra[XZZ19])

在本节中, 我们描述 GKR 协议的线性时间算法。首先, 假定给定以下层多项式:

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ add_{i+1}(z,x,y)\bigl(V_{i+1}(x)+V_{i+1}(y)\bigr) + mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr) \Bigr\}.

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} add_{i+1}(z,x,y)V_{i+1}(x) \;+\;

\sum_{x,y \in \{0,1\}^{S_i}} add_{i+1}(z,x,y)V_{i+1}(y) \;+\;

\sum_{x,y \in \{0,1\}^{S_i}} mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr).

For each term, a 2-phase Sumcheck protocol is executed. For instance, consider the third term:

\sum_{x \in \{0,1\}^{S_i}} h_{i+1}(x)V_{i+1}(x),

h_{i+1}(x) = ∑_{y ∈ {0,1}^{S_i}} mult_{i+1}(z,x,y)V_{i+1}(y).

2相检查协议如下进行:

通过Sumcheck证明h_{i+1}(x)的正确性。
通过Sumcheck证明∑_{x ∈ {0,1}^{S_i}} h_{i+1}(x)V_{i+1}(x)的正确性。

因此,对于每一层,总共执行6个Sumcheck实例。

3.1. GKRFold: 概述

假设我们有n个GKR实例,每个实例有d层。那么总共有n × d个层多项式。对于每一层,协议需要6个Sumcheck实例,总共有

6 × n × d

个Sumcheck实例。

这六种Sumcheck实例总结如下表所示:

来源

免责声明：以上内容仅为作者观点，不代表Followin的任何立场，不构成与Followin相关的任何投资建议。

喜欢