# Tip Selection

The TSA is one of the key algorithms for the Tangle as it has a huge impact on the health and performance of the entire system.

## Status quo

- IRI does a random walk ($\alpha=0$) starting from one of the latest MS (e.g. depth=4).

- There is no difference between IRI tip selection and Compass milestone selection.
- If the "depth" of the entry point is too large (too many new transactions) the RW will take very long, around 100-200TPS.
- If the TSA does not return a tip within the given time limit (60s), the new MS will directly approve the last MS. (This effectively renders the network useless in high TPS scenarios.)

## Objectives

- Let the Tangle grow in a healthy direction, even under attacks
- Computationally efficient, even in high TPS scenarios
- `belowMaxDepth`: Do not confirm tips that connect too far in the past
#### Good to have (for nodes)
- Nash-Equilibrium: Changing its own TSA makes the outcome worse
- Incentives to select a tip that helps the network
- Punish "lazy" tips

:::warning
There is no need to consider security or finality since we have the Coordinator.
:::

## Milestone selection

The objectives are different:
- Coordinator is a special node run by the IF.
- The Coordinator has more computational power than the average node.
- The MS does not make the Tangle grow; only indirectly.
- Selection can be enforced.

Maximizing (honest) CTPS is the main and only goal!

### Attack vectors

#### Parasite Chain
Creating a structure so that the confirmed transactions or honest confirmed transactions are low.
#### Blowball
#### Splitting
Dangerous, since many honest transactions can be invalidated with just two conflicts.

### Solutions

#### Splitting
- Keep conflicts in the Tangle. [Conflict White Flag](https://iota.cafe/t/conflict-white-flag-mitigate-conflict-spamming-by-ignoring-conflicts/233)
- Guarantees 100% protection against splitting attack.
- Very easy to implement, no network dependent parameters.

##### To decide
- How a transactions ordered?
Postorder depth first traversal (trunk, branch, root).
> [name=Wolfgang Welz] Seems like a very good solution.
- Are temporary overdrafts withing one milestone allowed?
> [name=Wolfgang Welz] Temporary overdrafts get even more complicated with "conflict depth". They are currently not supported, so we should not introduce them.
- Conflicts min depth: $-\infty$ works, but there is no local validity; 1 could lead to race conditions
> [name=Wolfgang Welz] No problem computationally (without overdrafts), why do we want this? Are there any usecases or just for the sake of "clean Tangle"?
> Discarding (not ignoring) conflicts causes splits, if the MS only picks up subsets of before valid conflicting transactions --> Don't discard only ignore!


#### Parasite Chain
- Choosing secret checkpoints against hidden structures.
- Issuing secret checkpoint transactions against self referencing structures.
- Future cone marker makes filtering $O(1)$.
##### To decide
- Possibility for the Coordinator to issue secret transactions? If yes, do it!
- Is it enough to only select/issue one CP?
- Selecting just one CP drastically simplifies the algorithm, updating information on-the-fly is more complex (e.g. marker).
- Danger of picking a "local maximum" is OK when a low-variance tip selection is used.


#### Blowball
- Any reasonable tips selection should work.
- Heaviest branch / largest co-weight offers the strongest protection.
> [name=Wolfgang Welz] Heaviest branch seems to be very good for the MS. Could be computationally expensive especially for very high TPS. But there are a few solutions: a) use bitsets b) issue more CPs c) use heuristic


## Tip selection

- Keep NE/incentives in mind.
- Should be "closer" to URTS.
- Low orphanage rate.
- Splitting does not need to be considered.
- Validity of tx can be checked upon arrival:
- Store MS-index (latest referenced MS) in every transaction
- Check whether that tx can be applied to that ledger state
- No need for a walk
- Attack vectors:
- Lazy tips
- Blowball

### Ideas

- Almost URTS: URTS but penalizing txs confirming too old transactions or transactions with too many children
- Heaviest Branch heuristic
- Combining heaviest branch with URTS
- ...