BLS 签名算法原理：双线性配对、聚合签名与门限密码学

概述

BLS（Boneh-Lynn-Shacham）签名算法由 Dan Boneh、Ben Lynn 和 Hovav Shacham 于 2001 年在论文《Short Signatures from the Weil Pairing》中提出。与 Schnorr、ECDSA 等基于离散对数问题（DLP/ECDLP）的签名方案不同，BLS 签名基于双线性配对（Bilinear Pairing）构造，其核心优势在于：

• 签名极短：在 BN254 曲线上仅约 48 字节（单个 G1 群元素），是 ECDSA 签名（64-72 字节）的 2/3
• 天然聚合：任意数量的签名可以合并为单个签名，且验证成本不随签名数量增长
• 唯一性：对同一消息的签名是确定性的（无随机数），避免了随机数生成器故障导致私钥泄露的风险（如 Sony PS3 ECDSA 事件）

BLS vs Schnorr vs ECDSA 对比

数学基础：双线性配对

椭圆曲线回顾

BLS 签名通常定义在配对友好曲线（Pairing-Friendly Curves）上，如 BN254（Barreto-Naehrig 曲线，嵌入度 k=12）、BLS12-381（Boneh-Lynn-Shacham 曲线，用于 Ethereum 2.0）。这些曲线的特殊结构使得在其上可以高效计算配对运算。

设椭圆曲线 $E$ 定义在有限域 $\mathbb{F}_q$ 上，$E(\mathbb{F}_q)$ 上的点构成一个加法群。

扩域上的子群

配对密码学需要三个群：

• $G_1$：定义在基域 $\mathbb{F}_q$ 上的椭圆曲线子群，阶为素数 $r$
• $G_2$：定义在扩域 $\mathbb{F}_{q^k}$ 上的椭圆曲线子群，阶同为 $r$（$k$ 为嵌入度）
• $G_T$：扩域 $\mathbb{F}_{q^k}$ 上的乘法子群，阶为 $r$

双线性配对的定义

双线性配对（Bilinear Pairing）是一个映射：

$$e: G_1 \times G_2 \rightarrow G_T$$

满足以下三个关键性质：

1. 双线性（Bilinearity）

对任意 $P, P' \in G_1$、$Q, Q' \in G_2$ 和 $a, b \in \mathbb{Z}_r$：

$$e(aP, bQ) = e(P, Q)^{ab} = e(bP, aQ) = e(P', Q) \cdot e(P, Q')$$

这是 BLS 签名聚合能力的数学根源。

2. 非退化性（Non-degeneracy）

存在 $P \in G_1$、$Q \in G_2$ 使得 $e(P, Q) \neq 1$（即配对不恒等于单位元）。

3. 可计算性（Computability）

存在高效算法（如 Miller 算法 + 最终指数化）在多项式时间内计算 $e(P, Q)$。

常用配对类型

配对友好曲线参数

BN254 曲线（常用于 ZK-SNARK、以太坊预编译合约）：
  q = 30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd45（254 位）
  r = 30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001（254 位）
  嵌入度 k = 12
  G1 点编码：48 字节（x 坐标，1 比特标志位）
  G2 点编码：96 字节（x0 + x1，每部分 48 字节）

BLS12-381 曲线（用于 Ethereum 2.0、Zcash）：
  q = 73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001（381 位）
  r = 73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001（381 位）
  嵌入度 k = 12
  G1 点编码：48 字节
  G2 点编码：96 字节

BLS 签名协议

密钥生成

输入：安全参数 λ（选择曲线和阶 r）
输出：私钥 sk，公钥 pk

1. 随机选择 sk ∈ Z_r（私钥，一个标量）
2. 计算 pk = sk · P₂ ∈ G₂（公钥，G₂ 上的点）

其中 P₂ 是 G₂ 的生成元。

注意：私钥是一个标量，公钥是 $G_2$ 上的点（而非 $G_1$）。这是 BLS 签名的设计选择——签名放在 $G_1$ 上（更短），公钥放在 $G_2$ 上。

签名

输入：私钥 sk ∈ Z_r，消息 m ∈ {0,1}*
输出：签名 σ ∈ G₁

1. 计算消息哈希：H(m) ∈ G₁（使用哈希到曲线算法，如 SWU 方法）
2. 计算签名：σ = sk · H(m) ∈ G₁

签名是 $G_1$ 上的一个点，编码后仅 48 字节。

哈希到曲线（Hash-to-Curve）：

将任意消息映射到椭圆曲线上的点，需要特殊处理：

• 先使用标准哈希函数（如 SHA-256）将消息哈希为域元素
• 再使用确定性算法（如 Simplified SWU）将域元素映射到曲线上的点
• 最终清除 cofactor 确保结果在素数阶子群中

验证

输入：公钥 pk ∈ G₂，消息 m，签名 σ ∈ G₁
输出：有效 / 无效

验证等式：e(σ, P₂) = e(H(m), pk)

正确性证明：

$$e(\sigma, P_2) = e(sk \cdot H(m), P_2) = e(H(m), P_2)^{sk} = e(H(m), sk \cdot P_2) = e(H(m), pk)$$

这里的关键步骤利用了配对的双线性性质：$e(aP, Q) = e(P, aQ) = e(P, Q)^a$。

协议流程图

┌─────────────┐                    ┌─────────────┐
│   签名者     │                    │   验证者     │
│  (持有 sk)   │                    │  (持有 pk)   │
└──────┬──────┘                    └──────┬──────┘
       │                                  │
       │  1. H(m) → G₁                   │
       │  2. σ = sk · H(m)               │
       │                                  │
       │────── σ, m ─────────────────────>│
       │                                  │
       │                    3. 计算 H(m)  │
       │                    4. 验证配对等式│
       │                                  │
       │         e(σ, P₂) ?= e(H(m), pk) │
       │                                  │
       │<──── 接受 / 拒绝 ────────────────│

签名聚合：BLS 的核心创新

为什么需要签名聚合？

在分布式系统中，常见场景是多个参与者需要对各自的消息进行签名：

• 区块链共识：数千个验证者对区块进行投票
• 证书透明度：多个 CT 日志操作员确认同一证书
• 多方计算：多个参与方确认协议执行结果

聚合签名机制

假设有 $n$ 个签名者，第 $i$ 个签名者的公钥为 $pk_i$，对消息 $m_i$ 的签名为 $\sigma_i$：

聚合签名：

$$\sigma_{agg} = \sigma_1 + \sigma_2 + \cdots + \sigma_n \in G_1$$

即 $G_1$ 上的点加法。

聚合验证：

$$e(\sigma_{agg}, P_2) = \prod_{i=1}^{n} e(H(m_i), pk_i)$$

正确性：

$$e(\sigma_{agg}, P_2) = e\left(\sum_{i=1}^{n} sk_i \cdot H(m_i), P_2\right) = \prod_{i=1}^{n} e(H(m_i), sk_i \cdot P_2) = \prod_{i=1}^{n} e(H(m_i), pk_i)$$

聚合验证的复杂度分析

注意：虽然聚合验证的渐近复杂度仍是 $O(n)$（因为需要计算 $n$ 个 $e(H(m_i), pk_i)$），但实际中可以使用批量配对优化（如乘积树）将 $n+1$ 次配对优化为约 $2\log n$ 次配对。

密钥聚合

BLS 还支持公钥聚合：将多个公钥合并为单个公钥，使得聚合签名看起来像是单个签名者签名的结果。

$$pk_{agg} = pk_1 + pk_2 + \cdots + pk_n \in G_2$$

此时验证简化为：

$$e(\sigma_{agg}, P_2) = e(H(m), pk_{agg})$$

限制：密钥聚合要求所有签名者对同一消息签名。对不同消息的签名只能使用消息分别验证的聚合方式。

安全性分析

安全假设

BLS 签名的安全性基于以下计算困难假设：

计算性 Diffie-Hellman 假设（CDH）在 $G_1$ 上：

给定 $P, aP, bP \in G_1$，计算 $abP$ 是计算困难的。

更精确地说，BLS 的安全性可归约到间隙 Diffie-Hellman 问题（Gap-DHP）：

• 判定性 Diffie-Hellman（DDH）在 $G_1$ 上容易（因为可以用配对验证 $e(aP, bP) = e(P, abP)$）
• 但计算性 Diffie-Hellman（CDH）在 $G_1$ 上仍然困难

存在不可伪造性（EUF-CMA）

在随机预言模型（ROM）下，假设 CDH 在 $G_1$ 上是困难的，则 BLS 签名满足选择消息攻击下的存在不可伪造性（EUF-CMA）。

证明思路（归约到 CDH）：

• 假设存在伪造者 $\mathcal{F}$ 能以不可忽略的概率伪造 BLS 签名
• 构造模拟器 $\mathcal{S}$ 利用 $\mathcal{F}$ 解决 CDH 问题
• $\mathcal{S}$ 收到 CDH 挑战 $(P, aP, bP)$
• $\mathcal{S}$ 设置公钥 $pk = aP$（对应未知私钥 $sk = a$）
• 当 $\mathcal{F}$ 请求消息 $m_i$ 的签名时，$\mathcal{S}$ 使用 $bP$ 和编程随机预言机来生成有效签名
• 当 $\mathcal{F}$ 输出伪造签名 $(m^*, \sigma^*)$ 时，$\sigma^*$ 恰好是 $abP$，即 CDH 的解

安全注意事项

1. 子群攻击（Subgroup Attack）

在 Type 3 配对中，$G_2$ 的点必须验证其确实在素数阶子群 $E(\mathbb{F}_{q^k})[r]$ 中。未经验证的 $G_2$ 点可能导致私钥信息泄露。

2. 哈希到曲线的安全性

哈希函数 $H: \{0,1\}^* \rightarrow G_1$ 必须是随机预言机。实际部署中需要标准化的 Hash-to-Curve 方法（如 RFC 9380 定义的 SSWU 方法）。

3. Rogue 密钥攻击（Rogue Key Attack）

在密钥聚合场景中，恶意参与者可以选择自己的公钥为 $pk_i = c_i \cdot P_2$（不知道 $c_i$ 但知道 $c_i \cdot P_2$），从而控制聚合公钥。防御方法：

• 证明拥有（Proof of Possession）：要求每个签名者提供其公钥对应的私钥知识证明
• 密钥贡献协议：使用分布式密钥生成（DKG）协议，确保每个参与者无法单方面选择公钥

门限 BLS 签名

门限签名概述

$(t, n)$-门限签名将私钥 $sk$ 分成 $n$ 个份额 $sk_1, \ldots, sk_n$，任意 $t$ 个份额可以生成有效签名，但 $t-1$ 个份额无法获得任何关于私钥的信息。

BLS 门限签名利用Shamir 秘密共享的线性性质：

• 密钥分发：使用 $(t, n)$-Shamir 秘密共享将 $sk$ 分为 $n$ 个份额
• 部分签名：每个参与者 $i$ 使用 $sk_i$ 对消息 $m$ 签名：$\sigma_i = sk_i \cdot H(m)$
• 签名聚合：收集 $t$ 个部分签名，使用拉格朗日插值系数聚合：

其中 $S$ 是 $t$ 个参与者的集合，$\lambda_i$ 是拉格朗日系数。

门限 BLS 的优势

实际应用

Ethereum 2.0 信标链

Ethereum 2.0 使用 BLS12-381 曲线上的 BLS 签名作为验证者的签名方案：

• 每个验证者持有一个 BLS 密钥对
• 对区块和见证（attestation）进行 BLS 签名
• 使用签名聚合将数千个验证者的签名合并为单个签名
• 大幅减少链上存储和验证成本

单个验证者签名：48 字节
1000 个验证者聚合签名：48 字节（而非 48,000 字节）

Dfinity / Internet Computer

Dfinity 使用 BLS 签名实现其共识协议中的门限签名机制：

• 子网中的节点使用门限 BLS 生成随机信标（Randomness Beacon）
• 随机信标驱动共识协议，实现快速最终性
• 使用 BLS12-381 曲线，与 Ethereum 2.0 兼容

证书透明度（CT）日志

多个 CT 日志操作员可以使用 BLS 聚合签名来证明他们都已记录某个证书：

• 每个操作员对证书哈希进行 BLS 签名
• 聚合签名证明"至少 N 个操作员已记录此证书"
• 减少证书透明度证明的存储大小

性能特征

计算成本

在 BN254 曲线上（Intel Core i7，优化实现）：

与 ECDSA 对比

国密生态中的聚合签名

国密标准现状

目前国密标准体系（GM/T）中尚无专门的聚合签名标准。但以下标准为相关方向提供了基础：

• GM/T 0003-2012（SM2 密码算法）：定义了 SM2 数字签名算法，SM2 基于椭圆曲线，理论上可通过选择配对友好曲线实现类似 BLS 的方案
• GM/T 0009-2012（SM2 密码算法使用规范）：定义了 SM2 签名的数据格式和流程
• GM/T 0010-2012（SM2 密码算法加密消息语法规范）：定义了 SM2 的消息格式

SM2 实现 BLS 签名的可行性分析

SM2 曲线（sm2p256v1）的参数：

p = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
n = 0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123

SM2 曲线的嵌入度 $k \approx 2^{128}$（非常大），这意味着：

• 在 SM2 曲线上计算配对运算极其昂贵（扩域 $\mathbb{F}_{p^k}$ 的 $k$ 太大）
• SM2 曲线不适合直接用于 BLS 签名

• 在国密系统中引入配对友好曲线（如 BLS12-381），与 SM2/SM3/SM4 组合使用
• 使用 SM2 实现 Schnorr 签名（利用其线性性质实现聚合），但功能不如 BLS 强大
• 等待国密标准中可能的聚合签名算法标准化

参考来源

• Boneh, D., Lynn, B., Shacham, H. (2001). *Short Signatures from the Weil Pairing*. ASIACRYPT 2001. DOI:10.1007/3-540-45682-3_32
• Boneh, D., et al. (2003). *Aggregate and Verifiably Encrypted Signatures from Bilinear Maps*. EUROCRYPT 2003.
• NIST FIPS 203 (2024). *Module-Lattice-Based Key-Encapsulation Mechanism Standard*. CSRC
• Ethereum 2.0 Specification. *BLS12-381 Signature Scheme*. eth2-specs
• RFC 9380 (2023). *Hashing to Elliptic Curves*. IETF
• Dfinity. *BLS12-381 Signature Scheme*. Internet Computer Docs

相关实践

• 如需了解 Schnorr 签名在比特币 Taproot 中的应用，请参阅《Schnorr 签名算法原理：数学基础、协议设计与门限签名》
• 如需了解秘密共享与门限密码学的更多内容，请参阅《秘密共享与门限密码学：从 Shamir 方案到现代阈值签名》
• 如需了解 SM2 国密算法的签名原理，请参阅《SM2 椭圆曲线公钥密码算法》