"'half of all computing resources' is off the mark."
I suppose that I could have stated it somewhat better by saying this: half the energy output of the planet needs to be devoted to the most energy-efficient Bitcoin mining hardware possible to guarantee that no attack is occurring, and only if that hardware is being used by honest miners and not an attacker. Of course, in practice no attacker will amass anything close to that (it would leave no power left for anything other than Bitcoin), but in practice the world will never devote anything close to half its energy resources to Bitcoin. Even generous estimates of what the world's energy economy could devote to Bitcoin leave an awful lot of room for an attack, and while the attack might not make economic sense in terms of the market value of Bitcoin or the mining payoff, it might be part of some broader plot (perhaps a war against a country where Bitcoin is popular and widely relied on).
"I could see the NSA running a large portion of nodes to de-anonymize users"
Why would they bother? Bitcoin transactions are broadcast to the entire Bitcoin network anyway. All the NSA would need is a handful of desktops and some auxiliary information about which wallets belong to which users (perhaps gather by watching Bitcoin exchanges). Bitcoin makes no anonymity guarantees at all.
Even generous estimates of what the world's energy economy could devote to Bitcoin leave an awful lot of room for an attack, and while the attack might not make economic sense in terms of the market value of Bitcoin or the mining payoff, it might be part of some broader plot...
I won't refute this, because you are right. I was just speaking in more manageable/realistic terms.
Why would they bother? Bitcoin transactions are broadcast to the entire Bitcoin network anyway. All the NSA would need is a handful of desktops and some auxiliary information about which wallets belong to which users (perhaps gather by watching Bitcoin exchanges). Bitcoin makes no anonymity guarantees at all.
Bitcoin is not anonymous, correct. That doesn't mean that it is easy to break the barrier from pseudonymous - > known identity.
Let's say there is a clever participant in the network, Satoshi, who is under investigation by the NSA. The NSA knows they will be sending 10btc to their cohort at address xyz. Satoshi is smart, he is not going to use an exchange to get his coins. Maybe he mined them. Maybe he got them in a f2f transaction.
This leaves few options to find out information about Satoshi. However, if the NSA ran a sufficient number of nodes, they could easily determine the first node to propagate a transaction. This would be Satoshi's IP address. That is why they would do this.
"This leaves few options to find out information about Satoshi. However, if the NSA ran a sufficient number of nodes, they could easily determine the first node to propagate a transaction. This would be Satoshi's IP address. That is why they would do this."
I suspect that there would be easier ways. Even just the time when the transaction occurs would reveal a data point (e.g. when the sender is awake). It also would not help much to avoid using exchanges; if the target mined their Bitcoins, then you can at least narrow them down to the people who could mine enough for the transaction (which becomes easier as transactions become larger). If the target was given the Bitcoins by someone else, you now have another transaction that can reveal some data points (e.g. when that transaction occurred, who sent the money, etc.).
Like I said, auxiliary information is key here. Sure, transactions in isolation might be hard to associate with a person, but transactions do not occur in a vacuum. If you want to speak rigorously about anonymity, you need to somehow include the notion that an attacker might have access to some information beyond the observations they make of the system; the point is that the system should not expand the attacker's knowledge (except by some negligible amount). This is the intuition behind concepts like "unlinkability" in academic work on digital cash: it should be computationally difficult to identify transactions that originated from the same spender (even better is the notion of transferable cash, which allows for "fully" offline payments; however, this has the drawback of causing the representation of the money to grow in the number of parties that have received it, and so it scales poorly [1]).
So, imagine a system where a party being watched by the NSA uses an offline protocol to pay another party e.g. they meet out in a field somewhere and do the transaction without any Internet connection. A system with divisibility and unlinkability [2] would make it hard for the NSA to track the target from the transaction, as the target could withdraw more money from the bank than he spends, and the receiver's deposit does not reveal which user sent the receiver the money (at least beyond what would be revealed by things like the timing of the withdrawals and deposits and the amount of money being deposited; the point is that the transaction protocol itself does not add any additional information). A system that supports transferable cash would take this even further: a party might receive the cash from one friend, then send it to another, both using offline transactions, and the NSA would not be able to identify "middle" party (or the "first" party that made the withdrawal).
Of course, these definitions cannot be applied to Bitcoin, for an obvious reason: these definitions call for a bank in the system, which acts as an authority on the validity of the money (sound familiar?) and which identifies "cheaters" e.g. double-spenders. On the other hand, there seems to be no good security definition for digital cash that does not involve such an authority; I suspect this has something to do with the lack of an economic theory for money with no intrinsic value and with no such authority.
No doubt there are better ways. If there were no useful data points (e.g. stolen then mixed via CoinJoin, traded atomically to another chain with less traceability then back again) then maybe it would be helpful. But then again, if it was a sophisticated user they probably wouldn't propagate the tx from their own IP. I brought it up only because it would be slightly more expensive then some other attacks.
Regardless, you are right. Absolute anonymity is not possible in Bitcoin at the moment. If offline transactions become more adept, then perhaps. But for now... not quite.
Comments
"'half of all computing resources' is off the mark."
I suppose that I could have stated it somewhat better by saying this: half the energy output of the planet needs to be devoted to the most energy-efficient Bitcoin mining hardware possible to guarantee that no attack is occurring, and only if that hardware is being used by honest miners and not an attacker. Of course, in practice no attacker will amass anything close to that (it would leave no power left for anything other than Bitcoin), but in practice the world will never devote anything close to half its energy resources to Bitcoin. Even generous estimates of what the world's energy economy could devote to Bitcoin leave an awful lot of room for an attack, and while the attack might not make economic sense in terms of the market value of Bitcoin or the mining payoff, it might be part of some broader plot (perhaps a war against a country where Bitcoin is popular and widely relied on).
"I could see the NSA running a large portion of nodes to de-anonymize users"
Why would they bother? Bitcoin transactions are broadcast to the entire Bitcoin network anyway. All the NSA would need is a handful of desktops and some auxiliary information about which wallets belong to which users (perhaps gather by watching Bitcoin exchanges). Bitcoin makes no anonymity guarantees at all.
I won't refute this, because you are right. I was just speaking in more manageable/realistic terms.
Bitcoin is not anonymous, correct. That doesn't mean that it is easy to break the barrier from pseudonymous - > known identity.
Let's say there is a clever participant in the network, Satoshi, who is under investigation by the NSA. The NSA knows they will be sending 10btc to their cohort at address xyz. Satoshi is smart, he is not going to use an exchange to get his coins. Maybe he mined them. Maybe he got them in a f2f transaction.
This leaves few options to find out information about Satoshi. However, if the NSA ran a sufficient number of nodes, they could easily determine the first node to propagate a transaction. This would be Satoshi's IP address. That is why they would do this.
"This leaves few options to find out information about Satoshi. However, if the NSA ran a sufficient number of nodes, they could easily determine the first node to propagate a transaction. This would be Satoshi's IP address. That is why they would do this."
I suspect that there would be easier ways. Even just the time when the transaction occurs would reveal a data point (e.g. when the sender is awake). It also would not help much to avoid using exchanges; if the target mined their Bitcoins, then you can at least narrow them down to the people who could mine enough for the transaction (which becomes easier as transactions become larger). If the target was given the Bitcoins by someone else, you now have another transaction that can reveal some data points (e.g. when that transaction occurred, who sent the money, etc.).
Like I said, auxiliary information is key here. Sure, transactions in isolation might be hard to associate with a person, but transactions do not occur in a vacuum. If you want to speak rigorously about anonymity, you need to somehow include the notion that an attacker might have access to some information beyond the observations they make of the system; the point is that the system should not expand the attacker's knowledge (except by some negligible amount). This is the intuition behind concepts like "unlinkability" in academic work on digital cash: it should be computationally difficult to identify transactions that originated from the same spender (even better is the notion of transferable cash, which allows for "fully" offline payments; however, this has the drawback of causing the representation of the money to grow in the number of parties that have received it, and so it scales poorly [1]).
So, imagine a system where a party being watched by the NSA uses an offline protocol to pay another party e.g. they meet out in a field somewhere and do the transaction without any Internet connection. A system with divisibility and unlinkability [2] would make it hard for the NSA to track the target from the transaction, as the target could withdraw more money from the bank than he spends, and the receiver's deposit does not reveal which user sent the receiver the money (at least beyond what would be revealed by things like the timing of the withdrawals and deposits and the amount of money being deposited; the point is that the transaction protocol itself does not add any additional information). A system that supports transferable cash would take this even further: a party might receive the cash from one friend, then send it to another, both using offline transactions, and the NSA would not be able to identify "middle" party (or the "first" party that made the withdrawal).
Of course, these definitions cannot be applied to Bitcoin, for an obvious reason: these definitions call for a bank in the system, which acts as an authority on the validity of the money (sound familiar?) and which identifies "cheaters" e.g. double-spenders. On the other hand, there seems to be no good security definition for digital cash that does not involve such an authority; I suspect this has something to do with the lack of an economic theory for money with no intrinsic value and with no such authority.
[1] https://dl.acm.org/citation.cfm?id=1754992
[2] http://eprint.iacr.org/2007/216.pdf
Good post.
No doubt there are better ways. If there were no useful data points (e.g. stolen then mixed via CoinJoin, traded atomically to another chain with less traceability then back again) then maybe it would be helpful. But then again, if it was a sophisticated user they probably wouldn't propagate the tx from their own IP. I brought it up only because it would be slightly more expensive then some other attacks.
Regardless, you are right. Absolute anonymity is not possible in Bitcoin at the moment. If offline transactions become more adept, then perhaps. But for now... not quite.