原文链接：Introducing zkTree: a zk recursion tree with ZKP membership proofs

本文作者：Polymer Labs  编译：CoinTime Candice

零知识证明是保护用户隐私的强大工具，首先在区块链中广泛使用，以验证私人交易的有效性（如Zcash）。零知识证明的一个同样重要和新兴的应用是压缩计算，在链上运行一个简短的验证可以证明一个长的计算已经在链外正确执行。这种验证可以用比在链上运行原始计算更少的时间和gas完成，从而实现zkEVM、zkRollup和zkBridge。

然而，零知识证明者在历史上一直非常缓慢的。通常情况下，证明者的时间复杂度至少与算术电路的大小成线性关系。在现实世界中，CPU上速度快的算法并不总是容易表示为zk运算电路。例如，广泛使用的EdDSA数字签名方案在curve25519上需要超过200万门的zk电路和12秒的证明时间。此外，链上验证的成本也很高，尤其是在以太坊上，最便宜的zk验证者的成本约为23万gas，而STARK验证则高达500万gas。这些挑战破坏了许多创新应用程序（如zkBridge和zkIBC）的可行性。

为了解决这些设计挑战，我们引入了zkTree结构，并对zkTree递归证明管道进行了原型设计，以提高证明时间并降低验证成本。通过将证明生成分布在不同的机器上，并通过zkTree递归合成证明，我们可以确保验证者拥有几乎无限制的计算能力和快速的证明速度，这可以大幅提高未来zk技术的功能。此外，通过与zk成员证明共享相同的链上验证者，不同的系统/公司可以分享恒定的链上验证成本，增加各种应用的经济可行性。

zkTree是一个树形数据结构，其中每个节点是一个zk证明（ZKP），每个母节点递归地证明其子节点的zk证明。当一个zk证明π递归证明了两个zk证明π0和π1，并且π在链上得到验证，那么所有的子证明π0和π1也在链上得到验证。

zkTree中有三种类型的证明。

zkTree示例如下图所示。在根节点中计算的电路哈希和输入哈希是所有用户电路和用户证明的merkle根。为了验证用户证明是否包含在根证明中，我们只需要验证其输入哈希值和用户电路哈希值的merkle路径。在下面的例子中，为了验证用户证明4是否包含在根证明节点3中，需要提供电路哈希值c4、c7、c9和输入哈希值h4、h3、h5。c_l和c_n是叶子电路和节点电路的电路哈希值，代表公共参数，可以用来验证zkTree构建器电路是否安全。

我们使用PLONK和FRI的组合Plonky2实现了zkTree，并在Groth16中递归地证明了它的根证明。我们还建立了管道，利用zkTree来验证Tendermint共识的默认签名方案，在以太坊虚拟机（EVM）中的一个证明中验证了32个ed25519签名。与ed25519 circom库相比，在EVM中相同的gas成本为23万的情况下，总证明时间从384秒减少到77秒。

zkTree实现了zk证明的快速和低成本的递归组合。成千上万个ZKP可以在大约一分钟内用merkle成员证明在链上递归组合和验证，一个Groth16证明的gas成本为12万。zkTree是灵活的，它的成本和速度可以根据不同的用例场景进行重新平衡。通过使用FPGA和ASIC等特定硬件，Plonky2和Groth16证明者可以进一步加速，从而可以进一步优化zkTree构建的总时间。叶子电路也可以作为Groth16/Plonk验证者来实现，扩大了zkTree的潜力，使之在未来具有更多的用途。

我们已经开放了zkTree的大部分代码。请参考以下代码库：

关于Polymer：

Polymer是第一个基于IBC的模块化网络协议。Polymer链将通过基于轻型客户端状态验证的无信任架构，实现所有集成链的ZK-IBC连接。Polymer相信多链的未来主要由一个开源、社区开发和维护的行业标准IBC x Polymer连接。

*本文由CoinTime整理编译，转载请注明来源。