Enable m-of-n signatures as standard transaction type(s).
This is only a proposal for expansion of IsStandard. This will allow experimentation with and implementation of multi-signature transactions.
@coblee @gavinandresen
See parent gist.
-
Wallet backup: master offline/secure key in case 'working' wallet is lost (1-of-2 signatures)
-
Wallet security: require off-device confirmation and signing (2-of-2 signatures)
-
Escrow/dispute resolution (2-of-3 signatures)
-
Long term lock funds, requiring signatures from 2 officers of a company to disburse
(2 of n) -
Short term lock funds, with 2-factor authentication to disburse and an additional 2 of n backup in case one of the factors is lost
(2-of-2 OR 2-of-n)* * "Escrow" with the the two parties having to agree or one of two backup observers helping in case of disagreement(2-of-2 OR 2-of-3 OR 2-of-3) -
An options contract where the outcome is triggered by a key being broadcast:
(Ks AND K1) OR (Kr AND K2)- s gets control of funds if K1 is broadcast, r gets control if K2 is broadcast.
I'm assuming deep knowledge of how bitcoin creates and verifies transaction outputs and inputs.
See:
- https://en.bitcoin.it/wiki/Transactions
- https://en.bitcoin.it/wiki/Script
- https://en.bitcoin.it/wiki/Contracts
"Funder" : the funder creates the ScriptPubKey that requires m-of-n signatures to spend
"Redeemer" : the redeemer gathers the necessary signatures and spends the m-of-n ScriptPubKey by filling in a matching ScriptSig
Must not split the blockchain-- so must use existing, enabled opcodes.
Must not rely on unproven cryptographic algorithms or techniques
-
Protocol/method for acquiring signatures
-
RPC calls to support above use cases
-
Wallet format
-
New bitcoin address format(s) for funders, if any
I'd like to address all of these in separate proposals, to keep discussion focused on just the very-low-level mechanism. To roll these features out smoothly we need to enable them as standard transactions a release or two BEFORE we make them available to end-users or web services so they will get relayed and included into blocks.
Bitcoin currently supports two standard transaction script templates. This transaction type is used for coin-generation and the obsolete send-via-ip:
ScriptSig: sig
ScriptPubKey: public_key CHECKSIG
This is the more common "send to bitcoin address":
ScriptSig: sig public_key
ScriptPubKey: DUP OP_HASH160 160-bit-bitcoin-address EQUALVERIFY CHECKSIG
The advantage to the second template is that funders only need the 20-byte bitcoin address, and not the 65-byte full public key.
The new multisign transaction type will have an m-of-n ScriptPubKey of the following form (2-of-3 example):
0
OVER 2SWAP CHECKSIG SWAP HASH160 {pk1hash} EQUAL BOOLAND ADD
OVER 2SWAP CHECKSIG SWAP HASH160 {pk2hash} EQUAL BOOLAND ADD
OVER 2SWAP CHECKSIG SWAP HASH160 {pk3hash} EQUAL BOOLAND ADD
2 GREATERTHANOREQUAL
ScriptSig in this case would be sig1 pk1 sig2 pk2 sig3 pk3 where some of the signatures and the matching pubkey can be zero.
Each branch may specify a pubkey instead of a pubkey hash (second pubkey specified explicitly in this example):
0
OVER 2SWAP CHECKSIG SWAP HASH160 {pk1hash} EQUAL BOOLAND ADD
SWAP {pk2} CHECKSIG ADD
OVER 2SWAP CHECKSIG SWAP HASH160 {pk3hash} EQUAL BOOLAND ADD
2 GREATERTHANOREQUAL
In this case ScriptSig would be sig1 pk1 sig2 sig3 pk3.
m-of-n scripts can be combined into m-of-n OR p-of-q:
NOTIF {m-of-n script}
ELSE {p-of-q script}
ENDIF
In this case ScriptSig would be 0 [m-of-n script] or 1 [p-of-q script].
For sanity purposes, limit n to 5 and the number of combined m-of-n scripts to 4. This implies a maximum number of sigops per output to 20, although the maximum actual number of sigops executed will be 5.
- The HASH160 version saves on transaction size for the
m-of-n OR p-of-qversion because the pubkey for one of the branches will never have to be recorded in the blockchain.
It has been proposed that allowing multiple sigops per script opens the network to a denial of service attack through malicious transactions that use up more CPU. However, the density of sigops per transaction KB is less than one in 28 bytes. This is only 20% more than the existing transaction types. If the 20% amount is a concern, we could require a padding of 6 bytes per sigop.
The user may supply more signatures than the minimum required to evaluate the script to true. However, this is not a new issue because the users are already able to create more inputs and outputs than they really need. If we want to discourage overuse of sigops, we will need to charge transactions fees per sigop, including for existing transaction types.
Aren't the scripts above complex? I believe most people familiar with the bitcoin scripting engine will be able to quickly evaluate the script format and review the corresponding IsStandard code for correctness. It seems better to spend some extra effort now for a general solution rather than creating multiple special cases that will have to be maintained indefinitely.
Why not use CHECKMULTISIG?
- It counts as 20 sigops for the DOS check. That brings the maximum txouts using CHECKMULTISIG per block to 1000. With a change output, that's only a max of 500 transactions.
- If we want to allow the HASH160 form, it doesn't make the script any shorter
Most recent update is last.
-
Switch to IF/ELSE version, explain why CHECKMULTISIG is not helpful
-
Clarified that this is an IsStandard expansion proposal
-
Spell out ScriptSigs
Why not use CHECKMULTISIG for the m-of-n ?
The farthest I'd want to generalize to start is:
(m-of-n) OR (p-of-q)
... with p and q <= 3.
I'm thinking exactly 2 new standard transactions will take care of the vast majority of multisig use cases:
m of n : just the plain-old CHECKMULTISIG
(m of n) OR (p of q)
And I'd rather implement the second using a plain IF / ELSE instead of the more generic TOALTSTACK/1SUB sequence, just because it means fewer opcodes used (which I could imagine possibly being important if a cryptographer ever tackles proving that bitcoin scripts are secure).