Reorgs and rewinding time

[Mirko-von-Leipzig]

Reorgs are not presently a concern for Miden, however we should begin exploring options for dealing with them.

Reorg causes

The main source of reorgs in blockchains are forks or disagreements in consensus. Miden is currently centralized and will be for quite some time still. We can (mostly) ignore this as an issue for now.

A more devious source of reorgs are bugs in any of the node components. As an example, a bug in the node might cause produced block proofs to be rejected by the L1 contract. This would then necessitate a "reorg" of the rejected blocks before the blockchain can progress. Similar things can happen with bugs or disagreements between any components. Miden proves a block before it publishes it which at least prevents reorg bugs between sequencer and prover.

Strategies

Irrespective of cause, we need some way to handle reorg situations. In the best case scenario, a node should handle a reorg by rolling back state and replaying the reorg'd transactions again.

Replaying transactions has its own issues, especially if the original cause was a bug. Post bugfix might now result in different outcomes, different state and some transactions now get rejected. Another problem is time - if transactions/code/notes rely on time in any capacity they'll now behave differently.

I imagine Miden's privacy also causes problems with replaying transactions, though I don't understand the machinery well enough to have well informed thoughts on this.

The simplest strategy is probably to rewind and drop the offending blocks.

[bobbinth]

The way things currently are, it would not be possible to replay transactions because by the time we insert a new block into the store almost all info about the transactions that went into it is erased. Specifically:

• All individual transaction proofs are discarded because the block's proof has recursively verified them - and so, having a block proof means that we've already checked the validity of all transaction proofs.
• Information about which transactions produced new notes or nullifiers is also erased. We know that the totality of all transactions in the block produced this set of notes and this set of nullifiers, but which transactions produced which is no longer identifiable.
• Information about "transient" notes (i.e., unauthenticated notes which are produced and consumed within the same batch) is also gone.

So, what we can presently do is roll back the chain to some prior state, but we would not be able to reapply any of the rolled-back transactions. To support this, we'd need to keep some kind of a transaction log - i.e., as soon as a transaction is accepted into the txpool, we also store it somewhere in its entirety (this data store can be pruned regularly and, overall, can probably store transaction data covering relatively short span of time). This is distinct but maybe related to #23.