零知识证明：zk-STARK 是什么？它如何运作？
1. 什么是 zk-STARK？
zk-STARK 储备金证明系统运用了一种称为 STARK 理论的复杂数学模型。zk-STARK是"Zero-Knowledge Scalable Transparent Arguments of Knowledge (零知识可扩展的透明知识论证)"的缩写，是一种加密证明技术，由以太坊发明人维塔利克-布特林 (Vitalik Buterin, 即"V神") 的理论发展而来，旨在通过区块链确保计算的完整性和隐私。本文将介绍 zk-STARK 的原理并解释一般的数学概念，如果您想深入了解，可以参考以下资料：
STARK Math: The Journey Begins
https://vitalik.eth.limo/general/2017/11/09/starks_part_1.html
zk-STARK 如何运作？
图1：zk-STARK 储备金证明执行记录表和默克尔树
第一步：设定约束条件
为了证明平台持有的用户资产，我们先提出三项陈述：
陈述 1： 平台每名用户资产价值的总和是正确的，包括每种数字货币的价值和全部用户的净资产价值。
陈述 2： 平台没有通过伪造净资产为负的虚拟用户，来减少平台持有用户资产价值的账面数字 (只有当单一用户的净资产大于 0 时，才允许存在负余额) 。
陈述 3： 平台持有的用户资产总和等于每一名用户的资产之和，因此每个用户都可以验证其净资产是否包含在平台持有的总资产中。
为了验证上述三项陈述，我们需要先构建约束条件，例如：
**陈述 1：**余额总和约束（验证余额总和计算结果是否正确）
uts: 用户记录体量 (user trace size)，即每名用户的数据记录表的行数
sum: 总用户余额
N: 用户数量
**陈述 2：**非负约束（验证总资产是否为正）
陈述 3：包含性约束 （验证是否所有用户的资产都已包括在结果之内）
根据上述约束条件，我们创建一个记录表，通过抽样检查来提交和验证余额总和和非负性。以下是构建记录表的方法（举一个简化的例子，假设有 3 个用户，总资产价值小于 4^6 = 4096 USD）：
**1）**首先创建一个 32 × 5 的表格，并将用户的资产价值和 ID 填入第
行，其中 k % 8 = 6，且 
。每 8 行是一个区域，用户资产信息现在在每个区域的倒数第 
个位置。假设第一个用户的余额为 0，因此我们可以将其公布，以证明资产价值总和的计算不是从负值开始的。
2）将用户的资产价值逐个累加，将结果填入第 
行，此处 k % 8 = 7，且 ，即每个区域的最后一行。
3）从每个区域的倒数第个位置开始，逐行将每个用户的总价值除以 4 并向下取整，进而通过检查每个区域的前几行是否为零来确保每个用户的净资产价值非负。如果某个用户的净资产价值为负，对应该用户区域的第一行将不为零，因为在有限域
中，负数 *(-x)*会变成 (p - x)，这是一个非常大的正数。
4）为每名用户配对一个随机数，并在表格中的空白部分填入 0。
第二步：低次多项式扩展 利用上述多项式约束，我们可以得到一个长度为 uts * N 的计算记录多项式。出于安全考虑，我们在一个更大的评估域上进行多项式承诺，扩展因子为 extension_factor。 在上述情况下，我们可以从 I(x) 计算出一个多项式 p(x)。当我们使用扩展因子 8 时，我们将在 p(x) 上计算另外 32 * (8-1) 个点。 由于两个不同的 D 次多项式最多共享 D 个点，因此具有有效多项式（满足上述约束条件）和 D 次假多项式（不满足上述约束条件）的多项式对最多共享 D 个点。这意味着假多项式有
的机会通过随机抽样检查。如果我们进行 n 次抽样检查，机会会降低到
。
我们默认将 extension_factor 设置为 16，将抽样检查默认次数设置为 16，因此安全级别将为 80 位。
第三步： 多项式承诺 我们用计算记录和相应的用户余额、用户 ID 以及每行对应约束多项式的值来计算哈希值，并生成默克尔树 (Mekel tree)。默克尔树根是多项式的承诺 (commitment) 值。
第四步：生成抽样证明 使用默克尔树根作为随机源对数据进行抽样，为避免泄露计算记录数据，在抽样过程中将会避免使用序号为 k * extension_factor 的数据，并生成相应的默克尔证明路径。
然后进行抽样检查，检查承诺的多项式是否是满足第一步中列出的约束条件的有效多项式。如第二步所述，抽样检查的次数将影响结果遭到篡改的可能性。
第五步：生成低次证明
我们可以通过抽样检查来控制结果遭到篡改的概率。但如第二步所述，我们需要确保验证的多项式次数不超过有效多项式的次数。
为了提高证明效率，我们将所有约束多项式线性组合成一个多项式，并为其生成低次证明。组合系数也是使用默克尔树根作为随机源生成的。
例如，如果我们想证明 p0(x)，p1(x) 和 p2(x) 不超过 D 次，我们可以从第三步生成的默克尔树根中生成 2 个随机系数，并计算线性多项式 l(x)：
k0 = hash(root + "0")
k1 = hash(root + "1")
l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)如果可以证明 l(x) 不超过 D 次，则 p0(x)，p1(x) 和 p2(x) 中任何一个的次数超过 D 的机会将接近于 0 。
第六步：总余额验证 首先验证第五步生成的低次证明，然后在第四步生成的抽样数据上进行进一步的开放验证。首先验证数据是否与多项式承诺一致，其次验证数据是否满足第一步中构建的约束条件。最后，验证低次测试多项式的组合系数。
第七步：生成包含性证明 为了证明每名用户的资产均包含在交易持有资产总额中，我们提供用户的计算记录、用户余额、用户 ID 以及与用户序号相对应的随机数，以及相应的默克尔路径。 例如，在图1的红色方框中的数据将被提供给 ID 为 k 的用户作为包含性证明。 证明示例：
{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
"bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43"
]
}
}第八步：用户验证包含性证明 用户可以检查他们的余额、ID，计算与他们序号对应数据的哈希值，并使用通过默克尔路径验证叶子节点上的哈希值。
2. 如何自行验证储备金证明？
2.1 验证 zk-STARK 包含性约束
验证理论
按照 STARK 程序，我们将计算所有用户资产的执行记录表，并将每个用户的信息加密生成哈希值记录表，作为默克尔树的叶子节点，然后将叶子节点提交到将在每轮储备金证明公布的默克尔树根中。 为了验证您的资产是否包含在树根中，我们将为您提供默克尔路径进行验证。您可以通过将您的资产信息加密生成哈希值来计算您的叶子节点，然后验证您的叶子节点是欧易公布的默克尔树根的有效叶子节点。 例如，在图1中，ID 为 id_k 的用户将计算 hashk = hash("20" + "15" + "5" + "id_k" + "99821")，红色方框中的其他数据将是默克尔路径验证，用户可以通过欧易提供的开源工具进行此验证。 由于默克尔数据树的叶子节点是经过加密生成的哈希值，您的任何私人信息都不会泄露给他人。
如何验证：
1）要验证您的账户资产余额是否以 zk-STARK 默克尔树叶子节点的形式包含在树根中，请登录您的欧易账号，前往"审计" 页面查看近期审计文件，点击"详情"查看审计数据。
2）点击"复制数据"获取手动验证所需的数据。
3）点击"复制数据"后，打开记事本或其他文本编辑器，粘贴刚刚复制的 JSON 文本并保存为文件。JSON 文本包含您的账户余额和默克尔路径快照，粘贴完成后请将文件保存在一个新建文件夹。
JSON 文本如下所示：
{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
"bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43"
]
}
}4）下载欧易的开源验证工具zk-STARKValidator
5）将 zk-STARKValidator和 JSON 文件保存在同一个文件夹。在下方示意图中，我们把验证工具和数据保存在"下载"文件夹中，命名为"proof-of-reserves"：
6）打开 zk-STARKValidator 并自动运行保存在文件夹中的 JSON 文本文件。
7）查看结果
- 如果验证通过，执行结果 "Inclusion constraint validation passed" 将显示如下：
- 如果验证失败，执行结果 "Inclusion constraint validation failed." 将显示如下：
2.2 验证 zk-STARK 总余额约束和非负约束
如何验证：
1）如需验证欧易持有的资产是否真实，以及没有用户持有负资产，请前往"审计文件" 的"账户余额文件" 部分下载 zk-STARK 文件，并保存至新建文件夹。
2）将下载到的文件解压缩，您将获取一个名为 "sum proof data" 的文件夹，包括一个聚合证明文件夹和数千个分支证明文件夹，每个文件夹均包含 "sum_proof.json" 和 "sum_value.json" 两个文件。
3）下载欧易的开源验证工具zk-STARKValidator
4）将zk-STARKValidator 和 "sum proof data" 文件夹保存在第一步新建的文件夹中。在下方示意图中，我们把验证工具和数据保存在"下载"文件夹中，命名为"proof-of-reserves"：
5）打开 zk-STARKValidator 并自动运行保存在文件夹中的"sum proof data"文件。
6）查看结果
- 如果验证通过，执行结果"Total sum and non-negative constraint validation passed"将显示如下：
- 如果验证失败，执行结果 "Total sum and non-negative constraint validation failed" 将显示如下：
