零知识证明在区块链中的应用综述_宋英齐.pdf

第 21 卷第 4 期2022 年12 月广州大学学报(自然科学版)Journal of Guangzhou University(Natural Science Edition)Vol 21No 4Dec2022收稿日期:2022-10-08;修回日期:2022-10-15基金项目:国家自然科学基金资助项目(12126301，12231015，61972032);国家重点研发计划资助项目(2018YFA0704703)作者简介:宋英齐(1996)，男，博士研究生 E-mail:vinsanity-S pku edu cn*通信作者 E-mail:fengrq math pku edu cn引文格式:宋英齐，冯荣权 零知识证明在区块链中的应用综述J 广州大学学报(自然科学版)，2022，21(4):21-36文章编号:1671-4229(2022)04-0021-16零知识证明在区块链中的应用综述宋英齐1，冯荣权2*(1 中国科学技术大学 数学科学学院，安徽 合肥230026;2 北京大学 数学科学学院，北京100871)摘要:零知识证明是现代密码学中的基本理论之一，在现代密码学前沿具有广泛的应用场景。随着零知识证明的工业化 简洁非交互零知识的知识论证(zero-knowledge Succinct Non-interactive Argument of Knowl-edge，zk-SNAK)的诞生，零知识证明在区块链领域得到了强有力的发挥，改进了早期区块链在隐私、效率和存储等多方面的问题，使得区块链能够在现代经济和社会中具有越来越显著的技术先进性。文章综述了零知识证明在区块链中，尤其是在公链项目中具有代表性的应用方式，旨在强调零知识证明等隐私计算技术是未来区块链与实体经济融合，并且发展良好区块链网络生态的必经途径。关键词:零知识证明;隐私计算;区块链中图分类号:TP 309 2文献标志码:AA survey on applications of zero-knowledge proof in blockchainSONG Ying-qi1，FENG ong-quan2*(1 School of Mathematical Sciences，University of Science and Technology of China，Hefei 230026，China;2 School of Mathematical Sciences，Peking University，Beijing 100871，China)Abstract:Zero-Knowledge Proof is one of the fundamental theories in modern cyptography which canbe widely used in application scenarios at the frontiers Along with the industrialization of zero-knowl-edge proof，the naissance of zero-knowledge succinct non-interactive argument of knowledge(zk-SNAK)，zero-knowledge proof has brought its superiority into full play in the domain of blockchain，ameliorating the existed issues of earlier blockchains in various aspects such as privacy，efficiency andstorage，and enabling blockchains to be increasingly technologically advanced in modern economiesand societies This paper makes a survey on some representative applications of zero-knowledge proofin blockchain，especially in public chain projects，and aims to emphasize that privacy-preservingcomputation technologies such as zero-knowledge proof are a necessary way to integrate blockchainswith the real economy and develop a good blockchain network ecology in the futureKey words:zero-knowledge proof;privacy-preserving computation;blockchain零知识证明(Zero-Knowledge Proof，ZKP)是现代密码学中一个极其重要的工具，它使得证明方在不泄露额外信息的前提下实现对某一事实的证明。零知识证明自 1985 年诞生以来，从交互式模型走向非交互式模型，为密码学和理论计算机科学带来了丰富的成果。由于其与现实情境十分贴合，具有丰富的应用场景，零知识证明迅速地进入了工程化实施阶段，并且不断在效率和安全性上得到改进。在 30 多年的发展过程中，零知识广州大学学报(自然科学版)第 21 卷证明已经具备了比较成熟的体系，并且能够与大量密码学工具配合使用。基于零知识证明本身的背景设定，它在以区块链(Blockchain)为代表的去中心化网络中的应用取得了丰富的成果。区块链是一个集合了密码学、分布式计算和博弈论等多学科交叉技术的领域，早期区块链所使用的密码学工具在真正意义上实现了区块链的本质特征，即去中心化。但是区块链距离设想中的能够得到广泛应用的去中心化信任机器(Decentralized TrustMachine)的目标还很远，需要有各项技术上的突破;其中隐私问题、效率问题和存储问题等尤为突出。在比特币、以太坊等传统的工作量证明(Proof of Work，PoW)共识机制的公链上暴露出一系列问题后，十几年来，科学家普遍借助零知识证明对区块链进行了一系列改进，在一定程度上成功解决了这些问题。如果能将零知识证明以及其它隐私计算技术发挥得当，那么理论上讲区块链可以突破各种问题的限制，合理地创建或消除信息不对称，从而搭载各种人们想要实现的功能，构建一个完善的去中心化生态。对于已有的零知识证明在区块链中的应用研究是必要的，因为这些具体应用以及相应问题的解决能够为后续技术突破提供借鉴，也能够为具体应用场景的设计提供现成的方案。当前，公链尚未在国内得到足够的认可，国际已有的公链也并没有在很大程度上影响到传统的中心化行业，究其原因是信任机制尚未成熟，与实体经济和大数据的结合还不够强，因此，区块链需要不断结合新的技术以寻求突破。1零知识证明及其工业化1 1零知识证明零知识证明这一概念最早见于 1985 年的文献 1，其目标是在一个双方收发信息的情景下，信息发送方为证明某个断言的真实性，以某种不暴露额外知识的方式与接收方进行信息交互。该文提出的收发双方利用交互式系统进行重复检验，以达成证明的方式实现了这一目标。由于此处交互性的存在，这样的零知识证明也称作交互式零知识证明。这种证明的模式一方面构建了一类证明系统，它能够让某项断言通过交互信息达成证明或证否，保护了信息接收方实现判断的基本权利，也能满足信息发送方实现证明过程的基本需求;另一方面，其不暴露信息本身内容的特点防止了信息发送方提供的消息被对方利用，保护了信息发送方隐私。交互式零知识证明是证明者 P 向验证者 V 试图证明某一断言 x 属于语言 L 的过程:P 具有足够的计算能力，使得当 xL 为真时，P 能够实现关于 xL 这一判断的证明;随后 P 与具有概率多项式时间计算能力的验证者 V 进行信息交互(自然也是多项式次数的)，让 V 在交互结束后判断 P 是否通过了证明。此处涉及到零知识证明定义中的 3 个重要性质:(1)完备性:如果 xL 为真，那么 V 判断 P 通过证明的概率可忽略地接近 1(完备性);(2)稳健性:如果 xL 为真，那么 V 判断 P 通过证明的概率是可忽略的，不论 P 具有多强大的计算能力;(3)零知识性:当 xL 时，任意的 P 和 V 可能的交互文本分布(在2 者的随机性下，交互文本构成一个分布)，与任何概率多项式时间的模拟机 M 在模拟 2 者的交互式证明时给出的模拟分布是计算不可区分的。交互式零知识证明的实现原理描述如下:假设 xL，则 P 具有能够证明 xL 的知识，此时 V 发出一个随机挑战，只有当 P 能够证明 xL 时，才能够给出应对该挑战的交互信息;换句话说，只有具有给出通过随机挑战的交互信息的计算能力才能够归约到 P 具有关于断言 xL 的证明能力。如果 xL，则 P 通常只能通过随机猜测给出回应，于是 P 能通过证明的概率随着挑战次数指数级的减小而减小。而根据随机挑战的正确回应，V 仅仅能够获得“P 具有证明xL 这一能力”的判断，但无法从 P 的证明本身获得任何额外知识。一个重要的事实是，当 LPSPACE 时，总存在关于L 的交互式零知识证明系统 3 4，换句话说，对于任何一个多项式空间范围内可识别的语言 L，都可以用零知识的方式证明其中的任何一个断言 x 确实属于该语言。实际应用中，我们通常考虑 L 是一个 NP 类语言，因此，xL 等价于存在一个简短证据 w，使得 w 可以转化为识22设 f:N+是一个函数，满足p x，NpN，使得 f(n)|p(n)|1 对一切 n Np成立，则称 f 是一个可忽略函数。交互式零知识证明的完备性定义中可以将“通过证明的概率可忽略地接近1”加强为“通过证明的概率为 1”，即具有完全完备性。对于完备性定义的加强并没有改变交互式零知识证明系统可识别语言类的范围，事实上 Furer 等2 于 1989 年证明了对于任何一个可由交互式零知识证明系统识别的语言 L，存在一个具有完全完备性的交互式零知识证明系统(Arthur-Merlin 证明系统)也识别 L。第 4 期宋英齐等:零知识证明在区块链中的应用综述别语言 L 的一个多项式时间非确定性图灵机 N，在输入x 时的停机于 N 接受格局的计算序列。换句话说，此时 P 拥有证明 xL 的知识等价于 P 可以计算出一个对应 x 的简短证据 w。NP 类语言的零知识证明可以借助一个密码学承诺(Cryptographic Commitment)来实现，证明者 P 将秘密信息 w 通过密码学承诺绑定下来，以保证后续的挑战始终以 w 作为额外知识参与计算，同时也通过承诺隐藏了 w 的信息。1 2非交互的实现交互式零知识证明的原理十分依赖交互性和验证者随机性。交互性体现在交互式零知识证明的基本逻辑是验证者发出挑战 证明者应对挑战，这一流程的不断重复才能推动证明的实现，仅依靠单次挑战应对很难排除证明者的偶然判断对结果带来的影响。而验证者随机性在于验证者借助自身生成的随机性对证明者发起挑战，这种随机性不能被具有更强计算能力和拥有更多额外知识的证明者提前知道，否则他可能有机会提前准备好相应的应对措施，从而提高自己通过验证的概率。交互性和验证者随机性这 2 个特点却并非适用于所有的应用场景。在一个具有一定用户规模的网络中，他们之间的证明需求可能是非常频繁的，区块链、集体之间的身份认证等就存在这样的情形。更有甚者，证明双方的关系可能会对调，并且每个人可能会和多人产生证明需求关系，如果再要考虑证明双方在空间和时间上的参与差异性，那么会给交互式的证明带来很多麻烦。此外，对一个知识的证明可能需要经过不同的验证者的检验，要求证明者始终配合验证需求随时进行交互也是完全不现实的。