经典签名算法

数字签名是现代密码学的核心技术之一，就像数字世界里的签字和盖章，用来证明信息的来源并确保内容没有被篡改。无论是在区块链、身份验证还是安全通信中，它都扮演着不可或缺的角色。在众多签名方案中，ECDSA、Schnorr 和 BLS 是最经典、最具代表性的三种。ECDSA 以高安全性和较短密钥著称，被比特币、以太坊等主流区块链长期采用；Schnorr 签名结构简洁、易于聚合，在新一代区块链协议中备受青睐；BLS 签名则凭借天然的可聚合特性和恒定大小的签名，在多方签名和分布式系统中展现出独特优势。这些算法不仅推动了密码学的发展，也为各种安全系统奠定了坚实基础，理解它们就像掌握了数字世界的签名艺术。

一、ECDSA 签名算法

1.1 ECDSA 签名简介

椭圆曲线数字签名算法（ECDSA）是基于椭圆曲线密码学（ECC）对数字签名算法（DSA）的一种改进版本。它于 1999 年成为 ANSI 标准，2000 年被 IEEE 和 NIST 采纳为标准，早在 1998 年就已被 ISO 接受，并被纳入多个其他国际标准的讨论范围。与传统的离散对数问题（DLP）和大数分解问题不同，椭圆曲线离散对数问题（ECDLP）目前没有已知的亚指数时间求解方法，因此在相同的安全等级下，ECC 所需的密钥长度远小于其他公钥密码体制，计算与存储效率更高。

有趣的是，ECDSA的前身DSA是ElGamal和Schnorr方案的结合，而DSA签名完全是为了规避Claus Schnorr的专利而设计的。事实上，就在Schnorr的美国专利发布两个月后，DSA的创造者美国国家标准与技术研究院（NIST）也为其解决方案申请了专利。Schnorr一度对此表示不满，并直接发邮件对其进行的批评。

1.2 DSA签名方案

作为ECDSA签名的"前身"，首先对DSA签名算法做一个简单的介绍，读者可以将ECDSA签名和DSA签名算法对比学习。由于下面会详细介绍ECDSA算法，这里DSA算法的介绍不在遵循标准的签名介绍方法，二十简单对其进行介绍。

1. 密钥生成：随机生成一个1024bit的大素数p，并找到p-1的一个160bit的素除数q 。找到一个q阶子群的生成元 $\alpha$ 并选择一个随机的整数 $d\in z_q^* $, 然后计算 $\beta \equiv \alpha^d \pmod p $ 。选择一个哈希函数 H 。 则公钥为 $K_{pub}=(p,q,\alpha,\beta,H)$ , 私钥为 $k_{pr}=d$.

2. DSA签名

1. 选择一个随机的整数 $k_E \in Z_q^* $,
2. 计算 $r\equiv (\alpha^{K_E} \pmod p) \pmod q$
3. 计算 $s\equiv (H(x)+d\cdot r)\cdot k_E^{-1} \pmod q$
4. 最终的DSA签名结果是一对 $(r,s)$

3. DSA验签

1. 计算辅助值 $w\equiv s^{-1} \pmod q$
2. 计算辅助值 $u_1 = w\cdot H(x) \pmod q$
3. 计算辅助值 $u_2 = w\cdot r \pmod q$
4. 计算 $v\equiv (\alpha^{u_1} \cdot \beta^{u_2} \pmod p) \pmod q$
5. 如果 $v=r \pmod q$ 则认为他是一个有效的签名，否则认为他是一个无效的签名。

1.3 ECDSA签名方案：

椭圆曲线数字签名算法（ECDSA）是一种基于椭圆曲线密码学（ECC）的数字签名方案，它在保证高安全性的同时，能以较短的密钥长度实现与传统公钥算法相同的安全等级，因此在区块链、TLS、加密货币等领域得到了广泛应用。它的基本流程包括系统初始化、密钥生成、签名和验签四个步骤，下面我们按照这个顺序，结合数学公式，来详细介绍 ECDSA 的工作原理。

1. 系统初始化 Setup
   系统初始化阶段，用来生成必要的签名参数。具体过程是：选择有限域$F_p$上的一个椭圆曲线$E(a, b)：y^2=x^3+ax+b \ (mod \ p)$且对于$E(a, b)$来说，它满足$4a^3+27b^2≠0\ (mod \ p)$ 选择$E(a, b)$上的一个点 $P$ 作为生成元，其中 $P$ 的阶为$n$ 。选择一个哈希函数 H , 则最终的参数为 $Params = ( E(a, b), P , H )$ 。

2. 密钥生成 KeyGen
   该过程用来生成用户的公私钥对，用于后续的签名（Sign）和验签（Verify）。选择随机数 $sk$ 作为私钥(其中k<n)，计算公钥 $P_{pub}=sk\cdot P$

3. 生成签名 Sign
   选择随机数$r$，计算$r\cdot P=(R, y)$。其中 $r\cdot P$ 是横纵坐标分别为 R 和 y 的椭圆曲线上的点。
   计算$h=H(m)$ 和 $s = r^{-1}(h + sk\cdot R) \pmod n$ （这里，$k^{-1}$是k在模n下的乘法逆元）
   则最终签名为$σ=(R, S)$。（注意，如果r, s中任意一个为零，重新选择随机数计算签名）

4. 验证签名 Verify
   假设收到的签名是 $(m, σ)=(m, R, S)$ 计算 $h = H(m)$
   计算 $(s^{-1}\cdot h)P+(s^{-1}\cdot R)P_{pub}=(x_1, y_1)$
   比较 $r_1≡x_1\ (mod\ p)$ 和 $r_1=R$ 是否成立，如果成立，验签成功。否则，验签失败

采用ECDSA的弊端主要有两个：

• ECDSA的验签过程中，需要进行求逆运算，计算开销较高。
• 不支持批量验证和多重签名，导致验证多个签名的开销会随着签名数量的增加而线性增长。

参考文献

• DSA签名
• ECDSA(2,2)多重签名实现

二、Schnoor 签名

2.1 Schnoor签名简介

Schnorr签名由德国数学家和密码学家Claus-Peter Schnorr于1990年在论文中提出，具有‌签名长度短、‌计算开销低、可扩展性强等优点，并且支持密钥聚合和批量认证。Schnoor签名的安全性基于离散对数困难问题，被广泛认为是一种安全可靠的签名方案。经过多年的发展，Schnoor签名还衍生出了多重签名、门限签名等扩展，并在身份认证、比特币、区块链等方面获得大量应用。 Schnoor签名本质上是一种零知识的技术，即Prover声称知道一个密钥x的值，通过使用Schnorr签名在不揭露x的情况下向Verifier证明其对x的知情权。（也就是证明自己拥有私钥）

2.2 作者简介

Schnoor于1970年获得University of Saarbrücken大学博士学位。Schnorr对密码学的贡献主要是对Schnorr groups的研究，这些研究被用于以他的名字命名的数字签名算法中。除此之外，Schnorr还因其对算法信息论的贡献和创建了一种算法随机序列的定义方法而闻名，该方法可替代Martin-Löf随机性的概念。 Schnoor于1993年获得莱布尼茨奖。2013年获得RSA数学卓越奖。

Schnoor在论文发表之前就申请了Schnoor签名的专利，直到2008年，该签名的专利才到期。有趣的是，2008年正是中本聪（Satoshi Nakamoto）开始创造比特币的时间。在比特币的构造过程中，需要考虑的一个关键设计是使用哪种签名方案。事实上，Schnoor签名与ECDSA相比更加适合于比特币系统的构建，但由于Schnoor签名的专利一直被Schnoor持有，而ECDSA没有专利问题，并且已经被开源加密工具OpenSSL支持，中本聪最终选择了ECDSA。直到多多年以后，Schnoor签名才被正式应用于比特币和区块链中。

2.3 签名方案

Schnoor签名分为交互式和非交互式两种，为了方便描述，我们称交互式的方案为 Schnoor 协议，非交互式的为 Schnoor签名。需要指出的是，在Schnoor签名的原始论中，作者是基于离散对数困难问题构造的签名方案，而椭圆曲线可以用更短的签名长度达到同样的安全级别，本文的介绍使用的是椭圆曲线上的Schnoor签名。

2.3.1 交互式的Schnorr协议

1. 系统初始化 Setup
   系统初始化阶段，用来生成数字签名需要用到的参数。具体过程是：选择一个p阶椭圆曲线E(a,b)以及它的生成元G，生成公共参数 pp = { E(a,b) , p , G } 并将其公布。

2. 密钥生成 KeyGen
   该过程用来生成用户的公私钥对，用于后续的签名（Sign）和验签（Verify）。假设要给用户 $U_a$ 生成公私钥对 , 首先生成一个随机数 $a \in_R Z_p^* $ , 计算 $PK=a*G$ , 令 $U_a$ 的公私钥对为 $(sk,PK)=(a,PK)$.

3. 签名和验证 Sign & Verify
   在交互式的签名过程中，签名者和验签者需要同时参与到签名的生成和验证过程中。假设Alice想要生成一个签名让Bob验证，并且共公共参数 pp Alice和Bob都知道，Alice的私钥为 a ，公钥为 PK 且 Bob已经获得了 PK 。交互式的Schnoor协议过程如下：

   • Alice 生成一个随机数 $r \in_R Z_p^* $ 并计算 $R=r\cdot G$, 然后将 R 发送给 Bob ；
   • Bob 选择一个随机数 c 作为挑战发送给 Alice ；
   • Alice 计算 $z=r+c\cdot sk$ 并将其发送给 Bob ;
   • Bob 验证等式 $z\cdot G=R+c\cdot PK $ 是否成立，如果成立，则验证签名成功。

说明

在协议开始之前，Bob知道Alice的公钥是 PK ，如果Alice知道私钥 sk ，那么它可以很容易的计算出$z=r+c\cdot sk$ ，将该等式两边同时乘G可得：$z\cdot G=c\cdot PK+R$。也就是说，如果Bob验证了上述等式，即可验证Alice确实拥有私钥sk。 (在上述协议中，验证者Bob并不能得到私钥sk的信息，因此这个过程是零知识的，且是交互式的。此协议是Sigma protocol的一个特例)

上述协议的的过程如下图所示：

该协议的一些分析

1. 零知识性（诚实验证者）
   交互式 Schnorr 协议是一个三步的 Σ-协议。在诚实验证者模型下，该协议是零知识的：存在高效模拟器可以直接生成与真实交互分布一致的记录 $(R, c, z)$，而无需知道私钥 $sk$。模拟器的典型方法是：先随机选择 $c, z \in \mathbb{Z}_q$，再设 $ R = z \cdot G - c \cdot PK $ 即可得到满足验证等是的三元组。证明存在模拟器是证明协议满足零知识性的一种常见做法，直观的解释如下：
   由于模拟生成的签名与真实签名在分布上不可区分，验证者无法判断签名是由模拟器生成还是由真实算法生成，因此无法从签名中提取任何关于 sk 的信息。若验证者能够从真实的签名中获得 sk，那么同样可以从模拟器生成的签名中获得 sk ，但模拟器本身并不掌握 sk，这显然是不可能的，因此签名不可能泄露私钥，也就保证了对密钥的零知识性。

2. 非公开可验证性
   由于该协议是交互式的，验证结果仅对参与交互的验证者有效，第三方无法直接通过交互记录确认证明者的身份，下面举一个Mallory 与 Bob 串通的例子。 假设 Mallory（冒充者）与 Bob（验证者）串通，约定 Bob 在协议中会返回一个特定的挑战 $c_0$

   • Mallory 生成随机数 $r \in_R \mathbb{Z}_q$，计算 $R = r \cdot G - c_0 \cdot PK$ 并将其发送给 Bob；
   • Bob 返回预先约定的挑战 $c_0$；
   • Mallory 回复 $z = r$；
   • Bob 验证 $z \cdot G = R + c_0 \cdot PK$ 结果成立，于是验证通过。

   从外部观察者的角度，这份交互记录与 Alice 和 Bob 的正常交互没有区别，但实际上 Mallory 并不知道 Alice 的私钥 $sk$。这说明，除了直接参与交互的验证者外，任何第三方都无法通过协议内容确认 Prover 的真实身份。

   挑战随机性的重要性：
   如果 Prover 能够提前预测或影响 Verifier 选择的挑战 $c$，同样可以在不掌握私钥的情况下提前构造可通过验证的交互记录。例如，Prover 可直接选取 $R = r \cdot G - c \cdot PK$ 并在收到挑战后回复 $z = r$，即可通过验证。因此，挑战必须由验证者随机、均匀、不可预测地生成，且挑战空间应足够大，以防止伪造。 若希望获得可公开验证的版本（如数字签名），可采用Fiat–Shamir变换将挑战设为 $c = H(R, \cdots)$ 从而在随机预言机模型下得到可公开验证的 Schnorr 签名。

3. 完备性与知识可靠性（Soundness / Proof of Knowledge）
   协议具有完备性（completeness）：诚实双方在正确执行协议时，验证总能通过。
   协议还具备知识可靠性：从同一承诺 $R$ 下、针对两个不同挑战 $c_1 \neq c_2$ 的两个可接受响应 $$ z_1 = r + c_1 \cdot sk, \quad z_2 = r + c_2 \cdot sk $$ 可以计算出 $ sk = (z_1 - z_2) \cdot (c_1 - c_2)^{-1} \pmod q $ 这表明协议是一个知识证明：如果没有私钥 $sk$，在一次交互中通过验证的概率至多为 $1 / |\mathcal{C}|$（挑战空间大小的倒数）。通过增大挑战空间或多轮交互，可以将这种概率显著降低。

2.3.2 非交互式的Schnorr签名

将交互式的Schnorr协议改造为非交互式 Schnoor签名非常简单。通过上述分析我们知道，保证协议中 Verifier 选择的挑战 c 的随机性是保证该协议安全的关键。Fiat-Shamir启发式方法假设存在抗碰撞的哈希函数 H，它的结果在随机预言机模型下被认为是随机的，由于哈希函数的不可逆性改造上述交互式协议，得到一个非交互式的 Schnoor 协议，也称 Schnoor 签名。

1. Schnorr 签名的过程如下：

1. Alice：随机选择 r，计算$R=r*G$ （椭圆曲线上的一点）；
2. Alice：计算 $c = H(R, PK)$；
3. Alice：通过计算 $z=r+c\cdot sk$， 将$(R, z)$给Bob；
4. Bob： Bob计算 $c=H(R,PK)$，Bob验证 $z\cdot G = c\cdot PK+R$。

需要说明的是，在正式的Schnoor签名中，存在一个被签名的消息 m ，我们需要做的是修改 c 的计算方式为 $c=H(R,PK,m)$，其余部分保持不变即可得到消息 m 的 Schnoor签名 (R,z) 。

2. 非正式的分析：
   下面粗略的分析一下上述Schnoor签名的安全性，正式的安全性证明请参考原文.

   • 上述 Schnoor 协议之中，Prover 和 Verifier 之间进行串通能够骗过非协议交互方的原因是 Prover 提前预知（通过串通）了一个与协议其他参数无关的挑战 c ，而在 Schnoor 签名中 c 由随机预言机 H 生成，无法被 Prover 预测，故 Schnoor 签名是安全的。
   • 在上述串通的 Schnoor 协议中，Mallory 预先串通得到 c ，通过计算 $R=r\cdot G - c \cdot PK$ 并令 z = r 使得 非交互式 Schnoor 协议无法公开验证。 而Schnoor签名(R,c,z)的计算过程中$c=H(R,PK)$。如果使用同样的方式进行伪造会发现，计算 R 需要用到 c ，计算 c 需要用到 R ；故导致敌手伪造 Schnoor 签名。
   • Sigma协议和Fiat-Shamir启发式：
     • https://www.yuque.com/xiaozeng-lhkfj/guc7a3/egsn1gzebrmkfcz1#fuMTK【笔记】

3. Schnorr签名的批量认证
   Schnorr 签名的一个优势在于它的线性结构，这使得我们可以将多个签名的验证合并为一次批量验证，从而在实现上获得效率提升（尤其是在需要验证大量签名的区块链等应用中）。

   • 单个 Schnorr 签名验证
     给定公钥 $PK_i = sk_i \cdot G$，消息 $m_i$，签名 $(R_i, z_i)$，验证过程即检查下式是否成立： $$ z_i \cdot G \stackrel{?}{=} R_i + c_i \cdot PK_i\ ; \ c_i = H(R_i, PK_i, m_i) $$
   • 批量验证的思路
     如果需要验证 $n$ 个签名 $(R_i, z_i)$，逐一验证上式的代价是：
     $n$ 次固定基点乘（$z_i \cdot G$）+ $n$ 次变基点乘（$c_i \cdot PK_i$）+ $n$ 次加法和哈希【可忽略】
     为了减少开销，可以将上述所有 $n$ 个验证式线性组合，得到一个等价条件： $$ \Big(\sum_{i=1}^n z_i\Big) G \stackrel{?}{=} \sum_{i=1}^n R_i + \sum_{i=1}^n c_i PK_i $$ 这样一来，批量验证的代价只需要：
     1 次固定基点乘 $(\sum z_i)G$ + $n$ 次变基点乘$(\sum_{i=1}^n c_i PK_i)$ + 若干次加法和哈希【可忽略】
   • 如果直接把等式相加，攻击者可能构造一组伪造签名让等式在整体上成立。引入随机权重 $a_i$ 可以防止这种攻击，保证批量验证的安全性。具体来说，可验证一个等价验证条件为： $$ \Big(\sum_{i=1}^n a_i z_i\Big) G \stackrel{?}{=} \sum_{i=1}^n a_i R_i + \sum_{i=1}^n (a_i c_i) PK_i $$

2.4 Schnoor多重签名

密钥聚合与签名生成:

这里我们引入一个聚合器 Agg ，她负责执行一些特点的操作，Agg 可以由生成多重签名的某个实体担当，也可以由其他任意实体充当。Schnoor多重签名的生成过程如下：

1. 聚合器 Agg 将签名者的公钥集合 $(PK_1,…,PK_n)$ 聚合称一个聚合公钥 $P = \sum_{i=1}^n PK_i$ ；
2. 每个用户分别选择随机数 $r_i$ 并计算 $R_i = r_iG$，随后每个人将自己的 $R_i$ 广播给其他人；
3. 收到 $\{R_i\}$ 后计算$R=\sum_{i=1}^nR_i$ 和 $c = H(m,P,R) ; s_i = r_i + c \cdot sk_i $ 并广播 $(R_i,s_i)$；
4. 聚合器 Agg 收到 n 个人的签名 $\sigma_1,…,\sigma_n$后，计算 $z=\sum_{i=1}^nz_i$ ， 最终的签名为 $(R,z)$；

多重签名验证：

验证者 Verifier 计算$c = H(m,P,R)$, 然后验证等式 $z\cdot G=R+c\cdot P$ 是否成立，如果成立，则完成了对n个用户的批量认证。 上述多重签名的过程似乎并未减少总的计算开销，那么他有什么用呢？事实上，上述多重签名的生成与验证过程计算量是不对称的，生成签名的计算量很大，但是验证签名的计算量永远都是验证一个签名的计算量。这个性质在某些应用场景下是非常有用的，比如在区块链中，某一个交易可能需要多个人的签名才能生效，而交易发出去之后，所有人都需要验证这个交易的合法性，此时验证成本低廉很有用。

这里提一句，Schnoor签名可以通过Merkle树实现(m,n)多重签名，有兴趣的读者可以自行搜索。

存在的问题

1. 上述Schnoor多重签名的生成过程需要签名方之间进行交互，当多重签名的用户比较多的时候，整个交互流程比较复杂。（暂时无法解决，最新的FROST签名可以做到半交互式）
2. 存在流氓密钥攻击。(可通过修改方案预防，具体来说是将签名和密钥的聚合过程改成非线性的,参考《Simple Schnorr Multi-Signatures with Applications to Bitcoin》或BLS的方案)
3. Schnoor签名实际上是一个零知识证明，它具有soundness，也就是存在一个提取器。因此所有的签名不能使用同一个随机数 r ，否则可以提取私钥(参考零知识证明)。

参考文献：

• http://blockchain.whu.edu.cn/uploads/soft/201105/1_1954088811.pdf
• Schnoor签名还可以实现(t,n)门限签名，聚合签名等，读者可自信搜索。

三、BLS短签名

3.1 BLS签名简介

BLS签名，由斯坦福大学计算机系的Dan Boneh，Ben Lynn以及Hovav Shacham在2001年提出，其核心思想是将待签名的消息哈希到椭圆曲线上的一个点，并利用双线性映射函数e的交换性质，在不泄露私钥的情况下进行签名验证。BLS签名被称为"BLS短签名"，因为签名本身只是椭圆曲线上的一个点，是已知的签名长度最短的签名。 BLS签名具有多个有趣的特性，例如支持签名的聚合和批量验证，还可以构建门限签名等。这些特性使得它在区块链等领域得到广泛应用。作为第一个使用双线性映射的数字签名方案，BLS签名对后续的数字签名乃至密码学的发展产生了重要影响，为后续更复杂、更广泛应用的签名方案奠定了基础。

3.2 作者简介

Dan Boneh于1969年生于以色列，并于1996年从普林斯顿大学获得计算机科学博士学位、并于1997年加入斯坦福大学任教至今，在Coursera上开设了大规模的开放在线课程，出版了很多密码学相关书籍、教材，以免费在线提供他的整个密码学入门课程而闻名。

Boneh与加州大学的Matt Franklin是基于配对密码学发展的主要贡献者之一，2016年被选为美国国家工程院院士。他在基于身份的加密、广播加密、同态加密、区块链等多个密码学领域均有重要成果发表；参与设计tcpcrypt用于传输层安全的TCP协议扩展，提出了一种针对HTTP协议的侧信道攻击和对OpenSSL的时序攻击，在比特币方面也有成果产出。他曾获哥德尔奖、RSA数学杰出奖、Selfridge奖、斯隆奖、ACM计算奖等。他担任斯坦福大学区块链研究中心的联合主任，并在2002年与三名学生创办名为Voltage Security的公司，随后于2015年被惠普收购，是即会理论又能实践的大佬。

3.3 BLS具体方案

Map to point Hash函数简介： 一般的hash（散列）函数的结果都是数值。在BLS签名算法中需要用的散列函数的结果是椭圆曲线上的一个点。SHA-256作为普通Hash函数的输出结果是256位，如果用Hash函数的数值结果对应于椭圆曲线上点横坐标x，有两个点y和-y都在椭圆曲线y²=x³+ax+b上。由二次剩余理论可知，有50%的概率找到两个点，同样有50%概率找不到点。

为了解决这个问题，需要用到直接从消息计算到一个点的哈希，给定消息 m，计算H(m)，使得 H(m)∈ G，其中G是椭圆曲线点构成的群。Dan Boneh在文章中给出了一个具体的做法，例如采用的仍然是普通哈希，把结果当作是一个点的 x 坐标，然后带入椭圆曲线公式计算相应的 y 坐标。如果不存在，则把第一步的 x 坐标作为输入继续算哈希得到另一个 x 坐标，计算相应 y坐 标，直到求出 y 为止。根据二次剩余理论，平均算2次即可得出一个对应的 y 。这样确保首先是一个确定性的算法，可以在有限步骤内(数学期望为2次)完成计算；其次，如果采用的哈希函数本身是安全的，则整体的计算过程也是安全的。这样整个计算称为Map-to-Point哈希。

BLS签名方案

假设Alice的私钥为$pk$，公钥为$P = pk×G$，想对消息 m 签名，则：

• 签名：计算$S = pk×H(m)$作为消息 m 的签名
• 验签：判断$e(P, H(m)) = e(G, S)$是否成立，成立则验签成功。

证明过程如下： $e(P, H(m)) = e(pk×G, H(m)) = e(G, pk×H(m)) = e(G, S)$

3.4 BLS多重签名

多重签名定义： 在数字签名应用中，有时需要多个用户对同一个文件进行签名和认证。比如，一个公司发布的声明中涉及财务部、开发部、销售部、售后服务部等部门，需要得到这些部门签名认可，那么，就需要这些部门对这个声明文件进行签名。能够实现多个用户对同一文件进行签名的数字签名方案称作多重数字签名方案。

在现实生活中，一份文件经常需要几个单位或部门分别签字(或盖章)才有效，多重签名技术就是在网络环境里解决这类问题的一种方法，用于同一文档必须经过多人的签名才有效的情形。多重签名通俗地讲就是指多个签名者共同参与对一份电子文档进行签名。简单地说，一个多重签名体制回答这样几个问题：哪些人参加签名，按照什么顺序签名，使用什么方法签名，怎么验证签名和安全性如何得到保证。BLS签名支持多重签名方案。

BLS多重签名

沿用上面的符号，我们假设有n个用户，它们的公私钥对分别为($P_i,pk_i$)，它们欲对同一个消息 $m$ 进行签名得到一个BLS多重签名。假设第 i 个用户对消息 $m$ 的 BLS 签名为 $S_i$ ，我们可以使用以下方式生成这些用户对消息 $m$ 的多重签名。

将 n 个用户的签名 $S_i$ 进行累加即可得他们对消息 m 的多重签名 $S = S_1+S_2+…+S_n$ , 其中 $S_i = pk_i×H(m)$;i={1, 2, …, n}。 为了验证多重签名的合法性，首先计算 $P=\sum_{i=1}^n P_i$ 作为验证该多重签名的聚合公钥，然后验证等式 $e(G, S) = e(P, H(m))$ 是否成立即可。

我们可以看出，使用BLS多重签名可以使得 n 个人的签名大小和一个人的签名大小完全一样，并且签名的验证过程比挨个验证 n 个签名计算量少了几乎一半。正确性显然成立，这里不再证明。

问题与改进

上述最直观的BLS多重签名方案容易受到"流氓密钥攻击"。比如说，Alice公私钥对为 $(pk_1,P_1)$ , 同时 Bob 的公私钥为 $(pk_2,P_2)$ , Bob可以对外声称自己的公钥为 $P’=P_2 - P_1$, 那么他可以使用自己的私钥生成BLS签名 S 作为他与Alice的多重签名，其他人认为 $P=P_1+P’=P_2$ 是 Bob 与 Alice 的聚合公钥，并使用它验证签名 S 。很显然验证可以通过，但实际上Alice并未参与这个多重签名。如果一笔钱需要 Alice 和 Bob 共同授权才能使用，那么 Bob 可以通过这种方式独自控制这笔财产。为了防止这种攻击，可以使用非线性方式构造聚合公钥。具体方式如下:

将 n 个用户的签名 $S_i$ 进行非线性累加得 $S = a_1S_1 + … + a_nS_n$ , 其中 $S_i = pk_i×H(m)$ 且 $a_i=H(P_i,\{P_j\}) ; i,j=\{1, 2, …, n\}$。我们将 $S$ 作为这 n 个用户对消息 m 的多重签名。 为了验证多重签名的合法性，验证者首先计算非线性聚合公钥 $P=\sum_{i=1}^n a_iP_i$ 作为验证该多重签名的聚合公钥，然后验证等式 $e(G, S) = e(P, H(m))$ 是否成立即可。

上述多重签名能够防止流氓攻击的关键是签名和聚合公钥的构造中，非线性系数 $a_i$ 与多重签名的所有参与者的公钥都有关，改变任何一个参与者的公钥都会导致所有系数的变化，这将导致攻击者无法同时控制自己的公钥和系数，从而大大增加了流氓密钥攻击的难度。

3.5 BLS阈值签名

阈值签名方案(TSS)是一种从多个签名者生成单一数字签名的方法。生成的签名看起来与没有使用阈值方案生成的签名一样,但它并不是由单一私钥创建的。相反,它是由多个私钥份额创建的,这些份额是分布式的,因此没有任何单一个人完全控制私钥。在阈值签名中，假设有 n 个参与者拥有秘密份额，要生成一个消息的签名, 至少需要 t 个人参与，则我们记这种阈值签名为(t,n)阈值签名。

秘密份额分发方法

要想进行阈值签名，首先要为参与者分发秘密份额，这个过程有很多方法。可以使用可验证的秘密共享进行分布式密钥协商，从而得到每个人的秘密份额。也可以使用一个秘密分发者进行秘密分发的方式进行份额的分发。它们的区别是，使用分布式秘密生成份额可以在开放的环境中进行，并且没有人知道真正的秘密值，所有人都只知道自己的秘密份额，但是这种方案计算开销较大。而是用秘密分发者的方式进行份额分发，必须在安全的环境中进行，并且秘密分发者知道所有人的份额和秘密，但计算开销很小。这里使用秘密分发者在安全通道分发秘密份额。

秘密份额分发

1. 秘密分发者首先随机生成 $ t - 2 $ 个小于 $ p $ 的随机数 $ a_{1}, a_{2},…, a_{t - 1} $ 并构造一个 t-1 阶的多项式 $ f (x) = a_0 + a_{1} x + … + a_{t-1} x^{t-1}$ ，其中公私钥对为 $\big(f (0) = a_{0} = s\ ;\ PK = sP\big)$。

2. 秘密分发者随机选取 $ n $ 个互不相同的整数 $ x_{1}, x_{2}, \cdot, x_{n} $ 并将 $ n $ 个整数代入多项式函数 $f(x)$得到 $ n $ 个值 $ sk_1 = f (x_1)$, $ sk_2 = f(x_2)$,…, $sk_{n} = f (x_{n}) $ , 然后将计算得到的 $ n $ 个坐标 $(x_i,y_i)$ 分别发给 $ n $ 各参与方并销毁 $ f (x) $，即第 $ i $ 个参与方获得 $ (x_{i}, y_{i}) $ 。为了简单起见，可以假设 $x_i = i$ ，这并不影响方案的安全性。

阈值签名的生成

• 情况一： 为生成一个阈值签名，至少需要 t 个参与者合作，参与者 i 计算拉格朗日插值函数值 $L_i = \prod_{j\in[n]}^{j\neq i} \frac{i}{j-i}$ ，然后使用自己的秘密份额生成消息 m 的部分签名 $S_i=sk_i\cdot L_i\cdot H(m)$. 随后将自己的部分签名广播出去。

• 情况二: 另外，也可以把拉格朗日插值函数值的计算放到验证者哪里执行，此时签名者 i 只需要计算消息 m 正常的BLS签名 $S_i=sk_iH(m)$并广播出去。

阈值签名的验证

• 情况一验证： 任何人在收到 t 个合法的部分签名之后，可以使用群组公钥 $PK$ 验证阈值签名的合法性。具体来说，验证者首先聚合收到的 t 个部分签名为 $S=S_1+…+S_t$ 。 然后验证等式 $e(S,G)=e(H(m),PK)$ 是否成立，如果成立，则签名验证通过。

• 情况二验证： 任何人在收到 t 个合法的部分签名之后，可以首先首先计算每个部分签名对应的拉格朗日插值函数值$L_i = \prod_{j\in[n]}^{j\neq i} \frac{i}{j-i}$，然后计算阈值签名 $S=L_1S_1+…+L_tS_t$ 。最后验证等式 $e(S,G)=e(H(m),PK)$ 是否成立，如果成立，则签名验证通过。

参考文献：

• ECDSA Schnoor BLS 对比