Today, i'm going to talk about the
multi-signature scheme (P2SH) in Bitcoin.
Many sources on the internet explain how to use the multi-signature scheme in the Bitcoin Core Client. However, there appears to be a lack of understanding or at least an explanation about what is actually happening under the hood. So much so that I bet many developers could tell you exactly how to create and sign using a multi-signature scheme, but would not be able to tell you what the new Bitcoin address represents.
What is a multi-signature scheme?
Remember, in Bitcoin, everyone has a Bitcoin address - which is essentially the hash of an ECDSA public key. This means for every Bitcoin address - there is a single ECDSA public/private key pair. (Public key is given to people and the private key is kept secret to sign documents)
This scheme takes a twist on threshold cryptography - this new Bitcoin Address is associated with more than one public key. To spend any bitcoins using this new address - you would need to provide signatures that are associated with more than one public key - that is where we get the name "multi-signature" - as one or more signatures is required!
Let's make this
a little bit more concrete before we continue.
The user will create "n" public keys. Let's say the user creates 3 public keys - A,B,C.
The user will also have "m" private keys - associated with each public key - a,b,c.
So now, we have potentially three Bitcoin addresses, (A,a) (B,b) (C,c).
However, we want to create a single Bitcoin address Z that requires at least two signatures to spend any bitcoins.
We call this a 'multisig' address that requires 2 signatures from 3 public keys. I could provide any combination of signatures ab, bc, ac to spend the coins. The important note - is that I do not require ALL three private keys to spend them. I may not even hold all three keys - each key could be given to a separate party (me, arbitrator, merchant).
The reason we use 'm' and 'n' - is because the combination is flexible - you could have a single Bitcoin address Z that is created using up to 20 public keys - but only require 5 private keys to spend it.
How does all this look in the Bitcoin world?
Well - as I mentioned earlier - a Bitcoin address is typically the hash of an ECDSA public key. However, in this case, the Bitcoin address will be the hash of a script... but what is a script?
OP_m <pubKey1> ... <pubKeyN> OP_n OP_CHECKMULTISIG
OP_m -
specifies the number of signatures required from the public keys in this script to authorise a payment.
<pubKey1> ... <pubKeyN> -
list of public keys that will be associated with this new Bitcoin address
OP_n -
specifies the total number of public keys associated with this new Bitcoin address
OP_CHECKMULTISIG -
Anchor to inform the Bitcoin Client what to do! (Check that the signatures provided match the public keys provided in the script).
In our trivial example:
2 A B C 3 OP_CHECKMULTISIG
As you can see - it matches the scripts conditions.
Now - how does this become a Bitcoin address?
The script is concatenated and hashed using SHA256 followed by RIPEMD-160. Let's call it H(script) for now. Then, we concatenate a byte to specify the type of address and a 4-byte checksum before encoding it using base58.
Lets call this magic art of concatenation and encoding - our multi-sig address Z.
Encode using base58: [one-byte version]||[20-byte hash = H(Script)]||[4-byte checksum]
Now that I have my multisig address Z - how does someone send me money?
It's slightly different than with the traditional Bitcoin address. To send money to your multisig address - the sender will require a slightly different scriptPubKey in their transaction output:
scriptPubKey: OP_HASH160 H(Script) OP_EQUAL
In this case,
the sender will use your H(script) as part of the transaction and
NOT Z. Remember, Bitcoin addresses are just for our understanding as humans - the protocol does not need to use an explicit Bitcoin address. In this case, H(script) is extracted from Z and placed inside the transaction (remember, the 20-byte hash in the multisig address is H(script)).
Someone has sent me money - how do I spend it?
As normal - your transaction will contain a scriptSig. Infact, the word 'scriptSig' makes more sense for the multi-signature scheme than it does for the traditional signature scheme. I say this because you are providing the script that specifies the conditions for spending the bitcoin (the pre-image of H(Script)) AND the signatures that are relevant for the script! (As such, script and sig are included, so scriptSig).
So in our trivial example, we will provide two signatures for the private keys a,b.
scriptSig: sig(a) sig(b) 2 A B C 3 OP_CHECKMULTISIG
Remember, we sign the hash of the transaction - H(T) - before any signatures have been included in the transaction! Someday I'll write a piece that talks in detail about what exactly is signed.
As you can see - it is the responsibility of the spender to specify the script that is used to redeem the bitcoins. That is why
we call the script the redeemScript. So in essence, the scriptsig requires:
scriptSig: ..signatures... <redeemScript>
The fact the spender reveals the redeemScript is useful - the ECDSA public keys are kept secret until the time our bitcoins will be spent. The H(Script) is a commitment to our multisig address and it is assumed in the security of cryptographic hash functions - that it is extremely unlikely that a second pre-image of H(Script) could be found, such that the signatures are not required to spend the bitcoins. (Remember, the scriptPubKey is only seeking a pre-image of H(Script) to be valid, but the pre-image is tied to the script, and this script must be processed to be valid before we consider if the scriptPubKey is valid as well).
Conclusion
I hope you have found this article useful in understanding what is happening under the hood with the multi-signature scheme. All I want you to understand is that the multi-signature scheme requires one or more signatures for a single Bitcoin address and in the end - it is still using single ECDSA public/private key pairs - it is simply, a set of ECDSA public/private key pairs. It is NOT using anything like Shamir's secret - where a single ECDSA private key is fragmented and the fragments are required to produce a single signature.
References:
Multi-sig encoding: http://bitcoin.stackexchange.com/questions/26872/what-cryptographic-operations-are-performed-on-the-3-public-keys-to-produce-a-mu
SHA256 then RIPEMD160: https://en.bitcoin.it/wiki/Script
P2SH: https://en.bitcoin.it/wiki/Transactions
