3.4 Neighbor Selection

3.4.1 Introduction

This section defines the Neighbor Selection protocol, its logic and the different requests and responses exchanged between nodes.

In order for the network to work efficiently and for the nodes to be kept up-to-date about the ledger state, nodes exchange information with each other. Each node establishes a communication channel with a small subset of nodes (i.e., neighbors) via a process called peering. Such a process must be resilient against eclipse attacks: if all of a node’s neighbors are controlled by an attacker, then the attacker has complete control over the node’s view of the Tangle. Moreover, to prevent or limitate sybil-based attacks, the neighbor selection protocol makes use of a scarce resource dubbed Consensus Mana: arbitrary nodes can be created, but it is difficult to produce high mana nodes.

Throughout this section, the terms Node and Peer are used interchangeably to refer to a Node device. The term neighbors implies a mutual relationship between two nodes put in place as a direct connection established and used by the gossip layer.

The Neighbor Selection specification depends on the following specifications:

• 3.3 - Peer discovery.
• 5.3 - Mana.

3.4.2 Detailed design

The goal of the neighbor selection is to build a node's neighborhood (to be used by the gossip protocol) while preventing attackers from “tricking” other nodes into becoming neighbors. Neighbors are established when one node sends a peering request to another node, which in turn accepts or rejects the request with a peering response.

To prevent attacks, the protocol makes the peering request verifiably random such that attackers cannot create nodes to which the target node will send requests. At its core, the neighbor selection protocol uses both a screening process called Consensus Mana rank and a score function that takes into account some randomness dubbed private salt and public salt. Half of the neighbors will be constituted from nodes that accepted the peering request, while half will be constituted of nodes that will request for the peering. The two distinct groups of neighbors are consequently called:

• Chosen neighbors (outbound). The peers that the node proactively selected through the neighbor selection mechanism.
• Accepted neighbors (inbound). The peers that sent the peering request to the node and were accepted as a neighbor.

3.4.2.1 Local variables

Local variables defined here are included to help in understanding the protocol described in this section. The node application shall handle those variables in some form.

Name	Type	Description
saltUpdateInterval	duration	The time interval at which nodes shall update their salts.
responseTimeout	duration	The time that node waits for a response during one peering attempt.
requestExpirationTime	duration	The time used for the request timestamp validation, if the timestamp is older than this threshold the request is dropped.
maxPeeringAttempts	integer	The maximum number of peering requests retries sent to the selected node before the next salt update.

3.4.2.2 Node identities

As for the peer discovery protocol, every node has a cryptographic identity, a key on the Ed25519 elliptic curve. The blake2b hash of the public key of the peer node serves as its identifier or node ID.

3.4.2.3 Salt generation

Nodes shall have a public and private salt both defined as array bytes of size 20. Nodes shall update both their public and private salt at a common fixed time interval saltUpdateInterval (e.g. 3 hours). The public salt is used for outbound peering requests, while the private salt is used during inbound peering requests.

The public salt must satisfy the following requirements:

1. Future salts must be unguessable: mining node ids to reduce the request score shall be prohibitive. This offers protection for the requesting nodes.
2. Salts must be chosen in a non-arbitrary way: if adversaries may choose their salt, they could manufacture malicious requests to any node.

This section proposes to set the public salts using hash chains, while private salts can be randomly generated on the fly. The nodes shall create a hash chain ζ = {ζ_0, ζ_1, ..., ζ_m} where next chain element is created by hashing the previous one: ζ_{i+1} = hash(ζ_i). Then nodes shall make public the last element ζ_m of their hash chain as their initial salt. Every future salt is the next element of the hash chain. Under this proposal, property 1 above holds because cryptographic hash functions are virtually irreversible. Property 2 holds fairly well: an adversary can only choose one element of their hash chain. Indeed, an adversary can pick a number to be their 300th salt, hash it 300 times, and post that as their initial salt. However, an adversary can only do this for one round since hash functions have effectively random outputs. Thus an adversary is limited in their ability to choose their own salt.

3.4.2.4 Mana rank interval

Each peer discovered and verified via the Peer Discovery protocol shall have a consensus mana value associated with it. The peer running the Neighbor Selection protocol shall keep this information up-to-date and use it to update a data structure called manaRank containing the list of the nodes' identities for each mana value. The aim of this ranking is to select a subset of peers having similar mana to the node preparing the ranking. More specifically, let's define potentialNeighbors to be such a subset, that is divided into a lower and an upper set with respect to a targetMana value (i.e., the mana value of the node performing the ranking). By iterating over the manaRank, each node shall fill both the lower and upper sets with nodes' identities having a similar rank to itself, not less/greater than a given threshold rho respectively, except when each subset does not reach the minimal size r.

The following pseudocode describes a reference implementation of this process:

Inputs:
    manaRank: mapping between mana values and the list of nodes' identities with that mana;
    targetMana: the mana value of the node performing the ranking;
    rho: the ratio determining the length of the rank to consider;
    r: the minimum number of nodes' identities to return for both lower and upper sets;
    Largest(r, targetMana): the set of r largest cMana holders less than targetMana;
    Smallest(r, targetMana): the set of r smallest cMana holders greater than targetMana;

Outputs:
    potentialNeighbors: the set of nodes' identities to consider for neighbor selection;

FOR mana IN manaRank
    nodeID = manaRank[mana]
    IF mana > targetMana
        IF mana / targetMana < rho
            Append(upperSet, nodeID)
    ELSE IF mana == 0 || mana == targetMana
        BREAK
    ELSE IF targetMana / mana < rho
        Append(lowerSet, nodeID)

IF Len(lowerSet) < r
    // set lowerSet with the r largest mana holders less than targetMana
    lowerSet = Largest(r, targetMana)

IF Len(upperSet) < r
    // set upperSet with the r smallest mana holders greater than targetMana
    upperSet = Smallest(r, targetMana)

potentialNeighbors = Append(upperSet, lowerSet)
RETURN potentialNeighbors

3.4.2.5 Selection

The maximum number of neighbors is a parameter of the gossip protocol. This section proposes to use a size of 8 equally divided into 4 chosen (outbound) and 4 accepted (inbound) neighbors. It is crucial to decide on a fixed number of neighbors, as the constant number decreases an eclipse probability exponentially. The chosen k is a compromise between having more connections resulting in lower performance and increased protection from an eclipse attack.

The operations involved during neighbor selection are listed in the following:

1. Get an up-to-date list of verified and known peers from the Peer Discovery protocol.
2. Use mana rank to filter the previous list to obtain a list of peers to be potential neighbors.
3. Use the score function to request/accept neighbors.

The score between two nodes is measured through the score function s, defined by:

s(nodeID1, nodeID2, salt) = hash(nodeID1 || nodeID2 || salt), where:

• nodeID1 and nodeID2 are the identities of the considered nodes.
• salt is the salt value that can be private or public depending on the peering direction (inbound/outbound).
• hash is the blake2b hash function.
• || is the concatanation operation.

Note that the value used as the score is an unsigned integer derived from the first 4 bytes of the byte array after the hash function.

In order to connect to new neighbors, each node with ID ownID and public salt pubSalt keeps a list of potential neighbors derived via Mana rank that is sorted by their score d(ownID, ·, pubSalt). Then, the node shall send peering requests in ascending order, containing its own current public salt and a timestamp representing the issuance time of the request. The connecting node shall repeat this process until it has established connections to enough neighbors or it finds closer peers. Those neighbors make up its list of chosen neighbors. This entire process is also illustrated in the following pseudocode:

Inputs:
    k: desired amount of neighbors;
    c: current list of chosen neighbors;
    p: list of potential peers;
    localID: local nodeID
    pubSalt: local public salt;

pSorted = SortByScoreAsc(P, localID, pubSalt)
FOR p IN pSorted
    peeringRequest = SendPeeringRequest(p)
    IF peeringRequest.accepted
        Append(c, p)
        IF Len(c) == Ceil(k/2)
            RETURN

More specifically, after sending a peering request a node shall:

• wait to get a Peering Response that could be positive or negative.
  • If positive, add the peer to its chosen neighbor list
  • If negative, filter out the peer from future requests until the next salt update or the end of the list of potential neighbors is reached.
  • If after responseTimeout no response is received, try again for a fixed maxPeeringAttempts. If not successful, filter out the peer from future requests until the next salt update or the end of the list of potential neighbors is reached.

Similar to the previous case, in order to accept neighbors, every node with ID ownID shall generate a private salt privSalt.

Upon reception of a Peering Request, a peer shall make a decision to accept, reject or discard the request by:

• verifying that the signature of the Peering Request is valid and discard the request otherwise;
• checking that the timestamp field is valid (i.e., not older than a given threshold requestExpirationTime specified by the node) and discard the request otherwise;
• checking that the mana of the requester peer is within the own Mana rank and send back a negative Peering Response otherwise;
• checking that the requestor salt matches its hash chain by:
  • taking the difference between the timestamp of the peering request and the time the initial salt was set, and then dividing this number by saltUpdateInterval, rounding down;
  • hashing the requester public salt as many times as the number of salt changes;
  • finally, if the result does not match the initial salt, discard the peering request;
• applying a statistical test to the request defined as s(remoteID, ownID, ζ_remote) < θ for a fixed threshold θ, and discard it otherwise;
  • this test determines the effectiveness of the brute force attack when an attacker tries to establish a connection with a desired peer;
  • with θ set to 0.01 an attacker has only 1% of chance of being successful;
• accept the peering request by sending back a positive Peering Response if either one of the following conditions is satisfied, and send back a negative Peering Response otherwise:
  • the current size of the accepted neighbors list is smaller than Floor(k/2);
  • the score defined as s(ownID, remoteID, privSalt) is lower than the current highest score among accepted neighbors. In this case, send a Peering Drop to drop the accepted neighbor with the highest score replaced by the requester peer.

3.4.2.6 Neighbor Removal

Neighbor removal can occur for several reasons:

• A node is replacing a neighbor with a better (in terms of score function) one;
• From the gossip layer, the connection with a neighbor is lost;
• If some form of reputation or bad behavior is being monitored, a neighbor could be dropped in case of misbehavior. For example, a node could respond to the peering request but choose not to gossip received messages.

Independently from the reason, when a peer drops a neighbor shall send a Peering Drop and remove the neighbor from its requested/accepted neighbor list. Upon reception of a Peering Drop, the peer shall remove the dropping neighbor from its requested/accepted neighbor list.

3.4.2.7 Requests and responses

Each peering request, response, drop shall be encapsulated into a data field of a generic Request and Response. Its type shall be specified in the type field and signed with the ed25519 private key of the sender's identity and contain the related public key to allow the receiver to verify the signature. All the received peering request, response, drop shall be verified and those with invalid signatures be discarded.

Request and Response Layout

Name	Type	Description
type	uint8	Defines the type of the request or response.
data	ByteArray	Contains the payload of the request or response (e.g., a PeeringRequest).
public_key	ByteArray[32]	The ed25519 public key of the peer's identity used to verify its signatures.
signature	ByteArray[32]	The ed25519 signature of the `data` field, signed by using the private key of the peer's identity.

Peering Request

Name	Type	Description
timestamp	time	The unix timestamp of the PeeringRequest.
salt	ByteArray[20]	The public salt of the requester.

Peering Response

Name	Type	Description
req_hash	ByteArray[32]	The blake2b digest of the corresponding received PeeringRequest.
status	bool	The response (true or false) of the PeeringRequest.

Peering Drop

Name	Type	Description
timestamp	time	The unix timestamp of the drop.