As a developer, I want to audit our kademlia implementation

[dkuehr]

Tasks:

• [x] Learn from external resources to get a better understanding of how kademlia/DHT works.
• [x] Code-review our implementation: think of problematic corner cases (IN PROGRESS).
• [x] Keep fuzz-testing our implementation (https://github.com/openmina/openmina/pull/560).
• [x] Review Go implementation for potential issues or misuse by the OCaml node.

[dkuehr]

General Observations and Design:

• Kademlia was first designed to use UDP, a connection-less transport.
  • This design lets the protocol keep many peers in its routing table without needing to keep a connection to all of them.
  • PING messages are used to check if peers are still alive.
  • In Mina, Kademlia uses Yamux streams as the transport protocol. Yamux is based on Noise/Pnet/TCP which needs to keep connections to peers.
  • This affects the number of connections we need to make: https://github.com/MinaProtocol/mina/commit/35c7ab4c447f00e35172dbea8c1c02367b0c9855
  • It also makes PING messages not needed, as we have to make a connection just to send the message. Note: PING isn't even implemented in OpenMina.
  • PING is needed for k-bucket updates to work right when a k-bucket is full (we only replace an older peer if it doesn't respond to PING).
• There seems to be no way to stop a peer from reporting fake peer-ids that point to known (good) IP addresses.
• In this case, nodes that get this fake info could try to connect to valid peers but disconnect during the Noise handshake because the peer-id won't match.
• What the attacker can't control is the distance, as it needs to break the hash function security.

OpenMina Implementation Observations:

• Only FIND_NODE message is implemented.
• Entry replacement policy:
  • Old addresses are always kept (as we don't implement PING).
  • New addresses can be added to the multiaddr vector for an existing peer-id if they aren't already there. This vector seems to have no limit.
• A P2pPeerAction::Discovered action is sent for every discovered peer. This always adds a new peer into the P2pState's .peers BTree. This seems to have no limit.