Coherence between state/storage updates in state circuit - MPT circuit

[ed255]

The EVM circuit tracks all accesses to the execution state that happen during a transaction via lookups to the rw_table in the state circuit. The only accesses that should be allowed are those tracked via the EVM circuit, so we must guarantee that the rw_table doesn't contain more entries than the ones in the EVM circuit.

To achieve this, the original design assigns a sequential counter to each rw access, and with it we can verify that the number of accesses in the EVM circuit and in the rw_table are the same. (this counter may be removed in favor of using the shuffle argument instead of lookups, which already guarantees that the items are the same in both sides).

A similar situation happens between the state circuit and the MPT circuit, which verifies the storage and state trie updates. We must guarantee that the MPT circuit doesn't do more updates than the ones tracked in the state circuit. To achieve this the current design defines the mpt_counter, which is a sequential counter used for each update from the state circuit, that is used to verify that the number of updates in the MPT circuit match.

Nevertheless a different design proposed by @han0110 is possible. Currently the updates in the MPT circuit are chained so that the prevUpdate.curStateRoot == curUpdate.prevStateRoot. The proposal consist of removing the chaining in the MPT circuit (so that each update in the MPT circuit is disconnected), and to track the state roots in the state circuit by adding the columns prevStateRoot and curStateRoot. The state circuit would guarantee that every storage/account update is chained via the prevStateRoot and curStateRoot and then expose the prevStateRoot of the first update and the curStateRoot of the last update as public inputs (in order to verify that they match with prevBlock.StateRoot and curBlock.StateRoot). This change would require adding the prevStateRoot and curStateRoot in the MPT lookup table. Following this approach removes the need to have the mpt_counter, which should simplify the design and implementation.

So the MPT lookup would change from

lookup(counter, target, address, key, value, value_prev)

to

lookup(target, address, key, value, value_prev, root, root_prev)

@miha-stopar What do you think about this proposal?

[miha-stopar]

From MPT circuit perspective this is even easier and at first I thought we will have something like this, but then I got the impression we would better like not to have these intermediate state roots in the state circuit? But yes, MPT can be quickly changed according to the proposal.

[z2trillion]

Mostly for my understanding, I've tried to synthesize @han0110's proposal with the option 2 from #200 (comment) and came up with this:

From privacy-scaling-explorations/zkevm-circuits#591, we add commited_value and value_prev advice columns with these constraints:

• committed_value = value_prev for a first access.
• prev_value = value when is_write is false.

We also add two advice columns, old_root and new_root, to the state circuit with the following constraints:

• old_root = prevBlock.StateRoot for the first row of the state circuit.
• old_root = new_root when the doesn't match match Account or AccountStorage or the row matches Account or AccountStorage but isn't a last access.
• new_root = curBlock.StateRoot for the last row of the state circuit.

(It's possible that we can elminate the prev_value and old_root advice columns and calculate their values from expressions, but we can optimize them away later.)

When

rw = Rw::AccountStorage {
  rw_counter,
  is_write,
  address,
  key,
  value,
  value_prev,
  tx_id,
  committed_value,
}

is the last access to (tx_id, address, key) in the block (as determined by the rw_counter), then the state circuit does

MptAccountStorageLookup {address, key, commited_value, value,  old_root, new_root}

which proves that updating commited_value at slot (address, key) to value changes the root from old_root to new_root.

For rw = Rw::Account {..} things are similar, except that we don't need to keep track of commited_value, so there's we only need one MptAccountLookup per (address, field_tag) per block instead of per tx.

With these, the state circuit proves that curBlock.StateRoot is obtained from prevBlock.StateRoot by a known sequence of updates, so we don't need the mpt_counter to ensure that there aren't extra updates in the mpt circuit.

The main thing that's missing in the state circuit for this is the sequence of intermediate state roots. Does the MPT circuit have access to these already?

@han0110, @ed255 , @miha-stopar, does my description here match what you guys have in mind?

[CPerezz]

I'm unsure if we want to reduce the lookup size. But note that we can RLC the prev_values with the curr ones.

So from:
lookup(target, address, key, value, value_prev, root, root_prev)
We go to:
lookup(target, address, key, RLC(value, value_prev, root, root_prev))
Or:
lookup(target, address, key, RLC(value, value_prev), RLC(root, root_prev))
If we're already dependant on Randomness via query_challenge API, include it should not be an issue + we reduce the shuffles we have to do in the lookup table by 4 in the most extreme case or by 2 in the conservative one. And int only comes at the cost of checking the RLC correctness of the 4 elements.

Not sure if it's worth TBH. But just leaving the thought here.

[miha-stopar]

The main thing that's missing in the state circuit for this is the sequence of intermediate state roots. Does the MPT circuit have access to these already?

Yes, intermediate state roots are returned by MPT witness generator together with other witness data.

[han0110]

@z2trillion The lookup process described here is exactly what I imagined! Also:

(It's possible that we can elminate the prev_value and old_root advice columns and calculate their values from expressions, but we can optimize them away later.)

My thought was to get rid of them in the beginning (less column and less constraint), but I realized it might be related to how we aggregate different circuits together, so I also think it's make more sense to keep them now.

[ed255]

@han0110, @ed255 , @miha-stopar, does my description here match what you guys have in mind?

Your description matches exactly the way I have in mind :)

The main points for me are:

1. Track the roots in the state circuit to remove the need for the MPT counter.
2. Do a single MPT lookup for N storage updates with same (tx_id, address, key) or M account updates with same (address, tag).

[z2trillion]

I'm unsure if we want to reduce the lookup size. But note that we can RLC the prev_values with the curr ones.

So from: lookup(target, address, key, value, value_prev, root, root_prev) We go to: lookup(target, address, key, RLC(value, value_prev, root, root_prev)) Or: lookup(target, address, key, RLC(value, value_prev), RLC(root, root_prev)) If we're already dependant on Randomness via query_challenge API, include it should not be an issue + we reduce the shuffles we have to do in the lookup table by 4 in the most extreme case or by 2 in the conservative one. And int only comes at the cost of checking the RLC correctness of the 4 elements.

Not sure if it's worth TBH. But just leaving the thought here.

@lispc had proposed (#210 (comment)) RLC'ing all the columns of a lookup together by default. In this case,

MptAccountStorageLookup {address, key, commited_value, value,  old_root, new_root} = 
  Lookup(RLC(address, key, commited_value, value,  old_root, new_root))

Is that no longer the plan, if it ever was?

[z2trillion]

I made a draft PR adding mpt lookups to the state circuit: privacy-scaling-explorations/zkevm-circuits#621.

[ed255]

Specs PR for this #236