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.
- Graph height: If message x approves messages x_1, x_2,…,x_k, then the graph height G(x) is defined as :
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!