Introduction to Schnorr Signatures

Home / Cryptography / Introduction to Schnorr Signatures

15 min read

Overview
Let’s get Started
Basics of Schnorr Signatures
- Public and Private Keys
- Creating a Signature
Schnorr Signatures
MuSig
References
Contributors

Overview

Private-public key pairs are the cornerstone of much of the cryptographic security underlying everything from secure web browsing to banking to cryptocurrencies. Private-public key pairs are asymmetric. This means that given one of the numbers (the private key), it’s possible to derive the other one (the public key). However, doing the reverse is not feasible. It’s this asymmetry that allows one to share the public key, uh, publicly and be confident that no one can figure out our private key (which we keep very secret and secure).

Asymmetric key pairs are employed in two main applications:

in authentication, where you prove that you have knowledge of the private key; and
in encryption, where messages can be encoded and only the person possessing the private key can decrypt and read the message.

In this introduction to digital signatures, we’ll be talking about a particular class of keys: those derived from elliptic curves. There are other asymmetric schemes, not least of which are those based on products of prime numbers, including RSA keys [1].

We’re going to assume you know the basics of elliptic curve cryptography (ECC). If not, don’t stress, there’s a gentle introduction in a previous chapter.

Let’s get Started

This is an interactive introduction to digital signatures. It uses Rust code to demonstrate some of the ideas presented here, so you can see them at work. The code for this introduction uses the tari_crypto library.

Tari makes use of the Ristretto elliptic curve in its cryptography ([Why Risretto?]).

This particular implementation has some nice features. We’ve overridden the + (addition) and * (multiplication) operators so that the Rust code looks a lot more like mathematical formulae. This makes it much easier to play with the ideas we’ll be exploring.

Basics of Schnorr Signatures

Public and Private Keys

The first thing we’ll do is create a public and private key from an elliptic curve.

On Ristretto, a private key is simply a scalar integer value between 0 and ~2²⁵⁶. That’s roughly how many atoms there are in the universe, so we have a big sandbox to play in.

We have a special point on the Ristretto curve called G, which acts as the “origin”. A public key is calculated by adding G on the curve to itself, $k_{a}$ times. This is the definition of multiplication by a scalar, and is written as:

P_{a} = k_{a} G

Let’s take an example from this post, where it is known that the public key for 1, when written in uncompressed format, is 6a493210f74...73a3b919. The following code snippet demonstrates this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
use tari_crypto;
use tari_crypto::keys::PublicKey;
use tari_crypto::ristretto::pedersen::RISTRETTO_PEDERSEN_G;
use tari_crypto::ristretto::{RistrettoPublicKey, RistrettoSecretKey};
use tari_crypto::tari_utilities::hex::Hex;
#[allow(non_snake_case)]
fn main() {
    // Create the secret key "1" . Ristretto uses little-endian encoding, so the number is written back to front
    let k = RistrettoSecretKey::from_hex(
        "0100000000000000000000000000000000000000000000000000000000000000",
    )
    .unwrap();
    // Generate the public key, P = k.G = 1.G
    let pub_from_k = RistrettoPublicKey::from_secret_key(&k);
    let known_pub = RistrettoPublicKey::from_hex(
        "e2f2ae0a6abc4e71a884a961c500515f58e30b6aa582dd8db6a65945e08d2d76",
    )
    .unwrap();
    // Compare it to the known value
    assert_eq!(pub_from_k, known_pub);
    println!("Ok, P = k.G");
    // But k = 1, so P = 1.G === G
    assert_eq!(pub_from_k.point(), RISTRETTO_PEDERSEN_G);
    println!("Ok, P = 1.G = G");
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Creating a Signature

Approach Taken

Reversing ECC math multiplication (i.e. division) is pretty much infeasible when using properly chosen random values for your scalars ([5],[6]). This property is called the Discrete Log Problem, and is used as the principle behind many cryptography and digital signatures. A valid digital signature is evidence that the person providing the signature knows the private key corresponding to the public key with which the message is associated, or that they have solved the Discrete Log Problem.

The approach to creating signatures always follows this recipe:

Generate a secret once-off number (called a nonce), $r$ .
Calculate the public version of the nonce, $R$ from $r$ (where $R = r . G$ ).
Send the following to Bob, your recipient - your message ( $m$ ), $R$ , and your public key ( $P = k . G$ ).

The actual signature is created by hashing the combination of all the public information above to create a challenge, $e$ :

e = H (R ‖ P ‖ m)

The hashing function is chosen so that e has the same range as your private keys. In our case, we want something that returns a 256-bit number, so SHA256 is a good choice.

Now the signature is constructed using your private information:

s = r + k e

Bob can now also calculate $e$ , since he already knows $m, R, P$ . But he doesn’t know your private key, or nonce.

Note: When you construct the signature like this, it’s known as a Schnorr signature, which is discussed in a following section. There are other ways of constructing $s$ , such as ECDSA [2], which is used in Bitcoin.

But see this:

s G = (r + k e) G

Multiply out the right-hand side:

s G = r G + (k G) e ​

Substitute $R = r G$ and $P = k G$ and we have: $s G = R + P e $

So Bob must just calculate the public key corresponding to the signature $(s . G)$ and check that it equals the right-hand side of the last equation above $(R + P . e)$ , all of which Bob already knows.

Why do we Need the Nonce?

Why do we need a nonce in the standard signature?

Let’s say we naïvely sign a message $m$ with

e = H (P ‖ m)

and then the signature would be $s = e k$ .

Now as before, we can check that the signature is valid:

\begin{aligned} s G & = e k G \\ = e (k G) = e P \end{aligned}

So far so good. But anyone can read your private key now because $s$ is a scalar, so $k = s / e$ is not hard to do. With the nonce you have to solve $k = (s - r) / e$ , but $r$ is unknown, so this is not a feasible calculation as long as $r$ has been chosen randomly.

We can show that leaving off the nonce is indeed highly insecure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
use rand::thread_rng;
use tari_crypto::keys::{PublicKey, SecretKey};
use tari_crypto::ristretto::{RistrettoPublicKey, RistrettoSchnorr, RistrettoSecretKey};
use tari_crypto::signatures::SchnorrSignature;
#[allow(non_snake_case)]
fn main() {
    // Create a random private key
    let mut rng = thread_rng();
    let k = RistrettoSecretKey::random(&mut rng);
    println!("My private key: {}", k.reveal());
    let P = RistrettoPublicKey::from_secret_key(&k);
    // Challenge, e = H(P || m), which effectively random
    let e = RistrettoSecretKey::random(&mut rng);
    // "Signature" without a nonce. DON'T DO THIS!
    let s = &e * &k;
    // Verify the signature
    assert_eq!(RistrettoPublicKey::from_secret_key(&s), &e * P);
    println!("'Signature' is valid... but it's not a signature!");
    // But let's try calculate the private key from known information
    let hacked = s * e.invert().unwrap();
    assert_eq!(k, hacked);
    println!("Hacked key:     {}", k.reveal())
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

ECDH

How do parties that want to communicate securely generate a shared secret for encrypting messages? One way is called the Elliptic Curve Diffie-Hellman exchange (ECDH), which is a simple method for doing just this.

ECDH is used in many places, including the Lightning Network during channel negotiation [3].

Here’s how it works. Alice and Bob want to communicate securely. A simple way to do this is to use each other’s public keys and calculate

\begin{aligned} (Alice) & S_{a} & = k_{a} P_{b} \\ (Bob) & S_{b} & = k_{b} P_{a} \\ ⟹ S_{a} = k_{a} k_{b} G & \equiv S_{b} = k_{b} k_{a} G \end{aligned}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
use blake2::digest::typenum::U64;
use blake2::Blake2b;
use rand::thread_rng;
use tari_crypto::hash_domain;
use tari_crypto::hashing::DomainSeparatedHasher;
use tari_crypto::keys::{PublicKey, SecretKey};
use tari_crypto::ristretto::{RistrettoPublicKey, RistrettoSecretKey};
use tari_crypto::tari_utilities::ByteArray;
hash_domain!(ECDH, "ecdh_demo");
#[allow(non_snake_case)]
fn main() {
    let mut rng = thread_rng();
    // Alice creates a public-private keypair
    let k_a = RistrettoSecretKey::random(&mut rng);
    let P_a = RistrettoPublicKey::from_secret_key(&k_a);
    // Bob creates a public-private keypair
    let k_b = RistrettoSecretKey::random(&mut rng);
    let P_b = RistrettoPublicKey::from_secret_key(&k_b);
    // They each calculate the shared secret based only on the other party's public information
    // Alice's version:
    let S_a = hash_pubkey(k_a * P_b);
    println!("Alice's version: {}", S_a.reveal());
    // Bob's version:
    let S_b = hash_pubkey(k_b * P_a);
    println!("Bob's version:   {}", S_b.reveal());
    assert_eq!(S_a, S_b, "The shared secret is not the same!");
    println!("The shared secret is identical")
}
fn hash_pubkey(p: RistrettoPublicKey) -> RistrettoSecretKey {
    let hash = DomainSeparatedHasher::<Blake2b<U64>, ECDH>::new_with_label("ecdh_derive")
        .digest(p.as_bytes());
    RistrettoSecretKey::from_uniform_bytes(hash.as_ref()).unwrap()
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

For security reasons, the private keys are usually chosen at random for each session (you’ll see the term ephemeral keys being used), but then we have the problem of not being sure the other party is who they say they are (perhaps due to a man-in-the-middle attack [4]).

Various additional authentication steps can be employed to resolve this problem, which we won’t get into here.

Schnorr Signatures

If you follow the crypto news, you’ll know that that the new hotness (at the time of writing, in 2018) in Bitcoin is Schnorr Signatures.

But in fact, they’re old news! The Schnorr signature is considered the simplest digital signature scheme to be provably secure in a random oracle model. It is efficient and generates short signatures. It was covered by U.S. Patent 4,995,082, which expired in February 2008 [7].

So why all the Fuss?

What makes Schnorr signatures so interesting and potentially dangerous, is their simplicity. Schnorr signatures are linear, so you have some nice properties.

Elliptic curves have the multiplicative property. So if you have two scalars $x, y$ with corresponding points $X, Y$ , the following holds:

(x + y) G = x G + y G = X + Y

Schnorr signatures are of the form $s = r + e . k$ . This construction is linear too, so it fits nicely with the linearity of elliptic curve math.

You saw this property in a previous section, when we were verifying the signature. Schnorr signatures’ linearity makes it very attractive for, among others:

signature aggregation;
atomic swaps;
“scriptless” scripts.

Naïve Signature Aggregation

Let’s see how the linearity property of Schnorr signatures can be used to construct a two-of-two multi-signature.

Alice and Bob want to cosign something (a Tari transaction, say) without having to trust each other; i.e. they need to be able to prove ownership of their respective keys, and the aggregate signature is only valid if both Alice and Bob provide their part of the signature.

Assuming private keys are denoted $k_{i}$ and public keys $P_{i}$ . If we ask Alice and Bob to each supply a nonce, we can try:

\begin{aligned} P_{a g g} & = P_{a} + P_{b} \\ e & = H (R_{a} ‖ R_{b} ‖ P_{a} ‖ P_{b} ‖ m) \\ s_{a g g} & = r_{a} + r_{b} + (k_{a} + k_{b}) e \\ = (r_{a} + k_{a} e) + (r_{b} + k_{a} e) \\ = s_{a} + s_{b} \end{aligned}

So it looks like Alice and Bob can supply their own $R$ , and anyone can construct the two-of-two signature from the sum of the $R s$ and public keys. This does work:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
use blake2::digest::typenum::U64;
use blake2::{Blake2b, Digest};
use generic_array;
use rand::thread_rng;
use tari_crypto;
use tari_crypto::hash_domain;
use tari_crypto::hashing::DomainSeparatedHasher;
use tari_crypto::keys::{PublicKey, SecretKey};
use tari_crypto::ristretto::{RistrettoPublicKey, RistrettoSchnorr, RistrettoSecretKey};
use tari_crypto::tari_utilities::hex::{to_hex, Hex};
use tari_crypto::tari_utilities::ByteArray;
#[allow(non_snake_case)]
fn main() {
    let mut rng = thread_rng();
    // Alice generates some keys
    let (ka, Pa) = RistrettoPublicKey::random_keypair(&mut rng);
    // Alice generates a nonce
    let (ra, Ra) = RistrettoPublicKey::random_keypair(&mut rng);
    // Bob generates some keys
    let (kb, Pb) = RistrettoPublicKey::random_keypair(&mut rng);
    // Bob generates a nonce
    let (rb, Rb) = RistrettoPublicKey::random_keypair(&mut rng);
    // // The challenge uses both nonce public keys and private keys
    // // e = H(Ra || Rb || Pa || Pb || H(m))
    let e = calculate_challenge(&Ra, &Rb, &Pa, &Pb, "This is a multisig");
    // Alice calculates her signature
    let sa = ra + ka * &e;
    // Bob calculates his signature
    let sb = rb + kb * &e;
    // Calculate the aggregate signature
    let s_agg = sa + sb;
    // S = s_agg.G
    let S = RistrettoPublicKey::from_secret_key(&s_agg);
    // This should equal Ra + Rb + e(Pa + Pb)
    assert_eq!(S, Ra + Rb + e * (Pa + Pb));
    println!("The aggregate signature is valid!");
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

But this scheme is not secure!

Key Cancellation Attack

Let’s take the previous scenario again, but this time, Bob knows Alice’s public key and nonce ahead of time, by waiting until she reveals them.

Now Bob lies and says that his public key is $P_{b}^{'} = P_{b} - P_{a}$ and public nonce is $R_{b}^{'} = R_{b} - R_{a}$ .

Note that Bob doesn’t know the private keys for these faked values, but that doesn’t matter.

Everyone assumes that $s_{a g g} = R_{a} + R_{b}^{'} + e (P_{a} + P_{b}^{'})$ as per the aggregation scheme.

But Bob can create this signature himself:

\begin{aligned} s_{a g g} G & = R_{a} + R_{b}^{'} + e (P_{a} + P_{b}^{'}) \\ = R_{a} + (R_{b} - R_{a}) + e (P_{a} + P_{b} - P_{a}) \\ = R_{b} + e P_{b} \\ = r_{b} G + e k_{b} G \\ ∴ s_{a g g} & = r_{b} + e k_{b} = s_{b} \end{aligned}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
use blake2::digest::typenum::U64;
use blake2::{Blake2b, Digest};
use rand::thread_rng;
use tari_crypto::hash_domain;
use tari_crypto::hashing::DomainSeparatedHasher;
use tari_crypto::keys::{PublicKey, SecretKey};
use tari_crypto::ristretto::{RistrettoPublicKey, RistrettoSecretKey};
use tari_crypto::tari_utilities::ByteArray;
// Domain separation prevents hashes accidentally colliding, are letting messages from one application be used in another
hash_domain!(CDomain, "cancellation_demo");
#[allow(non_snake_case)]
fn main() {
    // Alice generates some keys
    let (_ka, Pa, _ra, Ra) = get_keyset();
    // Bob generates some keys as before
    let (kb, Pb, rb, Rb) = get_keyset();
    // ..and then publishes his forged keys
    let Pf = &Pb - &Pa;
    let Rf = &Rb - &Ra;
    // The challenge uses both nonce public keys and private keys
    // e = H(Ra || Rb' || Pa || Pb' || H(m))
    let hash =
        DomainSeparatedHasher::<Blake2b<U64>, CDomain>::new_with_label("aggregated_challenge")
            .chain_update(Ra.as_bytes())
            .chain_update(Rf.as_bytes())
            .chain_update(Pa.as_bytes())
            .chain_update(Pf.as_bytes())
            .chain_update(b"a multisig transaction")
            .finalize();
    let e = RistrettoSecretKey::from_uniform_bytes(hash.as_ref()).unwrap();
    // Bob creates a forged signature
    let s_f = &rb + &e * &kb;
    // Check if it's valid
    let sG = &Ra + &Rf + &e * (&Pa + &Pf);
    assert_eq!(sG, PublicKey::from_secret_key(&s_f));
    println!("Bob successfully forged the aggregate signature!")
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Better Approaches to Aggregation

In the Key Cancellation Attack, Bob didn’t know the private keys for his published $R$ and $P$ values. We could defeat Bob by asking him to sign a message proving that he does know the private keys.

This works, but it requires another round of messaging between parties, which is not conducive to a great user experience.

A better approach would be one that incorporates one or more of the following features:

It must be provably secure in the plain public-key model, without having to prove knowledge of secret keys, as we might have asked Bob to do in the naïve approach.
It should satisfy the normal Schnorr equation, i.e. the resulting signature can be verified with an expression of the form $R + e X$ .
It allows for Interactive Aggregate Signatures (IAS), where the signers are required to cooperate.
It allows for Non-interactive Aggregate Signatures (NAS), where the aggregation can be done by anyone.
It allows each signer to sign the same message, $m$ .
It allows each signer to sign their own message, $m_{i}$ .

MuSig

MuSig is a recently proposed ([8],[9]) simple signature aggregation scheme that satisfies all of the properties in the preceding section.

MuSig Demonstration

We’ll demonstrate the interactive MuSig scheme here, where each signatory signs the same message. The scheme works as follows:

Each signer has a public-private key pair, as before.
Each signer shares a commitment to their public nonce (we’ll skip this step in this demonstration). This step is necessary to prevent certain kinds of rogue key attacks [10].
Each signer publishes the public key of their nonce, $R_{i}$ .
Everyone calculates the same “shared public key”, $X$ as follows:

\begin{aligned} ℓ & = H (X_{1} ‖ \dots ‖ X_{n}) \\ a_{i} & = H (ℓ ‖ X_{i}) \\ X & = \sum a_{i} X_{i} \end{aligned}

Note that in the preceding ordering of public keys, some deterministic convention should be used, such as the lexicographical order of the serialized keys.

Everyone also calculates the shared nonce, $R = \sum R_{i}$ .
The challenge, $e$ is $H (R | | X | | m)$ .
Each signer provides their contribution to the signature as:

s_{i} = r_{i} + k_{i} a_{i} e

Notice that the only departure here from a standard Schnorr signature is the inclusion of the factor $a_{i}$ .

The aggregate signature is the usual summation, $s = \sum s_{i}$ .

Verification is done by confirming that as usual:

s G \equiv R + e X

Proof:

\begin{aligned} s G & = \sum s_{i} G \\ = \sum (r_{i} + k_{i} a_{i} e) G \\ = \sum r_{i} G + k_{i} G a_{i} e \\ = \sum R_{i} + X_{i} a_{i} e \\ = \sum R_{i} + e \sum a_{i} X_{i} \\ = R + e X \\ ◼ \end{aligned}

Let’s demonstrate this using a three-of-three multisig:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
use blake2::digest::typenum::U64;
use blake2::{Blake2b, Digest};
use rand::thread_rng;
use tari_crypto::hash_domain;
use tari_crypto::hashing::DomainSeparatedHasher;
use tari_crypto::keys::{PublicKey, SecretKey};
use tari_crypto::ristretto::{RistrettoPublicKey, RistrettoSecretKey};
use tari_crypto::tari_utilities::ByteArray;
hash_domain!(MusigDomain, "musig_demo");
#[allow(non_snake_case)]
fn main() {
    let (k1, X1, r1, R1) = get_keys();
    let (k2, X2, r2, R2) = get_keys();
    let (k3, X3, r3, R3) = get_keys();
    // I'm setting the order here. In general, they'll be sorted
    let l = calculate_challenge(&[X1.as_bytes(), &X2.as_bytes(), &X3.as_bytes()], "L");
    // ai = H(l || p)
    let a1 = calculate_challenge(&[l.as_bytes(), X1.as_bytes()], "a1");
    let a2 = calculate_challenge(&[l.as_bytes(), X2.as_bytes()], "a2");
    let a3 = calculate_challenge(&[l.as_bytes(), X3.as_bytes()], "a3");
    // X = sum( a_i X_i)
    let X = &a1 * X1 + &a2 * X2 + &a3 * X3;
    let m = calculate_challenge(&[b"SomeSharedMultiSigTx"], "message");
    // Calc shared nonce
    let R = R1 + R2 + R3;
    // e = H(R || X || m)
    let e = calculate_challenge(&[R.as_bytes(), X.as_bytes(), m.as_bytes()], "challenge");
    // Signatures
    let s1 = r1 + k1 * a1 * &e;
    let s2 = r2 + k2 * a2 * &e;
    let s3 = r3 + k3 * a3 * &e;
    let s = s1 + s2 + s3;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Security Demonstration

As a final demonstration, let’s show how MuSig defeats the cancellation attack from the naïve signature scheme. Using the same idea as in the Key Cancellation Attack section, Bob has provided fake values for his nonce and public keys:

\begin{aligned} R_{f} & = R_{b} - R_{a} \\ X_{f} & = X_{b} - X_{a} \end{aligned}

This leads to both Alice and Bob calculating the following “shared” values:

\begin{aligned} ℓ & = H (X_{a} ‖ X_{f}) \\ a_{a} & = H (ℓ ‖ X_{a}) \\ a_{f} & = H (ℓ ‖ X_{f}) \\ X & = a_{a} X_{a} + a_{f} X_{f} \\ R & = R_{a} + R_{f} (= R_{b}) \\ e & = H (R ‖ X ‖ m) \end{aligned}

Bob then tries to construct a unilateral signature following MuSig:

s_{b} = r_{b} + k_{s} e

Let’s assume for now that $k_{s}$ doesn’t need to be Bob’s private key, but that he can derive it using information he knows. For this to be a valid signature, it must verify to $R + e X$ . So therefore:

\begin{aligned} s_{b} G & = R + e X \\ (r_{b} + k_{s} e) G & = R_{b} + e (a_{a} X_{a} + a_{f} X_{f}) & The first term looks good so far \\ = R_{b} + e (a_{a} X_{a} + a_{f} X_{b} - a_{f} X_{a}) \\ = (r_{b} + e a_{a} k_{a} + e a_{f} k_{b} - e a_{f} k_{a}) G & The r terms cancel as before \\ k_{s} e & = e a_{a} k_{a} + e a_{f} k_{b} - e a_{f} k_{a} & But nothing else is going away \\ k_{s} & = a_{a} k_{a} + a_{f} k_{b} - a_{f} k_{a} \end{aligned}

In the previous attack, Bob had all the information he needed on the right-hand side of the analogous calculation. In MuSig, Bob must somehow know Alice’s private key and the faked private key (the terms don’t cancel anymore) in order to create a unilateral signature, and so his cancellation attack is defeated.

Replay Attacks!

It’s critical that a new nonce be chosen for every signing ceremony. The best way to do this is to make use of a cryptographically secure (pseudo-)random number generator (CSPRNG).

But even if this is the case, let’s say an attacker can trick us into signing a new message by “rewinding” the signing ceremony to the point where partial signatures are generated. At this point, the attacker provides a different message, $e^{'} = H (\dots | | m^{'})$ to sign. Not suspecting any foul play, each party calculates their partial signature:

$s_{i}^{'} = r_{i} + a_{i} k_{i} e^{'}$ However, the attacker still has access to the first set of signatures: $s_{i} = r_{i} + a_{i} k_{i} e$ . He now simply subtracts them:

\begin{aligned} s_{i}^{'} - s_{i} & = (r_{i} + a_{i} k_{i} e^{'}) - (r_{i} + a_{i} k_{i} e) \\ = a_{i} k_{i} (e^{'} - e) \\ ∴ k_{i} & = \frac{s_{i}^{'} - s_{i}}{a_{i} (e^{'} - e)} \end{aligned}

Everything on the right-hand side of the final equation is known by the attacker and thus he can trivially extract everybody’s private key. It’s difficult to protect against this kind of attack. One way to is make it difficult (or impossible) to stop and restart signing ceremonies. If a multi-sig ceremony gets interrupted, then you need to start from step one again. This is fairly unergonomic, but until a more robust solution comes along, it may be the best we have!

References

[1] Wikipedia: “RSA (Cryptosystem)” [online]. Available: https://en.wikipedia.org/wiki/RSA_(cryptosystem). Date accessed: 2018‑10‑11.

[2] Wikipedia: “Elliptic Curve Digital Signature Algorithm” [online]. Available: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm. Date accessed: 2018‑10‑11.

[3] Github: “BOLT #8: Encrypted and Authenticated Transport, Lightning RFC” [online]. Available: https://github.com/lightningnetwork/lightning-rfc/blob/master/08-transport.md. Date accessed: 2018‑10‑11.

[4] Wikipedia: “Man in the Middle Attack” [online]. Available: https://en.wikipedia.org/wiki/Man-in-the-middle_attack. Date accessed: 2018‑10‑11.

[5] StackOverflow: “How does a Cryptographically Secure Random Number Generator Work?” [online]. Available: https://stackoverflow.com/questions/2449594/how-does-a-cryptographically-secure-random-number-generator-work. Date accessed: 2018‑10‑11.

[6] Wikipedia: “Cryptographically Secure Pseudorandom Number Generator” [online]. Available: https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator. Date accessed: 2018‑10‑11.

[7] Wikipedia: “Schnorr Signature” [online]. Available: https://en.wikipedia.org/wiki/Schnorr_signature. Date accessed: 2018‑09‑19.

[8] Blockstream: “Key Aggregation for Schnorr Signatures” [online]. Available: https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatures.html. Date accessed: 2018‑09‑19.

[9] G. Maxwell, A. Poelstra, Y. Seurin and P. Wuille, “Simple Schnorr Multi-signatures with Applications to Bitcoin” [online]. Available: https://eprint.iacr.org/2018/068.pdf. Date accessed: 2018‑09‑19.

[10] M. Drijvers, K. Edalatnejad, B. Ford, E. Kiltz, J. Loss, G. Neven and I. Stepanovs, “On the Security of Two-round Multi-signatures”, Cryptology ePrint Archive, Report 2018/417 [online]. Available: https://eprint.iacr.org/2018/417.pdf. Date accessed: 2019‑02‑21.

Introduction to Schnorr Signatures

Explore Topics

Learning paths

Cryptography

Consensus mechanisms

Scaling

Mining

Digital assets

Protocols

Network analysis

Labs

Style guide

Tari

Table of Contents

Overview

Let’s get Started

Basics of Schnorr Signatures

Public and Private Keys

Creating a Signature

Approach Taken

Why do we Need the Nonce?

ECDH

Schnorr Signatures

So why all the Fuss?

Naïve Signature Aggregation

Key Cancellation Attack

Better Approaches to Aggregation

MuSig

MuSig Demonstration

Security Demonstration

Replay Attacks!

References

Contributors

Elliptic Curves

Introduction to Scriptless Scripts

Introduction to Schnorr Signatures

Explore Topics

Learning paths

Cryptography

Consensus mechanisms

Scaling

Mining

Digital assets

Protocols

Network analysis

Labs

Style guide

Tari

Table of Contents

Overview

Let’s get Started

Basics of Schnorr Signatures

Public and Private Keys

Creating a Signature

Approach Taken

Why do we Need the Nonce?

ECDH

Schnorr Signatures

So why all the Fuss?

Naïve Signature Aggregation

Key Cancellation Attack

Better Approaches to Aggregation

MuSig

MuSig Demonstration

Security Demonstration

Replay Attacks!

References

Contributors

Elliptic Curves

Introduction to Scriptless Scripts

You might also be interested in