Number of m-of-n ouputs per transaction

[telepatheic]

a 14 of 20

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

[1714046753]

1714046753

[1714046753]

1714046753

[1714046753]

1714046753

[1714046753]

1714046753

[waxwing]

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.

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 (per explicit check in scripts.cpp)
P2SH w/ uncompressed keys = max of 3-of-4 (per scriptsig check in main.cpp)
P2SH w/ all compressed keys = max of 4-of-6 (per scriptsig check in main.cpp)

Non-standard but Valid
Native MultiSig = max of 20-of-20
P2SH = max of 20-of-20

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

Anyone else want to comment on the accuracy of that?

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.

[DeathAndTaxes]

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? 

[DeathAndTaxes]

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.

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.

[No_2]

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?

[Peter Todd]

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.

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.

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.

[DeathAndTaxes]

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?

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.

[No_2]

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?

[DeathAndTaxes]

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.

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.

If I've understood this correctly this will therefore involve 22 signatories to create this transaction.

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.

Is there anything else I should be aware of?

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

[DeathAndTaxes]

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

[theymos]

Invalid
Native MultiSig = more than 20-of-20

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

[DeathAndTaxes]

Each OP_CHECKMULTISIG has a limit of 20 public keys, but you can chain them together in Script to use more ...

Updated.

[kolinko]

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

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

[DeathAndTaxes]

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

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

[kolinko]

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

[DeathAndTaxes]

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.

[DeathAndTaxes]

I got a question about the prior summary here 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)" )
P2SH w/ all compressed keys = max of 15-of-15 ( "if(txin.scriptSig.size() > 1650)" )
P2SH w/ all uncompressed keys = max of 7-of-7 ( "if(txin.scriptSig.size() > 1650)" )

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)" )
P2SH w/ all compressed keys =  more than 15-of-15 ( "520 byte limit" )*
P2SH w/ all uncompressed keys = more than 7-of-7 ( "520 byte limit" )*

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

[Gavin Andresen]

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:

Code:

0 signature  serialized(1 pubkey1 ... pubkey20 20 CHECKMULTISIG)

to:

Code:

0 signature pubkey1 ... pubkey20 serialized( 1 ... something ... 20 CHECKMULTISIG)

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

Code:

21 ROLL ... repeated 20 times

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:

Code:

21 ROLL DUP HASH160 pubkey1hash EQUALVERIFY

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

[luv2drnkbr]

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

• The tx size > 100KB
• The scriptSig size is > 500 bytes.
• The value of any output is less than the dust threshold (currently 5,430 satoshis).
• The tx does not include the min mandatory fee (0.1 mBTC required for 0.8x nodes and 0.01 mBTC required by 0.9x nodes).**
• The tx is not final (nLockTime block has not been created yet).
• The tx version is unknown.

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?

[DeathAndTaxes]

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.