Peer-to-Peer Networking: From Kademlia to Discv5

Editor's Note: This article comes fromEthereum enthusiasts (ID: ethfans)Editor's Note: This article comes from

Ethereum enthusiasts (ID: ethfans)

, Author: dean, translation & proofreading: Pei Qi & A Jian, reprinted with authorization by Odaily.

If you've been working on Ethereum or related technologies, you've probably heard of discv4 or discv5. But what exactly are these? How do they work? Where is their excellence? To answer these questions, we need to start from scratch. This blog post assumes that the reader is relatively new to the field, so it can be read by people without a technical background.

secondary title

Early P2P file-sharing technologies, such as Napster, used a single server to share information that recorded who owned what files. A node initiates a connection to the central server and submits a list of files it owns. Another node then initiates a connection to the same central server, looks for the storage node of the file it needs, and then establishes a connection with the found node. However, this is a flawed system - the system is vulnerable to attack, and centralized server nodes may be subject to lawsuits. (Translator's Note: The corresponding relationship between file content and nodes is stored on a single server. If some links to copyrighted content are provided, the provider of this centralized server will be directly held accountable by the original copyright owner.)

distributed hash table

Therefore, another solution is urgently needed for peer-to-peer networks. After several years of research and experiments, researchers proposed a distributed hash table (DHT).

secondary title

distributed hash table

DHT has been mentioned above. So what exactly is DHT?

Kademlia

A Distributed Hash Table (DHT) is a distributed key-value list. Nodes participating in the DHT can easily retrieve the value corresponding to a certain key.

Suppose there are 9 key-value pairs and 3 nodes in a network. Ideally, each node only needs to store 3 key-value pairs (the best way is to store 6 key-value pairs to provide redundancy), It means that if a key-value pair is to be updated, only some network nodes need to be updated. The general idea is that any node in the network can know where to look for the particular key-value pair it needs based on the way the information is distributed among the nodes.

secondary title

XOR 10011001    00110010    --------    10101011

Now that we know what DHT is, let's take a look at Kademlia, the predecessor of discv4. Kademlia is a DHT protocol invented in 2002 by Petar Maymounkov and David Mazières. I think this protocol may be the most popular and widely used DHT protocol. How it works is simple, let's find out.

In Kademlia, nodes and values ​​are arranged by distance (the arrangement is defined strictly mathematically). The distance here is not a geographical distance, but an identifier-based representation. By using some distance function, the distance between two identifiers can be calculated.

• Kademlia uses XOR (exclusive OR operator) as the distance function. The characteristic of the XOR function is that the output is true only if the inputs are different. The following is an example expressed in binary identifiers.

• The example above says that the distance between the decimal numbers 153 and 50 is 171.

• There are many reasons to use XOR as a distance function, including:

An ID has a distance of 0 from itself.

The distances are symmetric, the distance from A to B is the same as the distance from B to A.

Following the triangle inequality, if A, B, C are three points on a triangle, then the distance from A to B is less than or equal to the distance from A to C plus the distance from B to C.

In summary, a node can determine which node is closer to it according to the distance function, and make decisions based on this "distance".

Kademlia nodes store a routing table. The routing table contains multiple lists. The nodes recorded in each subsequent list are a little farther away than the nodes in the previous list. Each node maintains information about the node closest to itself; the further away another node is, the less relevant information the local node keeps.

• Suppose I want to find a specific node. All I have to do is send requests to my known nodes which return neighbors in their records that are closer to my target node. I repeat this process until some group of neighbors help me find the target node.

• The same process works for values. The distance between the value and the node is deterministic, because the identifier ID of the value and the node are organized in the same way, so we can calculate this distance. If I want to look up a value, I just look for the nearest neighbor node to the value's key until I find the node that stores the value.

• In order for Kademlia nodes to support these functions, the protocol communicates through the following messages.

• PING - Used to check if a node is still running.

FINDNODE - Returns the closest node requested to the given ID.

Discv4

FINDVALUE - Same as FINDNODE, except that if a node stores a specific value, it will return the value directly.

This is a very simplified explanation of Kademlia, skipping various important details. For a more comprehensive understanding, I strongly recommend the original paper or a deeper design specification.

secondary title

After paving the way for the background, we finally come to discv4 (meaning discovery v4), which is the current node discovery protocol of Ethereum. The Discv4 protocol itself is based on Kademlia, but with some changes. For example, the value part in the DHT is no longer used in discv4.

Kademlia is mainly used for the organization of the network, so we can use the routing table to locate other nodes. But discv4 does not use the value part in DHT at all, so we can abandon the commands FINDVALUE and STORE used in Kademlia.

Previously, Kademlia's query method described how nodes get peers. A node initiates a request to other nodes to get a node closer to itself. Repeat this request process until no new nodes can be found.

Additionally, discv4 adds mutual terminal authentication. This is to ensure that the node that initiated the FINDNODE request is participating in the same node discovery protocol.

Finally, all discv4 nodes should maintain up-to-date ENR records. A record contains information about a node. Any node can use a discv4-specific package called ENRRequest to request an ENR record.

If you want to know more details about ENRs, please move on to my other blog post Network Addresses in Ethereum.

However, discv4 also introduces some problems. Let's take a look at a few of them.

Second, in order to defend against replay attacks, discv4 uses timestamps. This can cause all sorts of problems when a host's clock goes wrong. See the "Known Issues" section of the discv4 specification for more details.

Discv5

Finally, there are also problems in the mutual authentication of terminals. Because of the possibility of packet loss, there is no way to tell whether two peers have authenticated each other. That is, we may think we are authenticated, but the peers we are communicating with do not; they may drop our FINDNODE packets as a result.

Finally, there are also problems in the mutual authentication of terminals. Because of the possibility of packet loss, there is no way to tell whether two peers have authenticated each other. That is, we may think we are authenticated, but the peers we are communicating with do not; they may drop our FINDNODE packets as a result.

secondary title

Finally, let's look at discv5. Discv5 is an iterative version of discv4 and will serve as the node discovery protocol for Eth 2.0. Discv5 aims to fix many of the problems that existed in discv4.

The first change is the way FINDNODE works. Both traditional Kademlia and discv5 use identifiers. In discv5, we use logarithmic distance, that is, after sending a FINDNODE request, the nodes contained in the response are all within a specific logarithmic distance from the sender node.

Logarithmic distance means: first calculate the distance, and then use the log function with base 2, ie log2(A xor B).

The second very important change is that discv5 has been committed to solving the biggest problem in discv4: the distinction of secondary protocols. Discv5 adds topic tables. The topic table is a first-in-first-out list of nodes that provide a particular service. Nodes add themselves to this list by registering advertisements with peers.

As of this writing, there are still some issues with write operations in this sub-protocol differentiation scheme. There is currently no efficient way for a node to advertise on multiple peers, so a separate request needs to be sent to each peer, which is inefficient for large-scale networks.

Furthermore, it is unclear how many peers a node advertises to, and to which peers it advertises. See devp2p#136 for more details.

There are many other small changes in Discv5, but these changes are not that important, so they are omitted in this summary.