Open ed255 opened 2 years ago
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.
Mostly for my understanding, I've tried to synthesize @han0110's proposal with the option 2 from https://github.com/privacy-scaling-explorations/zkevm-specs/pull/200#issuecomment-1144667560 and came up with this:
From https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/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?
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.
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.
@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.
@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:
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 (https://github.com/privacy-scaling-explorations/zkevm-specs/pull/210#issuecomment-1152323592) 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?
I made a draft PR adding mpt lookups to the state circuit: https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/621.
Specs PR for this https://github.com/privacy-scaling-explorations/zkevm-specs/pull/236
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 therw_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 columnsprevStateRoot
andcurStateRoot
. The state circuit would guarantee that every storage/account update is chained via theprevStateRoot
andcurStateRoot
and then expose theprevStateRoot
of the first update and thecurStateRoot
of the last update as public inputs (in order to verify that they match withprevBlock.StateRoot
andcurBlock.StateRoot
). This change would require adding theprevStateRoot
andcurStateRoot
in the MPT lookup table. Following this approach removes the need to have thempt_counter
, which should simplify the design and implementation.So the MPT lookup would change from
to
@miha-stopar What do you think about this proposal?