Increase the ip address relay branching factor for unreachable networks

sipa commented at 5:57 am on August 15, 2020: member

Onion addresses propagate very badly among the IPv4/IPv6 network, resulting in difficulty for those to find each other.

The branching factor 1 is probably so low that propagations die out before they reach another onion peer. Increase it to 1.5 on average.

fanquake added the label P2P on Aug 15, 2020

Onion addresses propagate very badly among the IPv4/IPv6 network, resulting
in difficulty for those to find each other.

The branching factor 1 is probably so low that propagations die out before
they reach another onion peer. Increase it to 1.5 on average.

86d4cf42d9

sipa force-pushed on Aug 15, 2020

jonatack commented at 6:12 am on August 15, 2020: member

Concept ACK

luke-jr referenced this in commit 3116771e53 on Aug 16, 2020

practicalswift commented at 6:49 am on August 16, 2020: contributor

Concept ACK

jonatack commented at 3:42 pm on August 18, 2020: member

ACK 86d4cf42d97abf4c436d1eabf29e2ed150f69c1e. Code review, built and running with some sanity check logging. RelayAddress() is called by ProcessMessage() ADDR msg handling, from within the loop while processing each new address to relay it to a limited number of other nodes. According to git blame, the line setting nRelayNodes hasn’t been touched since 2016 in e736772c56a Move network-msg-processing code out of main to its own file, which moved the line but otherwise did not change it. Running a mixed clearnet/onion node with this patch and the logging below, I’m only seeing values of fReachable 1, nRelayNodes 2. IIUC, I need to use the settings in init.cpp that call SetReachable(*, false). Edit: with onlynet=onion am now seeing entries of fReachable 0 with nRelayNodes values of 1 and 2.

 0diff --git a/src/net_processing.cpp b/src/net_processing.cpp
 1index d637abcef3..bbe8073171 100644
 2--- a/src/net_processing.cpp
 3+++ b/src/net_processing.cpp
 4@@ -1488,10 +1488,13 @@ static void RelayAddress(const CAddress& addr, bool fReachable, const CConnman&
 5     uint64_t hashAddr = addr.GetHash();
 6     const CSipHasher hasher = connman.GetDeterministicRandomizer(RANDOMIZER_ID_ADDRESS_RELAY).Write(hashAddr << 32).Write((GetTime() + hashAddr) / (24 * 60 * 60));
 7     FastRandomContext insecure_rand;
 8+    uint64_t finalized = hasher.Finalize();
 9+    uint64_t bitwise_and_1 = finalized & 1;
10 
11     // Relay reachable addresses to 2 peers. Unreachable addresses are relayed randomly to 1 or 2 peers.
12-    unsigned int nRelayNodes = (fReachable || (hasher.Finalize() & 1)) ? 2 : 1;
13-
14+    unsigned int nRelayNodes = (fReachable || bitwise_and_1) ? 2 : 1;
15+    LogPrintf("RelayAddress hasher.Finalize() %lu, hasher & 1: %lu, fReachable %u, nRelayNodes %u\n", finalized, bitwise_and_1, fReachable, nRelayNodes);

 02020-08-18T15:31:09Z RelayAddress hasher.Finalize() 1664677747050559416, hasher & 1: 0, fReachable 1, nRelayNodes 2
 12020-08-18T15:31:09Z RelayAddress hasher.Finalize() 14731061525372265962, hasher & 1: 0, fReachable 1, nRelayNodes 2
 22020-08-18T15:31:22Z RelayAddress hasher.Finalize() 1787604340311053927, hasher & 1: 1, fReachable 1, nRelayNodes 2
 32020-08-18T15:31:28Z RelayAddress hasher.Finalize() 10657425253237162609, hasher & 1: 1, fReachable 1, nRelayNodes 2
 42020-08-18T15:31:28Z RelayAddress hasher.Finalize() 18319025149127497798, hasher & 1: 0, fReachable 1, nRelayNodes 2
 52020-08-18T15:31:28Z RelayAddress hasher.Finalize() 11453563408777926184, hasher & 1: 0, fReachable 1, nRelayNodes 2
 62020-08-18T15:31:28Z RelayAddress hasher.Finalize() 4017958700527958668, hasher & 1: 0, fReachable 1, nRelayNodes 2
 72020-08-18T15:31:28Z RelayAddress hasher.Finalize() 15886276406873487556, hasher & 1: 0, fReachable 1, nRelayNodes 2
 82020-08-18T15:31:28Z RelayAddress hasher.Finalize() 1898157685244540934, hasher & 1: 0, fReachable 1, nRelayNodes 2
 92020-08-18T15:31:28Z RelayAddress hasher.Finalize() 6290607360332194442, hasher & 1: 0, fReachable 1, nRelayNodes 2
102020-08-18T15:31:28Z RelayAddress hasher.Finalize() 5437874294151945053, hasher & 1: 1, fReachable 1, nRelayNodes 2
112020-08-18T15:31:28Z RelayAddress hasher.Finalize() 12907605550886134159, hasher & 1: 1, fReachable 1, nRelayNodes 2
122020-08-18T15:31:48Z RelayAddress hasher.Finalize() 10815737377431984780, hasher & 1: 0, fReachable 1, nRelayNodes 2
132020-08-18T15:31:54Z RelayAddress hasher.Finalize() 11087211122310743638, hasher & 1: 0, fReachable 1, nRelayNodes 2
142020-08-18T15:31:54Z RelayAddress hasher.Finalize() 409429789437464070, hasher & 1: 0, fReachable 1, nRelayNodes 2
152020-08-18T15:31:54Z RelayAddress hasher.Finalize() 12052452800598648185, hasher & 1: 1, fReachable 1, nRelayNodes 2
162020-08-18T15:31:54Z RelayAddress hasher.Finalize() 14040897625625156503, hasher & 1: 1, fReachable 1, nRelayNodes 2
172020-08-18T15:31:54Z RelayAddress hasher.Finalize() 9203608419962065951, hasher & 1: 1, fReachable 1, nRelayNodes 2
182020-08-18T15:31:54Z RelayAddress hasher.Finalize() 5316736545182478283, hasher & 1: 1, fReachable 1, nRelayNodes 2
192020-08-18T15:31:54Z RelayAddress hasher.Finalize() 10617593508301706293, hasher & 1: 1, fReachable 1, nRelayNodes 2
202020-08-18T15:31:54Z RelayAddress hasher.Finalize() 923666841117585603, hasher & 1: 1, fReachable 1, nRelayNodes 2
212020-08-18T15:32:10Z RelayAddress hasher.Finalize() 9832582743135619765, hasher & 1: 1, fReachable 1, nRelayNodes 2
222020-08-18T15:32:10Z RelayAddress hasher.Finalize() 5795304938231743402, hasher & 1: 0, fReachable 1, nRelayNodes 2
232020-08-18T15:32:15Z RelayAddress hasher.Finalize() 1016101328609244348, hasher & 1: 0, fReachable 1, nRelayNodes 2
242020-08-18T15:32:16Z RelayAddress hasher.Finalize() 300853884246103755, hasher & 1: 1, fReachable 1, nRelayNodes 2

jonatack commented at 5:09 pm on August 18, 2020: member

With onlynet=onion, proxy=127.0.0.1:9050, externalip=****.onion, bind=127.0.0.1, listen=1:

 02020-08-18T17:05:38Z RelayAddress h.finalized 4068200345127824492, &1: 0, fReachable 1, nRelayNodes 2
 12020-08-18T17:05:38Z RelayAddress h.finalized 14333925968780995702, &1: 0, fReachable 0, nRelayNodes 1
 22020-08-18T17:05:38Z RelayAddress h.finalized 7071100194704352672, &1: 0, fReachable 1, nRelayNodes 2
 32020-08-18T17:05:39Z RelayAddress h.finalized 195717758224480417, &1: 1, fReachable 1, nRelayNodes 2
 42020-08-18T17:05:45Z RelayAddress h.finalized 16817619203046534136, &1: 0, fReachable 1, nRelayNodes 2
 52020-08-18T17:06:13Z RelayAddress h.finalized 7552585319767041328, &1: 0, fReachable 0, nRelayNodes 1
 62020-08-18T17:06:13Z RelayAddress h.finalized 2109471816673549627, &1: 1, fReachable 0, nRelayNodes 2
 72020-08-18T17:06:13Z RelayAddress h.finalized 11995838901279751680, &1: 0, fReachable 1, nRelayNodes 2
 82020-08-18T17:06:13Z RelayAddress h.finalized 3893398105305938194, &1: 0, fReachable 0, nRelayNodes 1
 92020-08-18T17:06:14Z RelayAddress h.finalized 8161172177677664072, &1: 0, fReachable 0, nRelayNodes 1
102020-08-18T17:06:24Z RelayAddress h.finalized 10465762448033642779, &1: 1, fReachable 0, nRelayNodes 2
112020-08-18T17:06:24Z RelayAddress h.finalized 18393435326660999961, &1: 1, fReachable 0, nRelayNodes 2
122020-08-18T17:06:24Z RelayAddress h.finalized 4267516420658618872, &1: 0, fReachable 0, nRelayNodes 1
132020-08-18T17:06:54Z RelayAddress h.finalized 15906259941719365967, &1: 1, fReachable 1, nRelayNodes 2
142020-08-18T17:07:16Z RelayAddress h.finalized 5192449381305989311, &1: 1, fReachable 0, nRelayNodes 2
152020-08-18T17:07:16Z RelayAddress h.finalized 9128843626119142903, &1: 1, fReachable 0, nRelayNodes 2
162020-08-18T17:07:16Z RelayAddress h.finalized 3101762099756148826, &1: 0, fReachable 0, nRelayNodes 1
172020-08-18T17:07:16Z RelayAddress h.finalized 11756616115885090190, &1: 0, fReachable 0, nRelayNodes 1
182020-08-18T17:07:20Z RelayAddress h.finalized 787010406092213330, &1: 0, fReachable 0, nRelayNodes 1
192020-08-18T17:07:52Z RelayAddress h.finalized 11938741117950890368, &1: 0, fReachable 1, nRelayNodes 2
202020-08-18T17:07:59Z RelayAddress h.finalized 16536503547621818460, &1: 0, fReachable 1, nRelayNodes 2
212020-08-18T17:08:45Z RelayAddress h.finalized 1661031355910999457, &1: 1, fReachable 1, nRelayNodes 2
222020-08-18T17:08:45Z RelayAddress h.finalized 9867292503841828190, &1: 0, fReachable 1, nRelayNodes 2

vasild commented at 5:11 pm on August 18, 2020: member

@jonatack to observe the effect of this either run with -onlynet=onion (as you did) or run a normal node without any special arguments - no tor proxy, just IPv4/IPv6 connectivity. This will flag TOR addresses as unreachable.

sipa commented at 5:12 pm on August 18, 2020: member

@jonatack I wouldn’t expect to see observable differences from just one node doing this. The problem is that other nodes don’t relay your onion addresses well unless they’re on Tor themselves. Change will require widespread deployment.

jonatack commented at 5:14 pm on August 18, 2020: member

@vasild @sipa ACK, thanks. Agreed, this is just me getting a handle on this and sanity checking things.

vasild approved

vasild commented at 5:34 pm on August 18, 2020: member

ACK 86d4cf42d

I wonder why not treat all addresses equally (ie relay always to 2 nodes, even addresses from unreachable networks)? It did that but was changed in 2012 in 090e5b40f as part of #1021. Alas, no explanation why.

I tested this by extending the test in p2p_addr_relay.py as per the patch below.

Short story: it works as expected.

Long story: we send 5 TOR addresses from mininode1 to bitcoind, connect 2 other mininodes (mininode2 and mininode3) to bitcoind and observe what will be relayed to them.

Without the patch the sum of the TOR addresses received by mininode2 and mininode3 is always equal to 5 (because each of the 5 addresses is relayed to exactly one of mininode2 or mininode3).

0run1:
1TestFramework (INFO): Receiver1 got 5 IPv4 and 2 TOR addresses
2TestFramework (INFO): Receiver2 got 5 IPv4 and 3 TOR addresses
3
4run2:
5TestFramework (INFO): Receiver1 got 5 IPv4 and 4 TOR addresses
6TestFramework (INFO): Receiver2 got 5 IPv4 and 1 TOR addresses
7
8...

With the patch the sum of the TOR address received by both nodes is between 5 and 10.

0run1:
1TestFramework (INFO): Receiver1 got 5 IPv4 and 3 TOR addresses
2TestFramework (INFO): Receiver2 got 5 IPv4 and 3 TOR addresses
3
4run2:
5TestFramework (INFO): Receiver1 got 5 IPv4 and 4 TOR addresses
6TestFramework (INFO): Receiver2 got 5 IPv4 and 5 TOR addresses
7
8...

The changes in src/net_processing.cpp fix an unrelated issue - don’t consider for relaying a node that knows about that address because PushAddress() will just ignore it and so that peer will have been added in vain to best. It is needed to get predictable results from the test - otherwise sometimes the node which sent us the address is considered for relay and the address is not relayed.

  0diff --git i/src/net_processing.cpp w/src/net_processing.cpp
  1index d637abcef..ab000da9c 100644
  2--- i/src/net_processing.cpp
  3+++ w/src/net_processing.cpp
  4@@ -1492,14 +1492,14 @@ static void RelayAddress(const CAddress& addr, bool fReachable, const CConnman&
  5     // Relay reachable addresses to 2 peers. Unreachable addresses are relayed randomly to 1 or 2 peers.
  6     unsigned int nRelayNodes = (fReachable || (hasher.Finalize() & 1)) ? 2 : 1;
  7 
  8     std::array<std::pair<uint64_t, CNode*>,2> best{{{0, nullptr}, {0, nullptr}}};
  9     assert(nRelayNodes <= best.size());
 10 
 11-    auto sortfunc = [&best, &hasher, nRelayNodes](CNode* pnode) {
 12-        if (pnode->IsAddrRelayPeer()) {
 13+    auto sortfunc = [&addr, &best, &hasher, nRelayNodes](CNode* pnode) {
 14+        if (pnode->IsAddrRelayPeer() && !pnode->m_addr_known->contains(addr.GetKey())) {
 15             uint64_t hashKey = CSipHasher(hasher).Write(pnode->GetId()).Finalize();
 16             for (unsigned int i = 0; i < nRelayNodes; i++) {
 17                  if (hashKey > best[i].first) {
 18                      std::copy(best.begin() + i, best.begin() + nRelayNodes - 1, best.begin() + i + 1);
 19                      best[i] = std::make_pair(hashKey, pnode);
 20                      break;
 21diff --git i/test/functional/p2p_addr_relay.py w/test/functional/p2p_addr_relay.py
 22index 5c7e27a3a..f7315f97c 100755
 23--- i/test/functional/p2p_addr_relay.py
 24+++ w/test/functional/p2p_addr_relay.py
 25@@ -18,28 +18,56 @@ from test_framework.mininode import (
 26 from test_framework.test_framework import BitcoinTestFramework
 27 from test_framework.util import (
 28     assert_equal,
 29 )
 30 import time
 31 
 32+# Keep this with length <= 10. Addresses from larger messages are not relayed.
 33 ADDRS = []
 34-for i in range(10):
 35+
 36+num_ipv4_addrs = 5
 37+for i in range(num_ipv4_addrs):
 38     addr = CAddress()
 39     addr.time = int(time.time()) + i
 40     addr.nServices = NODE_NETWORK | NODE_WITNESS
 41     addr.ip = "123.123.123.{}".format(i % 256)
 42     addr.port = 8333 + i
 43     ADDRS.append(addr)
 44 
 45+i = 0
 46+for tor_addr in [ \
 47+        "2empatdfea6vwete.onion", \
 48+        "34aqcwnnuiqh234f.onion", \
 49+        "3gxqibajrtysyp5o.onion", \
 50+        "3sami4tg4yhctjyc.onion", \
 51+        "3w77hrilg6q64opl.onion" \
 52+    ]:
 53+    addr = CAddress()
 54+    addr.time = int(time.time()) + i
 55+    addr.nServices = NODE_NETWORK | NODE_WITNESS
 56+    addr.ip = tor_addr
 57+    addr.port = 8433 + i
 58+    ADDRS.append(addr)
 59+    i += 1
 60+
 61 
 62 class AddrReceiver(P2PInterface):
 63+    num_ipv4_received = 0
 64+    num_tor_received = 0
 65+
 66     def on_addr(self, message):
 67         for addr in message.addrs:
 68             assert_equal(addr.nServices, 9)
 69-            assert addr.ip.startswith('123.123.123.')
 70-            assert (8333 <= addr.port < 8343)
 71+            if addr.ip.startswith('123.123.123.'):
 72+                assert (8333 <= addr.port < 8338)
 73+                self.num_ipv4_received += 1
 74+            elif addr.ip.endswith('.onion'):
 75+                assert (8433 <= addr.port < 8438)
 76+                self.num_tor_received += 1
 77+            else:
 78+                assert False
 79 
 80 
 81 class AddrTest(BitcoinTestFramework):
 82     def set_test_params(self):
 83         self.setup_clean_chain = False
 84         self.num_nodes = 1
 85@@ -47,25 +75,39 @@ class AddrTest(BitcoinTestFramework):
 86     def run_test(self):
 87         self.log.info('Create connection that sends addr messages')
 88         addr_source = self.nodes[0].add_p2p_connection(P2PInterface())
 89         msg = msg_addr()
 90 
 91         self.log.info('Send too-large addr message')
 92-        msg.addrs = ADDRS * 101
 93+        msg.addrs = ADDRS * 101 # more than 1000 addresses in one message
 94         with self.nodes[0].assert_debug_log(['addr message size = 1010']):
 95             addr_source.send_and_ping(msg)
 96 
 97-        self.log.info('Check that addr message content is relayed and added to addrman')
 98-        addr_receiver = self.nodes[0].add_p2p_connection(AddrReceiver())
 99+        # Every IPv4 address must be relayed to both peers.
100+        # Every TOR address must be relayed to just one or both peers.
101+        self.log.info('Send normal addr message and check that addresses are relayed and added to addrman')
102+        addr_receiver1 = self.nodes[0].add_p2p_connection(AddrReceiver())
103+        addr_receiver2 = self.nodes[0].add_p2p_connection(AddrReceiver())
104         msg.addrs = ADDRS
105         with self.nodes[0].assert_debug_log([
106-                'Added 10 addresses from 127.0.0.1: 0 tried',
107+                'Added {} addresses from 127.0.0.1: 0 tried'.format(num_ipv4_addrs),
108                 'received: addr (301 bytes) peer=0',
109-                'sending addr (301 bytes) peer=1',
110         ]):
111             addr_source.send_and_ping(msg)
112             self.nodes[0].setmocktime(int(time.time()) + 30 * 60)
113-            addr_receiver.sync_with_ping()
114+            addr_receiver1.sync_with_ping()
115+            addr_receiver2.sync_with_ping()
116+
117+        assert addr_receiver1.num_ipv4_received == 5
118+        assert addr_receiver2.num_ipv4_received == 5
119+
120+        assert 0 <= addr_receiver1.num_tor_received <= 5
121+        assert 0 <= addr_receiver2.num_tor_received <= 5
122+
123+        self.log.info('Receiver1 got {} IPv4 and {} TOR addresses'.format(
124+                      addr_receiver1.num_ipv4_received, addr_receiver1.num_tor_received))
125+        self.log.info('Receiver2 got {} IPv4 and {} TOR addresses'.format(
126+                      addr_receiver2.num_ipv4_received, addr_receiver2.num_tor_received))
127 
128 
129 if __name__ == '__main__':
130     AddrTest().main()
131diff --git i/test/functional/test_framework/messages.py w/test/functional/test_framework/messages.py
132index 5207b563a..350bed670 100755
133--- i/test/functional/test_framework/messages.py
134+++ w/test/functional/test_framework/messages.py
135@@ -15,12 +15,13 @@ msg_block, msg_tx, msg_headers, etc.:
136 
137 ser_*, deser_*: functions that handle serialization/deserialization.
138 
139 Classes use __slots__ to ensure extraneous attributes aren't accidentally added
140 by tests, compromising their intended effect.
141 """
142+import base64
143 from codecs import encode
144 import copy
145 import hashlib
146 from io import BytesIO
147 import random
148 import socket
149@@ -197,44 +198,52 @@ def ToHex(obj):
150     return obj.serialize().hex()
151 
152 # Objects that map to bitcoind objects, which can be serialized/deserialized
153 
154 
155 class CAddress:
156-    __slots__ = ("ip", "nServices", "pchReserved", "port", "time")
157+    __slots__ = ("ip", "nServices", "pchReserved", "pchOnionCat", "port", "time")
158 
159     def __init__(self):
160         self.time = 0
161         self.nServices = 1
162         self.pchReserved = b"\x00" * 10 + b"\xff" * 2
163+        self.pchOnionCat = b"\xfd\x87\xd8\x7e\xeb\x43"
164         self.ip = "0.0.0.0"
165         self.port = 0
166 
167     def deserialize(self, f, *, with_time=True):
168         if with_time:
169             # VERSION messages serialize CAddress objects without time
170             self.time = struct.unpack("<i", f.read(4))[0]
171         self.nServices = struct.unpack("<Q", f.read(8))[0]
172-        self.pchReserved = f.read(12)
173-        self.ip = socket.inet_ntoa(f.read(4))
174+        buf = f.read(16)
175+        if buf.startswith(self.pchOnionCat):
176+            self.ip = base64.b32encode(buf[len(self.pchOnionCat):]).decode().lower() + ".onion"
177+        else:
178+            self.ip = socket.inet_ntoa(buf[len(self.pchReserved):])
179         self.port = struct.unpack(">H", f.read(2))[0]
180 
181     def serialize(self, *, with_time=True):
182         r = b""
183         if with_time:
184             # VERSION messages serialize CAddress objects without time
185             r += struct.pack("<i", self.time)
186         r += struct.pack("<Q", self.nServices)
187-        r += self.pchReserved
188-        r += socket.inet_aton(self.ip)
189+        if self.ip.endswith(".onion"):
190+            r += self.pchOnionCat
191+            r += base64.b32decode(self.ip[:-len(".onion")], casefold=True)
192+        else:
193+            r += self.pchReserved
194+            r += socket.inet_aton(self.ip)
195         r += struct.pack(">H", self.port)
196         return r
197 
198     def __repr__(self):
199-        return "CAddress(nServices=%i ip=%s port=%i)" % (self.nServices,
200-                                                         self.ip, self.port)
201+        return "CAddress(nServices=%i addr=%s port=%i)" % (self.nServices,
202+                                                           self.ip, self.port)
203 
204 
205 class CInv:
206     __slots__ = ("hash", "type")
207 
208     typemap = {

practicalswift commented at 5:49 pm on August 18, 2020: contributor

ACK 86d4cf42d97abf4c436d1eabf29e2ed150f69c1e – patch looks correct

jonatack commented at 5:58 pm on August 18, 2020: member

Probably obvious but confirming the PR description: testing with Tor turned off and no bitcoind onion conf args, I see a few fReachable 0 values but they are rare. OTOH, with onlynet=onion, unreachables are the majority.

naumenkogs commented at 2:15 pm on August 23, 2020: member

ACK 86d4cf4

jnewbery commented at 9:22 am on August 24, 2020: member

Concept ACK. R0 needs to be greater than one, or it’ll burn out before infecting the population. 🦠

laanwj merged this on Sep 5, 2020

laanwj closed this on Sep 5, 2020

sidhujag referenced this in commit 12b6afa79f on Sep 9, 2020

PastaPastaPasta referenced this in commit eb38ff195d on Jun 27, 2021

PastaPastaPasta referenced this in commit 86eeae31cc on Jun 28, 2021

PastaPastaPasta referenced this in commit 55137df60e on Jun 29, 2021

PastaPastaPasta referenced this in commit 83c79b2abf on Jul 1, 2021

PastaPastaPasta referenced this in commit c04fdbcbc7 on Jul 1, 2021

PastaPastaPasta referenced this in commit ebd2dffd92 on Jul 15, 2021

PastaPastaPasta referenced this in commit fdc99dcc64 on Jul 16, 2021

Fabcien referenced this in commit 5fe02fac29 on Sep 23, 2021

DrahtBot locked this on Feb 15, 2022

Increase the ip address relay branching factor for unreachable networks #19728