These changes implement countermeasures 3 (feeler connections) and 4 (test-before-evict) suggested in our paper: “Eclipse Attacks on Bitcoin’s Peer-to-Peer Network”.
Design:
The primary change is the creation of a feeler connection thread. Every 2 minutes this feeler thread launches one feeler connection, increasing the default number of max outgoing connections to 9. Feeler connections are very short lived and disconnect upon verifying the tested host is running bitcoind. Feeler connections exist only to test if the remote host to test is online. The feeler thread pulls the addresses to test from two sources:
Source 1. Tried table collisions. A collision occurs when an address, addr1, is being moved to the tried table from the new table, but maps to a position in the tried table which already contains an address. This change ensures that during a collision, addr1 is not inserted into tried but instead inserted into a buffer. The to-be-evicted address, addr2, is then tested by the feeler thread. If addr2 is found to be online, we remove addr1 from the buffer and addr2 is not evicted, on the other hand if addr2 is found be offline it is replaced by addr1.
Source 2. The new table. If the feeler thread has no tried table collisions to be tested, it selects an address from the new table. It does this to grow the number of fresh (recently online) addresses in the tried table.
Advantages:
- In our paper we sample several peer lists. We found that a large percentage of addresses in tried tables are stale IP addresses (the lowest was 72 percent stale, the highest was 95 percent stale), which increases the risk of eclipse attacks. This change remedies this by ensuring that the tried table grows quickly and contains many recently online addresses. Countermeasure 4 (feeler connections) strengthens countermeasure 3 (test-before-evict).
- Another small side advantage is that, as no more than ten addresses can be in the test buffer at once, and addresses are only cleared one at a time from the test buffer, an attacker is forced to wait at least two minutes to insert a new address into tried after filling up the test buffer. This rate limits an attacker attempting to launch an eclipse attack.
See our paper for a full analysis of the benefits of these countermeasures.
Risk mitigation:
- To prevent this functionality from being used as a DoS vector, we limit the number of addresses which are to be tested to ten. If we have more than ten addresses to test, we drop new addresses being added to tried if they would evict an address. Since the feeler thread only creates one new connection every 2 minutes the additional network overhead is limited.
- An address in tried gains immunity from tests for 4 hours after it has been tested or successfully connected to.
- To avoid issues of synchronization, the feeler thread sleeps for between 0 and 3 seconds prior to making a connection.
Tests:
We ran an instance with our changes for two days against our in house developed attack code to induce many collisions in the tried table. Under these conditions we used valgrind to look for memory leaks. See output of the test here:
0e0@ubuntu:~/bitcoin-fork/src$ valgrind ./bitcoind -debug -printtoconsole -testnet > output.txt
1==1918== Memcheck, a memory error detector
2==1918== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
3==1918== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
4==1918== Command: ./bitcoind -debug -printtoconsole -testnet
5==1918==
6^C==1918==
7==1918== HEAP SUMMARY:
8==1918== in use at exit: 3,864 bytes in 16 blocks
9==1918== total heap usage: 224,281,816 allocs, 224,281,800 frees, 32,337,629,302 bytes allocated
10==1918==
11==1918== LEAK SUMMARY:
12==1918== definitely lost: 0 bytes in 0 blocks
13==1918== indirectly lost: 0 bytes in 0 blocks
14==1918== possibly lost: 304 bytes in 1 blocks
15==1918== still reachable: 3,560 bytes in 15 blocks
16==1918== suppressed: 0 bytes in 0 blocks
17==1918== Rerun with --leak-check=full to see details of leaked memory
18==1918==
19==1918== For counts of detected and suppressed errors, rerun with: -v
20==1918== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
As we have made some cosmetic code changes since this test was run we are rerunning this test and will update this pull request when it is finished. We are launching several test nodes.
If you want to test my code, and you don’t want to simulate a large number of incoming connections, you need to generate a bunch of collisions that would trigger feeler connections. The way to do this is to reduce the the number of buckets in tried to 1. (That way, every address inserted into tried will have a high probability (at least p=1/64) to be a collision.)
addrman_tests.cpp contains unit tests for the code I added to addrman. As a small side note, because addrman bucket placement depends on a randomly chosen seed (nKey) I needed to create a method to set this seed to a known value so that the unit tests would be deterministic. This method is only available during the addrman unittests.
