通过ℓ₂-范数检查实现更高效的格折叠

通过 ℓ₂ 范数检查实现更高效的格点折叠

通过用 Rok and Roll [KLNO25] 和 SALSAA [KLOT25] 中的 ℓ₂ 范数检查替换范围检查，来提高 LatticeFold+ [BC25b] 的效率。

简介

想象一下，你正在运行一个 Layer 2 区块链，每秒处理数千笔交易。当需要将这些交易转移到主链 (L1) 时，它们都需要一个加密证明来确保有效性。传统的方法是什么？一次性为所有交易生成一个巨大的证明，但这需要将所有内容都保存在内存中，这很快变得不切实际。此外，证明者只有在收到所有交易后才能开始生成证明。如果可以逐步将实例“折叠”在一起，将两个实例组合为一个，然后将结果与另一个实例折叠，以此类推呢？这就是折叠方案的魔力。

折叠方案是一种密码学协议，可将多个问题实例压缩为更少的实例。可以将其想象成折叠一张纸：每次折叠都会使其更小更紧凑，但是纸仍然存在，没有任何东西丢失。

在实际应用中，增量处理证明（而无需一次性加载所有内容到内存中）对于可扩展性和并行化至关重要 - 无论是证明跨链传输的正确执行，验证对敏感数据上的机器学习模型训练，验证用于防止篡改的媒体内容，还是演示用于延迟函数中的计算工作。

传统的 SNARKs (简洁的非交互式知识论证) 产生非常简短的证明，但是它们要求证明者一次性处理整个计算。如果你正在流式传输数据（例如，随着区块链交易到达时对其进行处理），则需要存储所有内容，直到准备好进行证明。这既昂贵又缓慢。

折叠方案通过允许增量证明来解决此问题：将两个实例折叠在一起，将结果与另一个实例折叠，然后继续进行。在每个步骤中，你只需要记住恒定数量的状态。你甚至可以将验证本身折叠到计算中，从而创建所谓的增量可验证计算 (IVC)，即递归验证自身的证明。

基于格点的折叠

Boneh & Chen [BC25b] 和其他人的最新工作表明，基于格点的密码学特别适合于折叠方案。格点提供了两个关键优势：

1. 抗量子安全性：与许多当前系统不同，人们认为它们可以抵抗来自量子计算机的攻击
2. 效率：通过正确的技能，它们可以非常快

但是，这里有一个问题。所有当前的格点折叠方案都依赖于范围检查（技术上是 $\ell_∞$ 范数检查），以确保数字在折叠过程中不会变得太大。这些范围检查在计算上很昂贵，并且是瓶颈。

我们的贡献

在这篇博文中，我们将展示如何用更有效的 $\ell_2$ 范数检查来替换昂贵的范围检查，这些检查的灵感来自 Rok和 Roll [KLNO25] 的技术。尽管我们专注于改进 Boneh & Chen 的 LatticeFold+ [BC25b]，但这些技术具有通用性，并且可以使其他基于格点的折叠方案受益。

更具体地说？更快的证明者，相同的安全保证，以及使后量子折叠方案在实际应用中可行的步骤。

此处探讨的想法应被视为 [BC25a] 和 [BC25b] 框架的扩展，并具有来自 [KLNO25] 和 [KLOT25] 的更有效的范数检查。

现在，让我们深入研究技术细节。不用担心，我们将逐步构建概念。

符号

我们用 [n] 表示集合 {0,1,…,n−1}。在整篇文章中，我们使用粗体字母来表示向量和矩阵，它们分别用小写字母和大写字母表示。我们假设向量是列向量。我们写成 ||⋅|| 来表示向量的范数，其中具体的范数（例如 $\ell_∞$ 或 $\ell_2$）在需要时会明确指定。对于向量的串联，我们使用符号 [a||b] 来表示向量 a 和 b 的串联。

我们使用 $\mathcal{R}_q$ 来表示整数多项式的环，模为 $X^N+1$，系数在 $\mathbb{Z}_q$ 中，对于某个整数模数 $q$ 和次数 $N=2^k$。为了简单起见，可以将 $\mathcal{R}_q=\mathbb{Z}_q$（即 $N=1$）设置为获得标准整数向量，这主要足以用于我们的讨论。我们使用符号 ⊗ 来表示 Kronecker 积，⊙ 来表示 Hadamard 积。

给定一个向量 $\mathbf{v} \in \mathcal{R}_q^{2^\mu}$，它的多线性扩展定义为唯一的多线性多项式 $\text{MLE}\mathbf{v}$，使得对于每个 $\mathbf{b} \in {0,1}^\mu$，$\text{MLE}\mathbf{v}=v_\mathbf{b}$。如果向量具有结构化的形式，即它是低维向量的乘积，则可以有效地计算其多线性扩展。我们写成 $\mathcal{R}_q^{2^{\otimes \mu}}$ 来表示向量 $\mathbf{v} \in \mathcal{R}_q^{2^\mu}$ 的集合，使得对于某些向量 $\mathbf{v}_i \in \mathcal{R}_q^2$，$\mathbf{v}=\mathbf{v}_0 \otimes \mathbf{v}1 \otimes \cdots \otimes \mathbf{v}{\mu-1}$。

我们将广义 (NP) 关系 $\Xi$ 定义为一个三元组：

$\Xi := (\mathsf{pp, stmt, wtn}) \in \mathcal{P} \times \mathcal{S} \times \mathcal{W}$

因此，$\mathsf{pp}$ 是公共参数（在协议的执行过程中固定），$\mathsf{stmt}$ 是语句，$\mathsf{wtn}$ 是见证。如果谓词 $R_\Xi: \mathcal{P} \times \mathcal{S} \times \mathcal{W} \rightarrow {0,1}$ 的值为 1，则该关系成立，并写成 $(\mathsf{stmt, wtn}) \in \Xi$ 来表示实例-见证对是有效的。

一个特别感兴趣的关系是 Rank-1 约束系统 (R1CS)。R1CS 是在 SNARKs 和折叠方案中广泛使用的关系，因为许多 NP 语句（包括算术电路的评估）可以有效地简化为 R1CS。

$$ \Xi^{\mathsf{R1CS}} := \left. \begin{cases} \mathbf{(A,B,C),-,w} \ \overline{\mathbf{(A,B,C)} \in \mathcal{R}^{n \times n}_q }, \mathsf{w} \in \mathcal{R}^n_q \ \mathbf{Aw} \odot \mathbf{Bw} = \mathbf{Cw}\ \text{mod} \ q, \end{cases} \right} $$

我们注意到，为了简单起见，这里和 [BC25b] 中也考虑了这种算术化，但是通过一些通用修改（如 [BC25a] 中所示），我们准备将我们的构造扩展为支持更高级的算术化，例如可定制约束系统 [STW23]，它进一步推广了其他算术化，如 AIR 或 Plonkish。

Boneh & Chen 的基于格点的折叠方案框架

知识约简

非正式地，知识约简是一种交互式算法（在证明者和验证者之间），它获取一个关系的实例并生成另一个关系（可能不同）的实例。我们写成 $\Pi: \Xi_0 \rightarrow \Xi_1$ 来表示从关系 $\Xi_0$ 到关系 $\Xi_1$ 的约简。

我们说知识约简是正确的（完美地或静态地），如果对于每个有效的实例-见证对 $(\mathsf{stmt_0, wtn_0)} \in \Xi_0$，输出的实例-见证对 $(\mathsf{stmt_1, wtn_1}) = \Pi(\mathsf{stmt_0, wtn_0})$ 也是有效的，即 $(\mathsf{stmt_1, wtn_1}) \in \Xi_1$。

我们还说，知识约简是知识可靠的，如果对于每个语句 $\mathsf{stmt_0} \in \Xi_0$ 和对于输出实例 $(\mathsf{stmt_1, wtn_1}) = \Pi( \mathsf{stmt_0, wtn_0} )$ 的每个有效见证 $\mathsf{wtn_1}$，都存在一种有效的提取器算法，可以提取输入实例 $\mathsf{stmt_0}$ 的有效见证 $\mathsf{wtn_0}$。提取器允许使用相同的输入实例 $\mathsf{stmt_0}$ 但不同的随机性多次重新运行证明者算法。

LatticeFold+ [BC25b] 框架由知识约简的组成构成。

广义的承诺线性关系

在继续描述折叠方案之前，我们还定义了广义的承诺线性关系的概念，这将在构造中很有用。

$$ \Xi_{\beta}^{lin} := \left. \begin{cases} \underline{ (\mathbf{A},(\mathbf{M}i){i \in [t]}) , (y,(vi){i \in [t]} ,\mathbf{r}) , \mathbf{w} } \ \mathbf{A} \in \mathcal{R}_q^{n \times m} , \mathbf{M}_i \in \mathcal{R}_q^{n \times m}, \ \mathbf{y} \in \mathcal{R}_q^a , v_i \in \mathcal{R}_q ,\mathbf{r} \in \mathcal{R}_q^{2 \otimes \mu , }\ \mathbf{w} \in \mathcal{R}_q^m , \ \begin{pmatrix} \mathbf{A }\ \mathbf{r^T M0} \ \vdots \ \mathbf{r^T M{t-1}} \end{pmatrix} \mathbf{w} = \begin{pmatrix} \mathbf{y} \ v0 \ \vdots \ v{t-1} \end{pmatrix} \mod q, \ |\mathbf{w}| \leq \beta }. \end{cases} \right} $$

换句话说，公共参数由一个矩阵 $\mathbf{A}$ 组成，这应被视为 Ajtai 型承诺（在短整数解问题的环变体下绑定）和一组矩阵的集合 $(\mathbf{M}i){i \in [t]}$，这些矩阵对见证形成额外的约束。语句由向量 $\mathbf{y}$ 和 $(vi){i \in [t]}$ 组成，形成线性系统的右侧。此外，矩阵 $(\mathbf{M}i){i \in [t]}$ 通过向量 $\mathbf{r}$ “批量处理”，以便右侧保持简洁表示。要求见证 $\mathbf{w}$ 满足线性系统，并且还需为短范数（在 [BC25b] 的上下文中，使用 $ℓ_∞$ 范数）。

R1CS 关系的折叠方案

最终，我们准备描述折叠方案。

R1CS 关系的折叠方案通过两个主要成分获得：

• 从 R1CS 关系到广义的承诺线性关系的线性化约简；以及

• 广义的承诺线性关系的折叠方案。

后者又通过以下知识约简的组成获得：

• 范数检查约简，其在见证的范数上形成一个“检查点”，以便提取的见证具有正确的范数。

• 同质化，其统一了关系的左侧 (即，所有实例都使用相同的向量 $r$)。

  • 见证和右侧的随机线性组合，以将实例数从 $L$ 减少到 1。

  • 分解，通过将见证分成两个部分来减小见证的范数，形成线性关系的两个新实例。

这一复杂的约简序列的目标是获得一个折叠方案，其将实例数从 $L$ 减少到 2，同时保持见证的范数受控。更详细地，我们期望在折叠期间（即，在正确性方向上）和在提取期间（即，在知识可靠性方向上），见证的范数不会增长。此限制非常重要，否则，在几个折叠步骤之后，见证的范数将变得太大，以至于 Ajtai 式承诺无法保持绑定。

在正确性方向上，见证的范数在组合步骤中增长，但通过分解步骤将其减少回来。在知识可靠性方向上，见证的范数在分解步骤中增长。在折叠步骤中，见证的范数不仅增长，而且见证还会增加一个“短分母”（也称为松弛）。这种关系通常表示为松弛，仍然具有相当大的参数降级。需要控制这种范数的临时增长，这是通过范数检查步骤实现的。范数检查步骤确保提取的见证的范数与原始见证的范数完全相同。

范数检查约简

范数检查约简是从广义的承诺线性关系到其自身的一种知识约简。此约简用作见证范数的“检查点”。在提取方向上，它确保提取的见证与原始见证具有相同的范数。

简而言之，此约简的工作方式如下：输入关系的见证被分解为单项式，即，对于每个见证 $\mathbf{w} \in \mathcal{R}_q^m$，我们写成 $\mathbf{w} = \sumj \mathbf{w}^{(j)} X^j$。然后，证明者通过 Ajtai 式承诺来承诺每个单项式向量，并证明承诺的单项式与原始见证之间的一致性。因此，由于多项式的次数是有界的，证明者声明原始见证的范数通过 $ℓ∞$ 范数来限制。

为了节省通信量，证明者不会发送所有单项式的承诺，而是采用“双重承诺”技术。尽管如此，计算开销仍然很大。为了计算所有单项式的承诺，证明者需要执行 $L \cdot n \cdot m \cdot N \cdot \log_N \beta$ 次分圆环元素的加法，其中 $L$ 是实例数，$n \times m$ 是承诺矩阵的维度，$N$ 是环的次数。在实践中，此开销可能过高。

同质化约简

同质化约简是从广义的承诺线性关系到其自身的一种知识约简。此约简确保所有实例中关系的左侧是统一的，即，所有实例的向量 $\mathbf{r}$ 相同。

证明者和验证者用 sumcheck 声明来表达所有线性关系，即，对于每个实例 $j \in [L]$，它们将关系表示为 $\sum_{b \in {0,1}^\mu} \mathsf{MLE}r_i \cdot \mathsf{MLE}\mathbf{M}_i \mathbf{w}_j = y_{i,j}$

对于每个 $i \in [t]$。然后，证明者和验证者参与一个 sumcheck 协议（批量处理所有声明），以将声明减少为单个随机点 $r^* \in R_q^\mu$，获得以下一组方程式：

$\mathsf{MLE}\mathbf{M}_i \mathbf{w}_j = y_{i,j}^*,\ \ \ \ \forall i \in [t], j \in [L]$

其中 $y_{i,j}^*$ 是原始右侧的适当定义的线性组合。这些可以以矩阵-向量形式表示为：

$\mathbf{r}^ \mathbf{M}_i \mathbf{w}j = y{i,j}^,\ \ \ \ \ \forall i \in [t], j \in [L]$.

因此，新的关系在所有实例中具有统一的左侧 $\mathbf{r}^$。验证者直接验证对 $\mathsf{MLE}[r_i](r^)$ 的声明。

用 𝓁₂-范数检查替换范围检查

为了减轻范数检查约简的开销，我们建议用更有效的 $ℓ2$ 范数检查替换 $ℓ∞$ 范数检查。

Johnson-Lindenstrauss 引理

Johnson-Lindenstrauss 引理指出，可以使用随机矩阵将高维空间中的一小部分点嵌入到低维空间中，以便几乎保留点之间的距离。密码学家喜欢该引理的更简单的公式，该公式更适合我们的目的。以下 [BS23]，我们声明该引理如下：

引理 4.1（推论 3.2，[GHL21]），推论 4.2 [BS23]。

设 $C$ 为 ${-1,0,1}$ 上的分布，其中 $\Pr[C=0]=1/2$，且 $\Pr[C=1]=\Pr[C=-1]=1/4$, 那么对于每个向量 $\mathbf{w} \in \mathbb{Z}^d$，我们有

$30 |\mathbf{w}|_2 < |\Pi \mathbf{w} \mod q|_2 < 337 |\mathbf{w}|_2$.

除非在分布 $\Pi \leftarrow C^{256 \times d}$ 上的概率为 $2^{-128}$。

换句话说，此引理指出，通过使用具有来自指定分布的条目的随机矩阵将高维向量投影到低维空间上，我们可以确保投影向量的 ℓ2 范数集中在原始向量的 ℓ2 范数附近，并按某些因子缩放，且概率极高。

尝试 I：[BS23] 型 𝓁₂-范数检查

我们首先考虑从 [BS23] 中直接改编范数检查约简，该约简采用 Johnson-Lindenstrauss 引理来执行 $ℓ_2$ 范数检查。

我们考虑从广义的承诺线性关系到具有附加约束的类似关系的以下知识约简：

• 验证者从引理 4.1 中指定的分布中采样一个随机矩阵 $\Pi \leftarrow C^{256 \times m}$。我们通过将每个条目嵌入为常量多项式来隐式地将矩阵 $\Pi$ 从整数提升为分圆环元素。
• 证明者计算每个实例 $j \in [L]$ 的投影见证 $v_j = \Pi w_j \mod q$ 并将其发送给验证者。
• 验证者检查投影见证是否满足范数约束。验证者向证明者发送一个质疑 $c \in R_q^{256}$。
• 稍后，在同质化步骤中，证明者和验证者都将关系表示为每个实例 $j \in [L]$ 的 sumcheck 声明：

$\sum_{b \in {0,1}^\mu} \text{MLE}c^T \Pi \cdot \text{MLE}w_j = c^T v_j \mod q$. 这些关系以与之前类似的方式进行同质化。此方法存在两个主要缺点：

• 验证者需要采样一个新的随机矩阵 $\Pi$，并在同质化步骤期间进一步计算 $\text{MLE}c^T \Pi$ 的评估。这为验证者带来了显着的开销，现在验证者中见证的维度 $m$ 是线性的，并且通常是禁止的。
• 提取保证被削弱。尽管 Johnson-Lindenstrauss 引理确保在极高的概率下，投影见证的范数集中在原始见证的范数附近，但该界限仅保持到一个(非常小的)常数因子。这意味着在提取过程中，提取的见证的范数可能比原始见证大一个常数因子。在多个折叠步骤中重复应用此约简可能导致见证范数的无限增长，最终破坏承诺的绑定属性。

尝试 II：[KLNO25] 型 𝓁₂-范数检查

为了解决先前方法中发现的问题，我们提出了一种替代的 ℓ2 范数检查约简，该约简的灵感来自 [KLNO25] 中的技术。

这个想法非常简单：使用多个投影（共享随机性）而不是使用单个投影矩阵来投影见证。换句话说，我们将见证投影到小块中，以便每个块都独立投影。然后，证明者承诺所有投影块而不是发送单个投影见证。更详细地，我们考虑从广义的承诺线性关系到类似关系的以下知识约简：

假设 $L=2^e$ 是 2 的幂，令 $b=256 \cdot L$ 为块大小。

• 验证者从引理 4.1 中指定的分布中采样一个随机矩阵 $\Pi \leftarrow C^{256 \times b}$，其中 $b$ 是块大小。我们通过将每个条目嵌入为常量多项式来隐式地将矩阵 $\Pi$ 从整数提升为分圆环元素。
• 证明者将见证 $w \in R_q^m$ 分成大小为 $b$ 的 $m/b$ 个块，即 $w_j = [w_j^{(0)} | w_j^{(1)} | \cdots | w_j^{(m/b-1)}]$。证明者计算每个块的投影块 $v_j^{(i)} = \Pi w_j^{(i)} \mod q$。它将投影块组合成一个向量 $v_j = [v_j^{(0)} | v_j^{(1)} | \cdots | v_j^{(m/b-1)}]$，并且进一步 $v = [v_0 | v1 | \cdots | v{L-1}]$。证明者承诺该向量 $v$ 并将承诺发送给验证者。
• 验证者向证明者发送一个质疑 $c \in R_q^{\mu \otimes \mu}$，该质疑被分成 $c^{(0)} \in R_q^{2^{\otimes \mu-e}}$ 和 $c^{(1)} \in R_q^{2^{\otimes e}}$，使得 $c = c^{(0)} \otimes c^{(1)}$。
• 证明者发送 $s \in R_q$ 和 $t \in R_q^L$，以便

$c1^T (I{m/b} \otimes \Pi) w_j = t_j \mod q$ $(c_0^T \otimes c_1) v = s \mod q$

• 验证者检查 $\sum{j \in [L]} c{0,j} t_j = s$。
• 稍后，在同质化步骤中，证明者和验证者都将关系表示为每个实例 $j \in [L]$ 的 sumcheck 声明，其中 $t_j$ 是适当定义的右侧：

$\sum_{b \in {0,1}^\mu} \text{MLE}c1 (I{m/b} \otimes \Pi) \cdot \text{MLE}w_j = tj \mod q$. $\sum{b \in {0,1}^\mu} \text{MLE}c_0 \otimes c_1 \cdot \text{MLE}v = s \mod q$. 我们进一步修改协议。为了在提取中使用新附加的见证 $v$，我们需要确保此图像是低范数的。如果不是这种情况，则提取可能无法提取原始关系的有效见证。换句话说，与 $v$ 对应的关系不得是松弛的。为了实现此目的，我们考虑一种略有不同的折叠变体，该变体不涉及投影见证。因此，折叠步骤仅随机组合 $L+1$ 个实例中的 $L$ 个，而保留与 $v$ 对应的关系不动。这样，在提取期间，投影见证 $v$ 可以在没有任何松弛的情况下提供给提取器，并且提取器可以使用它来恢复原始见证 $w$。

现在，折叠的输出是一对两个实例：第一个实例对应于随机组合的 $L$ 个实例，而第二个实例对应于 $v$ 的关系。分解后，这些进一步分成两个实例，总共获得四个实例，作为下一个折叠步骤的累加器。

所建议的协议具有更好的效率，但是它使提取保证仍然(稍微)处于开放状态。实际上，我们设法将提取的见证的范数从松弛“升级”到几乎与原始见证的范数相同。但是，所提出的投影技术仍然在原始见证的范数和提取的见证之间留下了小的常数因子差距。在多个折叠步骤中重复应用此约简可能导致见证范数的无限增长，最终破坏承诺的绑定属性。

最终尝试：从“较短”见证到“短”见证

为了完全弥合提取保证差距，我们建议将 ℓ2 范数检查与最终的“缩短”步骤结合起来，该步骤将“较短”的见证转换为“短”的见证。这个想法最初已在 [KLOT25] 中在 SNARK 和折叠方案的上下文中进行了研究，但是对于低范数线性关系可满足性的限制性设置。

这次，我们利用了见证已经知道是“较短”的事实，即它的 ℓ2 范数以 $\alpha \beta$ 为界，其中 $\beta$ 是原始的见证范数，$\alpha$ 是折叠过程中范数增加的因子。

我们做以下观察，向量的 ℓ2 范数与向量与其自身的内积密切相关。更详细地，我们写成 $|w|_2^2 = \text{ct}(\langle w, \overline{w} \rangle) \mod q$, 其中 $\overline{w}$ 是 $w$ 的逐坐标复共轭。在 power-of-two 分圆环的情况下，复共轭对应于自同构 $X \mapsto -X^{N-1}$。有关更多详细信息，请参阅 [KLNO24]。我们写成 $\text{ct}: R_q \rightarrow Z_q$ 来表示分圆环元素的常数项。我们注意到，由于 $|w|_2^2$ 已经知道很小（即小于 $\alpha^2 \beta^2$），因此对于足够大的模数，上面的等式在整数上成立（即，没有 $\mod q$）。

因此，为了确保见证完全具有所需的范数，足以证明 $\text{ct}(\langle w, \overline{w} \rangle) \leq \beta^2$。

为了实现此目的，我们考虑从广义的承诺线性关系到具有附加约束的类似关系的以下知识约简：

• 证明者计算每个 $j \in [L]$ 的内积 $u_j = \langle w_j, \overline{w_j} \rangle$ 并将其发送给验证者。
• 验证者检查每个 $j \in [L]$ 的 $\text{ct}(u_j) \leq \beta^2$。
• 证明者和验证者将关系表示为每个实例 $j \in [L]$ 的 sumcheck 声明，其中 $u_j$ 是右侧：

$\sum_{b \in {0,1}^\mu} \text{MLE}w \cdot \text{MLE}\overline{w} = u_j \mod q$.

• 证明者和验证者参与一个 sumcheck 协议，并将声明减少为单个随机点 $r^* \in R_q^\mu$，获得以下一组方程式：

$\text{MLE}w_j \cdot \text{MLE}\overline{w_j} = u_j^* \mod q, \forall j \in [L]$.

• 证明者将方程式分成两个线性方程式，并发送 $u_j'$ 和 $u_j''$，以便对于每个 $j \in [L]$：

$\text{MLE}w_j = u_j' \mod q$ $\overline{\text{MLE}w_j} = \text{MLE}\overline{w_j} = u_j'' \mod q$.

• 验证者检查每个 $j \in [L]$ 的 $u_j' \cdot \overline{u_j''} = u_j^*$。
• 稍后，在同质化步骤中，证明者和验证者都将关系表示为每个实例 $j \in [L]$ 的 sumcheck 声明，并以与之前类似的方式将它们与其他关系组合在一起。

上述约简确保在提取期间，当提取的见证已经保证为短时，提取的见证与原始见证完全具有相同的范数。因此，通过将这个约简与基于 Johnson-Lindenstrauss 的 ℓ2 范数检查结合起来，我们可以获得具有精确提取保证的完整 ℓ2 范数检查约简。

具体参数和效率

从效率的角度来看，所提出的 ℓ2 范数检查减少方法，从证明者的角度来看，比 [BC25b] 中的原始 ℓ∞ 范数检查方法效率更高。原因是现在“繁重的步骤”是 Johnson-Lindenstrauss 投影的计算，这“仅仅”需要 $L \cdot m \cdot 256$ 次环元素的加法，这比 [BC25b] 中的单项式承诺在数量级上更有效，其中加法的次数为 $L \cdot n \cdot m \cdot N \cdot \log_N \beta$（对于具体参数，$n$ 通常设置为 $\log m / \log \lambda$）。此外，这些加法是在低范数元素上执行的。因此，这些加法在没有模约简的情况下发生，并且由于系数的短比特长度可以有效地向量化。

对于以下参数，已估算了证明大小：$L=8$, $q=2^{64}$, $N=128$, $m=2^{20}$, $B=2^{25}$ 和 $n=12$。对于这些参数，证明大小估计约为 175 KB。 这些设置几乎与来自 [BC25b] 的设置相匹配，除了更小的模数 $q$ 和更大的范数设置（因为我们使用 ℓ2 范数）。此外，在 [BC25b] 中，实例数 $L$ 设置为 3，这对应于累加器的两个实例和新关系的实例。在这里，我们将 $L$ 设置为 8，因为我们有累加器的 4 个实例，并且我们假设新关系的 4 个实例，这更方便，因为现在 $L$ 是 2 的幂。在调整 $L=5$ 参数以匹配来自 [BC25b] 的参数（累加器的 4 个实例和新关系的 1 个实例）后，我们获得的证明大小约为 110 KB，这与 [BC25b] 中的证明大小相匹配。

警告

在本博客文章中，为了便于阐述，我们省略了一些关于精确参数选择和安全分析的细节。

1. 我们忽略了并集界对证明可靠性的影响，即我们没有考虑在多个 folding 步骤中应用 Johnson-Lindenstrauss 引理的次数。这可以通过相应地调整引理的参数来轻松解决，这可能会导致证明大小的略微增加。[KLNO25] 中提供了仔细的分析。
2. 对于效率分析，我们仅考虑了证明者计算的主要项，即 Johnson-Lindenstrauss 投影的计算。 实际上，其他步骤，主要是同质化，也可能对整体计算做出重大贡献。同质化的复杂度是 $O(L \cdot m)$ 个环元素乘法，其中 $O(\cdot)$ 符号隐藏了一个小的常数因子（实际上，它应该在 6 左右）。此外，乘法（涉及模约简）比加法贵约 5 倍（在我们特定的参数体系中）。此外，我们没有利用同质化期间元素的 shortness（即小系数），就像我们在 Johnson-Lindenstrauss 投影期间所做的那样。总的来说，同质化可能贡献约 30-40% 的整体证明者计算。这些估计是粗略的，我们将更仔细的分析留给未来的工作。
3. 我们将讨论限制在分圆环是 2 的幂的分圆环的情况。这个假设简化了对复共轭和自同构的讨论。但是，这些技术可以扩展到一般分圆环，但需要一些额外的技术开销。
4. 我们将讨论限制为 R1CS 关系的环变体。但是，这些技术可以扩展到 R1CS 关系的域变体，但需要一些额外的技术开销，如 [NS24] 所示。此外，在正交的意义上，这些技术可以扩展到其他关系，例如 CCS 关系，如 [BC25a] 所示。

致谢

我感谢 Binyi Chen（斯坦福大学）、Russell W. F. Lai（阿尔托大学）和 David Balbás (IOHK) 对本博客文章早期版本的评论。

参考文献

• [BS23] W. Beullens, G. Seiler; LaBRADOR: Compact Proofs for R1CS from Module-SIS; Eurocrypt 2023.
• [BC25a] D. Boneh, B. Chen; LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems; Asiacrypt 2025.
• [BC25b] D. Boneh, B. Chen; LatticeFold+: LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems; Crypto 2025.
• [GHL21] C. Gentry, S. Halevi, V. Lyubashevsky; Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties; Eurocrypt 2022.
• [KLNO24] M. Klooß, R. W. F. Lai, N. K. Nguyen, M. Osadnik; RoK, Paper, SISsors - Toolkit for Lattice-based Succinct Arguments; Asiacrypt 2024.
• [KLNO25] M. Klooß, R. W. F. Lai, N. K. Nguyen, M. Osadnik; RoK and Roll - Verifier-Efficient Random Projection for O~(λ)-size Lattice Arguments; Asiacrypt 2025.
• [KLOT25] S. Kuriyama, R. W. F. Lai, M. Osadnik, L. Tucci; SALSAA - Sumcheck-Aided Lattice-based Succinct Arguments and Application.
• [NS24] W. Nguyen, S. Setty; Neo: Lattice-based folding scheme for CCS over small fields and pay-per-bit commitments.
• [STW23] S. Setty, J. Thaler, R. Wahby; Customizable constraint systems for succinct arguments

• 原文链接： osdnk.me/blog/l2-folding...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～