1. 引言

递归零知识证明（Recursive Zero-Knowledge Proof，简称递归ZKP）是一种使用递归概念的零知识证明，它通过递归的方式生成可更高效验证的证明，某些情况下还可以将多个证明合并成一个单一的证明。这在区块链系统中尤为重要，因为在这些系统中，效率和可扩展性是至关重要的。

1.1 零知识证明

零知识证明 是一种密码协议，它允许一方（证明方）向另一方（验证方）证明其知道某个信息（如一个秘密），而无需泄露该信息的具体内容。零知识证明保证了以下三个关键性质：

1. 完备性（Completeness）：如果陈述为真，诚实的证明方能够使验证方信服。
2. 可靠性（Soundness）：如果陈述为假，欺诈的证明方无法使验证方信服。
3. 零知识（Zero-Knowledge）：验证方除了知道陈述是真的之外，什么也不知晓（即验证方不会获得任何关于秘密的信息）。

1.2 递归零知识证明

在递归零知识证明中，证明的内容本身可以作为另一个证明的组成部分。换言之，证明方可以用一个证明来证明另一个证明的有效性，这样可以以递归的方式构建复杂的证明。具体而言，使用电路$Circuit$表达zkSNARK的验证算法$\mathsf{Verify}$，将验证算法所使用的证明 $Proof$ 和验证密钥 $VK$ 作为输入，并生成一个新的证明$Proof'$ 。

在递归零知识证明中，可以理解为“证明一个证明的有效性”，然后再继续证明下一个陈述，依此类推。递归就是“证明的证明”。简单来说，这意味着证明自己是真实的，同时证明其他证明也是有效的，并且可以通过递归构建更复杂的证明。

1.3 递归零知识证明的关键部件

1. 外部证明和内部证明：递归零知识证明包括一个外部证明，这个证明依赖于内部的其他证明。外部证明可以理解为“证明有效性”的证明，内部证明则是构成外部证明的一部分。
2. 递归组合：递归零知识证明的核心思想是，多个独立的零知识证明可以聚合成一个紧凑的证明。通过递归组合，多个计算、验证或过程（例如多个交易或合约执行）可以在一个证明中进行验证。
3. 效率和可扩展性：递归零知识证明在需要验证许多独立证明的情况下尤其有用，例如在区块链系统中，可能存在很多交易。与逐个验证每个证明不同，递归证明可以将多个证明合并成一个单一的证明，大幅提升验证效率并减少计算开销。

2. Plonky2递归零知识证明原理

2.1 生成第一层证明

第一层零知识证明，通常称为内嵌/底层证明（Inner Product），该证明主要确保以下5项内容正确：

(1). 公共输入的哈希值： 验证公共输入的承诺是否正确；

(2). 多项式验证： 验证电路约束是否在验证点上成立，主要验证内容如下：

• 电路约束多项式：
  • 每个零知识证明都表示一个电路，电路被编码为多项式的约束条件。
  • 验证这些约束是否在特定点上成立。
• 消去多项式 (Vanishing Polynomial)：
  • 检查底层证明的多项式是否在验证点 zeta 上“被消去”（即满足电路约束）。
  • 消失多项式的公式类似于：$ Z_H(\zeta) = \zeta^d - 1 $，其中 $d$ 是电路的阶。
• 商多项式 (Quotient Polynomial)：
  • 商多项式用于分解和验证消去多项式的结果。
  • 验证商多项式是否正确地将约束多项式分解为消去多项式的一部分。

(3). FRI验证: Low-degree test

• Merkle 树验证：
  • 验证多项式承诺的哈希路径是否正确。
  • 检查 Merkle 树的根哈希是否与提交的承诺一致。
• 折叠一致性 (FRI Folding)：
  • 验证多项式折叠后的结果是否满足一致性要求。
  • 折叠多项式是通过递归计算得到的，每次折叠都减少多项式的阶。

• 打开点验证：

  • 检查多项式在特定点上的值是否匹配底层证明提供的承诺。

  (4). Merkle树路径验证: Merkle proof

• 验证多项式承诺的 Merkle 树路径。

• 检查路径中每个节点的哈希计算是否正确。

  (5). 随机挑战值 确保生成的随机挑战值是由正确的public coin经过哈希得到，主要包括

• $\beta, \gamma$：用于多项式约束。
• $\alpha$：用于随机化约束多项式。
• $\zeta$：验证点，用于检查多项式在特定点上的值。

2.2 确定递归电路

首先先要确定递归电路的结构，并引入虚拟目标（Virtual Target）表示需要验证的数据（因为在确定验证电路之前，没有生成对应的内嵌证明）。

虚拟目标的作用： 由于递归证明涉及多层，且电路需要在一开始就进行确定，所以需要采用虚拟目标进行提前占位，在特定轮次进行递归证明时再填充对应数据。

主要包括以下步骤：

• 验证内容：
  • 验证底层证明的公共输入。
  • 验证多项式约束（消失多项式和商多项式）。
  • 验证多项式承诺的 FRI 证明。

• 构建虚拟目标： 在递归验证电路中使用 虚拟证明目标 占位，表示底层证明的所有数据。

  let pt = builder.add_virtual_proof_with_pis(&inner_cd);  // 虚拟目标

  • add_virtual_proof_with_pis 用于构建虚拟证明和公共输入。

• 验证逻辑： 使用 verify_proof 函数在递归电路中嵌套验证逻辑：

  builder.verify_proof::<InnerC>(&pt, &inner_data, &inner_cd)；

  • 验证底层证明的公共输入、打开点、FRI 证明等。

2.3 嵌套递归验证

通过递归将底层验证电路嵌套到更高一层电路，生成递归证明：

• 在递归电路中嵌套更高一层的验证逻辑。
• 通过多个递归步骤逐层压缩证明。

2.4 运行递归验证

使用递归验证电路逐步生成递归证明，验证所有嵌套证明的正确性：

• 填充虚拟目标，用实际底层证明数据替换占位符；
• 逐步运行递归验证电路，并逐步生成递归证明；
• 到最后一步后，生成最终的递归证明。

2.5 优化方向

(1) FRI 和low-degree test Plonky2 使用 FRI作为证明生成开销较低的多项式承诺方案，相比于传统 KZG，FRI 在递归场景中可以显著降低证明大小和验证复杂度。

(2) 高效字段 Goldilocks Goldilocks 是一个优化的 64 位素数域，支持快速的模运算，非常适合现代 CPU，通过在这个字段内构建约束，每一步的验证电路大小将会减小，并进一步减少计算开销。

(3) Poseidon 哈希函数 Plonky2 使用 Poseidon 构造约束友好的哈希函数，减少哈希运算的电路深度和门数量。

3. 优点与挑战

3.1 优点

• 紧凑性：递归零知识证明允许将多个证明压缩成一个更小的证明。
• 效率：使用递归零知识证明，验证许多陈述或计算的速度远高于单独验证每个证明。
• 可扩展性：它们使得系统能够处理大量的证明（如区块链中的交易），而不会遇到性能瓶颈。

3.2 挑战

• 复杂性：构建递归零知识证明是复杂的，涉及的密码学构造难以正确实现。
• 计算开销：尽管递归证明的验证效率很高，但创建（特别是在zk-SNARKs的情况下）涉及的计算开销较大。

4. 应用方向

1. 可扩展的区块链：递归零知识证明可以用于创建高效的区块链证明。例如，递归zk-SNARKs（零知识简洁非交互性知识论证）可以证明一组交易是有效的，而无需揭示交易的具体细节，同时还能够将多个区块的验证合并成一个证明。
2. Rollup技术：递归零知识证明是zk-rollups（零知识汇总）的基础，这是一种区块链扩展解决方案，像以太坊这样的区块链就采用了zk-rollups技术。zk-rollups将多个交易聚合成一个证明，并将这个证明发布到以太坊主链上，从而减少交易费用并提高吞吐量。
3. 可验证计算：在云计算或去中心化计算中，递归零知识证明可以用于证明某些计算过程是正确的，而无需透露计算过程中的任何数据。
4. 隐私保护协议：递归零知识证明允许在复杂的隐私保护应用中使用，例如证明一系列交易或活动是有效的，但不揭示具体的细节。

5. 总结

递归零知识证明将零知识证明的能力与递归的概念相结合，允许创建复杂的证明，并且能通过递归的方式合并多个证明，从而使系统更加高效、紧凑和可扩展。主要优势在于能够为复杂的计算提供紧凑的证明，特别适用于区块链系统、加密协议和隐私保护应用。