Addressing the Transaction Validation Issue in IOTA Tangle: A Tip Selection Algorithm Based on Time Division

Abstract

IOTA is a new public chain system specifically designed for the Internet of Things (IoT), which provides strong support for the high concurrency, scalability, and zero handling fees of the IoT. The distributed ledger of IOTA, called the tangle, adopts a Directed Acyclic Graph (DAG) structure. However, compared to the single-chain architecture, the tangle is more complex and highly vulnerable to security threats. The existing transaction verification methods still cannot simultaneously meet the need for accelerating approval speed and improving security to resist illegal transactions, such as lazy tips and permanent tips. In this work, we propose TDTS, a tip-selection algorithm based on time division to improve the efficiency of transaction verification. The main idea of the algorithm is to quickly determine two tips of an incoming transaction that need to be confirmed by sorting tip values in a time slot. It shortens the transaction verification time and reduces the number of lazy tips and permanent tips. A comprehensive theoretical analysis confirmed the effectiveness of our proposed algorithm. Based on 1000 IOTA nodes, the evaluations showed that TDTS can select tips quickly like URTS and resist lazy tips like MCMC.

1. Introduction

The Internet of Things (IoT) has higher requirements in decentralization, traceability, concurrency, scalability, and micropayment. The emergence of blockchain technology has provided the possibilities for the further development of the IoT [1,2,3,4]. However, the traditional blockchain architecture can no longer meet the above needs. The blockchain based on the Directed Acyclic Graph (DAG) structure has become the preferred solution for deep integration with the IoT. The most representative is IOTA [5,6,7].

IOTA is a new type of public chain system specifically designed for the IoT, which has more-prominent advantages in supporting concurrency, scalability, and zero handling fees compared to the single-chain architecture. IOTA’s distributed ledger adopts a DAG structure called the tangle.

In IOTA, each node issues a new transaction, which must provide the legitimacy proof of the transaction to avoid malicious interference and make the tangle a continuous and consistent network. Specifically, an incoming new transaction must approve two existing terminal transactions before it can be attached to the tangle. Theoretically, a node (or user) can choose any two transactions for approval. However, to ensure the security of IOTA and maintain stable growth of the tangle, the usual approach is to choose two unapproved transactions, called tips, to approve [5]. The selecting-tips process is called tip selection, and the corresponding algorithm is called Tip-Selection Algorithm (TSA). The TSA is a significant guarantee for IOTA’s sustainable development [8].

The tangle formed through tip selection brings many advantages to IOTA, while creating opportunities for malicious nodes to launch massive attacks. This is because that not all nodes will strictly follow the tip-selection algorithm provided by IOTA during the process of issuingtransactions. Some nodes bypass tips to avoid the tedious verification process. For instance, incoming new transactions select historical transactions for approval and generate lazy tips. This will seriously hinder the stable growth of the tangle. In addition, current classic tip-selection algorithms cannot ensure that all tips are approved in time. The remaining tips eventually evolve into permanent ones until they are discarded. This causes the sending nodes to reinvest their computing power to send these transactions after waiting for a period of time. Many resources are wasted. A reasonable TSA must help to improve IOTA’s security and promote the stable growth of the tangle.

In the early stages of IOTA, the system selected tips through the Uniform Random Tip-Selection (URTS) algorithm and the Unbiased Random Walk (URW) algorithm [9]. These two algorithms have a fast execution speed and low computational complexity, but their security is not high. Therefore, Serguei Popov et al. proposed a Biased Random Walk (BRW) algorithm based on cumulative weights, with the most-famous being Markov Chain Monte Carlo (MCMC) algorithm [10]. Although this algorithm can resist double-spending attacks to a certain extent and increase the security of the IOTA system, it overly relies on a specific parameter $\alpha$, which is a parameter to adjust the transfer probability of particle wandering. In [11], Ferraro et al. tried to solve the problem of $\alpha$ by providing a Hybrid Selection Algorithm (HSA). This algorithm selects tips by taking different $\alpha$ values in two stages: the first stage is to adopt the larger $\alpha$ to ensure network security. Select a small one in the second stage to resist permanent tips. However, it is still not clearly stated specifically how to take the values of $\alpha$. The G-IOTA method proposed in [12] has led to more transaction validation work, invisibly increasing resource consumption. E-IOTA [13], the improved algorithm for G-IOTA, weakens the ability to resist splitting attacks. In [14], there are differences between Halgamuge’s description of tangle and the description provided by the IOTA Foundation, such as the calculation method of cumulative weights. The important thing is that the tip-selection algorithm is not suitedfor the latter, especially the Best-Approver-Selection Method (BASM). This can cause fierce competition between IOTA nodes. Adopting the method of selecting IOTA nodes nearby or by default by the client will accelerate the speed of transaction verification and ledger broadcasting.

With the development of IOTA, its versions have changed from $1.0$ to $1.5$ and then to $2.0$. IOTA $2.0$ is currently the research goal, and soon, IOTA will achieve true decentralization. Due to the limitations of URTS and the BRW, Popov et al. improved the URTS algorithm in IOTA $2.0$ (Coordicide) [15]. However, the authors only mentioned the design concept of the improved algorithm in the Coordicide white paper, which involves the transaction target timestamp, the solidification time of the node issuing the transaction (i.e., the time when the node receives the transaction and all its historical records), and some fixed positive constant, without clearly indicating how to obtain or calculate them. To ensure the security and stability of the tangle, IOTA urgently needs an effective tip-selection solution that can quickly confirm transactions while effectively suppressing the formation of lazy and permanent tips.

We propose Tip Selection Based on Time Division (TDTS), a tip-selection algorithm based on time division, to reduce the number of lazy and permanent tips. This algorithm abandons particle wandering (Let particles perform independent discrete-time random walks “towards the tips” like in MCMC), reducing transaction approval time and accelerating transaction approval speed to a certain extent. In the IOTA system, we introduced the IOTA committee, which can strengthen the supervision and management of the IOTA system, reduce the computational load of the overall IOTA nodes, and reduce unnecessary resource consumption. The main contributions of this paper can be summarized as follows:

• We propose an effective tip-selection algorithm, TDTS, based on time division. It reduces the problem scale of tip selection. It limits the time for generating lazy and permanent tips to a single time slot. In addition, TDTS makes the transactions selection by nodes have a tendency, and if malicious nodes want to tamper with the tangle, they need to confront the honest nodes of the entire network.
• We introduced the IOTA committee, which has improved the efficiency of the system work. The election method proposed in this work ensures the fairness and impartiality of the election of committee members. The committee reduced the workload of IOTA nodes and saved system computing power to a certain degree.
• We provide and define the tip coefficient and tip value. The tip value is directly proportional to the tip coefficient and the time the tip stays in the tangle. The tip value measures the importance of a tip in the current time slot and is also a key indicator for tip selection.
• We present a comprehensive theoretical analysis and simulation experiments. The experimental simulation results confirmed the effectiveness of our proposed algorithm.

The rest of this paper is organized as follows. Section 2 present the related work. Section 3 describes the background. Section 4 introduces the TDTS design. The evaluation results are shown in Section 5. Finally, Section 6 concludes the whole paper.

2. Related Work

To develop a DAG-based blockchain and promote secure payment and communication between IoT devices, the IOTA Foundation launched the IOTA project in 2015 [16,17]. So far, the two most-classic tip-selection algorithms in IOTA are URTS and MCMC.

The URTS [18] algorithm has a simple idea and is easy to implement. It demonstrates sufficient fairness by randomly selecting tips. URTS has many ideal properties without considering malicious behaviors, such as a shorter confirmation transaction time, faster execution speed, and lower computational complexity. However, the algorithm cannot resist double-spending attacks. All honest nodes do not unite to tend to choose some tip, while malicious nodes can increase the probability of selecting one of the tips. Thus, by paying a lower cost, parasitic chain attacks or splitting attacks can be achieved [9].

The URW algorithm is slightly more complex than URTS, which is the foundation of the MCMC algorithm. The main idea of the URW is to place wandering particles in the position of Genesis transaction, which will reverse walking along a random path to reach tips. Assume x and y represent transactions. A wandering particle is placed on x, and y approves x. The probability of the wandering particle moving from x to y is $\frac{1}{N}$, where N represents the number of transactions directly approving x. The security of the URW is the same as that of URTS.

Compared with the URW algorithm, the MCMC algorithm introduces cumulative weight. Unlike the URW algorithm, the probability of wandering particles moving from x to y is expressed as $1-f(\alpha (H_x-H_y)$. Among them, f is a monotonic non-decreasing function. $H_x$ and $H_y$ represent the cumulative weights of transaction x and y, respectively. $\alpha$ is a controllable parameter. When $\alpha$ is high enough, even if the cumulative weight difference between two transactions is little, the larger the cumulative weight, the higher the probability of the transaction being randomly walked for selection. When $\alpha$ is low enough, even if there is a significant difference in the cumulative weights of two transactions, the probability of the transaction being randomly walked for selection is almost the same. According to the above, wandering particles to select the transactions with larger cumulative weights as the next hop have a high probability. MCMC makes the tip selection of honest nodes have a clear tendency. If malicious nodes want to manipulate the tangle, they will confront the honest nodes of the entire IOTA system and pay a high price. However, this algorithm cannot treat each tip equally. This is because the probability of selecting tips or branches with low cumulative weights by wandering particles becomes very small. The main idea of MCMC is as follows [10]:

• Consider all transactions on the interval $[W,2W]$, where the cumulative weight W of the transactions is sufficiently large (to prevent particles from moving quickly to tips).
• Place N particles independently within this interval (usually, more than two particles are placed).
• These particles independently walk randomly within the discrete time of the tip. This means the transition from x to y is possible only if y approves x.
• Choose the first two tips that arrive in the random walk. Note: To avoid choosing lazy tips, IOTA may discard random walking particles that reach the end too quickly.

The probability of a particle transferring to the next position is as follows: if y directly approves $x(y⇝x)$, the transfer probability $P_{xy}$ is proportional to $exp(-\alpha \left((H_x-H_y)\right))$. The calculation equation is:

$$P_{xy}=exp(-\alpha (H_x-H_y)){(\sum _{z:z⇝x}exp(-\alpha (H_x-H_z)))}^{-1}.$$

(1)

MCMC can increase the tangle security during the tip selection and prevent malicious nodes from launching double-spending attacks. However, this algorithm has the following shortcomings:

• The selection of the starting position range of particle wandering is ambiguous. If the particles start wandering from the position of the Genesis transaction, the wandering time of particles is too long as the tangle grows. This can reduce the efficiency of MCMC. If the particle wandering is too close to the tips, it cannot reflect randomness. Thus, further research is needed to determine the W value.
• The tip selection is mainly dependent on specific parameters $\alpha$. If $\alpha$ is 0, the algorithm evolves into the URW. If $\alpha$ is higher than 0, the algorithm only tends to select transactions with large cumulative weights for approval. Transactions having a small cumulative weight have a repeatedly delayed attachment to the tangle, ultimately becoming permanent tips. How to choose a reasonable $\alpha$ value, which can punish lazy behavior without leaving too many permanent tips, is currently an urgent problem to be solved.

In addition, the literature [11,12,13,19,20,21] has studied the characteristics and selection methods of tips. To solve the problems such as permanent tips in the BRW, Ferraro et al. [11] proposed the HSA to provide high-level security against attacks and ensure all tips are finally approved. In [12], Bu et al. proposed a new fair trust hybrid tip algorithm called G-IOTA. Firstly, use the BRW to select two of tips, and then, select the third legacy tip in a completely random manner. This method maintains the security of the BRW against splitting attacks, ensuring that honest transactions can be verified each time by selecting a legacy tip. E-IOTA, an improved G-IOTA scheme, was provided in [13]. Its basic idea is to set three reasonable algorithms and choose one of the algorithms each time to obtain the tip. The basic properties of the tangle were mainly studied in [19], including the cumulative weights of different tip selection mechanisms and the stability of tip numbers. In [20], the authors formally analyzed and estimated the probability of becoming a permanent tip by collecting different parameters. In [21], Attias et al. redefined the compute mode of cumulative weight. On this basis, they proposed an improved MCMC algorithm and tried to solve the problem of the low efficiency of the existing algorithms.

However, all tip-selection algorithms cannot eliminate or reduce lazy and permanent tips concurrently, and it takes a long time to confirm transactions. A large number of lazy tips and permanent tips are not conducive to the tangle’s stable growth. This can cause the tangle to stagnate. Therefore, by studying the problems of lazy tips and permanent tips in message security verification, we propose a time-division-based tip-selection algorithm. This algorithm divides the time for generating the tangle and focuses the global transaction validation problem on a single time slot, reducing the problem size while improving transaction validation efficiency. By sorting the tip values of tips in a single time slot in descending order, we select two tips to ensure that honest nodes have a certain tendency towards tip selection and increase the difficulty of malicious node attacks. This algorithm retains both the advantages of URTS in the execution speed and the advantages of MCMC in resisting double-spending attacks.

In the early period of IOTA, the overall network computing power was low. To ensure the usual operation of IOTA, a “Coordinator” was proposed to help the system reach consensus. Among them, the “Coordinator” node is a special node whose transactions are unconditionally accepted by the entire network. Currently, IOTA has initiated research on decentralized coordination with the aim of removing Coordinators to achieve true decentralization. Our research was based on the Coordicide rather than the “Coordinator” in this work.

3. Background

Each node in the IOTA system can conduct transactions and actively participate in consensus. IOTA adopts a consensual and incentive mechanism different from traditional blockchain, so IOTA nodes no longer receive mining rewards and transaction fees. IOTA nodes must manage and maintain the IOTA system together. Specifically, each new transaction issued by a node must contribute to the IOTA network by verifying terminal transactions to promote the stable growth of the tangle. Although not charging transaction fees can add IOTA node expenses, it promotes micro-payment applications’ development in the IoT.

As a distributed ledger of IOTA, the tangle has multiple attributes [10]. Weight is one of the most important in the tangle, which can measure the importance degree of transactions. In IOTA, weight is divided into cumulative weight and own weight. The larger the cumulative weight of a transaction in the tangle, the more significant it is. A transaction’s own weight is directly proportional to the workload of issuing the transaction node. The tangle structure is shown in Figure 1. The left-most transaction is the Genesis transaction, and the right-most unapproved transactions are called tips, such as A, B, and C. The numbers on each transaction represent the weight; the upper left corner represents the cumulative weight, and the lower right corner represents own weight. Since IOTA adopts a ternary structure, a transaction’s weight is expressed by the power of 3. Assuming that the own weight of each transaction is 1, it can be deduced that the cumulative weight of a transaction is equal to the total number of nodes directly or indirectly approving the transaction plus 1.

The transaction attachment in IOTA is mainly achieved by tip selection and rate control. A reasonable tip-selection algorithm helps to improve IOTA’s security and promote the stable growth of the tangle. All the tips in the tangle form a tip pool. A new transaction that arrives is marked as y, and an existing transaction in the tangle is marked as x. If y and x are directly connected through a directed edge, it is considered that y approves x directly. If there is no directed edge between transaction y and x, but there is a reachable path between y and x, it is considered that y indirectly approves x.

In the IOTA tangle, the more transaction validations a transaction receives, the more difficult it is to tamper with.

Figure 2 shows the process of attaching a transaction to the tangle. The blue pattern block represents an approved transaction (at least once approved); the green pattern block represents an unapproved transaction (tip); the white pattern block represents an upcoming transaction. The black solid line indicates the approval process has been completed (The approval process of a transaction is its attachment process, mainly including tip selection and PoW calculation), and the black dashed line indicates the ongoing approval process. The lightweight PoW mechanism used in the approval process is mainly to prevent malicious nodes from sending spam information to the IOTA network and control transaction rates. The lightweight PoW mechanism has less computational complexity than traditional PoW mechanisms in the blockchain. It can run on some computationally powerful clients in addition to IOTA nodes.

Figure 3 shows an instance of the cumulative weight of a transaction changing over time, with numbers only representing the cumulative weight of the transaction. The blue pattern block, green pattern block, and white block have the same meaning as Figure 2. To simplify the calculation, assume that the own weights of the transactions are all 1. When five new incoming transactions are successfully attached to the tangle, the cumulative weight of each directly or indirectly approved transaction will increase accordingly, as shown on the right side of Figure 3.

Some new incoming transactions will choose historical transactions to approve to avoid the tedious verification, so lazy tips are formed in the tangle. This is because the nodes issuing these tips are unwilling to pay the computational costs to increase the length of the tangle. They even do not accept the new tangle’s topology. Instead, they constantly add their own transactions to the previous old tangle topology and, then, broadcast transactions based on the topology, enjoying the benefits. If all IOTA nodes adopt such a behavior, new tips will no longer be approved, and the entire network will stagnate. Figure 4 shows the formation process of lazy tips. The more the number of lazy tips is, the more the stability of the tangle will be affected. Furthermore, existing tip-selection algorithms have not taken punitive measures against lazy tips.

4. The Design of the TDTS Algorithm

This section mainly proposes and designs the TDTS algorithm, including three subsections. In the first subsection, we introduce the IOTA committee mechanism to improve the efficiency of the IOTA system. In the second subsection, we propose an IOTA system architecture that includes the TDTS algorithm. In the last subsection, we design the TDTS algorithm.

4.1. IOTA Committee Mechanism

IOTA nodes need to perform multiple system tasks. To a certain extent, the proposal of the IOTA committee has reduced the overall workload of the system, accelerated the overall operation speed of the IOTA system, and improved the work efficiency. As shown in Figure 5, select a group of nodes from all active IOTA nodes to form the IOTA committee. It is responsible for executing the management, arbitration, and maintenance of the IOTA system [22].

Each IOTA node can apply to become a member of the IOTA committee (referred to as a member), and the IOTA system updates the member list every 24 h. To become a committee member, an IOTA node must follow the conditions: the member must meet the basic requirements for running IOTA operations, such as the hardware configuration. Allow the mana involved in their account to be detected. Enter the candidate list after meeting the above conditions. When the reputation age of a node (i.e., the product of the mana and the time it is held) reaches the lower limit specified by the IOTA system, the node will be marked as qualified and moved from the candidate list to the IOTA committee member list.

In IOTA, mana represents a reputation value equal to the total amount of funds transferred in the transaction, related to IOTA tokens, but in a separate state from IOTA tokens. The principle of mana is that nodes that contribute more to the IOTA system should receive more mana, but a node should not simply hold a large number of tokens or send tokens frequently to obtain a large amount of mana [15]. Here, three related concepts introduced:

• Pending mana: The address generates a pending mana at a rate proportional to the currency held.
• Mana: When IOTA tokens are disbursed from an address, the pending mana generated from the above address will be converted into mana and pledged to a node. The pending mana is now generated through tokens on the recipient’s address.
• Decay: Both the mana and pending mana will decay at a rate proportional to their value, preventing the mana from growing unrestricted over time.

Let us formalize the above concepts. Let S represent the number of tokens held by address x within a given time; $\beta$ indicates the generation rate of the pending mana; $\gamma$ represents the decay rate the coefficients of the mana and pending mana; $M_x\left(t\right)$ represents the pending mana held by address x at time t; $M_Z\left(t\right)$ represents the mana of node Z at time t. Therefore, if an address has S tokens at Time 0, then there are:

$$m_x\left(t\right)=m_x\left(0\right)e^{-\gamma t}+\frac{\beta S}{\gamma }(1-e^{-\gamma t}).$$

(2)

Note that the number of tokens on the address is a piecewise constant function. Generally, Equation (2) can be used to calculate the pending mana by considering the time interval during which the address balance remains unchanged. It is especially emphasized that, in the case where the address does not have a token before the initial time (it receives S tokens at Time 0), Equation (2) can be simplified as follows:

$$m_x\left(t\right)=\frac{\beta S}{\gamma }(1-e^{-\gamma t}).$$

(3)

Even if the pending mana decays over time, it is still observed that $m_x\left(t\right)$ in Equation (3) is strictly increasing. This is because the attenuation is proportional to its value, while the generation rate is constant (equal to the number of tokens). This means the decay rate is always lower than the generation rate, so the pending mana always increases, but it will slow down over time until it tends to flatten out. After being mortgaged to a node, the mana value will decay over time. Therefore, the node’s mana satisfies:

$$m_Z\left(t\right)=m_Z\left(0\right)e^{-\gamma t}.$$

(4)

If $\alpha$ and $\gamma$ are known, we can calculate the pending mana and the mana of all IOTA nodes according to Equations (2)–(4).

Nodes applying to join the IOTA committee must pledge a certain amount of mana. Once some nodes violate the membership rules, the mana will be deducted as a corresponding punishment to ensure the fairness of member elections. This is because a malicious node needs to undertake the consequences of one’s own actions. That is, once a violation of a node is discovered, according to the IOTA system regulations, the pledged mana of the node needs to be confiscated, making it unprofitable.

Similar to the age of coins in Proof of Stake (PoS), this paper proposes the concept of reputation age, which refers to the time when IOTA nodes hold mana. Nodes with an older age are more likely to be selected as members, and the expression for the reputation age is as follows:

$$repu\_age=mana\ast age.$$

(5)

Once a node is selected as a member, its corresponding reputation age needs to be cleared. The next round requires the node to participate in the calculation again.

It should be noted that the IOTA committee must consist of active IOTA nodes and ensure that more than two-thirds of its members are honest [22]. To further improve the enthusiasm of IOTA nodes to participate in the committee and increase the reliability of IOTA nodes, the system can appropriately introduce incentive mechanisms similar to Bitcoin and Ethereum. Essentially, the incentive mechanism is a mechanism that ensures the safe and reliable operation of the IOTA network. However, the existing incentive methods do not guarantee the complete decentralization and independent operation of IOTA. The reason is that the transaction volume generated by honest nodes in the network does not satisfy the basic requirements for achieving decentralization in the IOTA system, and the tamper resistance of the IOTA tangle still relies on the Coordinator.

4.1.1. Proposal of the TDTS Algorithm

The IOTA system is mainly composed of four entities, namely IoT devices, clients, IOTA nodes, and the IOTA committee, as shown in Figure 6 (Generally, due to the limited computing power of the client, the tip selection and calculating PoW difficulty are mainly performed by the client with the help of IOTA nodes). In the IOTA system architecture, the four types of entities have a clear division of labor and cooperate with each other to jointly generate the tangle and broadcast it to the entire network through P2P protocols to complete the consensus process [23]. Among them, the IOTA committee must not only be responsible for the daily management and maintenance of the IOTA system, but also ensure that the system clock is not tampered with to prevent some nodes from cheating due to unauthorized changes in the time of issuing transactions.

To avoid generating lazy tips or permanent tips and speed up transaction approval, we propose a new tip-selection algorithm called TDTS. TDTS runs on each IOTA node, as shown in Figure 6, and TDTS is highlighted in red. The main ideas are as follows:

Starting from generating the tangle, we divide the time into equal lengths in sequence and only complete the tip-selection work within the current time slot. A time slot’s length can be determined based on the actual situation of the IOTA system at the beginning stage. Next, calculate the tip value for all the tips in the current time slot. After that, select the two maximum tip values in descending order as the result of one tip selection. Finally, the IOTA node returns the result to the client. The TDTS algorithm process is shown in Figure 7.

4.1.2. The TDTS Algorithm

Firstly, determine the length of time slot in TDTS, which is obtained by the IOTA committee based on the scale of the IOTA system. Here is a method for calculating the time slot’s length.

We determine the time slot’s length through the estimated time when a transaction is first approved in our work. Under low network load (Low network load: The number of tips is small, often set to 1. If there is low network latency and the node calculation speed is fast, it is rare to have multiple tips), the number of tips is small, so the time a tip is first approved is approximately ${\lambda }^{-1}$, where $\lambda$ represents the arrival rate of transactions per unit time. In the case of high load (High network load: When the transaction flow is large, the calculation delay and network delay may make several different transactions to approve the same tip), the time when a tip gets approved is related to the specific tip-selection algorithm [10].

Let $L\left(t\right)$ represent the total number of tips in the IOTA system at time t. In an ideal situation, $L\left(t\right)$ fluctuates around a constant value of $L_0$, rather than tending towards infinity (or else, the system would have many unapproved transactions). Suppose that any node issues a transaction, and we observe its state before t rather than the current state of the tangle. This means that the transaction attached to the tangle at time t is not visible to the network until $t+h$, where h represents the average time a node needs to calculate when issuing a transaction. The incoming transactions follow a Poisson distribution, with a rate recorded as $\lambda$. To simplify the calculation, assume that $\lambda$ remains constant over time and that each node has approximately the same computational power.

For some IOTA node, there are $\lambda h$ hidden tips and r visible tips at time t (r represents the number of tips that were attached to the tangle before time $t-h$, but were still not approved at time t). Therefore, it can know $L_0=r+\lambda h$. At time t, when a new transaction arrives, the probability of a tip being selected is $\frac{r}{r+\lambda h}$. Therefore, the average number of tips selected is $\frac{2r}{r+\lambda h}$. In a stable state, the average number of selected tips should equal 1, so satisfy $\frac{2r}{r+\lambda h}=1$, obtain $r=\lambda h$, and deduce $L_0=2\lambda h$. It is known that the expected time for the first approval of a transaction is $\frac{L_0}{2\lambda }$. Consider the high load state of the network, i.e., the $L_0$ value is high. As mentioned above, assuming that the Poisson confirmation flow of each tip is independent, its rate is approximately $\frac{2\lambda }{L_0}$. The expected time for receiving the first approval of the transaction is approximately $\frac{L_0}{2\lambda }=h$. When the waiting time for the approval of a legitimate transaction is much longer than $\frac{L_0}{2\lambda }$, we mustapprove the transaction; else, it will become a permanent tip.

TDTS can estimate the time slot length through $\frac{L_0}{2\lambda }=h$. By dividing the time of generating the tangle sequentially, we can limit the problem scale to a single time slot. Furthermore, the algorithm no longer uses the particle random walk method like MCMC. At the same time, to overcome the low cost of the malicious node behavior caused by a completely random selection of tips, a tip value related to the cumulative weight is introduced, which can reduce the number of lazy tips and increase the difficulty of malicious attacks. Based on the above analysis, the specific steps of TDTS are as follows:

• Starting from the generation of the Genesis transaction, the time is gradually divided into slots (such as equal-length slots). The tangle will experience gradual growth in each time slot, represented by $T_i$ for each time slot. Due to the time required for network transmission and packaging transactions, we selected ten-times the estimated time for initial approval as the length of a time slot. That is, $t_d$, the length of $T_i$, is $10h$ ($\approx 1h\ast 10$). The tangle that grows over time is shown in Figure 8.
• The new transaction that arrives will only complete the tip selection in the current time slot. If refinement of the time slot is needed, we can further divide a time slot into smaller units. For example, the time minimum is h in our work.
• Before selecting a tip, TDTS must obtain tips and their quantity in the current time slot. When a transaction meets the conditions $W_c\left(k\right)=W_s\left(k\right)$, it is recognized as a tip. Among them, $W_c\left(k\right)$ represents the cumulative weight of the transaction and $W_s\left(k\right)$ represents the own weight of the transaction, $k\in 1,2,\dots ,m$. Let m represent the number of tips within the current time slot. The time each tip attaches to the tangle is recorded as $Time\left(k\right)$, $k\in 1,2,\dots ,m$.
• Define the tip coefficient. In IOTA, each tip in the current time slot has a tip coefficient, which is used to represent their importance, denoted as $Tipc$, and satisfies:

  $$Tipc\left(k\right)=W_s\left(k\right),k\in 1,2,\dots ,m.$$

  (6)
  This attribute indicates that transactions with a large weight have priority. This makes the tip selection have a certain tendency and adds to the difficulty of malicious attacks.
• Define the tip value. The tip value and tip coefficient are proportional to the product of the time that the tip stays in the tangle. The expression is:

  $$Tipv\left(k\right)=exp\left(Tipc\right(k)\ast (current\_time-Time\left(k\right)\left)\right),k\in 1,2,\dots ,m,$$

  (7)

  where $Current\_time-Time\left(k\right)$ represents the time that transaction k stays in the tangle. The exponential operation in Equation (7) can be chosen based on specific situations. Its function is to amplify values that are too small.
• Calculate all the tip values in the current time slot, that is $Tipv\left(1\right)$, $Tipv\left(2\right)$,…, $Tipv\left(m\right)$. Sort them in descending order. Take the first two items as the results of executing the tip-selection algorithm once.
• If multiple equal tip values are encountered, two tips are randomly selected from them (such as using URTS) as the final result. If the first item in descending order has only one tip value and the second item has multiple equal tip values, select another one using the same random selection method as above, and put it together with the first tip as the final tip selection result.
• If there are still unapproved tips left before entering the next time slot, these values need to be saved and postponed to the next new time slot for priority processing, reducing permanent tips.
• Due to network latency, it may generate lazy tips. Before entering the next time slot, check lazy tips in the tangle first and mark them. Then, incoming new transactions identify these lazy tips to avoid approving.

TDTS reduces not only permanent tips and lazy tips, but also shortens the approval time of transactions. TDTS is detailed in Algorithm 1.

Algorithm 1 The TDTS algorithm.

Input: m, number of tips within time slot t; h, the average time that nodes need to calculate when issuing transactions; $Tipc\left(k\right)$, the k-th tip coefficient; $Tipv\left(k\right)$, the k-th tip value. Output: Tip selection results.   Initialize system parameters;   There are a total of m tips in the current time slot t (with a time slot length of $10h$), and the following operations are performed on each tip:         Calculate the tip coefficient $Tipc\left(k\right)$ according to Equation (6);         Calculate the tip value $Tipv\left(k\right)$ according to Equation (7);   Sort all tip values in descending order;   If there are multiple equal tip values for the first item in the tangle,         Randomly select two tips as the final result;   Else, if the first item in the tangle has one tip value, and the second item has multiple equal tip values, Keep the first tip and randomly select one tip from the second item;         Else take the first two items in descending order as the final result;   Check if there are any unapproved tips. If any, save them and prioritize processing in the next time slot;   Check if there are any lazy tips. If any, mark hem. Based on the identification mark, new incoming transactions will no longer approve these lazy tips;   Return two selected tips.

We analyzed the time complexity of URTS, MCMC, and TDTS under the same conditions. Assume n transactions and m tips in the tangle, and $n\gg m$. According to the analysis of [10,15], the time complexity of URTS is $O\left(m^2\right)$, and the time complexity of MCMC is $\mathrm{\Omega }\left(n^3\right)$. In this paper, the time complexity of TDTS is $O(m\ast logm)$. It is better than the former two, as shown in

Table 1. Time complexity of the algorithms.

Algorithm	Time Complexity
URTS	$O\left(m^2\right)$
MCMC	$\mathrm{\Omega }\left(n^3\right)$
TDTS	$O(m\ast logm)$

.

5. Evaluation

By comparing and analyzing TDTS with two classic algorithms (namely URTS and MCMC) through experiments, we demonstrate the effectiveness of TDTS. We validated TDTS using simulation methods consistent with current mainstream methods [9,15]. Assume there are 1000 nodes in the IOTA network. $\lambda$ represents the speed at which a node issues transactions, which follows the Poisson distribution in each time slot (Currently, IOTA is mainly committed to removing the Coordinator, but has not yet fully achieved decentralization. Therefore, many studies on Coordicide (IOTA $2.0$) still use simulation methods. Due to different rates of transactions issued by nodes, in this experiment: $\lambda \in 0.015,0.016,0.017,0.018,0.019$, $h=1$ ms). The average time it takes for a node to issue a transaction is denoted as h, the unit length of the time slot. Run these three algorithms separately on a computer (with Intel i5-6500 processor, 8 GB memory).

The running results of URTS are shown in Figure 9. Through the analysis, it can be concluded that:

• URTS is simple and runs fast.
• With the number of transactions reaching the tangle increasing gradually, the number of tips also increases.
• URTS treats each transaction fairly, thus suppressing the generation of permanent tips.
• URTS cannot prevent the generation of lazy tips and does not impose any penalties on lazy tips.

The running results of MCMC are shown in Figure 10. Through the analysis, the following can be concluded:

• Place particles in the tangle at a certain depth (for example, this work selected the position of the Genesis transaction). Next, choose two of the tips by walking backwards based on the transfer probabilities. Because the ledger changes dynamically over time, it will take much time to calculate the transfer probabilities and wandering, so the time complexity of MCMC is much higher than URTS.
• The result of tip selection depends on $\alpha$. In Figure 11, the number of tips remains stable when $\alpha =0.1$. This indicates the smaller the $\alpha$ value, the more random the tip selection result is. When $\alpha =1$, the number of tips remains stable around a single value. The impact of $\alpha$ is not significant. When $\alpha =5$, the number of tips increases with $\alpha$. This shows that the higher the $\alpha$ value, the more inclined the tip selection is towards transactions with a large cumulative weight. This results in transactions with a small cumulative weight not being approved on time.
• Since MCMC is based on biased wandering, it is unlikely to choose lazy tips for approval in new transactions.
• In Figure 10, it can be seen that some permanent tips have been generated, and the number slightly fluctuated over time, but did not increase significantly. This indicates that some tips detained in the tangle have been discarded due to long waiting times. MCMC cannot prevent the generation of permanent tips and does not take punitive measures.

In TDTS, the time for generating the tangles is sequentially segmented by taking 10 h as a time slot. The running results are shown in Figure 12. Through the analysis, the following can be concluded:

• TDTS does not use the way of particle walking in MCMC to select tips, but obtains them by sorting the tip values, which reduces the time complexity and speeds up the transaction confirmation time.
• Under the same conditions as the above two algorithms, we know that the number of tips in TDTS changes steadily around a single value.
• Due to the tendency to choose a tip with a large weight every time, it effectively prevents the formation of lazy tips. If malicious nodes need to add transactions to the tangle, they must contribute the maximum computing power (or cost) each time to compete with honest nodes.
• In the next time slot, the unapproved tips will be prioritized first. Thus, the survival of unapproved tips (also known as permanent tips) will not exceed two time slots. Figure 12 shows the trend of the permanent tips’ number per time slot. However, there are still a certain number of unapproved tips within each time slot in Figure 12; this indicates that some permanent tips have not been completely eliminated.

In summary, by comparing the three algorithms, we drew the following conclusion: TDTS has a simple idea and is significantly better than MCMC in the speed of selecting tips and slightly better than URTS. Its effectiveness in suppressing lazy tips is similar to that of MCMC, which improves system security. Please refer to Figure 13 and Figure 14 for the details.

Although TDTS limits existing permanent tips to no more than two time slots, it still fails to prevent the generation of new ones in a short period of time. In addition, the current tip coefficient only considers an influence factor. We need to require a more-fine-grained approach to analyze and explore other attributes that affect the importance of tips. In the future, it will be necessary to continue optimizing TDTS.

6. Conclusions

This paper proposed a time-division-based tip-selection algorithm, TDTS, to solve the shortcomings of URTS and MCMC. It speeds up the transaction approval rate while minimizing lazy tips and permanent tips. Firstly, divide the time for generating the tangle into equal lengths in sequence to ensure tip selection within the current time slot. Secondly, calculate the tip coefficients and tip values of all tips in the current time slot, and select two tips that meet the conditions by decreasing the tip values. If multiple equal tip values appear, the final result must depend on random selection. TDTS does not use particle wandering to select tips that shorten the transaction approval time. It increases the difficulty of malicious attacks by sorting the tip values. At last, the simulation experiment further proved that the algorithm is effective.