Protocol Change: Ignore Conflicts (white-flag)

[GalRogozinski]

Description

If a milestone approves conflicting transactions simply ignore one. Do this by ordering the approved cone in a deterministic way. See: https://iota.cafe/t/conflict-white-flag-mitigate-conflict-spamming-by-ignoring-conflicts/233 and https://github.com/thibault-martinez/protocol-rfcs/blob/rfc-white-flag/text/0005-white-flag/0005-white-flag.md

Motivation

1. The abilty to merge conflicting subtangles should ensure a high CTPS.
2. Pave the way to different faster tipselection algorithms

Requirements

1. Traverse all approved transactions in deterministic manner
2. Find conflicts as you traverse ~3. Allow temporary overdrafts like before. For example if one spends, 10 iotas from an empty address and then later someone funds this address, it should be accepted.~
3. Add a flag to the transaction structure that tells us whether the tx was ignored or accepted
4. In case you are not approving conflicts, the resulting ledger state should be the same as before.

Proposed algorithm

1. When a milestone comes in start traversing in DFS (https://en.wikipedia.org/wiki/Depth-first_search) preferring trunk. Stop at the leafs (transactions that has only approved parents).
2. Start applying bundles to the diffmap only as you go up the recursion stack (when you climb up back from the leafs)
3. Every time you apply to the diffmap, check that it doesn't conflict with the last ledger state. If it does, store the conflicting bundle in a temporary set you put aside. ~4. Overdraft handling: After you are done traversing the graph attempt to apply again the conflicting bundles. Remove the ones successfully applied from the set. Repeat this step until the size of the conflicting set stops changing.~

Implementation tips

For requirement 4, one can maybe use a negative snapshotIndex (make sure to use absolute value when reading it), or use the Bitmasks trick like we do in flags. This way we won't change the transaction schema.

[GalRogozinski]

I expect for people to drop comments here before implementing and adding to https://github.com/iotaledger/protocol-rfcs

[GalRogozinski]

On a research call we concluded that there is no need for taking care of temporary overdrafts. An important observation we made is that even though the current Ledger Service that calculates the balances allows overdrafts, the tip-selection algo doesn't allow it.

[GalRogozinski]

New Proposed algorithm

1. When a milestone comes in start traversing in DFS preferring trunk. Stop at the leafs (transactions that has only approved parents).
2. Start applying bundles to the diffmap only as you go up the recursion stack (when you climb up back from the leafs)
3. Every time you apply to the diffmap, check that it doesn't conflict with the last ledger state. If it does, mark the tx as conflicting and ignore it for the final balance calculations.

[muXxer]

IMHO we need a big change in the Coordinator. We need some kind of Merkle proof of all balances of all addresses that got changed in that milestone, including the proof of the last milestone. The First milestone after a global snapshot should contain all balances and addresses in this proof.

Otherwise we can't detect if we start with a malicious snapshot. The ledger states of the nodes would diverge with the new approach, without the proof.

In the current situation a node would simply not accept the milestone if balances would be spent that are not included in the malicious snapshot.

[GalRogozinski]

This is just white-flag issue without tip-selection or coordinator

What you said is also necessary but it is besides this specific issue

[DyrellC]

Make sure to account for the conflicting bundles with the checkConsistency calls

[acha-bill]

Proposed changes

For each tx traversed in postorder on the sub tangle, calculate the running consistency

//LedgerService.generateBalanceDiff
state = new map
traverse the sub tangle in postorder taking trunk first ending at leafs
    for each tvm
        bundle = bundle.validate(tangle, snapshot, tvm.hash)
        currentState = new map
        currentState.put(bundle.address, bundle.value)
        currentState.add(state) //merge previous state 
        isConsistent = snapshotProvider.getLatestSnapshot().patchedState(new SnapshotStateDiffImpl(currentState)).isConsistent();
        if(isConsitent)
            state = currentState
        else
            tvm.setIgnored(true); //sets that this tx was ignored
    return state

Since we already calculated the running consistency in generateBalanceDiff we don't check the consistency again in generateStateDiff

@GalRogozinski , Having a new flag is more explicit. Instead of messing with tx.snapshot where setting snapshot = -1 * milestoneIndex will mean it was ignored. If so, we would also have to check in MilstoneService.updateMilestoneIndexOfSingleTransaction, if tx was ignored, and enforce it again by resetting snapshot = -1 * index We will also have to remember to use abs for snapshot index.

[GalRogozinski]

yes @acha-bill, but if you have a flag it means you change the db schema again, which may cause you to break other stuff besides farther backwards compatibility (even though this change already breaks it)

Changing the schema will mean that IRI won't be able to load old txs properly... Not sure if it matters so much, depending on how we do the transition to white-flag (which I am not sure about completely)... Maybe @jakubcech knows?

However, if you use the flags field with a bitmask it may work well w.o changing the schema :-)

[jakubcech]

I'd explore the non-schema-altering options first :)

[acha-bill]

👍