11

The IOTA Whitepaper dances around suggestions as to how a tip selection algorithm should be constructed.

  1. We need checkpoints for security to ensure that λ > μ (Arrival rate of honest nodes) > Computing Power of Attacker
  2. Nodes should use a MCMC algorithm to select tips
  3. Nodes should use a strategy of choosing N random sites to walk towards tips
  4. Nodes should discard random walker tips that arrive too fast (likely lazy tips) or too slow (likely ended up in a parasite chain)
  5. Nodes should choose a parameter, α, to determine how much a random walker should prefer weighted nodes to traverse to a tip
  6. Nodes need to have a "sharp-threshold" rule to make it hard to maintain balance between two branches of a tangle and thwart a splitting attack
  7. Nodes should consider a method where the next step in the Markov chain is deterministic yet more random when a walker is closer to tips (to avoid entering a weaker branch

(Am I missing any?)

What is the actual algorithm that the majority of IOTA nodes currently use to select tips to approve?!

Improve this question

1 Answer 1

Reset to default
7
+50

(I already know that this answer will disappoint you - as it did disappoint me when I found it out)

The current algorithms around the tangle depend on a central node run by the Foundation, known as the Coordinator (or Coo). This node will publish a signed milestone transaction approximately every minute. The exact rules which tips will be selected for this are not public (and the Coordinator source is not open, despite the Foundation promising to publish it soon™ after they become a legal entity), but we can at least assume that every milestone published will (directly or indirectly) approve the previous milestone.

Each node will keep track of the latest solid subtangle milestone transaction, i. e the milestone with highest milestone index that has a valid signature from the Coordinator and where the node has seen all transactions that are (directly or indirectly) approved by it.

For determining confirmation state, the node will consider a transaction confirmed if and only if it is (directly or indirectly) approved by the latest solid subtangle milestone. This milestone is also used to compute the authoritative balances returned when you ask the node for an address' current balance.

Tip selection uses a MCMC algorithm where every node has a weight of 1, while the starting node is determined by the following rules:

  • For one of the two tips, the MCMC algorithm always starts at the latest solid subtangle milestone (That way, transactions will always approve this milestone, making the transaction a likely candidate for being chosen as a tip for the next milestone by the Coo).

  • When a transaction to reference was passed when calling the tip selection API (which is used by the light wallet to "promote" stale transactions), for the second tip the MCMC always starts at that given transaction

  • When no transaction to reference was passed, the second MCMC will start at a previous milestone. The milestone depth can be specified as a parameter to the API; the wallet always uses 3 but some other tools (like the transaction spammer) use higher single-digit values. So when the current milestone is 12345 and depth is 3, the second walk will start at milestone 12342.

The tip selection algorithm is also tweaked so that it never ends inside a bundle (in case the rest of the bundle has not yet arrived at that node). In case the selected tip is not a tail transaction of a bundle, the MCMC will "walk back" to the previously visited node that is a tail transaction. As in a valid bundle, the tail transaction directly or indirectly approves all other transactions of the bundle, this case cannot happen if the bundle has arrived completely, since the algorithm would continue walking towards the tail transaction in that case.

I hope this answers your questions. In case I missed anything, feel free to comment.

Improve this answer
7
  • Is it correct that after walking back, the random walk does not actually walk forward further?
    – Phil-ZXX
    Jan 20, 2018 at 15:38
  • In case it has to walk back because of an incomplete bundle, it does not walk forward afterwards (it would probably lead to the same incomplete bundle anyway) - at least when I checked the code last (could theoretically have been changed meanwhile)
    – mihi ♦
    Jan 20, 2018 at 16:12
  • 2
    what exactly are the transition probabilities (from the current node to one of its children?
    – GJEEE
    Jan 21, 2018 at 15:08
  • 1
    @GJEEE The probability of a path to be taken is proportional to the number of descendant nodes behind it, where every node is treated equally with weight 1. In particular, if a node has only one child, the probability is 100%.
    – mihi ♦
    Jan 21, 2018 at 21:17
  • 1
    IOTA Nodes, currently, do not choose which tips to verify. The Central Coordinator tells them which which tips to verify and then they in turn verify that the transaction performed Proof of Work and legitimately has the funds?
    – Bill Bisco
    Jan 23, 2018 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.