当前位置：首页 > ds >正文

对比FRI 与 Ligero 证明大小

ds 2025/8/12 5:26:10

1. 引言

在多项式承诺方案中，如果不使用哈希（Merkle 哈希和 Fiat-Shamir 转换）以外的任何密码学原语，FRI 被认为是证明最短的方案。
但实际上，这取决于被承诺的多项式的阶数。

对于阶数不超过约 $2^{18}$ 的多项式，FRI 证明实际上比另一种称为 Ligero 的方案更大。
- 这一结论的成立不依赖于将 Ligero 的安全性建立在任何关于统计安全性的未经证实的猜想之上，而是建立在将 FRI 的安全性建立在这些猜想之上（参见与本说明相关的2023年11月博客——关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答的第 7 项）。

阶数 $2^{18}$ 虽然比大多数当前项目使用的要低，但有些项目计划在未来使用此阶数的多项式，以控制 FRI 证明者巨大的内存消耗（可达很多 GB）。

如果不将 FRI 的安全性建立在上述猜想之上，那么在阶数大于约 $2^{20}$ 之前，Ligero 证明仍然比 FRI 证明更小。

2. 摊销（Amortization）

比较变得更复杂，因为大多数当前基于 FRI 的项目会将其同时应用于多个多项式，从而摊销部分成本。虽然 Ligero 也有摊销能力，但不如 FRI 有效。然而，Ligero 在这些场景中可能仍然可行，本说明后面会讨论。

3. Ligero 与 FRI 背景

Ligero 与 FRI 工作在完全相同的有限域上，并基于相似的技术（即 Reed-Solomon 编码、Merkle 哈希和 Fiat-Shamir 转换）。

Ligero的证明由 $O(nλ)O(\sqrt{n\lambda})$ 个域元素和少量哈希计算组成。

干净的 Ligero 多项式承诺描述可以在 2021年 Brakedown: Linear-time and field-agnostic SNARKs for R1CS 论文的第 4.2 节中找到，安全性分析在附录 B；另见 Diamond 和 Posen 的2023年论文Proximity Testing with Logarithmic Randomness，其中给出了 Brakedown 论文未描述的额外优化的优秀说明。

Justin Thaler 猜测当前（2023年） Ligero 还不流行的原因是：

人们看到 $n\sqrt{n}$ 项就认为Ligero的证明太大而无用（早期实现也相当未优化，这可能给了大家一个性能较差的印象）。

然而，虽然 Ligero 对阶数上界 $n$ 的依赖在渐近意义上比 FRI 差（ $O(n)O(\sqrt{n})$ vs. $O(\log(n)^2)$ ），但 Ligero 对安全参数 $λ\lambda$ 的依赖更好。而且，对于较小的 $n$ ， $n\sqrt{n}$ 与 $log^2 n$ 相差不大。事实上，当 $n < 2^{16}$ 时， $n\sqrt{n}$ 甚至比 $log(n)^2$ 还小。

Ligero 还有额外的简单性和性能优势。如，Ligero的证明者天然会执行大约 $O(n/λ)O(\sqrt{n/\lambda})$ 次大小为 $O(nλ)O(\sqrt{n\lambda})$ 的 FFT，这比 FRI 中长度为 $O (n)$ 的单次 FFT 更容易并行化，性能更好。Ligero 的证明者还比 FRI 做更少的哈希计算。

4. FRI 与 Ligero 证明大小定量比较

在 $λ\lambda$ 位安全性（假设已知攻击恰好是最优的）下，FRI 证明大约包含
$λlog⁡(n/ρ)22log⁡(1/ρ)\frac{\lambda \log(n/\rho)^2}{2 \log(1/\rho)}$
个哈希值，其中 $1/ρ1/\rho$ 是所谓的 “FRI 扩展因子”（blowup factor）——控制了证明者时间与证明大小之间的权衡。将扩展因子设为 $1/4$ ， $λ=128\lambda = 128$ ，对于阶数 $n = 2^{18}$ 的多项式，证明大小约为 400 KB。

这是一个高估值：

由于诸如 Merkle capping 等技术（以增加承诺大小为代价缩短 Merkle 认证路径长度），可以节省约 33%，因此阶数 $n = 2^{18}$ 的多项式，其FRI证明估计值可降至约 270 KB。
如果不使用2023年11月博客关于Lasso、Jolt和SNARK设计最新进展的技术常见问题解答第 7 项中提到的猜想，该证明大小将超过两倍。

Ligero 证明（不使用类似的可靠性猜想）大约由
$2nλ/log⁡(2/(1+ρ))2\sqrt{n\lambda/\log\left(2/(1+\rho)\right)}$
个域元素和少量哈希值组成。许多基于 FRI 的项目目前使用 128 位域，虽然这在不依赖猜想的情况下略低于 128 位安全性。在 128 位域、扩展因子为 $1/4$ 、 $λ=128\lambda = 128$ 的情况下，对于同样的阶数 $n = 2^{18}$ ，Ligero 证明大小为 225 KiB。

这一定性比较已在近期工作中得到验证。如，FRI 调查报告（2022年论文A summary on the FRI low degree test）第 10 页顶部指出，在 128 位安全性（不依赖 Johnson bound以外的统计安全性猜想）下，对于阶数仅为 $2^{12}$ 的多项式，使用扩展因子 8 的 FRI 证明就已超过 300 KB。在相同安全水平下，Diamond 和 Posen 2023年论文Proximity Testing with Logarithmic Randomness 称，对于阶数 $2^{16}$ （即比 $2^{12}$ 大 16 倍）的多项式，使用扩展因子 4 的 Ligero 证明大小约为 270 KB，这意味着比扩展因子 8 的证明者至少快 2 倍。类似的结论也出现在 Ligero 最新extended version扩展版的相关工作部分中。

5. 摊销场景下的部署

在大多数部署中，FRI 被用于承诺 $k$ 个多项式，其中 $k$ 介于约 50 到几百之间（如可参见 RISC Zero 文档的第 5 节，其中 “columns” 的数量对应于承诺的多项式数量）。FRI 和 Ligero 都有非平凡的摊销机制，因此它们的证明大小远小于非摊销情况下（即 $k = 1$ ）的 $k$ 倍。

Justin Thaler 估计，在这些场景下（在激进的安全性猜想下），FRI 证明大约包含：
$3λlog⁡(n/ρ)/log(1/ρ)+λlog⁡(n/ρ)2/(2log⁡(1/ρ))3\lambda \log(n/\rho)/log(1/\rho) + \lambda \log(n/\rho)^2/(2 \log(1/\rho))$
个哈希值，以及
$kλ/log⁡(1/ρ)k\lambda/\log(1/\rho)$
个域元素；某些优化（如 Merkle capping）还可进一步节省空间。

Ligero 证明主要由：
$2knλ/log⁡(2/(1+ρ))2\sqrt{k n\lambda/\log\left(2/(1+\rho)\right)}$
个域元素组成。

在这种摊销场景中，比较结果更倾向于 FRI，但 Ligero 仍具有竞争力。如：

在 $λ=128\lambda = 128$ 、 $k = 60$ 、扩展因子为 4、域大小为 128 位、阶数 $n = 2^{18}$ 的情况下，
- FRI 证明大小约为 415 KB（激进猜想下）或 830 KB（无猜想）。
- 而 Ligero 在无猜想情况下约为 1.75 MB。

目前大多数 FRI 部署都使用 SNARK 递归，因此证明大小并不一定要尽可能小。重要的是 FRI 证明要足够小、验证足够快，使得递归不会成为证明者时间的瓶颈。这可能使 Ligero 即使在摊销场景中也比 FRI 更可取，因为它的证明者更快，而且在 $n = 2^{18}$ 时证明大小仅比 FRI 大 2-4 倍。

6. Grinding 技术

Ligero 和 FRI 承诺方案的证明长度都可以通过一种称为 “grinding” 的技术略有改进，该技术会提高已知针对 Fiat-Shamir 转换的攻击成本，而不会增加证明大小。在此上下文中，“grinding 技术” 是对“grinding 攻击” 的防御。由于 FRI 对安全参数 $λ\lambda$ 的依赖较差，FRI 从这种 grinding 技术中获益更多。当前有些 FRI 部署使用了该技术，有些则没有。