互联网计算机漫游指南

双线性映射

双线性映射是一个非常重要的密码学原语，通常表示为 \(e\) ：\(G_{1} * G_{2} -> G_{T}\) 。其中 \(G_{1}\) ，\(G_{2}\) 和 \(G_{T}\) 都是具有相同阶的循环群。

定义：一个双线性映射是由两个向量空间上的元素，生成第三个向量空间上一个元素之函数，并且该函数对每个参数都是线性的。

双线性映射 \(e\) 需要满足以下两个条件：

1. 双线性

对任意的 \(g_{1}∈G1\) ，\(g_{2}∈G2\) 和 \(a,b∈Z\) ，有： $$ e(g_{1}^{a}, g_{2}^{b}) = e(g_{1}, g_{2})^{ab} $$

2. 非退化

存在 \(g_{1}∈G1\) 和 \(g_{2}∈G2\) ，使得： $$ e(g_{1},g_{2})≠1_{G_{T}} $$ \(e\) 需要是关于每个变量的同态映射，且不能把所有元素都映射成 1 。

若有 A ，B ，C 三个向量空间，映射 e ： A × B → C 是一个双线性映射，则 A 固定，B 可变时，B 到 C 的映射是线性的。B 固定，A 可变时，A 到 C 的映射也是线性的。也就是说保持双线性映射中的任意一个参数固定，另一个参数对 C 的映射都是线性的。

即双线性的函数有两个输入，而且对这两个输入分别满足线性。

例如矩阵乘法，数据库两张表的笛卡尔积都是双线性配对的例子。

矩阵乘法满足：

(A+B)C = AC + BC （对 C 线性）

A(B+C) = AB + AC （对 A 线性）

两张表的笛卡尔积也满足类似的性质。

双线性映射是一个非常强大的工具，使得许多基于硬问题的公钥密码方案成为可能。比如 BLS 签名就是建立在双线性 Diffie-Hellman 问题的难度之上的。

双线性映射通常由 pairing 函数实现。目前常用的 pairing 函数包括 Tate pairing 、Weil pairing 等。这些 pairing 函数可以由特定的椭圆曲线来构造。

双线性映射让我们能在群之间轻松转换，并利用群之间关系来设计各种密码方案。它是许多密码学协议的关键基础，也是现代密码学发展的重要成果之一。

BLS签名

BLS 签名是一种基于双线性对称加密的数字签名方案。

它的密码学原理如下：

选择一个双线性对 \((G_{1},G_{2})\) ，其中 \(G_{T}\) , \(G_{1}\) 和 \(G_{2}\) 都是循环群，阶为一个大素数 \(q\) 。\(P\) 是 \(G_{1}\) 的生成元。

KeyGen 生成密钥：

选择一个随机的私钥 \(sk\) ，计算公钥 \(pk=sk*P\)​ 。

Sign 签名：

消息 \(m\) 先进行哈希运算，得到 \(H(m)\) 。

对 \(H(m)\) 进行签名，计算签名 \(σ = sk * H(m)\)。

Verify 验证：

验证签名 \(σ\) ，计算 \(e(P, σ) = e(pk, H(m))\) 。其中 \(e\) 是一个双线性映射，如果等式成立，则签名有效。

为什么可以这样验证？

这就用到了上面略过的曲线配对函数，简介如下：

有一个（或一种）特殊的函数记为 \(e\) ，它可以接受输入一条（或两条不同）曲线上两点 \(P\) 和 \(Q\) ，输出至一个数字，如下式： $$ e(P, Q) → n $$ 之所以说这个函数特殊，是因为它有一些特殊性质。例如我们有一个数 \(x\) 和两点 \(P\) 和 \(Q\) ，无论哪一个点乘以这个数字，函数结果相同即： $$ e(x * P, Q) = e(P, x * Q) $$ 更进一步： $$ e(a * P, b * Q) = e(P, ab * Q) = e(ab * P, Q) = e(P, Q)^{ab} $$ 当然还有其他性质，但是对于我们用来验证签名，主要用到以上性质。

BLS 签名的安全性建立在双线性对计算困难问题（bilinear Diffie-Hellman problem）的基础之上。它只需要两次群运算就可以完成签名和验证，效率很高。同时它还具有短签名、随机签名等优点。

BLS 支持简单的签名聚合：几个 BLS 签名可以通过群运算聚合成一个短签名。验证时对聚合签名做配对检验。

有了单个签名，我们再来看下聚合签名。

BLS阈值签名

区块链系统中，签名验证是一个非常重要也比较频繁的运算。为了确保安全，每个交易输入通常都需要一个签名来进行验证。但对于多方合作的场景，比如多签地址，这会导致交易大小急剧增长，并降低处理效率。

为了解决这个问题，研究人员提出了 BLS 阈值签名方案。BLS 签名是一种非常高效的数字签名方式，它基于双线性配对原理，只需要很短的签名即可确保安全。而 BLS 阈值签名方案在此基础上，可以将多个 BLS 签名聚合成一个，从而大大缩减存储和传输成本。

BLS 阈值签名如何工作呢？先简单回顾一下 BLS 签名本身的原理。它需要以下参数：一个双线性配对函数,两个循环群 G1 和 G0 ，G1 的生成元 P ，以及一个散列函数 H 。密钥生成是随机选择一个数字 sk ，计算公钥 pk=sk*P 。签名是对消息计算散列 H(m) ，然后计算签名 σ = sk * H(m) 。验证就是检验配对关系 e(P, σ) = e(pk, H(m)) 是否成立。

这个验证方程也解释了为什么可以进行签名聚合。如果有 n 个签名都是对同一消息 m 的签名，那么将所有签名乘起来，验证方程依然成立。因此验证方只需要提供一个聚合后的短签名，就可以同时验证 n 个签名，效率大大提升。

多个 BLS 签名可以简单地将签名值相乘得到聚合签名。也就是对于 \((pk_{1},m_{1},σ_{1}),\ ...\ ,(pk_{n},m_{n},σ_{n})\) ，计算：

$$ σ = σ_{1} * ... * σ_{n} $$ 验证聚合签名 σ 时，对每个签名分别检查签名验证等式。

当签名的消息 m 都相同时，验证可以更加简化，只需要： $$ e(g_{1}, σ) = e(pk_{1} * ... * pk_{n}, H(m)) $$ 这样只需要 2 个配对运算。这就是 BLS 签名聚合的优势所在。

但是直接聚合签名是不安全的，会存在 “ 恶意公钥 ” 攻击的风险。为了解决这个问题，BLS 阈值签名加入了一个新散列函数 H1 。这个散列函数输入是所有参与签名用户的公钥，输出是每个用户一个 “ 权重 ” 。在生成聚合签名时，每个用户的签名都要以其权重作为指数幂，才能计算出安全的聚合签名。关键思路是对每个公钥引入一个随机指数，这些指数由所有公钥的散列值决定。

验证时也是类似，重新计算出每个用户的权重，将公钥按权重聚合，与普通 BLS 签名验证流程一致。因此验证多个签名与单签效率是相同的。这种机制可以有效防止恶意公钥攻击，每个用户签名的贡献是精确控制的。

1. 生成密钥对 \((sk, pk=g1^sk)\) 。
2. 对消息 \(m\) 签名，输出 \(σ = H(m)^sk\) 。
3. 聚合时，对所有公钥计算指数 \((t_{1},...,t_{n}) = H1(pk_{1},...,pk_{n})\) 。
4. 计算聚合签名 \(σ = σ_{1}^{t_{1}} * ... * σ_{n}^{t_{n}}\) 。
5. 验证时，计算 \((t_{1},...,t_{n}) = H1(pk_{1},...,pk_{n})\) ，并计算聚合公钥 \(apk = pk_{1}^{t_{1}} * ... * pk_{n}^{t_{n}}\) 。
6. 检查 \(e(g_{1}, σ) = e(apk, H(m))\) ，等式成立即验证成功。

这个方案能防止公钥替换攻击，理论上也是安全的，基于 co-CDH 问题的难度假设。该方案保留了 BLS 签名聚合的优势，同时也不需要证明私钥知识。因此这是 BLS 阈值签名一个很好的改进方案。

BLS 阈值签名机制非常适合区块链系统。它不仅可以缩小交易大小，节省存储空间，还兼容交易批量验证，可以进一步提升处理性能。BLS 阈值签名可以非交互式聚合，更具有灵活性。未来如果搭配聚合公钥证明 (POP) 使用，可以完全隐藏用户的公钥信息。

随着区块链进入大规模商用的新阶段，各种效率和隐私技术会越来越重要。BLS 阈值签名为我们提供了一个非常实用的工具。

BLS 签名算法主要需要进行曲线配对和签名聚合两项工作。

曲线配对需要一个特殊的函数把曲线上的两个映射为一个数，需要满足的属性是无论哪个点乘以未知数x，结果必须相同。这种函数是存在的，并且不会暴露 x 的任何相关信息（安全性）。

在验签时，只需验证公钥和消息的哈希值（曲线上两个点）与曲线生成点和签名（曲线上另两个点）是否映射到同一个数，如果是就说明这是一个有效的 BLS 签名。

当然，BLS 签名也不是完美无缺的，它的复杂度要比 ECDSA 高上一个数量级。在验证区块中 1000 笔交易的聚合签名时，仍需要进行 1000 次配对计算，这可能比使用 ECDSA 时对 1000 个单独签名进行验证还要慢。唯一的好处在于，可以在区块中放更多笔的交易，毕竟聚合签名只占 32 字节。另外还有一种针对椭圆曲线加密体系的 MOV 攻击，利用配对函数来危害系统安全。

对 ECDSA 、Schnorr 和 BLS 签名算法的资料整理如下表：

[1] Schnorr 签名算法可以把一笔交易中的所有签名和公钥合并成单个签名和公钥，而且无从追溯是否合并过，一次性对合并后的签名验证，加快区块验证速度。