A brief intro to Bitcoin Schnorr Multi-signatures

TL;DR: Schnorr signatures are the hottest subject in Bitcoin; We release a Rust open-source implementation of MultiSig Schnorr.

It seems like Schnorr signatures are all the rage in the cryptocurrency community, and announced to be the biggest thing since sliced bread (or at least SegWit).

In this blog post we will explain one of the main advantages of Schnorr signatures’: its native support for Multi-Signatures (MultiSig). Since MultiSig is one of the most important mechanisms available for users to protect their account against the theft of their private key and given the high number of such hacks, it’s clear why this subject gets so much attention from the cryptocurrency community.

We will describe the mathematics behind Schnorr MultiSig in a layman’s terms. On top of that, we will share an open-source implementation of Schnorr MultiSig.

MultiSig

“Multisignature (often called multisig) is a form of technology used to add additional security for cryptocurrency transactions. Multisignature addresses require another user or users sign a transaction before it can be broadcast onto the blockchain.” https://en.wikipedia.org/wiki/Multisignature

Currently, most of blockchains implement this multiple locking mechanism with actual multiple signatures and some scripting or smart contract to verify that indeed everything is signed. However this design has a few drawbacks:

• Security: Scripting is prone to errors. In Ethereum, Parity’s MultiSig contact suffered from two different vulnerabilities, resulting more than $100M losses.
• Efficiency: Having multiple explicit signature bloats the size of the transactions and the fees that are associated with them.
• Privacy: Explicit multiple signatures gives away the fact that this address is MultiSig, and may garner unnecessary attention to it.

Schnorr signatures (named after Claus Schnorr, whose mathematical work laid the foundations for this signature) solve all these problems as they allow to aggregate multiple signatures and their corresponding keys into a single one. As a result, Schnorr MultiSig transactions are indistinguishable from regular (“MonoSig”) transactions and therefore does not impact privacy or transaction size and fees. The MultiSig verification is done in the cryptography layer and not in the scripting layer, which eliminates the security concerns scripting bugs.

The main difference between Schnorr signatures and Bitcoin current signatures (ECDSA) is that Schnorr signatures are Linear, while ECDSA signatures are not.

The most relevant property of linearity for our purpose, is that when you add two (or more) Schnorr signatures together, the result is a valid Schnorr signature too!

When adding two line equation together, y1=a1*X + b1 , y2=a2*X + b2 the result is another line equation y3= y1+y2= (a1+a2)* X + (b1+b2), where the new slope a3= (a1 + a2) and the new y-intercept is b3 = (b1+b2). This is practically the same for Schnorr signatures.

Adding the red and blue lines creates the green line (created with Desmos)

We will use Stepan’s excellent post formulation to explain:

Schnorr signatures use a point R and a scalar s. Similar to ECDSA, R is a random point on elliptic curve (R = k×G). Second part of the signature is calculated slightly differently: s = k + hash(P,R,m) ⋅ x. Here x is your private key, P = x×G is your public key, m is the message. Then one can verify this signature by checking that s×G = R + hash(P,R,m)×P.

In the basic MultiSig scenario, we have 2 parties, each has its own key pair.

With Schnorr signatures we can use a pair of private keys (x1,x2) and generate a shared signature corresponding to a shared public key P=P1+P2=x1×G+x2×G. To generate this signature each party need to choose a random number (k1,k2), generate a random point Ri=ki×G, add them up to calculate a common hash(P,R1+R2,m) and then get s1 and s2 from every party (si = ki + hash(P,R,m) ⋅ xi). By adding up these signatures and using the a pair (R, s) = (R1+R2, s1+s2) as their (multi-)signature for the shared public key P.

A word of caution: the algorithm described above is too naïve and it needs to be harden in order sustain real world attacks.

Luckily, some cryptography experts did just that. One of the most current papers on the matter is a work led by the Blockstream team called “Simple Schnorr Multi-Signatures with Applications to Bitcoin”.

One of the authors of this work, Pieter Wuillie, had created a Bitcoin Improvement Proposal (BIP), bip-schnorr, which is a fairly technical proposal on how to standardize Schnorr signatures as part of bitcoin.

Schnorr MultiSig Open Source Project

To support the community and encourage the adoption of Schnorr MultiSig we (mostly Omer Shlomovits & Gary Benattar) , created a project for experimenting with Schnorr MultiSigs, based on the aforementioned article and BIP.

KZen-networks/multisig-schnorr_multisig-schnorr - This project is a Rust implementation of multi-party Schnorr signatures over elliptic curves._github.com

The project is implemented in Rust for performance and security. it currently supports Bitcoin’s elliptic curve (secp256k1) and can be used for :

1. Key generation
2. Simple schnorr signing based on the BIP specifications.
3. Creating multi-signature for n participants.
4. Verify signature based on the BIP specification which is the same for one or more signers.

Examples for all the above can be founds in the test file. We also included a wiki page that explains the protocol in a step by step manner.

We hope that you will experiment with this project and even consider contributing to it. After all, it can help upgrading cryptocurrencies security, by helping users better protect the keys for their account, which is one of cryptocurrencies’ biggest problems and limits their wider adoption.