Bitcoin Forum

A new paper called "Deanonymisation of clients in Bitcoin P2P network (http://arxiv.org/pdf/1405.7418.pdf)" by Biryukov, Khovratovich and Pustogarov from the University of Luxembourg has been published on arxiv.org.
In contrast to the usual offerings, it's actually quite good.

The authors explain how to deny the use of TOR to connect to the bitcoin network by sending enough short messages of a particular form to get all the TOR exit nodes banned.
They analyze a method of discovering the 8 peers to which an average node maintains a connection thereby discovering the network topology.
They outline a DOS attack using ADDR flooding
They outline a method of rapidly lowering the difficulty under certain circumstances by constructing an "Alternate Reality". (A bit less exciting than it sounds!)

There are some other substantial chunks of experiment and analysis as well as some pretty graphs.

Probably the best constructed paper I've seen on Bitcoin.

ByteCoin

I am very confused now - in section 9.2 they are talking about bitcoin severs and clients. WTF is that??? Isn't bitcoind both/none of them?

You skipped this from page 1:

Thanks for the link. I've just had a very quick read but it sounds like a good paper indeed.

The principle used for the tor disconnection is really simple and smart ! It's also a good illustration of how hard is the task of core devs. By implementing something to secure the network (against spam in this case), you always have a risk that it's exploited for another kind of attack (tor disconnection in this case).

Several previous works have shown privacy leaks associated to analysis of transaction graph. Projects like dark wallet address this issue and that's good. But researches like this one are useful to remind us that privacy threats also lie at the network level.

This paper also points an interesting subject concerning the network topology. Studies in (social) network analysis have shown that network resilience is strongly related to its topology and that some topologies are more prone to targeted attacks which can lead to a (temporary) fragmentation of the network. For example, a study has shown that a P2P network like gnutella has a scale free topology and is highly prone to planned orchestrated attacks on highly connected nodes. Bitcoin core network is not so huge (8-10k full nodes) and a targeted attack on 3 or 4% of these nodes (300) is enough to create some serious disturbances if it's topology is scale free. By the way, if somebody knows some papers studying this subject or some services trying to monitor the network topology...

[EDIT]
Made some additional searches about Bitcoin network topology. It seems that Bitcoin network topology should be more like a random graph than like a scale free network, implying a greater resilience to targeted attacks.


http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf
https://bitcointalk.org/index.php?topic=26666.msg334840#msg334840

We're aware of that and specifically designed to address that— at least to the extent that we easily can, there is a lot of room for improvement here. You cannot completely disconnect tor peers using the attack they described because we use tor in two distinct ways:  One way is that we use tor via exit nodes, which that attack addresses— the other is that we use tor via hidden services. If you set onlynet=tor your tor-enabled node uses only this second mechanism, otherwise it uses both. Inbound connections from hidden services, if you have enabled them, are exempted from banning. Some nodes are dual stack— they receive connections via both IPv4 and tor hidden services, and thus act as bridges between the tor and non-tor hosts even if no tor exits are working.

It may well be the case that you could actually break Bitcoin on tor by also DOS attacking the HS-accepting hosts, since there aren't enough of them, and the defense above works in part because some of the existing DOS protections are disabled for HS peers so HS accepting nodes are more DOS vulnerable— though it might also be the case that you'd just break the tor network first, and there isn't much we can do about that.

Last year I proposed a novel approach (https://bitcointalk.org/index.php?topic=310323.0) using asymmetric storage costs to discourage hosts from connecting out to many peers concurrently, though since there have been no attacks (at least none that have risen to a sufficient level of irritation) there hasn't been a lot of interest in developing the idea further. Basically the idea has the outbound connecting host do a moderate amount of POW to precompute a table per peer they are connecting to that allows them to rapidly answer queries that the remote peer can efficiently compute (without storage), the remote peer continually challenges them, so that they must either constantly be doing a ton of POW work, or retain a fair amount of storage per peer.  I'd envisioned this to be an optional thing peers could signal at their connection time ("I'm willing to use up to 1GB storage to get priority access"). All of these "make connections costly" approaches open new attack avenues, however— e.g. what happens when you start a lot of useless nodes for the purpose of just making peers waste effort to connect? The best answer I had is that nodes would only perform the costly work to secure their connections with a small number of their 'favorite' peers (e.g. randomly selected peers which have proven themselves to be helpful in the past), but this only requires the attacker to make their misbehaving nodes good for a while before they start misbehaving. Using sustained local storage as the costly thing instead of one time POW has the useful property that the storage can be freed if a peer stops being useful, but sadly my approach still requires the initial setup be somewhat computationally expensive or otherwise an attacker can skip the storage and just redo the setup for every challenge.

WRT topology, we've worked to keep the wiring random in order to make the topology likely to be an expander graph. Concern about not screwing up the topology is why we don't yet have peer rotation— the first and most obvious way to do it that I came up with broke the topology in simulation (resulted in clustering that had a smallish min-cut). I'm reasonably confident that I know ways that won't, but it's always scary to change something which is hard to analyze.

@gmaxwell
Thanks for the details ! Very informative.

What was the rationale for disabling ddos protections against Tor hidden services ? I was specifically designed as a solution to attacks like the one described in this paper or is there another reason ?

WRT topology, it seems you've made a wise decision. You can't prevent people to try an attack, but this kind of topology significantly raises the cost of an effective attack.
I guess the main "threat" would be an alternative client with different networking rules (non random selection of peers) combined with an incentive to connect to specific nodes (higher bandwith, ...) which would lead to a more "centralized" topology. But that seems very hypothetical for now and I'm sure that network resilience is a very good incentive to prevent this kind of evolution.

thanks for the paper. my view is that nodes should encrypt and sign every connection, and user's should interact with the main bitcoin topology using overlay networks encrypted end to end. also we can do more privacy stuff on the bitcoin nodes.

Encrypting individual Bitcoin connections with overlay networks isn't as helpful as encrypting other kinds of connections, unless you're willing to waste large amounts of bandwidth and time. The problem is an observer who can watch traffic in and out of the encrypting server can watch a transaction-sized packet arrive over an encrypted connection and the decrypted transaction get relayed on to the P2P network a moment later. Given the highly predictable packet sizes and timings involved you can probably match them up very reliably. Delaying things doesn't really help - there aren't many transactions even across the whole Bitcoin network, so the anonymity set would be extremely small even if batched, and people want instantaneous response for things like in person transactions.

This could be solved by encrypting the entire P2P network (but then, it would be trivial for an adversary to connect to you and get the traffic unencrypted again), and by sending lots of cover traffic so it's harder to tell when a tx is being relayed. But that's very expensive, probably too expensive.

Privacy against privileged network observers is one thing. DoS is something else. As far as I know, nobody has ever built a P2P network that is really DoS resistant. It's not even clear it's possible with current technology. This may make Bitcoin technically unviable in the long run. However our current anti-DoS strategy is not that great and this is no news - e.g. banning an IP address because it sent an 81 byte message that cost almost nothing to process doesn't make a whole lot of sense (it would be better to put that IP at the bottom of a priority queue instead).

Nice paper. However one point:


This is questionable, users could be behind multiple VPNs. At least, those who are very serious about privacy will not only rely on Tor. In addition, they could use a network which is not theirs;

Thanks for the interesting comments.
We wrote a brief and simplified description of the attack and
also tried to answer questions raised during the discussion.
More comments, questions are welcome.
https://www.cryptolux.org/index.php?title=Bitcoin&oldid=1257

Nice and interesting read and some very good points stated.

Yes, — since we can't distinguish tor clients from each other banning them would just ban all tor peers, which isn't helpful so we don't do that.

I'd like to have some costly resource peers can optionally use to get themselves a preferred position, see the link I gave for some thinking about that... but absent any smarts it's still best to not increase an attackers power by letting them ban other nodes.

Right, most 'smarter' topologies are highly vulnerable... And bitcoin only requires one of its peers to be working well for the node to work well, so connecting to a couple nodes should provide  pretty reasonable performance most of time without further intelligence.

@gmaxwell : Thanks !

This is stupid

Guess who's behind this fud? The dark coin pump and dump fraud

Why do addr messages propagate for nodes who don't accept incoming connections?  If you know you're outgoing-only, you should be able to indicate so in your version message, so that the peer doesn't share any information about your IP address to others.

They don't, what you're describing isn't how the Bitcoin protocol works at all.

Other peers don't share information about you, you broadcast it— or  you don't. If your node is not configured to accept incoming connections (e.g. listen=0), knows its not in sync with the network, or is unable to determine a plausible external IP it won't broadcast an addr message for itself.

My understanding from the paper is that they were able to collect thousands of IP address of "clients" who were doing outbound connections only (apparently 90% of peers).  Is this because those client's don't have listen=0 set?

What about SPV nodes on peoples phones - I'm assuming they wouldn't / shouldn't advertise their addresses?

So to rephrase my question - why are so many nodes advertising their IP addresses if they can't accept incoming connections?

There are a healthy amount that are configured to accept connections— its a default in full nodes— but simply don't because some NAT/FW prevents it. SPV nodes do not advertise themselves.

It's not completely clear to me that the nodes in question there actually weren't accepting connections either, but in any case it's expected that there be a large number of advertising nodes which are actually unreachable.

So just stick to your credit card like a good sheep so the government can control where and what you spend your money on.  Online gambling in the U.S. land of the free has been shut down by using money as a weapon so in order to de weaponize money you need a level of anonymity. Other wise a government that can't directly control Bitcoin can go after users and control them.

Are there any example where one known identity has managed to link a bitcoin address to a physical address - and made the whole thing publicly available ?

No

There are no examples. And even if, it would be an exception rather than the rule

Your online wallets and exchanges know your ip tho

That really depends on if you use several layers of VPN, and on if you use offline wallets  :)

True but my Coinbase where I buy is fucked

Ok, 5 years+ and nothing, thats good "news". Of Course it doesn't mean its not done, if gov agencies or suchs have done it they most likely will not post about it. Having seen so many other hacks in the it-world and the subsequent show of, its still a good sign.

Might be also a bit problematic - while it may be doable (just like that website that crawled Twitter for people announcing to go on holidays/checking in for flights and then marking their homes on Google Maps), it might not be legal to do it widespread. Also there are certain costs involved with running such infrastructure and hosting that information, so you either have to sell the info or rely on ads/donations.

Especially large services like blockchain.info have VERY likely a good chance to link IPs to enough addresses to make deanonymizing the remaining few feasible.

Bitcoin is only pseudo anonymous

There's many ways to link your identity

Pseudonymous != pseudo anonymous.

Source?

Greek

pseudo- = wrong/false in greek, ano- = none/without (nym = name)

pseudo anonymity would be "false" anonymity or "falsely without name".

What's the correct one mean?

I am surprised that the percentage of "outbound only" nodes is so high.  Bitcoin takes advantage of UPnP.  This can be disabled either in the client or in the router, but today most routers ship with UPnp support enabled.   This behavior can be disabled by the user (either in the client or in the router) but any user sophisticated enough to do that would probably do port forwarding (more connections is always better in a trustless peer network). So my assumption was that most nodes (even those behind a NAT/FW) should be addressable.

Most new routers today maybe, most routers out in the field however are likely not very new at all.

I have for example blocked Bitcoin from incoming connections, 8 are more than enough for just keeping up with the block chain and my upload is too slow to be useful to others. I'll change this depending on how the implementation of header-first-sync is going to look like. If I can enforce a ban on older protocol versions, I'll likely enable inbound transactions again, since people loading single blocks or just headers are fine with me - people trying to load the whole chain are not.

By "new" I mean manufactured sometime in the last decade.

We solved this in Gnutella and now Ripple by having peers who receive an IP advertisement originating from a directly connected neighbor perform a "connectivity test" to make sure that the neighbor can accept incoming connections, and only relay the advertisement if the test succeeds. There is some info on Ripple's implementation in the Peerfinder documentation (https://github.com/ripple/rippled/tree/develop/src/ripple/peerfinder#livecache) and source code.

Ripple's connection strategy also strongly preferences peers to which it has had success connecting to in the past (https://github.com/ripple/rippled/tree/develop/src/ripple/peerfinder#bootcache)

I'm sure there's some price at which you'd be happy to serve them the entire chain.

Problem is there is no method via which that can be automatically negotiated in the current network.

We  have conducted a few more experiments to check some parameters of the
attack. First, we tested the stability of  the fingerprint (eight first-hop
connections). We were running our bitcoin client for about 10 hours. During this time 3
nodes out of eight  have disconnected. Analyzing the data from
http://getaddr.bitnodes.io/ we see that after two hours at most one node
would disconnect in average.  So for the typical duration of a client session the
fingerprint is very stable.

The second point we wanted to check was regarding the usage of VPN. Indeed
it will protect user's IP, but we wondered what would happen with the
stability of a fingerprint. I've made a couple  of experiments on the
testnet, connecting to it:
1) via public free VPNs (vpngate.net);
2) via a non-free one (AirVPN).
3) via my own VPN server.

For the cases 2) and 3) the stability of fingerprint was the same as if no
VPN was used.
For the case 1) connections to entry nodes were dropped
from time to time (about every 20 mins for the main net and about every
few minutes for the testnet due too absence of traffic) by the VPN servers.
It's likely that free VPN servers were set with small inactivity timeouts
and some limits for connection durations.

We are currently working on a countermeasure. In particular  we wonder how
reducing from eight to four entry nodes would effect the bitcoin network.
We also think to decay the connections based on the number of transactions
(for example  renewing half of the entry node connections after each
transaction). It might be interesting to include a proof of work for
creation of connections, but this would create a compatibility issue.

Excellent!

I've been accused in the past of "not caring about privacy" -- when I do care a lot about privacy. But I am not a privacy researcher, and I have a deep respect for how difficult it is to create a truly privacy-preserving system.

I'm very happy that somebody who is an expert is thinking about, and working on, countermeasures.