通过将 Rok and Roll [KLNO25] 和 SALSAA [KLOT25] 中的 $\ell_2$-范数检查替代范围检查，提升 LatticeFold+ [BC25b] 的效率。 原文：https://www.osdnk.me/blog/l2-folding-scheme

作者：Michał Osadnik

译者：Kurt Pan

引言

设想你正在运行一个 Layer 2 区块链，每秒处理数千笔交易。当需要将这些交易转移到主链（L1）时，它们都需要一个密码学证明来确保其有效性。传统方法是什么？一次性为所有交易生成一个巨大的证明，但这需要将所有内容保存在内存中，这很快就变得不切实际。此外，证明者只能在收到所有交易后才能开始生成证明。如果你可以增量式地"折叠"实例，将两个实例合并为一个，然后将该结果与另一个实例折叠，依此类推，那会怎样？这就是折叠方案的魔力所在。

折叠方案 是一种将多个问题实例压缩为更少实例的密码学协议。把它想象成折纸：每次折叠都使它变得更小更紧凑，但纸张仍然存在，什么都没有丢失。

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

传统的 SNARK （简洁非交互式知识论证）产生极短的证明，但它们要求证明者一次性处理整个计算。如果你正在流式处理数据——比如，处理到达的区块链交易——你需要存储所有内容直到准备好证明。这既昂贵又缓慢。

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

基于格的折叠

Boneh & Chen [BC25b] 等人最近的工作表明，基于格的密码学特别适合折叠方案。格提供两个关键优势：后量子安全性（与许多当前系统不同，它们被认为能够抵抗量子计算机的攻击）和效率（使用正确的技术，它们可以出奇地快）。

然而，有一个问题。所有当前的格折叠方案都依赖于范围检查（技术上说是 $\ell_\infty$-范数检查）来确保数在折叠过程中不会增长过大。这些范围检查计算成本高昂，它们是瓶颈所在。

我们的贡献

在这篇博文中，我们展示如何用更高效的 $\ell_2$-范数检查替代昂贵的范围检查，这受到了 Rok and Roll [KLNO25] 技术的启发。虽然我们专注于改进 Boneh & Chen 的 LatticeFold+ [BC25b]，但这些技术是通用的，可以使其他基于格的折叠方案受益。

更具体地说？更快的证明者、相同的安全保证，以及使后量子折叠方案适用于实际应用迈出的一步。

这里探索的想法应被视为对 [BC25a] 和 [BC25b] 框架的扩展，结合了 [KLNO25] 和 [KLOT25] 中更高效的范数检查。

现在，让我们深入技术细节。别担心，我们会逐步构建这些概念。

符号

我们用 $[n]$ 表示集合 $\{0, 1, \ldots, n-1\}$。在整篇文章中，我们使用粗体字母表示向量和矩阵，分别用小写和大写字母进一步表示。我们假设向量是列向量。我们用 $||\cdot||$ 表示向量的范数，具体范数（如 $\ell_\infty$ 或 $\ell_2$）在需要时会明确指定。对于向量的拼接，我们使用符号 $[\mathbf{a} || \mathbf{b}]$ 表示向量 $\mathbf{a}$ 和 $\mathbf{b}$ 的拼接。

我们用 $\mathcal{R}_q$ 表示模 $X^N + 1$ 的整系数多项式环，系数在 $\mathbb{Z}_q$ 中，其中 $q$ 是某个整数模数，$N = 2^k$ 是次数。为简单起见，可以设 $\mathcal{R}_q = \mathbb{Z}_q$（即 $N = 1$）以获得标准整数向量，这对我们的讨论基本足够。我们用符号 $\otimes$ 表示克罗内克积，用 $\odot$ 表示哈达玛积。

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

我们将一般（NP）关系 $\Xi$ 定义为三元组：

$$ \Xi := (\mathsf{pp}, \mathsf{stmt}, \mathsf{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} \to \{0,1\}$ 求值为 1，则关系成立，我们用 $(\mathsf{stmt}, \mathsf{wtn}) \in \Xi$ 表示实例-见证对是有效的。

一个特别感兴趣的关系是秩-1约束系统（R1CS）。R1CS 是 SNARK 和折叠方案中广泛使用的关系，因为许多 NP 陈述（包括算术电路的求值）可以高效地归约到 R1CS。

$$ \Xi^{\mathsf{R1CS}} := \left{ \begin{aligned} &\underline{(\mathbf{A}, \mathbf{B}, \mathbf{C}), - , \mathbf{w}} \ &\mathbf{A}, \mathbf{B}, \mathbf{C} \in \mathcal{R}_q^{n \times n}, \quad \mathbf{w} \in \mathcal{R}_q^{n} \ &\quad \mathbf{A} \mathbf{w} \odot \mathbf{B} \mathbf{w} = \mathbf{C} \mathbf{w} \bmod q, \end{aligned} \right} $$

我们注意到，这种算术化在这里以及在 [BC25b] 中为了阐述的简洁性而被考虑，但通过一些通用修改（如 [BC25a] 中所述），我们可以将我们的构造扩展到支持更高级的算术化，例如可定制约束系统 [STW23]，它进一步推广了 AIR 或 Plonkish 等其他算术化。

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

知识归约

非形式化地说，知识归约是一种交互式算法（在证明者和验证者之间），它接受一个关系的实例并产生另一个（可能不同的）关系的实例。我们用 $\Pi: \Xi_0 \rightarrow \Xi_1$ 表示从关系 $\Xi_0$ 到关系 $\Xi_1$ 的归约。

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

如果对于每个陈述 $\mathsf{stmt}_0 \in \Xi_0$ 和输出实例 $(\mathsf{stmt}_1, \mathsf{wtn}_1) = \Pi(\mathsf{stmt}_0, \mathsf{wtn}_0)$ 的每个有效见证 $\mathsf{wtn}_1$，存在一个高效的提取器算法可以为输入实例 $\mathsf{stmt}_0$ 提取有效见证 $\mathsf{wtn}_0$，则我们也说知识归约是知识可靠的。允许提取器使用相同的输入实例 $\mathsf{stmt}_0$ 但不同的随机性多次重新运行证明者算法。

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

广义承诺线性关系

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

$$ \Xi^{\mathsf{lin}}_\beta := \left{ \begin{aligned} &\underline{(\mathbf{A}, (\mathbf{M}i){i \in [t]}), (\mathbf{y}, (vi){i \in [t]}, \mathbf{r}), \mathbf{w}} \ &\quad \mathbf{A} \in \mathcal{R}_q^{n \times m}, \quad \mathbf{M}_i \in \mathcal{R}_q^{n \times m}, \ &\quad \mathbf{y} \in \mathcal{R}_q^{a}, \quad v_i \in \mathcal{R}_q, \quad \mathbf{r} \in \mathcal{R}_q^{2^{\otimes \mu}}, \ &\quad \mathbf{w} \in \mathcal{R}_q^{m}, \ \ &\quad \begin{pmatrix} \mathbf{A} \ \mathbf{r}^{\mathtt{T}}\mathbf{M}0 \ \vdots \ \mathbf{r}^{\mathtt{T}}\mathbf{M}{t-1} \end{pmatrix} \mathbf{w}

\begin{pmatrix}
    \mathbf{y} \\
    v_0 \\
    \vdots \\
    v_{t-1}
\end{pmatrix}
\bmod q,
\\
\\
&\quad \|\mathbf{w}\| \leq \beta

\end{aligned} \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] 的上下文中，使用 $\ell_\infty$-范数）。

R1CS 关系的折叠方案

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

R1CS 关系的折叠方案通过两个主要部分获得：从 R1CS 关系到广义承诺线性关系的线性化归约，以及广义承诺线性关系的折叠方案。

后者又通过以下知识归约的组合获得：范数检查归约（形成见证范数的"检查点"，使得提取的见证具有正确的范数）、同质化（统一关系的左侧，即所有实例使用相同的向量 $\mathbf{r}$）、见证和右侧的随机线性组合（将实例数量从 $L$ 减少到 $1$），以及分解（通过将见证分成两部分来减少见证的范数，形成线性关系的两个新实例）。

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

在正确性方向上，见证的范数在组合步骤期间增长，但通过分解步骤减少回来。在知识可靠性方向上，见证的范数在分解步骤期间增长。在折叠步骤中，见证的范数不仅增长，而且见证还被增加了一个"短分母"（也称为 松弛 ）。这种关系，通常表示为松弛的，在参数显著退化的情况下仍然保持绑定。这种范数的临时增长需要被控制，这是通过范数检查步骤实现的。范数检查步骤确保提取的见证的范数与原始见证的范数完全相同。

范数检查归约

范数检查归约是从广义承诺线性关系到自身的知识归约。该归约作为见证范数的"检查点"。在提取方向上，它确保提取的见证与原始见证具有相同的范数。

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

为了节省通信，证明者不发送所有单项式的承诺，而是采用"双重承诺"技术。然而，计算开销仍然显著。为了计算所有单项式的承诺，证明者需要执行 $L \cdot n \cdot m \cdot N \cdot \log_N \beta$ 次分圆环元素的加法，其中 $L$ 是实例数量，$n \times m$ 是承诺矩阵的维度，$N$ 是环的次数。这种开销在实践中可能是令人望而却步的。

同质化归约

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

证明者和验证者将所有线性关系表达为 sumcheck 声明，即对于每个实例 $j \in [L]$，他们将关系表达为

$$ \sum_{\mathbf{b} \in \{0,1\}^{\mu}} \mathsf{MLE}\mathbf{r}_i \cdot \mathsf{MLE}\mathbf{M}_i \mathbf{w}_j = y_{i, j} $$

对于每个 $i \in [t]$。然后，证明者和验证者参与 sumcheck 协议（批处理所有声明）将声明归约到单个随机点 $\mathbf{r}^* \in \mathcal{R}_q^{\mu}$，获得以下方程组：

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

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

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

使得新关系在所有实例中具有统一的左侧 $\mathbf{r}^$。$\mathsf{MLE}[\mathbf{r}_i](\mathbf{r}^)$ 上的声明由验证者直接验证。

用 ℓ₂-范数检查替代范围检查

为了减轻范数检查归约的开销，我们建议用 $\ell2$-范数检查替代 $\ell\infty$-范数检查。

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$，我们有

$$ \frac{1}{32} | \mathbf{w} |_2^2 \leq | \Pi \mathbf{w} |_2^2 \leq 32 | \mathbf{w} |_2^2 $$

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

用文字来说，该引理指出，通过使用具有指定分布条目的随机矩阵将高维向量投影到低维空间，我们可以确保投影向量的 $\ell_2$-范数以压倒性概率集中在原始向量的 $\ell_2$-范数乘以某些因子附近。

尝试 I：[BS23] 风格的 ℓ₂-范数检查

我们首先考虑从 [BS23] 直接改编的范数检查归约，它采用 Johnson-Lindenstrauss 引理来执行 $\ell_2$-范数检查。

我们考虑以下从广义承诺线性关系到具有额外约束的类似关系的知识归约：验证者从引理 4.1 中指定的分布采样随机矩阵 $\Pi \leftarrow C^{256 \times m}$。我们通过将每个条目嵌入为常数多项式，隐式地将矩阵 $\Pi$ 从整数提升到分圆环元素。证明者为每个实例 $j \in [L]$ 计算投影见证 $\mathbf{v}_j = \Pi \mathbf{w}_j \bmod q$ 并发送给验证者。验证者检查投影见证是否满足范数约束。验证者向证明者发送挑战 $\mathbf{c} \in \mathcal{R}_q^{256}$。稍后，在同质化步骤中，证明者和验证者为每个实例 $j \in [L]$ 将关系表达为 sumcheck 声明：

$$ \sum_{\mathbf{b} \in \{0,1\}^{\mu}} \mathsf{MLE}\mathbf{c}^{\mathtt{T}} \Pi \cdot \mathsf{MLE}\mathbf{w}_j = \mathbf{c}^{\mathtt{T}} \mathbf{v}_j $$

这些关系像以前一样被同质化。这种方法有两个主要缺点：验证者需要采样新的随机矩阵 $\Pi$，并在同质化步骤中进一步计算 $\mathsf{MLE}\mathbf{c}^{\mathtt{T}} \Pi$ 的求值。这为验证者引入了显著的开销，现在与见证的维度 $m$ 成线性关系，这通常是令人望而却步的。提取保证被削弱了。虽然 Johnson-Lindenstrauss 引理确保以压倒性概率投影见证的范数集中在原始见证的范数附近，但该界限仅在一个（非常小的）常数因子内成立。这意味着在提取期间，提取的见证的范数可能比原始见证大一个常数因子。在多个折叠步骤中重复应用此归约可能导致见证范数的无界增长，最终破坏承诺的绑定性。

尝试 II：[KLNO25] 风格的 ℓ₂-范数检查

为了解决先前方法中发现的问题，我们提出了一种受 [KLNO25] 技术启发的替代 $\ell_2$-范数检查归约。

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

假设 $L = 2^{e}$ 是 2 的幂，设 $b = 256 \cdot L$ 是块大小。验证者从引理 4.1 中指定的分布采样随机矩阵 $\Pi \leftarrow C^{256 \times b}$，其中 $b$ 是块大小。我们通过将每个条目嵌入为常数多项式，隐式地将矩阵 $\Pi$ 从整数提升到分圆环元素。证明者将见证 $\mathbf{w} \in \mathcal{R}_q^{m}$ 分成 $m / b$ 个大小为 $b$ 的块，即 $\mathbf{w}_j = [\mathbf{w}_j^{(0)} || \mathbf{w}_j^{(1)} || \ldots || \mathbf{w}_j^{(m/b - 1)}]$。证明者为每个块计算投影块 $\mathbf{v}_j^{(i)} = \Pi \mathbf{w}_j^{(i)} \bmod q$。它将投影块组合成单个向量 $\mathbf{v}_j = [\mathbf{v}_j^{(0)} || \mathbf{v}_j^{(1)} || \ldots || \mathbf{v}_j^{(m/b - 1)}]$，并进一步组合 $\mathbf{v} = [\mathbf{v}_0 || \mathbf{v}1 || \ldots || \mathbf{v}{L-1}]$。证明者对向量 $\mathbf{v}$ 进行承诺并将承诺发送给验证者。验证者向证明者发送挑战 $\mathbf{c} \in \mathcal{R}_q^{\mu^{\otimes \mu}}$，它被分成 $\mathbf{c}^{(0)} \in \mathcal{R}_q^{2^{\otimes \mu - e}}$ 和 $\mathbf{c}^{(1)} \in \mathcal{R}_q^{2^{\otimes e}}$，使得 $\mathbf{c} = \mathbf{c}^{(0)} \otimes \mathbf{c}^{(1)}$。证明者发送 $s \in \mathcal{R}_q$ 和 $\mathbf{t} \in \mathcal{R}^L_q$，使得

$$ s = \sum_{i \in [m/b]} \mathsf{MLE}\mathbf{c}^{(0)} \cdot \mathbf{c}^{(1)^{\mathtt{T}}} \mathbf{v}^{(i)} $$ $$ tj = \sum{i \in [m/b]} \mathsf{MLE}\mathbf{c}^{(0)} \cdot \mathbf{c}^{(1)^{\mathtt{T}}} \mathbf{v}_j^{(i)} $$

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

$$ \sum{\mathbf{b} \in \{0,1\}^{\mu}} \mathsf{MLE}[\mathbf{c}{1}\left( \mathbf{I}_{m / b} \otimes \Pi \right) ](\mathbf{b}) \cdot \mathsf{MLE}\mathbf{w}_j = t_j \bmod q $$

$$ \sum{\mathbf{b} \in \{0,1\}^{\mu}} \mathsf{MLE}[\mathbf{c}{0} \otimes \mathbf{c}_{1}](\mathbf{b}) \cdot \mathsf{MLE}\mathbf{v} = s \bmod q. $$

我们进一步修改协议。为了在提取中使用新附加的见证 $\mathbf{v}$，我们需要确保这个图像是低范数的。如果不是这种情况，提取可能无法为原始关系提取有效见证。换句话说，对应于 $\mathbf{v}$ 的关系不能被 松弛 。为了实现这一点，我们考虑一种略有不同的折叠变体，它不涉及投影见证。因此，折叠步骤只随机组合 $L + 1$ 个实例中的 $L$ 个，保持对应于 $\mathbf{v}$ 的关系不变。这样，在提取期间，投影见证 $\mathbf{v}$ 可供提取器使用而没有任何松弛，提取器可以使用它来恢复原始见证 $\mathbf{w}$。

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

建议的协议具有更好的效率，但它仍然留下提取保证（略微）开放。事实上，我们设法将提取的见证的范数从松弛的"升级"到几乎与原始见证相同。然而，所呈现的投影技术仍然在原始见证和提取的见证的范数之间留下了一个小的常数因子间隙。在多个折叠步骤中重复应用此归约可能导致见证范数的无界增长，最终破坏承诺的绑定性。

最终尝试：从略短到短的见证

为了完全弥合提取保证的间隙，我们建议将 $\ell_2$-范数检查与最终的"缩短"步骤相结合，将略短的见证转换为短的见证。这个想法最初在 [KLOT25] 中在 SNARK 和折叠方案的上下文中被探索，但针对低范数线性关系可满足性的限制性设置。

这次，我们利用见证已知是略短的这一事实，即其 $\ell_2$-范数由 $\alpha \beta$ 界定，其中 $\beta$ 是原始见证范数，$\alpha$ 是折叠期间范数增加的因子。

我们做出以下观察：向量的 $\ell_2$-范数与向量与自身的内积密切相关。更详细地说，我们写成

$$ | \mathbf{w} |_2^2 = \mathsf{ct}(\langle \mathbf{w}, \overline{\mathbf{w}} \rangle) \bmod q $$

其中 $\overline{\mathbf{w}}$ 是 $\mathbf{w}$ 的逐坐标复共轭。在 2 的幂次分圆环的情况下，复共轭对应于自同构 $X \mapsto -X^{N-1}$。有关更多详细信息，我们请读者参阅 [KLNO24]。 我们用 $\mathsf{ct} : \mathcal{R}_q \to \mathbb{Z}_q$ 表示分圆环元素的常数项。我们注意到，由于 $| \mathbf{w} |_2^2$ 已知是小的（即小于 $\alpha^2 \beta^2$），对于足够大的模数，上述等式在整数上成立（即没有 $\bmod q$）。

因此，为了确保见证正好具有所需的范数，只需证明 $\mathsf{ct} (\langle \mathbf{w}, \overline{\mathbf{w}} \rangle) \leq \beta^2$ 即可。

为了实现这一点，我们考虑以下从广义承诺线性关系到具有额外约束的类似关系的知识归约：证明者为每个 $j \in [L]$ 计算内积 $u_j = \langle \mathbf{w}_j, \overline{\mathbf{w}_j} \rangle$ 并发送给验证者。验证者检查每个 $j \in [L]$ 是否有 $\mathsf{ct} (u_j) \leq \beta^2$。证明者和验证者为每个实例 $j \in [L]$ 将关系表达为 sumcheck 声明，其中 $u_j$ 是右侧：

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

证明者和验证者参与 sumcheck 协议，将声明归约到单个随机点 $\mathbf{r}^* \in \mathcal{R}_q^{\mu}$，获得以下方程组：

$$ \mathsf{MLE}\mathbf{w}_j \cdot \mathsf{MLE}\overline{\mathbf{w}_j} = u_j^*, \quad \forall j \in [L] $$

证明者将方程分成两个线性方程，并发送 $u'_j$ 和 $u''_j$，使得对于每个 $j \in [L]$：

$$ \mathsf{MLE}\mathbf{w}_j = u'_j \bmod q $$ $$ \overline{\mathsf{MLE}\overline{\mathbf{w}_j}} = \mathsf{MLE}{\mathbf{w}_j} = u''_j \bmod q. $$

验证者检查每个 $j \in [L]$ 是否有 $u'_j \cdot \overline{u''_j} = u_j^*$。稍后，在同质化步骤中，证明者和验证者为每个实例 $j \in [L]$ 将关系表达为 sumcheck 声明，并像以前一样将它们与其他关系组合。

上述归约确保在提取期间，当提取的见证已经保证是略短的时，提取的见证与原始见证具有完全相同的范数。因此，通过将此归约与基于 Johnson-Lindenstrauss 的 $\ell_2$-范数检查相结合，我们获得了一个具有精确提取保证的完整 $\ell_2$-范数检查归约。

具体参数与效率

从效率角度来看，所提出的 $\ell2$-范数检查归约从证明者的角度来看比 [BC25b] 中的原始 $\ell\infty$-范数检查显著更高效。原因是现在"繁重步骤"是 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。

• https://github.com/osdnk/lattice-fold-plus-l2-norm-blog-estimates/blob/main/estimates.ipynb

这些设置几乎与 [BC25b] 中的设置相匹配，除了较小的模数 $q$ 和设置较大的范数（因为我们使用 $\ell_2$-范数）。此外，在 [BC25b] 中，实例数量 $L$ 设置为 3，对应于累加器的两个实例和新关系的一个实例。这里，我们设置 $L = 8$，因为我们有累加器的 4 个实例，并假设新关系的 4 个实例，这更方便，因为现在 $L$ 是 2 的幂。在将 $L=5$ 参数调整为与 [BC25b] 匹配（累加器的 4 个实例和新关系的 1 个实例）后，我们获得约 110 KB 的证明大小，这与 [BC25b] 的证明大小相匹配。

注意

在这篇博文中，为了阐述的简洁性，我们省略了关于精确参数选择和安全分析的一些细节。

我们忽略了联合界对证明可靠性的影响，即我们没有考虑在多个折叠步骤中应用 Johnson-Lindenstrauss 引理的次数。这可以通过相应调整引理的参数来轻松修复，这可能导致证明大小略有增加。仔细的分析可在 [KLNO25] 中找到。

对于效率分析，我们只考虑了证明者计算的主导项，即 Johnson-Lindenstrauss 投影的计算。在实践中，其他步骤，主要是同质化，也可能对整体计算有显著贡献。同质化的复杂度是 $O(L \cdot m )$ 环元素乘法，其中 $O(\cdot)$ 符号隐藏了小常数因子（实际上，它应该在 6 左右）。此外，乘法（涉及模约简）在我们的特定参数范围内比加法贵约 5 倍。此外，我们在同质化期间没有利用元素的短小性（即小系数），而我们在 Johnson-Lindenstrauss 投影期间可以利用。总的来说，同质化可能贡献约 30-40% 的整体证明者计算。这些估计是粗略的，我们将更仔细的分析留给未来的工作。

我们将讨论限制在分圆环是 2 的幂次分圆环的情况。这个假设简化了复共轭和自同构的讨论。然而，这些技术可以通过一些额外的技术开销扩展到一般分圆环。

我们将讨论限制在 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. https://eprint.iacr.org/2022/1341
• [BC25a] D. Boneh, B. Chen; LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems; Asiacrypt 2025. https://eprint.iacr.org/2024/257
• [BC25b] D. Boneh, B. Chen; LatticeFold+: LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems; Crypto 2025. https://eprint.iacr.org/2025/247
• [GHL21] C. Gentry, S. Halevi, V. Lyubashevsky; Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties; Eurocrypt 2022. https://eprint.iacr.org/2020/1397
• [KLNO24] M. Klooß, R. W. F. Lai, N. K. Nguyen, M. Osadnik; RoK, Paper, SISsors - Toolkit for Lattice-based Succinct Arguments; Asiacrypt 2024. https://eprint.iacr.org/2024/1972
• [KLNO25] M. Klooß, R. W. F. Lai, N. K. Nguyen, M. Osadnik; RoK and Roll - Verifier-Efficient Random Projection for $\tilde{O}(\lambda)$-size Lattice Arguments; Asiacrypt 2025. https://eprint.iacr.org/2025/1220
• [KLOT25] S. Kuriyama, R. W. F. Lai, M. Osadnik, L. Tucci; SALSAA - Sumcheck-Aided Lattice-based Succinct Arguments and Application. https://eprint.iacr.org/2025/2124
• [NS24] W. Nguyen, S. Setty; Neo: Lattice-based folding scheme for CCS over small fields and pay-per-bit commitments. https://eprint.iacr.org/2024/1973
• [STW23] S. Setty, J. Thaler, R. Wahby; Customizable constraint systems for succinct arguments. https://eprint.iacr.org/2023/552

• 本文转载自： mp.weixin.qq.com/s/Gvtwi... , 如有侵权请联系管理员删除。