基于 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 的约束效果。