HD wallets for increased transaction privacy [split from CoinJoin thread]

[justusranvier]

An extended public key only lets you see the transactions in the subchain its on. Not all your transactions!

It's still an inexcusably-high amount of metadata to leak.

It's not terrible for privacy, its essential for privacy because the alternative is the addresses people put in their signatures/profiles which get automatically scraped and listed on the web.

The alternative is that the forum gives out some token that can be used to find the other person to exchange pubkeys directly, without the forum being able to record the information itself.

For example, your HD wallet client can have Torchat functionality built in, and you post the address in your profile such that anyone wanting to get payment information can point their client to that address.

Substitute Bitmessage, or any other eavesdropping-resistant P2P messaging system, for Torchat as desired.

It just takes a bit more thought to architect the negotiation protocol, but it's not all that complicated. For extra credit, you design the extended pubkey request and exchange protocol to be transport-independent and add a plugin feature to the clients such that you can do it over Torchat, Bitmessage, IRC, I2P, Freenet, or any protocol you can write a transport plugin for.

[Mike Hearn]

I'm confused by this thread. You guys understand that the payment protocol already allows the recipient to request an arbitrary number of outputs, right? Whether they are generated from an HD key or not is an implementation detail of the recipient side. The sending side just gets a set of instructions that it must satisfy. It makes sense for the the sender to try and craft multiple independent transactions to satisfy those outputs, if that is what is best for privacy. Again, the payment protocol is already designed with this in mind.

There's no need for new URI or serialization schemes. Just implementing BIP 70 is sufficient.

[d'aniel]

I'm confused by this thread. You guys understand that the payment protocol already allows the recipient to request an arbitrary number of outputs, right? Whether they are generated from an HD key or not is an implementation detail of the recipient side. The sending side just gets a set of instructions that it must satisfy. It makes sense for the the sender to try and craft multiple independent transactions to satisfy those outputs, if that is what is best for privacy. Again, the payment protocol is already designed with this in mind.

There's no need for new URI or serialization schemes. Just implementing BIP 70 is sufficient.

The idea of sending public chain codes to people to be used into the future hasn't been sitting well with me because if your wallet is lost or compromised, then you'd have to go around to everyone you've given one out to and revoke them.  Or build an entire key revocation infrastructure around them.

The payment protocol makes a lot more sense to me too.

[Peter Todd]

Why not just generate addresses from HDseed+blockheight/n, where n is some small power of two integer like 8 or 16? Your wallet isn't going to have an issue generating and scanning for a few hundred addresses matching the rolling window, and it still provides the privacy benefit in most cases where payments are being spaced apart.

We don't need this to be perfect - the main usage is donation addresses where a really dedicated attacker could find them anyway.

Other than that I'd suggest creating a standard where the address is included in a small OP_RETURN data packet encrypted to the owner; you'd scan the whole blockchain for payments that you can decrypt.

[maaku]

I'm confused by this thread. You guys understand that the payment protocol already allows the recipient to request an arbitrary number of outputs, right? Whether they are generated from an HD key or not is an implementation detail of the recipient side. The sending side just gets a set of instructions that it must satisfy. It makes sense for the the sender to try and craft multiple independent transactions to satisfy those outputs, if that is what is best for privacy. Again, the payment protocol is already designed with this in mind.

There's no need for new URI or serialization schemes. Just implementing BIP 70 is sufficient.

This is for cases where the number of future transactions is unknown, and perhaps unbounded.

[justusranvier]

I'm confused by this thread. You guys understand that the payment protocol already allows the recipient to request an arbitrary number of outputs, right?

With an extended public key there is no need for the sender to request a pre-defined number of outputs at the negotiation phase. When a recipient gives a sender a BIP32 key that sender now has the ability to create as many as they will need, forever, with no need for additional negotiation.

[Mike Hearn]

Sure, I understand that, but then you're back to wondering - how many keys should I use, and what values should I assign to them?

Extending the payment protocol with deterministic pubkeys would be interesting and it was already suggested a long time ago. That's the sort of thing it's for. But you'd probably want to extend it with some kind of subscription related info at the same time. Otherwise it's incomplete ...

[justusranvier]

Sure, I understand that, but then you're back to wondering - how many keys should I use, and what values should I assign to them?

That's for the sender to figure out, based on whatever balance of privacy vs speed of transaction vs fees matches their own preferences.

The recipient doesn't need to know or care about that at all. If they are expecting a certain amount of funds to arrive they just keep watching their sequence of addresses for it to show up until it does. It shouldn't matter to them whether it arrives in a single transaction or 100 transactions.

One of the problems with the payment protocol with single addresses (instead of extended pubkeys) is that the recipient can effectively dictate the amount of potential privacy the sender can enjoy. (Refuse to provide more than a single deposit address and the sender might be forced to combine outputs from different addresses to make the payment, thus linking them on the blockchain). If that somehow become a default setting somewhere then we get privacy turned off by default in a large chunk of the ecosystem.

On the other hand, if the recipient provides an extended pubkey they can't restrict the number of payment addresses the sender uses and appropriately-coded clients get privacy on by default.

[Peter Todd]

Sure, I understand that, but then you're back to wondering - how many keys should I use, and what values should I assign to them?

That's for the sender to figure out, based on whatever balance of privacy vs speed of transaction vs fees matches their own preferences.

The recipient doesn't need to know or care about that at all. If they are expecting a certain amount of funds to arrive they just keep watching their sequence of addresses for it to show up until it does. It shouldn't matter to them whether it arrives in a single transaction or 100 transactions.

Yes it does: spending 100 transactions costs more in fees than spending 1 transaction.

At least, that's what it looks like at first glance; in reality it depends on how you spend your coins. Take the example of Alice, who receives a weekly paycheck from Bob, valued 100BTC: She starts off with a single txout, of 100BTC value, and pays her bills, buys lunch, gives her kids their allowance etc. Each payment she makes results in a wallet with a (100-expenditures) txout, so she's averaging one input and two outputs per transaction. If her payments were all 0.5BTC, she'll would have made ~200 transactions before that txout is finally used up. She could have instead received ten 10BTC txouts instead, and her total transaction fees paid would have increased slightly because a few more of the txouts would have had multiple inputs as the money ran out. But all the same her total tx fees have increased for the sake of maybe privacy.

On the other had Bob, who runs an online store, has to combine the payments of 200 customers to pay Alice. He has to pay transaction fees on the ~142 bytes required per txin, and the last thing he needs is for his customers to start paying him with even more txouts.

Having said that even Bob still has a privacy problem as it's likely that his payments to Alice, and his other employees, are going to end up linked together; Alice certainly has a problem. Overall they both could benefit from cut-thru payments, both to reduce total transaction fees, and improve privacy. I think in most cases it'd be enough to have Alice's wallet software just give Bob a list of addresses and amount ranges she's interested in - I don't think it's really required that for Bob's customers' wallet software support anything beyond single txout payments, although it wouldn't hurt.

Of course all this stuff is really assuming that blockchain space remains cheap enough that most transactions happen on the blockchain, in which case you have to wonder why anyone would care much about fees. On the other hand if blockchain space is expensive, Alice's transaction patterns are going to be mainly receiving large chunks of Bitcoins, and moving them to off-chain tx services periodically. That's easy to do with single-txin, single-txout transactions, has no privacy issues at all, and will naturally be supported by wallet software to save on fees.

[justusranvier]

Of course all this stuff is really assuming that blockchain space remains cheap enough that most transactions happen on the blockchain, in which case you have to wonder why anyone would care much about fees. On the other hand if blockchain space is expensive, Alice's transaction patterns are going to be mainly receiving large chunks of Bitcoins, and moving them to off-chain tx services periodically. That's easy to do with single-txin, single-txout transactions, has no privacy issues at all, and will naturally be supported by wallet software to save on fees.

You mean, no privacy issues other than that users are forced to hold their funds with a third party service who can monitor their transactions or lose or steal their bitcoins.

[Peter Todd]

Of course all this stuff is really assuming that blockchain space remains cheap enough that most transactions happen on the blockchain, in which case you have to wonder why anyone would care much about fees. On the other hand if blockchain space is expensive, Alice's transaction patterns are going to be mainly receiving large chunks of Bitcoins, and moving them to off-chain tx services periodically. That's easy to do with single-txin, single-txout transactions, has no privacy issues at all, and will naturally be supported by wallet software to save on fees.

You mean, no privacy issues other than that users are forced to hold their funds with a third party service who can monitor their transactions or lose or steal their bitcoins.

Off-chain Transactions - Bitcoin 2013 Conference - Peter Todd <- it's well understood how to prevent all those things.

Anyway decentralized consensus theory has advanced to the point where we can probably build crypto-coin systems that allow for much better tradeoffs when it comes to scalability, transaction volume, and security. But they'll require thousands of lines of code, and years of testing before any of it gets implemented. They're also all systems that clearly expose the underlying "There Ain't No Such Thing As A Free Lunch" nature of the world; outsourcing your security to miners comes at a cost and I mean it when I say these systems have tradeoffs. But so does Bitcoin - it's just not made obvious yet because Bitcoin is still in its infancy.

Anyway for now we've got the Satoshi Bitcoin v1 system, and we have to live with it's limitations.

[Mike Hearn]

The recipient still has to have some bound on the key lookahead, so in reality even with an extended key there isn't infinite flexibility about how to send money.

[justusranvier]

The recipient still has to have some bound on the key lookahead,

Why? As keys are used, just keep moving the lookahead window forward until you find the last transaction.

[gmaxwell]

The recipient still has to have some bound on the key lookahead,

Why? As keys are used, just keep moving the lookahead window forward until you find the last transaction.

What if there is no "last transaction"? How else but a lookahead bound to you propose to avoid scanning forever?

[justusranvier]

What if there is no "last transaction"? How else but a lookahead bound to you propose to avoid scanning forever?

If you're talking about an attacker trying to grief the recipient by consuming large numbers of addresses, the worst he could do is send a single satoshi to each address in sequence, and since the number of satoshis is finite there's no "forever" involved.

[gmaxwell]

What if there is no "last transaction"? How else but a lookahead bound to you propose to avoid scanning forever?

If you're talking about an attacker trying to grief the recipient by consuming large numbers of addresses, the worst he could do is send a single satoshi to each address in sequence, and since the number of satoshis is finite there's no "forever" involved.

No. The worst he can do is send nothing to 1000 addresses and then someone else sends 100 bitcoins to the next one. Knowing how many addresses gap there are permitted to be is important information!

[gmaxwell]

Substitute Bitmessage, or any other eavesdropping-resistant P2P messaging system, for Torchat as desired.

Please take a step back and consider how you're responding here.  Some people want to post addresses online so an anonymous party can pay them, even when they aren't online.  They can and do currently do this by throwing up a static address.  You are instead saying they need to be online 24/7 and use bitmessage or torchat or any of a bunch of other things that they aren't already using.

You have failed to improve anyone's privacy. With your response practically anyone, including _myself_ would just continue what they've been doing. Good job.

[justusranvier]

No. The worst he can do is send nothing to 1000 addresses and then someone else sends 100 bitcoins to the next one.

Under what circumstances would this be a problem?

[justusranvier]

You have failed to improve anyone's privacy.

You've subtly misrepresented what I said, which doesn't particularly surprise me, but whatever.

Are you honestly claiming that creating a honeypot is a way to improve privacy?

[gmaxwell]

You have failed to improve anyone's privacy.

You've subtly misrepresented what I said, which doesn't particularly surprise me, but whatever.

Because I'm an evil nasty person out to do you harm. Because thats totally more likely than us just having an honest misunderstanding and me not being able to figure out how you're not crazy here. 

Are you honestly claiming that creating a honeypot is a way to improve privacy?

I'm really very confused by your comments.

Being able to delegate address generation to less trusted things, like a VPS— allowing you to have unique addresses where otherwise reuse would be required was a major design goal of BIP32.

Yes, you could have some always online trusted server communicating over some strongly private channel. But that just isn't practical in many cases.  As evidenced by the rampant use of static addresses in these places.  Allowing the less trusted device to generate addresses is a _strict improvement_ in privacy over the alternative of equivalent usability, because it reduces the space of parties who can deanonymize these particular transactions to only those who can compromise the less trusted issuer.  True, it does not replace issuing from a trusted location— thats still preferable— but presumably people would still do that where its actually possible, as they already do.

I am struggling to come up with any remotely rational basis for your complaint.  Are you under the impression that a user could only have a single chain, and thus this practice would reduce their privacy for all their addresses rather than just the subset which would have instead used a single static address?

No. The worst he can do is send nothing to 1000 addresses and then someone else sends 100 bitcoins to the next one.

Under what circumstances would this be a problem?

Under any circumstance where it happens when the receiver is not looking forward at least 1000 addresses.