Bitcoin Forum

How many m-of-n contracts can exsist as outputs for a transaction?

For example can I have a 3BTC input and spend 1BTC to a 2-of-3, 1BTC to a 5-of-5 and 1BTC to a 7-of-11 on the same contract transaction?

Or can only 1 m-of-n exsist per transaction?

Its no different to a normal transactions limits on the number of vouts. They wouldn't be on the same contract. Each vout is separate to the rest.

Whysis you think it would be different?

I should have been clearer:

Thanks, this is what I thought would be the case. I understand there is a byte limit, but not sure if this is a 'hard limit', or just tends to incur fees as I also understand that there are fees (by consensus) associated with transactions over a certain byte size. E.g. if you create a transaction that aggregates many small inputs and this takes up a lot of data on the blockchain then it incurs a fee.

So, assuming the inputs are always more than or equal to the outputs, my questions are:

1. It is possible to have multiple m-of-n contracts as outputs for a transaction? From what I understand this should be possible but costly due to the bytes required to script the transaction.

2. Is there a size above which a miner (by consensus) will not mine a transaction to a block? You mention the number of bytes that are allowed? Is there a hard limit here or does the fee just increase above a certain byte size in relation to how many extra bytes are required to write the transaction to the blockchain?

3. I have been told that their is a hard limit of 20-of-20 for any given contract, as per the source code in version 0.8. I have also now read that their is a limit of 16-of-16 which is true? Or is it more complicated than that?

If you are sending to P2SH addresses then your initial transaction works just like normal. The usual size, fees and dust limits apply. This is because the P2SH addresses are just regular addresses other than the fact they are a hash of a script instead of the hash of a public key.

Where things can get trickier is in redeeming any of those outputs in subsequent transactions. As stated earlier, the redemption script for a 7-of-11 might be too large.

This is a critical point.  P2SH makes things easier.  For someone to send you funds you can just provide an address.  The outputs are also smaller (as the output just contains a fixed 32 byte script which contains the hash of the redeemScript).  However P2SH is a double edged sword.  It can make it more difficult for you to spend funds you receive if you create scripts which are non-standard and worse you can even created scripts which are invalid which the network can't verify until funds have already been 'locked up' at that address. See note at the bottom on testing and risk of losing of funds.

'Sending' funds TO a P2SH address
P2SH hash is in the output of the tx
You can have a nearly unlimited number of P2SH addresses as outputs
The output is a fixed length hash of the script.
Actual script not "known" to the network, only "normal" tx validation applies.  
The tx is not significantly different than a "normal" tx.  Instead of putting a hash of the pubkey in the output you are putting a hash of the script in the output.

'Spending' funds FROM a P2SH address
The redeemScript which hashes to the hash in the unspent output's PkScript is added to the ScriptSig portion of the 'spending' transaction's input.
In tx validation the script is hashed and compared to script hash in the prior tx's unspent output.
If that validates then the ScriptSig is validated normally.
The validation rules for scripts apply (see below).  Actually they apply for all scripts but a "normal" (P2PkH script can't exceed the limit).

This is where I think you may still be confused.  With P2SH, an n of m address is simply the HASH of the script.   3 of 3 keys, 7 of 11 keys, 15 of 15 keys, any other arbitrary script.  Instead of the conditions for spending the output being in the output just a hash of that script it placed in the output.  So the direct answer is yes; the size of the script doesn't matter as the output contains a fixed sized hash of the script not the script itself.  However pushes are limited to 520 bytes and since the whole redeemScript needs to be pushed to the stack to validate it's hash any address produced from the hash of a script larger than 520 bytes is effectively unspendable (without a hardfork).

Once again it is important to distinguish funding TO a P2SH address and spending FROM a P2SH address.

For funding a P2SH address (i.e. sending value to the P2SH address, the hash of the script is on the output side of the tx) in all but the most extreme edge cases there are no constraints.   Transactions have no hard size limit (other than they will need to fit in a 1MB block).  To be relayed by most nodes the tx will need to pass IsStandard which limits you to "only" 100KB but with the output being only ~40 bytes you could have thousands of such outputs.  

Now SPENDING FROM a P2SH address is a little more complex as there are restrictions on what scripts are valid and/or standard.   Also see the note at the end about the risk of losing funds due to delayed script validation.  

A tx is invalid if any of the following are true

• Block Size is >1,000 KB (this is a block level check but obviously a tx which can't fit into a block <=1MB could never be confirmed at least not until the 1MB limit is raised).
• A script is >10KB (this is per script so tx can be larger if it contains multiple scripts each less than 10KB).
• The size of the value being pushed in a script is >520 bytes (effectively limits P2SH scripts to 520 bytes as the redeemScript is pushed to the stack).
• The script contains more than 201 operations (excluding pushes).  OP_CHECKMULTISIG with m keys is considered m operations for the purpose of this check.
• The number of keys (n) for a OP_CHECKMULTISIG operation is > 20
• The number of signatures (m) for a OP_CHECKMULTISIG operation is > than number of keys (n)

Your script generation code should validate the script against all validation rules to avoid an "oh shit" moment.  See the warning about loss of funds at the bottom and be sure you understand how the 'delayed validation' of P2SH scripts makes it easier to lose funds.  This doesn't make P2SH bad but it does give you enough rope to hang yourself.  The bolded limitation is the easiest to violate.  Since redeemScripts are pushed to the stack in P2SH input validation the entire script must be less than 520 bytes.  Always do a hard check on the length of your redeemScript.  Don't trust any rule of thumbs.  For example a m-of-15 multisig script is <520 bytes if all keys are uncompressed however if your code accidentally generated one or more uncompressed keys you have now violated the 520 byte limit and created an address which is unspendable.

If the tx is valid but not standard it won't be relayed by most (virtually all) nodes and won't be included in a block by most miners.  To get it confirmed you will need to bypass the peer to peer network and push the transaction directly to a miner who accepts non-standard transactions.  There is no "miner discovery" mechanism in the protocol so you will need to manually check with each miner.   Also the miner may not accept any non-standard txn and may have specific fee requirements so this should only be done if you absolutely can't accomplish the task with standard transactions.  If the transaction is standard it will be relayed automatically by nodes and included in consideration for the next block by most miners so special handling is needed.

A transaction is not standard if any of the following are true

• The tx size > 100KB
• The scriptSig size is > 500 now 1650 bytes.
• The value of any output is less than the dust threshold (5,460 now 546 satoshis).
• The tx is low priority and doesn't include the minimum fee to relay (10,000 now 1,000 satoshis).**
• The tx is not final (nLockTime block has not been created yet).***
• The tx version is greater than the current version (which is 1).
• For 'native' multisig, the number of keys is > 3.
• For P2SH transactions, the number of SigOps is > 15.

** Technically this doesn't make the txn non-standard but even if standard the txn won't be relayed by most nodes if it has insufficient fee or priority so it may help to just consider it part of the IsStandard check.

*** The txn itself is only considered non-standard not invalid but if you include a nlocktime txn with a future nlocktime in a block then the block is invalid.

Note:  It is possible to lose funds with P2SH so extensive testing on testnet is strongly recommended.  The risk comes from the fact that the network is unaware of the script contents at the time the funds are "sent" to the P2SH address.   For a simplistic example create an otherwise valid Bitcoin script which is greater than 10KB in size.  Generate a P2SH address from the hash of the script.  Make a payment to the P2SH address.   The tx sending funds to the P2SH address will validated and be processed by the network without issue.  However any attempt to "spend" the coins sent to the P2SH address will fail as the only valid method of "redeeming" the output is the script and the script breaks the 10KB validation rule.  Those funds can never be spent (or at least can't be spent until the 10KB limit is raised or removed).

That isn't true. If you read the code, the limit is with the size of sigScript if you are using P2SH:


Signatures are of length 72 bytes and public keys are of length 33 bytes (if compacted) so 4 of 6 is about the limit. I've managed 3 of 4 and it passed as a standard transaction.

Looks like you are right.

Actually I believe it is 10 bytes in encoding (DER) + 32 bytes for r, s, x, and y ea.
So for compressed keys the ScriptSig (r, s, x and encoding) is 106 bytes.
For uncompressed keys the ScriptSig (r, s, x, y, and encoding) is 138 bytes.

FLOOR(500 / 106) = 4
FLOOR(500 / 138) = 3

Because with multisignature you have to put all the possible public keys into the transaction even if they aren't used to sign it. So 4 of 6 requires 4 signatures and 6 public keys.

This 500 byte limit is in IsStandardTx() check. You can still get your 10-of-20 multisig transaction included in block if your really need it.

Doh.  Of Course. :)

So as long as all 4 keys are compressed then it would look like 4 of 6 meets IsStandard.
4*72 + 6*34 = 492 bytes < 500 bytes

However if any of the keys are uncompressed then it is limited to 3 of 4 keys.
3*72 + 4*66 = 480 bytes < 500 bytes.

I used 34/66 bytes as I believe (going from memory here) the encoding used in tx for the PubKey contains one byte for the length.  Thanks I learned something today.

Actually there is a more restrictive check on the actual script so the max is 3 of 3 (for IsStandard) even if the size is under 500 bytes.
https://github.com/bitcoin/bitcoin/blob/ae7e5d7cebd9466d0c095233c9273e72e88fede1/src/script.cpp#L1414
Only applies to native multisig not P2SH.

That is correct, you also need to add an extra byte to the signature as well technically! The DER encoding is really unnecessary. I'm doing a refactor of bitcoin to get rid of some of these stupid extra bytes.

Well at the same time any altcoin should probably make a few other changes.
1 ) Move signature outside the input (i.e. header, inputs, outputs, signature)
2 ) Make hash for signature the entire tx (forced immutability)
3 ) Enforce a restricted canonical signature (r < half order)
4 ) Always require compressed keys (simplifies encoding, key export, signature verification, etc)
5 ) Use pubkey regeneration to remove the need for pubkeys in the tx input
6 ) Remove edge case tx types (like pay to PubKey vs pay to PubKeyHash)
7 ) Remove unnecessary DER encoding from the blockchain.  Purpose of DER is to allow a standardized format for sharing signatures between applications.  Bitcoin clients don't need that capability.
8 ) Make tx fees explicit.  A nice safety check against malformed txs at the expense of a few bytes (far less than what is saved by removing redundant encoding and pubkeys).
9 ) Make input values explicit.  Makes txn validation by hardware wallets easier.
10) Consider using Schnorr signatures.  Single signature needed for multi-sig making transactions smaller.

It would greatly simplify the codebase with essentially no loss of functionality.  Sadly I don't think such breaking changes will happen with Bitcoin.

This isn't really the place to have that discussion but if you are interested join us at http://www.reddit.com/r/conceptcoin

I took a look at your link telepatheic.  I don't get why
you would want to use a trusted source for randomness
when you could use a trustless method like NXT does.

DT, any plans for your own altcoin?

Because you can cheat at NXT forging. If you have control of a particular block then you can affect who will get to forge blocks in the future. (If you can't affect a future block, then another block between now and that future block must be able to affect it, repeat this argument until you arrive at the future block, someone must have had the final say on who gets to forge it.) Again, this isn't the place for this sort of discussion, post on the conceptcoin subreddit if you want more details of why an independent random source is needed.

I should have mentioned that earlier. That check applies to outputs (where standard multi-sig pub keys go) only not inputs (where P2SH pub keys go).

So 3 of 3 is the maximum standard normal multi-signature transaction and 4 of 6 is the maximum P2SH transaction.

Making sense now.

Standard
Native MultSig = max 3-of-3 (https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp#L1414 "if (n < 1 || n > 3)")
P2SH w/ all compressed keys = max of 7-of-15 (https://github.com/bitcoin/bitcoin/blob/master/src/main.cpp#L521 "if(txin.scriptSig.size() > 500)")
P2SH w/ all uncompressed keys = max of 7-of-7 (https://github.com/bitcoin/bitcoin/blob/master/src/main.cpp#L521 "if(txin.scriptSig.size() > 500)")

Non-standard but Valid
Native MultiSig = max of 20-of-20 (update me with line reference of limit for valid OP_CHECKMULTISIG)
P2SH w/ all compressed keys = max of 15-of-15 (https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki#520-byte-limitation-on-serialized-script-size)

Invalid
Native MultiSig = more than 20-of-20
P2SH = more than 15-of-15

Anyone else want to comment on the accuracy of that?

Don't you mean 20 of 20: The following transaction is a native 20 of 20 transaction: https://blockchain.info/tx/c4aaf7fbec7a9a079e670e50f6a672315451c7618814494ab1f89cf3fd97b3bb

Nice find, a 14 20-of-20.

No it's a 20 of 20. 0x14 (base 16) is 20 (base 10)

The redeemscript limit (https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki#520-byte-limitation-on-serialized-script-size) means significantly lower than 20/20 max for non-standard but valid P2SH. I managed 8/15 when I was playing around with it, although I think you might theoretically be able to get 15/15, but someone's got to mine it.

So I was able to create a 4-of-6 P2SH on both testnet and main net.
https://blockchain.info/tx/0f1daf1ff4c46b4028095d7862094d560541d7a25d0bd60a927a8987573e8329

Is there a way to determine the IsStandard() output via an API call? 

Thanks.  Updated my post.  That is a particularly awful "gotcha".  The limit should be raised to 34 * 20 =680 bytes to be inline with the OP_CHECKMULTISIG limit.

Thanks everyone for this. It's been really helpful and thanks DeathAndTaxes for your concise answers and testing this.

Getting hold of first hand info like this is very useful as I'm not a programmer so some of this can be a bit opaque to me.

DeathAndTaxes: can you clarify what you mean by standard and non-standard but valid? Does this mean for example for a 20-of-20 that some miners may mine this to a block?

Unfortunately raising the 520 byte limit would require a hard-fork; I don't think we're going to see that issue fixed. We may see it fixed in practice by a future soft-fork implementing a new form of P2SH, perhaps something similar to the original OP_EVAL design.

FWIW when I noticed the issue I pointed it out to some other devs, e.g. gmaxwell, who had never noticed it; I suspect the problem never occurred to Gavin when the P2SH mechanism was designed.

Correct.  IsStandard() is a check in the bitcoin-core client (and other clients implement similar checks).  If a tx doesn't pass IsStandard then nodes will not relay them (or mine them by default).  The tx is still however valid, so if you can find a miner to include it in a block (either by sending it to them directly, or mining it yourself) the tx and block will still be valid.

So all transactions can be categorized as standard, non-standard, or invalid.

Thanks, this is very helpful.

So ignoring IsStandard() for now, I'm looking to construct a transaction with two inputs and a 16-of-20 output, where the 16-of-20 output can be satisfied by any 20 signatories, where none of the 20 are the signatories who sent funds to the input of the transaction.

From what I understand this is possible but want to check this here.

If I've understood this correctly this will therefore involve 22 signatories to create this transaction. Is there anything else I should be aware of?

That is possible.  The signature limits are per script so in your example only the 16 of 20 is what matters.   The transaction could have 300 inputs as long as that doesn't violate some other rules You have to use native multisig because due to the 520 byte redeem script limit the largest redeemable P2SH script will be limited to 15 keys.  Make sure you understand the difference between native multisig and P2SH.  Sometimes the term multisig is used generically when refering to P2SH scripts.  Funds requiring P2SH scripts larger than 520 bytes can not be spent (unless a hard fork is done to raise the signature limit) so you can permanently lose funds.


I am not sure if that is not correct or the wording is just not clear.

There are only signatures for inputs (the whole tx is signed but the inputs determine which and how many signatures).

So you have a 16 of 20 multisig address.

To create the MS address will require 20 PubKeyHashes.
To sign transactions with that MS address will require 16 of the 20 private keys which correspond to the PubKeyHashes.
When "receiving"* funds TO that MS address the only signers are the keys which are required to spend the unspent outputs referenced in the input side of the tx.
When "sending"* funds FROM that MS address the only signers are the 16 of 20 specified in the address.

* I generally hate to use wording like that (there is no sending or receiving just inputs and output) but I wanted to make sure it was clear.



I would highly recommend starting first using testnet due to the potential for losing funds.  I would then create some demos on main net funded with token amounts (but above dust limit) before funding with any significant amounts of funds.  There are a lot of potential gotcha, the potential for losing funds is far higher than with "normal" transactions.  Understand my knowledge (especially regarding P2SH) is incomplete and I may be unaware of something critical.  The 520 vs 20 key "incompatibility" caught me off guard (see waxwing post upthread) and that could have resulted in a loss of funds.

You probably should also review this list of limits. https://bitcointalk.org/index.php?topic=585639.msg6477657#msg6477657   Understand it may not be complete and is a work in progress.

I found this documented demo by Gavin to be helpful (although it is for P2SH not native multisig).  Doing it step by step it was the first time for me that it all "clicked".
https://gist.githubusercontent.com/gavinandresen/3966071/raw/TwoOfThree.sh

I discovered an error in the limits that I posted upthread. The correct limits should be:

Standard
Native MultSig = max 3-of-3 (https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp#L1414 "if (n < 1 || n > 3)")
P2SH w/ all compressed keys = max of 7-of-15 (https://github.com/bitcoin/bitcoin/blob/master/src/main.cpp#L521 "if(txin.scriptSig.size() > 500)")
P2SH w/ all uncompressed keys = max of 7-of-7 (https://github.com/bitcoin/bitcoin/blob/master/src/main.cpp#L521 "if(txin.scriptSig.size() > 500)")

Non-standard but Valid
Native MultiSig = max of 20-of-20 (update me with line reference of limit for valid OP_CHECKMULTISIG)
P2SH w/ all compressed keys = max of 15-of-15 (https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki#520-byte-limitation-on-serialized-script-size)

Invalid
Native MultiSig = more than 20-of-20 (per OP_CHECKMULTISIG opcode)
P2SH = more than 15-of-15

Each OP_CHECKMULTISIG has a limit of 20 public keys, but you can chain them together in Script to use more. The actual max number of public keys you can put in a transaction is probably 20,000 (the max number of sigops per block).

Updated.

But that's a requirement for validity, right? Because the new rules say that for tx to be standard it should have no more than 15 signature checking operations:

https://gist.github.com/gavinandresen/88be40c141bc67acb247

Well those proposed new rules are not implemented yet but yes they will affect the IsStandard check and it will mean a large number of potential scripts will become standard as long as they have 15 or less signature operations.  Note the redeem script is still limited to 520 bytes as that is a validity check (pushes >520 bytes are invalid and the redeemScript must be pushed to the stack to validated it against the ScriptHash.  See https://github.com/bitcoin/bitcoin/blob/6513a9f7033737458735305a08606280d6d0d33c/src/script.cpp#L327

Thanks for the explaination... I already asked in another thread, but I'll ask here as well.. That 520 bytes limit also makes txs above 3 of 4 nonstandard right?

For example this one:
0100000001422991e418b7b92c3127c22dd5bfac0743d56ab216aeb1573bba9a1025747d6400000 000fd200100483045022100d5bc891c4305e67096cee29dceef455830decda9eb9e89b41a9a5fe3 dbe75c6202207964ea2f464f525748a39fcfeaf405f45312c4ba542879fb7beeaaf20a442835014 830450221008022e32bf35c05f44cef659653724dc1ddb164035d8056ccb60e9db8f3eadb0b0220 6da064420a221958a2e65add7e0bb51739423dbfdba733d5eaf3dbe6d7b7cdf6014c8b522102e8e 22190b0adfefd0962c6332e74ab68831d56d0bfc2b01b32beccd56e3ef6f02103903ea684377ca5 1d84fbdf1566db58499d80240725ab78e2917c3c285ace4eab2103a9bd3bfbd9f9b1719d3ecad86 58796dc5e778177d77145b5c37247eb306086182103f6c9fbe11ac0345676d0eb02f212a83bd0c9 1b3e9c3adfbf6c0a8d0b51b9235c54aeffffffff05b80b0000000000001976a91425de2fdaa7954 bb4e6a53f5228847afc09bee0cd88acb80b0000000000001976a91480e4032cf40387a2714d7511 05ec93a709d17f2688ac70170000000000001976a914f38ba5d948bf2016db759124bf0440e4bfa d8e4388ac080c0100000000001976a914f32e72b477081756559b5569a66647a5bf01051488acb8 0b0000000000001976a91476a4dc3e419783ec85503f12b591069c9b47639b88ac00000000

No.  The 520 byte limits refers to the maximum push to the stack.  It applies to any push to the stack but for P2SH the "output" (ScriptPubKey) doesn't contain the actual script, it contains a hash of the script. 

OP_HASH160 <scriptHash> OP_EQUAL


This means the script needs to be part of the "input" (ScriptSig) of the redeeming tx.  That script will need to be pushed to the stack. If the redeemScript is larger than 520 bytes that push will be invalid and the output can never be redeemed (spent).   In a P2SH output the output says (paraphrased) make a copy of the script, hash it and make sure it hashes to this scripthash then make sure the spender satisfies the terms of the script.

A 3 of 4 script would be:

OP_3 <pubkey0:34> <pubkey1:34> <pubkey2:34> <pubkey3:34> OP_4 OP_CHECKMULTISIG

The total size is 1 + 34 + 34 + 34 + 1 + 1 = 139 bytes. The SCRIPT (redeemScript) is 139 bytes which is < 520 bytes and thus is valid.

I got a question about the prior summary here (https://bitcointalk.org/index.php?topic=585639.msg6482470#msg6482470) and while it was valid at the time the standard limits have been raised as of v0.9.3.  The limit for ScriptSig size of standard transactions is now 1650 bytes not 500 bytes.  This simplifies the maximum number of keys in a standard transaction.  There is no change to the limit on valid transactions as that would require a hard fork.

Standard - relayed and included in blocks by most nodes
Native MultSig = max 3-of-3 ( "if (n < 1 || n > 3) (https://github.com/bitcoin/bitcoin/blob/0.10/src/script/standard.cpp#L193)" )
P2SH w/ all compressed keys = max of 15-of-15 ( "if(txin.scriptSig.size() > 1650) (https://github.com/bitcoin/bitcoin/blob/v0.9.3/src/main.cpp#L550)" )
P2SH w/ all uncompressed keys = max of 7-of-7 ( "if(txin.scriptSig.size() > 1650) (https://github.com/bitcoin/bitcoin/blob/v0.9.3/src/main.cpp#L550)" )

Non-standard but Valid - not relayed by most nodes but could be pushed directly to a miner who accepts non-standard txns
Native MultiSig = max of 20-of-20
There are no longer any non-standard but P2SH multisig scripts that are a single OP_CHECKMULTISIG (M <Keys> N OP_CHECKMULTISIG). 
Arbitrary scripts should be checked individually and do not fit into this guideline.

Invalid - not valid under any conditions, if included in a block the block is also invalid
Native MultiSig = more than 20-of-20 ( "if (nKeysCount < 0 || nKeysCount > 20) (https://github.com/bitcoin/bitcoin/blob/0.10/src/script/interpreter.cpp#L830)" )
P2SH w/ all compressed keys =  more than 15-of-15 ( "520 byte limit (https://github.com/bitcoin/bitcoin/blob/0.10/src/script/interpreter.cpp#L273)" )*
P2SH w/ all uncompressed keys = more than 7-of-7 ( "520 byte limit (https://github.com/bitcoin/bitcoin/blob/0.10/src/script/interpreter.cpp#L273)" )*

* The actual limit is that pushdata can not exceed 520 bytes.  Public keys (including push opcode) are 34 bytes or 68 bytes for compressed and uncompressed keys respectively.  There is a 3 byte overhead so the size of all the keys must be less than 517 bytes.  FLOOR(517/34) = 15.  FLOOR(517/68) = 7.  If the redeemScript contains a mix of compressed and uncompressed keys the upper limit will vary in the range of 7 to 15 keys per script.

DISCLAIMER: Funds sent to a ScriptHash produced from a RedeemScript larger than 520 bytes are unspendable. Raising this restriction would require a hardfork which may never happen so funds are effectively lost.  Always verify your redeemScript length to prevent a loss of funds and always test new scripts on testnet before deploying to mainnet.

Very nice work, DeathAndTaxes.

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

Warning: half baked thoughts off the top of my head here, check my work and TEST TEST TEST:

There isn't room in 520-bytes for all the compressed public keys needed for m of 16-20. Can we safely move the public keys out of the serialized P2SH onto the scriptSig stack?

e.g. go from a scriptSig that looks like:


to:


That's easy to do unsafely; ... something ... is just:


That's unsafe because anybody can redeem it with any 20 keys.

To be safe, you need a secure digest of the 20 public keys inside the serialized P2SH stuff. We've got HASH160 to create 20-byte digests, so we can get 26-bytes-per-pubkey with:


Using PICK instead of ROLL you can probably save a byte per pubkey; if it can be done in 25 bytes then that gets under the 520-byte-push limit.

Aside: It would've been lovely if Script had a "hash the top N items on the stack, and push the result onto the top of the stack" operator.  Ah well.

BUT you're now putting 33+26 = 59 bytes per key into the scriptSig, so the 1650-byte-for-scriptSig-IsStandard limit will bite. If I counted everything correctly (and I almost certainly didn't), you could get 1 through 6 -of-20 as standard (20-of-20 as non-standard but valid).

EDIT:  I already see a mistake:  pushing 21 onto the stack requires two bytes, not one.....

Wait a sec... is it possible for nlocktime tx's to get mined before the lock time?  You say that's not standard, but is that even *valid*??  Will other nodes accept that block?

No.  The txn can not be included in a block before the nlocktime.  That would violate the block validation rules.  I will update that post to make that clear.   I wouldn't really consider the txn to be invalid it just would make the block invalid if included in a block prior to the nlocktime.

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.

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.

... 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.

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.

Bump.

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

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.

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