binius_circuits/ecdsa/
bitcoin.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},
9	util::all_true,
10};
11
12/// "Bitcoin style" verification of ECDSA signatures over secp256k1
13///
14/// # Arguments
15/// * `pk` - public key, a curve point in affine representation, asserted to be a valid curve point
16/// * `z`  - hash of signed message as an integer
17/// * `r`  - R part of the signature, the x coordinate of the nonce point
18/// * `s`  - S part of the signature
19///
20/// # Assertions
21/// The public key `pk` is asserted to be a valid curve point
22///
23/// # Outputs
24/// A boolean wire equal to all-1 if the signature is valid, all-0 otherwise.
25pub fn verify(
26	b: &CircuitBuilder,
27	pk: Secp256k1Affine,
28	z: &BigUint,
29	r: &BigUint,
30	s: &BigUint,
31) -> Wire {
32	let curve = Secp256k1::new(b);
33
34	// secp256k1 is cofactor-1 and PAI is not on it.
35	curve.assert_on_curve(b, &pk);
36
37	let f_scalar = curve.f_scalar();
38
39	let valid_r = b.band(b.bnot(r.is_zero(b)), biguint_lt(b, r, f_scalar.modulus()));
40	let valid_s = b.band(b.bnot(s.is_zero(b)), biguint_lt(b, s, f_scalar.modulus()));
41
42	// u1 = z / s, u2 = r / s. `div` requires reduced dividends: `z` (the message hash) and
43	// `r` must be in `[0, n)`. `valid_s` gates the shared divisor `s`.
44	let u1 = f_scalar.div(b, z, s, valid_s);
45	let u2 = f_scalar.div(b, r, s, valid_s);
46
47	// Recover the candidate nonce point as the multi-scalar multiplication `u1*G + u2*PK`.
48	let g = Secp256k1Affine::generator(b);
49	let nonce = msm_strauss_endo(b, &curve, MSM_WINDOW, &[u1, u2], &[g, pk]);
50	let nonce_not_pai = b.bnot(nonce.is_point_at_infinity);
51	let r_diff = curve.f_p().sub(b, &nonce.x, r);
52
53	let conditions = [valid_r, valid_s, nonce_not_pai, r_diff.is_zero(b)];
54	all_true(b, conditions)
55}
binius_circuits/ecdsa/bitcoin.rs

binius_circuits/ecdsa/
bitcoin.rs
