devp2p.kademlia doesn't properly support explicit node lookups #50

konradkonrad · 2016-11-29T14:42:00Z

1) The state model for node handshakes is incomplete:

Prior to any further messages, new nodes need to handshake by two-way ping ing each other (with a respective pong response).

pydevp2p is not enforcing the handshake, whereas other implementations seem to do.

Handshaking in pydevp2p happens implicitly, by
a) responding to all received pings with a pong
b) pinging all received neighbours
c) responding to a remote handshake (remote send a ping, we respond with pong, now we are supposed to ping the remote) seems not to be supported

However, when querying find_node, the handshake is not initialized. Furthermore the state handling in the kademlia protocol implementation doesn't allow for tracking handshake progress.

Suggested fix:

Add handshake tracking to the kademlia.Node class.
Add a handshake task, that can explicitly enforce finishing handshakes (regardless of the initiator).

2) A task model for iteratively closing in towards a target node is missing

Finding a key (i.e. a node) through kademlia works by recursively asking the closest (to the target) known neighbours for new neighbours closer to the target key until the target is included in the received neighbour set (or the operation times out). Prior to sending new requests to newly discovered neighbours, they will require a handshake.

There is a FindNodeTask stub that is incomplete. However, a part of the protocol is implemented in kademlia.protocol.recv_neighbours.

The current implementation misses a couple of things:

a) The handshake needs to succeed(!) prior to sending new requests. This leads to "forwarded" find_node requests being silently discarded by the newly discovered remotes.
b) Filtering against the closest already known node is susceptible to local minima, where a badly connected (or badly behaving) known node with a promising (close) key lets the algorithm terminate early. Since there is no tracking for the originating request, there is no way to discard an unhelpful remote.
c) There is no mechanism in place to track the results of a find_node request (task).

Suggested fix:

Ensure handshakes prior to forwarding find_node requests to newly discovered nodes.
Use the intermediary results more exhaustively, to avoid early termination.
Track the overall progress of a find_node task, potentially in a dedicated class; this would also allow to receive a result.

(edit:)

Clarification:

The current implementation is sufficient for the blockchain use case, since it does add some nodes through its implicit state model. With a distributed blockchain this adds enough connectivity to synchronize. However, when using the pydevp2p stack in other applications, being able to lookup specific keys/nodes can be a hard requirement.

The text was updated successfully, but these errors were encountered:

The `update()` method of `KademliaProtocol` is far too complex for sensible refactoring, this is a first step to untangle all involved state transitions.

Due to bonding (ping/pong), it must be possible to delay sending of find_node requests until bonding succeeded. Delayed requests will be send in `update()` method after bonding.

KademliaProtocol delays `find_node` requests until bonding succeeded. This is now reflected in the test.

At the end of bonding a node is not necessarily in the routing table. But if it is, we ensure the bonding property (i.e. node identity between `node` in scope and `node` from routing).

This fixes the `test_many` test to cater for bonding during the bootstrapping loop.

Note: this passes all of the previous assertions, although I'm unsure whether this really tests the desired behaviour.

At this point I am unsure why this test is set up this way: it triggers a pytest timeout and is then marked xfail, while the test method is worded `test_..._timeout`. This should probably be revisited, but I consider it out of scope for this.

I left the name for the function that triggers updates independent from the current node in scope open during refactoring. This part does sanity checks, cleanup, pruning every time `update` is called, so I go with `periodic_updates` now.