Maintaining Privacy
To maintain maximal privacy, it is important to not re-use bitcoin addresses. However, re-generating such keys repeatedly with each transaction would make many of the backup benefits that come with this system difficult. Users of bitcoin standard addresses already face this problem today and use a variety of deterministic wallet mechanisms to generate multiple keys from a single source.
The same techniques can be applied to the 2-of-3 address. Any key used as a signature should be rotated to a new address based on the next sequence in the deterministic key.
As a compromise solution, the 2-of-3 address offers one more option: only rotating the server's key. Since the 2-of-3 key is generated from 3 keys, one of which is managed by the service, we can rotate the user's funds to a new address by only rotating the servers key. The resulting address cannot be correlated to the original 2-of-3 address. However, upon spending of the outputs, the public keys will again be revealed and a correlation could be made at that time. To maintain the ability for the user to extract funds without the service, the service will need to send the newly minted service public key to the user for safekeeping. This can be done via email. But again for maximal privacy, use of deterministic key rotation is recommended.
I'm totally with you on multisig for wallet security. That said, I'm unconvinced these privacy measures are worth the inconvenience they incur vs the benefits of having a stable address. It will be painfully obvious which TX output is change because it's overwhelming likely to be the only P2SH output ... there are other signals one could incorporate as well but this one alone would likely be sufficient 99% of the time.
Cool. Good to know. You're right that for now the P2SH keys kinda stand out :-)
Right now I'm working on a scheme which uses deterministic wallets to auto-rotate your address in a way that you never have to worry about. A 2-of-3 P2SH address is simply a set of 3 keys; we can independently rotate them on the client & server predictably such that your addresses change with every transaction in an uncorrelated way without revealing the private keys to the other machine. It turns out that I need this more for maintaining sane key management than for privacy. Users do need multiple addresses - and if you've got 2 keys to manage for each address, it's just too much work.
Hopefully P2SH will not be so standout 6 months from now!
If you want to try it out, this is live on bitgo.com now and has been in use for some time. Send me (or tiffney if you prefer!) an email for an invite.
mike@bitgo.com.
mike