Skip to content

Discovery Overview

Nick Savers edited this page Mar 7, 2019 · 11 revisions

Overview

This purpose of this article is to help clarify the terminology and direction of the Ethereum peer-to-peer (p2p) discovery protocols.

This is not a set of formal specifications, but more of a plain English summary of things. The questions that frequently arise about the discovery mechanisms do show that there is a good deal of uncertainty around both the lexicon and roadmap, so this document aims to serve as a reference point whenever those questions arise in future.

Terminology

The range of questions we encounter include

  • "How do Ethereum nodes discover each other?"

  • "Will discovery v5 be phased out?"

  • "Will libp2p replace discovery?"

  • ...and many others

Discussions on these will be helped when everyone is on the same page with terms, and the definitions below will answer some questions directly. Without going into excess detail, this document goes through the basic lexicon (in alphabetical order).

This symbol shows discussion on some of the technical details. In areas of the proposed protocols this discussion is both to help stimulate conversation and to illustrate where areas of uncertainty or flux may still lie.

This symbol indicates an important change on the roadmap (a.k.a "discovery v5").

The symbol shows useful resources for the section.

Underlined text indicates an influence or requirement on the upcoming wire protocol format.

List of relevant terms:

Bonding

This term is found in some technical documentation of the discovery v4 protocol. It is an extension to the Kademlia discovery protocol, with the intention of preventing attacks that exploit unverified endpoint information.

It is basically a synonym for mutual endpoint verification (so that some RPC/bidirectional message exchange can be carried out).

When a node receives a discovery v4 FindNode request from another node, guarantees must already be in place that the UDP source endpoint is authentic. (That endpoint information is obtained from the UDP frame and not any From field.) Otherwise, malicious traffic with spoofed source IPs could cause large, unsolicited 'Neighbors' packets to be returned to a victim for example, swamping them with data.

Currently those guarantees are achieved by each node pair Pinging (Kademlia) each other to get a response, validating each other's responses before they establish a 'bonded' status. This is done before FindNode is invoked.

The present design causes implementation difficulties. In order to call FindNode (see Kademlia) on another node, our node first needs to establish the authenticity of the endpoint, and the other node needs to ensure that we are a valid node in the DHT. The problem is that there is no certainty that Pong (discovery v4) responses are ever processed, and in practice for various reasons they do seem to get lost, and there is no certainty that a previously bonded status has not been otherwise lost. This can result in FindNode calls being rejected because our node considers the potential peer 'bonded' when the peer does not. Developers must cater for this scenario which can cause extra network traffic and code complexity.

An alternative to the bonding process is being researched and will be specified in an upcoming wire protocol.

Bootnodes

When nodes want to join the network, they need a starting point to begin searching for neighbour nodes. The term bootnode is used interchangeably to represent:

  • A known, maintained Ethereum instance running with the purpose of serving a well-known discovery endpoint. There are several of these, and some of which are maintained by the Ethereum Foundation itself.

  • The discovery endpoint identifying the physical bootnode. From the perspective of a peer wishing to join the network, an endpoint such as 1.2.3.4:30303 may be referred to as a bootnode.

Geth has a list of bootnodes hardcoded into the implementation.

Capability

The term capability originates out of the devp2p/RLPx TCP-based p2p transport protocol specifications. It basically means the devp2p/rlpx sub-protocols such as Ethereum or LES that the peer supports. In those specifications, a capability also reserves zero or more message type identifiers mutually understood by the peers.

The original intension of capability was something like 'the protocol itself and the message space required for that protocol over the devp2p transport.' This term does not really belong in the scope of discovery documentation, and certainly not in the scope of discovery v4, but because peers of certain capabilities cannot now be discovered until after the devp2p/rlpx handshakes are established, and because this complicates certain peer discovery scenarios (such as searching for LES nodes), various mechanisms are being proposed to make node capabilities visible during the discovery process.

Discovery v4 does not attempt to differentiate between node capabilities. So, it is possible to 'accidentally' discover peers in other networks, such as an Ethereum node finding an Ethereum Classic node for example. It is not until the more resource intensive devp2p/rlpx higher level handshake is established that the peer gets to learn that it is attempting to add an invalid peer to its own set of neighbours. This common base layer introduces noise, which is shared across the networks. The fact that the peer capability is not known until after the devp2p/rlpx handshake is established also complicates the search for less common nodes, such as LES (light Ethereum) protocol serving peers.

The new improvements to discovery introduce mechanisms that help with the above issue. Please refer to ENR and Topic Discovery for information on those.

Discovery v4

At the time of writing, the mechanism by which peers discover each other is called, "discovery v4."

The way it works is that each peer maintains a Kademlia table of endpoints, so that when a new peer wants to join the network it can ask an existing peer for sets of neighbour peers it can connect to. That protocol is carried out by exchanging simple messages over UDP.

When a node wants to join the network, it needs to know of at least one other existing, active endpoint in order to ask it for neighbours. There are two ways this can currently happen. One is via bootnodes, the other is via protocol specific (eg: Ethereum) known peers, for example those accumulated in a database from previous sessions.

Once the initial endpoint is obtained, Kademlia dictates how the peers communicate with each other to establish neighbours and form networks. In addition to this, however, discovery v4 also introduces the bonding protocol to help verify endpoints.

For the purposes of this document, the key aspects of Kademlia and discovery v4 that should be understood are the following:

  • When a node first starts up and tries to join the network via the discovery process, it runs a 'boot process.' This is an iterative process, where our node contacts its initial known node, for example a bootnode, and asks that peer for nodes closest to our node, and then proceeds to ask them for even closer nodes, until no further nodes can be found.

    This is achieved by repeatedly calling FindNode (which accepts a 'target' parameter) on each of some of the closest returned nodes. All those newly discovered nodes populate our table of neighbours, which we serve to others who might call FindNode to us, and which we use to try and peer with over higher-level protocols.

  • No incoming FindNode request is served unless the source is first verified by the bonding protocol.

  • All nodes are identified by their 64-byte elliptic curve public key. However, the Kademlia table identifies nodes as the 32-byte SHA256 hash of the node id.

  • FindNode is called with a 'target' parameter of the node id and is supposed to return 'k' (16 by default) nodes closest to that target.

  • Packets are signed with an "EC recoverable" signature based on the source node id key-pair, meaning that the source node's public key (and therefore node id) can be recovered from the source packet signature.

  • Every packet has an expiration field, which is an absolute timestamp. Clock synchronisation issues can cause packet rejection. The purpose of the expiration field is to prevent packet replay. The prevalence of synchronization issues means a better packet replay prevention mechanism is needed.

  • Certain specified packet fields such as the "From" field in a Ping are ignored by implementations.

There are various issues arising from the above key points in discovery v4.

  • The bonding protocol is imprecise (see bonding).

  • The protocol does not clearly express how a new node is ever added into the distributed table. Calling FindNode does return the other node's neighbours but it is not plain how that other node ever got the full information (including ids) about other nodes. One way of achieving this is by recovering the public key from a signed packet after a bonding process completes. The public key is the id of the node, so the local table can be safely updated with the UDP packet ('from' fields are ignored, or implementations fill them with garbage) endpoint and recovered node id. However, some consider that a security weakness, as it is easily possible to obtain an Ethereum node id from IP address alone. (Packet verification or at least the way bonding exposes the recoverable id may need to change).

  • Kademlia cannot be fully implemented as per the guidelines in the original Maymounkov and Mazieres papers (see Kademlia)

The new ENR record format suggests that networks may opt for mixed id types, eg secp256k1 or some other curve. Is this a scenario that should ever be supported? If so, packet signatures will need to be validated after the bonding process is complete, once the id and type is known.

The current discovery v4 specification is here: https://github.com/ethereum/devp2p/blob/master/discv4.md

Discovery v5 (aka discv5)

This label has come to be a significant source of confusion and ambiguity.

The "v4" and "v5" version labels seem to be arbitrary labels loosely corresponding to the set of discovery features currently either implemented or under development. If there is any documentation about versions 1,2 or 3, I am not aware of it. While referring to each set of code as 'v4' or 'v5' might help internal technical discussions, it is a source of confusion for newcomers.

Within the geth source code and technical discussions in the geth online communities, "discv5" is also used to mean the software package, where some prototype code or early releases of the new discovery mechanisms has been implemented. To add further uncertainty, "discovery" is synonymous there with "discovery v4."

Those wishing to implement their own clients, or trying to develop their own network client tools, or just trying to figure out in which areas to invest their own education have often asked themselves:

  • "Should we invest in discovery v5?"

  • "Will discovery v4 and v5 run in parallel?"

  • "How long will clients run v4 for?"

  • "What discovery version will be used for Ethereum 2.0?"

It is important to bring some clarity to this area:

'discv5' as a software package will be deprecated in geth.

'discovery v5' will continue to be used in a colloquial sense to represent the planned new enhancements to discovery (more on this below), but the use of version numbers will be avoided in future. There will just be 'discovery,' and its associated features (topic discovery, etc).

Where possible, existing forward-compatibility will be used to assist with co-existence of the protocol versions and features.

Ethereum 2.0 discovery will use "discovery v5," (though initial development versions may work with libp2p Kademlia just until sharding is needed)

To summarise the labelling changes, all the discovery-area labels will converge on the one label, Ethereum "Discovery." This will mean the feature or functional area, as well as the software package name in geth for both Ethereum 1.X and 2.0.

The new common discovery protocol, at the time of writing will include the following enhancements along with any other technical modifications indicated by the roadmap symbol in this document:

  • ENR -- Node records (see resources) will be provided instead of the (ip, port, port, id) tuples where possible. At the time of writing the wire protocol is being written so at this point no further details are available on exactly how this achieved.

  • Packets will be obfuscated using some inexpensive masking algorithm, not for confidentiality but to make them less prone to modification or inspection by network elements (under research).

  • Some alternative to the bonding process is under research and will also be part of the wire protocol.

  • Topic Discovery will be introduced.

The ENR specification is available here: https://eips.ethereum.org/EIPS/eip-778

A draft Topic Discovery specification is available here: https://github.com/fjl/p2p-drafts/blob/master/discv5-topics.md

Endpoint

This term is only included to clarify that in the discovery context, the endpoint is a UDP network endpoint, and to provide a placeholder for discussion.

There has been some discussion around supporting other transports like TCP, such as for discovery over TOR. This can be made available via ENR for example.

Care must be taken to make sure that the endpoint entered in the DHT is not an ephemeral NAT port (or otherwise inaccessible because of NAT). What further decisions should be made related to NAT traversal methods like hole-punching and so on?

ENR

ENR or Ethereum Node Records are generalisations over the tuples found in Kademlia about node endpoints. They are an extensible format expressing signed, versioned information about a node, particularly about discovery related connectivity. They offer a common, forwards-compatible structure for this information, so that they can be conveyed through other channels (such as DNS), and so that extensions can be made more easily.

Discovery v5 wire protocol will attempt to offer a backwards compatible method of relaying ENRs in FindNode responses. The Kademlia tables should maintain ENR s, not discovery v4 tuples.

The modified bonding process (TBD) will need to be responsible for populating the Kademlia routing table with ENR s. What about other mechanisms of local additions to the routing table? Such as AddPeer? Admin RPC formats?

The ENR specification is here: https://eips.ethereum.org/EIPS/eip-778

Ethereum 2.0

Ethereum 2.0 represents research and specifications created with the aim of improving Ethereum, to make it more scalable and performant, with key changes such as sharding and Proof-of-Stake in its design goals.

There has been a lot of speculation if libp2p was going to be used for p2p layers and to what extent. Ethereum 2.0's sharding also produces new requirements on the discovery layers.

The new "discovery v5" will be used for Ethereum 2.0

Kademlia

Without going into all the technicalities of Kademlia (see resources below), the most relevant aspects of the system are the following:

  • Kademlia is originally intended to offer both the ability to store/find values at nodes, as well as find nodes. Discovery v4 has no use of the value storage but does make use of the routing table to locate other nodes.

  • Kademlia defines a simple communication protocol involving RPC calls Ping, Store, FindNode, and FindValue. Store and FindValue are not used by discovery v4. FindNode in discovery v4 accepts a 'target to search for' argument that is the node id (not Kademlia id)

  • Kademlia uses a 'XOR metric' to determine the 'distance' between nodes. This is achieved by simply XORing the two ids and the result is considered the distance. The same Kademlia node id XOR'd with itself yields zero, representing a zero distance to itself.

  • Discovery v4 uses SHA256(node id) as the Kademlia id. This is a 32-byte value.

  • Kademlia's routing table is a set of lists, called k-buckets (where each k-bucket holds a maximum of k endpoints and node ids). There is one list for each bit of the Kademlia id. Each list corresponds to a specific distance from the Kademlia id of the node, that distance being the range of values with that bit being the highest differing bit. One of the key characteristics of the k-buckets is that they should maintain sets of live nodes at each distance range. Live nodes are not evicted, so reliable nodes are preserved. Buckets that have not been 'touched' for a while need to be refreshed by asking neighbours to return nodes belonging to that distance range.

  • Kademlia's bootstrapping process (joining the network) and K-bucket-actualisation process rely on being able to select random ids in a specific K-bucket (distance) and query neighbouring nodes for neighbours that would belong to that K-bucket.

  • Kademlia's final paper and other implementations include variations to the original Kademlia spec. The most important of these are:

    • There can be one initial K-bucket that covers the whole range of distances from 0 to 2^32-1. This can then be split after the k-bucket becomes full (and the range of node ids permits a meaningful reallocation of node ids between k buckets). K-buckets can keep on splitting until there is one bucket per bit-distance.

    • K-bucket distance ranges can be optimised by allowing them to cover broader ranges, shortening the number of hops to find a target by repeated lookup.

Discovery v4 accepts the 64-byte public key, the node id, as the target to search for in a FindNode call. It is converted to a SHA256(node id) 32-byte Kademlia id. This means it is practically impossible to implement the Kademlia bucket-refresh scheme by selecting a random id in the bucket range.

The protocol does not try to enforce a specific variation of the implementation. It makes assumptions that each peer calculates distance metrics similarly for example. A FindNode request could result in a series of hops that diverge from rather than converge on a target. This allows for intentional or unintentional effects on the network health (see the resource links below).

"Discovery v5's" draft specification attempts to correct the problem with k-bucket refresh by changing the FindNode parameter to SHA256(node id). This allows for a random Kademlia id to be generated in a bucket range and submitted as the target for a FindNode. However, this still places the responsibility of supplying nodes according to a commonly agreed-on distance metric and overall implementation style on the FindNode implementation of the remote node. Peers must trust each other. Given that multiple p2p networks are currently sharing the same Kademlia DHT, problems should be considered inevitable. The following is a proposal to avoid this. It is first necessary to understand that the discovery protocol expressly states that there is one k-bucket per bit. No bucket-splitting is assumed. Normally, when a FindNode is issued to a node, the result can include nodes from multiple k-buckets, as close nodes will contain less than k nodes anyway, and other k-buckets may also not yet be fully populated, and Kademlia mandates that k nodes must be returned in a FindNode call if the table has them. This means it is difficult to guarantee that the k nodes returned adhere to any proximity calculation for a given bucket. The proposed solution is to change FindNode yet further, so that it accepts the bit distance, or k-bucket number, as the parameter. The bootstrapping process would then involve iteratively asking for the bucket covering the XOR distance between the sha256(target id) and sha256(asked node id). The returned results could then be checked for distance calculation and total number, with incorrect results being ignored and the node expelled from the DHT.

There are various resources online to help with a technical understanding of Kademlia. The original specifications are a couple of different versions of academic papers produced by Maymounkov and Mazieres. The Wikipedia article makes a pretty good job of explaining Kademlia in less formal language too. However, despite these resources, there are many ambiguities and variations in the interpretations and implementations of Kademlia:

This paper illustrates some difficulties with having clients with mixed distance metrics or other variations in implementation. A recent discrepancy between geth and Parity could have affected the health of the network:

Libp2p

Possibly because of the similarity with the word "devp2p," it seems that in some discussions this term has been misunderstood to be the one and only protocol suite for future versions of Ethereum.

To clarify, Libp2p is a toolset or library with several different platform implementations in various stages of development. It evolved out of the IPFS project. While Libp2p will most likely be used by some client implementers for various aspects of p2p networking, it is unrelated to devp2p discovery.

Libp2p features and implementations: https://libp2p.io/implementations/

Topic Discovery

This is an additional layer of discovery on top of the existing discovery mechanisms, allowing nodes to be both advertising media and advertisers of belonging to a certain 'topic'.

It allows nodes to advertise their own node ids in association with a certain topic. It also allows nodes to search for node ids belonging to a certain topic. There are still protocol details, such as how advertising nodes should be selected (radius selection), to be discussed, but these do not necessarily have an impact on the upcoming wire protocol. New packets supporting the registration of ads and the discovery of ads are being added.

A more detailed summary of topic discovery will be provided here when the below draft approaches finalisation.

The security considerations do not seem to address the malicious advertisement of arbitrary new topics. While the registration wait time increases exponentially per topic, what safeguard is there for creating random new FIFO topic queues at an advertiser, to flood the global registration space?

It may be that a searcher will need to look for multiple criteria. Eg: "find LES nodes on Shard X", or "Give me all LES nodes with a secp256k1 ENR id type." For these scenarios multiple ad requests are required (as opposed to having a single request that accepts AND constructs)

Consider that some 'benevolent' node has gone to the trouble of discovering (for example) a LES node already, as part of the 'non-topic' standard Kademlia bootstrap process for example. Can these serendipitous discoveries of 'rarer' nodes be exploited somehow so that the searching node voluntarily advertises the other node without a request? Should the topic list be an RLP encoded list in the ENR record? If so, it could serve as an incentive to activate features such as LES?

Draft topic discovery mechanisms are described here: https://github.com/fjl/p2p-drafts/blob/master/discv5-topics.md

Wire Protocol

Distilled from the above, the upcoming wire protocol will likely cover:

  • An alternative bonding process

  • Packet verification process (reduce or remove the possibility to obtain node id from endpoint info alone)

  • Possibly mixed id types (different curves)

  • Use existing forward compatibility, rather than try to implement a parallel protocol

  • Provide ENR records rather than tuples

  • Packet obfuscation

  • Modify FindNode to seek by bucket, rather than target id

  • New packets for ad registration and discovery

  • Most likely, timestamps/expirations will be avoided.