A Bitcoin upgrade known as taproot was recently approved and is due to go live in November 2021. While this brings several new features, one is the introduction of Schnorr signatures to replace ECDSA that has been used by Bitcoin since it was created in 2009. These are both methods of creating and verifying digital signatures that, from the outside, are very similar and play the same role. However, Schnorr signatures do have several benefits, both theoretically and practically. The feature that I will discuss here is the ability to combine multiple public keys and signatures into a single one via a process referred to as MuSig. This will be a high level discussion, without going into technical details of the implementation.
Recall the general process of creating signatures that was discussed previously. First, Alice creates a public/private key pair. The private key (or secret key) sk is chosen randomly, so that it virtually impossible for anyone to guess its value, and Alice must protect this and ensure that it is kept secret. The public key PK is shared freely, so that it can be used by any third party as part of the validation process. Next, suppose that Alice has a message that she wants to authorise. In the case of Bitcoin, the ‘message’ is a transaction spending her coins. Alice uses her private key sk together with the message in the signing algorithm to produce the digital signature. This is then distributed publicly along with the original message. Finally, any third party in possession of the public key PK can apply the verify algorithm to this signed message to determine that it was indeed authorised by Alice. If the verification algorithm outputs True, then it is valid, otherwise if it outputs False, then it is invalid. This is as in figure 1 below, where the third party or validator called Val performs the verification step. The important feature of the whole process is that only someone in possession of Alice’s private key is able to create a valid signature.
Next, consider multi-signatures. One situation is where Alice wants to generate multiple public and private keys for additional security. Now, authorisation requires a signature corresponding to each one of the public keys. Then, for an attacker to authorise messages on her behalf and spend her coins, they would need to gain access to all of the corresponding private keys. Alternatively, we could have joint custody of an account by, say, three people, Alice, Bob and Carol. They each choose their own public/private key pair and distribute the public keys, while each keeping their private key secret. Given a message, then authorisation requires all three of Alice, Bob and Carol sign. This is as in figure 2 below. The multi-signed message consists of the original message together with all of Alice, Bob and Carol’s signatures.
In order to verify that the signed message has been authorised by the custodians, the validator needs all of the following. First, she needs all three of Alice, Bob and Carol’s public keys. Next, she needs the message which is distributed along with all of Alice, Bob and Carol’s signatures. Val then applies the verify algorithim three times, once for each public key and signature and, finally, determines that the multi-signed message is valid if all three signatures are valid.
This works fine, and is the standard way of securing an account by multiple signatures. So long as they keep their private keys secure, each of the Alice, Bob and Carol can be sure that no-one is able to fool the validators into verifying the message without their consent. There are some issues though. First, instead of having to distribute a single public key and a single signature, they need to distribute three keys and three signatures. As these keys and, particularly, the signatures, can be quite long, having three of them can significantly increase the amount of data that needs to be distributed. This is particularly an issue for signing Bitcoin transactions where space on the blockchain comes at a cost. Next, it is requiring the validator to perform extra work and validate three separate signatures rather than just the one. Finally, it requires using a separate representation from the single signature case, so that the validator knows that it is a multi-signature account and that they have to perform the verify procedure on each signature.
Key and signature aggregation, such as is provided by the MuSig algorithm, completely solves these issues. At the first step, Alice, Bob and Carol each randomly select a private key as before and use these construct their public keys, in a process called ‘keygen’ in figure 4 below. They keep their private keys skA, skB, skB secret including, importantly, from each other. However, they communicate between each other in order to aggregate their public keys into a single combined public key PK. From the outside, this combined key looks exactly the same as a single signature public key, and is distributed freely in exactly the same way. Next, suppose that Alice, Bob and Carol create a message (i.e., a transaction) that they want to validate. As in the multi-sig approach described above, they can each sign the message using their private keys. However, they now also communicate between each other in order to do this signing in a consistent way and to combine their individual signatures into a single signature which, from the outside, looks exactly the same as those produced for a simple single signature account. This is as shown in figure 4.
The combined signature is distributed along with the message. The validator, Val, now just takes the message, signature and public key PK and applies the verify procedure in exactly the same was as for a single sig message, as depicted in figure 1 above. In fact, as there is no difference, she does not even know that there are multiple signatories. All of the communication between Alice, Bob, and Carol, required to combine their public keys and signatures occurs only between themselves, and is not transmitted to the blockchain or anywhere else. As far as Val is concerned, she is just validating one signature using the associated public key. This addresses the issues mentioned above for the basic multisig approach.
- Less data needs to be transmitted than with traditional multisig methods. Only one public key and one signature is required to be stored on the blockchain, leading to smaller and cheaper transactions.
- The validation process is simpler, requiring a single application of the verify procedure, rather than one for each signatory.
- No special code or support is required for this multisig approach, since the verification is exactly the same as for a single signature.
- There is some additional security or privacy, since it is not possible to tell from the transaction data, including public keys and signatures, whether a given transaction on the blockchain is single signature or multi-signature.
It should be noted that this method of combining signatures is not part of the protocol. In fact, regardless of the digital signature algorithm, only the verification procedure is fixed by the protocol. All that the signatories are required to do is to create a signature, by whatever means, that the verify algorithm will determine is valid. If you can come up with a signature and key combining method for the existing ECDSA implementation, then that could be used just as well. However, the difference with Schnorr signatures is that such a method, called MuSig, is known, whereas none is known that works for the ECDSA signature verification.
For a multisig method to be secure, each one of the signatories has to be confident that no-one else can create a valid signature without their input. That is, in the description above, Alice should know that, as long as she keeps her private key secure, it is impossible to correctly sign a message without her authorisation. She cannot rely on Bob and Carol keeping their private keys secure and, in fact, cannot assume that the other two are trustworthy at all. Even if Bob and Carol were conspiring in an attempt to steal money by signing transactions without Alice’s consent, then Alice should be able to trust the algorithm that they cannot do this. For the simple multisig in which the transaction requires each one of their signatures, then it is secure. A transaction is not valid unless it includes Alice’s signature, requiring use of her private key, which she has not communicated to anyone else.
For key aggregation methods, security is not so obvious. For example, Alice, Bob and Carol could combine public keys simply by adding them together and, for a linear method such as with Schnorr, this corresponds to adding together their private keys. This may sound reasonable and, as long as Alice chooses her private key at random and independently of the others, then the sum of the keys should also be random (even given the information of Bob and Carol’s private keys). However, the fact that they need to share public keys means that the private keys are not necessarily independent. For example, Carol could start by choosing a private key at random and compute the corresponding public key. Then, when Alice and Bob transmit their public keys to her in the key aggregation stage, she just subtracts these from her initial public key, and communicates this modified key to the others for the aggregation. The resulting sum of these public keys would give Carol’s initial public key back, so that she would be able to sign transactions and messages without input from either of the other parties. This weakness can be avoided by, for example, requiring Alice, Bob and Carol to first share a hash of their public keys before sharing the keys themselves. Due to the ease with which such vulnerabilities can creep into proposed key aggregation methods, the existence of a mathematical proof of security is important.
Note that in figure 4, I include an arrow suggesting that the private keys can be aggregated into a single key sk. While this is possible, it should not actually be applied. Each of Alice, Bob and Carol should keep their private keys secret to themselves, so no algorithm can be applied which requires all three of these. Furthermore, anyone in possession of sk would be able to sign messages whereas, the idea of the scheme is that it requires all three signatories to produce a valid signature. So, sk should not actually be computed. It is only included for theoretical reasons. The idea is that as long as the public key corresponds to some private key, and that the aggregated signatures correspond to this same private key, then the method works and the signatures will be valid. Furthermore, if Alice chooses her private key, and she is able to argue that this results in a combined key sk that is entirely random from Bob and Carol’s perspective, even given the information shared between them, then it is impossible for Bob and Carol, or anyone else, to produce a valid signature without her input. This reduces arguments and proofs of the security of the key aggregation method to that of the basic single signature algorithm.
So far, I have only discussed multisig approaches requiring each one of the signatories to be available for the signing process. In the case of the Alice, Bob and Carol examples discussed, this is a 3 of 3 multisig. However, what about 2 of 3, where any two of the signatories are sufficient? Or, m of n? What about more complex setups with different conditions for spending coins in an account? In answer, the additional features introduced to Bitcoin with the taproot upgrade help here, and allow the MuSig method to form the basis of more complex contracts. I do not go into details on taproot in this post but, in the same way that we can combine multiple public keys into one, we can also aggregate the key with additional binary information. In particular, in taproot, the public key can be combined with a hash of an alternative script specifying how coins can be spent, or even the merkle root of a whole array of alternative scripts. In combination with key aggregation, this opens up the following possibilities.
- m of n multisig: Consider 2 of 3 multisig, where any two of Alice, Bob and Carol are required to sign a transaction. There will usually be an expected way in which signing will occur. For example, Alice and Bob will sign but, in the event that either of these cannot be contacted, Carol will fill their place as the second signatory. Then, we would create an aggregated ‘2 of 2’ public key where Alice and Bob can sign transactions. However, we would also create additional scripts where Alice and Carol, or Bob and Carol, can sign. In the event that Carol is required, one of these alternative scripts would be used. This would mean transmitting the additional script along with the signatures, requiring some additional space on the Blockchain and increasing transaction costs. As long as Alice and Bob are available to sign, the expected 2 of 2 multisig is used, which will be efficient and not require transmission of alternative scripts.
- Smart contracts: A smart contract will generally involve multiple parties which, as in the rest of this post, I assume to be Alice, Bob and Carol. There will then be a set of conditions, or clauses, under which the different parties are able to spend the coins. For example, maybe Alice and Bob can jointly claim the coins as long they do this within a set time period, otherwise Carol can claim. This could be done by a Bitcoin script, although creating a long script covering all features of the contract would take up a lot of space on the blockchain. The alternative approach, using taproot, is to split these up into separate scripts with one for each way in which the coins can be spent. Only the script corresponding to the clause in the contract that is being applied needs to be submitted when spending the coins, reducing the transaction size. However, the important point is that, so long as all parties agree to a transaction, they should be able to validate it without any explicit recourse to the contract itself. In reality, the script describing the contract is only there to enforce compliance. We therefore lock up the coins using a 3 of 3 aggregated MuSig method, with the expected method being that all of Alice, Bob and Carol sign when the coins are spent. Only in the event that there is a dispute, or when one of the parties cannot be contacted, do the hardcoded alternative scripts need to be used. This has the advantage that smart contracts on the Bitcoin blockchain are indistinguishable from standard single-signature accounts, except when there is a dispute or, for whatever reason, the contract needs to be explicitly enforced on-chain.
Zero Knowledge 