Cobo 密码知识讲堂｜第五讲：探索聚合签名奥妙

作者：Cobo 密码学团队

随着香港开始允许散户交易数字资产，数字资产也在逐步走进每个人的生活，数字资产、数字签名等新概念层出不穷。Cobo 密码知识讲堂计划推出以“门限签名”为主题的系列科普文章，旨在以深入浅出的方式，带领读者了解数字签名中门限签名的技术本质和应用原理。该系列科普文章每一篇内容相互独立又互相补充，涵盖门限签名的概念及典型应用、ECDSA 门限签名的设计及发展现状、Schnorr 门限签名的设计及发展现状、基于门限签名的账户体系构建，以及层级化门限签名设计等多个该领域的热点和难点问题，力求通过对技术研究的深层次剖析和解读，让读者对门限签名领域有更加深刻的理解。

《Cobo 密码知识讲堂｜第一讲：门限签名的概念与应用》

《Cobo 密码知识讲堂｜第二讲：ECDSA 算法及其门限化设计介绍》

《Cobo 密码知识讲堂｜第三讲：ECDSA 门限签名典型算法介绍》

《Cobo密码知识讲堂｜第四讲：ECDSA 门限签名算法分析与比较》

本讲概述：在前面几期课程中，我们重点介绍了门限签名技术，包括其概念、技术路线以及典型算法。本期我们将开启一个新篇章，介绍另一种密码学技术——“聚合签名”。该技术已经广泛应用于区块链领域，如 Eth2.0 中的信标链使用到了 BLS 聚合签名算法，而 Bitcoin 的 Taproot 升级也增加了对 Schnorr 聚合签名的支持。本期内容由四部分组成：首先，介绍聚合签名的概念和算法组成；其次，从设计动机和适用范围两个维度比较聚合签名和门限签名的差异；再次，详细描述聚合签名设计的难点、面临的安全风险以及可能的抵御手段；最后，介绍 BLS 聚合签名和 Schnorr 聚合签名的两个典型算法实例。

Part 1：聚合签名的概念

聚合签名（Aggregate Signature）是一种有广阔应用前景的密码学组件，是近年来学术界和产业界的研究热点，其相关研究成果纳入密码学顶级会议和期刊。在聚合签名下，多个主体针对不同或相同消息的签名，能够有效“压缩”为单个签名，对该签名的验证能够实现对多个签名“批量”验证的效果。由于其较低的计算和存储消耗，聚合签名目前广泛应用于分布式系统中。具体而言，聚合签名由算法六元组 AS=(Setup,Keygen,Sign,Verify,AggS,AggV) 组成，具体含义如下：

Setup：系统启动函数，输入安全参数，输出系统公共参数，如椭圆曲线、基点、有限域等；
Keygen：密钥生成函数，输入公共参数，输出公钥和私钥；
Sign：签名函数，输入私钥和待签名消息，输出签名结果；
Verify：签名验证函数，输入签名消息、公钥、签名，若签名合法，则输出 True，否则输出 False；
AggS：签名聚合算法，输入多个节点的签名，输出聚合后的唯一签名；
AggV：聚合签名验证算法，输入聚合签名、签名信息和节点公钥信息，若所有参与聚合的签名合法，则输出 True，否则输出 False。

需要说明的是，(Setup,Keygen,Sign,Verify)构成一个完整的数字签名方案，因此聚合签名并不是一种“平地而起”、特殊构造的签名算法，而是基于已有数字签名算法所构造的具有特殊性质的新型签名算法。此外，个别聚合签名算法也单独设置了公钥聚合算法 AggPK，但是也可以将该算法过程融合到 AggV 计算过程中，因此不额外赘述。

Part 2：聚合签名和门限签名的区别

聚合签名和门限签名都是需要多个节点参与且最终输出唯一签名，也都应用于区块链中的“访问控制”（广义概念）设计，因此非密码学专业人士，往往会对两种技术产生混淆，对二者的关联关系认识不够清晰。以下从设计初衷和技术特征两个方面去对比聚合签名和门限签名。

（1）设计初衷

门限签名的设计核心在于两个词，即“权力拆分”和“容错”：“权力拆分”，就是将签名的权限从单一节点掌握，拆分下发到多个节点，每个节点都掌握部分签名权力，且都是对等关系；“容错”则是门限化后的特有特征，即完整签名权力的恢复并不需要所有节点参与，而是超过门限数量的节点参与即可。

聚合签名的设计核心也在于两个词，即“批处理”和“压缩”：“批处理”是指多个节点的签名结果的正确性能够进行批量验证，一次运算完成签名的验证；“压缩”则是指多个节点的数字签名能够转化成一个唯一数字签名，既能降低存储消耗，又为批量验证建立数据基础。

通过上述分析我们可以发现，门限签名和聚合签名有着迥然不同的设计初衷（图1）。门限签名采用的是“由内向外”的设计哲学，将一个存在于理论层面的主公钥签名权限向外拆分；聚合签名则采用的是“由外向内”的设计哲学，即将多个现实存在的公钥签名结果汇聚为合成的唯一签名。

需要注意的是，还有另外一个概念是多重签名（Multi-Signature），该技术等价于节点签名消息一致情况下的聚合签名。

（2）技术特征

聚合签名和门限签名具有不同的技术特征，我们可以从六个维度开展对比（表1）：

私钥生成方式：聚合签名下，节点的私钥为各自在本地生成，无需和其他节点进行交互，节点之间的私钥不存在计算关系；门限签名下，节点通过一系列的交互、以分布式的方式完成私钥碎片的生成，且所有节点的私钥碎片共同构成主私钥的 Shamir 秘密分享。需要强调的是，无论是聚合签名还是门限签名，最终签名对应的私钥都是理论存在，并不会在计算过程中出现。
签名大小：聚合签名和门限签名的输出结果均与普通数字签名大小一致。
底层算法线性度：聚合签名下，底层数字签名算法需要具备线性特征，如 Schnorr 签名、BLS 签名等；门限签名下，对底层数字签名算法的线性度无明确要求。
兼容性：聚合签名下，如果各节点的签名消息相同，则聚合后签名的验证方法和普通数字签名一致，满足兼容性，如果各节点的签名消息不同，则不满足兼容性；门限签名下，签名结果与普通数字签名结果不可区分，满足兼容性。
门限化：聚合签名不支持门限化设置，门限签名天然具备门限化特征。
计算复杂度：聚合签名的计算复杂度略高于普通数字签名算法，会有 1 到 3 轮的交互，取决于底层签名算法以及聚合算法；门限签名的计算复杂度要高于普通签名算法，往往会伴随多轮交互，交互轮数一般 4 轮以上。

表1：聚合签名和门限签名的对比

比较维度	聚合签名	门限签名
私钥生成方式	节点本地生成	分布式生成
签名大小	和普通数字签名大小一致	和普通数字签名大小一致
底层算法线性度	底层算法需具备线性特征	无明确要求
兼容性	取决于签名消息是否一致	满足
门限化	不支持	支持
计算复杂度	稍复杂于普通数字签名算法	复杂于普通数字签名算法

Part 3：聚合签名算法的设计难点及解决思路

门限签名的设计难点是“门限化”的构造，比如 ECDSA 极差的线性特征使得构造门限签名需要复杂的密码学技术实现（如同态加密、零知识证明等）。而聚合签名的难点不在于“聚合”的实现，而是聚合后安全性的保证。因为聚合签名底层的签名算法线性度很高，这是一把双刃剑，在容易实现聚合的同时，也很容易通过巧妙构造伪造出合法的签名。目前常见的攻击手段有两种，即 Rogue Key Attack 和 Dijvers Attack，分别做简要介绍：

Rogue Key Attack：在这种攻击下，攻击者会基于诚实节点的公钥和签名过程中所选择的随机数去构造一个“虚假公钥”。攻击者并不掌握该公钥对应的私钥，但是使用虚假公钥参与聚合签名，会在签名过程中抵消诚实节点的公钥信息，仅留下攻击者真实公钥信息。因此攻击者基于其真实私钥可以生成攻击者和诚实节点对某个消息的聚合签名，从而达到签名伪造的目标。抵御 Rogue Key Attack 的常用方法是要求每个节点在公布公钥时候，都要提供对应私钥的 Proof of Possession 证明。
Dijvers Attack：这是一种更为复杂的攻击，攻击者同时发起多个签名请求，待诚实节点返回其签名随机数信息以及签名后，借助 Wagner’s Algorithm 进行碰撞构造，输出攻击者需要选择的随机数值，从而保证多个已有签名的哈希值加和等于伪造目标的哈希值，从而完成签名伪造。抵御 Dijvers Attack 的常用方法是，让节点先对自己所选择的随机数进行承诺，待所有节点选定后，再公开各自随机数。

以上两种攻击虽然都有对应的抵御方法，但是也同样产生不少应用成本，比如 Proof of Possession 证明会增加额外的计算量，而对随机数进行承诺则会使得协议增加一轮交互次数。因此如何抵御上述两种攻击，而又不增加计算复杂度和通信复杂度，是聚合签名设计的核心难点。目前解决这一难点的哲学思路是对协议中的组件进行随机化，从而形成“构造循环”，导致攻击者无法有效发动攻击。“构造循环”的具体内涵可以通过下一部分的算法实例得到体现。

Part 4：典型的聚合签名算法

在本部分，我们介绍两个典型的聚合签名算法，即 BLS 聚合签名算法和 Schnorr 聚合签名算法，前者来源于论文 BDN18（参考文献 1），后者来源于论文 MuSig2（参考文献 2）。

（1）BLS聚合签名算法

BLS 签名算法由斯坦福大学的 Dan Boneh、Ben Lynn 和 Hovav Shacham 共同提出，是构建于椭圆曲线配对（Pairing）的数字签名算法，具有短签名长度、高效性、安全性等技术优势。同时，BLS 签名也具备非常好的线性特征，因此非常适用于聚合签名的设计。

BDN18 提出的 MSP 协议是目前常用的 BLS 聚合签名算法，通过对签名的随机化，实现了对 Rogue Key Attack 的有效抵御（图 2）。具体而言，首先，基于所有参与节点的公钥信息 {pk1,pk2,...,pk3}，生成随机序列 { t1,t2,...,tn}；然后，以该随机序列去将节点的签名信息进行线性重组，生成聚合后的签名；最后，签名验证过程中，也用相同的随机序列生成聚合公钥，即可基于普通的 BLS 签名验证函数完成聚合签名的合法性验证。

在 BDN18 机制下，攻击者在发动 Rogue Key Attack 时候，需要根据其他节点公钥构造自身的虚假公钥，然而虚假公钥的加入，会直接影响随机序列，从而间接影响到聚合签名，为保证聚合签名能够验证通过，攻击者要重新构造虚假公钥，然后循环往复，就形成了前文所提到的“构造循环”，永远无法构造成功，无法成功发动 Rogue Key Attack。

（2）Schnorr 聚合签名算法

Schnorr 签名算法是由德国数学家、密码学家 Claus Schnorr 提出，是构建于椭圆曲线群上的数字签名算法，具有可证明安全、验证速度快、支持聚合签名等特征，被当前很多公链采纳作为账户管理的签名算法。

MuSig2 是当前广泛使用的 Schnorr 聚合签名算法，具备安全、通信轮数低、输出标准化、支持 Preprocess 过程等优势。相比已有的算法（如 BN06），MuSig2 并不需要节点对所选择的随机数进行承诺，因此将聚合签名的交互轮数由 3 轮降低为 2 轮。而实现这一效果同时由保证能够抵御 Dijvers Attack 的核心在于，MuSig2 对节点贡献的随机数进行了“重组”（图 3）。具体而言，每个节点不再选取一个随机数，而是选择了长度为的随机数组。然后由所有节点选择的随机数以及待签名的消息共同计算得到本次签名的随机因子 b。每个节点对签名结果贡献的随机数为其所选随机数组在随机因子 b 作用下的线性组合。

经过以上设计，攻击者在发动 Dijvers Attack 时候，需要借助 Wagner’s Algorithm，基于聚合签名构造攻击者的签名随机数，然而攻击者的签名随机数会直接影响随机因子 b，进而间接影响聚合签名，因此攻击者需要重新构造其签名随机数，然后循环往复，形成“构造循环”（图 4）。

参考文献

Boneh, D., Drijvers, M., Neven, G. (2018). Compact Multi-signatures for Smaller Blockchains. In: Peyrin, T., Galbraith, S. (eds) Advances in Cryptology – ASIACRYPT 2018. Lecture Notes in Computer Science, vol 11273. Springer, Cham.
Nick, J., Ruffing, T., Seurin, Y. (2021). MuSig2: Simple Two-Round Schnorr Multi-signatures. In: Malkin, T., Peikert, C. (eds) Advances in Cryptology – CRYPTO 2021. Lecture Notes in Computer Science, vol 12825. Springer, Cham.