4.3 Tip Selection Algorithm

4.3.1 Introduction

The tip selection algorithm is the method by which messages are selected for approval by other issued messages joining the network. This approval mechanism represents “belief” in the Tangle: If message $y$ approves message $x$, this implies that the node issuing $y$ believes that $x$, and possibly its past cone, are "good".

The tip selection algorithm allows the Tangle to grow in a stable and secure way, with quick approval and finality times.

We call the new Tip-Section algorithm "R-URTS", which means "Restricted Uniform Random Tip Selection". Here we summarize the main differences that the new Tip Selection Algorithm has, compared to the legacy version:

1. Uniform Selection: Unlike the old Random Walk tip selection, we will use a much faster and simpler solution that will select uniformly among a subset of eligible tips.
2. Approval Switch Mechanism: A new mechanism that will allow us to keep a clear Tangle while preventing orphanage from splits due to disliked branches.

Although we will not be using here, the new message layout (more information in Section 2.2 - Message Layout) has the capabilities for a message to have a non-fixed number of messages that it approves (parents), which range from two to eight . This can be used to develop tip spam protection mechanisms among other purposes. We will denote the number of parents being used in the algorithm by Parental Number.

The Tip Selection Algorithm specification depends on the following specifications:

• 2.2 - Message Layout
• 2.4 - Data Flow
• 4.1 - The Tangle
• 5.2 - Ledger State

4.3.2 Definitions

One of the main improvements of the new Tip Selection Algorithm comes from its ability to keep both a clean non-conflicting subtangle, as well as to ignore the existence of conflicts in its selection, hence emulating the ability that Chrysalis White Flag approach has of being unsplittable. In IOTA 2.0, those properties come from the approval switch mechanism. In the rest of this subsection, we present the theory of the approval switch, which classify approvals and messages in "weak" and "strong". This information is necessary to define the tip pools, i.e., the sets of (recent) messages which are selectable by the Tip Selection Algorithm (we provide a more complete description of tip pools later in this document).

4.3.2.1 Approval Switch

In order to properly define and explain the approval switch mechanism, we will need some extra defintions. We also refer to the basic concept of branches (Section 5.2 - Ledger State) and validity (Section 4.1 - The Tangle), as they are required to the understanding of some of the definitions below.

• Tip: A message is considered a tip (by a node) if it is selectable by the Tip Selection Algorithm, i.e. it is an element of any Tip Pool (of that node). In general, it is perceived as a message that has yet to receive any direct approvers.

• Eligibility: A Message is said eligible if:

  • It is weakly valid;
  • It passes the timestamp check with level of knowledge at least 2;
  • All its parents are also eligible messages.

• Approval switch: : A binary field with values strong and weak in the message associated with each of its parents, filled by its issuer node.

  • Strong approval: Represents that the issuer node declares that the message and its entire past cone are liked.
  • Weak approval: Represents that the issuer node declares that the message and its payload is liked, but its past cone is not completely liked.

4.3.2.2 Branch

Furthermore, to properly define the tip pool, additional definitions derived by the branch are required. Here we give a summarized definition for the sake of understanding.

• Monotonically Liked Branch: A branch is monotonically liked if all of its transactions are individually liked.

• Monotonically Liked Message: A message is monotonically liked if its aggregated branch is monotonically liked.

4.3.2.3 Strong and Weak Messages

In a heuristic way, one can think of a monotonically liked message as a message that has a liked payload and that all other payloads that depend on it are also liked. With this we can classify the messages:

• Strong Messages: We say a message $x$ is strong (for a node) if it is:

  • Eligible;
  • Monotonically liked.

• Weak Messages: We say a message $x$ is weak (for a node) it is:

  • Eligible;
  • Contains a liked payload;
  • It is not monotonically liked with level of knowledge at least 2.

Image 4.3.1: An example of strong and weak parents. Observe that although B is in the past cone of I, it is not in its strong past cone.

4.3.3 Tip Pools

The tip is a product of the construction of the Tip Pools, and in general it represents messages that are yet to be directly approved by other messages. The tip pools are built by filtering the messages that arrive from the neighbors, checking which ones are proper to be selectable by the algorithm. In this subsection we will define such filters and classifications that are used to make the Tip Pools.

Differently from the legacy implementation, we will not have a single pool, but instead two, divided according to the new concept of the Approval Switch mechanism.

4.3.3.1 Construction of the Tip Pools

We will define a sequence of pools, each one selected by filtering the previous one regarding one condition, until we conclude with the two elements used in the Tip Selection Algorithm: the Strong Tips Pool and the Weak Tip Pool.

1. Eligible Messages Pool: This pool consists of all messages that were also approved by the Eligibility Check (see Section 2.4 - Data Flow).

2. Liked Payload Pool: This pool consists of all eligible messages that contain a payload tagged as "liked", i.e. is either data or an individually liked transaction.

3. Strong Tips Pool: This pool consists of all strong messages in the Liked Payload Pool.

4. Weak Tips Pool: This pool consists of all messages from the Liked Payload Pool that were not included in the Strong Tips Pool.

The two main pools to be used by the tip selection algorithm are the Strong Tips Pool and the Weak Tips Pool. Observe that from our definition, each pool in the list is always constructed by performing a filtering in the previous one, but how this filtering will be performed is considered an implementation detail and hence will not be further considered here.

4.3.3.2 Update of the Tip Pools

There are two types of updates that can be done with the strong and weak tip pools:

1. Removal: Tips are removed when they are approved by other messages. This can happen in two ways:
   • When the node issues a message, the selected tips will be removed from the respective tip pools after the Tip Selection Algorithm is performed (we briefly explain the procedure in the R-URTS subsection.
   • When a new message is received, its parents shall be removed from the respective tip pools by the Tip Manager application (further information may be found in the Section 2.4 - Data Flow).
2. Rearrangement: Tips can be changed from the strong tip pool to the weak tip pool, or from the weak tip pool to the strong tip pool if the perception of the branches they belong to changes, this is explained in more details in Section 6.5 - Node Peception Reorganization.

4.3.4 R-URTS

We want to reiterate here that, ultimately, the tip selection is a free procedure not enforced by the protocol. Therefore each node may, if it sees worth, to select its approvees in a manual way or following another algorithm of its preference. What we will present here is the standard algorithm, that works both as a suggestion but also as something that the nodes will have implemented and will use by default.

The suggested standard tip selection algorithm is R-URTS (Restricted Uniform Random Tip Selection), which selects messages with uniform probability among the list of tips restricted by some condition.

Let us give an example for a Tip Selection Algorithm with Parental Number $k$:

1. Consider the Strong Tips Pool and the Weak Tip Pools updated.
2. The node shall select the first tip from the Strong Tips Pool.
3. The node shall select tips from numbered $2$ to $k$ from the union of the Strong Tips Pool and the Weak Tips Pool.
4. The node shall register in the message's Parents type field if each selected parent was from the strong or weak tip pools.
5. The node shall remove the selected tips from their respective pools.