One framing of the problem: “Honest nodes are not as reachable as attacker-controlled nodes. This gives attackers an extra advantage when trying to occupy outbound connection slots.”
With that framing, I think having some sort of holepunching would be very valuable. Option 2 seems like a good start, given that the % of nodes advertising a Tor address (already have Tor working) is quite high.
I came up with option 6: coordinator-less hole punching
Every option so far needs a coordinator, because two nodes behind NATs have to (a) learn each other’s IP:port and (b) agree on when to fire. In option 6 addresses come from normal addr-relay, and holepunch timing is derived from the next blocks (e.g. header timestamp) that arrive.
A node that wants to hole punch announces a new addrv2 type with its hole-punchable IP:port and an ephemeral EC public key P. Nodes keep their ephemeral private key p.
Nodes receiving it store the address and calculate a ECDH shared secret with P_other and p_own.
On every new block, each node computes SHA256(tag || shared_secret || block_hash) for every entry it had received before the block. It sorts the resulting hashes and keeps the few lowest. Those are the peers it tries this round.
For each candidate, it calls connect() to that IP:port from its punch port and leaves the socket pending.
Both sides derive the same shared secret, which also causes them to derive the same hash. Two peers find themself through being their sets of the lowest hash candidates. The timing is derived from the block header (exact way is tbd) and the same for both nodes. We don’t need the timing to be exact. During testing, a few seconds plus or minus didn’t matter. So clocks can be slightly out of sync.
The (next) block hash is used to stop an attacker from grinding. Without it, someone with my P could try private keys until their hash is tiny and be my top pick forever. When using the block hash as salt, there’s nothing to grind, since the block doesn’t exist yet when they publish their key. Nodes just have to ignore blocks they heard about before receiving the address. Privacy-wise, two public keys don’t reveal the shared secret, so an outside observer can’t tell who connects to whom or when. Participation is public though, since both sides publish an IP:port.
Both sides have to announce and have each other’s address, so success depends on how widely these spread. Additionally, it needs careful design of an holepunch address manager and rate-limiting to mitigate an attacker flooding the node with fake addresses or public keys that will never result in a holepunch connection.
Wouldn’t it also be effective for an attacker to flood with real addresses/public keys, to attempt to monopolize all connections made via this mechanism?
To maintain 8 connections to 100k peers, you’d need ~1M active ports; but for the actual address sharing step, I think you’d likely only need to advertise ~10k ports (800k connections cycling once a week is about 800 per block, so with 10k attacker addresses advertised at any one time, you should be an early match against each victim – about 85% of honest nodes will have the top two matches be attackers, in that scenario; and even when that happens, the odds of the other peer not having an attacker’s node at a higher ranked seems very low?