optim/best-degree: set the optimal gate degree

[naure]

The gate degree of the EVM circuit is currently 7. This is set by the gate "Constrain state machine transitions". However, the constraint builder limits other gates to 6 instead of 7. The parameters and the comment seem outdated.

Meanwhile, 7 is a poor trade-off. The next threshold is 9, which is chosen in this PR.

The effective degree of gadgets goes from 2 to 5. This will reduce the usage of cells for stored expressions. This, in turn, allows someone to simply configure fewer "Storage" columns, saving verifier time.

Stats!

• The gate complexity is down 17% (from 10623 to 8838). This is measured as the count of multiplications, after memoizing. This is the bottleneck in prover time.

Observing the stored expressions of some individual states:

• CALLDATALOAD is no longer the largest instruction. It uses ~2X fewer stored expressions, moving to its next bottleneck at a lower height.
• PUSH -68%. MEMORY -63%. SIGNEXTEND -51%. MUL -20%. ADD -12%. BITWISE -10%.

Data using #863 -- Before -- After.

[ed255]

Thanks for the analysis! The EVM circuit degree was recently increased in this PR https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/718 where I explain a bit the rationale behind going to a non-optimal gate degree: the plan is to reduce 1 degree once we remove the blinding factors by removing the q_usable selector from the expressions.

Nevertheless I thought that the current max gate degree in EVM was 6: 5 + 1. If it's 7, even if we reduce 1 degree by removing q_usable we're still at extended k = 3. I've checked where the 7 comes from and found the reason (I introduced that extra +1 as well): https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/b87a9d2a08d88cd9d04ba64a5e7ca3c7f6e34471/zkevm-circuits/src/evm_circuit/execution.rs#L687-L691

The degrees are:

• q_usable: 1
• q_step: 1
• (1 - q_step_last): 1
• execution_state_selector: 2
• poly: 2

I guess we could find a creative way bring the degree down (like adding an extra column to hold q_step * (1 - q_step_last).

In summary: the current degree was supposed to be temporary and we were aiming for degree 5 in the mid-term. We may decide to go to degree 9 but we need to consider the proving performance implications.

[naure]

Couldn’t instead q_step be constrained by q_usable?

if q_usable == 0 then q_step = 0

Then q_usable won’t need to multiply all gates because q_step is already doing it.

[ed255]

Couldn’t instead q_step be constrained by q_usable?

if q_usable == 0 then q_step = 0

Then q_usable won’t need to multiply all gates because q_step is already doing it.

Yes! That would work and we'd remove q_usable with it. Now we only need to remove one more factor to get the degree at 5. If we can turn q_step * (1 - q_step_last) into an expression of degree 1 that would do it. Currently we need a way to distinguish all the steps from the last one because all steps must enforce a correct transition to the next one, except for the last (which doesn't have a next step). Maybe we could have an extra EndBlock after the last EndBlock with q_usable = 0, q_step = 0 so that the last step can have transition constraints to the next fulfilled? Then we'd remove 1 - q_step_last from the expression, and enable the EndBlock transition constrains in all steps.

Having said that, I'm afraid at some point we may need to have constraints that not "stateless" enforced in the last EndBlock, like sending a reward to the miner (which increases the rwc), although... we could have multiple EndBlocks doing that as long as we don't force an rwc increase for the next step (they would just verify the same state change over and over, using the same rwc values in the lookups in each EndBlock step).

@han0110 what do you think about this? Is the idea clear?

[han0110]

Couldn’t instead q_step be constrained by q_usable?

if q_usable == 0 then q_step = 0

Then q_usable won’t need to multiply all gates because q_step is already doing it.

This should be possible and desirable when we remove the blinding factor.

Adding an extra column to hold q_step * (1 - q_step_last).

This seems could be temporary solution for now.

[ChihChengLiang]

Hi, @naure @ed255 @han0110 what's the status of this PR? Does anything need more clarification?

[ed255]

@icemelon could you do a second review to this PR? It's a small change that gives some performance benefits (and I think it's useful for the time until we bring constraint the degree down to 5)

[CPerezz]

I did not notice that this was assigned to me apologies!!! Let me know if you still want me to look at this!

[aguzmant103]

@naure just doing a ping as I think there are some open comments to solve before getting this to merge

[aguzmant103]

Applying the "won'tfix" label now because this optimization is not required now, but we can reconsider it once this optimization becomes more critical.

[leolara]

@aguzmant103 I close it then