# Improving the Coordinator

The most imminent bottleneck seems to be the TSA and in particular the *milestone selection*.

## Status quo

- In Compass, the coordinator uses the same TSA as any IRI node to select the MS.
- One MS is issued about every minute.
- 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

Any good MS selection should meet the following criteria:
- Maximize CTPS (confirmed transactions per MS), even during attacks
- Computationally efficient, even in high TPS scenarios

## Attack vectors

Double spends are no issue as the Coordinator guarantees security and finality. An attacker can however try to reduce the CTPS of the network or try to increase the chance that the coordinator selects his transactions:
- *Parasite Chain*
Creating a structure with many transactions but no references of honest transactions, in such a way that the probability that a tip in that structure is selected is maximized. This attack reduces the number of confirmed honest transactions.
- *Blowball*
Spamming lazy transactions not confirming any honest transactions, i.e. only confirming the entry point of the MS selection. This attack reduces the overall CTPS of the system.
- *Splitting*
Issuing conflicts/re-attachments shortly after the last MS to split the network (see [Conflict Spamming Attack](https://iota.cafe/t/conflict-spamming-attack/232)). This is a dangerous attack, since many honest transactions can be invalidated with just two (or very few) conflicts.

## Solutions

Key observation: The milestone selection has different objectives and restrictions than the regular TSA. Thus, it makes a lot of sense to use an optimized and specialized algorithm for it.

- *Parasite Chain*
Run the MS selection more often (for example every 10s). The resulting tip is not published, but kept hidden as a checkpoint, that is only used as a starting point of the next MS selection.
Any parasite chain that was not present during the creation of a checkpoint will never be selected. Parasite structures published already earlier can be referenced by honest nodes and do not pose an attack vector. Performing the CP selection in shorter intervals also has computational advantages as the set of transactions on which the selection is run will be much smaller.
In order to avoid getting stuck in "local minima", multiple CP alternatives can be computed in each step. The final MS can then be selected from all CP alternatives of the last step.
- *Blowball*
The MS selection strategy must try to maximize the CTPS even in case of blowballs. The optimimum here is to select the heaviest branch, i.e. the tip (or pair of tips) that reference the most transactions since the last MS.
Finding the heaviest tip is similar to computing the cumulative weight, but it propagates forward instead of backward which makes it algorithmically nicer: For each incoming transaction, the set of referenced transactions is computed by forming the union of the sets of its directly referenced transactions. As these sets stay fixed, they can be efficiently computed using bit set of fixed sizes.
For heuristic algorithm to find the heaviest pair, see also [Heavist Branch Selection](https://iota.cafe/t/milestone-selection-algorithm/256).
- *Splitting*
Keep conflicts in the Tangle: Use milestones to order previous transactions and ignore everything but the first conflict. The MSA is still relevant to prevent other attack vectors, but it can be greatly simplified as validity checks are no longer necessary. However, it represents a backward compatible breaking change in the way the balances are computed. See [Conflict White Flag](https://iota.cafe/t/conflict-white-flag-mitigate-conflict-spamming-by-ignoring-conflicts/233).

## Proposal

In the following we will describe a very simple proposal that combines all of the ideas above:

1. Change the balance computation as described in [Conflict White Flag](https://iota.cafe/t/conflict-white-flag-mitigate-conflict-spamming-by-ignoring-conflicts/233). Order the transactions within a MS by postorder depth first traversal (trunk, branch, root).
2. For each incoming transaction, the Coordinator keeps track of the set of referenced transactions since the last MS/CP.
3. After 10s or after a threshold of incoming transactions (this number needs to be determined in experiments using the actual selection algorithm in order to prevent overloads in high TPS scenarios), the Coordinator selects the transaction with the highest coweight, i.e. cardinality of the set of referenced transactions, as the next CP. If there is more than one such transaction, select the one that was seen first.
4. When a CP was selected and more than 60s have passed since the last MS a new MS is published that references the last MS and the last selected CP.

This marks an initial version of such a proposal. There are several aspects where the protocol could be optimized (for resilience and computational performance). However, it seems likely that the overall aspect of the improvements will be rather small:
- Use a different order for Conflict White Flag.
- Compute more than one CP.
- Do not select the optimal heaviest tip, but use a heuristic.
- Select a pair of tips for the MS.