1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
helo=mx.sourceforge.net)
by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <pieter.wuille@gmail.com>) id 1Rrh1R-00023U-6O
for bitcoin-development@lists.sourceforge.net;
Mon, 30 Jan 2012 02:31:09 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
designates 74.125.82.53 as permitted sender)
client-ip=74.125.82.53; envelope-from=pieter.wuille@gmail.com;
helo=mail-ww0-f53.google.com;
Received: from mail-ww0-f53.google.com ([74.125.82.53])
by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-MD5:128)
(Exim 4.76) id 1Rrh1Q-0004Mc-55
for bitcoin-development@lists.sourceforge.net;
Mon, 30 Jan 2012 02:31:09 +0000
Received: by wgbdr12 with SMTP id dr12so4111810wgb.10
for <bitcoin-development@lists.sourceforge.net>;
Sun, 29 Jan 2012 18:31:02 -0800 (PST)
MIME-Version: 1.0
Received: by 10.180.76.235 with SMTP id n11mr25134094wiw.11.1327890662132;
Sun, 29 Jan 2012 18:31:02 -0800 (PST)
Received: by 10.223.83.199 with HTTP; Sun, 29 Jan 2012 18:31:02 -0800 (PST)
Date: Mon, 30 Jan 2012 03:31:02 +0100
Message-ID: <CAPg+sBjNTS3n8Q3XzZi5GpBL6k_-4AxRKr0BkWa=-AAVgqS=2Q@mail.gmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
To: bitcoin-development@lists.sourceforge.net
Content-Type: text/plain; charset=ISO-8859-1
X-Spam-Score: -1.6 (-)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(pieter.wuille[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1Rrh1Q-0004Mc-55
Subject: [Bitcoin-development] CAddrMan: Stochastic IP address manager
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Mon, 30 Jan 2012 02:31:09 -0000
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
|
