登录 后可观看高清视频

ZK 白板 S3M4: LatticeFold 基于格的折叠方案

13次播放
1天前

视频 AI 总结：

该视频深入探讨了 LatticeFold，一种基于格的折叠方案，旨在实现内存高效的大规模零知识证明。视频首先介绍了多项式环在格密码学中的应用及其带来的效率优势，特别是对于SWIFFT承诺。随后，它阐述了折叠方案的核心挑战，即如何维持证明中证人（witness）范数的有界性，并提出了分解技术来解决这一问题。最后，视频详细讲解了LatticeFold独特的范围证明机制，该机制利用多项式环的代数结构，实现了高效且安全的折叠，并与现有方法进行了对比。

视频中提出的关键信息：

  1. 多项式环 (Polynomial Rings) 及其应用：

    • 多项式环是整数的推广，在格密码学中用于提高效率和安全性，例如使用 Z[x]/(x^d+1) 形式的循环多项式环。
    • 介绍了多项式环的算术运算（加法、乘法模 x^d+1 和 q）以及范数（L-infinity 范数）。
    • Rq（系数模 q 的多项式环）具有快速乘法特性（O(d log d) 复杂度）。

  2. SWIFFT 承诺 (Ajtai Commitments 的高效变体)：

    • SWIFFT 是一种更高效的 Ajtai 承诺，通过将数据 f 分割成环元素，并使用 Rq 上的承诺矩阵 A。
    • 其安全性可归结为结构化格问题（理想格问题），被认为是后量子安全的。
    • 计算效率远高于传统 Ajtai 承诺（m log n 对 n*m）。

  3. 折叠方案 (Folding Schemes) 及其挑战：

    • 折叠方案旨在将两个证明实例合并为一个更简单的实例，以实现证明的累积。
    • 需满足完备性、可靠性和简洁性（验证者复杂度亚线性）等特性。
    • 核心挑战在于，简单的随机线性组合（cm = cm1 + r * cm2）会导致新证人 f = f1 + r * f2 的范数显著增大，从而破坏承诺的绑定性。

  4. 范数增长问题的解决方案：

    • 改进挑战集 S： 将随机挑战 r 限制在系数较小的多项式集合 S 中（例如，系数为 {-1, 0, 1}），可以将范数增长限制在 d * B 范围内，但仍会在多次折叠后累积。
    • 分解技术 (Decomposition Technique)： 将证人 f 分解为 f_l 和 f_h（例如 f = f_l + sqrt(B) * f_h），并对分解后的部分进行承诺。通过验证这些承诺的一致性，并巧妙地组合，可以确保最终折叠后的证人范数保持在 B 以下（例如，当 B = 16d^2 时）。

  5. 范围证明 (Range Proof) 机制：

    • 分解技术的安全问题： 分解技术本身无法强制证明者绑定到正确的、小范数的分解向量，因此需要范围证明来强制执行范数约束。
    • 现有范围证明方法的局限性： 现有的格基 Bulletproofs、Labrador 或基于 SNARK 的 plookup 等方法，要么验证者复杂度为线性，要么存在辅助向量范数过高导致的循环性问题，不适用于折叠方案。
    • LatticeFold 的范围证明：
      • 将证人 f 分解为 t 个向量（f_1 到 f_t），每个向量的系数限制在 {-1, 0, 1} 范围内。
      • 将范数约束转换为代数“零检查”关系（例如 f_i * (f_i - 1) * (f_i + 1) = 0）。
      • 利用 Sum-Check 协议将这些关系高效地归约为线性关系和求值语句。
    • LatticeFold+ 的优化：
      • 直接利用 Rq 的代数结构，而不是依赖于分解和高次多项式的 Sum-Check。
      • 通过在 Rq 上构造低次多项式公式来表示范围约束，使得 Sum-Check 协议的开销大大降低。
      • 最终证明者开销显著降低，接近于一到两个 SWIFFT 承诺的计算成本，从而实现更高效的大范围证明。