零知识证明:什么是zk-STARKs以及它们是如何工作的？(zk-STARK V2)

一、什么是储备证明和零知识证明？

1、什么是储备证明（PoR）？

储备证明（PoR），简单来说，就是加密货币交易所向外界证明“我有足够的钱来覆盖所有用户的余额”的一种机制。核心目的是让用户相信平台没有偷偷藏着什么负债，从而建立信任。最直接的做法是把交易所持有的资产总额和所有用户的余额列表都公开出来，这样每个人都能自己去核对：

• 交易所持有的用户资产总量，应该等于每个用户资产余额的总和。

• 每个用户的总余额都是正的，资产能够覆盖负债，确保每个用户都处于净资产为正的状态。

• 交易所公布的总价值必须包含每一位用户，因此每个用户都应该能验证自己的净值是否被正确计入。

但这里有一个明显的矛盾：如果把所有余额都亮出来，用户的隐私就全没了。所以需要一种既能证明平台有足够资产，又不用暴露用户具体信息的技术——这就是零知识证明（ZKP）的用武之地。

2、什么是零知识证明（ZKP）？

零知识证明（ZKP）是一种安全技术，它允许交易所在不透露任何额外信息的前提下，证实某个声明的真实性。就我们的场景而言，我们希望在不泄露每个用户具体账户细节的情况下，证明平台有足够的资金。

目前大多数ZKP方案分为两大类：

• zk-SNARK

• zk-STARK

我们选择的是zk-STARK，因为它更安全，底层的安全假设也更少。这篇文章会重点解释，我们如何利用zk-STARK在保护用户隐私的同时，实现偿付能力的证明。在深入之前，先了解几个基本的ZKP概念会很有帮助，比如电路、默克尔树和承诺。如果是刚接触这些术语的读者，网上有很多入门资源可以参考。

二、zk-STARK是如何工作的？

具体做法是：我们把每个用户账户的哈希值作为“叶子”，构建一棵默克尔树。每个账户里记录的是各种代币（比如BTC、ETH）的美元余额。为了处理这些余额，我们会把余额拆分成每个代币对应的非负权益（Equity）和债务（Debt）。这样所有数据就都变成了正数，计算起来更方便，也能减少出错的可能。

举个例子：

• 如果用户的BTC余额是A，那么BTC权益就是A，BTC债务就是0。

• 如果用户的ETH余额是-B，那么对应的权益就是0，债务就是B。

接下来，用这些账户值作为叶子构建一棵默克尔树。树根（Root）就成了代表所有用户余额的一个唯一值。每个用户可以通过一条默克尔路径（Merkle Path）来证明自己的账户是树的一部分，这条路径展示了他们的账户是如何连接到树根的。

我们还会公布所有用户所有代币的总资产和总债务。然后，创建一个零知识证明，核心要验证两件事：

• 求和证明
  ：默克尔树中的资产和债务价值确实正确地加总了。

• 非负证明
  ：每个用户的总资产都大于他们的总债务，没有人是“负资产”。

要验证这么大一棵默克尔树，一台机器的算力显然不够一次性搞定整棵树。为了攻克这个难题，我们把账户拆分成一个个较小的组，称为“批次”（Batch）。每个批次用独立的“批次电路”单独处理，电路负责检查默克尔树底层的部分。

批处理不仅让计算变得可行，还能让这些检查并行跑起来（同时处理多个批次）。拿到每个批次的结果后，再通过另一层叫做“递归电路”的电路，把所有批次的结果组合起来并逐层验证，直到最终证明整棵默克尔树都是正确的。

1、什么是批处理电路？

批处理电路每次接收1024个账户（acc0, acc1, …, acc1023）作为输入，然后生成3个主要输出：一个哈希值（hbatch），一个总资产价值（ebatch），和一个总债务价值（dbatch）。它主要负责检查以下内容：

• 每个账户的美元权益总额都大于其债务总额。

• ebatch 是这些账户中所有美元计价权益的总和。

• dbatch 是这些账户中所有美元计价债务的总和。

• hbatch 是根据账户哈希构建的默克尔树的根。

• 在计算 ebatch 和 dbatch 的总和时没有发生溢出。

2、什么是递归电路？

递归电路则从低层电路中获取64个不同的证明（π0, …, π63）、哈希值（h0, …, h63）、权益值（e0, …, e63）和债务值（d0, …, d63）作为输入。它把这些输入整合起来，产生3个输出：新的哈希值（hrecursive）、总资产（erecursive）和总债务（drecursive）。它的检查内容包括：

• 64个证明中的每一个都是有效的。

• 每一个来自下层电路的证明（π0, …, π63）都有效。

• erecursive 是 e0, …, e63 的总和。

• drecursive 是 d0, …, d63 的总和。

• hrecursive 是 h0, …, h63 串联后的哈希值，即 hrecursive = Hash(h0 || h1 || … || h63)。

• 在计算 erecursive 和 drecursive 的总和时没有发生溢出。

3、批处理电路和递归电路之间的关系是什么？

下图展示了批处理电路和递归电路是如何互相连接并传递数据的。需要注意的是，为了便于说明，图中复制了多个电路实例，但在实际实现中，每一层我们只使用一个电路。

我们的默克尔树结构有些特别之处：在底部10层，每个父节点有2个子节点；而在上层，每个父节点则有64个子节点。这是因为批处理电路负责处理最底层，而递归电路负责处理上层结构。下图用了一个“Alice”的例子，展示了默克尔树以及她的默克尔路径（用绿色标出）。

三、zk-PoR版本2的进展

我们的zk-PoR版本2相比之前版本，有了几个比较明显的进步。

• 更高的效率
  ：新版本的运行速度比旧版本快了整整50倍。在单台10核机器上只需3小时就能完成，而之前的版本在9台64核机器上也需要36小时。提速的关键在于采用了Plonky2框架，它能把Rust编写的电路高效编译成机器语言，取代了之前比较慢的Python脚本。我们还对Plonky2进行了优化，让部分计算跑在GPU上，进一步减少了30%的处理时间。

• 更好的可审计性
  ：在版本2中，我们使用了更高级的框架来处理那些复杂的加密细节，这让代码变得更清晰、更易读，出错的概率也大大降低。

• 简明证明
  ：V2的证明大小（约500KB）只有V1（约1.2GB）的0.05%。得益于递归方法，证明可以被反复聚合、压缩成一个非常小的证明文件。

四、如何执行准备金证明（PoR）的自我验证？

如果你想亲自确认自己的资产余额是否被包含在zk-STARK默克尔树的叶子中，可以按照以下步骤操作：

1、登录你的OKX账户，进入“资产”页面，选择“PoR报告”。

2、点击“详细信息”查看审计数据。

3、选择“复制数据”来获取手动验证所需的数据。

4、复制数据后，打开一个文本编辑器（比如记事本），粘贴JSON字符串并保存为文件。文件名必须以“_inclusion_proof.json”结尾。这个JSON字符串包含你的账户余额和默克尔路径的快照。将文件保存在一个新文件夹里。

5、打开文本编辑器（比如记事本），粘贴JSON字符串并将其保存为文件。文件名必须以“_inclusion_proof.json”结尾。将文件保存在新文件夹中。

• JSON字符串包含账户余额和Merke路径的快照。

• JSON文本格式大致如下：

{"sum_tree_siblings":["9ffb169fecf075e203edca2af65e4c69fa4331d13ac75ccae4cd5b990c91b675","7149661a789763cb61293ebf5d8bdd5570e79ee203738f87a444c79642b89a79","788aac9e392fa62bc3f79c98c7afd7bb41ee7d5bd496876cd0580080f19e002f","e828a44d345e6799e232aabc57cb2b92986ee1c52b65344d83e79d84b4b571b7","6c0675de9cd6b2be1abd6a98260e7ea776492c4aa9aadf31086f23452cb7c48d","2dfe3aadb5ac00ee0b1110ee8c313afdee85d9f9c62904d6ee79c8f02354d80a","5068ae26192587432892a6de8b54ea25a8aafd1c010ab5e67b55b2c30c6257fa","a1bb026ec9f3d8a1fa1b6f498c40ed8b117a57e1af9816d08d9135ab4fe43a60","119dfcd214191405b7f7f7c7091b89196c0cae818bfcd8252a48f20d9cf3c378","4d9403482ca177c669df34a60bb2afab7a18097012d0b70703c8e59258cdfee6"],"recursive_tree_siblings":[{"right_hashes":["e041eaa366259f873e9e1477aac77362f4b1b460c2d5e1c14907fa9288d66cff","b45a8c503e649ff39543a918996b06fc65f4df9b61d071b22f7342f94862c9be","e00ec1225dfe6b7e950f6b9b8e9d1121bf17eb60c444fd7191b861a2ddddad23","c02c12beb73c03f996508cdce7bef927f0aa8b77ebd899f6a75df83de9d4022e","d36b95f14c5fd5bfaf1347e3177340e2fc9475a77b852321b80527132e7d539c","c0b9770178e70a7bba4ac8aeaadab2bcb2ae7f90d0f678bd463f2c42ff4f4a7b","fab5e7c6f7f8bc6d51f515c5db235cc1ebe987adee8c19c9bc7313e9e266d72c","b3884fb88fc95949c78ca8867cfa9e8a3c4c59fa1a48d8371f7fbfbebda0acfd","0c6da9bdbd40065f92ddaa45297670f2f0bffedb74020c5d5752e70d8b507b77","left_hashes":["1101beee3c6a36a168ceee9d43fcf6cb6de7e5c87ed4d22cd0308c9870d17839","d40a8e9eb4c873996ec515600def480eaa9378ca8481a7bcdf5f77725dbec4ae","63b12566ba8473f502386e92d500664cb63683dca6c26593378dcc9715257b77","166440a8ccbfbc1ce6ec5efaf8bc0b25e1bf692fa972e2729e45ce709d1d35a3","724451ad1d937fc47de5ede930d159dce78093d5e6a1f2e698452f8a29b4de3a","081a88f12d4e23173a1bf5038d4a9413cc92dd421c92261065de06492b5010ec","a76dbb1d4c393539b9546f4460d50ebc7582748d7de63c62c463b793c55bac7c","91e6c21de3f4060e1bd864131a570af42de31bbcd84a5afcbbc8fedcbf806002","fad08eca5bfdc5f37d39eabb44c2216afc6498afcb6b913d72586eaaf132a572","d39b06fe28387ba8045e2b2f95e90613916beef4f79df7961514e6e4cbfd07fa","81d07e300a116a0e4fcb56c39715c5fd5921abe8d10329b07c3f33d417b70ca8","7b72a7e62a45c9958a8a55eec2ba47352f2af701bacba098668589f6a3ce0423","8766bc64c38c2bb4188d89de0e732bca103daaed0c779cba9a8b191e24b51c9c","fa57ae4409e46c605f3cbfd01dfd9ccebc86cbd765cdc067206cb9367832442f"]}, ...... "index":9583119,"account":{"id":"50f5f08cc5036e15a541c64ac4ac6d2d9aa8ddab1ec32ed58b10e6ed3edfad59","debt":["0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"],"equity":["8412384","9386185","45265193","0","0","8751","3824171","2716990","0","313671","28319","0","0","0","41261","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","142353","0","0","0","0","0","4435","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","662","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","993","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","25132","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","305","0","0","0","0","0","0","0","0","6141","0","0","0","0","0","0","0","0","0","0","0","5511","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"]}

6、下载OKX开源验证工具：zk-STARKValidator。

7、将zk-STARKValidator和上一步保存的JSON文件放在同一个新建的文件夹里。在我们的示例中，我们把工具和数据文件都放在了名为“por_inclusion_proof.json”的下载文件夹里，如下图所示：

8、运行zk-STARKValidator；它会自动识别并处理与你保存在同一文件夹中的JSON文件。

9、检查运行结果：

如果验证通过，界面会显示“约束验证通过”的提示：

如果验证失败，则会显示“约束验证失败”的提示：

五、如何验证zk-STARK总余额和非负约束？

如果你想进一步验证交易所声称持有的总资产是否真实，以及是否真的没有用户持有负净资产，可以按下面的步骤来操作：

1、前往“储备证明”页面，选择“责任报告”。

2、下载zk-STARK文件，并将其保存在一个新文件夹中。

3、解压下载的文件，提取出“sum_proof_data.json”文件。

4、下载OKX开源验证工具：zk-STARKValidator。

5、将zk-STARKValidator和“sum_proof_data.json”文件放在步骤2中创建的同一个文件夹里。在我们的示例中，我们将工具和数据文件都放在了名称为“储备证明”的下载文件夹中，如下图所示：

6、运行zk-STARKValidator；它会自动处理与你保存在同一文件夹中的求和证明数据文件。

7、检查运行结果：

如果验证通过，会显示“Total sum and Non-negative constraint verification passed”的结果：

如果验证失败，则会显示“Total sum and Non-negative constraint verification failed”的结果：