acvm_blackbox_solver/ecdsa/
secp256k1.rs

1use acir::BlackBoxFunc;
2
3use k256::{
4    AffinePoint, ProjectivePoint, PublicKey,
5    elliptic_curve::{
6        PrimeField,
7        ops::Reduce,
8        scalar::IsHigh,
9        sec1::{Coordinates, FromSec1Point, Sec1Point, ToSec1Point},
10    },
11};
12use k256::{Scalar, ecdsa::Signature};
13
14use crate::BlackBoxResolutionError;
15
16/// Verifies an ECDSA signature over the Secp256k1 elliptic curve.
17///
18/// This function implements ECDSA signature verification on the Secp256k1 curve
19///
20/// # Parameters:
21///
22/// * `hashed_msg` - The 32-byte hash of the message that was signed
23/// * `public_key_x_bytes` - The x-coordinate of the public key (32 bytes, big-endian)
24/// * `public_key_y_bytes` - The y-coordinate of the public key (32 bytes, big-endian)
25/// * `signature` - The 64-byte signature in (r, s) format, where r and s are 32 bytes each
26///
27/// Returns `true` if the signature is valid, `false` otherwise.
28///
29/// The function does not validate a signature if any of the following are true:
30/// - The signature is not "low S" normalized per BIP 0062 to prevent malleability
31/// - The signature components `r` and `s` is zero
32/// - The public key point is not on the Secp256k1 curve
33///
34/// If `hashed_msg >= k256::Secp256k1::ORDER`, the message hash is reduced modulo the curve
35/// order per ECDSA specification (SEC 1, section 4.1.4).
36pub(super) fn verify_signature(
37    hashed_msg: &[u8; 32],
38    public_key_x_bytes: &[u8; 32],
39    public_key_y_bytes: &[u8; 32],
40    signature: &[u8; 64],
41) -> Result<bool, BlackBoxResolutionError> {
42    // Convert the inputs into k256 data structures
43    let Ok(signature) = Signature::try_from(signature.as_slice()) else {
44        // Signature `r` and `s` are forbidden from being zero.
45        log::warn!("Signature provided for ECDSA verification is zero");
46        return Ok(false);
47    };
48
49    let point = Sec1Point::<k256::Secp256k1>::from_affine_coordinates(
50        public_key_x_bytes.into(),
51        public_key_y_bytes.into(),
52        false,
53    );
54
55    let pubkey = PublicKey::from_sec1_point(&point);
56    if pubkey.is_none().into() {
57        // Public key must sit on the Secp256k1 curve.
58        log::warn!("Invalid public key provided for ECDSA verification");
59        return Ok(false);
60    }
61    let pubkey = pubkey.unwrap();
62
63    // Convert the hashed message to a scalar.
64    // Per ECDSA specification (SEC 1, section 4.1.4), if `hashed_msg >= k256::Secp256k1::ORDER`,
65    // the message hash should be reduced modulo the curve order.
66    let z = <Scalar as Reduce<k256::U256>>::reduce(&k256::U256::from_be_slice(hashed_msg));
67
68    // Finished converting bytes into data structures
69
70    let r = signature.r();
71    let s = signature.s();
72
73    // Ensure signature is "low S" normalized ala BIP 0062
74    if s.is_high().into() {
75        log::warn!(
76            "Signature provided for ECDSA verification is not properly normalized (high S value)"
77        );
78        return Ok(false);
79    }
80
81    let s_inv = s.invert().unwrap();
82    let u1 = z * s_inv;
83    let u2 = *r * s_inv;
84
85    #[allow(non_snake_case)]
86    let R: AffinePoint = ((ProjectivePoint::GENERATOR * u1)
87        + (ProjectivePoint::from(*pubkey.as_affine()) * u2))
88        .to_affine();
89
90    // Compare R.x with signature's r component.
91    match R.to_sec1_point(false).coordinates() {
92        Coordinates::Uncompressed { x, y: _ } => {
93            // The conversion from R.x to a scalar can fail if R.x >= curve_order (a possible but rare case).
94            // In this case, the signature is invalid per ECDSA specification, so we return false.
95            // The prover will handle this gracefully - it should generate a proof that fails verification.
96            Ok(Scalar::from_repr(*x).into_option().map_or_else(
97                || {
98                    log::warn!(
99                        "ECDSA Secp256k1 verification: R.x coordinate exceeds scalar field order - signature is invalid"
100                    );
101                    false
102                },
103                |scalar| scalar == *r,
104            ))
105        }
106        Coordinates::Identity => Ok(false),
107        _ => Err(BlackBoxResolutionError::Failed(
108            BlackBoxFunc::EcdsaSecp256k1,
109            "Unexpected coordinate encoding".to_string(),
110        )),
111    }
112}
113
114#[cfg(test)]
115mod secp256k1_tests {
116    use super::verify_signature;
117
118    // 0x3a73f4123a5cd2121f21cd7e8d358835476949d035d9c2da6806b4633ac8c1e2,
119    const HASHED_MESSAGE: [u8; 32] = [
120        0x3a, 0x73, 0xf4, 0x12, 0x3a, 0x5c, 0xd2, 0x12, 0x1f, 0x21, 0xcd, 0x7e, 0x8d, 0x35, 0x88,
121        0x35, 0x47, 0x69, 0x49, 0xd0, 0x35, 0xd9, 0xc2, 0xda, 0x68, 0x06, 0xb4, 0x63, 0x3a, 0xc8,
122        0xc1, 0xe2,
123    ];
124    // 0xa0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7
125    const PUB_KEY_X: [u8; 32] = [
126        0xa0, 0x43, 0x4d, 0x9e, 0x47, 0xf3, 0xc8, 0x62, 0x35, 0x47, 0x7c, 0x7b, 0x1a, 0xe6, 0xae,
127        0x5d, 0x34, 0x42, 0xd4, 0x9b, 0x19, 0x43, 0xc2, 0xb7, 0x52, 0xa6, 0x8e, 0x2a, 0x47, 0xe2,
128        0x47, 0xc7,
129    ];
130    // 0x893aba425419bc27a3b6c7e693a24c696f794c2ed877a1593cbee53b037368d7
131    const PUB_KEY_Y: [u8; 32] = [
132        0x89, 0x3a, 0xba, 0x42, 0x54, 0x19, 0xbc, 0x27, 0xa3, 0xb6, 0xc7, 0xe6, 0x93, 0xa2, 0x4c,
133        0x69, 0x6f, 0x79, 0x4c, 0x2e, 0xd8, 0x77, 0xa1, 0x59, 0x3c, 0xbe, 0xe5, 0x3b, 0x03, 0x73,
134        0x68, 0xd7,
135    ];
136    // 0xe5081c80ab427dc370346f4a0e31aa2bad8d9798c38061db9ae55a4e8df454fd28119894344e71b78770cc931d61f480ecbb0b89d6eb69690161e49a715fcd55
137    const SIGNATURE: [u8; 64] = [
138        0xe5, 0x08, 0x1c, 0x80, 0xab, 0x42, 0x7d, 0xc3, 0x70, 0x34, 0x6f, 0x4a, 0x0e, 0x31, 0xaa,
139        0x2b, 0xad, 0x8d, 0x97, 0x98, 0xc3, 0x80, 0x61, 0xdb, 0x9a, 0xe5, 0x5a, 0x4e, 0x8d, 0xf4,
140        0x54, 0xfd, 0x28, 0x11, 0x98, 0x94, 0x34, 0x4e, 0x71, 0xb7, 0x87, 0x70, 0xcc, 0x93, 0x1d,
141        0x61, 0xf4, 0x80, 0xec, 0xbb, 0x0b, 0x89, 0xd6, 0xeb, 0x69, 0x69, 0x01, 0x61, 0xe4, 0x9a,
142        0x71, 0x5f, 0xcd, 0x55,
143    ];
144
145    #[test]
146    fn verifies_valid_signature_with_low_s_value() {
147        let valid = verify_signature(&HASHED_MESSAGE, &PUB_KEY_X, &PUB_KEY_Y, &SIGNATURE).unwrap();
148
149        assert!(valid);
150    }
151
152    #[test]
153    fn signature_does_not_verify_on_signature_that_does_not_have_the_full_y_coordinate() {
154        let mut pub_key_y_bytes = [0u8; 32];
155        pub_key_y_bytes[31] = PUB_KEY_Y[31];
156
157        let result =
158            verify_signature(&HASHED_MESSAGE, &PUB_KEY_X, &pub_key_y_bytes, &SIGNATURE).unwrap();
159        assert!(!result);
160    }
161
162    #[test]
163    fn signature_does_not_verify_on_invalid_signature() {
164        // This signature is invalid as ECDSA specifies that `r` and `s` must be non-zero.
165        let invalid_signature: [u8; 64] = [0x00; 64];
166
167        let result =
168            verify_signature(&HASHED_MESSAGE, &PUB_KEY_X, &PUB_KEY_Y, &invalid_signature).unwrap();
169        assert!(!result);
170    }
171
172    #[test]
173    fn signature_does_not_verify_on_invalid_public_key() {
174        let invalid_pub_key_x: [u8; 32] = [0xff; 32];
175        let invalid_pub_key_y: [u8; 32] = [0xff; 32];
176
177        let result =
178            verify_signature(&HASHED_MESSAGE, &invalid_pub_key_x, &invalid_pub_key_y, &SIGNATURE)
179                .unwrap();
180        assert!(!result);
181    }
182
183    #[test]
184    fn signature_does_not_verify_when_hashed_msg_exceeds_curve_order() {
185        // All 0xFF bytes is larger than the secp256k1 curve order
186        // (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141).
187        // The function should reduce it modulo the order, not panic.
188        let oversized_hash: [u8; 32] = [0xff; 32];
189
190        // The result will be false (signature doesn't match the reduced hash), but no panic.
191        let result = verify_signature(&oversized_hash, &PUB_KEY_X, &PUB_KEY_Y, &SIGNATURE).unwrap();
192        assert!(!result);
193    }
194
195    #[test]
196    fn signature_does_not_verify_when_hashed_msg_equals_curve_order() {
197        // The exact secp256k1 curve order.
198        let curve_order: [u8; 32] = [
199            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
200            0xFF, 0xFE, 0xBA, 0xAE, 0xDC, 0xE6, 0xAF, 0x48, 0xA0, 0x3B, 0xBF, 0xD2, 0x5E, 0x8C,
201            0xD0, 0x36, 0x41, 0x41,
202        ];
203
204        let result = verify_signature(&curve_order, &PUB_KEY_X, &PUB_KEY_Y, &SIGNATURE).unwrap();
205        assert!(!result);
206    }
207}
acvm_blackbox_solver/ecdsa/secp256k1.rs

acvm_blackbox_solver/ecdsa/
secp256k1.rs
