In this topic, we discuss a potential solution to mitigate the Conflict spamming attack in a setting where milestones or checkpoints exist.
Here, an attacker has created several equivalent conflicts to introduce a network split and to force the re-attachment of many honest transactions.
Ignoring Conflicts below Milestones
The availability of Coordinator milestones is a powerful tool as it provides us with global and unmodifiable timestamps. This allows us to specify a well-defined and globally accepted way to compute the ledger state of a milestone even if it contains conflicting transactions in its past cone:
Let the milestone number of a transaction be the first milestone which approves it. Further, let < denote an order on the set of all transaction bundles with the same milestone number. They can, for example, be ordered by hash (or in some other way since it doesn’t matter).
Now, the ledger state L_m for milestone m can be computed in the following way:
- Initialize B_0 \leftarrow L_{m-1}
- Sort the bundles x_i with milestone number m such that x_1 < \dots < x_n
- For i = 1,\dots,n do
- If x_i applied to B_{i-1} is valid, then
- B_i \leftarrow x_i applied to B_{i-1}
- Else
- B_i \leftarrow B_{i-1}
- If x_i applied to B_{i-1} is valid, then
- Return L_m = B_n
Essentially, B_i is the balance seen at bundle x_i . When computing the next B_i , we ignore x_i if it makes the balance negative (i.e. it is a double spend).
Note: As described in the algorithm, conflicts should be ignored not only within one MS, but also across multiple MS. Otherwise, the following situation could occure:
When there is only milestone MS1, using Conflict White Flag, it is perfectly valid to issue to conflicting transactions C1 and C2 and to attach to those conflicts. When the next milestone MS2 is issued only confirming C1 but not C2, C2 must also be ignored. It cannot be seen as a conflict, otherwise all valid transactions attached to C2 will also become invalid and would require re-attachments. This would allow for a different kind of splitting attack.
The following are the advantages of this system:
- The complexity of the balance computation is equal to the complexity of sorting all the new transactions by hash (or similar) which can be done very efficiently.
- A conflict has no different impact on the system than any other transaction. As such, the conflict spamming attack is completely eliminated.
- Re-attachments are easy: If two reattachments are approved by milestones, the second one will be ignored.
- As conflicts are ignored in the balance computation, they don’t need to be considered during tip selection of the nodes. This allows for much easier tip selection algorithms and tremendously speeds up this step.
- By using this approach in combination with an appropriate TSA, during regular use, no honest transaction will ever require re-attaching.
This method has the following potential downsides:
- The ledger state is only well-defined at milestones. This means, we have to wait till each milestone is issued in order to confirm a spend (exactly the current mainnet status).
- To prove that a certain (non-milestone) transaction is valid, it is no longer sufficient to just provide the “path” to its confirming milestone, but, instead, all transactions in its past cone.
(When it manifests that this is a relevant use case, additional Merkle tree information could be added to the milestones to overcome this drawback.)