How to modify "standard" multisig script to create multiple P2SH addresses?

[DeathAndTaxes]

I am looking for a good way to create more than one P2SH address (address is based on the hash of the script) which is encumbered by the same set of private keys.

"Standard" multisig script is <OP_m> [PubKeys] <OP_n> <OP_CHECKMULTISIG>

So with the following PubKeys:

02171f8058701e94efbbca609509b858f0ef1e32923d51991eac403ade22952421
03694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60
036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a644488

The script would be:

<OP_2> <"OP_PUSH_33"> <PubKey1:02171f8058701e94efbbca609509b858f0ef1e32923d51991eac403ade22952421> <"OP_PUSH_33"> <PubKey2:03694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60> <"OP_PUSH_33"> <PubKey3:036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a644488> <OP_3> <OP_CHECKMULTISIG>

In hex:

522102171f8058701e94efbbca609509b858f0ef1e32923d51991eac403ade22952421210369441 1c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f6021036b033de166421921 6408262a9a32dfb801f09b0bfb53dd83f036fedf1a64448853ae

The base58 encoded (0x05 prefix byte) HASH-160 hash of the script above is the address 3KKVrgqN2AYAsLQoJQchT5GK2KnKQ3dAPL.  The simplest way to get a new address would be to change the keys but lets say I want a set of addresses which use the same keys.  I could make one of the keys bogus and use it as a counter value (obviously this requires more keys i.e. for a real 2-of-3 script would require creating a pseudo 2-of-4 script).  

As an example, in the two scripts the following key the first key is invalid and just used to create a unique hash output so this is effectively a 2-of-2 script despite being 2-of-3.

script: 5221020000000000000000000000000000000000000000000000000000e0000000000012103694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f6021036b033de 1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a64448853ae
address: 3DmfeKGpHVsC7HHf2GumUE31NG14f4P8SM

script: 52210200000000000000000000000000000000000000000000000000000000000000022103694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f6021036b033de 1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a64448853ae
address: 3AeD9PWp4nCi5x1BKFhyX4qHVkiejfTbq8

Addresses can be created on demand by incrementing the counter value in the pseudo-key and recomputing the scriptHash.  This naive approach however is rather wasteful (and cludgy). It requires 34 additional bytes when only a few bytes are needed.  If we assume a 3 byte counter (>16 million sequential addresses) then this has 31 bytes of overhead.

Any ideas on a more space efficient way to accomplish the same task?  I am thinking maybe pushing the nonce to the stack and then using an OP_DROP?

<"OP_PUSH_3"> <0x010000> <OP_DROP> <OP_2> <"OP_PUSH_33"> <PubKey1> <"OP_PUSH_33"> <PubKey2> <OP_2> <OP_CHECKMULTISIG>

Any other ideas?  Any way to make it pass IsStandard()?

[Aleksei Richards]

OP_DROP might not work as the BIP16 spec specifies.

"Validation fails if there are any operations other than "push data" operations in the scriptSig."

Why not use one of the public keys as a master public key an derive other keys based on an index ?

[gmaxwell]

Yuck. BIP32 exists so that people can derive their partners addresses and do so privately with respect to the rest of the world (and without adding overhead on the network).

[amaclin]

script: 5221
020000000000000000000000000000000000000000000000000000000000000002
2103694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60
21036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a64448853ae
address: 3AeD9PWp4nCi5x1BKFhyX4qHVkiejfTbq8

Addresses can be created on demand by incrementing the counter value in the pseudo-key and recomputing the scriptHash.  This naive approach however is rather wasteful (and cludgy). It requires 34 additional bytes when only a few bytes are needed.  

Should the pseudo-key be 33/65 bytes long? I think that in is possible to use smaller array of bytes

[DeathAndTaxes]

OP_DROP might not work as the BIP16 spec specifies.

"Validation fails if there are any operations other than "push data" operations in the scriptSig."

Good catch.  That is weirdly worded and I have no idea what it means.  As written no no multisig P2SH script would be valid.  <OP_CHECKMULTISIG> is not a "push data" operation.  I will try testing the OP_DROP script on testnet.

[DeathAndTaxes]

Yuck. BIP32 exists so that people can derive their partners addresses and do so privately with respect to the rest of the world (and without adding overhead on the network).

Come on man.  Nobody derives their partners address and certainly not for creating unique P2SH addresses.  Would you really give the sender (thousands of potentially novice users) the three master pubkeys and have them create the proper P2SH address?  I mean isn't any good end user wallet support for sending to a BIP32 based Pay2PubKeyHash address much less P2SH.

If you are saying that the receiver (me) should use BIP32 to create the keys and the unique P2SH that certainly would work.  Still all three PubKeys in the script would need to be unique to maintain privacy.  As soon as bitcoind supports BIP32 I will gladly use that.  In the interim since you are worried about space let me know if you can think of a more space efficient way to accomplish the stated goal in the redeemScript.

[DeathAndTaxes]

Should the pseudo-key be 33/65 bytes long? I think that in is possible to use smaller array of bytes

Yes that would be possible I kinda assumed that a pubkey of invalid length would be invalid but it looks like it isn't (just non-standard)

Code:

decodescript 52210200000000000000000000000000000000000000000000000000000000000000012103694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f6021036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a64448853ae

{
"asm" : "2 020000000000000000000000000000000000000000000000000000000000000001 03694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60 036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a644488 3 OP_CHECKMULTISIG",
"reqSigs" : 2,
"type" : "multisig",
"addresses" : [
"1MRxjnjFDhZfjtjgpxBNczsMGVEtYqfFyS",
"155RH27o1NPWbQCyoEUC9ojR7HQepBmhoT",
"1DD1kbNw9XtG2JWYa8kg6p89DqgCpb91oG"
],
"p2sh" : "3DmfeKGpHVsC7HHf2GumUE31NG14f4P8SM"
}

decodescript 52030100002103694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f6021036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a64448853ae
{
"asm" : "2 1 03694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60 036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a644488 3 OP_CHECKMULTISIG",
"type" : "nonstandard",
"p2sh" : "32S6ymyH4XbZFQuvAVfcxRR2bxCenXc16o"
}

Both would appear to work (anyone reading along always do your own extensive testing on testnet).  The size of the redeemScript in the first is 105 bytes and in the second is 70 bytes.  So using a non-standard keysize makes the second 30 bytes shorter but it also makes it non-standard.  If limited to non-standard options I would prefer to not use a pseudo-key if possible.  It is unfortunate so few scripts are standard.  It would be nice if this was loosened especially for p2sh.

[dserrano5]

So with the following PubKeys:

02171f8058701e94efbbca609509b858f0ef1e32923d51991eac403ade22952421
03694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60
036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a644488

[…]

The base58 encoded (0x05 prefix byte) HASH-160 hash of the script above is the address 3KKVrgqN2AYAsLQoJQchT5GK2KnKQ3dAPL.

Permuting the pubkeys would give a different hash, thus a different address. Using m-of-5 allows you to generate up to 120 addresses. But the fact that no one has pointed out this obvious way to do it makes me think I must be missing something .

[DeathAndTaxes]

So with the following PubKeys:

02171f8058701e94efbbca609509b858f0ef1e32923d51991eac403ade22952421
03694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60
036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a644488

[…]

The base58 encoded (0x05 prefix byte) HASH-160 hash of the script above is the address 3KKVrgqN2AYAsLQoJQchT5GK2KnKQ3dAPL.

Permuting the pubkeys would give a different hash, thus a different address. Using m-of-5 allows you to generate up to 120 addresses. But the fact that no one has pointed out this obvious way to do it makes me think I must be missing something .

That would be an option and probably a good one especially if someone only needs a limited number of permutations but it would be larger than just using a "pseudo-key" and for my purposes I need a large number of addresses (unique user address directly into m-of-n cold storage).

If you went that route you could increase the permutations by using uncompressed versions of the same private key as well (i.e. 02ABCD32823BA8BE625AEF4BEDFB812641F2DB2A05AB72BBC0E90B44AD0ABA7222 and 04ABCD32823BA8BE625AEF4BEDFB812641F2DB2A05AB72BBC0E90B44AD0ABA722253CC1EA3ABF0E 3BA8959203ADA5B85E55587BD5CD475438FB371FCB52797C342 can both be created from the same raw private key).

[gmaxwell]

Yuck. BIP32 exists so that people can derive their partners addresses and do so privately with respect to the rest of the world (and without adding overhead on the network).

Come on man.  Nobody derives their partners address and certainly not for creating unique P2SH addresses.  Would you really give the sender (thousands of potentially novice users) the three master pubkeys and have them create the proper P2SH address?  I mean isn't any good end user wallet support for sending to a BIP32 based Pay2PubKeyHash address much less P2SH.

If you are saying that the receiver (me) should use BIP32 to create the keys and the unique P2SH that certainly would work.  Still all three PubKeys in the script would need to be unique to maintain privacy.  As soon as bitcoind supports BIP32 I will gladly use that.  In the interim since you are worried about space let me know if you can think of a more space efficient way to accomplish the stated goal in the redeemScript.

By "partners" I'm referring to the various multisig signers not the sender, it lets them all continue generating a sequence of addresses in parallel without further coordination. A sender should never change anything they've been given (and a receiver should never accept a script unilaterally changed by the sender, if somehow they notice it at all), and no one has specified an address encoding that changes things for them.

Bitcoind doesn't support any of the other alternatives here— it won't generate "padded" p2sh, it won't redeem them, so I'm not following your support concern. The only space efficient way to do this is to use the entropy thats already there, and change one (or all) of the pubkeys.

There is at least one web wallet that does this and http://ms-brainwallet.org/#bip32  so it's not a complete unicorn.

[DeathAndTaxes]

By "partners" I'm referring to the various multisig signers not the sender

That makes more sense.  The partners in this case are cold storage custodians within the same enterprise.  The server will need to be able to deterministically generate a sequence of P2SH addresses using a key (or keys) held by the custodians on an as needed basis.  I prefer to do this in the most lightweight way possible.  bitcoind makes that possible with static keys but doesn't support BIP32.  

Bitcoind doesn't support any of the other alternatives here— it won't generate "padded" p2sh, it won't redeem them, so I'm not following your support concern.

I can use RPC calls to create a padded multisig address.  It would be fairly simple.

Code:

createmultisig 2 '["020000000000000000000000000000000000000000000000000000000000000001","03694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f60","036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a644488"]'
{
"address" : "3DmfeKGpHVsC7HHf2GumUE31NG14f4P8SM",
"redeemScript" : "52210200000000000000000000000000000000000000000000000000000000000000012103694411c22d04a72ced42e79d584de695e322e67b9f2bafc1f2805146dda20f6021036b033de1664219216408262a9a32dfb801f09b0bfb53dd83f036fedf1a64448853ae"
}

The first key in the array would be 0x02 concatenated with the counter as a 256 bit hex string.  I understand it is a hack and I would be happy to consider alternatives.  I can't use bitcoind to generate a generate a sequence of BIP32 addresses from a seed and I do not wish to use another wallet/client as despite its limitations I have trust in bitcoind.

Maybe it will help if I explain what I am doing.  Currently a service accepts funds from users through a unique (Pay2PubKeyHash) address.  The "deposits" are swept to P2SH multisig cold storage.  I would prefer instead to have users deposit directly to the cold storage.  The problem is that bitcoind provides very poor support for P2SH and no support for BIP32.  Nice link I will check that out.

I guess an offline hack would be to use a BIP32 "generator" to load the required the necessary keys into the offline signing wallets (bitcoind).  The server could use three BIP32 master public keys to and a counter to generate the three unique pubkey and create the deterministic P2SH addresses on demand.  One headache in redemption will be "finding" all the cold storage unspent outputs to "redeem" them.  It is bad enough with a single P2SH address but with thousands?  It would be nice is bitcoind supported a RPC call that would return the set of unspent outputs for an arbitrary address.  However I don't believe there is any way to do that right?