binius_circuits/ecdsa/
ecrecover.rs

1// Copyright 2026 The Binius Developers
2// Copyright 2025 Irreducible Inc.
3use binius_frontend::{CircuitBuilder, Wire};
4
5use super::scalar_mul::{MSM_WINDOW, msm_strauss_endo};
6use crate::{
7	bignum::{BigUint, biguint_lt},
8	secp256k1::{Secp256k1, Secp256k1Affine, coord_zero},
9	util::all_true,
10};
11
12/// EcRecover - an "Ethereum-style" verification of ECDSA signatures over secp256k1.
13///
14/// # Arguments
15/// * `z`         - hash of the signed message as an integer
16/// * `r`         - R part of the signature, the x coordinate of the nonce point
17/// * `s`         - S part of the signature
18/// * `recid_odd` - parity flag of the y coordinate of the assumed nonce point R with R.x = r; note
19///   that we do not support `r` being greater or equal than the scalar field modulus, and thus only
20///   need parity; some implementations assume 0-3 bitmask which encodes both y parity and r scalar
21///   field overflow, but that's not needed for Ethereum.
22///
23/// # Outputs
24/// The recovered public key `pk` in affine form.
25pub fn ecrecover(
26	b: &CircuitBuilder,
27	z: &BigUint,
28	r: &BigUint,
29	s: &BigUint,
30	recid_odd: Wire,
31) -> Secp256k1Affine {
32	let curve = Secp256k1::new(b);
33
34	let nonce = curve.recover(b, r, recid_odd);
35	let nonce_not_pai = b.bnot(nonce.is_point_at_infinity);
36
37	let f_scalar = curve.f_scalar();
38	let valid_r = b.band(b.bnot(r.is_zero(b)), biguint_lt(b, r, f_scalar.modulus()));
39	let valid_s = b.band(b.bnot(s.is_zero(b)), biguint_lt(b, s, f_scalar.modulus()));
40
41	// u1 = -(z / r), u2 = s / r. `div` requires reduced dividends: `z` (the message hash)
42	// and `s` must be in `[0, n)`. `valid_r` gates the shared divisor `r`.
43	let u1 = f_scalar.sub(b, &coord_zero(b), &f_scalar.div(b, z, r, valid_r));
44	let u2 = f_scalar.div(b, s, r, valid_r);
45
46	// Recover the public key as the multi-scalar multiplication `u1*G + u2*R`.
47	let g = Secp256k1Affine::generator(b);
48	let recovered_pk = msm_strauss_endo(b, &curve, MSM_WINDOW, &[u1, u2], &[g, nonce]);
49
50	let conditions = [valid_r, valid_s, nonce_not_pai];
51	recovered_pk.pai_unless(b, all_true(b, conditions))
52}
binius_circuits/ecdsa/ecrecover.rs

binius_circuits/ecdsa/
ecrecover.rs
