Re-rooting the state of a block

[rphmeier]

Substrate chains may occasionally need to do state rollbacks.
In Polkadot, that's the case when we have a fully-malicious validator committee whose misbehavior is discovered.

We introduce ext_reroot(ancestor: BlockNumber) -> Hash for this purpose.
This will set the current storage to be equal to the post-state of the ancestor of the current block with the given block number.

Some pseudocode for an implementation:

// substrate-executor
fn ext_reroot(ancestor: BlockNumber) -> Hash {
    ext.reroot(ancestor);
}

// substrate-state-machine

struct Ext<'a, B: 'a + Backend> {
     backend: Cow<'a, B>,
     prospective: &'a mut OverlayedChanges,
     // ...
}

impl Ext {
    fn reroot(number: BlockNumber) {
        // prospective is an overlay of all storage items changed so far within the runtime execution
        // of the block.
        prospective.clear();
        if current_number <= ancestor { trap() }
        self.backend = Cow::Owned(self.backend.reroot(number));
    }
}

struct TrieBackend {
    fn reroot(&self, number) -> TrieBackend {
        let db_overlay = MemoryDB::new();   

        // reverse, inserting all deletions of ancestors and deleting all insertions.
        for (num, hash) in ancestry_iter(parent_hash) {
            if num == ancestor { break }
            let pruning_record = db.pruning_record(hash);
            for (inserted_key, _val) in pruning_record.insertions {
                db_overlay.remove(&inserted_key); // undo an insertion.
            }

            // values might not actually be available in the current implementation of pruning.
            // but the value should still be available within the DB because we are assuming this block hasn't been canonicalized yet (so deletions haven't been applied yet).
            for (_deleted_key, val) in pruning_record.deletions {
                db_overlay.insert(val); // undo a deletion.
            }
        };

        
        // we used a memorydb for `db_overlay` because it's very likely that many of the storage operations cancel out.
        // now, we have to make sure that the `update` produced by `Backend::root` and passed to `client::BlockImportOperation::update_storage` is based on top of the `db_overlay`, but still includes any further deltas.
    }
}

I would expect that most of this implementation is within state_machine::Ext and state_machine::Backend. Ext needs to clear the prospective overlay, and we would make the backend field on Ext into a Cow. Backend gets a new Backend::reroot(new_number) -> Self. For the trie implementation, this would do all of the pruning-overlay logic mentioned above, and create a new Backend with the new state root and a pre-update to apply the del

This won't play that nicely with the storage changes root or light clients for consensus. What we can do is introduce a special storage changes root digest which says "everything changed". To maintain good light client compatibility on the consensus layer, the caller of this function should force-issue a change digest to the same set as is currently enabled afterwards.

[arkpar]

Implementation would also need to clear shared state cache on commit.

[cheme]

I started looking at this issue, it seems to me that it is a bit impactfull when considering the current api/design.

Main point being that at this time, state-machine and Externalities implementation (Ext) are not aware of the chain history (all is defined at for a given block state).

core/client seems to be currently the first place where querying chain ancestry is possible.

I can think of two ways of doing things:

• put a reference to client in Ext, then the prototype implementation shall be possible. It feels like this broke general state-machine and externalities trait design.
  The rebuild of backend also need a way to do it (associated type builder from trie root), I wonder if going this way may endup in the definition of a new trait (implemented over client) for externalities that involve blockchain access (probably only read only operation except cache related things). But going that way it is not super clear if current abstraction keep a sense.

• make reroot an information that is returned to upper client layer and do actual reroot at the end of block import or at block finalization (in core/client). I started to do things this way, basically it involve many api breaking changes (blockbuilder, bake, finalize_block, call_at_state, storage_root): to return additional info (a possible reroot; can probably be extend to more use case) with the calculated state root.

Main issue here would be that we cannot have change over this previous block state in this block, but that is probably something good for all extrinsics others than the one calling reroot.

Now that I think of it, do we want to call reroot from an extrinsic evaluation ? That is something I infer from the use of state-machine but the real use case may be communication between srml module and core/client code.

[arkpar]

I suppose it's fine if it applied on block finalization. Much like code upgrade.

[rphmeier]

Yeah, that's fine.

@cheme It might become necessary to include a reference to client or the client-db somehow in externalities in order to implement this correctly. But if that is the case, we should do it via a trait that's implemented for Client higher up. I don't want direct references to Client polluting everything.

So the workflow for a chain would be something like:

• do ext_reroot
• make sure digests are issued that keep consensus etc. consistent
• disallow further extrinsics from being processed.

[rphmeier]

One other thing to note:

in a typical situation where we have to re-root the state of a block, we'll probably be performing some other state changes that should be applied beyond the revert. This includes e.g. slashing and disabling validators who voted on a thing in Polkadot, and recording the fact that they were slashed for that offence. Because of that, it might still be easier to re-root the block in the middle of the execution rather than wait til the end to do the re-root.

[cheme]

Could also be some additional 'payload' parameter to 'ext_reroot'.
Do we need to check those additional operation?
Checking reroot is legit is by checking that 'ext_root' get played with all associated onchain logic, but checking post reroot operations seems more difficult.
Edit: If I think of reroot as a similar action as code update, checking post reroot operation does not make to much sense.

[rphmeier]

I don't know what you mean by "check"ing those storage operations. Either the operation is done or it isn't. Those operations do need to be done though.

[cheme]

Sure, so if they fail we probably want to rollback/abort the reroot call.
It also seems to me that the next instruction after a reroot should not be possible on the rerooted state, so before running them we probably want to apply a small change on the rerooted state (like inserted a simple key/value indicating we are rerooting things).
Edit : things should necessarilly be able fail (with proper runtime code), and condition to activate changes are already checked before so if rerooting during the process (as stated in the description) things could be fine.

[rphmeier]

outdated