After much fruitful discussion and evolution, this proposal is now a series of "Bitcoin Improvement Proposals" -- see BIP 11, 12 and 13: https://en.bitcoin.it/wiki/Bitcoin_Improvement_Proposals
Sincere thanks to everybody who contributed improvements, ideas and code.
I like the idea of using a general case to keep things simple. Easier to read and less room for error. That's worth the extra bytes.
But maybe we can optimize it just one bit (save 3 opcodes) since we know n is at least 2.
General case for m-of-n:
ScritpSig: sig1 pubkey1 sig2 pubkey2 ... sigN pubkeyN
....any sig/pubkey pair may be a placeholder (e.g. OP_0 OP_0)
ScriptPubKey:
TUCK CHECKSIG SWAP HASH160 {pkhash} EQUAL BOOLAND
OVER 2SWAP CHECKSIG SWAP HASH160 {pkhash} EQUAL BOOLAND ADD // n-1 times
m GREATERTHANOREQUAL
(1 and 2) or 3:
ScritpSig: sig1 pubkey1 sig2 pubkey2 sig3 pubkey3
....any sig/pubkey pair may be a placeholder (e.g. OP_0 OP_0)
ScriptPubKey:
TUCK CHECKSIG SWAP HASH160 {pk3hash} EQUAL BOOLAND DUP ADD // If sig3/pubkey3 checks out, then this evaluates to 2
OVER 2SWAP CHECKSIG SWAP HASH160 {pk2hash} EQUAL BOOLAND ADD
OVER 2SWAP CHECKSIG SWAP HASH160 {pk1hash} EQUAL BOOLAND ADD
2 GREATERTHANOREQUAL
I like the idea of using highly optimized special-cased scripts for the most common cases.
And I think the optimized versions are much easier to read; they mostly look like the existing single-sig DUP HASH160. I don't see any advantage to generalizing.
Gavin,
I have to side with coblee here. It's easier to maintain a general case than an expanding set of special cases. It also reduces the effort for third party tools (blockexplorer, android wallet).
Updated proposal; I think we would regret prior proposals, because ECDSA signature verification is NOT cheap, and prior proposals would have resulted in potentially lots of extra unnecessary signature verifications.
I'm taking the approach of redeemer puts exactly the right number of signatures in ScriptSig, along with a number that indicates of which case is being satisfied.
Improvements and suggestions are, as always, most welcome.
case 2 and 4 is effectively pointless, it's like a shitty lock, there's no point adding OR in the m-of-n mutli-sign. there only needs to be type 3 with extensions and type 5, ([1..n]) OR Z which is essentially type 3 with a master key.
I like this updated proposal.
I don't like these scripts.
For the 1-of-3 case, if I do "sig 3", the only reason why it fails is because 3 is not true. It seems problematic that we are not actually checking anything if you pass in an invalid number and the only reason why it fails is because you will never end up with a 1 on the top of the stack when it's done due to a side effect of our scripts. That just seems like a bad idea.
Oh wait, I know why this feels wrong. It's because it's busted.
This should satisfy the 1-of-3 case: "1 3"
Since 3 doesn't satisfy any of the IFs, you will end up with "1" on the stack and "3" on the alt stack.
Putting the pass/fail value on the alt stack should work:
ScriptSig: siga 0 or ScriptSig: sigb 1 or ScriptSig: sigc 2
ScriptPubKey:
0 TOALTSTACK
DUP 0 EQUAL IF DROP pubkeya CHECKSIG TOALTSTACK 0 ENDIF
DUP 1 EQUAL IF DROP pubkeyb CHECKSIG TOALTSTACK 1 ENDIF
DUP 2 EQUAL IF DROP pubkeyc CHECKSIG TOALTSTACK 2 ENDIF
FROMALTSTACK
Not sure if the first line "0 TOALTSTACK" is needed. What happens if we call FROMALTSTACK with nothing on the stack? Does the transaction fail? If so, then we don't need to push the initial 0 onto the alt stack.
We could also generalize it and save a opcode per line by using 1SUB:
ScriptSig: siga 0 or ScriptSig: sigb 1 or ScriptSig: sigc 2
ScriptPubKey:
0 TOALTSTACK
DUP NOTIF DROP pubkeya CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DUP NOTIF DROP pubkeyb CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DUP NOTIF DROP pubkeyc CHECKSIG TOALTSTACK 0 ENDIF 1SUB
FROMALTSTACK
I still like the previous more generalized solution. Here's a change to make it only do checksig when needed:
ScritpSig: sig1 sig2 sig3
....any unused sig should be OP_0 to avoid unnecessary CHECKSIGs
ScriptPubKey:
0
SWAP DUP NOTIF DROP ELSE pubkey CHECKSIG ADD ENDIF // n times
m GREATERTHANOREQUAL
Basically if the sig is 0, we just drop it. Otherwise, we do the checksig and add 1 to the total if sig checks out.
To save an extra opcode, we could do this: (but it's a bit more complicated)
0
SWAP DUP 0NOTEQUAL NOTIF pubkey CHECKSIG ENDIF ADD // n times
m GREATERTHANOREQUAL
And this is the case if the sender only has the pubkey hashes and the redeemer needs to provide the pubkeys:
ScritpSig: sig1 pubkey1 sig2 pubkey2 sig3 pubkey3
....any unused sig/pubkey pair should be "OP_0 OP_0" to avoid unnecessary CHECKSIGs and HASH160s
ScriptPubKey:
0
OVER 2SWAP NOTIF DROP ELSE OVER CHECKSIG SWAP HASH160 pubkeyhash EQUAL BOOLAND ENDIF ADD // n times
m GREATERTHANOREQUAL
Nice catch RE: what happens if all the if's fail-- I like the 1SUB solution, I'll check to see what FROMALTSTACK does if there is nothing on the alt stack (pretty sure that causes the script to fail), and will update the proposal to use that.
Regarding "just put OP_0" on the stack and they won't get checked" : I'm worried about an attacker trying, on purpose, to cause a node to waste CPU cycles doing unneeded signature checks.
A combination of the previous solution and the DUP NOTIF ... ENDIF 1SUB would work. The advantage of the previous solution is efficiently representing things like 2-of-4. With @gavinandresen's current proposal it would take 12 clauses. The advantage of the current proposal's DUP NOTIF is that only one branch is evaluated.
script.cpp already optimizes the sig = 0 case. If CPU becomes an issue, an extension of the current anti-DOS mechanism could be implemented where a component of the tx fee is proportional to the number of non-0 sigs in the scriptSig.
Wouldn't nodes just drop transactions that aren't valid? So an attacker won't be able to do much damage since those transactions would not propagate. We could even do more checking such that if any of the checksigs fail, we fail the transaction. So the attacker can't send a transaction with 2 bad signatures and 1 good one.
0
SWAP DUP 0NOTEQUAL NOTIF pubkey CHECKSIGVERIFY 1 ENDIF ADD // n times
m GREATERTHANOREQUAL
In terms of opcodes, it's about the same. But the general case can handle complicated requirements much better. You don't need to handle every possible case and the redeemer does not really need to know which case he satisfies.
For example, the "(a and b) or c" case:
0
SWAP DUP 0NOTEQUAL NOTIF pubkeyc CHECKSIGVERIFY 2 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeyb CHECKSIGVERIFY 1 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeya CHECKSIGVERIFY 1 ENDIF ADD
2 GREATERTHANOREQUAL
The current proposed 2-of-3 case is complicated. The redeemer needs to know which case he's satisfying. How would this information be stored in the wallet?
DUP NOTIF DROP pubkeyb CHECKSIGVERIFY pubkeya CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DUP NOTIF DROP pubkeyc CHECKSIGVERIFY pubkeyb CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DUP NOTIF DROP pubkeyc CHECKSIGVERIFY pubkeya CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DROP FROMALTSTACK
My proposed general 2-of-3 case is much simpler and uses less opcodes. The redeemer just needs to know, for example, that he has keya and keyc. So he just does "keya OP_0 keyc" to redeem. He does not need to know that his transaction actually satisfies the 3rd case.
0
SWAP DUP 0NOTEQUAL NOTIF pubkeyc CHECKSIGVERIFY 1 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeyb CHECKSIGVERIFY 1 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeya CHECKSIGVERIFY 1 ENDIF ADD
2 GREATERTHANOREQUAL
If you are still not convinced, think of what the 3-of-5 case will look like for both.
To answer the problem of unwieldy listing of all possible combinations for m-of-n under the current proposal, consider using a modified form of the current proposal that would handle a disjunctive list of m-of-n cases. (m1-of-n1) OR (m2-of-n2) OR (m3-of-n3)
@casey-bowman - agreed, that's what I was trying to say
@coblee - you can't do 0NOTEQUAL on something that can be a signature because a signature cannot be casted to a CBigNum. The script will throw an exception and fail. Just do:
0
SWAP pubkeyc CHECKSIG ADD
SWAP pubkeyb CHECKSIG ADD
SWAP pubkeya CHECKSIG ADD
2 GREATERTHANOREQUAL
script.cpp doesn't actually run the heavy computational stuff when the input is zero.
I agree that "checking more signatures than needed" is not an attack mode, because the concept of "needed" is ill-defined. I could create a valid 5-of-5 transaction just for kicks even if I have no need for 5 signatures on it. The only way to get people to use what they need is to charge proportional transaction fees. That will be up to miners at some future point when CPU usage becomes an issue.
Miners can figure out the cost of evaluating the various scripts proposed here without executing them. Even with the version that doesn't use IF/ENDIF, we can figure out the cost of execution by counting the number of non-zero signatures in scriptSig. If we can figure out the cost of execution we can charge accordingly. Once miners start charging, it would incentivise users to just fill in the minimal number of signatures to evaluate to true.
A bad case would be when we can't efficiently figure out the real number of sig ops, but none of the proposals here have that property.
@Mesmer : good idea.
All: So I feel like we started wandering down a path, looking for a way to combine hashed signatures together. We ran into a dead end, so we started wandering through the forest looking for second-best solutions, learned a lot, but eventually got lost among the trees.
Mesmer's comment seems right to me: why not just do m-of-n OR master-key ?
If we need to, maybe in the future we could expand to a second: m-of-n OR p-of-q, which would also be simple. We could even do that now (m-of-n OR master key is the same as m-of-n OR 1-of-1)....
I've forked this gist and wrote up my latest proposal here: https://gist.github.com/dba89537d352d591eb36 . Input is very welcome.
Groffer's above proposal has the advantage of being much more general than the ad-hoc constructions specified here.
Gavin says "optimizing for size is worthwhile, even if that means more work for implementors"
More work for implementors means delay in implementation and more volume for bugs as optimised cases are added in future.
Gavin says "Users will pay for extra bytes in transactions via transaction fees over and over again".
Then change the fees to reflect the real costs and incentives. Transactions and the block chain are already take significantly more bytes than necessary but it's not considered a problem. Currently the concern is the number of verifications. In this case change the fees to reflect the worst-case number of verifications to spend the transaction.
I've implemented initial support for these in the hopes of including relaying/block inclusion in the 0.5 release:
Supporting these doesn't cut off support for the more general transactions in the future.
@gavinandresen, why not @groffer's proposal? It as simple, more powerful, and I have yet to see a clearly articulated position against it.
@maaku: simpler? Compare my patches against groffer's, or write out an (a and b) or c transaction using both proposals. I disagree that groffer's is simpler; maybe simpler conceptually, but much more complicated to implement and (more importantly) test.
As I said, supporting 3 simple transaction types for wallet security and backup does NOT preclude also supporting more general m-of-n cases in the future.
@gavinandresen: I meant simpler in terms for future maintenance, support, and extensions, since that will be an on-going, continuous effort whereas the implementation need only be written once.
Regardless, the real issue is one of community trust. You opened with a proposal for new m-of-n transactions types. A significant segment of the community responded that this is actually a special case of a more general need. Besides @groffer's work on an alternative proposal, there has been significant discussion on the forums about what kinds of things generalized m-of-n transactions would allow, and the discussion was not confined to the usual group of commentators. However without reaching consensus for or against, you go ahead and implement your own proposal and pull it into 0.5. The downside? Now I, @groffer, or anyone else who supported his proposal really don't feel motivated to put effort into any of your proposals in the future (not that I contributed much to this one, but I was still new to bitcoin-dev).
That's now how a community project is or should be run, and one need only look to successful community projects like Python or Django to see the difference.
Thanks for the feedback. I'm pushing this hard because I want much better wallet security and backup sooner rather than later.
There is no groffer proposal to pull (I think gmaxwell might take a shot at implementing the 2-of-3 case), and I don't see how to implement wallet security and backup on top of the fully-generic transactions (I'm probably just being dense).
Also, again: this isn't "either-or".
Please consider including the 2-of-3 case. This would enable simple escrow - buyer, seller, arbiter.
Oh, I just saw your comment just now after submitting my own. Great!
Btw, @gavinandresen, I forgot to say thanks for all your hard work :)
EDIT: for some reason the reply I sent by my phone (prior to your last comment) didn't post to github. Here it is:
Like most things, this could have been avoided with better communication. The following would have done nicely:
"Support for this minimum feature set is needed for 0.5's improved security features. The security of the whole network is improved by adding these transactions immediately. Support for generalized m-of-n transactions will be added as soon as a consensus is reached, but we deemed it necessary to split the process into two stages so as to get these new security features out the door ASAP."
FYI, for the future.
I can update my pull to implement the latest version of the generalized proposal within two weeks. I have not been motivated to do so because of the issues that @maaku raises. If such a pull will be seriously considered I can go ahead.
I don't see the problem with wallet security/backup on top of the generalized case. To get the a AND b OR c case, just use 2-of-2 OR 1-of-1.
Two weeks will be too late for the 0.5 release, and you'll need to split your PULL into two parts (just the IsStandard() changes and then another pull that adds RPC commands to generate the transactions; the IsStandard part has to be released first so users don't start generating might-take-days-to-confirm transactions).
I'm surprised you feel like all of this isn't being "seriously considered" given the amount of discussion and back-and-forth.
@gavinandresen - I feel that there is a reluctance to accept substantial contributions from the community. As @maaku I am also concerned about community trust and I think the success of bitcoin project depends on that and good communication. A decision was made even though the balance of arguments seemed in favor of the generalized solution.
As to code complexity, the IsStandard part of pull #319 is very simple - https://github.com/bitcoin/bitcoin/pull/319/files - wallet.cpp line 1125 to 1179. The only other part is a refactoring of Solver in script.cpp that is generally useful. Extending this to multiple OR clauses will be only a few more lines of code.
To keep things simple and avoid special cases in the ScriptSig, consider using the form of the 2-of-3 ScriptSig for all cases, including the case (a AND b) OR c.
ScritpSig: sig1 pubkey1 sig2 pubkey2 sig3 pubkey3 ... sigN pubkeyN
....any sig/pubkey pair may be a placeholder (e.g. OP_0 OP_0)
coblee's general case for ScriptPubKey works for all the m-of-n cases, and a variation of it would work for (a AND B) OR c and similar cases.