Conflict white flag: Mitigate conflict spamming by ignoring conflicts

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}
  • 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.)
1 Like

The simplest way to do this is to use DFS where we always pick the trunk first (arbitrary choice). This will give us a topological order that will be consistent across nodes. We also have to traverse the txs anyhows so we are actually not incurring any additional overhead with sorting.

We should of course wait until we go down the recursion stack and when we hit a leaf (a transaction that has all of its “approvees” confirmed) only then we should start changing the state as we traverse up. This will ensure that older txs are the ones that count.

  • 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.)

Currently the node API just tells you whether the tx is approved or not via a flag the tx has. Is there anyone who wants those fancy proofs?

So just to be clear, what we can do is while we traverse is to save on the side any “bad” bundle that leads to a negative state. After we are done applying all the “good” bundles to the state we can try to apply the “bad” ones again.
We repeat the process until the “bad” bundles set size stops changing.

This adds overhead, but I think we should allow temporary overdrafts. Especially if the order of the bundles is not defined by the tangle DAG.

Also, the way we do conflict detection is dependent on whether we do reusable addresses (with Hybrid signatures: Combining WOTS with hashed public keys). In the meanwhile I will create an issue on github that ignores the reusable address portion…

Two remarks to the original proposal:

  1. Conflicts should be ignored not only within one milestone, but also across milestones.
    It is not possible to say, that transaction x with milestone number m_x conflicts with transaction y and milestone number m_y, even if m_x \gg m_y. As this would lead to a split network.
  2. If temporary overdrafts (within the same milestone) are allowed, the balance computation algorithm would get more complicated (as described above by @gal.rogozinski). Also, it could be possible that a future milestone only confirms (and thus ignores) the “bad” bundle. After this, the “good” bundle would be a regular transaction and not part of any overdraft and thus lead to an inconsistent state.
    As temporary overdrafts are currently not supported, it seems best to not introduce them.

The OP has been eddited to take these aspects into account.

They are supported currently. When a milestone comes in we first compute the new ledger state and only later we check that they are consistent.
To me temp overdrafts make sense, because one can make a funding transaction and then make another transaction that utilized the funds but it is in the “wrong order” on the tangle