feat: differentiate ecrecover with strict and lax check for s

[ivokub]

Ethereum Yellow paper defines two initial conditions for ECRecover:

• in case of checking transaction signatures, s should be s < N+2 + 1
• in case of ECREC precompile, s should be s < N.

This PR updates the current precompile method which takes additional variable which defines the upper bound to compare s against. Also added test cases (strict check, lax check, assumed failure).

This is based on top of fix/ecdsa-v which depends on update in gnark-crypto. So have to wait for other PRs being merged before can merge this one.

CC: @AlexandreBelling, @OlivierBBB -- can you confirm this behaviour is good?

[yelhousni]

• in case of checking transaction signatures, s should be s < N+2 + 1

I assume you mean s < N/2 + 1?

[ivokub]

• in case of checking transaction signatures, s should be s < N+2 + 1

I assume you mean s < N/2 + 1?

Yes! Sorry, my typo.

[yelhousni]

I think 01-ecrecover.go should exclude the bounds checks on s and r as these are done on the zkEVM arithmetization side to avoid junk calls https://github.com/ConsenSys/zkevm-spec/issues/50

[ivokub]

I think 01-ecrecover.go should exclude the bounds checks on s and r as these are done on the zkEVM arithmetization side to avoid junk calls ConsenSys/zkevm-spec#50

I would also avoid, but there is a gotcha. This primitive is used in two places - first by the arithmetization when ECRECOVER precompile is called and second to verify the validity of the transaction.

For the first case it is obvious that it would be better to perform the check on the arithmetization side to avoid calling the circuit. But for the second case the check is done by the prover directly on the block data without passing to arithmetization. And there it may be better if we do the check on our side (I'm not fully sure, @AlexandreBelling can confirm?).

Now, we have two options - either implement two different circuits where in one we do not check s (for calling precompile in arithmetization) and in the second one we do (for prover verifying transaction signature). Or we have only a single circuit with a selector to select the bound we check s against. For simplicity I went for a single-circuit route.

[ivokub]

So, I asked @AlexandreBelling, and as far as I understood then there is a fixed amount of ECRecover calls within a block. Having a single circuit allows to allocate these calls more efficiently between transaction verification and calling ECREC precompile. So the recommendation was to have a single circuit, even if when calling precompile we perform additional check on s.

[yelhousni]

Ok single-circuit then! Now either we'll duplicate arithmetization checks on s or remove them from the arithmetization side. I would choose the duplication option (cc @OlivierBBB).