2023年6月9日，来自 CMU 的张嘉恒博士访问北京大学前沿计算研究中心，在静园五院做了题为“Efficient Zero-Knowledge Proofs: Theory and Practice”的报告。报告由中心助理教授李彤阳老师主持。

张嘉恒博士报告现场（报告视频：https://www.bilibili.com/video/BV1qu411W7mq/）

　　张博士从理论与应用两个角度分别入手，介绍了自己有关零知识证明的一系列工作。在理论方面，主要介绍了 Libra——首个线性证明时间（prover time）、亚线性证明大小和验证时间（succinct proof size）的零知识证明协议。在应用方面分别介绍了针对跨链桥（ZK-Bridge）问题和决策树（Decision Tree）问题的零知识证明协议，这两个问题在实际应用中被大家广泛关心。该分布式跨链桥已经实现了了最优可伸展性（perfect scalability），即 T 个机器带来 T 倍加速，以及最优通信（minimal communication）。

　　零知识证明（Zero-Knowledge Proof）的概念，最早在 [GMR85] 中提出，主要旨在通过隐私安全的方式，实现对私密信息的某种验证。更严格地说，零知识证明的协议中，证明者（Prover）一方要向验证者（Verifier）一方证明其持有的私有输入w在某个公开的函数C下的取值为y并提供相应的证明信息，验证者检查对应的证明判定证明是否正确，满足如下安全性要求：

1. 完备性（Completeness）：若C(w)=y，则验证者将（以高概率）判定证明正确。
2. 可靠性（Soundness）：若C(w)≠y，则证明者将难以构造证明信息，使验证者判断正确。
3. 零知识（Zero-Knowledge）：验证者除了得知C(w)是否等于y之外，不应该得知任何其他有关w的信息。

　　零知识证明协议在实际的场景中具有广泛的应用：举例来说，用户可以在不泄露具体身份信息的情况下验证符合某些年龄要求，或者机器学习模型的服务提供方可以在不泄露模型具体参数的情形下，证明模型在特定数据集上具有良好表现。除此之外，在发展迅速的区块链技术中零知识证明同样扮演了相当重要的角色。

　　张博士首先为我们介绍了 Libra 协议的设计工作，该协议改进自基于算术电路（Arithmetic Circuit）的 [GKR 08] 协议，在该协议中，验证算术电路的结果是否正确可以一层层向上倒推为对上一层输出的多项式函数和的验证，而对这一特殊形式的和的验证已有 [LNFK 92] 给出十分高效的 sumcheck 协议，于是可以得到相对高效的结果。

　　对该协议的改进工作主要从效率与安全性两个方面着手：通过将其中对于 sumcheck 协议的使用进行变形，使得证明时间（Prover Time）达到电路大小的下界O(|C|)；另一方面，使用一个大小远小于原先多项式的随机多项式，可以隐匿电路中真实的数据，达到隐私保护的效果。

　　张博士介绍的第二个工作是介于理论和实际应用之间的，主要给出了一个具有相当好的实际效率的零知识跨链桥（zkBridge）。跨链桥用于在两条区块链之间进行信息共享或状态改变，譬如进行区块链之间的转账，这使其在现实中有很大的应用，因为加密货币的蓬勃发展催生出众多的区块链，如比特币、以太坊、Avalanche、Ethereum 等等，那么将众多的不同区块链联系起来就显得尤为重要，因此跨链桥被称为 web3 世界的高速公路。

　　但令人失望的是，之前已有的跨链桥方案由于使用第三方委员会（committee）实现发送方和接受方之间的交易认证和转移，故而当委员会的某一些成员被贿赂（corrupted）时，该方案无法保证安全，造成了很多事故。

　　事实上注意到，当我们有了零知识证明这样的有力工具，只需要将发送发的区块头（header）的正确性的零知识证明发送给接受方，就可以保证接受方获取准确的交易信息。主要技术挑战在于效率：由于数字签名转化成电路后的大小非常大，就算使用很高效的零知识证明也会导致难以接受的证明时间。

　　张博士和其合作者们设计了一个高速低交互的分布式零知识跨链桥，解决了这一技术挑战。在实际效率方面，每个数字签名只需要 2M 个门，总共 0.2B 个门，仅需15秒的证明时间。由于在实际应用方面的重大潜力，本文的工作也促进了工业界的很多发展，基于此技术，成立了大量的基金会和公司，如 zkCollective 和 Polyhedra 等。

　　第三篇工作服务于应用，为决策树的预测和准确性设计了一个零知识证明。机器学习是如今计算机界最火热的领域之一，但是目前的机器学习也面临着诸多问题，如可复现性（reproducibility）——其他研究者能否复现某些工作声称的效果，和有效性（validity）——结果是否确实由数据和模型所生成。注意到这些性质都带有证明属性，因此可以想到将零知识证明技术应用到机器学习领域，并且零知识证明由于只需要证明说明某种正确性而不需要运行整个程序，因此在证明效率上可以期待更多提升。具体地说，张博士与合作者提出了一种把决策树预测（decision tree prediction）转化为电路的方法，并基于此进行零知识证明，这一方法大大降低了电路和证明的大小，并做到了最优。

　　该工作是第一篇将零知识证明应用到机器学习的工作，引起了很多新的跟进研究，让零知识机器学习成为了一个冉冉升起的领域。

　　关于零知识证明领域未来的工作，张博士认为，在理论方面人们致力于寻找最优证明时间（optimal prover）的证明模型，在应用方面应当尽力为所有的应用场景设计高效的零知识证明。

　　到场的同学和老师们对这一领域和这几篇工作兴味盎然，纷纷提问和交流，讲座在热烈的讨论中结束。