* [Bitcoin-development] CAddrMan: Stochastic IP address manager
@ 2012-01-30 2:31 Pieter Wuille
2012-01-30 2:37 ` Luke-Jr
2012-01-30 16:53 ` Michael Hendricks
0 siblings, 2 replies; 13+ messages in thread
From: Pieter Wuille @ 2012-01-30 2:31 UTC (permalink / raw)
To: bitcoin-development
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.
--
Pieter
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-30 2:31 [Bitcoin-development] CAddrMan: Stochastic IP address manager Pieter Wuille
@ 2012-01-30 2:37 ` Luke-Jr
2012-01-30 16:53 ` Michael Hendricks
1 sibling, 0 replies; 13+ messages in thread
From: Luke-Jr @ 2012-01-30 2:37 UTC (permalink / raw)
To: Pieter Wuille; +Cc: bitcoin-development
On Sunday, January 29, 2012 9:31:02 PM Pieter Wuille wrote:
> 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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-30 2:31 [Bitcoin-development] CAddrMan: Stochastic IP address manager Pieter Wuille
2012-01-30 2:37 ` Luke-Jr
@ 2012-01-30 16:53 ` Michael Hendricks
2012-01-31 2:05 ` Gavin Andresen
1 sibling, 1 reply; 13+ messages in thread
From: Michael Hendricks @ 2012-01-30 16:53 UTC (permalink / raw)
To: Pieter Wuille; +Cc: bitcoin-development
On Sun, Jan 29, 2012 at 7:31 PM, Pieter Wuille <pieter.wuille@gmail•com> wrote:
> 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.
> 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.
> 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.
> 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.
--
Michael
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-30 16:53 ` Michael Hendricks
@ 2012-01-31 2:05 ` Gavin Andresen
2012-01-31 2:07 ` Luke-Jr
` (2 more replies)
0 siblings, 3 replies; 13+ messages in thread
From: Gavin Andresen @ 2012-01-31 2:05 UTC (permalink / raw)
To: Michael Hendricks; +Cc: bitcoin-development
> 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.
--
--
Gavin Andresen
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 2:05 ` Gavin Andresen
@ 2012-01-31 2:07 ` Luke-Jr
2012-01-31 2:57 ` Gregory Maxwell
2012-01-31 4:33 ` Michael Hendricks
2 siblings, 0 replies; 13+ messages in thread
From: Luke-Jr @ 2012-01-31 2:07 UTC (permalink / raw)
To: bitcoin-development
On Monday, January 30, 2012 9:05:49 PM Gavin Andresen 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.
How about just disable it by default for 0.6 and strip it out entirely before
0.7 if there's no problems?
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 2:05 ` Gavin Andresen
2012-01-31 2:07 ` Luke-Jr
@ 2012-01-31 2:57 ` Gregory Maxwell
2012-01-31 8:19 ` grarpamp
2012-01-31 13:50 ` solar
2012-01-31 4:33 ` Michael Hendricks
2 siblings, 2 replies; 13+ messages in thread
From: Gregory Maxwell @ 2012-01-31 2:57 UTC (permalink / raw)
To: Gavin Andresen; +Cc: bitcoin-development
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 2:57 ` Gregory Maxwell
@ 2012-01-31 8:19 ` grarpamp
2012-01-31 13:50 ` solar
1 sibling, 0 replies; 13+ messages in thread
From: grarpamp @ 2012-01-31 8:19 UTC (permalink / raw)
To: bitcoin-development
> 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).
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 2:57 ` Gregory Maxwell
2012-01-31 8:19 ` grarpamp
@ 2012-01-31 13:50 ` solar
1 sibling, 0 replies; 13+ messages in thread
From: solar @ 2012-01-31 13:50 UTC (permalink / raw)
To: bitcoin-development
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:
> 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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 2:05 ` Gavin Andresen
2012-01-31 2:07 ` Luke-Jr
2012-01-31 2:57 ` Gregory Maxwell
@ 2012-01-31 4:33 ` Michael Hendricks
2012-01-31 7:17 ` Gregory Maxwell
2012-01-31 9:21 ` Phantomcircuit
2 siblings, 2 replies; 13+ messages in thread
From: Michael Hendricks @ 2012-01-31 4:33 UTC (permalink / raw)
To: Gavin Andresen; +Cc: bitcoin-development
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".
--
Michael
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 4:33 ` Michael Hendricks
@ 2012-01-31 7:17 ` Gregory Maxwell
2012-01-31 15:06 ` Michael Hendricks
2012-01-31 15:07 ` Michael Hendricks
2012-01-31 9:21 ` Phantomcircuit
1 sibling, 2 replies; 13+ messages in thread
From: Gregory Maxwell @ 2012-01-31 7:17 UTC (permalink / raw)
To: Michael Hendricks; +Cc: bitcoin-development
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.
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 7:17 ` Gregory Maxwell
@ 2012-01-31 15:06 ` Michael Hendricks
2012-01-31 15:07 ` Michael Hendricks
1 sibling, 0 replies; 13+ messages in thread
From: Michael Hendricks @ 2012-01-31 15:06 UTC (permalink / raw)
To: Gregory Maxwell; +Cc: bitcoin-development
On Tue, Jan 31, 2012 at 12:17 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
> 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.
--
Michael
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 7:17 ` Gregory Maxwell
2012-01-31 15:06 ` Michael Hendricks
@ 2012-01-31 15:07 ` Michael Hendricks
1 sibling, 0 replies; 13+ messages in thread
From: Michael Hendricks @ 2012-01-31 15:07 UTC (permalink / raw)
To: Gregory Maxwell; +Cc: bitcoin-development
On Tue, Jan 31, 2012 at 12:17 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
> 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.
--
Michael
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Bitcoin-development] CAddrMan: Stochastic IP address manager
2012-01-31 4:33 ` Michael Hendricks
2012-01-31 7:17 ` Gregory Maxwell
@ 2012-01-31 9:21 ` Phantomcircuit
1 sibling, 0 replies; 13+ messages in thread
From: Phantomcircuit @ 2012-01-31 9:21 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 2305 bytes --]
On 01/30/2012 11:33 PM, Michael Hendricks wrote:
> 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.
[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4515 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2012-01-31 15:07 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-01-30 2:31 [Bitcoin-development] CAddrMan: Stochastic IP address manager Pieter Wuille
2012-01-30 2:37 ` Luke-Jr
2012-01-30 16:53 ` Michael Hendricks
2012-01-31 2:05 ` Gavin Andresen
2012-01-31 2:07 ` Luke-Jr
2012-01-31 2:57 ` Gregory Maxwell
2012-01-31 8:19 ` grarpamp
2012-01-31 13:50 ` solar
2012-01-31 4:33 ` Michael Hendricks
2012-01-31 7:17 ` Gregory Maxwell
2012-01-31 15:06 ` Michael Hendricks
2012-01-31 15:07 ` Michael Hendricks
2012-01-31 9:21 ` Phantomcircuit
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox