zk-SNARK如何改进币安的储备金证明系统
要点
2022年11月，币安发布应用默克尔树密码学的储备金证明系统，用户可验证其持有的资产。
现在币安采用zk-SNARK（一种零知识证明协议），改进了该解决方案。
用户如今能以安全、私密的方式验证账户的总净余额是否为非负数，以及用户资产是否为币安公布的用户资产总净余额的一部分。
现在深入了解一下币安新储备金证明方案。此方案结合zk-SNARK和默克尔树算法，为用户提供全新的、已改进的验证币安储备金的方式。
币安开发团队在过去的几个月中一直努力构建先进的偿还能力证明解决方案。FTX暴雷引发了席卷整个行业的信任危机，此时这类工具对于中心化数字货币交易平台来说尤为重要。币安以1:1的比例持有所有用户资产（以及储备金），币安重振行业信任度的计划中很重要的一部分就是找到让客户顺利验证以上事实的方法。
2022年11月，我们发布应用默克尔树密码技术的储备金证明系统，用户可验证在币安持有的资产。币安用户资金的透明度顺利提高，但该方案的初步设计有以下两个缺点：
为保护用户隐私，默克尔证明中的叶节点代表用户持有的哈希值，因此，默克尔根无法反映叶节点的总余额。
若被验证储备金的实体在默克尔树下添加余额为负值的假账户，那所需的储备金总值就会变少。下图来自Vitalik Buterin的博客，展示了此种恶意默克尔树算法（尽管在这种情况下，根节点反映了所有叶节点余额的总和，可能会涉及隐私问题）。
现在，我们有一种方案可以弥补这些缺点、改进币安储备金证明系统。应用零知识证明协议zk-SNARK后，我们可以证明：
默克尔树的所有叶节点都是币安公布的用户每项资产的总余额的组成部分。
默克尔树中不含总净余额（用户持有的所有资产的总美元价值）为负值的用户。
关于负余额和交易的解释
币安提供杠杆、质押借币和合约交易产品，因此每位用户的加密货币资产余额可能都由资产和负债组成。用户某一加密货币资产可能为负值，但他们的所有加密货币资产的总净余额不应为负值（因为所有借币都是进行了相应抵押的）。
假设一个场景：Alice在币安充值了10,000 BUSD，然后使用4,000 BUSD作为抵押借出了2 BNB（以1 BNB= 1,000 BUSD的利率，假设币安总是超额抵押）。下表为Alice的资产负债表。
然后如果Alice用1 BNB与Bob（他也存入了10,000 BUSD）交易1,000 BUSD，交易成功后他们的资产负债表即为：
此时，Alice的BNB余额为-1，这不是默克尔树中的有效节点，并且只是BNB这一种资产的状况。但Alice的总净余额仍为10,000 BUSD。
另一个挑战为币安庞大的用户规模。币安有数千万用户，且有些用户可能在我们平台上拥有超过300种加密货币资产，而我们必须找到一种行之有效的方案为用户提供用户证明和zk-SNARK证明。
总之，我们希望在合理的时间范围内提供事实证明：
每位币安用户的资产都是币安在快照中公布总用户余额的一部分。用户可以使用区块链浏览器（像以太坊钱包用的Etherscan或BNB Chain钱包用的BscScan），根据币安持有的资产地址来验证币安公布的总用户余额。
每位用户的总净余额都非负值，也就是说，币安无法创建余额为负值的假账户来人为地减少公布的储备金数值。
什么是zk-SNARK？
在我们深入研究此解决方案之前，先简要概述一下零知识证明机制。zk-SNARK一类的零知识协议是一方（证明者）向另一方（验证者）证明证明者已在特定限制下使用特定输入准确地执行了特定计算，无需公开输入。计算比较耗时，但这一基本数学机制可以快速安全地帮验证者评估证明。
证明者（币安）定义一组其打算证明的计算限制。限制是在可以用高级编程语言（此处是gnark的分叉版本）表达的电路定义。
然后证明者进行繁重的计算，将所有用户的ID和资产负债表进行哈希运算，生成满足预先设定的限制的计算证明。为此，证明者用计算追踪（见证）公共或个人输入。
验证者（用户）获取证明，并使用电路的公共输入对其进行验证，确认计算是在满足所有限制的情况下准确执行的。与证明时间相比，验证计算花费的时间极少。如果证明者不在预先定义的电路上生成证明，则无法生成可通过验证的有效证明。
深入了解zk-SNARK的本质，请参看此系列文章。
我们的解决方案
升级后的储备金证明解决方案的基本建构仍是默克尔树。上面的示例可以展示为：
除默克尔树外，我们还维持了全局状态，该状态代表每位币安客户持有的每种资产的总净余额列表。
为证明我们的储备金，我们会为默克尔树的构建生成zk-SNARK证明。对于每位用户的余额组合 - 默克尔树的叶节点，我们的电路将确保：
该用户的每种资产的余额都包含在上述全局状态列表中。
用户的总净余额不是负值。
默克尔树根的变化将在此次用户信息更新到叶节点后生效。
每次证明储备金总量时，我们都会发布：
1.默克尔证明：每位用户的哈希值（如上图片中的蓝色节点是Alice的哈希值）。
2.zk-SNARK证明和所有用户电路的公共输入（每种资产的总净余额列表和 默克尔根）。
验证默克尔证明后，用户可以确保自己的资产负债表包含在默克尔树跟中。验证默克尔证明后，用户可以确保默克尔树的构建满足电路定义的限制。
该解决方案的安全性在很大程度上依赖证明密钥和验证密钥的设置。我们正在研究密钥的去中心化设置。现存的去中心化可信设置仪式中，以太坊仪式是很好的例子。我们即将拥有多方计算(MPC)解决方案，使设置去信任化。
性能
由于应包含其余额的币安用户数量庞大，无法一次性获得涵盖所有用户的默克尔树构建的单一证明。应对这一问题的解决方案是将用户分为每批864人的批次，可缩小电路规模和并行证明程序规模。
每组有864位拥有350种不同资产的用户，假设每种资产余额范围在【0, 2^64-1】之间。若服务器为32核128GB，生成zk证明约需要110秒，证明验证的时间小于1毫秒。
币安将同时启用1000个服务器，可在2小时内为所有账户生成证明。运行证明者服务器1小时的成本约为0.56 USD，因此生成涵盖所有用户的zk证明大约需要1000 USD。
结论
我们将在后续的储备金证明公告中为用户提供此次新解决方案生成的第一次迭代证明。此外，我们还将开源用户数据处理器、证明者、电路和验证者，以便中心化交易平台可以轻松依照我们的模型为其用户和资产生成证明。
我们希望此举能让数字资产行业的透明度提升到新的高度。我们也在研究Vitalik博客中提到的效率更高的解决方案，希望可以实施此方案，以更低的成本更频繁地提供证明。
这是zk-SNARK的第一版，期待收到社区反馈，帮助我们继续改进系统。