We've implemented the MuSig aggregate signature scheme (developed by Blocksteam) in BCHD. In this post we'll explain what it is, how to use it, and how we might use this in BCH in the future.
Last May we activated Schnorr signatures on the Bitcoin Cash network. Schnorr signatures have a unique property in that you can create a m of m multisig address that looks indistinguishable from a standard Pay-to-Pubkey-Hash address.
To understand this consider that Schnorr allows you to add public keys together:
AggregatePubkey = AlicePubkey + BobPubkey
The funds can simply be sent to an address built from the aggregate public key and then when Alice and Bob want to release the funds they each create a signature using their key and just add the R and s values from their signatures together to produce an aggregate signature. This aggregate signature is valid for the AggregatePubkey.
The problem with the scheme above is it can be insecure if done improperly. Consider if Alice generates her public key and sends it to Bob, then Bob can set his public key to:
BobPubkey = BobPubkey - AlicePubkey
Then when the keys are added together you get:
AggregatePubkey = AlicePubkey - AlicePubkey + BobPubkey
Which just equals BobPubkey and would allow Bob to spend the funds by himself.
To get around this problem you have to add more rounds of communication between Alice and Bob where both parties first share the hashes of their public keys and then the public keys themselves. Likewise they have to also share hash commitments for the Rvalues in their signatures before revealing the actual values themselves.
Last year Mark Lundeberg, Checksum0, and I made a 3 of 3 Schnorr multisig transaction using this scheme.
However, the MuSig construction allows users to drop the initial public key commitment round and just share the public keys directly. This makes the scheme easier to use and requires less rounds of communication between parties.
You can find an example in Go here.
Unfortunately we still need to share R commitments because there's a theoretical attack that Bob can do where if he can chose the message to be signed and has access to the Alice's R pubkey he can forge an aggregate signature in something like 2^32 operations depending on the number of signatures Alice made.
Towards 1 signature per transaction
What we would love to do with this is use the MuSig to move Bitcoin Cash from using one signature per input to one signature per transaction.
If we used the naive signature aggregation scheme that I mentioned above to aggregate signatures across inputs we would make it possible for anyone to spend anyone else's coins. However, MuSig prevents this by nature of how the aggregate public key is constructed.
Consider how a current signature script looks:
<signature <sighash>> <pubkey>
The signature is appended with a one byte sighash flag which tells the interpreter how to hash the transaction.
One way we could do this would be to introduce a new sighash flag ― SigHashAggregate. When using this flag the signature script would look like:
<sighashAggregate> <pubkey>
So the signature data push would contain only one byte which would be the new sighash flag. The OP_CHECKSIG and OP_CHECKMULTISIG opcodes would then have to return true to the stack without actually validating any signatures.
The major change this causes is the interpreter would then need to not only return whether or not the script was valid but it would also need to return any public keys that need to be aggregated and validated using the transaction's aggregate signature. This is a major change to the script dynamics because right now each input is validated independently of all other inputs. This change would mean that is no longer the case and the transaction needs to be validated as a whole.
Once the interpreter returns all the public keys, we aggregate them using the MuSig algorithm, then validate the aggregate signature using the aggregate public key against a hash of the entire transaction (minus the aggregate signature).
Where Do We Put The Signature?
In my opinion it would be ideal to just add an extra field into the transaction:
The downside of doing this is it would change how the transaction ID is calculated (because there's an extra field) and any wallets that calculate transaction ID based off raw transactions would need to upgrade to know how to calculate the new ID.
But then if we're changing the transaction format why don't we throw in everything plus the kitchen sink into the new format? This could easily get complicated and difficult to get consensus for in a hurry.
Alternatively we could just stick the aggregate signature in the first input. It would be backwards compatible but a very hacky solution.
Benchmarks
Obviously the big win here would be smaller transactions, less bandwidth usage and less storage. In other words, we can pack more transactions into a block of the same size.
But what about CPU usage?
Musig requires point multiplication when calculating the aggregate public key so it isn't per se faster. It depends on the number of signatures in the transaction.
My benchmarks showed MuSig was something like 15% slower for a 2 input transaction and 8% slower for a 3 input transaction. However, 4 input transactions and up are faster to validate using MuSig. The gains increase as the number of inputs increase.
I scanned through the last few weeks of blocks in the chain and for transactions which had more than one input, the average was exactly 4. So this would suggest widespread use of MuSig would result in a small to modest improvement in CPU usage.
What do you think?
Like. Useful.