静5前沿讲座回顾 | 区文浩教授谈密码学前沿进展及在区块链中的应用
关键词：北京大学海外学者讲学计划
编者按
2023年9月19、21、23日，香港理工大学的区文浩教授访问了北京大学前沿计算研究中心，并在静园五院作题为“Advances in Cryptography & Blockchain Applications”的系列报告，介绍了应用密码学研究前沿及其在区块链中的应用。系列报告由中心邓小铁教授主持，本次带来区教授的三次报告内容回顾。
该系列讲座受到了北京大学海外学者讲学计划支持。
区文浩教授报告现场
讲座1
区块链中的密码学应用
区老师在本次讲座中从区块链的基本框架出发，首先回顾了区块链创立之初所想要解决的基本问题。他指出，区块链想要实现一个完全没有任合中心化节点的系统，以彻底解决单点攻击问题。这一系统中包含许多节点，且随时都可能有新的节点加入，同时还要保证所有的节点都能认可同一个账本。与此同时，系统中还存在一些恶意节点，他们可能不完全遵守系统协议来尽可能使自己获利。
为了解决上述问题并实现一个分布式系统，中本聪最先提出的比特币协议使用哈希函数来表示区块之间的链接关系，即新区块必须将父区块的哈希值放在区块中，同时必须保证区块的哈希值小于一个定值才能提出区块。同时协议还规定，所有节点都以最长链原则来判断区块链的合法性。这两个规则既保证了诚实节点能够对区块链形成共识，又意味着恶意节点想要修改区块链历史需要非常大量的计算能力，防止了恶意节点通过篡改历史来获利的可能性。同时，比特币协议会给予提出合法区块的矿工一些货币奖励，这也解决了在没有中心节点时，如何激励节点打包区块的问题。
更进一步，以太坊协议在比特币的基础上引入了智能合约的概念，即允许在区块链上直接执行完全由代码控制的账户。这一创新性的改进使得很多应用程序可以直接在区块链上部署，极大地扩展了区块链的应用功能。尽管区块链存在交易时间不确定的劣势，但是其拥有的去中心化性、不可篡改性和可追踪性的优势使其可以在商业、供应链、身份管理等方面得到很好的应用。
区老师介绍区块链的优势
但是，区块链目前仍然有很多业务和技术方面的障碍。在业务方面，区块链系统存在着虚拟货币价值变化过快、交易难以审计、分布式应用没有规范化的问题。而在技术方面，区块链首先存在效率低下的问题，处理交易的速度远不及传统的中心化系统。同时，由于区块链公开透明的特点，链上用户的隐私难以保护。最后，由于区块链中虚拟货币直接与私钥绑定，如果用户忘记私钥，那么所有货币都将受到损失，其安全性也有待提高。
为此解决区块链存在的以上障碍，区老师介绍了多种区块链中常用的密码学原语，并解释了其如何解决区块链中的技术问题，具体包括：
多签名：多签名是一种利用多个用户的公钥和私钥共同对消息进行签名的机制。在区块链中，多签名可以用来创建共同账户，并保障钱包的安全。
聚合签名：聚合签名是将多个对不同消息的签名聚合成一个更小的签名，以加速签名验证过程，提高区块链交易的效率。
零知识证明：零知识证明是一种保护隐私证明方式，同时可以用来提高区块链处理交易的效率，这个技术将在下一节讲座中详细介绍。
环签名：环签名是一种签名方式，可以证明某个集体中的用户进行了签名，但外界无法知道是哪个用户签名的。在区块链中，环签名可以用来保证 UTXO 的隐私性。
匿名凭证：匿名凭证是一种证明用户属于某个联盟的方式，通常通过零知识证明进行验证。
门限密码：门限密码能够将私钥分成多份，只需任意几份就能组成合法的签名，以同时保证安全性和鲁棒性。相关内容将在第三次讲座中详细介绍。
可验证加密签名：可验证加密签名可以证明加密的签名所表示的信息。在区块链中，加密签名代表着转账交易，可以先进行转账签名，然后在公证处进行解密以完成转账操作。这一机制既确保了安全性，又保证了可追溯性。
区老师介绍密码学原语在区块链中的应用
报告回放：
讲座2
零知识证明前沿进展
区老师首先介绍了零知识证明。零知识证明是一种交互式协议，由 Prover 和 Verifier 两方组成。双方共同知道一个 Statement ，只有 Prover 知道使 为真的 witness ，即二者满足某个关系 。在该协议中，Prover 和 Verifier 可以进行多轮交互，在协议结束后 Verifier 将根据交互过程决定是否相信 Statement 。
一个零知识证明协议需要具备以下特点：
完备性（Completeness）：只要 Prover 确实知道存在一个 witness，那么通过协议一定能让一个诚实的 Verifier 相信这个 Statement。
有效性（Soundness）：如果 Prover 并不知道是否存在 witness，那么他就无法说服一个诚实的 Verifier。
零知识性（Honest Verifier Zero-Knowledge）：在协议中，诚实的 Verifier 无法获得除了 Statement 为真之外的任何其他信息。
在密码学中，为了说明一个协议拥有零知识性，我们通常需要构造一个不知道 witness 的 Simulator 来和 Verifier 进行交互。如果这个交互过程和 Prover 与 Verifier 的交互过程是无法区分的，那么我们就说明了该协议拥有零知识性。
此外我们还可以注意到，在上述的定义中我们只需要 Prover 知道 witness 存在，而并不一定需要 Prover 知道 witness 的确切值。为了确保这一点，一些零知识证明协议中还引入了 Proof of Knowledge 的定义，即要求只有 Prover 确实知道 witness 时，Verifier 才选择相信 Statement。
例子：Schnorr Identification 零知识证明协议
例如，如果 Prover 知道一个离散对数关系 ，想向 Verifier 证明自己确实知道这个 并不泄露 的值，那么双方可以通过上图的 Schnorr Identification 协议来进行这个零知识证明。首先 Prover 随机选取一个 ，并将 发送给 Verifier，之后 Verifier 需要选取一个随机的 challenge 发送给 Prover。Prover 根据 和 计算 并发送给 Verifier。最后 Verifier 选择接受 Statement，当且仅当 。区老师逐一解释了为何这一协议满足上述的完备性、有效性（Proof-of-Knowledge），以及零知识性的性质。
零知识证明在区块链中有着多种应用方式，可以提高区块链的效率，安全性和隐私性。在介绍如何提高区块链的隐私性方面，区老师首先提出了一个开放性问题：如何定义区块链中的隐私？我们知道，虽然区块链的交易地址是匿名的，但是经过研究，仍有多种方法可以破译地址之间的关系。例如当一个交易是两个地址同时给别人付款时，那么这两个地址很大概率属于同一个人。为了缓解这种问题，人们想到使用密码学中的环签名，即用多个无关公钥一起做一次性环签名，让交易无法对应到指定地址。
然而，这种方式也并不一定能完全保证隐私性。例如，如果有三个人用相同的三个公钥对三笔交易进行环签名，那么即使攻击者无法得知每个公钥对应具体哪个人，但是通过逻辑推理可以得知这三个公钥一定对应这三个人之一。如此一来，这三个公钥在其他环签名里就不再能起到保护隐私的作用。针对这一发现，区老师及其团队提出了一种可能的攻击算法，并以此提出如何定义区块链地址隐私性的问题。
区老师介绍环签名面临的攻击
既然环签名也无法保证隐私，那么应该怎样做才更加安全呢？这时候零知识证明就派上了用场。ZCash 是目前最著名的基于零知识证明技术的匿名加密货币协议，其允许在不泄露任合关于交易详情信息下对交易的合法性进行验证。在 ZCash 中，只有对交易的承诺（Commitment）会放在链上，并附上对承诺合法性的零知识证明。当用户需要转账交易时，他们需要根据公钥地址和自己原本的私钥进行铸币行为，并将新币的承诺和证明发送到链上。由于链上只有承诺和证明，这种交易不会泄露任合交易信息。同时，通过在承诺和证明过程中使用伪随机函数，可以保证同一个承诺只能使用一次，保证了协议的安全性。虽然 ZCash 的证明过程较为繁琐和复杂，但这保证了其强大的隐私性和匿名性。
区老师介绍 ZCash 协议
在保护隐私性之外，零知识证明技术还可以用来提高区块链的效率。区老师介绍了目前最常用的通用高效零知识证明系统 Plonk。Plonk 是一种可扩展的证明系统，其可以用于证明各种复杂数学问题的正确性。该方案首先将需要证明的问题进行算术化，将其转换成算数电路的形式。之后使用多项式 IOP 的证明技术，通过使用置换和线性组合的方式构建效率较高的承诺和零知识证明，这使该协议能够以较低的计算和通信成本来生成对各种复杂问题的证明。
区老师介绍 Plonk 证明系统
最后，区老师还提及了零知识证明在区块链中的其他应用：包括应用在 Layer2 的 ZK rollup 技术可以对区块链进行扩容；将零知识证明技术和分布式身份认证技术进行结合，实现更灵活的信息认证功能；以及将零知识证明技术与机器学习技术结合，实现对学习结果的验证等等。零知识证明在区块链中还有广泛的应用空间，值得大家去共同探索。
讲座3
高效门限椭圆曲线签名算法及其应用
这次报告中，区老师介绍了目前区块链中应用最多的加密签名方式：椭圆曲线签名。区块链中通常都需要使用者对交易进行签名，来确认交易发送方。在这一过程中，用户首先将生成一对公钥地址和私钥地址，并将公钥地址发送到链上。之后每当用户发送交易时，其就需要使用私钥对交易进行签名，要声明交易的发送者。这样，链上的其他用户和矿工可以用公钥验证签名的合法性，来保证交易的正确执行。在这些公钥数字签名中，椭圆曲线签名由于被比特币协议、TLS 协议等使用，以及被美国国家标准技术研究所（NIST）设为数字签名的技术标准，受到研究者的广泛关注。
但是，在区块链中应用数字签名也存在着单点故障问题。由于区块链中钱包直接和私钥地址进行绑定，因此如果用户不小心忘记了自己的私钥，那么钱包中的所有虚拟货币都将丢失。为了解决这个问题，研究者提出了门限数字签名技术：用户可以设置多个私钥，并将它们存储在不同的设备上；只要使用其中的几份私钥就可以构造出合法的数字签名。通过这种技术，可以防止因为单点故障导致的私钥丢失问题，同时还能提高钱包的安全性，防止别人盗用私钥。本次报告中，区老师介绍了其在门限椭圆曲线签名上的工作，并介绍了研究该问题用到的主要技术。
区老师介绍门限椭圆曲线数字签名研究工作
在椭圆曲线签名中，用户使用私钥 对一条消息 签名时，需要选取一个随机数 ，并计算签名 。这里 是一个公开的哈希函数， 是一个公开的值。用户需要保密其中 和 的值。因为，如果想要做一个门限椭圆曲线签名，只需要使用门限秘密分享技术分享 和 的值就可以实现我们的目标。
如何构造门限椭圆曲线签名
然而，传统的秘密分享技术至少需要执行两次 Multiplication-to-Additive（MtA）函数才能把 和 的值进行安全分享。那么有没有可能用更快的方式来构造门限椭圆曲线签名呢？区老师及其团队设计了最优的两方门限椭圆曲线签名，其通过巧妙地设计 和 的不同分享方式，实现了只需要执行一次 MtA 函数就能够完成目标的椭圆曲线签名协议。这是目前为止最好的门限椭圆曲线签名方法，其也被 Hyperledger Fabric 采纳，并使用在区块链的众多应用之中。
除此之外，区老师还介绍了其团队在改进 MtA 函数效率上的研究。通过重新设计 JoyeLibert 加密和承诺方式，区老师团队设计出一种计算效率更高，并能够节省带宽的 MtA 函数实现方法。该研究进一步提高了门限椭圆曲线数字签名的效率。
合影留念
图文 | 李济宸
往期讲座
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。