在信息安全和区块链技术蓬勃发展的当下，零知识证明（ZK-SNARK）协议作为一项前沿技术，正在展现出巨大的潜力和广泛的应用前景。2024年5月17日下午，三亚学院信息与智能工程学院的大数据专业教授杨明教授，以其深厚的学术背景和研究实力，为信智学院的师生们带来了一场主题为“零知识证明ZK-SNARK协议及应用”的专题讲座。讲座在学院的会议室举办。
杨明教授，作为工学博士，自1995年以来一直在解放军理工大学任教，并在大数据分析、信息安全及算法研究等领域取得了显著成就。他参与并负责了多项国家级和省级自然科学基金项目，并在国内外核心刊物及国际会议上发表了40余篇相关论文，展现出了其卓越的科研实力和学术影响力。
在本次讲座中，杨明教授首先深入浅出地解释了零知识证明的基本概念，即通过一系列步骤，证明者能够在不泄露任何额外信息的情况下，向验证者证明某个陈述的真实性。他进一步阐述了零知识证明的完备性、可靠性和零知识特性，并通过数独游戏等生动的例子帮助师生们更好地理解这一复杂的概念。
ZK-SNARK协议是近年来提出的有效的零知识证明协议，广泛用于区块链、数字身份、外包计算等的隐私保护。本次讲座，杨教授重点介绍ZK-SNARK协议的数学基础、基本原理、通用协议及应用。本次讲座以下三个个方面进行了交流：
1.零知识证明的概念
2.ZK-SNARK协议
3.ZK-SNARK协议的应用
一、零知识证明的概念
零知识证明（Zero-Knowledge Proof）实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。零知识证明允许一方（证明者）向另一方（验证者）证明一个陈述是真实的，而不透露任何超出陈述本身有效性的信息。
零知识证明有三个基本特性：
- 完备性：如果输入是有效的，那么零知识协议应该始终返回"真"。 因此，如果所依据的声明是真的，同时证明者和验证者都诚实，那么证明就能被接受。
- 可靠性：如果输入是无效的，那么理论上不可能欺骗零知识协议输出“真”。 因此，一个说谎的证明者无法忽悠一个诚实的验证者相信一个无效的声明是有效的（小概率事件除外）。
- 零知识：验证者除了知道声明的有效性或虚假性之外，其余一概不知（他们对声明内容“一无所知”）。 这项要求也阻止了验证者从证明中推导出原始输入（声明的内容）
为便于大家理解，杨教授深入浅出地用数独游戏举例说明了如何向他人证明你已解决数独问题，同时又不泄露你的答案？
二、ZK-SNARK协议
1.zk-SNARK的含义
zk-SNARK表示“Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”，即零知识简明非交互式知识证明，名字的主体是“argument of knowledge”，即“知情证明”，也就是掌握某知识的证据。修饰主体分别代表了此技术要解决的三个问题
- zero knowledge：零知识，证明某个陈述为真但不揭露任何其他信息。
- succinct：简洁的，表示证明大小很短且易于验证。
- non-interactive：无交互。
- Arguments：在proof system中，即便是计算能力无限的prover也没法欺骗verifier去相信一个错误的陈述为真（统计可靠性），而在argument system中，只有多项式时间计算能力的没法欺骗（计算可靠性），假设能破解椭圆曲线离散对数问题，那么可能就不再安全。
- of Knowledge：如果prover没有相应的witness（证据），那么构建相应的proof（对于proof system）或argument（对于argument system）是不可能的。
2.zk-SNARK技术的发展
2010 年的论文 《Short Pairing-based Non-interactive Zero-Knowledge Arguments》中提出了目前零知识证明的关键性理论，实现了基于 ECC 算法的 O(1) 常数级的ZK，也是zk-SNARK 的理论先驱。
2013年，Pinocchio协议《Pinocchio: Nearly Practical Verifiable Computation》实现了分钟级别证明，毫秒级别验证，证明大小不到300字节，将零知识证明从理论带到了应用。
2015 年 Zcash 使用的零知识证明系统，实现了对交易及金额隐私的保护，后来发展到 zk-SNARKs 和智能合约相结合，ZK技术进入了更为广泛的应用场景。
2016年，《Groth16:On the Size of Pairing-based Non-interactive Arguments》算法对证明的大小进行了精简，是目前主流的 ZK 算法中的基础性算法之一。
2017年， 《 Bulletproofs: Short Proofs for Confidential Transactions and More》 算法被提出，设计出了一种非常短的非交互式的零知识证明，无需可信设置。
2018年，论文《 zk-STARKs (BBHR18) Scalable, transparent, and post-quantum secure computational integrity》提出了一种无需可信设置的算法，抗量子计算攻击能力的零知识证明协议。
3.zk-SNARK的基本原理
P类问题
P={DTM能在多项式时间内所接受的语言类}
例：排序问题、矩阵连乘问题、最小生成树问题、图搜索问题
NP类问题
NP (Nondeterministic Polynomial time)
NP= {NDTM能在多项式时间内所接受的语言类}
NP= {DTM能在多项式时间内验证的语言类}
例：旅行售货员问题(TSP)，布尔表达式的可满足性问题(SAT)
未解的世纪难题P=NP?
zkSNARKs是基于NP问题的，因为如果是一个P问题的话，那么直接求解就行了，证明就无从谈起，所以zkSNARKs的依托于某种NP问题，很难求解但是可以快速验证。zkSNARK先把问题转换成正确的“形式”来处理，这种形式叫做 "quadratic arithmetic problem"(QAP)
4.zk-SNARK基本过程
整个证明体系将会由以下几步来完成：
将数学运算电路
转化为到R1CS程序矩阵。
从R1CS程序矩阵还原成多项式。
用多项式表达式定义LPCP。
从多项式LPCP到可信初始化（trusted setup）的简短零知识证明（zkSNARK）。
先将运算的证明转换为电路，将电路拍平变为由基本电路构造运算电路。然后再转换为R1CS。
5.基本的zk-SNARK协议
三、zk-SNARK协议的应用
zk-SNARK作为一个通用的零知识证明工具在隐私保护特别是区块链、数字身份、外包计算等诸多方面有广泛的应用。
在区块链扩容方面，区块链由于自身的性能问题导致其难以满足当下需求，基于零知识的扩容方案将有望解决区块链性能瓶颈。扩容是指在不牺牲去中心化和安全性的前提下提高交易速度和交易吞吐量。ZK-Rollups是基于零知识证明的Layer2扩容方案，通过将计算转移到链下来提高区块链的吞吐量，即将大量交易打包到一个Rollup 区块内，并在链下为该区块生成一个有效性证明，Layer 1 上的智能合约只需验证该证明即可直接应用新的状态，可以实现更低的 Gas 和更高的链上安全性。zkSync 是 Matter Labs 推出的一款 Layer2 扩容方案，通过采用基于零知识证明的 Rollup 提升以太坊网络的可拓展性。目前该项目已经上线聚焦于支付目的 1.0 主网和完全兼容 EVM 的通用 2.0 主网。Polygon于2018 年由Jaynti Kanani等人创建于印度，目前已经发展出一套自己的以太坊扩展工具。Polygon正在积极布局他们的ZK（Zero Knowledge）战略，承诺将投入超10亿美元的资金用于ZK技术的研究和探索。
在数字加密货币方面，BTC隐私保护存在局限性。2013年5月，为了改进Coinjoin需要第三方参与的缺陷，约翰霍普金斯大学教授Matthew D. Green等提出了Zerocoin协议。此协议提议允许销毁并重新生成数字通证，以保证通证交易匿名化且无需第三方参与。2014年5月，Matthew D. Green等人基于Zerocoin创建了Zerocash协议。该协议利用密码学领域的高级证明——零知识证明方法对Zerocoin进行了完善和改进。Zerocash提出了一种经典的零知识证明方法——zk-SNARKs。Monero门罗币是最早的知名隐私币项目之一，也是第一个部署Bulletproof技术的隐私币项目。
在ZK应用方面，保密的秘密分享：ZK技术赋予用户通过无需信任的结算层机密地分享秘密的能力。如zkMail和zkVoting协议。链上保密身份：ZK应用程序使用户能够以可组合的方式创建链上的保密身份，超越传统数据混淆方法的限制。链下安全保证：利用ZK技术提供了强大的链下安全保证，确保了大量链下数据和计算的完整性和预期状态。互操作性信任：由ZK技术支持的预言机和桥梁在将链下数据桥接到区块链网络时起着关键作用，维护了加密完整性。
在可验证计算方面， 验证已发生的计算而不披露所有细节。Filecoin使用的ZK Proof of Storage可确保矿工在任何给定时间存储数据的副本。 验证媒体的真实性，区分真实图像和篡改图像已成为不断升级的挑战，助长了假新闻的蔓延。Boneh及其团队已经实施了用于各种照片编辑的ZKP，包括裁剪、转置、翻转、旋转以及调整对比度/亮度。因此，任何用户都可以轻松检查证据，以验证新闻报道是否真实，而无需依赖“社区注释”。 验证财务信息，通过利用ZK证明，个人可以将其KYC数据转化为客户端设备上的ZK证明，并在不披露敏感信息的情况下与Dapp共享，以满足合规要求。
讲座中，杨明教授与师生们进行了深入的交流和讨论。他鼓励大家积极关注和研究零知识证明等前沿技术，为信息安全和区块链技术的发展贡献自己的力量。同时，他也表示将继续致力于相关领域的研究和教学工作，为推动学科发展和人才培养做出更大的贡献。本次讲座不仅为师生们提供了一次难得的学习和交流机会，也进一步提升了大家对零知识证明等前沿技术的认识和了解。相信在杨明教授等优秀学者的引领下，三亚学院信息与智能工程学院将在信息安全和区块链技术等领域取得更加卓越的成就。
