Skip to content
This repository has been archived by the owner on Dec 28, 2023. It is now read-only.

Schnorr Signatures (Aggregate Signatures)

Jump to bottom
Gary Yu edited this page Dec 5, 2018 · 29 revisions

Schnorr Signatures, a.k.a. Aggregate Signatures, or MuSig, is proposed by Gregory Maxwell,Andrew Poelstra,Yannick Seurin, and Peter Wuille. Yes, three of them are the main contributors of the underlying optimized C library for EC(Elliptic Curve): secp256k1. This rust-secp256k1-zkp lib is a Rust wrapper around secp256k1.

Their paper Simple Schnorr Multi-Signatures with Applications to Bitcoin was published on Jan 15, 2018 for first edition.

The Schnorr's original paper was published in 1990. And it was covered by Schnorr's U.S. Patent 4,995,082 but already expired in February 2008.

And please note that there're multiple "standard" as well. The Schnorr Signatures implementation in secp256k1 could be different from others.

Schnorr Signatures would help to improve Bitcoin:

  • On-chain transaction size is reduced
  • Faster validation for each transaction
  • Improved privacy for participants of a Multi-Signature wallet

A BIP is proposed by Pieter Wuille at Jul 6 2018.

A Quick Recap on ECDSA

A quick recap on ECDSA(Elliptic Curve Digital Signature Algorithm) which is used on current Bitcoin implementation, and widely used everywhere since Bitcoin.

To sign a message m:

  1. Signer select a random integer k, 1≤k≤n-1. Note: n is the order of G, n*G=O(point at infinity), and G is the base point of an EC.
  2. k*G = (x,y), get this EC point's X-Coordinate x.
  3. r = x mod n, if r=0, repeat step 1.
  4. k^(-1) mod n, where k^(-1) satisfies k^(-1) * k mod n = 1.
  5. e = SHA-1(m), get SHA-1 hash of message m.
  6. s = k^(-1) * (e + p*r) mod n, where p is signer's private key. If s=0, repeat step 1.
  7. Done. The signature is (r,s).

One sentence as a brief of above procedure: select a random EC point R=k*G and get its x coordinate as r, and calculate {hash(m)+p*r}/k as s.

Then anyone can verify this signature with signer's public key P = p*G, by checking EC point {hash(m)/s}*G + (r/s)*P has x coordinate equal to r.

Schnorr Signature

Let's take a look at Schnorr Signature. (the version of the Dr Maxwell's paper) And there's a good simple introduction here.

To sign a message m:

  1. Select a random EC point R=k*G.
  2. Calculate e = hash(R,P,m), where P=p*G is signer's public key.
  3. Calculate k + e*p as s, where p is signer's private key.
  4. Done. The signature is (R,s).

Then anyone can verify this signature (R,s) with signer's public key P=p*G:

  1. Calculate e = hash(R,P,m).
  2. s*G = R + hash(R,P,m)*P
  3. Verify if above equation is true. Done.

secp256k1 version:

To save space, the secp256k1 lib take the signature format as (r,s) instead of (R,s), where r is the x-coordinate of EC point R. (r,s) is 64 bytes which is then same as ECDSA signature.

To verify this signature (r,s) with signer's public key P=p*G:

  1. Calculate e = hash(R,P,m).
  2. Calculate R' = s*G - e*P
  3. Verify R'.x = r. Done. Where R'.x is the x-coordinate of EC point R'.

TODO: secp256k1 has an additional step, to check whether public nonce R y coordinate is a quadratic residue, I can't find the document to explain what this step's exactly doing, and for what?

Compare to ECDSA, Schnorr Signature is much simple and less calculation. In ECDSA, the signature verification calculation need one inversion 1/s and two multiplications on EC points, and these are very complex computation.

An exciting thing in Schnorr Signature: the equation s*G = R + hash(P,R,m)*P is linear! That means, for multiple signatures, we can add or subtract each other but still stay valid! This bring some very good features.

Signature Aggregation (Batch Verification)

The 1st nice feature it will bring is batch verification: for 1000 signatures, we don't need calculate 2000 multiplications on EC points, just 2 points multiplications and 1000 points addition plus 2000 arithmetic addition, since sum(s)*G = sum(R) + sum{hash(R,P,m)}*P. Batch verification save a lot of computation.

We still need to know all the public keys (each R and each P), but at least all the signatures in the block can take only ONE sum(s) (32 bytes).

Key Aggregation

We can use a pair of private keys (p1,p2) and generate a shared signature:

To sign a message m:

  1. Select two random EC points R1=k1*G and R2=k2*G, get R=R1+R2.
  2. Calculate P=P1+P2, where p1 is 1st private key, P1=p1*G is 1st public key; p2 and P2 for 2nd.
  3. Calculate k1 + hash(R,P,m)*p1 as s1, calculate k2 + hash(R,P,m)*p2 as s2. And s=s1+s2.
  4. Done. The signature is (R,s) = (R1+R2,s1+s2), for shared public key P=P1+P2.

Then anyone can verify this signature with the shared public key P=P1+P2:

  1. s*G = R + hash(R,P,m)*P.
  2. Done.

Because

   s*G 
 = s1*G                        +   s2*G
 = k1*G + {hash(R,P,m)}*p1*G   +   k2*G + {hash(R,P,m)}*p2*G
 = R1+{hash(R,P,m)}*P1         +   R2+{hash(R,P,m)}*P2
 = (R1+R2) + {hash(R,P,m)}*(P1+P2)
 = R + {hash(R,P,m)}*P

This aggregation has an obvious constraint: when each party sign, the hash(R,P,m) must be same, that means, all participants must share with each other about their public key Pi, i=1..N (suppose we have N parties), and their chosen Ri, i=1..N.

Interesting Demos

Now, let's do some interesting demos on these.

First Demo: What the Schnorr Signature look like?

Source Code (Click to expand) 

    #[test]
    fn demo_aggsig_single() {
        let secp = Secp256k1::with_caps(ContextFlag::Full);
        let (sk, pk) = secp.generate_keypair(&mut thread_rng()).unwrap();

        println!("public key (P):\t\t{:?}\nprivate key (p):\t{:?}", pk, sk);

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();
        let sig = sign_single(&secp, &msg, &sk, None, None, None).unwrap();
        println!("msg:\t\t\t{:?}", msg);
        println!("\nschnorr sig:\t\t{:?}", sig);

        let result = verify_single(&secp, &sig, &msg, None, &pk, false);
        if true == result {
            println!("signature check:\tOK");
        }else{
            println!("signature check:\tNOK");
        }
    }
Running result: 
$ cargo test --release  demo_aggsig_single -- --nocapture

running 1 test
public key (P):		PublicKey(ef81860b9d8a5c92036e58aab53c42dac56c88034e0d1f646a922ced02156f36825fc3311ad0f676518c426ea8cb88cfc8b990a24f66fde25ad9335fda538ff5)
private key (p):	SecretKey(113d2f084e35f1a11532ff7d29c74704af534337c98f30aa378c5c30a542ed57)
msg:			Message(39ebdbcea928f5fc0d632bc48270963315aacbf1f0acb06f5b1d014e65ca8946)

schnorr sig:		Signature(a74492ca64af15db38523b7a088640bbc26164eaa4f86c0088be72fff389cb8cd82319cedca3754d9a2600478944dfde9315a28efd5a53747b6d5404db807ceb)
signature check:	OK

Second Demo: Efficient Computation

Let's have a compare between ECDSA and Schnorr Signature.

Source Code (Click to expand) 

    #[test]
    fn bench_ecdsa_sign_efficiency() {
        let secp = Secp256k1::with_caps(ContextFlag::Commit);

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        let mut secret = SecretKey([0; 32]);
        thread_rng().fill_bytes(&mut secret.0);

        let now = SystemTime::now();

        for _ in 1..LENGTH+1 {
            secp.sign(&msg, &secret).unwrap();
        }

        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} signing)", used_time, LENGTH);
        }
    }

    #[test]
    fn bench_ecdsa_check_efficiency() {
        let secp = Secp256k1::with_caps(ContextFlag::Commit);

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        let mut secret = SecretKey([0; 32]);
        thread_rng().fill_bytes(&mut secret.0);
        let pubkey = PublicKey::from_secret_key(&secp, &secret).unwrap();

        let sig = secp.sign(&msg, &secret).unwrap();

        let now = SystemTime::now();

        let mut ok_count = 0;
        for _ in 1..LENGTH+1 {
            if let Ok(_) = secp.verify(&msg, &sig, &pubkey){
                ok_count += 1;
            }
        }
        println!("ecdsa check ok:\t{}/{}", ok_count, LENGTH);
        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} verify)", used_time, LENGTH);
        }
    }

    #[test]
    fn bench_aggsig_sign_efficiency() {
        let secp = Secp256k1::with_caps(ContextFlag::Full);
        let (sk, _pk) = secp.generate_keypair(&mut thread_rng()).unwrap();

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        let now = SystemTime::now();

        for _ in 1..LENGTH+1 {
            sign_single(&secp, &msg, &sk, None, None, None).unwrap();
        }

        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} signing)", used_time, LENGTH);
        }
    }

    #[test]
    fn bench_aggsig_check_efficiency() {
        let secp = Secp256k1::with_caps(ContextFlag::Full);
        let (sk, pk) = secp.generate_keypair(&mut thread_rng()).unwrap();

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        let sig=sign_single(&secp, &msg, &sk, None, None, None).unwrap();

        let now = SystemTime::now();

        let mut ok_count = 0;
        for _ in 1..LENGTH+1 {
            if true == verify_single(&secp, &sig, &msg, None, &pk, false){
                ok_count += 1;
            }
        }
        println!("aggsig check ok:\t{}/{}", ok_count, LENGTH);
        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} verify)", used_time, LENGTH);
        }
    }

    #[test]
    fn bench_aggsig_check_with_pubnonce_efficiency() {
        let secp = Secp256k1::with_caps(ContextFlag::Full);
        let (sk, pk) = secp.generate_keypair(&mut thread_rng()).unwrap();

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        let secnonce = export_secnonce_single(&secp).unwrap();
        let pubnonce = PublicKey::from_secret_key(&secp, &secnonce).unwrap();

        let sig=sign_single(&secp, &msg, &sk, Some(&secnonce), Some(&pubnonce), Some(&pubnonce)).unwrap();

        let now = SystemTime::now();

        let mut ok_count = 0;
        for _ in 1..LENGTH+1 {
            if true == verify_single(&secp, &sig, &msg, Some(&pubnonce), &pk, false){
                ok_count += 1;
            }
        }
        println!("aggsig check ok:\t{}/{}", ok_count, LENGTH);
        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} verify with pubnonce)", used_time, LENGTH);
        }
    }
Running result: 
$ cargo test --release  bench_ecdsa -- --nocapture

running 2 tests
spent time:	14(s)/(100000 signing)
ecdsa check ok:	100000/100000
spent time:	17(s)/(100000 verify)


$ cargo test --release  bench_aggsig -- --nocapture

running 3 tests
spent time:	12(s)/(100000 signing)
aggsig check ok:	100000/100000
spent time:	16(s)/(100000 verify)
aggsig check ok:	100000/100000
spent time:	13(s)/(100000 verify with pubnonce)

As we can see, the Schnorr Signature is little bit faster than ECDSA, for single signature and verification.

Third Demo: Key Aggregation

Let's have a demo for 3 Keys.

Source Code (Click to expand) 

    #[test]
    fn demo_aggsig_multi() {

        let numkeys = 3;
        let secp = Secp256k1::with_caps(ContextFlag::Full);

        let mut keypairs:Vec<(SecretKey, PublicKey)> = vec![];
        for _ in 0..numkeys {
            keypairs.push(secp.generate_keypair(&mut thread_rng()).unwrap());
        }

        let pks:Vec<PublicKey> = keypairs.clone().into_iter()
            .map(|(_,p)| p)
            .collect();

        println!("aggsig context with {} pubkeys: {:#?}", pks.len(), pks);

        let aggsig = AggSigContext::new(&secp, &pks);

        println!("Generating nonces for each index");
        for i in 0..numkeys {
            let retval=aggsig.generate_nonce(i);
            println!("{} returned {}", i, retval);
        }

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        let mut partial_sigs:Vec<AggSigPartialSignature> = vec![];
        for i in 0..numkeys {
            println!("\nPartial sign:\n\tmessage:\t{:?} at index {}\n\tPubkey:\t\t{:?}", msg, i, keypairs[i].1);

            let result = aggsig.partial_sign(msg,keypairs[i].0,i);
            match result {
                Ok(ps) => {
                    println!("\tPartial sig:\t{:?}", ps);
                    partial_sigs.push(ps);
                },
                Err(e) => panic!("Partial sig failed: {}", e),
            }
        }

        let result = aggsig.combine_signatures(&partial_sigs);

        let combined_sig = match result {
            Ok(cs) => {
                println!("\nCombined sig: {:?}", cs);
                cs
            },
            Err(e) => panic!("\nCombining partial sig failed: {}", e),
        };

        println!("\nVerifying Combined sig: {:?}\n\tmsg:\t{:?}\n\tpks:\t{:#?}", combined_sig, msg, pks);
        let result = aggsig.verify(combined_sig, msg, &pks);
        if true==result {
            println!("\nSignature verification:\tOK");
        }else{
            println!("\nSignature verification:\tNOK");
        }
    }
Running result: 
$ cargo test --release  demo_aggsig_multi -- --nocapture

running 1 test
aggsig context with 3 pubkeys: [
    PublicKey(
        4bcb2d167dc03faad734bcf79e322a150b559c8d74606b1eaf50b9f5aa538040bc9f14dca1290e8691712268e13b65bd1618b255d0d63b62ef47d1cdaf211291
    ),
    PublicKey(
        0aa20b3833b4f54c975aa730cbcb17b53ec73774c1e8a2756ffdf2c67489353e0cf119251d7c0015c8131c5288105c15fa3234e14b9b7fc11d313b97593ad222
    ),
    PublicKey(
        f3484d9248a1b284cb9daddc483ecc71c548d566e0ff9a8b4979b75e6545bd79e2d66b5595649b5826c0f9b2b86bdb6667c581dbe0f51fd297efc351160173dc
    )
]
Generating nonces for each index
0 returned true
1 returned true
2 returned true

Partial sign:
	message:	Message(b32975d4b3b65f39863a9a3fe368f84dd9609252b38bcda3d39cbc531294a16b) at index 0
	Pubkey:	PublicKey(4bcb2d167dc03faad734bcf79e322a150b559c8d74606b1eaf50b9f5aa538040bc9f14dca1290e8691712268e13b65bd1618b255d0d63b62ef47d1cdaf211291)
	Partial sig:	AggSigPartialSignature(59e9b526be3161f4350a57f53635f20affc23ad9f1b503652480e4487d683735)

Partial sign:
	message:	Message(b32975d4b3b65f39863a9a3fe368f84dd9609252b38bcda3d39cbc531294a16b) at index 1
	Pubkey:	PublicKey(0aa20b3833b4f54c975aa730cbcb17b53ec73774c1e8a2756ffdf2c67489353e0cf119251d7c0015c8131c5288105c15fa3234e14b9b7fc11d313b97593ad222)
	Partial sig:	AggSigPartialSignature(07f2feaaccd4d0e560acbdf1c9958527a4e71c434620a1fd0befc4bdfb177dd1)

Partial sign:
	message:	Message(b32975d4b3b65f39863a9a3fe368f84dd9609252b38bcda3d39cbc531294a16b) at index 2
	Pubkey:	PublicKey(f3484d9248a1b284cb9daddc483ecc71c548d566e0ff9a8b4979b75e6545bd79e2d66b5595649b5826c0f9b2b86bdb6667c581dbe0f51fd297efc351160173dc)
	Partial sig:	AggSigPartialSignature(e28aa4fd92e174e8f7a088a93b7ab44590c0b138f7846ea5ab36ac818e0455fd)

Combined sig: Signature(446758cf1de7a7c28d579e903b462b797abb2b6f801173cc1bd4f6fb364dc9c2faa4c8e3e2379afb32c97b87b2ed500f663e87cf450eed599f1890f4960cb413)

Verifying Combined sig: Signature(446758cf1de7a7c28d579e903b462b797abb2b6f801173cc1bd4f6fb364dc9c2faa4c8e3e2379afb32c97b87b2ed500f663e87cf450eed599f1890f4960cb413)
	msg:	Message(b32975d4b3b65f39863a9a3fe368f84dd9609252b38bcda3d39cbc531294a16b)
	pks:	[
    PublicKey(
        4bcb2d167dc03faad734bcf79e322a150b559c8d74606b1eaf50b9f5aa538040bc9f14dca1290e8691712268e13b65bd1618b255d0d63b62ef47d1cdaf211291
    ),
    PublicKey(
        0aa20b3833b4f54c975aa730cbcb17b53ec73774c1e8a2756ffdf2c67489353e0cf119251d7c0015c8131c5288105c15fa3234e14b9b7fc11d313b97593ad222
    ),
    PublicKey(
        f3484d9248a1b284cb9daddc483ecc71c548d566e0ff9a8b4979b75e6545bd79e2d66b5595649b5826c0f9b2b86bdb6667c581dbe0f51fd297efc351160173dc
    )
]

Signature verification:	OK

Fourth Demo: Batch Verification

Let's have a demo for 3 Keys.

Source Code (Click to expand) 

    #[test]
    fn demo_aggsig_batch_verify() {

        /*
         * Signature Aggregation (Batch Verification):
         * All the signatures in the block can be removed and only keep an aggregated one.
         * Signature aggregation can be done by a miner and save a lot of space in the block.
         */

        let secp = Secp256k1::with_caps(ContextFlag::Full);

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        //--- Generate nonce: k1,k2,k3
        let secnonce_1 = export_secnonce_single(&secp).unwrap();
        let secnonce_2 = export_secnonce_single(&secp).unwrap();
        let secnonce_3 = export_secnonce_single(&secp).unwrap();

        //--- Calculate public nonce: R1,R2,R3
        let pubnonce_1 = PublicKey::from_secret_key(&secp, &secnonce_1).unwrap();
        let pubnonce_2 = PublicKey::from_secret_key(&secp, &secnonce_2).unwrap();
        let pubnonce_3 = PublicKey::from_secret_key(&secp, &secnonce_3).unwrap();

        //--- And sum public nonce: R = R1+R2+R3
        let nonce_sum = PublicKey::from_combination(&secp, vec![&pubnonce_1, &pubnonce_2, &pubnonce_3]).unwrap();

        //--- sig1
        println!("\n--- sig1 ---");

        let (sk1, pk1) = secp.generate_keypair(&mut thread_rng()).unwrap();

        println!("public key (P):\t\t{:?}\nprivate key (p):\t{:?}", pk1, sk1);

        // e=hash(R, P, m)    s=k1+e*p1    sig1=(s,r1)
        let sig1 = sign_single(&secp, &msg, &sk1, Some(&secnonce_1), Some(&nonce_sum), Some(&nonce_sum)).unwrap();
        println!("msg:\t\t\t{:?}", msg);
        println!("\nschnorr sig1:\t\t{:?}", sig1);

        // sig1.s*G-e*P1 = k1*G+e*p1*G-e*P1 = R1,   check R1.x == sig1.r ?
        let result = verify_single(&secp, &sig1, &msg, Some(&nonce_sum), &pk1, true);
        if true == result {
            println!("sig1 signature check:\tOK");
        }else{
            println!("sig1 signature check:\tNOK");
        }

        //--- sig2

        println!("\n--- sig2 ---");

        let (sk2, pk2) = secp.generate_keypair(&mut thread_rng()).unwrap();

        println!("public key (P):\t\t{:?}\nprivate key (p):\t{:?}", pk2, sk2);

        // e=hash(R, P, m)    s=k2+e*p2    sig2=(s,r2)
        let sig2 = sign_single(&secp, &msg, &sk2, Some(&secnonce_2), Some(&nonce_sum), Some(&nonce_sum)).unwrap();
        println!("msg:\t\t\t{:?}", msg);
        println!("\nschnorr sig2:\t\t{:?}", sig2);

        // sig2.s*G-e*P2 = k2*G+e*p2*G-e*P2 = R2,   check R2.x == sig2.r ?
        let result = verify_single(&secp, &sig2, &msg, Some(&nonce_sum), &pk2, true);
        if true == result {
            println!("sig2 signature check:\tOK");
        }else{
            println!("sig2 signature check:\tNOK");
        }

        //--- sig3

        println!("\n--- sig3 ---");

        let (sk3, pk3) = secp.generate_keypair(&mut thread_rng()).unwrap();

        println!("public key (P):\t\t{:?}\nprivate key (p):\t{:?}", pk3, sk3);

        // e=hash(R, P, m)    s=k3+e*p3    sig3=(s,r3)
        let sig3 = sign_single(&secp, &msg, &sk3, Some(&secnonce_3), Some(&nonce_sum), Some(&nonce_sum)).unwrap();
        println!("msg:\t\t\t{:?}", msg);
        println!("\nschnorr sig3:\t\t{:?}", sig3);

        // sig3.s*G-e*P3 = k3*G+e*p3*G-e*P3 = R3,   check R3.x == sig3.r ?
        let result = verify_single(&secp, &sig3, &msg, Some(&nonce_sum), &pk3, true);
        if true == result {
            println!("sig3 signature check:\tOK");
        }else{
            println!("sig3 signature check:\tNOK");
        }

        //--- Batch Verification

        println!("\n--- Batch Verification ---");

        let sig_vec = vec![&sig1, &sig2, &sig3];
        let combined_sig = add_signatures_single(&secp, sig_vec, &nonce_sum).unwrap();

        // Sum public keys: P = P1+P2+P3
        let pk_sum = PublicKey::from_combination(&secp, vec![&pk1, &pk2, &pk3]).unwrap();

        println!("\nCombined sig:\t{:?}\n\tmsg:\t{:?}\n\tpk_sum:\t{:?}", combined_sig, msg, pk_sum);
        // sig.s*G-e*P = k*G+e*p*G-e*P = R,   check R.x == sig.r ?
        let result = verify_single(&secp, &combined_sig, &msg, Some(&nonce_sum), &pk_sum, false);
        if true==result {
            println!("\nSignature Batch Verification:\tOK");
        }else{
            println!("\nSignature Batch Verification:\tNOK");
        }
    }
Running result: 
$ cargo test --release demo_aggsig_batch_verify -- --nocapture

running 1 test

--- sig1 ---
public key (P):		PublicKey(8a80bcd2fcc9e7209928da69ec1e56c9915fbb7c81b7f7bb14544235f6bb9bfa48d14b702d29a30bf25e9bb796d73b932584c69095e39c03aeb863d0656d0155)
private key (p):	SecretKey(4ab9677dd124b95cf8f1833b003260ab7ed1a34eeedcaf88d2265c84f039d81c)
msg:			Message(157a86e9e798e2381660001b5b3682b8888cd4b67e8ac03d45e785bc9c051059)

schnorr sig1:		Signature(a1439d84d1771e538c33eac19998e51721b19e55370752bb230185ec9cd0196989697003d919a93641c3fc563907551f35fdb3f6c736ecc71a906392efe9b05f)
sig1 signature check:	OK

--- sig2 ---
public key (P):		PublicKey(e88a44c9cd923d22a106e24efe3e35ba06badcb63509e08b10657adb46f81f2132dccb3443008ca76ce1445b2d564b71c4d18d947e0d6c4ab42b8c5d96faf987)
private key (p):	SecretKey(b88e4e8c83ef7ecd7aa2fd497c27d8d5377696cacb41179ee25116a9be0aef18)
msg:			Message(157a86e9e798e2381660001b5b3682b8888cd4b67e8ac03d45e785bc9c051059)

schnorr sig2:		Signature(9beda0ed060709b8604c702afa460cfeca482e763add50d3c79f2449944da94eebe993e83354277042ddfe0bbf316ba363ae565ea276a218ec09302e7c91662b)
sig2 signature check:	OK

--- sig3 ---
public key (P):		PublicKey(6ccbc02b6d9de6f3c0f7fcd76aa1e0a3b01d540b16d8d85f95f8ea1213becf74f1a0f97ed2a60da360b98cec2c8e4d41a3eb439073f46422674079bfefbc7881)
private key (p):	SecretKey(c6d0cfd9bb17eb3ed1858863e708ea72e21828d416386a67bb3de64513ae2758)
msg:			Message(157a86e9e798e2381660001b5b3682b8888cd4b67e8ac03d45e785bc9c051059)

schnorr sig3:		Signature(a2e2fa9fe0822cfc871650c15944c9b302ad98aaa37e21def5225ce87db768014717d78b54b1a9ff958fa6ebe169428a5d84ae49867fae1831f8035d3a59381e)
sig3 signature check:	OK

--- Batch Verification ---

Combined sig:	Signature(e0143911b80055087396abaded23bbca33f8888f661a25321ff0a891de9ee97779866d4e01b516690fa683c34571e8b963742f091b0910445d1919ebb675def1)
	msg:	Message(157a86e9e798e2381660001b5b3682b8888cd4b67e8ac03d45e785bc9c051059)
	pk_sum:	PublicKey(204c288dc55097754852b03e3b64442c1ed134938aac6d4f34158675aecf173603fadbd6c2282a9f4ae0064a9b3e1d7b4c8a60ee8160e95604891c75bcb01950)

Signature Batch Verification:	OK

Explain:

  1. Generate random number nonce: k1,k2,k3
  2. Calculate public nonce: R1,R2,R3, for each Ri=ki*G
  3. Sum public nonce: R = R1+R2+R3
  4. Calculate 1st signature: sig1. e=hash(R, P, m) s=k1+e*p1 sig1=(s,R1.x)
  5. Verify sig1: sig1.s*G-e*P1 = k1*G+e*p1*G-e*P1 = R1, check R1.x == sig1.r ?
  6. Calculate 2nd signature: sig2. e=hash(R, P, m) s=k2+e*p2 sig2=(s,R2.x)
  7. Verify sig2: sig2.s*G-e*P2 = k2*G+e*p2*G-e*P2 = R2, check R2.x == sig2.r ?
  8. Calculate 3rd signature: sig3. e=hash(R, P, m) s=k3+e*p3 sig3=(s,R3.x)
  9. Verify sig3: sig3.s*G-e*P3 = k3*G+e*p3*G-e*P3 = R3, check R3.x == sig3.r ?
  10. Combine signature: s=s1+s2+s3, R.x = (R1+R2+R3).x
  11. Batch Verification: sum public keys: P = P1+P2+P3, then sig.s*G-e*P = (k1+k2+k3)*G+(e*p1+e*p2+e*p3)*G-e*P = R1+R2+R3 + e*(P1+P2+P3) - e*P = R, check R.x == sig.r ?.

Basics

Researches

Clone this wiki locally