Height-Projection TSA

Introduction and Assumptions

Recent discussions on the protocol group brought to light a potential problem in the Chrysalis TSA: it inability to handle structural CTPS attacks (such as blowball attacks and side-chain attacks) with overly-powerful attackers, i.e. attacker that have issuance power of the same order of the rest of network (or even larger).
Before talking about the proposed solution in this document, it is important to state two points about properties of the TSA:

  • Ultimately the tip selection algorithm is free, so each node may choose the one they want. It is realistic, although, to consider that the standard algorithm will me used by the majority (at least 80-90%) of the network if it has no evident drawbacks as speed and security (what we make sure doesn’t happen).

  • In an ideal scenario an attacker will not be able to have such issuance power, as it’s a basic assumption that the network runs on a TPS high enough such that this kind of attack would be too expensive to be performed.

  • Finally, the IOTA 2.0 protocol has other defense mechanisms that would act in such a situation, as the rate control and congestion control, so this problem and solutions are inherently suited for chrysalis, with ideas that could be used for IOTA 2.0.

Step 1: k-fold TSA

The first ingredient in the TSA is to increase the number of tips a new message needs to approve from 2 to k, this will ensure that tips are approved in a much faster way and make rarer the occurrences of orphan messages and side structures. Some points about this are:

  • The discussion about increasing the number of approvers is going for a while and looks certain for Coordicide, what would make the implementation in Chrysalis a smoother transition for the network.
  • The main proposal currently considered states that a node, instead of issuing always
  • There are some minor drawbacks in the increase too: message size, issuance time and Tangle width.
    • Message Size: Although there is some increase in size, it is negligible when compared to the whole size of the structure, so this change will not have a big impact.
    • Issuance time: The time needed to select k tips will be larger than the time to select 2 in a proportional way (of course), but the impact of this change here depends on the TSA used. As we will show in the next sections, the proposed TSA is supposed to be fast enough such that this time is still small compared to the PoW duration.
    • Tangle width: Although it is not easy to calculate the expected width of the tangle, we can have an idea about the impact looking at the expected number of tips. With the k-fold URTS and the standard assumptions of \lambda,h we have that the expected number of tips is \frac{k}{k-1}\lambda h , so the impact is not so big.
      • The impact still can be countered with a imposed delay: When a message is selected as a parent, it still kept as a tip for extra s seconds. This works as an “artificial network delay” and hence increases the number of tips and width of the Tangle.
  • Another fair concern is that under low network usage (adoption phase), the increased number of approvals could make the network become chainlike, this can be easily solved by using a variable number of approvals: When the network is using under x% of its capacity then the number of approvals for each new message changes from maximum k to maximum m.

Step 2: Height Function

The proposed TSA will use a height function it maxes in order to chose tips.

  • The main purpose of the height function is to prevent blow-ball and spam like attacks, since messages with such behavior will have constant to low height.
  • There is not a single possibility for a height function here. Many are usable including the old Cumulative weight and its similars. Since we care about the simplicity of the function to make it faster to calculate, our standard proposal here will be the graph height. Defined are follows.
    • Graph height: If message x approves messages x_1, x_2,…,x_k, then the graph height G(x) is defined as :
      G(x)=1+\max _{j=1,2,\ldots,k} G(x_j),
      and G(g)=0, where g is the Genesis message.
      A weakness of using a height maximizer TSA is that an attacker could potentially build an structure in such a way that honest users would end up selecting tips from that structure all the time, potentially trapping the tangle and reducing the finality rate of messages. This could even be paired with eventual blowballs in the structure to also trap tips using URTS. The proposed TSA in the next section is exactly a counter-measure against such attacks.

Step 3: Height-Projection Tip Selection Algorithm

Now with all the ingredients we can properly define the tip selection algorithm. The idea is to get the set of all tips \mathcal{T} and split it in two subsets \mathcal{T}_1 and \mathcal{T}_2=\mathcal{T}_1^\complement in such a way that such subsets are very simple to define and check!
We will call each pair of subsets (that constitutes a partition) a projection.
Then each new pair of approvals would be a selection from each of such subsets, while the first two tips would use URTS. Different projections should be defined each time, with the only constraints being that they should be very easy to calculate and should have a meaningful proportion of the tips (in expected value at least).

To illustrate how it works I will give an example and then we can discuss how this make potential structure attacks harder.

Example: 4-fold HP-TSA

Let \mathcal{T} be the set of tips, \mathcal{T}_1 be the subset of tips with odd message ID and hence \mathcal{T}_2 the ones with even ID.
Each message needs to chose 4 tips to approve. The rules used for each would be:

  • Tip 1: URTS
  • Tip 2: URTS
  • Tip 3: Select one tip uniformly from the 10 tips with highest height in \mathcal{T}_1.
  • Tip 3: Select one tip uniformly from the 10 tips with highest height in \mathcal{T}_2.

Analysis

  • Blowballs are structures that trap TSAs that need to “walk” from milestones, while also working as spams that hinder the URTS TSA. The height function potentially kill its effectiveness.
  • Side chains in the past relied on conflicting chains (not really chains since we are in a DAG, maybe side-structures would be more appropriate) not being able to merge to create race conditions and kill one of the chains. This is already impossible to happen due to the white-flag approach in place, those chains would effectively merge.
  • Under the use of a height-maximizing TSA, the attacker could try an alternative structure attack where it creates a structure that will have all the height-maximizing tips. If he can do this at will, he can effectively drop an specific message he desires or just do this action multiple times in order to drop the confirmation rate.
  • Increasing the number of approvals does not prevent this if just height-maximizing or height-based selections are made. Mixing height-maximizing TSA with URTS partially works since an attacker would need to spam tips while creating the structure to trap a milestone, reducing his effective power.
  • The Height-Projection TSA cuts the attacker power, since now he needs to make multiple structures inside each of the subsets in order to trap messages (especially the milestone). If the attacker can control his message IDs then it’s a big cut in his power, and if he couldn’t for some reason then it completely negates the attack.
  • In case a subset is not large enough for the selection, the TSA could in that instance be replaced by the URTS.

Potential improvements

Since we made assumptions that would guarantee that such TSA would not affect the performance of the network, the only potential problem would be in the predictability of the quantity used (in this case message ID). Introducing randomness would potentially solve this problem.
• The first way to implement randomness would be in the quantity used for defining the projections. This idea is equivalent to making random subsets (perhaps just using coin-tossing variables for each tip). This would the subsets unpredictable.
• Another way to induce unpredictability without resorting to randomness is to use local modifiers: Nodes could replace messageID with arrival time (up to some precision). This would make the attacker unable to determine how each node will build their projections, as they would be different.
• The two solutions above can be combined if each node uses their own independent source of randomness.

PS: This idea (and the name) is a draft so comments are very welcome!

1 Like

Pretty interesting solution Darcy, thanks!
Implementation-wise seems pretty trivial too; associate a height metadata to each transaction within a certain amount of milestone epochs (no need to keep those BMD). Your proposal would translate to having solid entry points [SEPs] (pruning point / BMD border) at height 0, the rest could be calculated as a +1 over the max of approved tips.
What I don’t see yet is how we can efficiently update in cascade the heights metadata when new SEPs are established, with pruning rolling forward towards the future. With a BMD of 15, 10 seconds between Milestone epochs, and a 100 TPS regime, we will have to “walk” from SEPs to current tips around 15K worth of transactions. We will have to walk them as heights are hierarchically dependent on each other, all this while holding a lock on the ledger. While calculation seems a no-brainer, this update process looks pretty painful.

Darcy, many thanks!

^ looks like some text was lost here?..

Exactly for that reason, I don’t think that the metadata should be updated during pruning:

  • During bootstrapping, the node loads a snapshot file. All the solid entry points of this snapshot get initialized with height=0.
  • For each newly solid transaction, it is always possible to compute the height from its parents.
  • The height of a transaction is stored as part of its metadata and never changes.
  • Theoretically, the height could overflow since it is always growing. However, by storing the height as a 64-bit integer this will never happen in practice.
1 Like

Here my thoughts about a potential implementation of the proposed ideas:

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? 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?
2 Likes