m of n where each of n addresses is m' of n'

jl2012

legendary

Activity: 1792

Merit: 1111

Quote from: Peter Todd on July 23, 2014, 05:11:56 AM

Quote from: jl2012 on July 23, 2014, 03:55:28 AM

It should take 525 bytes, so you could only store 19 pubkeys

Doh! Looks like I had a stray pubkeys[1:] in my Python script and miscounted.

Quote from: jl2012 on July 23, 2014, 03:55:28 AM

It could be simplified if it requires M-of-M signatures:

Good idea!

If OP_CAT was not disabled, we could have much more interesting and compact scripts. It is really a pity that OP_CAT and OP_SUBSTR were disabled.

Peter Todd

legendary

Activity: 1120

Merit: 1152

Quote from: jl2012 on July 23, 2014, 03:55:28 AM

It should take 525 bytes, so you could only store 19 pubkeys

Doh! Looks like I had a stray pubkeys[1:] in my Python script and miscounted.

Quote from: jl2012 on July 23, 2014, 03:55:28 AM

It could be simplified if it requires M-of-M signatures:

Good idea!

jl2012

legendary

Activity: 1792

Merit: 1111

Quote from: Peter Todd on July 22, 2014, 11:52:07 PM

That's not to say doing a 20-of-20 P2SH is impossible though - you can put 20-byte hashes in the limited size redeemScript and provide the pubkeys in the scriptSig:

Code:

(OP_DUP OP_HASH160 8e4358ca4d6c9cd53a8e01e75bf0d25475c352e7 OP_EQUALVERIFY OP_TOALTSTACK) * 20
20
(OP_FROMALTSTACK) * 20
20 OP_CHECKMULTISIG

Total size: 500 bytes.

That's close enough to 520 bytes that I'm sure you could squeeze in one more pubkeyhash with some micro-optimizations, but I'm procrastinating right now so I'll let someone else do it.

Quote

(OP_DUP OP_HASH160 8e4358ca4d6c9cd53a8e01e75bf0d25475c352e7 OP_EQUALVERIFY OP_TOALTSTACK) * 20 500bytes
20 2bytes
(OP_FROMALTSTACK) * 20 20bytes
20 OP_CHECKMULTISIG 3bytes

It should take 525 bytes, so you could only store 19 pubkeys

It could be simplified if it requires M-of-M signatures:

Code:

(OP_DUP OP_HASH160 8e4358ca4d6c9cd53a8e01e75bf0d25475c352e7 OP_EQUALVERIFY OP_CHECKSIGVERIFY)  * (M - 1)
OP_DUP OP_HASH160 8e4358ca4d6c9cd53a8e01e75bf0d25475c352e7 OP_EQUALVERIFY OP_CHECKSIG

Size is M*25

That will allow 20 pubkeys.

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

You are looking at the size of the entire transaction. The 520 byte limit is the maximum push to the stack. The redeemScript in the input (ScriptSig) will be pushed to the stack and so it must be less than 520 bytes.

kolinko

full member

Activity: 518

Merit: 101

For example, this tx, which redeems "2 of 4":

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

It barely fits the 512 bytes limit, right? Are we doing something wrong?

kolinko

full member

Activity: 518

Merit: 101

Code:

The limit of 7-of-15 is somewhat of an artificial one.  This can be raised in the future.  Raising it to 15-of-15 is relatively easy (the "m" is only limited by "IsStandard" check not a validity check).  Raising it to 20-of-20 requires a hard fork to raise the redeemScript limit from 520 bytes to at least 683 bytes.  In theory it could be raised beyond that by a hard fork which makes OP_CHECKMULTISIG with an n >20 as valid but I doubt that'll ever happen.

From our experience more than 3 of 4 causes redeemScript to exceed 520 bytes size. Do you have an example transaction that redeems anything higher than X of 6, and will still be considered standard?

Peter Todd

legendary

Activity: 1120

Merit: 1152

That's not to say doing a 20-of-20 P2SH is impossible though - you can put 20-byte hashes in the limited size redeemScript and provide the pubkeys in the scriptSig:

Code:

(OP_DUP OP_HASH160 8e4358ca4d6c9cd53a8e01e75bf0d25475c352e7 OP_EQUALVERIFY OP_TOALTSTACK) * 20
20
(OP_FROMALTSTACK) * 20
20 OP_CHECKMULTISIG

Total size: 500 bytes.

That's close enough to 520 bytes that I'm sure you could squeeze in one more pubkeyhash with some micro-optimizations, but I'm procrastinating right now so I'll let someone else do it.

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: trout on July 22, 2014, 02:09:35 PM

To get around this, would it be possible to have a P2SH m of n script where each of the m redeaming addresses is another m' of n' script?

No because the Bitcoin protocol doesn't use addresses. When you provide your client an address to "send" funds to it. The client decodes the address into either a PubKeyHash or a ScriptHash depending on the type of address. It then constructs either a Pay2PubKeyHash or a Pay2ScriptHash output. The address is never part of the transaction. It is merely a method of communicating a type and hash in a human friendly format.

Likewise OP_CHECKMULTISIG references a sequence of Public Keys (not addresses, not scripts, not script hashes, not pubkeyhashes). The only valid spendable use of OP_CHECKMULTISIG requires a sequence of PubKeys.

The limit of 7-of-15 is somewhat of an artificial one. This can be raised in the future. Raising it to 15-of-15 is relatively easy (the "m" is only limited by "IsStandard" check not a validity check). Raising it to 20-of-20 requires a hard fork to raise the redeemScript limit from 520 bytes to at least 683 bytes. In theory it could be raised beyond that by a hard fork which makes OP_CHECKMULTISIG with an n >20 as valid but I doubt that'll ever happen.

theymos

administrator

Activity: 5222

Merit: 13032

Quote from: trout on July 22, 2014, 04:43:52 PM

Thanks for the answer! What about "native" multisignature addresses (not P2SH)?
From what I found, addmultisigaddress requires n keys where
" Each key is a bitcoin address or hex-encoded public key ". So each of these can be a multisig address
as well?

Any address that starts with 3 is P2SH. There is no address format defined for "native" multisig AFAIK. Even if there was, using it would just be a shortcut to including more public keys directly.

You can only use an address in addmultisigaddress if the address is in your wallet. Bitcoin Core gets the public key from your wallet and uses that.

trout

sr. member

Activity: 333

Merit: 252

Thanks for the answer! What about "native" multisignature addresses (not P2SH)?
From what I found, addmultisigaddress requires n keys where
" Each key is a bitcoin address or hex-encoded public key ". So each of these can be a multisig address
as well?

theymos

administrator

Activity: 5222

Merit: 13032

No. A script can only contain at most one P2SH script evaluation. Trying to do a m-of-n with P2SH addresses would require more than one P2SH script evaluation (you'd need an OP_EVAL). Also, standard m-of-n scripts deal with public keys directly, not addresses.

trout

sr. member

Activity: 333

Merit: 252

I read in this thread that
for m of n P2SH to be standard it must have m<= 7 and n <=15.

To get around this, would it be possible to have a P2SH m of n script where each of the m redeaming addresses is another m' of n' script?

If such transactions are posible, then I'm pretty sure one can build a tree of 2-of-3 transactions to achieve m of n for any possible m and n.

Topic: m of n where each of n addresses is m' of n' (Read 1105 times)