ecRecover stalling over test from Ethereum Execution Spec Test

[advaita-saha]

While integrating constantine as a backend for evm precompiles in nimbus-eth1 it was tested against the latest EEST release. And for a particular test, the eth_evm_ecrecover stalls. More details -> status-im/nimbus-eth1#3587 (comment)

Upon further debugging, the exact input value which was stalling the eth_evm_ecrecover was found to be 18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c000000000000000000000000000000000000000000000000000000000000001c00b1693892219d736caba55bdb67216e485557ea6b6af75f37096c9aa6a5a75feeb940b1d03b21e36b0e47e79769f095fe2ab855bd91e3a38756b7d75a9c4549

A sample test case to re-produce the same

proc testECRecoverStall() =
  echo "Running ecRecover tests for stalling"
  
  let input = "18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c000000000000000000000000000000000000000000000000000000000000001c00b1693892219d736caba55bdb67216e485557ea6b6af75f37096c9aa6a5a75feeb940b1d03b21e36b0e47e79769f095fe2ab855bd91e3a38756b7d75a9c4549"

  var inputbytes = newSeq[byte](input.len div 2)
  inputbytes.fromHex(input)

  var r: array[32, byte]

  let status = eth_evm_ecrecover(r, inputbytes)
  echo "Run Completed"
  echo status

[mratsim]

Tested without Crandall and endomorphism acceleration just in case, they are not the issue.

The code is stuck in the pubkey recover loop:

constantine/constantine/signatures/ecdsa.nim

Lines 341 to 383 in c6097d7

	# Due to the conversion of the `x` coordinate in `Fp` of the point `R` in the signing process
	# to a scalar in `Fr`, we potentially reduce it modulo the curve order (if `x >= r` with
	# `r` the curve order).
	# As we don't know if this is the case, we need to loop until we either find a valid signature,
	# adding `M` each iteration or until we roll over again, in which case the signature is invalid.
	# NOTE: For secp256k1 this is _extremely_ unlikely, because prime of the curve `p` and subgroup
	# order `r` are so close!
	var validSig = false
	while (not validSig) and bool(x1.toBig() <= rInit):
	# 1. Get base `R` point
	var R {.noinit.}: EC_ShortW_Aff[Fp[Name], G1]
	let valid = R.trySetFromCoordX(x1) # from `r = x1`
	if not bool(valid):
	x1 += M # add modulus of `Fr`. As long as we don't overflow in `Fp` we try again
	continue # try next `i` in `x1 = r + i·M`
	let isEven = R.y.toBig().isEven()
	# 2. only negate `y ↦ -y` if current and target even-ness disagree
	R.y.cneg(isEven xor SecretBool evenY)
	# 3. perform recovery calculation, `Q = -m·r⁻¹ * G + s·r⁻¹ * R`
	# Note: Calculate with `r⁻¹` included in each coefficient to avoid 3rd `scalarMul`.
	var rInv = signature.r
	rInv.inv() # `r⁻¹`
	var u1 {.noinit.}, u2 {.noinit.}: Fr[Name]
	u1.prod(msgHash, rInv) # `u₁ = m·r⁻¹`
	u1.neg() # `u₁ = -m·r⁻¹`
	u2.prod(signature.s, rInv) # `u₂ = s·r⁻¹`
	var Q {.noinit.}: ECJac # the potential public key
	var point1 {.noinit.}, point2 {.noinit.}: ECJac
	point1.scalarMul(u1, G) # `p₁ = u₁ * G`
	point2.scalarMul(u2, R) # `p₂ = u₂ * R`
	Q.sum(point1, point2) # `Q = p₁ + p₂`
	# 4. Verify signature with this point
	validSig = Q.getAffine().verifyImpl(signature, msgHash)
	# 5. If valid copy to `recovered`, else keep neutral point
	recovered.ccopy(Q.getAffine(), SecretBool validSig) # Copy `Q` if valid
	# 6. try next `i` in `x1 = r + i·M`
	x1 += M

From the comment

As we don't know if this is the case, we need to loop until we either find a valid signature,
adding M each iteration or until we roll over again, in which case the signature is invalid.
NOTE: For secp256k1 this is extremely unlikely, because prime of the curve p and subgroup
order r are so close!

my initial assumption was that fuzzing found a x that forced the rollover and the condition bool(x1.toBig() <= rInit) is true if there is a rollover to around 0. cc @Vindaar

Do you have some history on the test? I assume it comes from https://github.com/ethereum/execution-spec-tests/tree/main/tests/static/state_tests/stPreCompiledContracts2

[advaita-saha]

Do you have some history on the test?

Not at the moment, but digging up more details on the test case
These tests come to us as blocks, and not precompile test vectors, so a little backtrace to do, not very straightforward