Height-Projection TSA

--- 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)$ ##### OnNewSolidMessage(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$. ##### Select(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$ - Return $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 OnNewSolidMessage($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 Select(T, i), the sets $B_0$ and $B_1$ should be updated on-the-fly in OnNewSolidMessage($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 ##### Select(T) *Input:* a set of tips $T$ *Output:* a set of tips to be used as the parents of an issues message - $P \gets$ urts.Select(T) $\cup$ urts.Select(T) - $P \gets P \cup$ hpts.Select(T, 0) $\cup$ hpts.Select(T, 1) - Return $P$ ### Implementation Details - If any two Select-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?