Coordicide Update — Autopeering: Part 2

In the last blog post, we shared with you the IOTA Research Team’s simulator of the current autopeering model, along with some early results. In this second part of the series, we aim to give you a clear overview of the autopeering algorithm and its functioning.

First of all, why is it important to peer automatically and with a certain degree of randomness? Roughly speaking, if a new node connects to others that were gossiped to it by a neighbor, the information received by the former node will be very similar to the information available for the latter. This creates a form of an echo chamber. Moreover, with this kind of network growth, an attacker can eclipse a chosen region by just gossiping a large amount of his own nodes to the newcomers.

So our goal is to implement an algorithm that provides:

1) good topological properties (i.e., properties related to the arrangement of the nodes), to allow a good convergence for the voting mechanism built on top of it

2) a negligible probability of an attack by a malicious actor to be successful

In order to do that, we introduced an algorithm that combines three different variables; one which is verifiable, one which is unpredictable, and a final one which is related to something scarce.

Here, we will explain how the autopeering process occurs after the node discovery is already finished, as it is modeled in the already shared simulator. Each of the nodes will have set:

1) A public node id (a 32 bytes string).

2) A public salt (a 20 bytes string).

3) A private salt (a 20 bytes string).

We define the requesting distance between nodes A and B as follows:

d_req(A,B) = hash(node_id(A)) XOR hash(node_id(B)+pub_salt(A))

To request a new connection, node A will calculate d_req(A,B) for all nodes it knows and will order the nodes by this distance. After that, the node will start requesting from the closest to the farthest, until k connections are accepted by the other nodes, and consequently established.

We also define the accepting distance between nodes A and B as follows:

d_acc(A,B) = hash(node_id(A)) XOR hash(node_id(B)+priv_salt(A))

A node A will accept a request from a node B whenever

1) it accepted less than k requests

2) d_acc(A,B) is smaller than the acceptance distances to one of his accepted peers. In this case, node A will drop the connection to its farthest accepted node.

Periodically, the nodes will change their salts and update all the distances. Note that each node will aim to have 2k connections, k established by requesting other nodes, and k established by accepting other nodes’ requests.

First, let us focus on the public/private salt scheme. The requesting distances depend only on public information. This way, the nodes can verify if a certain request is probably legitimate or not, by evaluating if the distance has an appropriate order of magnitude. This already makes the job a little bit harder to the attacker, since now he will have to “mine” a public salt that locates him close enough to the node he wants to eclipse. Furthermore, if the salts are generated with the use of hash chains, the nodes commit themselves to a long sequence of salts, making it virtually impossible for a successful attack to be sustained for a large amount of time.

Now, as the acceptance will depend on a variable only known by the target (the private salt), whether an attacker will or will not establish a connection with a target is completely unpredictable to the attacker. This will further narrow down the malicious part’s possible strategies, making trial and error with several different nodes the only possible strategy in practice. This leads us to the final component of the system: mana*. If we weigh the distances defined above with mana differences, the algorithm will establish connections between nodes with similar amounts of mana. This way, since mana is designed to be a scarce resource, no attacker will possess enough of it to try this kind of trial-and-error attack on participating (non-zero mana) nodes. This makes our autopeering the most promising randomized, automated, not easily gameable, peering algorithm among the major DLTs.

We hope you enjoyed this small series about the autopeering model! As always, all questions and comments are welcome, either here or on our Discord server.

* not implemented yet in the simulator