双线性映射

  1. $G_1, G_2, G_T$ 是三个阶为素数 $p$ 的循环群
  2. 群 $G_1$ 的生成元为 $g_1$，群 $G_2$ 的生成元为 $g_2$
  3. $e$ 为双线性映射 $G_1 \times G_2 \rightarrow G_T$

  4. 双线性映射性质

    • 双线性：对任意 $a, b \in Z^*, u \in G_1, v \in G_2$，有 $e(u^a, v^b)=e(u, v)^{ab}$ 成立，即先指数运算再映射等于先映射后指数运算
    • 非退化性：$e(g_1, g_2) \ne 1$

    因此，$e(g_1, g_2)$ 是 $G_T$ 的生成元

BLS 签名

$(G_1, G_2)$ 是 co-GDH 群对，阶均为 $p$，哈希函数 $H: \left\{0,1\right\}^* \rightarrow G_1$

  • 密钥生成：随机选择私钥 $x \in Z_p$，计算公钥 $v=g_2^x \in G_2$
  • 签名：消息为 $m$，则签名为 $\sigma = H(m)^x \in G_1$
  • 验证：$e(\sigma, g_2)=e(H(m), v)$
  • 推导：$e(\sigma, g_2)=e(H(m)^x, g_2)=e(H(m), g_2)^x=e(H(m), g_2^x)=e(H(m), v)$
  • 安全性：CDH 困难，则签名不可伪造

BLS 签名仅一个随机因子，即私钥，不用于交易签名，用于区块链共识投票。

BLS 聚合签名

假设 $n$ 个用户对同一个消息 $m$ 签名，则能实现批量验证。

  1. 随机选择 $n$ 个整数 $c_1, ...c_n \in [0, B]$，$B$ 为某个固定值
  2. 计算 $V = \prod_{i=1}^nv_i^{c_i} \in G_2$，$U = \prod_{i=1}^n\sigma_i^{c_i} \in G_1$
  3. 验证 $e(U, g_2)=e(H(m), V)$

随机数 $c_1, ..., c_n$ 起随机化作用

双线性映射计算复杂度高，尽量少算

其它群运算计算复杂度低，可以多算

推导：

$e(a\cdot b, c) = e(a, c) \cdot e(b,c)$

$e(\prod_{i=1}^na_i, b)=e(a_1 \cdot a_2... \cdot a_n, b) = e(a_1, b) \cdot ... \cdot e(a_n, b) = \prod_{i=1}^n e(a_i,b)$

$e(U, g_2)=e(\prod_{i=1}^nH(m^{x_ic_i}), g_2) = \prod_{i=1}^ne(H(m), g_2)^{x_ic_i}$

$e(H(m), V)=e(H(m), \prod_{i=1}^ng_2^{x_ic_i}) = \prod_{i=1}^ne(H(m), g_2)^{x_ic_i}= \prod_{i=1}^ne(H(m), g_2)^{x_ic_i}$

示例

#[allow(dead_code)]
fn gen_bls_signature(message: &[u8], bls_keypairs: &[(SecretKey, Vec<u8>)]) -> [u8; 96] {
    let mut signatures = vec![];
    let mut pubkeys = vec![];

    // 用各自的私钥得到各自的签名
    for (privkey, _) in bls_keypairs {
        let signature = privkey.sign(message, DST.as_bytes(), &[]);
        let pubkey = privkey.sk_to_pk();
        signatures.push(signature);
        pubkeys.push(pubkey);
    }

    // 把所有的签名聚合成一个签名
    let signatures = signatures.iter().collect::<Vec<_>>();
    let signature = AggregateSignature::aggregate(signatures.as_slice(), true)
        .unwrap()
        .to_signature();

    // 把所有的公钥聚合成一个公钥，注意公钥的聚合顺序要和签名的聚合顺序保持一致
    let pubkeys = pubkeys.iter().collect::<Vec<_>>();
    let pubkey = AggregatePublicKey::aggregate(&pubkeys, false)
        .unwrap()
        .to_public_key();

    // 用聚合后的公钥对聚合后的签名验签
    let result = signature.verify(true, message, DST.as_bytes(), &[], &pubkey, false);

    assert!(
        result == blst::BLST_ERROR::BLST_SUCCESS,
        "pubkeys not match signatures"
    );

    signature.compress()
}

参考

【新火公开课】密码学基础系列课程2(下): 数字签名