【区块链】BLS数字签名算法介绍及拓展

大家好，欢迎来到IT知识分享网。

BLS数字签名原理

一、概念须知

• 曲线哈希（Hashing to the curve）
• 曲线配对（curves pairing）
• 双线性配对特性(方便理解聚合签名)
  $e(a\ast b,p)=e(b,a\ast p)$
  $e(a,b+c)=e(a,b)\ast e(a,c)$

更加具体的介绍，网上很多，此处不赘述。

二、基础应用

2.1 单个签名

1、$pk$代表私钥，$P=pk\ast G$代表公钥，$msg$代表要签名的消息
2、签名：$Sig=pk\ast H(msg)$ ，其中$H(msg)$为$msg$经过哈希运算得到的摘要信息

2.2 单个签名验证

我们可以使用公钥$P$来验证签名。
验证过程可理解为：验证 公钥 和 消息 的哈希值（曲线上的两点） 与 曲线基点$G$（也称：生成点）和 签名（曲线上的另外两个点）是否映射到同一个数。
$e(P,H(msg))=e(G,Sig)$

三、比特币中的应用

3.1 签名聚合

对于比特币来说，BLS极度优美。
一个区块中包含若干笔交易，每笔交易都有对应的签名(记为$si{g}_n$)，将每笔交易的签名进行简单聚合，可得到聚合签名$Sig$
$Sig=Si{g}_1+Si{g}_2+Si{g}_3+\dots +Si{g}_n$

3.2 聚合签名验证

聚合签名验证即为验证：
$e(G,Sig)=e(P_1,H(ms{g}_1))\ast e(P_2,H(ms{g}_2))\ast \dots \ast e(P_n,H(ms{g}_n))$
即：知晓聚合签名、签名者的公钥、和每笔交易的摘要信息，即可同时验证多比交易。

上述等式推导过程：（选择性观看）
$$\begin{gathered} e(G,Sig) \\ =e(G,Si{g}_1+Si{g}_2+Si{g}_3+\dots +Si{g}_n) \\ =e(G,p{k}_1\ast H(ms{g}_1)+p{k}_2\ast H(ms{g}_2)+\dots +p{k}_n\ast H(ms{g}_n)) \\ =e(G,p{k}_1\ast H(ms{g}_1))\ast e(G,p{k}_2\ast H(ms{g}_2))\ast ..\ast e(G,p{k}_n\ast H(ms{g}_n)) \\ =e(p{k}_1\ast G,H(ms{g}_1)\ast e(p{k}_2\ast G,H(ms{g}_2)\ast \dots \ast e(p{k}_n\ast G,H(ms{g}_n) \\ =e(P_1,H(ms{g}_1))\ast e(P_2,H(ms{g}_2))\ast \dots \ast e(P_n,H(ms{g}_n)) \end{gathered}$$

应用聚合签名技术，可大大提升区块的验证速度！！！

四、联盟链中的应用

主要考虑应用到联盟链共识机制中，收集投票信息时采用！！！
可以降低主副节点间的通信复杂度！！！敲重点！！！

4.1 (m,m)多重签名

实际场景：系统内的所有节点需要针对一个信息(记为$msg$)进行投票
其中：
i – 节点私钥：$p{k}_i$
ii – 节点公钥：$P_i=p{k}_i\ast G$

1、聚合：
（1）聚合公钥：$P=p{k}_1+p{k}_2+\dots +p{k}_n$
(ps:聚合公钥的计算方式有很多种，为了提升系统的安全系数，一般不会仅是进行加减法！！！本文方便理解，以加法为例。)
（2）聚合签名：$Sig=Si{g}_1+Si{g}_2+Si{g}_3+\dots +Si{g}_n$
2、签名验证：
即为验证：$e(G,Sig)=e(P,H(msg))$

推导：（选择性看）
$$\begin{gathered} e(G,Sig) \\ =e(G,Si{g}_1+Si{g}_2+\dots +Si{g}_n) \\ =e(G,(p{k}_1+p{k}_2+\dots +p{k}_n)\ast H(msg)) \\ =e((p{k}_1+p{k}_2+\dots +p{k}_n)\ast G,H(msg)) \\ =e(P_1+P_2+\dots +P_3,H(msg)) \\ =e(P,H(msg)) \end{gathered}$$

4.2 (m,n)多重签名(较复杂，重点)

实际场景：系统内的部分节点对一个信息进行投票。
同样：
i – 节点私钥：$p{k}_i$
ii – 节点公钥：$P_i=p{k}_i\ast G$
两个哈希函数：（注意区分）
i – 普通哈希函数 $hash(m)$，结果为 一个 数字；
ii – 曲线哈希函数 $H(x)$，结果为曲线上的点！！！

步骤

1、初始化：保证签名者之后无需通信
（1）聚合公钥：$P=a_1\ast P_1+a_2\ast P_2+\dots +a_n\ast P_n$
补充说明：关于$a_n$，$a_n$是一个数字，计算方式有多种，本文取
$a_i=hash(P_i,(P_1,P_2,\dots ,P_n))$
（2）成员密钥：
成员密钥的作用：验证 该成员 确实是 签名组 （我自己起的名字，可能不太准确）内的成员！！！
$M{K}_i=(a_1\ast p{k}_1)\ast H(P,i)+(a_2\ast p{k}_2)\ast H(P,i)+\dots +(a_n\ast p{k}_n)\ast H(P,i)$

成员密钥的验证：$e(G,M{K}_i)=e(P,H(P,i))$

推导：（选择性观看！！！）
$$\begin{gathered} e(G,M{K}_i) \\ =e(G,(a_1\ast p{k}_1)\ast H(P,i)+(a_2\ast p{k}_2)\ast H(P,i)+\dots +(a_n\ast p{k}_n)\ast H(P,i)) \\ =e(G,(a_1\ast p{k}_1+a_2\ast p{k}_2+\dots +a_n\ast p{k}_n)\ast H(P,i)) \\ =e((a_1\ast p{k}_1+a_2\ast p{k}_2+\dots +a_n\ast p{k}_n)\ast G,H(P,i)) \\ =e(a_1\ast (p{k}_1\ast G)+a_2\ast (p{k}_2\ast G)+\dots +a_n\ast (p{k}_n\ast G),H(P,i)) \\ =e(a_1\ast P_1+a_2\ast P_2+\dots +a_n\ast P_n,H(P,i)) \\ =e(P,H(P,i)) \end{gathered}$$

2、聚合签名

如果使用私钥$p{k}_1,p{k}_2,\dots ,p{k}_m$对交易进行签名，我们会生成m个签名：
$Si{g}_1=p{k}_1\ast H(P,m)+M{K}_1$
$Si{g}_2=p{k}_2\ast H(P,m)+M{K}_2$
…
$Si{g}_m=p{k}_m\ast H(P,m)+M{K}_m$

聚合签名：
$(S^{\prime },P^{\prime })=(Si{g}_1+Si{g}_2+\dots +Si{g}_m,P_1+P_2+\dots .+P_m)$

3、签名验证
(m,n)多重签名验证即为验证等式：
$e(G,S^{\prime })=e(P^{\prime },H(p,m))\ast e(P^{\prime },H(P,1)+H(P,2)+\dots +H(P,m))$

推导：（选择性看！！！）
$$\begin{gathered} e(G,S^{\prime }) \\ =e(G,Si{g}_1+Si{g}_2+\dots +Si{g}_m) \\ =e(G,p{k}_1\ast H(P,m)+p{k}_2\ast H(P,m)+\dots +p{k}_m\ast H(P,m)+M{K}_1+M{K}_2+\dots +M{K}_m) \\ =e(G,p{k}_1\ast H(P,m)+p{k}_2\ast H(P,m)+\dots +p{k}_m\ast H(P,m))\ast e(G,M{K}_1+M{K}_2+\dots +M{K}_m) \\ =e(G\ast (p{k}_1+p{k}_2+\dots +p{k}_m),H(P,m))\ast \\ e(G,(a_1\ast p{k}_1+a_2\ast p{k}_2+\dots +a_m\ast p{k}_m)\ast (H(P,1)+H(P,2)+\dots +H(P,m))) \\ =e(P^{\prime },H(P,m))\ast e(P^{\prime },H(P,1)+H(P,2)+\dots +H(P,m)) \end{gathered}$$

五、BLS的缺陷

六、JAVA简单实现

很早以前写的了，不保证能运行成功。

public class Pki<R, T> { 
    Map<ClientID,privkey> public static Map<Integer, BigInteger> privKeys = new HashMap<>();//分私钥（PKI保存） //Map<clientID,pubKey> public static Map<Integer, Element> pubKeys = new HashMap<>();//分公钥（需要公布） //Map<clientId,keyInfo> public static Map<Integer, KeyInfo> keyInfos = new HashMap<>(); //初始化 - 一旦生成，就不可变！ public static final Pairing bp = PairingFactory.getPairing("a.properties"); public static final Field G1 = bp.getG1(); public static final Field Zr = bp.getZr(); public static final Element g = G1.newRandomElement().getImmutable(); public static final int CERTAINTY = 256; public static final SecureRandom random = new SecureRandom(); //(Element)主公钥/主私钥 //(BigInteger)主私钥（Element）转换称为（BigInteger）形式，作为（secret）进行分割 private static final Element privateMaster = Zr.newRandomElement();//主私钥（私有） public static final Element publicMaster = g.duplicate().powZn(privateMaster);//主公钥（目前没有什么作用） private static final BigInteger secret = privateMaster.toBigInteger(); public static final BigInteger prime = new BigInteger(secret.bitLength() + 1, CERTAINTY, random); public static void split(final BigInteger secret, int needed, int available, BigInteger prime, Random random) { 
    /* * split(final BigInteger secret, int needed, int available, BigInteger prime, Random random) * - secret - 待分割的秘密 * - needed - 几份可拼凑成完整的 * - available - 分成几份 * - prime - 大素数 * - random - 随机数 * * 此函数执行后，会将：privKeys,pubKeys填满 * */ final BigInteger[] coeff = new BigInteger[needed]; coeff[0] = secret; for (int i = 1; i < needed; i++) { 
    BigInteger r; while (true) { 
    r = new BigInteger(prime.bitLength(), random); //r>0 && r<prime if (r.compareTo(BigInteger.ZERO) > 0 && r.compareTo(prime) < 0) { 
    break;//强制为+ } } coeff[i] = r; } for (int x = 1; x <= available; x++) { 
    BigInteger privKey = secret; for (int exp = 1; exp < needed; exp++) { 
    privKey = privKey.add(coeff[exp].multiply(BigInteger.valueOf(x).pow(exp))); } privKeys.put(x, privKey); Element pubKey = g.pow(privKey).getImmutable(); pubKeys.put(x, pubKey); KeyInfo keyInfo = new KeyInfo(pubKey, privKey); keyInfos.put(x, keyInfo); } } } 

KeyInfo

import it.unisa.dia.gas.jpbc.Element; import java.math.BigInteger; public class KeyInfo { 
    private Element publicKey; private BigInteger privKey; public KeyInfo() { 
    } public KeyInfo(Element publicKey, BigInteger privKey) { 
    this.publicKey = publicKey; this.privKey = privKey; } @Override public String toString() { 
    return "KeyInfo{" + "publicKey=" + publicKey + ", privKey=" + privKey + '}'; } public Element getPublicKey() { 
    return this.publicKey; } public void setPublicKey(Element publicKey) { 
    this.publicKey = publicKey; } public BigInteger getPrivKey() { 
    return this.privKey; } public void setPrivKey(BigInteger privKey) { 
    this.privKey = privKey; } } 

• 关于属性是否私有的设置：public ，private
  根据个人需要，自行设置即可！
  一般要做数据传输的话，privateKey会设置成private（非全网可见），publicKey设置成public（全网可见）
• 此程序存在一定的缺陷，此处列出：
  1.关于prime，没有进行处理；只是简单实现了门限签名的原理
  不添加prime，可以成功分割签名，但是做不到聚合签名验证，验证会出现不一致！实际与理想 差了一个mod prime!!! 如有需要，请自己补充！（ps：博主能力有限，想了好几天没搞出来）