Protocol version v5.1

This document explains the algorithms and data structures used by the protocol.

Nodes, Records and Distances

A participant in the Node Discovery Protocol is represented by a ‘node record’ as defined in [EIP-778]. The node record keeps arbitrary information about the node. For the purposes of this protocol, the node must at least provide an IP address ("ip" or "ip6" key) and UDP port ("udp" key) in order to have it’s record relayed in the DHT.

Node records are signed according to an ‘identity scheme’. Any scheme can be used with Node Discovery Protocol, and nodes using different schemes can communicate. The identity scheme of a node record defines how a 32-byte ‘node ID’ is derived from the information contained in the record.

The ‘distance’ between two node IDs is the bitwise XOR of the IDs, taken as the big-endian number.

distance(n₁, n₂) = n₁ XOR n₂

In many situations, the logarithmic distance (i.e. length of differing suffix in bits) is used in place of the actual distance.

logdistance(n₁, n₂) = log2(distance(n₁, n₂))

Maintaining The Local Node Record

Participants should update their record, increase the sequence number and sign a new version of the record whenever their information changes. This is especially important for changes to the node’s IP address and port.

Implementations should determine the external endpoint (the Internet-facing IP address and port on which the node can be reached) and include it in their record. If communication flows through a NAT device, the UPnP/NAT-PMP protocols or the mirrored UDP envelope IP and port found in the [PONG] message can be used to determine the external IP address and port. If the endpoint cannot be determined (e.g. when the NAT doesn’t support ‘full-cone’ translation), implementations should omit IP address and UDP port from the record.

Sessions

Discovery communication is encrypted and authenticated using session keys, established in the handshake. Since every node participating in the network acts as both client and server, a handshake can be initiated by either side of communication at any time.

Handshake Steps

Step 1: Node A sends message packet

In the following definitions, we assume that node A wishes to communicate with node B, e.g. to send a FINDNODE message. Node A must have a copy of node B’s record in order to communicate with it.

If node A has session keys from prior communication with B, it encrypts its request with those keys. If no keys are known, it initiates the handshake by sending an ordinary message packet with random message content.

A -> B    FINDNODE message packet encrypted with unknown key

Step 2: Node B responds with challenge

Node B receives the message packet and extracts the source node ID from the packet header. If node B has session keys from prior communication with A, it attempts to decrypt the message data. If decryption and authentication of the message succeeds, there is no need for a handshake and node B can simply respond to the request.

If node B does not have session keys or decryption is not successful, it must initiate a handshake by responding with a [WHOAREYOU packet]. It first generates a unique id-nonce value and includes it in the packet. Node B also checks if it has a copy of node A’s record. If it does, it also includes the sequence number of this record in the challenge packet, otherwise it sets the enr-seq field to zero.

Node B must also store the A’s record and the WHOAREYOU challenge for a short duration after sending it to node A because they will be needed again in step 4.

A <- B    WHOAREYOU packet including id-nonce, enr-seq

Step 3: Node A processes the challenge

Node A receives the challenge sent by node B, which confirms that node B is alive and is ready to perform the handshake. The challenge can be traced back to the request packet which solicited it by checking the nonce, which mirrors the request packet’s nonce.

Node A proceeds with the handshake by re-sending the FINDNODE request as a [handshake message packet]. This packet contains three parts in addition to the message: id-signature, ephemeral-pubkey and record.

The handshake uses the unmasked WHOAREYOU challenge as an input:

challenge-data = masking-iv || static-header || authdata

Node A can now derive the new session keys. To do so, it first generates an ephemeral key pair on the elliptic curve used by node B’s identity scheme. As an example, let’s assume the node record of B uses the “v4” scheme. In this case the ephemeral-pubkey will be a public key on the secp256k1 curve.

ephemeral-key = random private key generated by node A
ephemeral-pubkey = public key corresponding to ephemeral-key

The ephemeral key is used to perform Diffie-Hellman key agreement with node B’s static public key and the session keys are derived from it using the HKDF key derivation function.

dest-pubkey        = public key corresponding to node B's static private key
secret             = ecdh(dest-pubkey, ephemeral-key)
kdf-info           = "discovery v5 key agreement" || node-id-A || node-id-B
prk                = HKDF-Extract(challenge-data, secret)
key-data           = HKDF-Expand(prk, kdf-info)
initiator-key      = key-data[:16]
recipient-key      = key-data[16:]

Here HKDF-Extract(salt, IKM) and HKDF-Expand are the functions defined in RFC 5869 using HMAC-SHA-256. The salt is challenge-data and the input keying material is secret; HKDF-Expand is invoked with kdf-info and produces 32 bytes of output.

Node A creates the id-signature, which proves that it controls the private key which signed its node record. The signature also prevents replay of the handshake.

id-signature-text = "discovery v5 identity proof"
id-signature-input = id-signature-text || challenge-data || ephemeral-pubkey || node-id-B
id-signature = id_sign(sha256(id-signature-input))

Finally, node A compares the enr-seq element of the WHOAREYOU challenge against its own node record sequence number. If the sequence number in the challenge is lower, it includes its record into the handshake message packet. The request is now re-sent, with the message encrypted using the new session keys.

A -> B    FINDNODE handshake message packet, encrypted with new initiator-key

Step 4: Node B receives handshake message

When node B receives the handshake message packet, it first loads the node record and WHOAREYOU challenge which it sent and stored earlier. If node B did not have the node record of node A, the handshake message packet must contain a node record. A record may also be present if node A determined that its record is newer than B’s current copy. If the packet contains a node record, B must first validate it by checking the record’s signature.

Node B then verifies the id-signature against the identity public key of A’s record. After that, B can perform the key derivation using its own static private key and the ephemeral-pubkey from the handshake packet. Using the resulting session keys, it attempts to decrypt the message contained in the packet.

If the message can be decrypted and authenticated, Node B considers the new session keys valid and responds to the message. In our example case, the response is a NODES message:

A <- B    NODES encrypted with new recipient-key

Step 5: Node A receives response message

Node A receives the message packet response and authenticates/decrypts it with the new session keys. If decryption/authentication succeeds, node B’s identity is verified and node A also considers the new session keys valid.

Identity-Specific Cryptography in the Handshake

Establishment of session keys is dependent on the [identity scheme] used by the recipient (i.e. the node which sends WHOAREYOU). Likewise, the signature over id-sig-input is made by the identity key of the initiator. It is not required that initiator and recipient use the same identity scheme in their respective node records. Implementations must be able to perform the handshake for all supported identity schemes.

At this time, the only supported identity scheme is “v4”. id_sign(hash) creates a signature over hash using the node’s static private key. The signature is encoded as the 64-byte array r || s, i.e. as the concatenation of the signature values. ecdh(pubkey, privkey) creates a secret through elliptic-curve Diffie-Hellman key agreement. The public key is multiplied by the private key to create a secret ephemeral key eph = pubkey * privkey. The 33-byte secret output is y || eph.x where y is 0x02 when eph.y is even or 0x03 when eph.y is odd.

Handshake Implementation Considerations

Since a handshake may happen at any time, UDP packets may be reordered by transmitting networking equipment, implementations must deal with certain subtleties regarding the handshake.

In general, implementations should keep a reference to all sent request packets until the request either times out, is answered by the corresponding response packet or answered by WHOAREYOU. If WHOAREYOU is received as the answer to a request, the request must be re-sent as a handshake packet.

If an implementation supports sending concurrent requests, multiple responses may be pending when WHOAREYOU is received, as in the following example:

A -> B    FINDNODE
A -> B    PING
A -> B    TOPICQUERY
A <- B    WHOAREYOU (nonce references PING)

When this happens, all buffered requests can be considered invalid (the remote end cannot decrypt them) and the packet referenced by the WHOAREYOU nonce (in this example: PING) must be re-sent as a handshake. When the response to the re-sent is received, the new session is established and other pending requests (example: FINDNODE, TOPICQUERY) may be re-sent. Note that WHOAREYOU is only ever valid as a response to a previously sent request. If WHOAREYOU is received but no requests are pending, the handshake attempt can be ignored.

Another important issue is the processing of message packets while a challenge is received: consider the case where node A has sent a packet that B cannot decrypt, and B has responded with WHOAREYOU.

A -> B    FINDNODE
A <- B    WHOAREYOU

Node B is now waiting for a handshake message packet to complete the new session, but instead receives another ordinary message packet.

A -> B    ORDINARY MESSAGE PACKET

In this case, implementations should re-send the challenge which is already in progress, i.e. the WHOAREYOU packet referencing the earlier message packet, instead of creating a new challenge.

Session Cache

Nodes should store session keys for communication with other recently-seen nodes. Since sessions are ephemeral and can be re-established whenever necessary, it is sufficient to store a limited number of sessions in an in-memory LRU cache. To prevent IP spoofing attacks, implementations must ensure that session secrets and the handshake are tied to a specific UDP endpoint. This is simple to implement by using the node ID and IP/port as the ‘key’ into the in-memory session cache.

When a node switches endpoints, e.g. when roaming between different wireless networks, sessions will have to be re-established by handshaking again. This requires no effort on behalf of the roaming node because the recipients of protocol messages will simply refuse to decrypt messages from the new endpoint and reply with WHOAREYOU.

The number of messages which can be encrypted with a certain session key is limited because encryption of each message requires a unique nonce for AES-GCM. In addition to the keys, the session cache must also keep track of the count of outgoing messages to ensure the uniqueness of nonce values. Since the wire protocol uses 96 bit AES-GCM nonces, it is strongly recommended to generate them by encoding the current outgoing message count into the first 32 bits of the nonce and filling the remaining 64 bits with random data generated by a cryptographically secure random number generator.

Node Table

Nodes keep information about other nodes in their neighborhood. Neighbor nodes are stored in a routing table consisting of ‘k-buckets’. For each 0 ≤ i < 256, every node keeps a k-bucket for nodes of logdistance(self, n) == i. The Node Discovery Protocol uses k = 16, i.e. every k-bucket contains up to 16 node entries. The entries are sorted by time last seen — least-recently seen node at the head, most-recently seen at the tail.

Whenever a new node N₁ is encountered, it can be inserted into the corresponding bucket. If the bucket contains less than k entries N₁ can simply be added as the first entry. If the bucket already contains k entries, the liveness of the least recently seen node in the bucket, N₂, needs to be revalidated. If no reply is received from N₂ it is considered dead, removed and N₁ added to the front of the bucket.

Neighbors of very low distance are unlikely to occur in practice. Implementations may omit k-buckets for low distances.

Table Maintenance In Practice

Nodes are expected to keep track of their close neighbors and regularly refresh their information. To do so, a lookup targeting the least recently refreshed bucket should be performed at regular intervals.

Checking node liveness whenever a node is to be added to a bucket is impractical and creates a DoS vector. Implementations should perform liveness checks asynchronously with bucket addition and occasionally verify that a random node in a random bucket is live by sending [PING]. When the PONG response indicates that a new version of the node record is available, the liveness check should pull the new record and update it in the local table. If a node’s liveness has been verified many times, implementations may consider occasional non-responsiveness permissible and assume the node is live.

When responding to FINDNODE, implementations must avoid relaying any nodes whose liveness has not been verified. This is easy to achieve by storing an additional flag per node in the table, tracking whether the node has ever successfully responded to a PING request.

In order to keep all k-bucket positions occupied even when bucket members fail liveness checks, it is strongly recommended to maintain a ‘replacement cache’ alongside each bucket. This cache holds recently-seen nodes which would fall into the corresponding bucket but cannot become a member of the bucket because it is already at capacity. Once a bucket member becomes unresponsive, a replacement can be chosen from the cache.

Lookup

A ‘lookup’ locates the k closest nodes to a node ID. The lookup initiator starts by picking α closest nodes to the target it knows of from the local table. The initiator then sends FINDNODE requests to those nodes.

α is an implementation-defined concurrency parameter, typically 3. As NODES responses are received, the initiator resends FINDNODE to nodes it has learned about from previous queries. Of the k nodes the initiator has heard of closest to the target, it picks α that it has not yet queried and sends FINDNODE to them. The lookup terminates when the initiator has queried and gotten responses from the k closest nodes it has seen.

To improve the resilience of lookups against adversarial nodes, the algorithm may be adapted to perform network traversal on multiple disjoint paths. Not only does this approach benefit security, it also improves effectiveness because more nodes are visited during a single lookup.

The initial k closest nodes are partitioned into multiple independent ‘path’ buckets, and concurrent FINDNODE requests executed as described above, with one difference: results discovered on one path are not reused on another, i.e. each path attempts to reach the closest nodes to the lookup target independently without reusing intermediate results found on another path. Note that it is still necessary to track previously asked nodes across all paths to keep the paths disjoint.

Lookup Protocol

This section shows how the wire protocol messages can be used to perform a lookup interaction against a single node.

Node A is looking for target x. It selects node B from the local table or intermediate lookup results. To query for nodes close to x on B, node A computes the query distance d = logdistance(B, x) and sends its request.

A -> B    FINDNODE [d]

Node B responds with multiple nodes messages containing the nodes at the queried distance.

A <- B    NODES [N₁, N₂, N₃]
A <- B    NODES [N₄, N₅]

Depending on the value of d and the content of Bs table, the response to the initial query might contain very few nodes or no nodes at all. Should this be the case, A varies the distance to retrieve more nodes from adjacent k-buckets on B:

A -> B    FINDNODE [d+1]

B responds with more nodes:

A <- B    NODES [N₆, N₇]

Node A now sorts all received nodes by distance to the lookup target and proceeds by repeating the lookup procedure on another, closer node.

Topic-based Service Discovery

Topic-based discovery (TopDisc) extends Discovery v5 with a mechanism to discover nodes according to their provided services (topics). It allows nodes to advertise participation in a service and allows other nodes to discover those advertisements while reusing the existing Node Table and ENR mechanisms.

Co-existence with Node Discovery

The TopDisc system builds on the basic routing of discv5. A TopDisc-capable node first joins the network using FINDNODE and populates its local node table, learning about TopDisc capable nodes. These nodes are then used to bootstrap service tables (see below). As registration and lookup operations proceed, TopDisc-capable nodes can also return additional nodes to improve the service tables, as described below.

A TopDisc failure does not by itself imply an ordinary Discovery v5 failure. A node may be usable for ordinary node discovery but unusable for registration or lookup. Conversely, a node that fails ordinary Discovery v5 liveness checks ceases to be eligible for insertion into service tables.

ENR Capability

A node indicates support for service discovery messages by including the ng ENR entry.

ng = <version>

The value of ng is an unsigned integer identifying the supported TopDisc protocol version. Nodes whose ENR does not contain ng, or whose ng value is not supported by the local implementation are not inserted into service tables and are not selected for registration or lookup requests.

Services and Service Identifiers

TopDisc operates on 32-byte service identifiers. A service identifier denotes a higher-level service, subnetwork, overlay, or protocol-specific discovery target.

Service identifiers are in the same 256-bit identifier space as Node IDs. This allows TopDisc to apply the Node Discovery v5 XOR distance function between service identifiers and node IDs.

The mapping from higher-level service names or application-specific parameters to service identifiers is defined by the relevant service binding. Such parameters MAY include, for example, protocol name, network name, fork identifier, client capability, subnet identifier, or other service-specific values.

This document does not define a canonical derivation rule for service identifiers. The application can choose its identifiers freely.

Node Roles

A node that advertises ng capability in its ENR acts as a registrar, subject to local policy and resource limits.

A registrar accepts registration and lookup requests, admits advertisements into its local ad cache, and returns admitted advertisements to discoverers.

A TopDisc-capable node may also act as an advertiser, a discoverer, or both.

An advertiser participates in a service and registers advertisements for that service with registrars. A node acts as an advertiser only for services that it chooses to advertise.

A discoverer queries registrars to obtain advertisements for a target service. A node acts as a discoverer only when it is looking up peers for a service.

The roles are not mutually exclusive. A single node can simultaneously act as a registrar, advertise one or more services, and discover peers for one or more services.

Service Tables

A service table B(s) is a per-service node table centred on service identifier s, rather than on the local node ID.

Similar to the ordinary Node Table, B(s) is divided into distance buckets. The difference is the reference point used to assign nodes to buckets. In the ordinary node table, a node n is placed according to logdistance(self, n), where self is the local node ID. In a service table, the same node n is placed according to logdistance(s, n), where s is the service identifier.

For each 0 ≤ i < 256, bucket bᵢ(s) contains TopDisc-capable nodes whose node IDs are at logarithmic distance i from the service identifier:

bᵢ(s) = { n | logdistance(s, n) = i }

Thus, B(s) gives the local node a service-centred view of the discovery network. Buckets closer to s contain nodes whose IDs are closer to the service identifier, while buckets farther from s contain nodes from progressively larger regions of the key space.

A node may maintain a service table for each service identifier for which it performs TopDisc operations. Advertisers use B(s) as an advertise table for service s; discoverers use B(s) as a search table for service s.

The registrar ad cache is separate from service tables. A registrar does not need to maintain B(s) for every service represented in its ad cache.

Bootstrap from Ordinary Node Discovery

A node does not start advertisement placement or lookup from an empty service table.

The node first joins the Node Discovery v5 network using the standard bootstrapping procedure. It populates its ordinary local node table through the existing PING, PONG, FINDNODE, lookup, refresh, and liveness mechanisms.

For a service identifier s, the initial service table

B(s) = { b₀(s), b₁(s), ..., b₂₅₅(s) }

is derived from the ordinary node table. When constructing this initial service table, implementations should:

1. take nodes currently known in the ordinary node table;
2. discard nodes whose ENR does not advertise a supported TopDisc version;
3. discard nodes whose liveness has not been verified by the ordinary Node Discovery v5 table-maintenance rules;
4. discard nodes currently excluded by local TopDisc usability policy;
5. insert each remaining node into the corresponding bucket of B(s).

The resulting B(s) is soft state. It need not be complete before operations begin. If the ordinary node table contains too few nodes that can be used for operations, implementations should continue ordinary Node Discovery v5 refresh and lookup operations until more candidates are learned.

Ongoing Maintenance of B(s)

A service table is maintained from two sources:

1. the ordinary Discovery v5 node table; and
2. auxiliary ENRs learned through NODES delivered as a response to TOPICQUERY.

When a newly verified node advertising TopDisc capability is learned through ordinary discovery, it becomes eligible for insertion into relevant service tables.

Responses to registration and lookup requests may include auxiliary ENRs selected from the responder’s view of the service table. Such ENRs may be inserted into B(s) only after ENR validation, capability checking, and any local usability checks.

Over time, this causes B(s) to become better aligned with the service identifier than the ordinary local node table, while still remaining anchored in ordinary Discovery v5 state.

Auxiliary ENR Selection

TopDisc responses may include auxiliary ENRs. Auxiliary ENRs are routing information used by the requester to improve its local service table B(s); they are not service lookup results.

A request may carry a list of topic-distances at which the requester’s service table has free space. A topic-distance is a logarithmic distance from the service identifier s to a node ID, and therefore identifies a bucket of B(s).

When such a list is present, the registrar SHOULD use it as a hint for auxiliary ENR selection. For each requested topic-distance d, the registrar SHOULD return at most one ENR for a TopDisc-capable node n such that:

logdistance(s, n) = d

The registrar may obtain such ENRs from any local source of known TopDisc-capable nodes, including an existing service table B(s), the ordinary node table filtered to TopDisc-capable nodes, or an implementation-local cache. A registrar is not required to maintain a service table for every service represented in its ad cache.

A recommended selection algorithm is:

1. iterate over the topic-distances supplied by the requester;
2. for each distance d, select at most one known TopDisc-capable node whose node ID satisfies logdistance(s, n) = d;
3. prefer pseudo-random selection when multiple eligible ENRs are available for the same distance;
4. skip ENRs that fail local validation or usability checks;
5. stop when all requested distances have been considered or when an implementation-defined cap on auxiliary ENRs has been reached.

Selecting at most one ENR per requested distance keeps responses compact and spreads coverage across the requester’s free buckets. It avoids overrepresenting a single distance and reduces the ability of a responder to fill a response with many ENRs from one bucket.

If the registrar has no eligible ENR for a requested distance, it omits that auxiliary ENR.

The same auxiliary-ENR selection rule applies to registration responses and lookup responses.

TopDisc Liveness and Temporary Exclusion

A node advertising TopDisc capability is not automatically a usable registrar for every TopDisc operation. It may time out, return malformed responses, reject requests, or fail to implement the extension correctly.

Implementations should therefore maintain TopDisc-level usability state for nodes in B(s).

If a node in B(s) repeatedly fails to answer registration or lookup requests, times out, or returns malformed responses, implementations should temporarily exclude that node from selection for operations. Temporary exclusion may be implemented by removing the node from B(s), suppressing its selection for a backoff period, or assigning it lower selection priority.

Temporary exclusion is not a permanent blacklist. After the backoff period expires, the node may become eligible for re-insertion into B(s) if it is still present in the ordinary node table, still advertises TopDisc capability, and still satisfies ordinary Discovery v5 liveness requirements.

Failure of a request does not by itself require removal from the ordinary Discovery v5 node table. Retention in the ordinary node table continues to follow Discovery v5 liveness and table-maintenance rules.

Registrar Behaviour

Ad Cache

A registrar stores admitted advertisements in a bounded ad cache.

Each admitted advertisement expires after duration E. The ad cache has capacity C. A registrar stores at most one active advertisement for the same advertiser and service.

The ad cache is not a service table. It is registrar-local storage used to answer service lookup requests.

An ad cache entry contains at least:

• the service identifier;
• the advertiser ENR;
• the expiry time;
• any advertisement payload defined by the service binding or wire-format document.

Implementations may maintain additional indices for efficient retrieval by service, expiry time, advertiser, and IP prefix.

Expired advertisements are removed automatically. Once an advertisement expires, it is no longer returned in lookup responses.

If a registrar receives a registration request for an advertisement that is already present in its ad cache, the registrar may treat the request as a renewal or ignore it, depending on the renewal semantics specified by the wire-format document. The registrar must not store duplicate active advertisements for the same advertiser and service.

Advertisements

An advertisement states that the node identified by an ENR participates in a service/topic.

An advertisement is defined as:

ad = [topic, ENR]

where:

• topic is the 32-byte service/topic identifier;
• ENR is the advertised node record.

The advertisement digest is:

ad-digest = H(ad)

where H is the digest function defined for ticket construction.

If future versions allow service-specific advertisement payloads, the advertisement definition becomes:

ad = [topic, ENR, payload]

Admission Control

Registrars use admission control to decide whether and when an incoming registration request for an advertisement may be admitted to the ad cache.

Admission is based on a waiting-time mechanism. If an advertisement is not admitted immediately, the registrar returns a ticket and a waiting time. This mechanism promotes diversity in the ad cache and avoids requiring registrars to keep unbounded per-request state for pending registrations.

When a registrar receives a registration request, it computes a waiting time from the current state of the ad cache and the incoming advertisement. If the effective remaining waiting time is less than or equal to zero, the advertisement is admitted. Otherwise, the registrar returns a ticket and a waiting time.

The registrar does not need to keep per-request state for pending registrations. Instead, the state needed to prove accumulated waiting time is carried by the advertiser in the registrar-issued ticket.

The waiting time in a ticket is not binding. On each retry, the registrar recomputes the waiting time using the current ad cache state. The advertiser is admitted only when its accumulated waiting time is sufficient according to the recomputed waiting time.

If an advertiser retries too early, retries too late, omits the latest ticket, or presents an invalid ticket, the registrar treats the request as a new registration attempt or rejects it, depending on the wire-format rules.

Tickets

A ticket is a registrar-issued, registrar-authenticated object that allows an advertiser to retry a registration attempt after waiting.

A ticket is bound to a specific advertisement and registrar. The advertisement is denoted ad and includes the service identifier, the advertised ENR, and any service-specific advertisement payload. The ticket contains a digest of this advertisement, denoted adDigest.

The advertiser uses the latest ticket issued by the registrar when retrying the registration. A ticket issued for one advertisement or registrar MUST NOT be accepted for a different registration request. In particular, a ticket issued for one service, advertised ENR, or advertisement payload MUST NOT be reused for another.

The ticket is opaque to the advertiser. The advertiser does not interpret the ticket contents; it stores the latest ticket returned by the registrar and presents it in the next registration attempt to the same registrar. The exact ticket encoding, digest function, authentication mechanism, signature format, and signature domain are specified in the wire-format document.

Algorithmically, a ticket contains enough authenticated information for the registrar to verify:

• adDigest: the digest of the advertisement to which the ticket applies;
• tinit: the registrar-local time at which the ticket was first issued;
• tmod: the registrar-local time at which the ticket was last modified;
• twait: the remaining waiting duration reported to the advertiser;
• auth: registrar authentication over the ticket contents.

The registrar authenticates the ticket, for example by signing the ticket body or applying a registrar-local MAC. A registrar MUST reject a ticket that fails authentication or that was not issued by that registrar.

The timestamps tinit and tmod are generated and interpreted only by the registrar. They are local to the registrar and are not compared against the advertiser’s clock. The only timing value used by the advertiser is the relative waiting duration twait reported by the registrar in the registration response.

A retry is valid only during the registration window associated with the ticket:

tmod + twait ≤ now ≤ tmod + twait + δ

where now is the registrar’s current local time when processing the retry, and δ is the registration window duration.

The advertiser does not use tmod to schedule the retry and does not need its clock to be synchronised with the registrar’s clock. The advertiser waits for the relative duration twait using its own local timer, then retries with the latest ticket. The registrar validates the retry window using its own clock when the ticket is presented again.

When a returning advertiser presents a valid ticket, the registrar computes the accumulated waiting duration as:

waited = now - tinit

where now and tinit are both interpreted according to the registrar’s local clock.

If the retry is too early, too late, does not include the latest ticket, includes a ticket whose adDigest does not match the advertisement in the current registration request, or includes an invalid ticket, the registrar SHOULD reject the request or treat it as a new registration attempt according to the registration rules.

Because the ticket is bound to adDigest, changing the service identifier, advertised ENR, or service-specific advertisement payload during a registration attempt requires starting a new registration attempt or obtaining a new ticket for the updated advertisement.

Waiting-Time Function

The waiting-time function determines how long an advertisement must wait before admission.

The function depends on the current ad cache occupancy, the number of cached advertisements for the same service, the IP similarity of the advertiser, and a safety constant. The waiting time shapes the contents of the ad cache and provides flow control at the registrar.

The waiting time is:

w(ad) = E * 1 / (1 - c/C)^Pocc * ( c(ad.service)/c + score(ad.IP) + G )

where:

• E is the advertisement expiry duration;
• C is the ad cache capacity;
• c is the current number of advertisements in the cache; when c = 0, the service-similarity term is defined as 0.
• c(ad.service) is the number of cached advertisements for the service being advertised;
• score(ad.IP) is the IP similarity score computed from the advertiser’s IP (ad.IP) in the advertised ENR;
• Pocc is the occupancy exponent;
• G is the safety constant.

The occupancy component increases the waiting time as the ad cache approaches capacity. This limits the rate at which new advertisements can be admitted.

The service-similarity component increases the waiting time for services that are already well represented in the cache. This makes it easier for less represented services to obtain cache entries.

The IP-similarity component increases the waiting time for advertisers whose IP prefixes are overrepresented in the cache. This discourages a small number of IP prefixes from dominating the registrar’s ad cache.

The safety constant prevents the waiting time from becoming zero when the cache is sparsely populated and the incoming advertisement appears dissimilar to existing entries.

When a returning advertiser presents a valid ticket, the registrar computes the effective remaining waiting time as:

tremaining = w(current-cache, ad) - (now - tinit)

where tinit is the ticket creation time. The advertisement is admitted when tremaining ≤ 0.

IP Similarity Tree

Registrars maintain an IP-prefix tree over the IP addresses of admitted advertisements.

The tree is used to compute the IP similarity score. Prefixes that are overrepresented in the ad cache increase the score, causing advertisements from similar IP prefixes to receive higher waiting times.

For IPv4, the tree has 32 levels below the root. Each edge corresponds to one bit of the IP address, and each vertex stores a counter. The root counter represents the total number of IP addresses represented in the ad cache.

To score an IP address, the registrar walks the tree along the bits of the address. At each level, the registrar compares the observed counter for the corresponding prefix with the counter expected in a perfectly balanced tree. Prefixes that are overrepresented contribute to the score.

The resulting score is normalised to the interval [0, 1].

The tree is updated when advertisements are admitted or expire. When an advertisement is admitted, counters along the path corresponding to the advertiser’s IP address are incremented. When the advertisement expires or is removed, those counters are decremented.

For IPv6, the same construction applies over 128 address bits. Implementations that support both IPv4 and IPv6 should define whether separate trees are maintained or whether addresses are mapped into a common representation.

Waiting-Time Lower Bound

Registrars enforce a lower bound on waiting times so that an advertiser cannot obtain a better effective waiting time by repeatedly requesting new tickets.

Without a lower bound, a pending advertiser could repeatedly request new tickets in the hope that cache changes cause a lower waiting time. The lower-bound rule ensures that a new waiting time cannot improve on the old one by more than the elapsed time.

Registrars do not maintain unbounded per-request lower-bound state for pending registrations. Lower-bound state is maintained only for bounded structures, such as:

• services already represented in the ad cache; and
• prefixes represented in the IP similarity tree.

When a service s enters the ad cache for the first time, the registrar initialises lower-bound state for s. When a later ticket request for s arrives, the registrar computes the service waiting-time component and applies the stored lower bound before issuing a new ticket.

For IP addresses, lower-bound state is maintained at the IP-tree vertex corresponding to the longest prefix match already present in the tree, without introducing new vertices only for pending requests. If multiple IP addresses map to the same vertex, the registrar aggregates their lower-bound state using a maximum.

Advertiser Behaviour

Advertisement Placement

For each service s that a node advertises, the advertiser attempts to maintain up to K_register active or pending registrations in each bucket of its advertise table B(s).

Candidate registrars are selected from the corresponding bucket of the advertise table. Placement starts from the furthest bucket from s and progresses towards the closest bucket.

The advertiser maintains per-bucket state for ongoing and active registrations. This state records the registrars for which an advertisement attempt is already pending or active, so that the advertiser does not repeatedly choose the same registrar when filling the same bucket.

Within a placement cycle, registrar selection should not repeatedly return the same registrar from the same bucket.

For each bucket bᵢ(s), while the number of active or pending registrations in that bucket is below K_register, the advertiser selects a candidate registrar from bᵢ(s) and starts a registration attempt.

If no eligible registrar remains in the bucket, the advertiser stops trying to fill that bucket during the current placement cycle. The bucket may be attempted again later after the service table is refreshed or after temporary exclusions expire.

Advertisement placement is continuous soft state. Advertisers periodically repeat placement and renewal so that advertisements remain available despite expiry, churn, registrar failure, and changes in the service table.

Registration Procedure

An advertiser registers an advertisement by sending a registration request to a selected registrar. The corresponding wire-format request is specified in REGTOPIC.

The first registration request for an advertisement is sent without a ticket. The registrar either admits the advertisement immediately or returns a ticket and a waiting time in a REGCONFIRMATION response.

If the registrar returns a ticket, the advertiser waits before retrying with the latest ticket. A single waiting interval SHOULD NOT exceed E, the advertisement expiry duration. If the registrar still cannot admit the advertisement after the retry, it may return an updated ticket and a new waiting time.

The protocol does not define a fixed maximum total duration for a registration attempt. An implementation MAY abandon an attempt after a local timeout, after a configured maximum number of retries, or if the registrar is considered unusable according to local liveness policy.

A registration attempt fails if the registrar is unreachable, rejects the request, returns malformed responses, the registration window is missed, a local retry or timeout limit is reached, or the registrar is otherwise considered unusable according to local liveness policy. On failure, the advertiser removes the registrar from the pending state for that bucket and may select another registrar.

When registration succeeds, the advertisement remains stored by the registrar until it expires, unless it is removed earlier by registrar policy.

Registration responses may include auxiliary ENRs selected from the registrar’s view of the service table. The advertiser may use these ENRs to update its advertise table B(s) after validating the ENRs, checking TopDisc capability, and applying local usability policy. The recommended auxiliary-ENR selection rule is described in Auxiliary ENR Selection.

Renewal

An admitted advertisement remains stored until its expiry time E.

Advertisers should renew advertisements before expiry, or continuously maintain enough active and pending registrations, to preserve the target number of placements in each bucket.

A renewal is a new registration attempt for an advertisement already admitted or about to expire. The exact renewal encoding and the treatment of duplicate registrations are specified by the wire-format document.

If a renewal fails, the advertiser may attempt to register with another eligible registrar in the same bucket.

Advertisers should treat registrations as soft state. The target is not to permanently bind a service to a fixed set of registrars, but to maintain sufficient active or pending placements across the service-centred key space.

Discoverer Behaviour

Lookup Procedure

A discoverer looking for service s queries registrars selected from its search table B(s). The corresponding wire-format request is specified in TOPICQUERY. Lookup proceeds bucket by bucket, starting from the bucket furthest from s and progressing towards buckets closer to s. For each bucket bᵢ(s), the discoverer selects candidate registrars from that bucket and queries up to K_lookup of them.

A registrar returns advertisements for service s in TOPICNODES responses. The discoverer validates the returned advertisements, extracts the advertised ENRs, and de-duplicates them by advertiser identity. Advertisements are candidate results for the target service. The lookup terminates when the discoverer has collected enough distinct advertisers for its local or service-specific purpose, or when no unqueried registrars remain. This local target is denoted F_lookup in this document. The value of F_lookup is determined by the application, service binding, or local implementation policy, rather than by the TopDisc lookup procedure itself. If fewer than F_lookup advertisers are found before all available candidate registrars are exhausted, the lookup returns the valid advertisers collected so far.

The same registrar should not be queried repeatedly during a single lookup unless the implementation has exhausted other candidates and chooses to retry according to local policy. If a queried registrar is unreachable, times out, or returns a malformed response, the discoverer treats that query as failed and continues with another candidate. Repeated failures may cause the registrar to be temporarily excluded from operations.

Lookup responses may also include auxiliary ENRs in NODES responses. These ENRs are not lookup results; they are auxiliary routing information used to improve the discoverer’s search table B(s). The recommended auxiliary-ENR selection rule is described in Auxiliary ENR Selection.

Lookup Responses

A registrar receiving a lookup request for service s returns advertisements for that service from its ad cache. A registrar receiving a TOPICQUERY request for service s returns advertisements and auxiliary ENRs using the response format defined for TOPICQUERY in the wire specification.

The registrar MUST NOT return expired advertisements. If more than F_return advertisements for the service are present in its ad cache, the registrar SHOULD return a pseudo-random subset of at most Freturn advertisements. The selection procedure SHOULD avoid deterministic bias towards the same advertisers across repeated lookup requests.

A registrar may also return auxiliary ENRs selected from its view of the service table for s. These ENRs are not lookup results; they are auxiliary routing information used to improve future registration and lookup operations.

The requester uses returned auxiliary ENRs to update its local service table B(s) after validating the ENRs, checking TopDisc capability, and applying local usability policy. The exact encoding of returned advertisements, auxiliary ENRs, and any topic-distance list is specified in the wire-format document.

Updating the Search Table During Lookup

The discoverer updates B(s) using auxiliary ENRs returned in lookup responses.

An ENR learned through lookup is eligible for insertion into B(s) only if:

1. the ENR is valid;
2. the ENR advertises TopDisc capability;
3. the node is not temporarily excluded by local TopDisc usability policy;
4. the node satisfies ordinary Discovery v5 liveness requirements, or is scheduled for ordinary liveness verification.

Implementations may insert learned ENRs immediately with an unverified flag and verify liveness asynchronously.

Parameters

The TopDisc algorithms use the following parameters:

Implementation Considerations

ENR Freshness

Advertisers should send their current ENR when registering an advertisement.

Registrars should store the ENR that was admitted and return that ENR in lookup responses until the advertisement expires or is renewed.

Clocks

TopDisc does not require clock synchronisation between advertisers and registrars.

Tickets carry registrar-generated timing information. Advertisers only need to wait for the duration indicated by the registrar before retrying.

Response Splitting

TopDisc responses may be split across multiple packets when supported by the wire protocol.

Implementations should collect all response packets belonging to the same request until the announced response count is reached or the request times out.

Wire Encoding

This document describes algorithms and data structures.

The exact encoding of TopDisc messages, ticket signatures, request identifiers, response splitting, returned advertisements, neighbour ENRs, and any application-specific advertisement payload is specified in the wire-format document.