---
# System prepended metadata

title: Height-Projection TSA
tags: [discussion]

---

---
tags: discussion
---

# Height-Projection TSA

Based on https://iota.cafe/t/height-projection-tsa/1197

## Height-Projection Tip Selection

### Idea

Separate the set of tips $T$ into two disjoint sets of almost equal cardinality and select a tip from either set that maximizes the graph height $g_m$.

### Algorithm

During bootstrapping, initialize:
- $g_m \gets 0  \quad \forall m \in S$, where $S$ is the set of solid entry points
- select random $r \in [0,256)$

##### <span style="font-variant:small-caps;">OnNewSolidMessage</span>(m)
*Input:* a solid message $m$
- $g_m \gets 1 + \max_{j=1,\dots,k} g_{m_k}$, where $m_1,\dots,m_k$ are the $k$ parents of $m$.

##### <span style="font-variant:small-caps;">Select</span>(T, i)
*Input:* a set of tips $T$, an index $i \in \{0,1\}$
*Output:* a tip to be used as one of the parents for a new message

- $T_i \gets \{m \mid m \in T \text{ and } b_r(m) = i\}$, where $b_r(m)$ returns the $r$-th bit of the _Message ID_ of $m$
- $B_i \gets \underset{m \in T_i}{\operatorname{arg\,max}}\, g_m$
- select random tip $t \in B_i$
- <span style="font-variant:small-caps;">Return</span> $t$

### Implementation Details

- The graph height $g_m$ never changes and can therefore be stored as a constant in $m$'s metadata. As such, the time complexity of <span style="font-variant:small-caps;">OnNewSolidMessage</span>($m$) is $\mathcal{O}(1)$.
- Instead of during bootstrapping, $r$ can also be initialized every time the node is started. This has the same effect, but does not require $r$ to be persisted.
- For a time complexity of $\mathcal{O}(1)$ of <span style="font-variant:small-caps;">Select</span>(T, i), the sets $B_0$ and $B_1$ should be updated on-the-fly in <span style="font-variant:small-caps;">OnNewSolidMessage</span>($m$):
  - $i \gets b_r(m)$ 
  - **if** $g_m$ is larger than the height of $B_i$:
    - $B_i \gets \{m\}$
  - **else if** $g_m$ is equal to the height of $B_i$:
    -  $B_i \gets B_i \cup \{m\}$

## Parent selection

### Idea

Each message has (up to) four parents, two are selected using URTS and two using Height-Projection Tip Selection.

### Algorithm

##### <span style="font-variant:small-caps;">Select</span>(T)
*Input:* a set of tips $T$
*Output:* a set of tips to be used as the parents of an issues message

- $P \gets$ <span style="font-variant:small-caps;">urts.Select</span>(T) $\cup$ <span style="font-variant:small-caps;">urts.Select</span>(T)
- $P \gets P \cup$ <span style="font-variant:small-caps;">hpts.Select</span>(T, 0) $\cup$ <span style="font-variant:small-caps;">hpts.Select</span>(T, 1)
- <span style="font-variant:small-caps;">Return</span> $P$

### Implementation Details

- If any two <span style="font-variant:small-caps;">Select</span>-calls return the same tip, the duplicates can be skipped instead of re-selecting. This approach, simplifies the implementation slightly.

### Open Questions

- When using the combined parent selection, is it sufficient to use trivial URTS instead of [Weighted Uniform Random Tip Selection](https://github.com/iotaledger/protocol-rfcs/blob/master/text/0008-weighted-uniform-random-tip-selection/0008-weighted-uniform-random-tip-selection.md)? Height-Projection Tip Selection offers strong blowball-protection, therefore the additional checks in Weighted URTS might not be necessary.
- The currently implemented URTS uses a retention policy of a few seconds to only remove tips from $T$ after that amount of time has passed. This can also be applied for the Height-Projection Tip Selection.
An alternative would be, to not only keep the largest graph height values in $B_i$ but also values one or two lower than the maximum. However, using such an approach would weaken its attack protection.
- Do we need to consider high load / attack scenarios in which more than 4 parents should be selected?
- It is trivial to extend Height-Projection Tip Selection, to separate into 4 or more subset. Could that be beneficial?
