Adding Public Keys … Part 1: The Schnorr Way

Adding Public Keys … Part 1: The Schnorr Way

The Schnorr signature method supports the merging of public keys to produce a single signature for a transaction [Schnorr aggregate]. Unfortunately, it is not secure and suffers from the cancellation problem [here], but which can be overcome with the MuSig method or the BN Method [here]. In this article, I will illustrate how the Schnorr signature method works. The MuSig method is outlined by Greg Maxwell et al in this paper [1][here]:

In Part 2, I will outline the MuSig method using Rust, but in this article I will focus on a simple demonstration of the Schnorr signature method using Rust. If you want a quick outline of MuSig, click here.

Schnorr with Multiple Signers

In areas such as Bitcoin, we can have multiple signers to a transaction. This would require multiple signatures to prove each of the signers. The advantage with the Schnorr signature method is that we can simply add each of the public keys, and signatures together to produce a valid single signature. So let’s take an example of a message that both Bob and Alice sign.

Initially, Alice has a private key r1, and her public key will then be:

U=r1×G

To sign a new message, she then generates random nonce rt1 and defines a commitment to this value:

Ut1=rt1×G

Initially, Bob has a private key r2, and her public key will then be:

U=r2×G

To sign a new message, she then generates random nonce rt2 and defines a commitment to this value:

Ut2=rt2×G

We then merge their public keys with an addition:

U=U1+U2

and their commitments:

Ut=Ut1+Ut2

Next, with a message (m), she computes a challenge (c) with a hash function of:

c=H(m,Ut)

and where H() is a hashing function, such as with SHA-256. Next, Alice computes:

rz1=rt1+c×r1

Bob computes:

rz2=rt2+c×r2

We then get:

rz=rz1+rz2

Alice and Bob then send Ut and rz to Victor (the verifier). Victor then determines if:

rz×G=Ut+c×U

In this case, we will use the Edwards curve (Ed25519) for our signature. In the following Rust code, we use a base point on the curve (G), and generate a random private key for Peggy (the prover) of r. Her public key becomes another point on the curve represented by rG.

In Rust, we trust to sign

An outline of the Rust code is [here]:

extern crate curve25519_dalek;
extern crate rand_core;
extern crate sha2;

use curve25519_dalek::constants;

use curve25519_dalek::scalar::Scalar;

// use rand::prelude::*;

use sha2::{Sha256, Digest};

use rand_core::OsRng;
use std::env;

fn main() {

    let mut message="password";
    let args: Vec = env::args().collect();
  
    if args.len() >1 { message = args[1].as_str();}

    // Base point
    let G = &constants::ED25519_BASEPOINT_POINT;

    let r1 = Scalar::random(&mut OsRng);
    let r2 = Scalar::random(&mut OsRng);

    //Public key (rG)
    let U1 = r1*G;
    let U2 = r2*G;

    //Create a random nonce (rt) for each proof
    let rt1 = Scalar::random(&mut OsRng);
    let rt2 = Scalar::random(&mut OsRng);

    let Ut1= rt1*G;
    let Ut2= rt2*G;

    // Challenge generation
    let mut temp: [u8;32] = [0u8;32];
    let mut hasher = Sha256::new();
    hasher.update(message.as_bytes());
    hasher.update(Ut1.compress().to_bytes());
    temp.copy_from_slice(hasher.finalize().as_slice());

    let c = Scalar::from_bytes_mod_order(temp);

    let rz1 = rt1 + c*r1;
    let rz2 = rt2 + c*r2;

    println!("Message:={:}",message);

    println!("\nG={:}",hex::encode(G.compress().as_bytes()));

    println!("First signer: Bob");
    println!("-- Let's pick the private key (r1) -- ");
    println!("r= {:}",hex::encode(r1.as_bytes()));
    println!("-- Let's generate the public key (r1G) -- ");
    println!("\nU=rG= {:}",hex::encode(U1.compress().as_bytes()));

    println!("\n-- Let's pick a random value (rt) -- ");
    println!("rt= {:}",hex::encode(rt1.as_bytes()));

    println!("Ut=rtG= {:}",hex::encode(Ut1.compress().as_bytes()));

    println!("First signer: Alice");
    println!("-- Let's pick the private key (r2) -- ");
    println!("r= {:}",hex::encode(r2.as_bytes()));
    println!("-- Let's generate the public key (r2G) -- ");
    println!("\nU=rG= {:}",hex::encode(U2.compress().as_bytes()));

    println!("\n-- Let's pick a random value (rt2) -- ");
    println!("rt= {:}",hex::encode(rt2.as_bytes()));

    println!("Ut=rtG= {:}",hex::encode(Ut2.compress().as_bytes()));

    println!("\n-- Let's generate the challenge (c) and response (rz) -- ");
    println!("c= {:}",hex::encode(c.as_bytes()));
    println!("rz=rt+c*r {:}",hex::encode(rz1.as_bytes()));

    let U = U1 + U2;
    let rz = rz1 + rz2;
    let Ut = Ut1 + Ut2;

    println!("\n-- Let's merge signers -- ");
    println!("Ut=U1+U2= {:}",hex::encode(Ut2.compress().as_bytes()));
    println!("rz=rz1+rz2 {:}",hex::encode(rz.as_bytes()));
    println!("Ut=U1+U2= {:}",hex::encode(Ut.compress().as_bytes()));
    
    let p1=rz*G;
    let p2=Ut+c*U;
    println!("\n-- Computing the proof -- ");
    println!("\nrz*G={:}",hex::encode(p1.compress().as_bytes()));
    println!("Ut+c*U{:}",hex::encode(p2.compress().as_bytes()));

    if (p1==p2) {
        println!("Proven!!");   
    }
    else {
        println!("Not proven");
    }

}

A sample run is [here]:

G=5866666666666666666666666666666666666666666666666666666666666666
First signer: Bob
-- Let's pick the private key (r1) -- 
r= e8e68217b083852f960e3665860a450f01336bb1bbb64742b7205eb7b089a002
-- Let's generate the public key (r1G) -- 

U=rG= 8152ce9e948f639a63b0f924187c57fdd135dcce759cf406ec94ab8eeaee5549

-- Let's pick a random value (rt) -- 
rt= 593a2ff2fd546670c5105dd520213df11d4c68531bc1ca8375d856b181ebcb04
Ut=rtG= 554f7ee8b9681f6bd82220d1f8c2aa57c72a0882cd015a740e87ec9161deaddb
First signer: Alice
-- Let's pick the private key (r2) -- 
r= a905b05bfaf7e19d4e56d3001dcc3318c280088ba59a7a4b8975bfb2b6ac2706
-- Let's generate the public key (r2G) -- 

U=rG= 98586f18f1221cd8135af03167c45440ea8df4497345b95751ffbe9afc27dfde

-- Let's pick a random value (rt2) -- 
rt= c8dcd6fc124d9add1f849b5356aafeb769d719ad97bc1b2cd56747821b80290a
Ut=rtG= 4b0853dc36c7c822538b0dc8cd319a9d234ff8bceb20ed1135762d4d0347a806

-- Let's generate the challenge (c) and response (rz) -- 
c= 81ba7a4474bc4f5532897e80ccb0de107b4fbef6edd1b3967b45bc4725dd5700
rz=rt+c*r cf5c93c5213cac21f03f055ed0b0e0e0b3ee7a72b6e9ca8eb26b025a5523d100

-- Let's merge signers -- 
Ut=U1+U2= 4b0853dc36c7c822538b0dc8cd319a9d234ff8bceb20ed1135762d4d0347a806
rz=rz1+rz2 f704e8799f8d3118399875993da73ca1d545ccee7dcc81784be96764e3e05f05
Ut=U1+U2= cef153934cae57e8fb462fa60621ef45d9bbaacfea7a62b203c105bd6665a98d

-- Computing the proof -- 

rz*G=0720d00cc73856bada2d8eb797a8d2ed59b01471b3a93079589ba980a864ac0b
Ut+c*U0720d00cc73856bada2d8eb797a8d2ed59b01471b3a93079589ba980a864ac0b
Proven!!

Reference

[1] Maxwell, G., Poelstra, A., Seurin, Y., & Wuille, P. (2019). Simple schnorr multi-signatures with applications to bitcoin. Designs, Codes and Cryptography, 87(9), 2139–2164 [here].