基于 ZK 的资产证明

Summa

我们一般持有加密货币常常会在中心化交易所进行货币的买卖兑换等操作。在中心化交易所进行交易非常便捷迅速，自比特币发行以来十多年的时间，市场上涌现过许许多多的中心化交易所，极大的方便了用户进行加密货币买卖操作。但是伴随着中心化交易所的繁荣，欺诈和恶意卷款跑路等行为屡见不鲜。奈飞曾为此专门拍摄过一部关于交易所突然倒闭，创始人神秘死亡的宣传片：别信任任何人，虚拟货币悬案^[1]。特别的，2022 年 FTX 因为资不抵债而宣布破产更是震惊了世界，诸多用户和基金公司为此蒙受巨大损失。

事实上，不止在加密货币领域，其他传统领域通过会计做假账的方式欺瞒投资者的行为也是难以计数。如 21 世纪初轰动世界的安然事件。安然是一家连续六年被《财富》杂志评选为「美国最具创新精神公司」，然而就是这样拥有上千亿资产的公司，在 2002 年在几周内迅速破产。又比如恒大公司，将本来用于盖楼的专款资金挪去他用，最终导致无数业主背上 30 年房贷苦等来的却是烂尾房屋。

多个不同领域层出不穷的欺诈行为背后的一个重要原因就是审计和会计工作本身并不完全公开透明，于是产生巨大的腐败和作弊空间。但是为了保护公司利益和投资者隐私，关键财务数据又不可能做到完全公开透明，因此应对财务造假除了加强监管一直没有很好的解决办法，但是随着零知识证明技术逐渐成熟，我们可以看到一种新的解决思路。

如果每个用户都可以验证自己部分的资产是否有财务作假行为，那么只要验证的用户足够多，那么一个组织想要去做财务欺诈难度就会非常高。而又因为验证的过程是零知识的，那么验证数据在网络传输过程中，第三者即使截获了数据，他也不知道用户的真实资产到底是多少，这样一来，验证过程就完全可以在网络上公开展示出来。在零知识证明技术的帮助下，相当多的审计工作不再是像四大会计事务所一样是某些组织的专利，关起门来秘密进行。而是任何利益相关方都可以参与的公开过程。

Summa^[2]是一个 PSE 研究项目，旨在用 zk 的办法来去做用户资产验证。本文接下来的内容就概要的介绍一下该项目，以及技术实现原理。

合约

Summa 的整体数据流如图所示。智能合约在这里主要用于对一些公共数据存储和验证。并不一定和以太坊强绑定，即使将来部署在像 Solana 等其他区块链也是可以的（只要 Halo2 有对应区块链支持，本项目中一些合约是由 Halo2 证明生成的^[3]）。

图中 Custodian 表示中心化交易所。合约由交易所部署上链，合约所有权归交易所所有，公共数据只能由交易所提交。公共数据包含两部分，一部分是交易所掌控的链基本信息以及数字签名等。

第二部分是链上资产的信息，包括 Merkle sum tree 的 root hash，以及 root balance（链上资产的具体数量，比如多少个 BTC ），该部分数据将用于 zk 证明的 instance 输入。

这两部分数据都是很容易在链上公开可以查询到的（除了 root hash ）。交易所很难对这些数据作弊。任何人都可以对比合约中存储的数据和区块链地址上实际数据结果。

proof 生成目前是由交易所生成，由用户向交易所提交需要验证的关键信息，然后由交易所生成 proof 返回给用户。用户可以拿着这个 proof 向智能合约请求，由合约来验证 proof。

最后 Proof Verify 是用户同合约直接交互的。该部分合约是由 Halo2 电路翻译成 Solidity 代码然后作为一个单独的验证合约部署上链。

在实际使用时可以通过传入 proof 来在链上计算和验证。

下面的代码示例是实际的 Hash 运算所用到的函数，可以看到整个 hash 计算本身并没有用到位运算，只有加法和乘法计算，是 zk 友好的。

zk 数据计算和传统的程序计算不同的是 zk 数据要在有限域中计算，Merkle Tree 构建时确保每一个结点数据不能超过有限域就十分必要了，为此在计算前先要对数据做 range check 以后数据 overflow。

range check 的大致原理类似下面示例所示。首先对于输入的数据，以 8 位为长度单位，截出多份，方便将来做减法运算。然后每次进行 next数值计算的时候都按照下面示例的计算步骤去做计算。range check 电路做约束的时候实际上是根据中间结果diff = z_cur - z_next * Expression::Constant(Fp::from(1 << 8))去做约束，要求 diff 只要在 8 位数值之内即可。这样对于一个 32 位数据的约束，只需要占用 4 个计算 cell，还有 256 个 lookup table，以后最高位为 0 的 instance 约束即可。如果不是这样设计，单纯去做 32 位数值的 range check，需要  大小的 lookup table，显然这样的电路就太大了，无法实际应用。

有了这些辅助结构就可以正式构建 Merkle Sum Tree。每一个用户输入数据都称之为 Entry，其结构为：

Merkle Tree 中间结点的 hash 计算方式是H(LeftChild.balance[0] + RightChild.balance[0], LeftChild.balance[1] + RightChild.balance[1], ..., LeftChild.balance[N_CURRENCIES - 1] + RightChild.balance[N_CURRENCIES - 1], LeftChild.hash, RightChild.hash)，因此实际要计算的 vec 数组长度是N_CURRENCIES + 2。

下面我们完整构建一下整个 Merkle Tree。叶子结点部分比较简单，只需要将 Entry 转换为 Node 即可。中间结点需要逐层构建，每一个中间结点的值都和下一层的左子树和右子树的值有关。最后将计算的中间结点结果放到 tree 数组里：

接下来我们使用 Merkle Tree 构建 zk proof。zk 要证明的是某个用户的 entry 确实在该 Merkle Tree 上。所以首先需要对制定具体的 entry 索引，根据 Merkle Tree 生成 zk proof 需要的数据结构。

我们可以通过设置 0 和 1 来巧妙的达到让整个等式为 0 的约束效果。

Merkle Tree zk 约束主要有两部分，一部分是 swap 约束，以确保交易所在生成证明的时候确实是按照上图的真实顺序生成的。另一部分是 balance 约束，即父结点的 balance 确实来自左子结点和右子结点的和。关于 balance 的 sum 约束比较简单，这里着重看一下 swap 约束。

我们之前介绍的 Merkle zk tree 数据结构sibling_middle_node_hash_preimages是一个数组，并没有包含位置信息。图中虚线方框的位置到底是在应该在树的左侧还是右侧，要有path_indices的 0 和 1 来判断。因此我们一定要确保当数值为 0 的时候，该生成父结点位于左侧，他对应的同 level 的兄弟结点位于右侧，1 的时候相反。在数据导入 zk 电路时该逻辑可以比较轻松的用代码实现：

整体的 Merkle Sum Tree zk proof 的过程就是逐层的处理数据，然后将对应位置数据输入 zk 约束电路检查。构建起整个 Merkle Tree。最后输出的是根节点 hash 和总的 balance，它应该和合约中的对应数据保持一致，使用 instance 来验证一致性。如果所有验证都没有问题，至此整个 Merkle Tree 的证明工作算是结束。

Solvency Verify

生成 proof 的过程是由用户向交易所请求，然后交易所返回 proof 数据，随后用户再向智能合约去做验证。目前该项目暂时不支持用户绕过交易所自行生成 proof，但是觉得未来或许可能是一个可以探索的方向。由用户直接生成 proof，而不是由交易所返回。整个 halo2 证明电路可以用 rust 打包成 web assembly，然后使用 ethers rs^[7] 作出对应的交互 api。Merkle Tree root 验证时间复杂度是 log(n)，或许用户的设备做验证并不需要太多的时间，这样进一步增强了去中心化的安全性。

参考

[1]

别信任任何人，虚拟货币悬案: https://www.netflix.com/hk/title/81349029

[2]

Summa: https://github.com/summa-dev

[3]

Halo2证明生成的: https://github.com/privacy-scaling-explorations/halo2-solidity-verifier

[4]

Poseidon Hash: https://github.com/ingonyama-zk/poseidon-hash

[5]

参数准备阶段和Hash运算阶段: https://autoparallel.github.io/overview/index.html

[6]

Linear-feedback shift register: https://en.wikipedia.org/wiki/Linear-feedback_shift_register

[7]

ethers rs: https://github.com/gakonst/ethers-rs

推荐阅读

ZK Insights 系列

zkp 学习笔记

Wen Building Podcast

研究分析系列文章

Uniswap 精翻系列

Antalpha Labs 是一个非盈利的 Web3 开发者社区，致力于通过发起和支持开源软件推动 Web3 技术的创新和应用。

官网：https://labs.antalpha.com

Twitter：https://twitter.com/Antalpha_Labs

Youtube：https://www.youtube.com/channel/UCNFowsoGM9OI2NcEP2EFgrw

联系我们：[email protected]