tip: 2
title: White Flag Ordering
description: Mitigate conflict spamming by ignoring conflicts
author: Thibault Martinez (@thibault-martinez) 
discussions-to: https://github.com/iotaledger/tips/pull/5, https://github.com/iotaledger/tips/pull/30
status: Active
type: Standards
layer: Core
created: 2020-03-06

Summary

This RFC is part of a set of protocol changes, Chrysalis, aiming at improving the network before Coordicide is complete.

The feature presented in this RFC, White Flag, allows milestones to confirm conflicting messages by enforcing deterministic ordering of the Tangle and applying only the first message(s) that will not violate the ledger state.

The content of this RFC is based on Conflict white flag: Mitigate conflict spamming by ignoring conflicts.

Motivation

Eliminates the Conflict spamming attack;
As conflicts are ignored in the balance computation, they do not need to be considered during tip selection of the nodes allowing much easier tip selection algorithms leading to increased TPS;
By using this approach in combination with an appropriate TSA, during regular use, no honest message will ever require re-attaching leading to increased CTPS;
Does not come with added computation complexity by integrating nicely into already existing algorithms;

Detailed design

First, let us define what it means for a message A to be:

referenced (indirectly or directly) by message B: A is contained in the past cone of B;
confirmed: A is referenced by a milestone;
applied: A is confirmed and applied to the ledger state;
ignored: A is confirmed but not applied because it is semantically invalid;
conflicting: A would lead to an invalid ledger state if applied;

In case of conflicting messages with White Flag, a node applies only one message to the ledger state and ignores all the others. For this to work, all the nodes need to be sure they are all applying the same message; hence, the need for a deterministic ordering of the Tangle.

First, this RFC proposes a deterministic ordering of the Tangle, then it explains which message is selected in case of conflicts.

Note: The past-cone of milestone can only contain syntactically valid messages. If an invalid message is encountered, operations must be stopped immediately.

Deterministically ordering the Tangle

When a new milestone is broadcasted to the network, nodes will need to order the set of messages it confirms.

A subset of the Tangle can be ordered depending on many of its properties (e.g. alphanumeric sort of the message hashes); however, to compute the ledger state, a graph traversal has to be done so it can be used to order the messages in a deterministic order with no extra overhead.

This ordering is then defined as a topological ordering because it respects the dependency of messages, ensuring that parents of a message are applied before it. Since there are multiple valid topological orders for the same graph and, to avoid conflicting ledger states, it is required that all nodes apply messages in the exact same order.

For this reason, this RFC proposes an order that has to be rigorously followed by all node implementations. This order is the topological ordering generated by a post-order Depth-First Search (DFS) starting from a milestone message, going through its parents (in the order they appear in the message) and finally analysing the current message. Since only a subset of messages is considered, the stopping condition of this DFS is reaching messages that are already confirmed by another milestone.

Applying first message(s) that does not violate the ledger state

If a conflict is occurring in the set of messages confirmed by a milestone, nodes have to apply the first - with regards to the order previously proposed - of the conflicting messages to the ledger and ignore all the others.

Once a message is marked as ignored, this is final and cannot be changed by a later milestone.

Since the ledger state is maintained from one milestone to another, a message conflicting with a message already confirmed by a previous milestone would also be ignored.

Pseudo-code

The following algorithm describes the process of updating the ledger state which is usually triggered by the arrival of a new milestone confirming many new messages.

Pseudo-code means that implementation details such as types, parameters, ..., are not important but that the logic has to be followed with care when implementing a node to avoid differences in the ledger state.

update_ledger_state(ledger, milestone, solid_entry_points) {
    s = new Stack()
    visited = new Set()

    s.push(milestone)

    while (!s.is_empty()) {
        curr = s.peek()
        next = null

        // Look for the first eligible parent that was not already visited
        for parent in curr.parents {
          if (!solid_entry_points.contains(parent) && !parent.confirmed && !visited.contains(parent)) {
            next = parent
            break
          }
        }

        // All parents have been visited, apply and visit the current message
        if next == null {
          ledger.apply(curr)
          visited.add(curr)
          s.pop()
        }
        // Otherwise, go to the parent
        else {
          s.push(next)
        }
    }
}

Notes:

solid_entry_points is a set of hashes that are considered solid even though we do not have them or their past in a database. They often come from a snapshot file and allow a node to solidify without needing the full tangle history. The hash of the genesis message is also a solid entry point.
confirmation_index is the index of the milestone that confirmed the message.

Example

In this example, there are 26 messages labeled from A to Z. The set of red messages {A, B, C, E, F, H} is confirmed by milestone H. The set of purple messages {D, G, J, L, M, N, K, I, O, S, R, V} is confirmed by milestone V. The set of blue messages {Q, U, X, Y, Z, W, T, P} is confirmed by another milestone.

Applying the previously shown algorithm on the purple set produces the topological order {D, G, J, L, M, R, I, K, N O, S, V}.

Here, message G and message O, both confirmed by milestone V, are conflicting. Since in the topological order just produced, G appears before O, G is applied to the ledger and O is ignored.

Drawbacks

The ledger state is now only well-defined at milestones, meaning that we have to wait until each milestone is issued in order to confirm a spend;
Everything that is seen is now part of the Tangle, including double-spend attempts, meaning that malicious data will now be saved as part of the consensus set of the Tangle;
To prove that a specific (non-milestone) message is valid, it is no longer sufficient to just provide the "path" to its confirming milestone, but instead all messages in its past cone.

Rationale and alternatives

The main alternative to White Flag is what has been done so far i.e. not allowing conflicting messages confirmation. As explained in this RFC, this comes with added complexity when performing a Tip Selection Algorithm because a node has to constantly check for ledger inconsistencies.

As part of Chrysalis and coupled with an adequate Tip Selection Algorithm, White Flag is an improvement of the network by allowing a potential increase of TPS/CTPS.

Unresolved questions

A node consumes and produces snapshot files and bases the computation of its ledger state on them. In the current network, if one of these files was tampered with and fed to a node, it would eventually lead to an invalid ledger state where a message confirmed by a milestone would actually be a double spend. This situation would be detected by the node and it would stop its activities as a security measure. However, with White Flag, such messages would be confirmed by milestones but ignored by the node, the fake snapshot then going unnoticed. The ledger state would then become more and more corrupted and the view of the balances completely wrong, errors just accumulating over time. The need for a snapshot verification mechanism is then amplified by the implementation of White Flag. This mechanism being out of the scope of this RFC, it will be described in another RFC.

The Tangle Improvement Proposal (TIP) Book