Delayed state execution in practice

Sharding
,
2

I love the idea of fork choice rules for execution. :slight_smile: The portfolio of strategies for minimised onchain execution keeps expanding:

I’ve written your fork choice rule scheme below in my own words (skipping the cross-shard communication section for discussion in another post). It took me quite some time to digest your post and fill in detail that made sense to me. Did I get anything wrong below?

Construction

We have an Executor Manager Contract (EMC) in each child shard. The EMC is a “black box” contract where execution of the EMC is done via externally enshrined fork choice rules. The EMC mints ETH to reward executors.

The EMC has the following methods (mirroring those of the VMC):

  • deposit: Immediately adds an executor to the executor set and issues an ExecutorAdded log.
  • withdraw: Immediately removes an executor from the executor set and issues an ExecutorRemoved log. After a 4 months lock period the initial deposit plus rewards minus slashing is released.
  • addClaim: Takes a claim of the form [height, shard, prev_state_root, collation_hash, post_state_root, signature] and issues a ClaimAdded log. If the claim is valid and truthful then an ExecutorRewarded log is issued. If the claim is valid and untruthful then an ExecutorSlashed log is issued.

(Having logs is not strictly necessarily but helps the discussion below. It also helps light clients efficiently search for EMC events using the Bloom filter indexing of logs.)

A claim is valid if:

  1. The shard number matches that of the EMC.
  2. The collation_hash matches the collation header at the specified height.
  3. The signature is a valid signature from the executor set.

A claim is truthful if prev_state_root and post_state_root are the real state roots corresponding to the collation with hash collation_hash.

The EMC does not gate the submission of claims (addClaim always returns True) and has no notion of real state. Instead honest executors calculate the real state through offchain execution and use it to check the truthfulness of claims.

The valid (but not necessarily truthful) claims naturally form a directed and weighted graph, called the “claims graph”. The vertices are the state roots included in valid claims, and there’s a directed edge from prev_state_root to post_state_root with weight the sum of the corresponding claims. If all valid claims are also truthful then the claims graph forms a “claims chain” pointing from genesis to the real state root. If not, at least one of the depositors gets slashed and the real state is correspondingly updated.

Slashing happens as a fork choice rule by executors (not validators) within the EMC. So we have three nested fork choice rules:

  • miners choose block headers in the main shard
  • validators choose collation headers in the VMC
  • executors choose claims in the EMCs

Light clients can guess the real state following a GHOST-like protocol on the claims graph. For that they need to:

  1. filter out invalid claims, i.e. check the shard, height, collation_hash and signature of every claim
  2. know the weight of executors to apply the correct weighting to the claims graph

Filtering out invalid claims is the easy part. It assumes the availability of ExecutorAdded, ExecutorRemoved and ClaimAdded logs. These three logs readily derive from transactions that call the deposit, withdraw or addClaim method of the EMC.

Knowing the weight of executors is harder. First of all, the issuance of ExecutorRewarded versus ExecutorSlashed logs depends on prev_state_root and post_state_root matching the real state which light clients are trying to guess. Second, if slashing does occur then the claims graph needs to be retrospectively re-weighted, which itself affects the guessing process.

To address the inherent uncertainty around the issuance of ExecutorRewarded versus ExecutorSlashed logs, light clients use heuristics. They settle disagreements among executors at a vertex of the claims graph as follows:

  1. If the disagreement is over 10%, all claims are ignored until a valid proof of execution is verified, in which case the known-truthful claims are given a weight of infinity and the executors with known-untruthful claims are slashed.
  2. If there is no disagreement, or the disagreement is under 10%, light clients follow an optimistic strategy where they don’t do any slashing.

Initial questions and remarks

  1. Is the above description of the scheme correct?
  2. For light clients it seems the scheme depends on the historical availability of transactions that call the EMC, or at least the availability of the ExecutorAdded, ExecutorRemoved and ClaimAdded logs to filter out invalid claims. Is that right?
  3. For executors it seems that the EMC has “black box” state. Indeed, the EMC has implicit state (namely, the set of depositors and their weight) which is reflected in the state roots but never made explicit. It cannot be made explicit because the state transitions of the EMC for ExecutorRewarded and ExecutorSlashed logs is done with fork choice rules without explicit witness-bearing transactions. Does this bar new executors from joining the EMC without historical availability of the transactions (see the above point)? Maybe we can isolate the EMC’s state from the rest of the shard’s state somehow.
  4. Not only do light clients need to download and evaluate the ExecutorAdded, ExecutorRemoved and ClaimAdded logs, they also need to keep these in memory in order to allow for retrospective re-weighting if the optimistic strategy turns out to be wrong. Is that correct?