Number of m-of-n ouputs per transaction

[DeathAndTaxes]

The 0.10 release makes almost all P2SH Script forms standard, opening up possibilities for working around the 520-byte-push limit.

...
Can we safely move the public keys out of the serialized P2SH onto the scriptSig stack?

Interesting.  I need to do some experiments with this.

I was thinking maybe only a single digest could be stored in the redeemscript by combining multiple pubkeys by XOR the next pubkey to the working hash and then hash again.
Digest = H(H(H(a) XOR b) XOR c) ...

On edit: damn I forgot OP_XOR is disabled.

[DeathAndTaxes]

So I was curious how small could the redeemscript for a 20-of-20 be if XOR was not disabled.  Here is an example.  

RedeemScript:  DUP HASH160 2 PICK XOR HASH160 3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
ScriptSig:  0 <Signatures> 3 PubKey1 PubKey2 PubKey3

This is only 3-of-3 but it can be expanded by adding a "n PICK XOR HASH160" just prior to the <Digest>

How small?
RedeemScript size:  4*20 + 24 = 104 bytes (4*n+24)
ScriptSig size: RedeemScript + 20*(74+34)+ 4 = 2,268 (38*n + 74*m + 28)

So up to 11-of-20 could be done standard if XOR was enabled and even 20-of-20 would be only 2,268 bytes.  Of course this is academic because it will take a hard fork to enable the disabled op-codes.  Oh well what a waste.  Any ideas why XOR was disabled?  I can't see it being a security risk especially with pushes already limited in length.

Code:

Stack (signatures removed for brevity)          Script
3 PubKey1 PubKey2 PubKey3			DUP HASH160 2 PICK XOR HASH160 3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 PubKey3		HASH160 2 PICK XOR HASH160 3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash3			2 PICK XOR HASH160 3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash3	3		PICK XOR HASH160 3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash3	PubKey2 	XOR HASH160 3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hxorp2 		HASH160 3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash32 		3 PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash32 3		PICK XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash32 PubKey1	XOR HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hxorp1		HASH160 <Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hash321		<Digest> EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hash321 <Digest>	EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3			3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 3 4			PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 3 3			EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 3			CHECKMULTISIG

[Gavin Andresen]

... I managed to be wrong twice:  I forgot about the AreInputsStandard check for P2SH transactions that makes any transaction with more than 15 signature operations non-standard.

So if you REALLY need a m-of-16-to-20 transaction, use a non-standard raw CHECKMULTISIG, don't bother with Script gymnastics to try to workaround the 520-byte push limit.

[No_2]

This is really interesting, thanks for all this. I think I even managed to understand about 90% of it so thanks for the clear explanations too.

There has been mention of compressed public keys in this thread. What are compressed public keys? Is this still ECDSA encryption but without DER encoding? If so can someone explain what this means?

Why is it stated in some places that scripts need to be below 1,650 bytes and there is also a limit for 520 bytes mentioned for P2SH – can someone explain where these two different constraints come from?

If each signature is 72 bytes and each public key is 34 byes can someone explain to me how this fits into the 15-of-15 limit at 520 bytes, or is this the 1,650 byte limit?

So would a P2SH multisig of 14-of-16 redeem script in a transaction input validate under IsStandard() as true? And therefore be spendable? Because I calculate this to be (14*72)+(16*34) = 1628 bytes under the 1,650 byte limit.

[No_2]

Bump.

Have I understood the P2SH multisig address Public Key and Signature size limitations correctly for input scripts in my last post?

[No_2]

On a related note, I understand that signature order for P2SH or P2PKH multisig is not important. Surely this would mean searching which signatures corresponded to which pub keys would be NP-hard search? Is this a non issue because the search space is limited in size?

I've not been able to find an answer to this online so apologies if it's a replete question.

[amaclin]

On a related note, I understand that signature order for P2SH or P2PKH multisig is not important.

signature order in script is important in msig.
order of signing is not

[No_2]

signature order in script is important in msig.
order of signing is not

So you are saying the signatures have to be entered into the redeeming script in the right order, but this is independent of the order people are signing in?

E.g. redeeming a 2-of-3 multisig transaction can be done in the following way: the second listed signatory (in the output script) signs and places their signature in the second position in the input script on a redeeming transaction. The first listed signatory (in the output script) then signs and places their signature in the first part of the input script on the same redeeming transaction and broadcast this to the network.

[amaclin]

signature order in script is important in msig.
order of signing is not

So you are saying the signatures have to be entered into the redeeming script in the right order, but this is independent of the order people are signing in?

E.g. redeeming a 2-of-3 multisig transaction can be done in the following way: the second listed signatory (in the output script) signs and places their signature in the second position in the input script on a redeeming transaction. The first listed signatory (in the output script) then signs and places their signature in the first part of the input script on the same redeeming transaction and broadcast this to the network.

Let us take an example
https://blockchain.info/tx/792c6999daeb47901cfdc546091c839a59b36787523af65a999dd2675c631109?show_adv=true
this transaction has one input
the redeem script is ( I've put linebreaks for readability )
52
2102931593c439ec55f4ac4451b46f17ae757f174bfeb02ea4c61442ee2317f2d7ce
2102c12eca0e168f8a400a70596810a12258ce47541510d7c20fa89e4c960464f85b
2103f9484c51127f8a308bca12552d9698d0c0f9d8807a1402b15b53643b0ece1900 53 ae


so, this is 2-of-3 multisig
Alice has private key AAA and her public key is  2102931593c439ec55f4ac4451b46f17ae757f174bfeb02ea4c61442ee2317f2d7ce
Bob has private key BBB and his public key is 2102c12eca0e168f8a400a70596810a12258ce47541510d7c20fa89e4c960464f85b
Charley has private key CCC and his public key is 2103f9484c51127f8a308bca12552d9698d0c0f9d8807a1402b15b53643b0ece1900

two of these three can redeem the address 3FekZqHj2VGz96nGGgoaXh76QStxbgQQzq

We have exact two signatures in this transaction
SIG1 = 3045022100bdaa107c18b4a43d853ff3c2cbf2a329c036942218ca9e52c1342829cccd017f02201 98d0c06bbf4b4a4ea01ff543515bdc0419f895c077fff5652d58de7a6c7ea3f01
SIG2 = 3045022100cb0f6863db278bc5fc99061ed7c9a87d5c7c5a67e291c8090c03051cb3c2f79b02207 df4862b6fa5a9f3cd23ca9cbdb72b22ab47e47019b3c5d10694e40d757378d901


I do not have a program to validate these signatures right now, but I can say that
SIG1 does not belong to Charley
SIG2 does not belong to Alice
because the order of signatures does matter

It is possible to determime who was those two (Alice + Bob or Alice + Charley or Bob + Charley) who signed this transaction
But it is not possible to determine the who signed yesterday and who signed today