Signature Verification & Multi-Signatures

This post follows from my last post, “How does ECDSA work in Bitcoin”.

A quick recap on the math behind ECDSA:

• You can combine finite fields with elliptic curves and still maintain the group law allowing you to perform the necessary math to create a ‘one way equation’
• The math includes point addition and point multiplication allowing us to perform scalar multiplication
• The scalar multiplication from one point to another point is ‘easy’ to compute, but working backwards is ‘hard’
• The key equation: P = xG where P is the public key, x is the private key and G is the public generator point. You can see how it is ‘easy’ to calculate the public key by performing scalar multiplication around the generator point G when you know the private key, x, but it is ‘hard’ to calculate the private key, x, when you only know the public key P and public generator point G.

ECDSA:

The power of ECDSA is being able to prove that a received piece of data can only have come from the person who has the private key to the used public key. Said another way, the owner of the private key can easily produce valid signatures, and everyone else can easily verify the signature with the public key created from that private key without ever knowing the private key.

The formal math behind signing and verifying with ECDSA can be found here, but the basic algorithm is as follows assuming a cyclic group T, prime order p, and generator point G of T:

Signature —

1. Select a private/public key pair (P, x) where P= xG
2. Choose random nonce r
3. Calculate R = rG
4. Choose your message z
5. Calculate s = (z + Rx) / r
6. Signature = (R, s)

Verification —

1. Given signature (R, s)
2. Calculate u = z / s
3. Calculate v = R / s
4. Verify that rG = uG + vP

The ECDSA signature works great. Unfortunately, it uses field division, which is computationally difficult, and its use for multi-signatures requires signature and verification of each participant in the multi-signature transaction.

Schnorr Signatures:

Schnorr signatures were first created by CP Schnorr in 1989. He went on to patent the signature algorithm. The patent expired in 2008, which is probably why Satoshi went with ECDSA instead of Schnorr. Schnorr signature algorithm eliminates the computationally costly field division of ECDSA and replaces it with hashing. The full mathematical proof can be found here.

Signature —

1. Select a private/public key pair (P, x) where P= xG
2. Choose random nonce r
3. Calculate R = rG
4. Choose your message z
5. Calculate a new variable c = H(P, R, z)
6. Calculate s = r + cx
7. Signature = (R, s)

Verification —

1. Given signature (R, s)
2. Valid if sG = R + cP where c = H(P, R, z)

Multi-signature Schemes

In a recent post, Pieter Wuille succinctly describes multi-signature schemes:

A multi-signature scheme is a combination of a signing and verification algorithm, where multiple signers (each with their own private/public key) jointly sign a single message, resulting in a single signature. This single signature can then be verified by anyone who also knows the message and the public keys of the signers. Note that in the context of Bitcoin, the term “multisig” usually refers to a k-of-n policy, where k can be different from n. In the cryptographic literature, multi-signatures really only refers to n-of-n policies, though we can easily construct k-of-n on top of n-of-n.

As mentioned before, multi-signatures for ECDSA are easy, but not efficient and have no privacy for those involved for a multi-signature transaction; every participant’s public key is exposed.

Schnorr changes the game for multi-signatures. Schnorr allows native multi-signature because of its use of a hashing algorithm instead of field division. The same math above works for a group of n participants in a transaction, each with their own private/public key pair. There are only a few changes to the signature equation above:

1. X = summation of each individual participants public key, P.
2. Each individual chooses their own unique r and calculates their own unique R = rG and R(sum) is the summation of all R.
3. Each individual now must calculate their own s = r + cx and s(sum) is the summation of all s.
4. The signature is now the summation of all unique R and all unique s giving a signature (R(sum), s(sum)).
5. Verification is the same as a single transaction except you replace P with summation of all P, X.

Valid if s(sum)G = R(sum) + cX where c = H(X, R, z)

The verification of Schnorr multi-signatures is the same as a single Schnorr signature replacing P with X, therefore verification does not require knowledge of individual public keys, just the aggregate public key.

Now you can see why Schnorr has a native multi-signature feature. To verify the signature algorithm you just take ONE signature (R(sum), s(sum)). There is no way to know whether that signature is from one individual or many individuals. It looks the same. This feature is known as signature aggregation.

Unfortunately, there is an easy attack on the Schnorr multi-signature scheme. Again, I’ll let Pieter Wuille explain.

Alice has a key pair (xA,XA) and Bob has (xB,XB). However, nothing prevents Bob from claiming his public key is XB’ = XB — XA. If he does so, others will assume that XA + XB’ is the aggregated key that Alice and Bob need to cooperate in order to sign for. Unfortunately, that sum is equal to XB, and Bob can clearly sign for this by himself.

This means we need to find a solution that allows us to continue using signature aggregation but eliminates this attack.

Bellare-Neven

Bellare-Neven (BN) signature algorithm was proposed to stop this attack from happening. It is an adaptation of the Schnorr signature where a new variable is introduced, L, the hash of the set of each individual’s Public key, P. Now our algorithm becomes the following:

Signature —

1. L = H(set of each individuals Public key P)
2. Each individual chooses their own unique r and calculates their own unique R = rG and R(sum) is the summation of every participant’s R.
3. Each individual now must calculate their own s = r + cx, but this time c = H(L, R, P, z) and s(sum) is the summation of every participant’s s.
4. The signature (R(sum), s(sum)) is now the summation of all unique R and all unique s

Verification —

1. Given signature (R(sum), s(sum))
2. Valid if s(sum)G = R(sum) + cP for every participant where c = H(L, P, R(sum), z)

While BN eliminates the attack introduced by multi-signatures using Schnorr signatures, it just reintroduced the problem that ECDSA had; you need to know every participant’s public key again. Now we have lost the privacy gains that we achieved with Schnorr signatures, so BN won’t quite work.

MuSig

Greg Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille came up with a solution to keep signature aggregation while eliminating the attack that naive Schnorr signatures introduced. They called it MuSig and it builds off of both Schnorr and BN.

Signature —

1. L = H(set of each individual’s Public key P).
2. Now we have X = summation of every participants H(L,P)P.
3. Each individual chooses their own unique r and calculates their own unique R = rG and R(sum) is the summation of all R.
4. c also changes from BN equation. c = H(X, R(sum), z)*a. A new variable ‘a’ is introduced where each participant uses their unique public key to calculate a = H(L, P). So, c = H(X, R(sum), z)H(L, P).
5. Each individual now must calculate their own s = r + cx and s(sum) is the summation of all s.
6. The signature (R(sum), s(sum)) is now the summation of all unique R and all unique s.

Verification —

1. Given signature (R(sum), s(sum))
2. Valid if s(sum)G = R(sum) + cX where c = H(X, R, z).

We have reintroduced signature aggregation because the verification algorithm does not require individual participant’s public key, P, but instead only requires the summation of all P, X. This means that a single signature transaction will look the exact same as a multi-signature transaction to nodes. This gives a much greater increase in privacy.

But, even further, MuSig has introduced key aggregation that eliminates the vulnerability of generalized Schnorr signatures. Since X is now the summation of the Hash of L and their public key, P, multiplied by P, we now only need one public key for multi signature transactions. Nodes won’t be able to see the various public keys P that make up the value of X.

Conclusion

MuSig leads to native and private multi-signature transactions with both signature aggregation — only one (R, s) signature — and key aggregation — only one X to represent the group’s ‘public key’ — in order to create and verify transactions.

The benefits of MuSig are numerous:

1. Signature data for multi-signature transactions can be large and cumbersome. MuSig will allow users to create more complex transactions without burdening the network and revealing compromising information.
2. More efficient than single ECDSA transactions today, so that should make it easier for new and existing nodes.
3. This also means it should create more space in each block and therefore lower transaction fees.
4. Incentivizes the use of other privacy tools like coinjoin.

Looking forward to seeing this implemented!

Here are more resources that I used to write this post:

• Jimmy Song’s videos like this one.
• Spencer Bogart’s post here.
• Pieter Wuille and Blockstream’s post here.
• The academic paper mentioned above.
• Bitcoin Core blog post on Schnorr Signatures.