Stop Believing Liars

[dnwiebe]

Background: Here's how connecting a Node into the network works:

Debuting Node D sends Debut Gossip (containing data for Node D) to existing Node E.

Node E checks to see if D has any neighbors. It doesn't, so Node E adds D to its neighborhood database, selects its neighbor N to introduce, and sends Introduction Gossip (containing data for Nodes E and N, revealing the IP address of N) to Node D.

Node D examines the Introduction Gossip and identifies E as the introducer and N as the introducee. It adds E to its neighborhood database and sends Debut Gossip (containing data for Node D) to N.

Node N checks to see if D has any neighbors. It does (E), so instead of sending Introduction Gossip, N just adds D to its neighborhood database and sends Standard Gossip, revealing no new IP addresses to D.

Problem: See the phrase "checks to see if D has any neighbors" above? That's the problem. The way E and N check to see if D has any neighbors is to look at the Debut Gossip sent by D. If D claims in that Gossip to have neighbors, then it gets Standard Gossip; if it claims to have no neighbors, it gets Introduction Gossip containing a new Node's IP address. An evil Node could simply send a series of Debuts, always claiming to have no neighbors, and use Introductions (or Passes) to traverse a big chunk of the network and harvest IP addresses.

Solutions and Pitfalls:
One apparent solution is for E and N to check their neighborhood databases to see how many neighbors D has, rather than trusting its Gossip. The pitfall here is that all Gossip is signed by the originator: therefore, the NodeRecords they have in their databases are exactly the same as the Gossip they were sent; there's no benefit.

This could be circumvented by counting not the number of arrows D claims are coming out of it, but the number of arrows other Nodes in the database claim are going into it. That is, half-neighborships from X to D, where X is any other Node in the database. The problem with this is that if incoming half-neighborships disqualify a Node from having other Nodes introduced to it, then A) you're opening another attack surface where evil Nodes can prevent other Nodes from becoming well-connected by claiming half-neighborships with them as soon as they appear in the evil Nodes' databases, and B) a Node that has just broken a full neighborship with an evil Node will be disqualified from connecting to a replacement.

I can't think of any other solutions. Can you?

[dnwiebe]

Ideas:

1. When sending an Introduction in response to a Debut, always send Standard Gossip depicting the new half-neighborship with the debuting Node before sending the Introduction Gossip to the debuting Node. (Does the Standard Gossip go to the debuting Node as well, or just to all the other neighbors? Interesting question. Dunno.)
2. When checking to see if a debuting Node has neighbors, check to see if any Nodes in your database claim half-neighborships to it. If they do, whether or not the debuting Node claims half-neighborships back, send it Standard Gossip instead of an Introduction.
3. Whenever Gossip is received, check to see if any Node in the Gossip has suddenly stopped claiming neighborship with us. (That is, in our database it claims to be our neighbor, but in the Gossip it claims not to be.) If this happens, then also immediately eliminate any neighborship we may be claiming with it. This will not only help with this issue, but it will lead to cleaner databases and quicker purging of dead Nodes.
4. This still doesn't prevent evil Nodes from preventing innocent Nodes from becoming well-connected by claiming persistent half-neighborships with them.