Execute Reorg

[capossele]

Reorg is the reorganization of a node's perception of the ledger state, and, thus, also the tangle and branches. It is necessary when a node temporarily comes to the wrong conclusion, e.g., due to being eclipsed, while syncing, as to what – more specifically, which conflict of a conflict set and its future cone aka branch – is confirmed. As such, the necessity of a reorg operation can be detected easily: a branch that was rejected becomes confirmed.

Currently, we always create a new branch for each arriving conflict (an exception is the case where a conflicting transaction arrives but the existing transaction is already confirmed, then we lazy book) and never clean up the BranchDAG. This leads to an ever-growing (wide and deep) BranchDAG and eventually performance degradation of algorithms since we need to walk the BranchDAG frequently. Therefore, we need to "clean up" branches on confirmation, while keeping their rejected branches around "for a while" (e.g. until snapshotting = partition tolerance) to track approval weight in case a future reorg becomes necessary.

Consider the following example of the green and red conflicts.

The green branch is gaining enough approval weight and therefore merged into master. Everything that arrives now building on top of the red, blue, or purple branch will be lazy booked since the green one has already been confirmed and merged to master.

If for some reason, now the red branch gains enough approval weight so that it should become confirmed, a reorg is necessary. We then need to reintroduce the green branch (that was previously merged into master), outputs, transactions and messages in this branch as not final. Everything that is lazily booked on top of the red branch needs to be booked as well and with it the tips adjusted (that should happen automatically when booking, except for the weak tips).

The local opinion of a node might need to be updated as well depending on the approach we're taking overall: either we poll the local opinion when issuing a message or we keep track of the local opinion all the time. In the latter the opinion needs to be updated accordingly.