Uniqueness for multisig addresses

[weex]

Imagine a set of  2-of-3 multisig addresses need to be created that can be signed by the same three public keys. What would be the cheapest and safest way to generate unique addresses in this scenario? I'm thinking uniqueness is important only for up to 10-20 tries since accepting that the same address might be generated multiple times is ok beyond a certain number. I'm thinking that including a nonce of some sort would do the trick but where to put the nonce as well as the size of the nonce are in question.

[weex]

Bump.

[dive]

I think what you are looking for can be solved by Hierarchical Deterministic Multisig. I believe Copay wallet allows you to do that.

[weex]

I'm talking about creating redeem scripts, not looking for a wallet to help me do it. Using HD keys though would be a good way to be able to generate a bunch of public keys and solve this. That solution is a bit more complicated however than using some kind of a nonce.

[dev942]

If you generate a nonce e, add e*G to all three base public keys, and generate the address from those, then (a) only those who know the corresponding base private keys and nonce can spend the txo, and (b) only those who know the nonce can find the base public keys in the blockchain, even after the txo is spent (sample code from my experimental market). That's just the usual stealth math, and you can transmit the nonce however you want.

If you use BIP32 keys, then whoever generates the key can also find all other transactions by that base public key (xpub) once they're spent. So either you lose privacy, or you need some back and forth (because each party needs to generate his own key for a particular transaction).

If you literally need the transaction to be signed with the exact unmodified base keys, then you must lose privacy when the redeem script appears in the blockchain. You could e.g. do 2/4 multisig where the fourth key was provably garbage, or 3/4 multisig where it was known to everyone. That seems like an odd requirement, though.