CAddrMan: Stochastic IP address manager
13 messages, 30 to 31 Jan 2012. Started by Pieter Wuille.
Michael Hendricks (4), Luke Dashjr (2), Greg Maxwell (2), Pieter Wuille, Gavin Andresen, grarpamp, phantomcircuit, solar
Hello all,
wanting to move to IPv6 support in the Satoshi bitcoin client somewhere in the future, the way IP addresses were managed is not really possible anymore. Right now, basically all addresses ever seen are kept - both on-disk and in-memory, and sorted on last-seen time with some randomization. For some people this lead to multi-megabyte addr.dat files that took ages (well, seconds) to load.
After some discussion with Gregory Maxwell and others on IRC, I decided to write a specialized address manager based on an entirely different principle: only keep a limited number of addresses, keep and index them in-memory, and only occasionally (and asynchronously) dump them to disk. This of course leads to a weakness: attackers may try to poison your entire address cache with addresses they control, in order to perform a Sybil attack. This is especially dangerous in the context of IPv6, where much more possible addresses exist.
To protect against this, we came up with this design: keep two tables: one that keeps addresses we've had actual connections with, and one that maintains untried/new addresses. Both are separated into several limited-size buckets. Each tables provides a level of protection against sybil attacks: * Addresses in the first table are placed in one of only a few buckets chosen based on the address range (/16 for IPv4). This way, an attacker cannot have tons of active nodes in the same /16 range, and use those to fill the table. * Addresses in the second table are placed in one of a few buckets chosen based on address range the information came from, instead of the address itself. This way, an attacker spamming you with tons of "addr" messages can only still have a limited effect. * All crucial decisions (selection of addresses, picking a place in a bucket, which entry to evict if necessary, ...) are randomized with biases to improve efficiency. Selection of buckets is based on a cryptographic hash using a secret key to deterministically randomize behaviour.
The implementation is available in pull request 787 (https://github.com/bitcoin/bitcoin/pull/787), but there is certainly need for testing, and room for improvements. Test reports, comments, constructive criticism, suggestions and improvements are very welcome.
On Sunday, January 29, 2012 9:31:02 PM Pieter Wuille wrote:
Quoted text (4 lines)
> The implementation is available in pull request 787 > (https://github.com/bitcoin/bitcoin/pull/787), but there is certainly > need for testing, and room for improvements. Test reports, comments, > constructive criticism, suggestions and improvements are very welcome.
As of yesterday, this is also part of my `next' and `next-test' branches.
Summary of latest next/next-test:
*** ACCEPTED (`next' branch) 719 coinbaser 3dc0e2a 755 explicit_p2sh 6728ecb 787 sipa/addrman 70b8988 786 sipa/checkkeys c0e8c4d
*** NEEDS ACCEPT 570 force_send (557) 9437c14 568 rpc_keepalive 178f2c3 (threaded_rpc included)
*** NEEDS REVIEW 457 origin-pull/457/head* 433b275 IPv6 JSON-RPC 565 optimize_FastGetWork 4c1214f 691 origin-pull/691/head 6192d6d Temporarily disable "minimize to tray"
*** NEEDS SUPPORT 780 checkhashverify 60649bd 715 bugfix_client_name fd6fc41 559 accept_nonstdtxn 7945399 552 base58_liberal_parsing e005327 553 bugfix_qt_uri_amount_… 45d7c36 562 optimize_ToHex a781103
Luke
On Sun, Jan 29, 2012 at 7:31 PM, Pieter Wuille <pieter.wuille@gmail•com> wrote:
Quoted text (6 lines)
> wanting to move to IPv6 support in the Satoshi bitcoin client > somewhere in the future, the way IP addresses were managed is not > really possible anymore. Right now, basically all addresses ever seen > are kept - both on-disk and in-memory, and sorted on last-seen time > with some randomization. For some people this lead to multi-megabyte > addr.dat files that took ages (well, seconds) to load.
I think this is a great change for IPv4 too. On certain machines with slow IO, I routinely delete the address database before starting bitcoind to improve load times.
Quoted text (5 lines)
> After some discussion with Gregory Maxwell and others on IRC, I > decided to write a specialized address manager based on an entirely > different principle: only keep a limited number of addresses, keep and > index them in-memory, and only occasionally (and asynchronously) dump > them to disk.
I've started a couple patches with a similar design, but not produced anything I'm happy with. That work has persuaded me that this architecture is a valuable improvement over what we have today.
Quoted text (4 lines)
> This of course leads to a weakness: attackers may try to > poison your entire address cache with addresses they control, in order > to perform a Sybil attack. This is especially dangerous in the context > of IPv6, where much more possible addresses exist.
If the Bitcoin client has multiple peer discovery methods enabled (IRC, DNS, seed nodes, etc), it might be wise to guarantee that at least one peer is selected via each method. This requires a Sybil attacker to control all peer discovery methods for a successful attack.
Quoted text (13 lines)
> To protect against this, we came up with this design: keep two tables: > one that keeps addresses we've had actual connections with, and one > that maintains untried/new addresses. Both are separated into several > limited-size buckets. Each tables provides a level of protection > against sybil attacks: > * Addresses in the first table are placed in one of only a few > buckets chosen based on the address range (/16 for IPv4). This way, an > attacker cannot have tons of active nodes in the same /16 range, and > use those to fill the table. > * Addresses in the second table are placed in one of a few buckets > chosen based on address range the information came from, instead of > the address itself. This way, an attacker spamming you with tons of > "addr" messages can only still have a limited effect.
Cool design. It seems resilient to many attacks. A Sybil attack coming from a large botnet (which controls addresses in many ranges) can still fill all buckets in both tables, I think. As far as I can tell, that wasn't possible with the old design.
Quoted text (4 lines)
> Cool design. It seems resilient to many attacks. A Sybil attack > coming from a large botnet (which controls addresses in many ranges) > can still fill all buckets in both tables, I think. As far as I can > tell, that wasn't possible with the old design.
Given the randomness in Pieter's design, that seems extremely unlikely / difficult to do. Is it possible to do a back-of-the-envelope calculation to figure out what percentage of nodes on the network an attacker would have to control to have a (say) 1% chance of a successful Sybil attack?
I like this change; I'd like to pull it for the 0.6 release.
I've also been wondering if it is time to remove the IRC bootstrapping mechanism; it would remove a fair bit of code and we'd stop getting reports that various ISPs tag bitcoin as malware. When testing the list of built-in bootstrapping IP addresses I always connect fairly quickly, and the DNS seeding hosts seems to be working nicely, too.
On Monday, January 30, 2012 9:05:49 PM Gavin Andresen wrote:
Quoted text (5 lines)
> I've also been wondering if it is time to remove the IRC bootstrapping > mechanism; it would remove a fair bit of code and we'd stop getting > reports that various ISPs tag bitcoin as malware. When testing the > list of built-in bootstrapping IP addresses I always connect fairly > quickly, and the DNS seeding hosts seems to be working nicely, too.
How about just disable it by default for 0.6 and strip it out entirely before 0.7 if there's no problems?
On Mon, Jan 30, 2012 at 9:05 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:
Quoted text (5 lines)
> I've also been wondering if it is time to remove the IRC bootstrapping > mechanism; it would remove a fair bit of code and we'd stop getting > reports that various ISPs tag bitcoin as malware. When testing the > list of built-in bootstrapping IP addresses I always connect fairly > quickly, and the DNS seeding hosts seems to be working nicely, too.
Sο— would we remove it or leave it deactivated as a fallback users can turn on?
I have two different thoughts about IRC depending on the answer.
I think it's important that we have more mechanisms then just DNS and hardcoded seednodes.
This is important because the mechanisms we have are all pretty subject to blocking. Now— before you say it— Bitcoin isn't intended to be blocking resistant (combine it with Tor and Tor anti-censorship tools) but by making blocking a bit harder we discourage people from even trying, even if we're not seriously in the anti-blocking business— and it gives bitcoin users more confidence because there is a bit less FUD "What if your ISP blocks it?? It uses DNS! Someone might take away the domains! SOPA PIPI ACTA CIPA Alakazam".
Is the fact that users can addnodes / addr.txt enough of an alternative to address this? _If so_, then removing it is a good idea. I volunteer to maintain a multi-channel joining node for the foreseeable future to avoid letting old clients get partitioned (several people need to do this).
An area where I think our mechanisms are inadequate absent IRC is announcing new nodes. I had a new listener up for over a week recently and was basically getting no inbound until I enabled IRC. I volunteer to do some measurement of this (e.g. bring up some nodes with no irc and find out how long until sipa hears about them). If DNS seeds are slow to learn about new nodes we may need to add a simple UDP announcement feature.
In any case, I hadn't been thinking that we would completely remove IRC— I was expecting us to keep IRC around but turned off.
In particular I think it may be a little risky to turn off IRC at the same time as deploying addrman, because if addrman has unexpected bad behavior IRC is what may keep things going. Obviously it should be well tested enough to feel confident, but belt-and-suspenders is the way to go.
If we do keep in the long run I think it's important to _fix_ IRC. Right now it has some really stupid behavior which is highly pro-partitioning.
*/who only returns a few nodes, and because most idlers aren't actually working (no port forward) it's usually for there to be only a few that work. (I've never seen zero, but I've seen 1). *Other than who we only learn about nodes when they join. But the stable long lived nodes we need to hear about seldom rejoin. Nonuseful windows boxes go up and down a lot. *Nodes sit in a single channel forever. There are 100 of them. Especially with fewer clients on line nodes may be sitting alone with no correctly working nodes with them. *Nodes recently seen on IRC are highly promoted in the peer selection.
So, here is an updated irc.cpp which I've been running (in various versions) for a while: http://people.xiph.org/~greg/irc.cpp
It does the following things: * Only stays connected for a half hour * If its sure its not listening it uses a random nick so people won't try to connect * Reconnects if it needs more connections * If the node is actually listening (evidence by actual incoming connections) it reconnects on its own every 1-2 hours and joins two channels at random rather than one. (it doesn't change peer selection— It's hard to be confident of the impact of that change. I think addrman makes it less of an issue)
I've only not submitted it as a pull request because I haven't had a chance to test to my standards, and because I felt unsure about the future of IRC.
I feel strongly that if we're going to keep IRC as a backup we should fix it. If we're not going to bother then thats fine— but I think we need to think carefully if we're doing enough for bootstraping (with the points I made) without it.
Certainly getting it off by default would be a good move. The botnet allegations are horrible.
On Mon, Jan 30, 2012 at 7:05 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:
Quoted text (5 lines)
> Given the randomness in Pieter's design, that seems extremely unlikely > / difficult to do. Is it possible to do a back-of-the-envelope > calculation to figure out what percentage of nodes on the network an > attacker would have to control to have a (say) 1% chance of a > successful Sybil attack?
The randomness prevents finely crafted attacks since an attacker can't predict which bucket his address ends up in. I don't think it helps against brute force attacks though. If 60% of the network's nodes are controlled by an evil botnet, 60% of the nodes we pull out of the address manager point to the attacker. If a client has 8 connections to the network, a Sybil attack would succeed 1.7% of the time. At current network size, 60% of listening nodes is 2,800; only 2-5% of a decent botnet.
Nodes that accept incoming connections are far less vulnerable, since the probability of success decreases exponentially with the number of connections. 95% botnet control with 125 connections has 10^-6 chance of success.
Perhaps we could add a command-line option for increasing the maximum number of outbound connections. That way, nodes unable to accept incoming connections can easily decrease their susceptibility to Sybil attack.
Quoted text (5 lines)
> I've also been wondering if it is time to remove the IRC bootstrapping > mechanism; it would remove a fair bit of code and we'd stop getting > reports that various ISPs tag bitcoin as malware. When testing the > list of built-in bootstrapping IP addresses I always connect fairly > quickly, and the DNS seeding hosts seems to be working nicely, too.
I think it should be disabled by default one release after the new address manager is released. That way, we're not changing too many parts of the bootstrapping process at once.
As an aside, I can't help but wonder whether ISPs blocking IRC traffic filters some botnets out of the IRC bootstrapping channels; keeping them more "pure".
On Mon, Jan 30, 2012 at 11:33 PM, Michael Hendricks <michael@ndrix•org> wrote:
Quoted text (2 lines)
> address manager point to the attacker. If a client has 8 connections > to the network, a Sybil attack would succeed 1.7% of the time.
Meh, careful not to mixup addrman created issues with preexisting ones simply related to the number of connections vs the number of nodes. Even absent addressman someone who can spin up a large multiple of the current nodes as tcp forwarders to a system they control can capture all of a nodes outbound connections.
Increasing the number of outbound connections is a very bad solution to this problem: It invites a tragedy of the commons: you get the "best" security by setting your number as high as it will let you. Who doesn't want security? Meanwhile we've come pretty close to running out of open listening ports already in the past.
There is a much more scalable improvement for those concerned about the sybil attack (I say those concerned because a sybil attack is not that fatal in bitcoin— checkpoints prevent a total fantasy chain, it's mostly but not entirely a DOS risk)...
The solution is to addnode a couple of (ideally) trusted nodes, or failing the availability of trusted nodes, a few that you think are unlikely to be mutually cooperating against you.
A single connection to the 'good' network kills isolation attacks dead, so a couple carefully selected outbound connections its a more secure remedy and one which doesn't explode the network.
Quoted text (8 lines)
> I think it's important that we have more mechanisms then just DNS and > hardcoded seednodes. > This is important because the mechanisms we have are all pretty > subject to blocking. Now— before you say it— Bitcoin isn't intended to > be blocking resistant (combine it with Tor and Tor anti-censorship > tools) > Is the fact that users can addnodes / addr.txt enough of an > alternative to address this?
Perhaps not worry about removing it too much. As above, if blocking or other issues arise, people will be hosting manual lists and nodes on hidden sites... Tor/I2P/etc. The nodes are already there. For that matter, since the nodes are talking once seeded, why not deploy a DHT and be done. All you'd need is one friendly node and the list comes in and maintains itself through node expiry rules. Your node publishes its hello for others to discover, etc. IRC, DNS, etc would go away in favor of autonomy. It wouldn't be any more resistant. But if people wanted that, some form of signatures from the hidden nodes would do... if you trusted them. Booting and running is easy, trust isn't (ask the Tor/I2P people).
On 01/30/2012 11:33 PM, Michael Hendricks wrote:
Quoted text (38 lines)
> On Mon, Jan 30, 2012 at 7:05 PM, Gavin Andresen <gavinandresen@gmail•com> wrote: >> Given the randomness in Pieter's design, that seems extremely unlikely >> / difficult to do. Is it possible to do a back-of-the-envelope >> calculation to figure out what percentage of nodes on the network an >> attacker would have to control to have a (say) 1% chance of a >> successful Sybil attack? > The randomness prevents finely crafted attacks since an attacker can't > predict which bucket his address ends up in. I don't think it helps > against brute force attacks though. If 60% of the network's nodes are > controlled by an evil botnet, 60% of the nodes we pull out of the > address manager point to the attacker. If a client has 8 connections > to the network, a Sybil attack would succeed 1.7% of the time. At > current network size, 60% of listening nodes is 2,800; only 2-5% of a > decent botnet. > > Nodes that accept incoming connections are far less vulnerable, since > the probability of success decreases exponentially with the number of > connections. 95% botnet control with 125 connections has 10^-6 chance > of success. > > Perhaps we could add a command-line option for increasing the maximum > number of outbound connections. That way, nodes unable to accept > incoming connections can easily decrease their susceptibility to Sybil > attack. > >> I've also been wondering if it is time to remove the IRC bootstrapping >> mechanism; it would remove a fair bit of code and we'd stop getting >> reports that various ISPs tag bitcoin as malware. When testing the >> list of built-in bootstrapping IP addresses I always connect fairly >> quickly, and the DNS seeding hosts seems to be working nicely, too. > I think it should be disabled by default one release after the new > address manager is released. That way, we're not changing too many > parts of the bootstrapping process at once. > > As an aside, I can't help but wonder whether ISPs blocking IRC traffic > filters some botnets out of the IRC bootstrapping channels; keeping > them more "pure". >
If the number of outbound connections is increased the delay of transaction broadcast code needs to be improved to avoid a broadcast storm.
We split IRC among all those channels to handle the load when there were 60k clients.. the ideal thing would be some kind of dynamic sizing, and this applies to the number of outbound connections and transaction relaying logic too.. the same values that work for 1k clients don't work as well for 50k. It is difficult to get this kind of thing tuned correctly, especially with the added complexity of potentially malicious nodes.
I think the observed isolation problems, with or without IRC, are simply due to there not being many bitcoin nodes leaving/joining the network. The ones that are stable are happy with their 8 connections or whatever they're set to, and they're just relaying. There are only about 5k clients on IRC now.. it would probably work to go back to the single channel model as (at least from the IRC point of view) the usage is declining not growing. Maybe people are just turning off IRC though. IRC works well with many channels having a few clients each, not with one channel having many clients. We considered probing bitcoin clients to see if they're listening and favoring those clients in the WHO response, kind of like the DNS booters, but nobody got around to doing it.
Still, I think it's good to have a bunch of different ways to bootstrap in case one or the other is broken/poisoned.
Laszlo
On Jan 31, 2012, at 2:57 AM, Gregory Maxwell wrote:
Quoted text (99 lines)
> On Mon, Jan 30, 2012 at 9:05 PM, Gavin Andresen <gavinandresen@gmail•com> wrote: >> I've also been wondering if it is time to remove the IRC bootstrapping >> mechanism; it would remove a fair bit of code and we'd stop getting >> reports that various ISPs tag bitcoin as malware. When testing the >> list of built-in bootstrapping IP addresses I always connect fairly >> quickly, and the DNS seeding hosts seems to be working nicely, too. > > Sο— would we remove it or leave it deactivated as a fallback users can turn on? > > I have two different thoughts about IRC depending on the answer. > > I think it's important that we have more mechanisms then just DNS and > hardcoded seednodes. > > This is important because the mechanisms we have are all pretty > subject to blocking. Now— before you say it— Bitcoin isn't intended to > be blocking resistant (combine it with Tor and Tor anti-censorship > tools) but by making blocking a bit harder we discourage people from > even trying, even if we're not seriously in the anti-blocking > business— and it gives bitcoin users more confidence because there is > a bit less FUD "What if your ISP blocks it?? It uses DNS! Someone > might take away the domains! SOPA PIPI ACTA CIPA Alakazam". > > Is the fact that users can addnodes / addr.txt enough of an > alternative to address this? _If so_, then removing it is a good > idea. I volunteer to maintain a multi-channel joining node for the > foreseeable future to avoid letting old clients get partitioned > (several people need to do this). > > An area where I think our mechanisms are inadequate absent IRC is > announcing new nodes. I had a new listener up for over a week recently > and was basically getting no inbound until I enabled IRC. I > volunteer to do some measurement of this (e.g. bring up some nodes > with no irc and find out how long until sipa hears about them). If > DNS seeds are slow to learn about new nodes we may need to add a > simple UDP announcement feature. > > In any case, I hadn't been thinking that we would completely remove > IRC— I was expecting us to keep IRC around but turned off. > > In particular I think it may be a little risky to turn off IRC at the > same time as deploying addrman, because if addrman has unexpected bad > behavior IRC is what may keep things going. Obviously it should be > well tested enough to feel confident, but belt-and-suspenders is the > way to go. > > > If we do keep in the long run I think it's important to _fix_ IRC. > Right now it has some really stupid behavior which is highly > pro-partitioning. > > */who only returns a few nodes, and because most idlers aren't > actually working (no port forward) it's usually for there to be only a > few that work. (I've never seen zero, but I've seen 1). > *Other than who we only learn about nodes when they join. But the > stable long lived nodes we need to hear about seldom rejoin. Nonuseful > windows boxes go up and down a lot. > *Nodes sit in a single channel forever. There are 100 of them. > Especially with fewer clients on line nodes may be sitting alone with > no correctly working nodes with them. > *Nodes recently seen on IRC are highly promoted in the peer selection. > > So, here is an updated irc.cpp which I've been running (in various > versions) for a while: > http://people.xiph.org/~greg/irc.cpp > > It does the following things: > * Only stays connected for a half hour > * If its sure its not listening it uses a random nick so people won't > try to connect > * Reconnects if it needs more connections > * If the node is actually listening (evidence by actual incoming > connections) it reconnects on its own every 1-2 hours and joins two > channels at random rather than one. > (it doesn't change peer selection— It's hard to be confident of the > impact of that change. I think addrman makes it less of an issue) > > I've only not submitted it as a pull request because I haven't had a > chance to test to my standards, and because I felt unsure about the > future of IRC. > > I feel strongly that if we're going to keep IRC as a backup we should > fix it. If we're not going to bother then thats fine— but I think we > need to think carefully if we're doing enough for bootstraping (with > the points I made) without it. > > Certainly getting it off by default would be a good move. The botnet > allegations are horrible. > > ------------------------------------------------------------------------------ > Keep Your Developer Skills Current with LearnDevNow! > The most comprehensive online learning library for Microsoft developers > is just $99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3, > Metro Style Apps, more. Free future releases when you subscribe now! > http://p.sf.net/sfu/learndevnow-d2d > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
On Tue, Jan 31, 2012 at 12:17 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
Quoted text (9 lines)
> On Mon, Jan 30, 2012 at 11:33 PM, Michael Hendricks <michael@ndrix•org> wrote: >> address manager point to the attacker. If a client has 8 connections >> to the network, a Sybil attack would succeed 1.7% of the time. > > Meh, careful not to mixup addrman created issues with preexisting ones > simply related to the number of connections vs the number of nodes. > Even absent addressman someone who can spin up a large multiple of the > current nodes as tcp forwarders to a system they control can capture > all of a nodes outbound connections.
I think I've explained myself poorly. On my nodes, the old address database routinely has 120k addresses. With the new address manager, it will have 20k addresses. Filling the former with 60% evil nodes requires 72,000 evil nodes; while the latter requires 12,000.
As I mentioned in my first post, I think the new address manager "is a valuable improvement over what we have today". I think it should be included in the next release.
I also think we should be aware that we're making it somewhat easier to isolate outbound-only nodes. A single listening node can support 15 non-listening nodes (125/8). The network currently has 5 non-listening nodes for every listening node. That ratio has stayed quite stable, so I think we have wiggle room if we wanted to allow more outbound connections in some circumstances.
On Tue, Jan 31, 2012 at 12:17 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
Quoted text (9 lines)
> On Mon, Jan 30, 2012 at 11:33 PM, Michael Hendricks <michael@ndrix•org> wrote: >> address manager point to the attacker. If a client has 8 connections >> to the network, a Sybil attack would succeed 1.7% of the time. > > Meh, careful not to mixup addrman created issues with preexisting ones > simply related to the number of connections vs the number of nodes. > Even absent addressman someone who can spin up a large multiple of the > current nodes as tcp forwarders to a system they control can capture > all of a nodes outbound connections.
I think I've explained myself poorly. On my nodes, the old address database routinely has 120k addresses. With the new address manager, it will have 20k addresses. Filling the former with 60% evil nodes requires 72,000 evil nodes; while the latter requires 12,000.
As I mentioned in my first post, I think the new address manager "is a valuable improvement over what we have today". I think it should be included in the next release.
I also think we should be aware that we're making it somewhat easier to isolate outbound-only nodes. A single listening node can support 15 non-listening nodes (125/8). The network currently has 5 non-listening nodes for every listening node. That ratio has stayed quite stable, so I think we have wiggle room if we wanted to allow more outbound connections in some circumstances.