Skip to content

Latest commit

 

History

History
170 lines (127 loc) · 9.19 KB

0005-white-flag.md

File metadata and controls

170 lines (127 loc) · 9.19 KB
Raw

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 bundles by enforcing deterministic ordering of the Tangle and applying only the first bundle(s) that does 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 transaction 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 bundle A to be:

  • referenced (indirectly or directly) by bundle 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;
  • conflicting: A would lead to an invalid ledger state if applied;

In case of conflicting bundles with White Flag, a node applies only one bundle 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 bundle; hence, the need for a deterministic ordering of the Tangle.

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

Note: this RFC is about ledger computation only. For this reason, it assumes that the past cone of a milestone has already been confirmed and all the referenced bundles have been validated. However, in the event that an invalid bundle was encountered in the confirmation traversal, a node's expected behaviour would be to completely stop operations - and log the error - as it would mean the coordinator confirmed something it should not have.

Deterministically ordering the Tangle

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

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

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

For this reason, this RFC propose 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 and by going first through trunk bundle, then branch bundle and finally current bundles. Since only a subset of bundles is considered, the stopping condition of this DFS is reaching bundles that are already confirmed by another milestone.

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

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

Once a bundle 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 bundle conflicting with a bundle already confirmed by a previous milestone would also obviously 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 bundles.

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.empty()) {
        curr = s.peek()

        // Only apply if a leaf has been reached or both approvees have been visited or confirmed by another milestone
        if ((solid_entry_points.contains(curr.trunk) || visited.contains(curr.trunk) || curr.trunk.confirmation_index != milestone.index)
          && (solid_entry_points.contains(curr.branch) || visited.contains(curr.branch) || curr.branch.confirmation_index != milestone.index)) {
            ledger.apply(curr)
            visited.add(curr)
            s.pop()
        }
        else if (!solid_entry_points.contains(curr.trunk)
          && !visited.contains(curr.trunk)
          && curr.trunk.confirmation_index == milestone.index) {
            s.push(curr.trunk)
        }
        else if (!solid_entry_points.contains(curr.branch)
          && !visited.contains(curr.branch)
          && curr.branch.confirmation_index == milestone.index) {
            s.push(curr.branch)
        }
    }
}

Notes:

  • Even though the tangle is a graph made of transactions, for the sake of this pseudo-code it is considered as a graph of bundles. For this reason, when the trunk and/or the branch of a bundle are mentioned, they are actually referring to the trunk and/or branch of the last transaction of the bundle.
  • solid_entry_points is a set of hashes that are considered solid even though we do not have them or their past in 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 transaction is also a solid entry point.
  • confirmation_index is the index of the milestone that confirmed the bundle.

Example

In this example, there are 26 bundles labeled from A to Z. The set of red bundles {A, B, C, E, F, H} is confirmed by milestone H. The set of purple bundles {D, G, J, L, M, N, K, I, O, S, R, V} is confirmed by milestone V. The set of blue bundles {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, bundle G and bundle 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) 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.

Rationale and alternatives

The main alternative to White Flag is what has been done so far i.e. not allowing conflicting bundles 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 tempered with and fed to a node, it would eventually lead to an invalid ledger state where a bundle 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 bundles 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.