【zkMIPS系列】Plonky2递归零知识证明原理

  • ZKM
  • 更新于 4天前
  • 阅读 137

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

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. 总结

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

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
ZKM
ZKM
github: https://github.com/zkMIPS