Skip to content

Latest commit

 

History

History
165 lines (128 loc) · 7.18 KB

tip-0003.md

File metadata and controls

165 lines (128 loc) · 7.18 KB
Raw
tip title description author discussions-to status type layer created
3
Uniform Random Tip Selection
Perform fast tip-selection to increase message throughput
Luca Moser (@luca-moser) <[email protected]>
Active
Standards
Core
2020-03-09

Summary

Weighted Uniform Random Tip Selection on a subset enables a node to perform fast tip-selection to increase message throughput. The algorithm selects tips which are non-lazy to maximize confirmation rate.

Motivation

Because of the white-flag confirmation algorithm, it is no longer necessary to perform complex tip-selection which evaluates ledger mutations while walking. Therefore, a more simple, better performing algorithm can be used to select tips, which in turn increases overall message throughput.

To maximize confirmation rate however, the algorithm needs to return tips which are non-lazy. Non-lazy in this context means that a tip does not attach to a cone of messages which is too far in the past. Such a cone is likely to be already confirmed and does not contribute to the rate of newly confirmed messages when a milestone is issued.

Detailed design

Definitions:

  • Direct Approvers - The set of messages which directly approve a given message.
  • Approvee - The directly approved message of a given message.
  • Solid Message - A message that its past cone is known to the node.
  • Valid Message- A message which is syntactically valid.
  • Tip - A valid solid message that doesn't have approvers. Its past cone contains only valid messages.
  • Score - An integer assigned to a tip. The tip selection algorithm uses it to determine how to select tips.
  • Confirmed Root Message - The set of first seen messages which are confirmed by a previous milestone when we walk the past cone of a given message. The walk stops on a confirmed message.
    Note that the red marked milestone is also a Confirmed Root Message. sdf
  • Message Snapshot Index (MSI) defines the index of the milestone which confirmed a given message.
  • Oldest Message Root Snapshot Index (OMRSI) defines the lowest milestone index of a set of Confirmed Root Messages of a given messages.
  • Youngest Message Root Snapshot Index (YMRSI) defines the highest milestone index of a set of Confirmed Root Messages of a given message.
  • Latest Solid Milestone Index (LSMI) the index of the latest solid milestone.
  • Below Max Depth (BMD) defines a threshold value up on which it is decided on whether a message is not relevant in relation to the recent parts of the Tangle. The current BMD for mainnet nodes is 15 milestones, which means that messages of which their OMRSI in relation to the LSMI is more than 15, are "below max depth".

OMRSI / YMRSI example

Given the blue PoV message, the OMRSI of it is milestone 1 and YMRSI milestone 2. Note that, here again, the milestones are also Confirmed Root Messages. sdf

Milestone based tip scoring

The milestone based scoring defines a tip's score by investigating the tip's relation to the cone it approves and previous issued milestones.

A tip can have one of 3 score states:

  • 0: The tip is lazy and should not be selected.
  • 1: The tip is somewhat lazy.
  • 2: The tip is a non-lazy tip.

Definitions:

  • C1: Max allowed delta value for the YMRSI of a given message in relation to the current LSMI.
  • C2: Max allowed delta value between OMRSI of a given message in relation to the current LSMI.
  • M: Max allowed delta value between OMRSI of the given message in relation to the current LSMI. M is the below max depth (BMD) parameter.

Recommended defaults:

  • C1 = 8 milestones
  • C2 = 13 milestones
  • M = 15 milestones

Scoring Algorithm (pseudo code):


enum Score (
    LAZY = 0
    SEMI_LAZY = 1
    NON_LAZY = 2
)

const (
    C1 = 8
    C2 = 13
    M = 15
)

func score(tip Tip) Score {
    
    // if the LSMI to YMRSI delta is over C1, then the tip is lazy
    if (LSMI - YMRSI(tip) > C1) {
        return Score.LAZY
    }
    
    // if the OMRSI to LSMI delta is over M/below-max-depth, then the tip is lazy
    if (LSMI - OMRSI(tip) > M) {
        return Score.LAZY
    }
    
    if (LSMI - OMRSI(tip) > C2) {
        return Score.SEMI_LAZY
    }

    return Score.NON_LAZY
}

Random Tip-Selection

A node should keep a set of non-lazy tips (score 2). Every time a node is asked to select tips to be approved, it will pick randomly from the set. A node must not execute tip-selection if it is not synchronized.

A tip should not be removed from the tips set immediately after it was selected in select(), to make it possible for it to be re-selected, which in turn makes the Tangle wider and improves synchronization speed. A tip is removed from the tips set if X amount of direct approvers are reached or if a certain amount of time T passed. It is recommended to use X = 2 and T = 3 but the threshold should be configurable.

Purpose Of Semi-Lazy Tips

Semi-Lazy tips are not eligible for tip-selection, but the coordinator node may implement a tip selection algorithm that confirms semi-lazy tips. Semi-lazy tips will usually be left behind, but parties interested in having them confirmed are incentivized to run spammers that will actively reduce the amount of semi-lazy tips eligible for coordinator's tip selection. Given a coordinator that chooses semi-lazy tips, running such spammers may get those messages confirmed before they become lazy.

Drawbacks

Depending on when and how often YMRSI/OMRSI values are computed, this tip-selection could still have a slow runtime, as one would need to constantly walk down the Tangle to compute those values. However, smart caching might resolve this issue.

Rationale and alternatives

The previous tip-selection was written in accordance to the original IOTA whitepaper, as it also functioned as part of the consensus mechanism. However, relatively soon it became apparent that the cumulative weight computation was too heavy for an actual high throughput scenario and, as such, the CW calculation is currently not used within node implementations at all.

Because confirmations with the white-flag approach no longer approve cones only with state mutations, which are consistent with a previous ledger state, it makes sense to alter the tip-selection to provide a fast way to get tips to approve with one's own message. The only important thing is to disincentive lazy behaviour to be able to maximize confirmation rate.

Unresolved questions

When to compute the score and YMRSI/OMRSI of a transaction?

It is not yet clear when or how often the YMRSI/OMRSI values of a transaction should be updated. If the values are only computed once after a transaction became solid, the YMRSI/OMRSI might not resemble the true values, as subsequent milestones might confirm transactions within the same cone the given transaction approved.

Currently, we suggest recomputing the values every time a new milestone solidifies. Since different tips indirectly reference the same transactions, this computation can be optimized.

Copyright

Copyright and related rights waived via CC0.