Scaling Bitcoin: Schnorr Signatures

Published in

Bitcoin Tech Talk

8 min readMay 22, 2018

Schnorr Signatures are an exciting innovation that can help scale on-chain transactions and improve privacy and security of participants. The majority of the work is spearheaded by Pieter Wuille (Blockstream) a more detailed explanation of it can be found here. Most of this articles information is derived from that article and this video by Pieter Wuille.

Some prior knowledge of Private and Public Key Elliptic Curve Cryptography is assumed.

Why

On-chain transaction size is reduced
Faster validation for each transaction
Improved privacy for participants of a Multi-Signature wallet
Can lead to and help other scaling solutions

Background on Signatures, UTXOs and Multi-Sigs

Bitcoin uses a UTXO (Unspent Transaction Output) model using ECDSA (Elliptic Curve Digital Signature Algorithm) to prove ownership of Bitcoin
By providing a signature, a user can remove an encumbrance(scriptPubKey aka a Locking Script) and the UTXO can be used as input in a transaction

Multi-sigs (Multi Signature Addresses) use a M-of-N scheme, meaning any combination of valid signatures within N will unlock the UTXO by requiring a threshold of M number of valid signatures
In order to prove ownership of a UTXO of a Multi-Sig, the scriptSig (aka an Unlocking Script), would have to contain M number of ECDSA signatures

Elliptic Curve Digital Signature Algorithm

Each ECDSA signature is DER formatted, 65 bytes in length. The size of scriptSigs (Unlocking Scripts) grows linearly according to M number of signatures. This obviously bloats the size of transactions when dealing with Multi-Sigs
If we take a P2PKH (Pay to Pub Key Hash) transaction that uses 1 input and assigns 1 output and uses a compressed public key, the size of the transaction would be approximately 183 bytes

Transaction: P2PKH := 
{
    version (4 bytes)           + 
    number of inputs (1 byte)   + 
    prev hash input (32 bytes)  + 
    prev index input (4 bytes)  + 
    scriptSig (100 bytes)       + 
    sequence (4 bytes)          + 
    number of outputs (1 byte)  + 
    value of outputs (8 bytes)  + 
    scriptPubKey (25 bytes)     + 
    locktime (4 bytes)
}Size := 183 bytes

The issue of Multi-Sig transaction size becomes apparent when we breakdown the size of transactions of an M-of-N implementation, for example a 3 of 4 Multi-Sig
Lets look at an example P2SH (Multi-Sig) transaction. The transaction unlocks 1 input and assigns 1 output

Multi-Sig Transaction: P2SH (3 of 4) := 
{
    version (4 bytes)           +
    number of inputs (1 byte)   +
    prev hash input (32 bytes)  +
    prev index input (4 bytes)  +
    scriptSig (305 bytes)       +
    sequence (4 bytes)          +
    number of outputs (1 byte)  +
    value of outputs (8 bytes)  +
    scriptPubKey (23 bytes)     +
    locktime (4 bytes)          +
}Size := 386 bytes

The size of a Multi-Sig transaction would be 386 bytes, double the amount of a P2PKH transaction
The size of the scriptSig would grow linearly according to the number of participants in the Multi-Sig
Schnorr Signatures provide a solution to reduce the size of on-chain transactions and by reducing M number of signatures to one signature

Schnorr Signatures

Schnorr signatures aggregates multiple signatures into one signature
This means that our previous 3 of 4 scriptSig held 3 different DER formatted signatures (according to each participant)
Using Schnorr Signatures, the unlocking script would simply have 1 signature representing an aggregate of each participants signature

How Schnorr Signatures work

m = Message
x = Private key
G = Generator point
X = Public key (X = x*G, public key = private key * generator point)(R, s) = Signature (R is the x co-ordinate of a random value after multiplying by the generator point, s is the signature)H(x, y, z..) = Cryptographic Hashing function* Capitalised letters are usually points on an Elliptic curve (except the Hashing function)* Lower cased letters are usually scalars====================================================================
Schnorr Signatures
====================================================================
Signature creation:
(R, s) = (r*G, r + H(X, R, m) * x)* r is a random nonceR = random nonce * generator point (becomes a point on the Elliptic Curve)s = random nonce + Hash function(Users Public Key, Random point on Elliptic Curve, the message (transaction)) * Private Key
 Signature verification:
s*G = R + H(X,R,m) * X* Verification is a linear equation, both sides of the equation must be satisfied for the signature to be validsignature * generator point = Random Point on Elliptic Curve + Hashing function(Public Key, Random Point on Elliptic Curve, message (transaction)) * Public Key

Naive implementation of Schnorr Signatures

Using the algorithms above to generate signatures and verify them, we will want to aggregate multiple signatures into one signature

====================================================================
Naive Schnorr Signatures
====================================================================Signature creation:
X = the summation of each Public Key Point 
* X = (Xi + (Xi+1) + (Xi+2)...)R = the summation of each participants random nonce 
* R = (Ri + (Ri+1) + (Ri+2)...)s = the summation of each participants signature 
* si = ri + H(X,R,m) * X 
* s = (si + (si+1) + (si+2)...)(R, s) = is the signature with s being the summation of all signaturesSignature verification:
s*G = R + H(X,R,m) * X * X represents the summation of all participants Public Keys

The signature is an aggregation of all signatures but there is a security problem with this approach known as Rogue Key Attacks

Rogue Key Attacks

The naive implementation of aggregating Schnorr Signatures expose an attack vector where a participant could claim a false Public Key, and control the Multi-Sig

Rogue Key Attack:* Alice and Bob want to create a 2-of-2 Multi-Sig* Alice has a key pair of (xA, XA) (Private Key, Public Key)
* Bob has a key pair of   (xB, XB) (Private Key, Public Key)* We can assume that XAB (Aggregated Public Key) = XA + XB* Bob sends a false Public Key: XBf = XB - XA* This is important because the Aggregated Key (XAB) that emerges from using Bob's false Public Key is actually equal to Bob's true key XB* Other users may think they are sending to a 2-of-2 controlled by Alice and Bob but it's simply an address controlled by Bob's true Public KeyAn extremely simplistic example:
XA (Alice's Public Key) = 10
XBt (Bob's true Public Key) = 11XBf (Bob's false Public Key) = XBt(11) - XA(10) = 1XAB = XA(10) + XBf(1) = 11* Bob has attacked the Aggregated Public Key, by sending a false key which after aggregation with other keys, equals his true Public Key* Bob now controls the Multi-Sig

The problem with participants in an Aggregated Signature scheme is that each participant would need to prove to others, that their Public Key is valid according to a Signature produced by its corresponding Private Key
This reduces the problem back to on-chain proof for each participant generating a Signature to validate the authenticity of a Public Key, losing the scaling and efficiency benefits

Bellare-Neven

The Bellare-Neven scheme addresses the security issue of Rogue Key Attacks
Allows aggregation of signatures

====================================================================
Bellare-Neven
====================================================================Signature creation:
L = H(Xi + (Xi+1)...) 
* L is the hash of the summation of all Public KeysR = (ri * G) + ((ri+1) * G)...
* R is the summation of each participants Random Point
* They share their Random Nonce Points with other signerssi = ri + H(L, Xi, R, m) * xi
* si is the signature generated for each participant
* si = random nonce + Hash(Hash of all Public Keys, Participants Public Key, Sum of all Random Points, message (transaction)) * Participants Private Keys = (si) + (si+1) + (si+2)...
* s is the summation of each participants signature* (R, s) is the final signatureSignature verification:
s*G = R + H(L,X1,R,m) * X1 + H(L,X2,R,m) * X2 +...* Verification is a linear equation, both sides of the equation must be satisfied for the signature to be valid* sum of participants signatures * generator point = sum of Random Nonce Points + Hash(Sum of all Public Keys, Participant 1’s Public Key, Sum of Random Nonce Points, message (transaction)) * Participants 1’s Public Key... same is repeated for each participant

A draw back of BN is that in-order to verify a Multi-sig, we will still need to present the Public Key of each Participant

Mu-sig

Using Mu-sig we are able to aggregate the Signatures and the Public Keys
Instead of verifying a signature according to each participants Public Key, Mu-sig will allow one Public Key to be used in verification
The validator will not need multiple Public Keys to validate a signature and it will hide that the signature is derived from multiple Private Keys

====================================================================
Mu-sig
====================================================================Signature creation:
L = H(Xi + (Xi+1)...)
* L is the hashed summation of all Public Keys X = ( (H(L, Xi) * Xi) + (H(L, Xi+1) * Xi+1)...)
* X is the sum of all Hashed Public Keys + Participants Public Key- Hash(Sum of all Public Keys hashed, Participant 1's Public Key) * Participant 1’s Public KeyR = (ri * G) + ((ri+1) * G)...
* R is the summation of each participants Random Point
* They share their Random Nonce Points with other signerssi = ri + H(X, R, m) * H(L, X) * xi
* si is the signature generated for each participant
* si = random nonce + Hash(X, Sum of all Participant's Random Points, message (transaction)) * Hash(Hashed sum of all Public Keys, X) * Participant's Private Keys = (si) + (si+1) + (si+2)...
* s is the summation of each participants signature* (R, s) is the final signatureSignature verification:
s*G = R + H(X, R, m) * X* Verification is a linear equation, both sides of the equation must be satisfied for the signature to be valid* sum of participants signatures * generator point = sum of Random Nonce Points + Hash(X, sum of Random Nonce Points, message (transaction)) * X

Mu-sig achieves signature validation without having to present each Public Key, instead we use X as the sum of each Participants Public Keys — meaning Multi-Sig validation would occur on chain with one Signature
We can reduce on-chain size transactions by aggregating signatures and Public Keys
Mu-sig seems to be the current and up to date implementation of Schnorr Signatures and it seems a BIP is currently in the works