Number of m-of-n ouputs per transaction

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: No_2 on July 03, 2017, 04:44:29 AM

Quote from: amaclin on June 28, 2017, 09:25:46 AM

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

No_2

hero member

Activity: 906

Merit: 1034

BTC: the beginning of stake-based public resources

Quote from: amaclin on June 28, 2017, 09:25:46 AM

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

legendary

Activity: 1260

Merit: 1019

Quote from: No_2 on June 28, 2017, 04:48:06 AM

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

hero member

Activity: 906

Merit: 1034

BTC: the beginning of stake-based public resources

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.

No_2

hero member

Activity: 906

Merit: 1034

BTC: the beginning of stake-based public resources

Bump.

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

No_2

hero member

Activity: 906

Merit: 1034

BTC: the beginning of stake-based public resources

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.

Gavin Andresen

legendary

Activity: 1652

Merit: 2311

Chief Scientist

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

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

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 EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
ScriptSig: 0 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

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  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 PubKey3		HASH160 2 PICK XOR HASH160 3 PICK XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash3			2 PICK XOR HASH160 3 PICK XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash3	3		PICK XOR HASH160 3 PICK XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash3	PubKey2 	XOR HASH160 3 PICK XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hxorp2 		HASH160 3 PICK XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash32 		3 PICK XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash32 3		PICK XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 Hash32 PubKey1	XOR HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hxorp1		HASH160  EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hash321		 EQUALVERIFY 3 4 PICK EQUALVERIFY CHECKMULTISIG
3 PubKey1 PubKey2 PubKey3 hash321 	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

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: Gavin Andresen on February 25, 2015, 12:20:15 PM

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

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: luv2drnkbr on February 25, 2015, 04:01:40 PM

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.

luv2drnkbr

hero member

Activity: 793

Merit: 1026

Quote from: DeathAndTaxes on April 30, 2014, 12:05:26 PM

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?

Gavin Andresen

legendary

Activity: 1652

Merit: 2311

Chief Scientist

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

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

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

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

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

kolinko

full member

Activity: 518

Merit: 101

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

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: kolinko on July 23, 2014, 01:07:57 AM

Quote

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

full member

Activity: 518

Merit: 101

Quote

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

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: theymos on July 20, 2014, 07:38:49 PM

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

Updated.

theymos

administrator

Activity: 5222

Merit: 13032

Quote from: DeathAndTaxes on July 20, 2014, 05:37:57 PM

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

donator

Activity: 1218

Merit: 1079

Gerald Davis

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

Topic: Number of m-of-n ouputs per transaction (Read 6124 times)