Failed to verify schnorr signature (secp256k1)

[jonas089]

Aim

Successfully verify a signature using hashed_message, pub_x, pub_y and signature

Expected Behavior

Successful verification of signature

Bug

Here is the python code that I use to generate my parameters:

from secp256k1 import PrivateKey, PublicKey
import hashlib
import ecdsa

message_hash = hash_hex = hashlib.sha256("Hello, World!".encode('utf-8')).hexdigest()
message_bytes = list(bytes.fromhex(message_hash))

# Generate a random private key
private_key = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)

# Derive the corresponding public key
public_key = private_key.get_verifying_key()

# Sign the message using the private key
signature = private_key.sign(bytes.fromhex(message_hash))
public_key_hex_uncompressed = public_key.to_string("uncompressed").hex()
print("Public Key (Uncompressed):", public_key_hex_uncompressed)
x_coordinate_bytes = list(bytes.fromhex(public_key_hex_uncompressed)[1:33])  # Exclude the prefix byte
y_coordinate_bytes = list(bytes.fromhex(public_key_hex_uncompressed)[33:])
assert(len(x_coordinate_bytes) == len(y_coordinate_bytes) == 32)

signature_hex = signature.hex()
print("x: ", x_coordinate_bytes)
print("y: ", y_coordinate_bytes)
print("Signature:", list(bytes.fromhex(signature_hex)))
print("Message:", message_bytes)
print(
    "PARAMETERS FOR NOIR: ", '\n'*3,
    message_bytes, ', \n',
    x_coordinate_bytes, ', \n',
    y_coordinate_bytes, ', \n',
    list(bytes.fromhex(signature_hex))

)

# Verify the signature using the public key
try:
    public_key.verify(signature, bytes.fromhex(message_hash))
    print("[Expectation] Signature is valid!")
except ecdsa.BadSignatureError:
    print("Signature is invalid")

My circuit (with tests):

use dep::std;

fn main(hashed_message : [u8;32], pub_key_x : [u8;32], pub_key_y : [u8;32], signature : [u8;64]) {
     let valid_signature = std::ecdsa_secp256k1::verify_signature(pub_key_x, pub_key_y, signature, hashed_message);
     assert(valid_signature);
}

#[test]
fn test_add() {
    main(

[53, 7, 44, 26, 229, 70, 53, 14, 11, 250, 122, 177, 29, 73, 220, 111, 18, 158, 114, 204, 213, 126, 199, 235, 103, 18, 37, 187, 209, 151, 200, 241],
 [86, 108, 161, 209, 220, 50, 159, 13, 11, 174, 9, 64, 18, 167, 94, 78, 26, 221, 11, 96, 123, 11, 82, 18, 174, 103, 61, 227, 200, 231, 228, 152], 
 [250, 143, 10, 186, 165, 243, 156, 244, 31, 104, 193, 230, 162, 120, 183, 90, 102, 255, 188, 224, 180, 81, 213, 90, 0, 66, 199, 51, 144, 210, 57, 13], 
 [46, 78, 23, 125, 234, 214, 80, 209, 154, 73, 39, 89, 84, 184, 149, 173, 135, 140, 79, 204, 254, 30, 115, 24, 158, 234, 135, 203, 125, 195, 161, 170, 18, 242, 180, 83, 142, 132, 214, 94, 168, 151, 154, 132, 227, 141, 191, 85, 99, 36, 68, 206, 198, 31, 231, 85, 200, 80, 247, 92, 56, 243, 29, 43]
    );
}

nargo test output:

Error: [sig_verifier] 1 test failed

Location: crates/nargo_cli/src/cli/mod.rs:79:5

To Reproduce

1. run python script
2. copy outputs ("PARAMETERS NOIR") to #[test] test_add
3. run nargo test

Installation Method

Binary

Nargo Version

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[ghost]

@jonas089 I have thoroughly examined your code and identified the bug inside parameters generation. Let me provide a detailed breakdown.

Problem analysis

The sequence of operations in your code first hashes the message using hashlib.sha256. Subsequently, the resulting digest is passed to SigningKey.sign(). However, it's important to note that the SigningKey.sign() method internally hashes the passed data again :exclamation:

This behavior can be traced back in the python-ecdsa repository:

• The sign() method hashes data by default. Refer to this link for details.
• By default, the hash function employed is sha1. See here.

As a result of this sequence, your message undergoes a double hashing process. This leads to a mismatch during the proof step.

Solution

To resolve the issue, you should:

1. Pass the raw message to sign(), rather than the message_hash.
2. Adjust the default hash function from sha1 to sha256 to ensure consistency with your original message hashing.

TIP: For a more Bitcoin-like (RFC6979) implementation, consider utilizing sign_deterministic() with canonized (lower-s) signature format sigencode_string_canonize.

---

Full working example

Input generator prepare_input.py:

import hashlib
import os

from ecdsa import SigningKey, SECP256k1
from ecdsa.util import sigencode_string_canonize

def generate_parameters():
    """Generate parameters for ECDSA."""
    # Generate the SigningKey and VerifyingKey.
    sk = SigningKey.generate(curve=SECP256k1, hashfunc=hashlib.sha256)
    vk = sk.get_verifying_key()

    # Create a sample message or use random bytes: os.urandom(38).
    message = b'Instructions unclear, ask again later.'
    hashed_message = hashlib.sha256(message).digest()

    # Generate a deterministic signature.
    signature = sk.sign_deterministic(
        message, 
        sigencode=sigencode_string_canonize, 
        extra_entropy=b"", 
        hashfunc=hashlib.sha256
    )

    # Extract x and y coordinates from the VerifyingKey.
    pub_key_bytes = vk.to_string()
    pub_key_x = pub_key_bytes[:32]
    pub_key_y = pub_key_bytes[32:]

    return message, hashed_message, pub_key_x, pub_key_y, signature

def bytes_to_decimals(b):
    """Convert bytes to their decimal values."""
    return [byte for byte in b]

# Generate and display parameters.
message, hashed_message, pub_key_x, pub_key_y, signature = generate_parameters()

print("message =", bytes_to_decimals(message))
print("hashed_message =", bytes_to_decimals(hashed_message))
print("pub_key_x =", bytes_to_decimals(pub_key_x))
print("pub_key_y =", bytes_to_decimals(pub_key_y))
print("signature =", bytes_to_decimals(signature))

Example output (can be copy pasted to Prover.toml):

message = [73, 110, 115, 116, 114, 117, 99, 116, 105, 111, 110, 115, 32, 117, 110, 99, 108, 101, 97, 114, 44, 32, 97, 115, 107, 32, 97, 103, 97, 105, 110, 32, 108, 97, 116, 101, 114, 46]
hashed_message = [58, 115, 244, 18, 58, 92, 210, 18, 31, 33, 205, 126, 141, 53, 136, 53, 71, 105, 73, 208, 53, 217, 194, 218, 104, 6, 180, 99, 58, 200, 193, 226]
pub_key_x = [45, 122, 161, 225, 32, 136, 228, 165, 181, 156, 54, 116, 145, 110, 3, 39, 247, 39, 226, 208, 55, 2, 93, 71, 16, 101, 111, 23, 124, 105, 7, 49]
pub_key_y = [157, 79, 235, 206, 98, 26, 140, 196, 10, 156, 207, 84, 247, 58, 171, 240, 180, 14, 202, 178, 9, 71, 114, 146, 158, 92, 229, 95, 207, 205, 146, 10]
signature = [206, 167, 117, 244, 118, 234, 65, 141, 56, 193, 117, 103, 143, 64, 75, 203, 242, 97, 53, 95, 244, 65, 110, 55, 214, 139, 34, 124, 120, 211, 67, 114, 117, 134, 171, 252, 226, 158, 140, 150, 73, 231, 164, 92, 71, 164, 148, 7, 151, 20, 39, 94, 244, 80, 126, 168, 138, 199, 177, 174, 215, 84, 236, 197]

Finally, updated circuit main.nr:

use dep::std;

fn main(message : [u8;38], hashed_message : [u8;32], pub_key_x : [u8;32], pub_key_y : [u8;32], signature : [u8;64]) {
    // Hash the message, since secp256k1 expects a hashed_message
    let expected= std::hash::sha256(message);
    assert(hashed_message == expected);

    let valid_signature = std::ecdsa_secp256k1::verify_signature(pub_key_x, pub_key_y, signature, hashed_message);
    assert(valid_signature);
}

I trust this will help you in resolving the issue :smile:

[jonas089]

Thanks Andrzej, I very much appreciate your effort. Would have never thought they use sha-1 under the hood 😄

[kevaundray]

Amazing work @andrzej-casper ! Closing as you have solved the issue :)