摘要

人类尊严要求向公众隐藏个人信息，例如医疗和法医数据。但旨在保护隐私的保密面纱也可能被负责数据的机构滥用来掩盖谎言和欺骗，不公正地伤害公民并削弱对中央机构的信任。
零知识（ZK）证明系统是一种巧妙的密码学解决方案，可以解决个人隐私理想与机构完整性之间的紧张关系，以不损害前者的方式强制实施后者。公共信任要求 ZK 系统具有透明度，这意味着它们的建立不依赖任何受信任方，并且没有可能被强大团体利用来提供虚假证人的陷门。对于要与大数据一起使用的 ZK 系统，公共验证过程必须在数据大小上呈次线性扩展。透明的 ZK 证明可以比数据大小指数级更快地进行验证，这一点在 20 世纪 90 年代首次被描述，但早期的构造是不切实际的，并且迄今为止在代码中实现的 ZK 系统（包括 ZcashTM 等加密货币使用的系统）既实现了透明性又实现了指数级增长。同时，一般计算的验证加速。
在这里，我们报告了透明 ZK 系统（ZK-STARK）的首次实现，其中验证的扩展速度比数据库大小呈指数级增长，而且，验证中的这种指数级加速是在有意义的顺序计算中具体观察到的，如下所述。我们的系统使用了交互式预言证明 (IOP) 的多项最新进展，例如用于纠错码的“快速”（线性时间）IOP 系统。
我们的概念验证系统使警方能够向公众证明总统候选人的 DNA 档案没有出现在警方维护的法医 DNA 档案数据库中。该证据由警方生成，不依赖于外部受信任方，并且不会透露有关数据库内容或候选人个人资料的进一步信息。特别是，DNA 信息不会透露给警方以外的任何一方。证明的长度小于 DNA 数据库的大小，并且验证速度比直接检查该数据库所需的时间更快。

1, 介绍

机密数据集计算完整性的可扩展验证 这里解决的问题最好通过一个假设的例子来说明：假设负责国家法医 DNA 档案数据库 (D) 的警察 (P) 声称 DNA 档案 (p)即将被任命且涉嫌腐败的总统候选人的信息并未出现在 D 中。加密协议能否在不损害 D 或 p 的情况下，不依赖任何外部可信的情况下，说服持怀疑态度的公众相信这一说法？一方（例如首席大法官），并拥有“合理”的计算资源？
DNA 谱匹配 (DPM) 示例是更普遍问题的特例。对数据集 (D) 执行计算 (C) 的一方 (P) 可能有动机误报正确的输出 (C(D))，从而引发计算完整性 (CI)1 问题 — 确保 P 确实报告 C( D）而不是对 P 更有利的输出。当数据集 D 公开时，有兴趣验证 CI 的任何一方（V）都可以在 D 上重新执行 C 并将其输出与 P 报告的输出进行比较，就像客户可能会那样检查餐馆账单，或者新的比特币节点将验证其区块链[86]。这种简单的解决方案无法扩展，因为验证者 (TV) 花费的时间与执行程序 (TC) 所需的时间一样大，并且 V 必须读取完整的数据集 D。基于加密哈希函数的承诺方案 [33]通常用于计算大型数据集 Dt 的时间 t 时的状态的短不可变“指纹”cmt [33]。通常，与 Dt 相比，cmt 的长度2可以忽略不计，并且可以很容易地发布在区块链上作为公告3。因此，我们寻求的 CI 解决方案应该具有可扩展的验证，其中验证时间和通信复杂性大致像 log TC 和 |cmt| 一样扩展。 （cmt的位长），而不是像TC和|Dt|；至少验证时间/通信应严格小于 TC 和 |Dt|。
当数据集 D 包含机密数据时，简单的解决方案将不再能够实现，并且负责 D 的 P 方可能会在保密的面纱下隐藏对计算完整性的侵犯。对机密数据实施 CI 的流行方法依赖于“受信任方”，例如审计师或会计师，代表公众自然地验证计算。该解决方案仍然不提供扩展，就像数据公开时一样。更糟糕的是，它要求公众信任第三方，这在协议中造成了潜在的单点故障，因为该第三方（在可以商定的范围内）可能会被恶意方破坏、贿赂或胁迫。
零知识（ZK）证明和论证系统是自动化协议，取代人类审计员，作为保证机密数据的计算完整性以实现任何高效计算的一种手段，消除腐败并降低成本[59]。用于计算 C 的 ZK 系统 S 是一对随机算法，S = (P, V)；证明者 P 是用于证明计算完整性的算法，验证者 V 检查此类证明。 S 的完整性和可靠性意味着 P 可以有效地证明所有真理，但无法说服 V 任何错误（概率几乎可以忽略不计）。 20 世纪 90 年代初讨论的具有用于一般计算的可扩展验证器的 ZK 系统的第一个理论结构是基于概率可检查证明 (PCP) 的。 （有关最近的替代 ZK 构造，请参见第 1.3 节。）著名的 PCP 定理 [7,6,3,2] 在证明者构造证明 (TP) 所花费的运行时间与运行时间之间提供了令人惊讶的权衡。验证者检查所消耗的时间（TV）；这种权衡意味着与原始计算时间 (TP = TO(1)) 相比，证明时间呈多项式增加，而验证时间则呈指数减少 (TV = logO(1) TC)。
基于 PCP 定理 (ZK-PCP) [74,85,49,75,71] 的 ZK 系统具有三个额外的优势，这对于公众对计算完整性的持续信任至关重要。首先，这些结构的安全性所依据的假设——用于交互式解决方案的抗冲突散列函数[74]的存在，以及用于非随机解决方案的对随机函数6（“随机预言模型”[50]）的共同访问。交互式的[85]——不知道是否容易受到大规模量子计算机的攻击；我们将此类解决方案称为后量子安全。量子计算机规模的预期增长 [43] 以及美国国家标准与技术研究院 (NIST) [37] 等对后量子加密协议的呼吁，凸显了后量子安全 ZK 解决方案的重要性。
其次，ZK-PCP 是知识证明（POK）系统，或者，当如上所述实现时，知识论证（ARK）系统[33, 9]。非正式地，在 DPM 示例的背景下，ZK-ARK 是一种证据，可以让公众相信警方使用了“真实”数据集 Dt 和总统候选人 DNA 图谱 p，其承诺之前已宣布（参见定义 3.3）。
第三，也是最重要的，ZK-PCP 是透明的（或“公共随机性”7），这意味着验证者使用的随机性8是公开的；特别是，与较新的 ZK 解决方案（包括 ZcashTM 加密货币使用的解决方案）相比，设置 ZK-PCP 不需要外部可信设置阶段（参见第 1.3 节）。透明度对于持续的公众信任至关重要，因为它严重限制了即使是最强大的 P 方滥用系统的能力，因此只要可观察的宇宙中存在不可预测的东西，透明的系统就是公众可以信赖的系统。
总而言之，ZK-PCP 是确保公众对 CI 而非机密数据的信任的绝佳方法，并具有六个核心优点：

• (i) 透明度，
• (ii) 通用性 - 适用于任何高效计算 C，即使它需要辅助（并且可能需要辅助）机密）输入，如上面的 Dt，
• (iii) 机密性（ZK）——不损害辅助输入，如 Dt，
• (iv) 后量子安全，
• (v) 知识证明/论证和
• (vi)可扩展验证。

尽管 ZK-PCP 自 20 世纪 90 年代中期以来就已为人所知，但迄今为止还没有在代码中实现，因为用最近的一项调查[110]的话来说，“PCP 定理（尽管有渐近改进）产生的证明太长了而且很复杂，生成和检查它们需要数千年的时间，并且需要比宇宙中原子更多的存储位。”因此，最近用于一般计算的 ZK 系统的实现工作（在第 1.3 节中进行了调查）集中于无法实现所有 (i)-(vi) 的替代技术，尽管有些技术在实践中对于具体电路尺寸和摊销计算非常有效。