您当前的位置： 首页 > 

mutourend

暂无认证

  • 3浏览

    0关注

    661博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Musig方案代码解析

mutourend 发布时间：2020-06-25 10:51:06 ，浏览量：3

1. 引言

Musig方案由Blockstream团队2018年论文《Simple Schnorr Multi-Signatures with Applications to Bitcoin》中提出。 对应的代码实现：

  • https://github.com/lovesh/signature-schemes （Rust语言，所用的amcl库有点bug，详见 issue。）
  • https://github.com/KZen-networks/multi-party-schnorr（Rust语言）
  • https://github.com/matter-labs/schnorr-musig（Rust语言）

参见博客 Simple Schnorr Multi-Signatures with Applications to Bitcoin 学习笔记。

Musig方案基本流程为：（即一群签名者对同一消息进行联合签名）

  • KeyGen：每个签名者生成公私钥对 ( x , X = g x ) (x,X=g^x) (x,X=gx)。
  • Sign：待签名消息 m m m，所有签名者公钥 L = { X 1 , ⋯   , X n } L=\{X_1,\cdots,X_n\} L={X1​,⋯,Xn​}，对于 i ∈ { 1 , ⋯   , n } i\in\{1,\cdots,n\} i∈{1,⋯,n}，签名者计算 a i = H a g g ( L , X i ) a_i=H_{agg}(L,X_i) ai​=Hagg​(L,Xi​)，然后计算aggregated public key X ~ = ∏ i = 1 n X i a i \tilde{X}=\prod_{i=1}^{n}X_i^{a_i} X~=∏i=1n​Xiai​​；选择随机数 r 1 ← Z q r_1\leftarrow \mathbb{Z}_q r1​←Zq​，计算 R 1 = G r 1 , t 1 = H c o m ( R 1 ) R_1=G^{r_1},t_1=H_{com}(R_1) R1​=Gr1​,t1​=Hcom​(R1​)，将 t 1 t_1 t1​发送给所有其它签名者；当收齐其它签名者发来的 t 2 , ⋯   , t n t_2,\cdots,t_n t2​,⋯,tn​时，将 R 1 R_1 R1​发送给所有其它签名者；当收到其它签名者发来的 R 2 , ⋯   , R n R_2,\cdots,R_n R2​,⋯,Rn​时，验证 t i = H c o m ( R i ) ) t_i=H_{com}(R_i)) ti​=Hcom​(Ri​))是否成立（for all i ∈ { 2 , ⋯   , n } i\in\{2,\cdots,n\} i∈{2,⋯,n}），若不成立则停止，否则继续计算 R = ∏ i = 1 n R i , c = H s i g ( X ~ , R , m ) , s 1 = r 1 + c a 1 x 1 m o d    p R=\prod_{i=1}^{n}R_i,c=H_{sig}(\tilde{X},R,m),s_1=r_1+ca_1x_1\mod p R=∏i=1n​Ri​,c=Hsig​(X~,R,m),s1​=r1​+ca1​x1​modp，将 s 1 s_1 s1​发送给其它所有签名者；当收到了所有的签名信息 s 2 , ⋯   , s n s_2,\cdots,s_n s2​,⋯,sn​时，计算 s = ∑ i = 1 n s i m o d    p s=\sum_{i=1}^{n}s_i\mod p s=∑i=1n​si​modp，最终的签名信息为 σ = ( R , s ) \sigma=(R,s) σ=(R,s)。【各签名者之间需要交互interactive。】
  • Ver：Given L = { X 1 , ⋯   , X n } , m , σ = ( R , s ) L=\{X_1,\cdots,X_n\},m,\sigma=(R,s) L={X1​,⋯,Xn​},m,σ=(R,s)，验签者计算 a i = H a g g ( L , X i ) , X ~ = ∏ i = 1 n X i a i ， c = H s i g ( X ~ , R , m ) a_i=H_{agg}(L,X_i),\tilde{X}=\prod_{i=1}^{n}X_i^{a_i}，c=H_{sig}(\tilde{X},R,m) ai​=Hagg​(L,Xi​),X~=∏i=1n​Xiai​​，c=Hsig​(X~,R,m)，验证 g s = R ∏ i = 1 n X i a i c = R X ~ c g^s=R\prod_{i=1}^{n}X_i^{a_ic}=R\tilde{X}^c gs=R∏i=1n​Xiai​c​=RX~c是否成立，若成立则签名验证成功。
2. lovesh/signature-schemes

https://github.com/lovesh/signature-schemes/musig中为Musig方案的代码实现。

2.1 主要库依赖

看https://github.com/lovesh/signature-schemes/musig/Cargo.toml中内容：

  • https://github.com/lovesh/amcl_rust_wrapper：主要做了基础运算的constant time 和variable time function封装。支持的曲线主要有"bls381", “bn254”, “secp256k1”, “ed25519”。（具体可参见博客 Polynomial Commitments代码实现【2】——lovesh/kzg-poly-commit 第1节内容。）
[dependencies.amcl_wrapper]
git = "https://github.com/lovesh/amcl_rust_wrapper"
rev = "4ea40f758e9d676937ea3e609d63b37fe9e1df7f"
features = ["secp256k1"]
  • rand：随机数生成器，Musig方案中的随机数要求为strong random number。
  • lazy_static：lazy_static是在第一次调用时（运行时）进行初始化。而非编译时，而static是在编译时进行初始化，运行阶段分配内存空间。（实际未使用，可去除。）
  • log：提供日志接口。（实际未使用，可去除。）
2.2 代码实现
  • KeyGen：
let keypair = Keypair::new(None);
    OR
let rng = EntropyRng::new();
let keypair = Keypair::new(Some(rng));

let my_sk = keypair.sig_key;
let my_vk = keypair.ver_key;
  • Sign：签名过程主要分为3个interactive阶段。 – 1）第一阶段：每个签名者选择随机数 r i ← Z q r_i\leftarrow \mathbb{Z}_q ri​←Zq​，计算相应的commitment R i = G r i , t i = H c o m ( R i ) R_i=G^{r_i},t_i=H_{com}(R_i) Ri​=Gri​,ti​=Hcom​(Ri​)，将 t i t_i ti​发送给所有其它签名者。必须保证收齐了所有其它人的 t i t_i ti​值（可调用is_phase_1_complete来判断），才进入第二阶段。
let signer = Signer::new(num_cosigners);     // num_cosigners is the total number of signers including the current signer
signer.init_phase_1();

	/// Signer creates his r, R and t
    pub fn init_phase_1(&mut self) {
        let r = FieldElement::random();
        let R = G1::generator() * r;
        // TODO: Need domain separation for H_com
        let t = FieldElement::from_msg_hash(&R.to_bytes());
        self.r = r;
        self.R[0] = R;
        self.t[0] = t;
    }

Each signer gives a numeric reference starting from 1 to other signers. These references are local to the signer. 每个签名者的编号都是本地的，本人的编号总是从0开始。 On receiving hash h from signer referred by j, it calls got_hash.

/// `t`, `R` are local (to the current signer) references to the cosigners.
/// The current signer always references himself by index 0.
pub struct Signer {
    pub r: FieldElement,
    pub R: Vec,
    pub t: Vec,
}

			// Do phase 1. Each cosigner generates r, t, R and shares t with others.
            let ts: Vec = (0..num_cosigners)
                .map(|i| signers[i].t[0].clone())
                .collect();
            for i in 0..num_cosigners {
                let signer = &mut signers[i];
                let mut k = 1;
                for j in 0..num_cosigners {
                    if i == j {
                        continue;
                    }
                    signer.got_hash(ts[j], k).unwrap();
                    k += 1;
                }
            }
            for i in 0..num_cosigners {
                assert!(signers[i].is_phase_1_complete());
            }

	/// Process the received `t` from other cosigners
    pub fn got_hash(&mut self, t: FieldElement, cosigner_ref: usize) -> Result {
        self.validate_cosigner_ref(cosigner_ref)?;
        self.t[cosigner_ref] = t;
        Ok(())
    }

	fn validate_cosigner_ref(&self, cosigner_ref: usize) -> Result {
        if cosigner_ref == 0 {
            // Since 0 always references the current signer
            return Err(MuSigError::IncorrectCosignerRef(cosigner_ref));
        }
        // Does not matter if `self.R.len` is used or `self.t.len` as they have same length
        if cosigner_ref >= self.t.len() {
            return Err(MuSigError::UnknownCosignerRef(cosigner_ref));
        }
        Ok(())
    }

– 2）第二阶段：收齐了所有的commitment hash值 t i t_i ti​后，签名者会将相应的commitment R i R_i Ri​发送给所有其它签名者。当签名者收齐（调用got_commitment，用于验证 t i = H c o m ( R i ) t_i=H_{com}(R_i) ti​=Hcom​(Ri​)是否成立。）了所有其他人的 R i R_i Ri​值之后（可调用is_phase_2_complete来判断），才进入第三阶段。

			// Do phase 2. Each cosigner shares R with others
            let Rs: Vec = (0..num_cosigners)
                .map(|i| signers[i].R[0].clone())
                .collect();
            for i in 0..num_cosigners {
                let signer = &mut signers[i];
                let mut k = 1;
                for j in 0..num_cosigners {
                    if i == j {
                        continue;
                    }
                    signer.got_commitment(Rs[j], k).unwrap();
                    k += 1;
                }
            }
            for i in 0..num_cosigners {
                assert!(signers[i].is_phase_2_complete());
            }

–3）第三阶段：当收齐了所有其他签名者的commitment R i R_i Ri​后，各个签名者分别用自己的私钥对同一消息进行签名。

	 let mut signatures: Vec = vec![];
            let msg_b = msg.as_bytes();
            for i in 0..num_cosigners {
                let signer = &signers[i];
                let keypair = &keypairs[i];
                let sig = signer
                    .generate_sig(msg_b, &keypair.sig_key, &keypair.ver_key, &verkeys)
                    .unwrap();
                signatures.push(sig);
            }

收集所有签名者的签名信息，进行aggregate：

			let aggr_sig = AggregatedSignature::new(&signatures).unwrap();
            assert!(aggr_sig.verify(msg_b, &verkeys));

Musig方案支持Key aggregation：

			let verkeys = keypairs.iter().map(|k| k.ver_key.clone()).collect();
            let L = HashedVerKeys::new(&verkeys);
            let mut avk = AggregatedVerKey::new(&verkeys);

当需要同一签名群体对不同的消息多次签名时，可采用aggregated key avk来进行签名和验签操作，减少重复计算量。

			 let verkeys = keypairs.iter().map(|k| k.ver_key.clone()).collect();
            let L = HashedVerKeys::new(&verkeys);
            let mut avk = AggregatedVerKey::new(&verkeys); //aggregated key

            let mut signatures: Vec = vec![];
            let R = Signer::compute_aggregated_nonce(&signers[0].R);
            for i in 0..num_cosigners {
                let keypair = &keypairs[i];
                let a = L.hash_with_verkey(&keypair.ver_key);
                let sig = Signer::generate_sig_using_aggregated_objs(
                    msg_b,
                    &keypair.sig_key,
                    &signers[i].r,
                    &keypair.ver_key,
                    R,
                    &a,
                    &avk, //aggregated key
                );
                signatures.push(sig);
            }
            let aggr_sig = AggregatedSignature::new(&signatures).unwrap();
            assert!(aggr_sig.verify_using_aggregated_verkey(msg_b, &avk)); //aggregated key
  • Ver：验签。
assert!(aggr_sig.verify(msg_b, &verkeys));

OR

assert!(aggr_sig.verify_using_aggregated_verkey(msg_b, &avk)); //aggregated key
3. KZen-networks/multi-party-schnorr

https://github.com/KZen-networks/multi-party-schnorr/tree/master/src/protocols/aggsig 为Musig方案和Boneh等人2018年论文《Compact Multi-Signatures for Smaller Blockchains》第5章内容的联合实现。 Aggragated Signatures: {n,n} scheme based on simple_schnorr_multi_signatures_with_applications_to_bitcoin and the scheme for discrete-logs (section 5) from compact_multi_signatures_for_smaller_blockchains。【早期的Musig方案有缺陷，最新的两者其实是一致的。】 在这里插入图片描述

3.1 主要库依赖
  • serde：A generic serialization/deserialization framework。
  • serde_derive：Macros 1.1 implementation of #[derive(Serialize, Deserialize)]。
  • hex：Encoding and decoding data into/from hexadecimal representation.
  • https://github.com/KZen-networks/curv：提供了support for some useful operations/primitives such as verifiable secret sharing, commitment schemes, zero knowledge proofs, and simple two party protocols such as ECDH and coin flip。主要支持的曲线有Secp256k1、Ed25519、Jubjub、Ristretto和BLS12-381。
curv = { git = "https://github.com/KZen-networks/curv" , tag = "v0.2.4", features =  ["ec_secp256k1","merkle"]}
  • https://github.com/KZen-networks/centipede：A scheme for instantiating KMS’s with recovery。
3.2 代码实现
  • KeyGen：
pub struct KeyPair {
    pub public_key: GE,
    private_key: FE,
}
 		// round 0: generate signing keys
        let party1_key = KeyPair::create();
        let party2_key = KeyPair::create();
OR

	let private_key_raw = "B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF";
	let party1_key = KeyPair::create_from_private_key(
            &BigInt::from_str_radix(&private_key_raw, 16).unwrap(),
        );
  • Sign：签名过程主要分为3个interactive阶段。
		// round 1: send commitments to ephemeral public keys
        let party1_ephemeral_key = EphemeralKey::create();
        let party2_ephemeral_key = EphemeralKey::create();
        let party1_commitment = &party1_ephemeral_key.commitment;
        let party2_commitment = &party2_ephemeral_key.commitment;

		/ round 2: send ephemeral public keys and check commitments
        // p1 release R1' and p2 test com(R1') = com(R1):
        assert!(EphemeralKey::test_com(
            &party2_ephemeral_key.keypair.public_key,
            &party2_ephemeral_key.blind_factor,
            party2_commitment
        ));
        // p2 release R2' and p1 test com(R2') = com(R2):
        assert!(EphemeralKey::test_com(
            &party1_ephemeral_key.keypair.public_key,
            &party1_ephemeral_key.blind_factor,
            party1_commitment
        ));

		//round 3：签名
		// compute apk:
        let mut pks: Vec = Vec::new();
        pks.push(party1_key.public_key.clone());
        pks.push(party2_key.public_key.clone());
        let party1_key_agg = KeyAgg::key_aggregation_n(&pks, 0);
        let party2_key_agg = KeyAgg::key_aggregation_n(&pks, 1);
        assert_eq!(party1_key_agg.apk, party2_key_agg.apk);

        // compute R' = R1+R2:
        let party1_r_tag = EphemeralKey::add_ephemeral_pub_keys(
            &party1_ephemeral_key.keypair.public_key,
            &party2_ephemeral_key.keypair.public_key,
        );

        let party2_r_tag = EphemeralKey::add_ephemeral_pub_keys(
            &party1_ephemeral_key.keypair.public_key,
            &party2_ephemeral_key.keypair.public_key,
        );

        assert_eq!(party1_r_tag, party2_r_tag);

        // compute c = H0(Rtag || apk || message)
        let party1_h_0 =
            EphemeralKey::hash_0(&party1_r_tag, &party1_key_agg.apk, &message, is_musig);
        let party2_h_0 =
            EphemeralKey::hash_0(&party2_r_tag, &party2_key_agg.apk, &message, is_musig);
        assert_eq!(party1_h_0, party2_h_0);

        // compute partial signature s_i and send to the other party:
        let s1 = EphemeralKey::sign(
            &party1_ephemeral_key,
            &party1_h_0,
            &party1_key,
            &party1_key_agg.hash,
        );
        let s2 = EphemeralKey::sign(
            &party2_ephemeral_key,
            &party2_h_0,
            &party2_key,
            &party2_key_agg.hash,
        );

        let r = party1_ephemeral_key.keypair.public_key.x_coor().unwrap();

        assert!(verify_partial(
            &ECScalar::from(&s1),
            &r,
            &ECScalar::from(&party1_h_0),
            &ECScalar::from(&party1_key_agg.hash),
            &party1_key.public_key
        )
        .is_ok());

        // signature s:
        let (r, s) = EphemeralKey::add_signature_parts(s1, &s2, &party1_r_tag);
  • Ver：
 assert!(verify(&s, &r, &party1_key_agg.apk, &message, is_musig,).is_ok())

参考资料： [1] https://github.com/lovesh/signature-schemes [2] https://github.com/KZen-networks/multi-party-schnorr [3] 博客 rust crate: lazy_static

关注
打赏
1664532908
查看更多评论

最近更新

热门博客

[ 申请 ]友情链接：

ClashX教程 绘画宝宝 配音宝宝
立即登录/注册

微信扫码登录

0.0457s