基于 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 需要的数据结构。

We generally hold cryptocurrencies and often conduct operations such as currency trading and exchange in centralized exchanges. It is very convenient and rapid to conduct transactions in centralized exchanges. Since the issuance of Bitcoin for more than ten years, many centralized exchanges have emerged in the market, which greatly facilitates users to conduct cryptocurrency trading operations. However, with the prosperity of centralized exchanges, fraud and malicious running away, it is not uncommon. Netflix once filmed a special film about the sudden closure of exchanges. Don't trust anyone in the propaganda film of mysterious death of people. The bankruptcy of virtual currency because of insolvency in a special year shocked many users and fund companies in the world. In fact, it is not only in the field of cryptocurrency, but also in other traditional fields, it is countless to cheat investors by making false accounts through accounting. For example, Enron, which caused a sensation in the world at the beginning of the century, was selected as the most innovative company in the United States by Fortune magazine for six consecutive years. However, this is how it is owned. Companies with assets of 100 billion went bankrupt quickly in a few weeks in 2008. For example, Evergrande moved the special funds originally used for Gai Lou to other purposes, which eventually led to countless owners suffering from mortgage loans last year. However, an important reason behind the endless fraud in many different fields of unfinished houses is that the auditing and accounting work itself is not completely open and transparent, which creates huge space for corruption and cheating. However, in order to protect the company's interests and investors' privacy, it is impossible to completely disclose key financial data. Therefore, there is no good solution to deal with financial fraud except strengthening supervision, but with the gradual maturity of zero-knowledge proof technology, we can see a new solution. If every user can verify whether some of his assets have financial fraud, it will be very difficult for an organization to commit financial fraud as long as there are enough users to verify, and because the verification process is zero-knowledge, even if the third party intercepts the verification data in the network transmission process. After obtaining the data, he doesn't know how much the user's real assets are, so the verification process can be completely displayed publicly on the Internet. With the help of zero-knowledge proof technology, quite a lot of audit work is no longer the patent of some organizations behind closed doors like the four major accounting firms, but the public process that any interested party can participate in is a research project aimed at using new methods to verify the user's assets. The overall data flow of the project and technical realization principle contract is shown in the figure. Smart contracts are mainly used to store and verify some public data here, and are not necessarily strongly bound to Ethereum. Even if they are deployed in other blockchains like this in the future, it is ok as long as there is corresponding blockchain support. Some contracts in this project are generated by certificates. The figure shows that centralized exchange contracts are deployed by the exchange, and the ownership of the winding contracts belongs to the exchange. Public data can only be submitted by the exchange, and public data contains two parts. One part is the basic information of the chain controlled by the exchange and the digital signature. The second part is the information of the assets on the chain and the specific number of assets on the chain, such as how many. These two parts of data are easy to be disclosed on the chain and can be queried. Except for the exchange, it is difficult for anyone to cheat on these data. Anyone can compare the data stored in the contract with the actual data on the blockchain address. At present, the result generation is generated by the exchange and submitted by the user to the exchange. The key information that needs to be verified is then generated by the exchange and returned to the user. The user can take this and ask the smart contract for verification by the contract. Finally, the part of the contract that the user interacts directly with the contract is translated into code by the circuit and then deployed as a separate verification contract. In actual use, the chain can be calculated and verified by passing in. The following code example is the function used in the actual operation. It can be seen that the whole calculation itself does not use bit operation, only addition and sum. Multiplication calculation is friendly. The difference between data calculation and traditional program calculation is that it is necessary to ensure that the data of each node cannot exceed the finite field when building. Therefore, the general principle of data is similar to that shown in the following example. First, multiple copies of the input data are cut out in bits to facilitate subtraction in the future, and then every time the numerical calculation is carried out, the calculation circuit is constrained according to the calculation steps in the following example. In fact, the constraint requirement is made according to the intermediate result as long as it is within the bit value, so that the constraint of a bit data only needs to occupy one calculation and the constraint of the highest bit value in the future. If it is not designed in this way, it is obvious that such a circuit is too big for practical application. With these auxiliary structures, it is possible to formally construct the calculation method that every user input data is called the intermediate node, so it is actually necessary to calculate. The length of the array is as follows. It is relatively simple to construct the whole leaf node. It is only necessary to convert it into intermediate nodes. The values of each intermediate node are related to the values of the left subtree and the right subtree of the next layer. Finally, the calculated results of the intermediate nodes are put into the array. Next, we use the construction to prove that a user really deserves it. Therefore, we first need to formulate specific indexes and generate the required data structure. 比特币今日价格行情网_okx交易所app_永续合约_比特币怎么买卖交易_虚拟币交易所平台

我们可以通过设置 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

联系我们：hello.labs@antalpha.com