Countermeasures against eclipse attacks #5941

pull sipa wants to merge 6 commits into bitcoin:master from sipa:betteraddrman changing 3 files +260 −244
  1. sipa commented at 0:26 am on March 24, 2015: member
    This implements countermeasures 1, 2, and 6 from the http://cs-people.bu.edu/heilman/eclipse/ paper.
  2. Switch addrman key from vector to uint256 b23add5521
  3. Make addrman's bucket placement deterministic. 
    Give each address a single fixed location in the new and tried tables,
which become simple fixed-size arrays instead of sets and vectors.

This prevents attackers from having an advantages by inserting an
address multiple times.

This change was suggested as Countermeasure 1 in
Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman,
Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report
2015/263. March 2015.

It is also more efficient.
    e6b343d880
  4. Simplify hashing code a8ff7c62ed
  5. Do not bias outgoing connections towards fresh addresses 
    This change was suggested as Countermeasure 2 in
Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman,
Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report
2015/263. March 2015.
    f68ba3f67b
  6. Always use a 50% chance to choose between tried and new entries 
    This change was suggested as Countermeasure 2 in
Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman,
Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report
2015/263. March 2015.
    c6a63ceeb4
  7. Scale up addrman 
    This change was suggested as Countermeasure 6 in
Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman,
Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report
2015/263. March 2015.
    1d21ba2f5e
  8. laanwj added the label Priority High on Mar 24, 2015
  9. laanwj added the label P2P on Mar 24, 2015
  10. laanwj added this to the milestone 0.10.0 on Mar 24, 2015
  11. sipa commented at 11:59 am on March 24, 2015: member
    Someone should test how long it takes to find peers with this, when DNS seeding and the built-in seeds are disabled. I’m not able to test the next ~3 days or so.
  12. sipa commented at 1:00 pm on March 24, 2015: member
    This is running on bitcoin.sipa.be, with -DDEBUG_ADDRMAN enabled.
  13. laanwj commented at 1:54 pm on March 24, 2015: member

    Going to test this.

    Someone should test how long it takes to find peers with this, when DNS seeding and the built-in seeds are disabled.

    OK, disabling those.

  14. jgarzik commented at 1:57 pm on March 24, 2015: contributor

    Typically, (a) less than 11 seconds if you have a fresh addrman, or (b) sometimes hours or longer, if not.

    Current code skips DNS seeds & built in seeds automatically, if it manages to connect to some peers within a short amount of time.

  15. sipa commented at 2:05 pm on March 24, 2015: member
    @jgarzik I mean after this patch. Reason is the bias changes in peer selection. If you have very few tried peers, the new code will likely very actively keep retrying those (as there is a 50% chance to pick a previously tried peer), and there is no bias towards more recently learned addresses anymore. Both probably slow down initial connection, but likely don’t have that much impact in a working system.
  16. laanwj commented at 2:06 pm on March 24, 2015: member

    It instantly found a peer on start:

    02015-03-24 13:55:51 init message: Loading addresses...
12015-03-24 13:55:51 Loaded 14669 addresses from peers.dat  664ms
2...
32015-03-24 13:55:51 receive version message: /Satoshi:0.9.2/: version 70002, blocks=346129, ...
  17. gavinandresen commented at 8:18 pm on March 24, 2015: contributor

    Ran this with -dnsseed=0 and a peers.dat from a bitcoind that I stopped 23 hours ago:

     02015-03-24 20:15:18 Loaded 12904 addresses from peers.dat  512ms
 1   ...
 22015-03-24 20:15:30 connect() to 93.143.11.182:8333 failed after select(): Connection refused (61)
 32015-03-24 20:16:15 connect() to 85.199.110.252:8333 failed after select(): Connection refused (61)
 42015-03-24 20:16:16 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349059, us=...., peer=1
 5 ...
 62015-03-24 20:16:28 receive version message: /Satoshi:0.9.1/: version 70002, blocks=349059, us=..., peer=2
 7...
 82015-03-24 20:17:09 receive version message: /Marilyn:0.9.99/: version 70002, blocks=30160, us=..., peer=3
 9...
102015-03-24 20:17:15 connect() to 82.130.103.162:8333 failed after select(): Connection refused (61)
11...
122015-03-24 20:17:44 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349059, us=..., peer=4

    … so just under one minute to connect to first peer, and it looks like it is finding about a peer a minute.

  18. ghost commented at 10:21 pm on March 24, 2015: none

    utAck. The paper does not specify a countermeasure “6” in Section 7.

    We’ve still got a bit to go (the symptoms being #5886, #5397, #5352, #5299), but great to see the attention on P2P. Let it remind us that P2P is at the (decentralized) core of Bitcoin Core as much as transactions are; arguably more so.

  19. sipa commented at 11:01 pm on March 24, 2015: member
    21E14: there are further countermeasures listed in the appendix.
  20. ghost commented at 0:11 am on March 25, 2015: none

    It’s worth pointing out.

    This may also be a good opportunity to tilt the balance of preprocessor directives vs “magic” values, e.g. ADDRMAN_TRIED_BUCKETS_PER_GROUP (2 occurrences) vs 24 * 60 * 60 & 60 * 10.

    Interestingly, P2P is not very well reflected in the ongoing libification. As it stands, libbitcoin_server is its closest anchor, but the two are arguably distinct. A large subset of the protocol is arguably entirely P2P (ver, verack, ping, pong, inv, getheaders, …).

  21. fanquake commented at 3:35 am on March 26, 2015: member

    Running with -dnsseed=0

    02015-03-26 03:21:39 init message: Loading addresses...
12015-03-26 03:21:39 Loaded 12984 addresses from peers.dat  94ms
22015-03-26 03:21:39 DNS seeding disabled
32015-03-26 03:21:40 connect() to 199.167.100.226:8333 failed after select(): Connection refused (61)
42015-03-26 03:21:52 receive version message: /Satoshi:0.9.3/: version 70002, blocks=349268, us=..., peer=1
52015-03-26 03:21:58 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349268, us=..., peer=2
62015-03-26 03:22:05 receive version message: /Satoshi:0.9.2.1/: version 70002, blocks=349268, us=..., peer=3
72015-03-26 03:22:16 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349268, us=..., peer=4

    Removed peers.dat

    02015-03-26 03:28:42 init message: Loading addresses...
12015-03-26 03:28:42 Loaded 0 addresses from peers.dat  1ms
22015-03-26 03:28:42 dnsseed thread start
32015-03-26 03:28:44 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349269, us=..., peer=1
42015-03-26 03:28:45 72 addresses found from DNS seeds
52015-03-26 03:28:45 dnsseed thread exit
62015-03-26 03:28:46 receive version message: /Satoshi:0.8.6/: version 70001, blocks=349269, us=..., peer=2
72015-03-26 03:28:47 receive version message: /Satoshi:0.10.0/: version 70002, blocks=349269, us=..., peer=3
82015-03-26 03:28:56 receive version message: /Satoshi:0.9.3/: version 70002, blocks=349269, us=..., peer=4
  22. sipa commented at 6:41 pm on March 27, 2015: member
    I tried a few times with -dnsseed=0 and a copy of bitcoin.sipa.be’s peers.dat, and always had an initial connection between 15 and 30 seconds later.
  23. laanwj commented at 2:44 pm on March 30, 2015: member
    Works for me - tested ACK
  24. gmaxwell commented at 4:31 pm on March 30, 2015: contributor
    ACK.
  25. jgarzik commented at 4:38 pm on March 30, 2015: contributor

    ut ACK

    My only nit: I wonder if we could replace that ‘%’ with a shift. Could be, if the powers [of two] are aligned.

  26. sipa commented at 5:05 pm on March 30, 2015: member
    At -O2, gcc does strength reduction which should turns the modulo operations into bitmasking.
  27. jgarzik commented at 5:22 pm on March 30, 2015: contributor
    @sipa should, agreed. With our 256 bit C++ implemented integer type, I wonder if that is true?
  28. sipa commented at 5:37 pm on March 30, 2015: member

    There are no uint256’s involved in the modulus operations. Hashing is performed, then the lower 64 bits are extracted, and then a modulus is applied.

    Besides, uint256 does not even offer arithmetic operations anymore. It’s just an encapsulated 256-size bit vector.

  29. laanwj merged this on Apr 1, 2015
  30. laanwj closed this on Apr 1, 2015
  31. laanwj referenced this in commit f7dea1cba7 on Apr 1, 2015
  32. sipa referenced this in commit b788994256 on Apr 1, 2015
  33. sipa referenced this in commit cf0218f8b2 on Apr 1, 2015
  34. sipa referenced this in commit 2218d4bbe0 on Apr 1, 2015
  35. sipa referenced this in commit 214154e6fc on Apr 1, 2015
  36. sipa referenced this in commit 0c6f334c32 on Apr 1, 2015
  37. sipa referenced this in commit aa587d4cae on Apr 1, 2015
  38. laanwj commented at 2:42 pm on April 1, 2015: member
    Cherry-picked to 0.10 as aa587d4 0c6f334 214154e 2218d4b cf0218f b788994 Some conflicts encountered with uint256 usage, but was easy to backport.
  39. laanwj referenced this in commit ae1479a114 on Apr 1, 2015
  40. theuni referenced this in commit 3c3c4fa518 on Apr 23, 2015
  41. dexX7 referenced this in commit 88d6c5eb95 on Apr 27, 2015
  42. theuni referenced this in commit 605a735425 on May 14, 2015
  43. dexX7 referenced this in commit 0dcd7f203f on May 16, 2015
  44. reddink referenced this in commit 8b90a7da1b on May 27, 2020
  45. reddink referenced this in commit f79dcd9594 on May 27, 2020
  46. reddink referenced this in commit 2a18b01677 on May 27, 2020
  47. reddink referenced this in commit fdd5083a01 on May 27, 2020
  48. reddink referenced this in commit 22b97dd50d on May 27, 2020
  49. reddink referenced this in commit 92dd498f55 on May 27, 2020
  50. reddink referenced this in commit 878521f691 on May 27, 2020
  51. vasild referenced this in commit 7bd598a23b on Nov 2, 2020
  52. vasild referenced this in commit 00187c364b on Nov 2, 2020
  53. vasild referenced this in commit 5cde641689 on Nov 2, 2020
  54. vasild referenced this in commit 1c60aba1da on Nov 10, 2020
  55. vasild referenced this in commit eaa04bec65 on Nov 10, 2020
  56. vasild referenced this in commit b303dc0d1d on Nov 10, 2020
  57. vasild referenced this in commit 2ed531dfcd on Nov 11, 2020
  58. vasild referenced this in commit 204678cf42 on Nov 11, 2020
  59. vasild referenced this in commit 38ada892ed on Nov 11, 2020
  60. laanwj referenced this in commit 0bd4929cd0 on Nov 12, 2020
  61. sidhujag referenced this in commit 216ac49972 on Nov 12, 2020
  62. willyko referenced this in commit 93a6d72c96 on Nov 12, 2020
  63. janus referenced this in commit dffff7273a on Dec 13, 2020
  64. deadalnix referenced this in commit 5be9d5e9c4 on Feb 11, 2021
  65. furszy referenced this in commit 643baad5c1 on Jul 29, 2021
  66. furszy referenced this in commit c2c11f8ca1 on Jul 30, 2021
  67. furszy referenced this in commit df5fcdb1c1 on Jul 31, 2021
  68. furszy referenced this in commit a5e1635e92 on Aug 1, 2021
  69. fanquake referenced this in commit 3308c61091 on Aug 4, 2021
  70. sidhujag referenced this in commit b04bed5bee on Aug 4, 2021
  71. furszy referenced this in commit 86543a3718 on Aug 4, 2021
  72. furszy referenced this in commit 400706d2a9 on Aug 5, 2021
  73. furszy referenced this in commit 13cc19e197 on Aug 8, 2021
  74. furszy referenced this in commit 89df7f2b00 on Aug 10, 2021
  75. MarcoFalke locked this on Sep 8, 2021


sipa laanwj jgarzik gavinandresen ghost fanquake gmaxwell

Labels
P2P

Milestone
0.10.0

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-17 15:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me