零知识证明技术发展报告.pdf

1 版权声明陀螺研究院 *安比实验室 *壹账通零知识证明技术发展报告版权为深圳市陀螺传媒有限公司拥有，是陀螺研究院和合作单位的研究与统计成果，其目的是为投资者和从业者提供参考，陀螺研究院报告仅限于行业内部使用。未经陀螺研究院的审核、确认及书面授权，购买报告的客户不得以任何方式，在任何媒体上（包括互联网）公开引用本报告的数据和观点，不得以任何方式将报告的内容提供给其他单位或个人。否则引起的一切法律后果由该客户自行承担，同时陀螺传媒亦认为其行为侵犯了陀螺研究院的著作权，陀螺传媒有权依法追究其法律责任。报告的所有图片、表格及文字内容的版权归陀螺研究院所有。其中，部分图表在标注有数据来源的情况下，版权归属原数据所有公司。如有侵权行为的个人、法人或其它组织，必须立即停止侵权并对其因侵权造成的一切后果承担全部责任和相应赔偿。否则我们将依据中华人民共和国著作权法、计算机软件保护条例等相关法律、法规追究其经济和法律责任。指导单位：深圳市信息服务业区块链协会协撰单位：深圳大学区块链技术研究中心编委会成员指导：余文锋杨达豪郭宇张胜利贾牧主笔人：余维仁编写人员：卢艺文余维仁 2 前言 4月初，从在会议中播放色情内容的 “ Zoom轰炸 ” ，到偷偷向 Facebook发送用户数据，视频会议软件 Zoom的隐私丑闻持续引发大家的关注。联想之前炒得沸沸扬扬的脸书公司隐私泄露事件，隐私问题已经成为制约互联网产业发展的最大绊脚石之一。资料来源： Risk Based Security 回顾 2019即将过去的一年，大规模的数据泄露事件频频发生，呈现爆发递增的趋势。据安全情报供应商 Risk Based Security (RBS) 的 2019年 Q3季度的报告， 2019年 1月 1日至 2019年 9月 30日，全球披露的数据泄露事件有 5183起，泄露的数据量达到了 79.95亿条记录！随着以人工智能、大数据和物联网为代表的信息技术革命的推进，数据的价值进一步凸显，数据成为了企业的重要资产和持续创新的推动力。因此，保障数据在采集、传输、利用和共享等各个环节安全的重要性不言而喻。区块链作为一种底层技术和基础架构，将它与其他新兴信息技术，如人工智能，大数据分析，零知识证明技术，物联网，数据存储等，相互结合将创造极大的价值。它能够在金融服务、政务管理、能源管理、知识产权、公益、监管、数据共享、供应链管理、保险和存储等领域发挥重要的作用，甚至是颠覆性地变革。 3 零知识证明技术做为现代密码学的重要组成部分，它能够在不泄漏任何秘密信息的前提下完成对此秘密信息的验证。零知识证明技术对于解决当前信息安全中的诸多问题，如数据安全、隐私安全、监管检查等都能够发挥重要的作用。零知识证明与区块链的完美结合很好的解决了区块链当前面临的困局。一方面，区块链公开透明的天然特性，使其在在隐私和数据安全问题上存在诸多局限；另一方面如何解决性能问题，提高吞吐量和响应速度是当前区块链大规模落地所面临的最大问题。 4 目录Table of Contents 前言 3一、区块链与零知识证明技术综述 7 二、零知识证明技术发展 9 2.1 零知识证明的概念 10 2.2 理论发展 102.2.1 诞生 112.2.2 奠基时期 11 2.2.3 理论发展时期 122.2.4 工程落地序幕 132.2.5 应用驱动的繁荣时期 14 2.3 工程实现 162.3.1 技术架构 162.3.2 实现语言 182.3.3 开源库 18三、零知识证明在区块链领域的应用 21 3.1 隐私保护 223.1.1 链上资产交易 22 3.1.2 数字身份认证 233.1.3 监管检查 24 3.2 扩容 243.2.1 链下扩容 253.2.2 链上区块压缩 263.2.3 轻量级客户端 27 5 四、应用案例分析 29 4.1 公链基础 304.1.1 Zcash 304.1.2 Monero 314.1.3 Filecoin 324.1.4 Coda 32 4.2 底层扩展 334.2.1 ZK Rollup 334.2.2 ZEXE 354.2.3 ZoKrates 354.2.4 ZkVM 36 4.2.5 FiMAX 36 4.3 上层应用 37 4.3.1 Loopring 374.3.2 zkPoD 384.3.2 AZTEC 38五、零知识证明技术发展趋势 39 5.1 后量子零知识证明 40 5.2 性能优化 415.2.1 证明协议优化 415.2.2 硬件加速 42 5.3 零知识全同态加持 43 5.4 标准化 44 5.5 公链集成 44六、总结 46参考资料 48 6 一、区块链与零知识证明技术综述自 2008年中本聪白皮书发布以来，区块链技术至今已经历了 12 年的发展，期间不乏许多戏剧化的演变。从早期在密码学圈子里兴起，到中间经历了资本疯狂泡沫的时代，再到如今逐渐回归理性，区块链真正服务于社会的价值也慢慢凸显。如今区块链在信息技术已经明显占据了一席之地，也是各国争相角逐地新的技术竞技场。而在过去十多年的技术和应用演进中，区块链已经不仅只是中本聪白皮书中所描绘的一种点对点支付协议，而是在它原生支持支付和弱化第三方的基础上，结合更多技术和应用需求，逐步发展成为 “ 世界计算机 ” 。但随着区块链应用的不断探索，近两年数据隐私和性能扩展成为社区最广泛讨论的问题。根据目前的实践来看，零知识证明正是解决这些问题的最有力武器，随着技术的落地，零知识证明如今已经成为区块链技术中不可缺少的一环。互联网与大数据技术的快速发展，为社会生活带来了翻天覆地的变换。信息数据时代，每天产生海量的数据，小到个人信息，大到国家数据信息，这些数据既在当下拥有不可估量的力量，对预测未来的发展趋势也尤为重要。新华社 11 月 5 日发布了中共中央关于坚持和完善中国特色社会主义制度推进国家治理体系和治理能力现代化若干重大问题的决定，正式将数据列为生成要素。数据资产化已经成为不可阻挡的趋势。而区块链作为重塑生产关系的关键因素，也将在数据生产，数据共享，数据确权和数据保护中发挥了重要作用。其中值得一提的是隐私数据泄漏的问题和数据所有权的矛盾已经变得尤为突出，这对个人人身安全和财产安全带来的威胁都是致命的。所以如 7 何数据隐私安全问题和数据所有权问题是当下技术研究的一个重要方向。研究人员渐渐将目光转向区块链领域，尤其是结合以零知识证明为代表的密码学方案去解决这类问题，是具备极好的优势的。区块链由于本身的限制，导致其无法在性能和交易处理速度上达到传统应用的要求，这一点严重制约了区块链的大规模落地应用。因此如何提高区块链的性能及其吞吐量尤为关键。零知识证明技术在压缩数据量提高性能方面可以发挥很大的作用，这一点很好的弥补了区块链的这一约束。 8 二、零知识证明技术发展 2.1 零知识证明的概念 2.2 理论发展 2.3 工程实现 9 2.1 零知识证明的概念零知识证明技术是现代密码学的一个重要组成部分。它是指证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。一个零知识证明必须满足三个性质： 1.完备性（ Completeness）：当证明者和验证者都表现诚实，遵循协议来执行验证步骤时，如果证明者的陈述是真的，那么一定可以被验证者接受。 2.可靠性（ Soundness）：如果证明者的陈述是假的，那么任何一个作弊的证明者不可能使一个诚实的验证者相信他的陈述。 3.零知识（ Zero-knowledge）：证明执行完成后，验证者仅能知道证明者的陈述是否为真，除此以外，他在证明过程中获取不到其它任何信息。零知识证明技术的背后依赖于强大的理论基础，如计算复杂性理论和信息论。包括图灵机，概率可检查证明， P/NP 问题等等都在其研究范围内。2.2 理论发展零知识证明技术的理论研究已经过了三十几年的发展历程，目前也已取得了非常显著的成果，但直到近十年来，其巨大潜力才逐渐突显出来。如今，零知识证明理论研究正呈现一种百花待放的态势。 10 2.2.1 诞生零知识证明思想由来已久，早在 16世纪的文艺复兴时期，意大利有两位数学家为竞争一元三次方程求根公式发现者的桂冠，就采用了零知识证明的方法。但 “ 零知识证明 “ 这个概念真正在学术界被提出是在 20 世纪 80 年代中期，由 S.Goldwasser、 S.Micali 及 C.Rackoff 三人在一篇名为交互式证明系统的知识复杂性 GMR85的论文中提出。这篇论文在 NP 的证明系统中引入了 ” 交互 ” 和 ” 随机性 ” ，构造了交互式证明系统。同时这篇论文中还提出了零知识证明的这个名词，并给出了其性质的定义。零知识证明逐步成为密码学领域的一个理论研究分支。2.2.2 奠基时期随后的十几年里，密码学家们提出了一系列的概念，这些巨大的突破为后来的零知识证明发展奠定了基础。比如 1986年， Amos Fiat 和 Adi Shamir提出了 Fiat-Shamir 变换，是一种将交互式证明系统变成非交互的通用方法。此外，为了实现非交互式零知识（ NIZK）证明系统。 M. Blum, P. Feldman, and S. Micali指出了 ” 交互 ” 与 “ 隐藏随机性 ” 并不是必要的，继而提出基于公共参考串 CRS Common Reference String）模型的非交互式零知识证明系统。 1992年， J. Kilian 提出了简洁非交互零知识证明的概念，并基于概率可检查证明（ PCP）提出了一种证明系统。 1990 年，德国数学家和密码学家 Claus-Peter Schnorr 提出一种基于离散对数难题的知识证明机制，它实现的签名机制（称为 Schnorr 签名）。 1996 年，Cramer在博士论文中推广了 Schnorr 签名，正式提出了 Sigma 协议的概 11 念，这成为一种被广泛采用的零知识证明构造框架。 1998 年， Ronald Cramer 和 Ivan Damgard提出了基于算术电路可满足性（ NPC问题）的零知识证明系统，可以把通用的计算转换成抽象的算术电路，然后即可以用零知识证明来验证输入与给定的输出对应。2.2.3 理论发展时期经过 20 年的理论发展，零知识证明最底层的理论根基已经逐渐清晰，开始逐渐走向成型，并出现了不同的零知识证明技术分支。 2005 年， Dan Boneh, Eu-Jin Goh 和 Kobbi Nissim提出了一种基于双线性映射的单次乘法的同态公钥加密方案，于是在 2006 年， J. Groth, R. Ostrovsky 和 A. Sahai. N基于这个工作提出了基于双线性映射的非交互式零知识证明技术，这也是第一个适用于所有 NP 问题的达到 “ 完美零知识 ” 的论证系统（ Argument）。该系统还有一个非常重要的优化就是它第一次通过采用椭圆曲线的双线性映射，大大缩短了 CRS 的长度以及证明长度。从此，椭圆曲线双线性映射成为零知识证明构造技术中相当重要的一环。 2007 年， Yuval Ishai， Eyal Kushilevitz， Rafail Ostrovsky 和 Amit Sahai提出了利用安全多方计算（ MPC， Secure multiparty computation)，产生零知识证明的技术新思路，被称为 MPC-in-the-head，它也建立了零知识证明的一个重要研究分支。 2008 年， Shafi Goldwasser、 Yael Tauman Kalai和 Guy N. Rothblum提出了一种交互式的证明系统 GKR协议，这是一种实现可验证计算的美妙方案。这个协议也成为实现通用零知识证明的一个重要技术分支，比如后续的 zkVSQL、 Hyrax、 Libra等协议。 12 2009 年， Jens Groth提出了一种实用的实现常见矩阵运算零知识证明系统。证明系统无需 Trusted-Setup，基于标准的离散对数难题假设。这个证明系统奠定了一个重要的零知识分支，其中的向量内积证明、向量 Hadamard证明是 “ 防弹证明 ” （ Bulletproofs）的重要理论基础，也形成了基于椭圆曲线的通用零知识证明技术的一个重要分支。 2010 年， Jens Groth 提出了一种在当时颇具争议性的安全假设指数知识假设（ Knowledge of Exponent Assumption， KEA），通过采取这个争议性假设，可以将零知识证明的长度缩短到常数级别。 Groth 的这个大胆工作直接将零知识证明朝着实用性方向发展推进了一大步。但是，这个方案也引入了一个技术问题，并且在后来区块链领域应用中成为一个关注的焦点，这就是可信预设置（ Trusted-Setup）。 Groth 通过把一些秘密随机值隐藏到 CRS 中，实现了证明长度的大幅缩减，但是也带来了一些安全风险。无论如何，这一方案确立了未来十年最重要的零知识证明技术分支。同时 2006年前后， Eli Ben-Sasson 等人改进了 PCP 理论构造，将概率可检查证明的长度压缩到了准线性级别。这些学者的工作推动了基于 PCP 理论的通用零知识证明构造技术，成为后续 zkSTARK， Aurora 等证明系统的关键理论基础。成为无可信预设置，并且可以抗量子的零知识证明技术重要分支之一。2.2.4 工程落地序幕进入到 21世纪的第二个十年，随着不同的零知识证明分支理论的发展，一些零知识证明技术已经初现工程实用的曙光。密码学家们开始在工程化方向上深入研究，也正式拉开了零知识证明工程化的序幕。其中在 2012 年，Nir Bitansky, Ran Canetti, Alessandro Chiesa 和 Eran Tromer 发表 13 论文正式提出了 zk-SNARK （ Zero-knowledge Succinct Non-interactive Argument of Knowledge）这个名词。大家意识到，证明长度必须要足够小，才能降低证明的验证时间，并且非交互性对实际应用极具诱惑力。接下里， 2013 年 Rosario Gennaro， Craig Gentry， Bryan Parno 和 Mariana Raykova的研究成果（ GGPR13）意义重大。他们在 J. Groth 2010年工作的基础上，提出了一种漂亮的改进方案，利用 QSP（ Quadratic Span Programs）或 QAP（ Quadratic Arithmetic Program）技术，大大缩短了证明时间，并且把证明长度压缩到了很小的常数级别，几百个字节大小。随后， Parno 等人在此基础上实现了一个叫做 Pinocchio 的可验证计算协议，并且继续做了优化和改进，最重要的是， Pinocchio 协议不满足于停留在纸面理论阶段，而是做了完整的工程化实现，并且有力证明了零知识证明的工程可行性。 Pinocchio 协议可以将庞大的计算压缩到不足 300字节，并且证明时间接近线性。 2014年， Eli Ben-Sasson, Alessandro Chiesa等人稍稍改进了 Pinocchio 协议，并且提出了一个名为 ZeroCash 的匿名币协议，这是著名的区块链匿名加密货币 ZCash 的前身。随后 ZCash 团队在零知识证明工程化方面做出了比较大的贡献。2.2.5 应用驱动的繁荣时期最近几年，随着区块链技术的蓬勃发展，零知识证明的应用场景也在不断增多，也不断对零知识证明的理论与技术提出了新的挑战。区块链项目中以 ZCash 为代表的团队需要性能表现更加出色的方案，Groth16在 Pinocchio 协议上做了一步极致优化，在略微加强安全性假设的情况下，把证明尺寸压缩了将近一半，成为目前区块链领域中最广泛使用的零知识证明技术方案。 14 随着匿名加密货币的发展，更轻量级的金额范围证明有较大的需求空间。 B. Bunz 等人在论文 BCGP16的基础上改进得到了一个可以聚合的范围零知识证明，该方案就是著名的 “ 防弹证明 ” 。它一经提出就迅速被 Monero 项目采纳并实现。当然防弹证明不仅仅可以用作范围证明，也是一个无需可信预设置的通用零知识证明技术，也逐步被一些团队采纳并应用。 Groth16 方案的使用不方便之处在于备受争议的可信预设置。 Eli Ben-Sasson 等人在 PCP 理论的基础上逐步发展出了 “ 透明 ” zkSNARK，也被成为 zkSTARK。所谓透明，正是指预设置过程可以一种更加透明的方式来完成。并且 zkSTARK 主要基于 Hash 算法，不再依赖椭圆曲线，是一种目前可以对抗量子计算机的方案。随后的 Aurora 等工作进一步改进了 zkSTARK 技术，目前已经成为极具竞争力的主流零知识证明技术之一。 2018年， Jens Groth 等人提出了一种可更新的全局 CRS 方案 Sonic，所谓可更新是指，可信预设置可以随时进行更新，只要大家怀疑秘密已被泄露。所谓全局，是指计算过程不再与 CRS 绑定，一个应用只需要完成一次可信预设置即可实现不同的零知识证明电路计算。此外，基于 GKR 协议的零知识证明方案，比如 Hyrax 也可以实现透明预设置，但会牺牲一部分性能，而 Yupeng Zhang 等人通过加入全局可信预设置的折中方案，可以大大提高效率，这也是 Libra 方案一个优势。折中方案兼顾安全性与性能，获得了不少团队的青睐，新的证明系统 PLONK， Marlin 等都在这个全局可更新 CRS基础上进行各种优化，并且取得了一些成果。值得一提的是 Jiaheng Zhang， Tiancheng Xie, Yupeng Zhang 与 Dawn Song 提出的 Virgo 方案，这是基于 GKR 协议，透明预设置的高效证明系统，并且具有较好的证明生成性能。 15 区块链应用中有大量数据不断更新的应用场景，这需要可以递归组合的零知识证明，也催生了 Halo 与 Fractal 等递归零知识证明。这些零知识证明方案各有千秋，需要根据应用场景来选择甚至改造，这无疑阻碍了零知识证明的标准化和落地应用。但斯坦福大学的 Dan Boneh 教授在近期一次访谈中，预言在几年内可能会有统一的零知识证明协议出现，进而可能会大大促进零知识证明的工程化，标准制定，以及落地应用。2.3 工程实现当前零知识证明技术的工程实现自 2013 年算起至今，尚处于早期阶段，还有很长的路要走。但零知识证明技术在近两年引起关注，越来越多的团队正在投入到这一领域，因此零知识证明技术的工程实现成果也在快速增长。而随着区块链产业的进一步扩大和隐私问题的越发突显，相信未来对零知识证明技术的投入也将进一步提高。本文整理了当前零知识证明技术在工程上的实现，并从技术结构，实现语言，开源库三个方面分析发展现状。2.3.1 技术架构当前零知识证明的技术实现架构大致可以分为五层结构： 1. 底层基础底层基础算法库是实现零知识证明系统的前提，因为零知识证明技术依赖于大量的数学基础原理来完成计算，如有限域计算，矩阵运算，椭圆曲线运算等等。如基于椭圆曲线的零知识证明协议中，就需要依赖大量的椭圆曲线实现。 secp256k1， BN254 和 BLS12-381 是工程实现中大量使用的几条曲线。 16 在中华人民共和国密码法颁布后，国内一系列的应用也开始基于SM2、 SM9等国密算法的曲线标准构建零知识证明系统。 2. 证明系统（ proof system）证明系统也就是零知识证明协议，拥有证明系统才能完成证明。零知识证明协议有很多，每一种协议的实现步骤也不尽相同，因此每一种协议都需要对应一个证明系统。目前应用最为广泛的当属 Groth16，Bulletproofs。 3. 电路约束（ circuit）为了完成一次零知识证明，需要先将待证明的实际问题转换成证明协议可以验证的约束关系。这种约束关系是以电路的形式表示出来的。因此构造电路约束关系是零知识证明工程实现中一个非常核心的部分，它是建立在实际问题和证明之间的桥梁。电路的构造是难度很大。一方面，由于不同问题所对应的约束关系不同，电路也有所不同；另一方面，构造电路的正确性难以保证，一旦构造的电路不正确，证明结果的可靠性就难以保证，并且尤其对于复杂的问题，约束关系若不完整或者不正确也很难被发现。因此在实际的应用中，如何保证电路实现的正确性，完整性和高效率是尤为关键的一环。 4. 电路组件（ gadget）在实际的复杂约束关系中包含了很多复用的简单约束关系，如布尔值证明、范围证明和哈希证明等等，而这些约束关系经常被作为一个 gadget 集成在开源库中，这样即开发人员仅需直接调用接口即可正确得完成这部分的电路构造，这既简化了开发人员的工作量，也减少了开发过程中的错误。 17 5. 上层应用上层主要分为两大类： 1. 在应用中直接通过调用零知识证明库完成电路构造和证明 2. 为了简化区块链上层 DAPP 开发零知识证明应用的难度，开发人员在区块链底层构建工具包集成零知识证明开源工具，如以太坊上的 SNARK 工具箱 ZoKrates2.3.2 实现语言出于不同实现