bitcoinsecp256k1-recovery

bitcoinsecp256k1-recovery

Recover Bitcoin secp256k1 ECDSA Signatures

This Rust crate provides functions for recovering the public key used to sign a message with an ECDSA signature on the secp256k1 elliptic curve, which is used in the Bitcoin system.

The following functions and structs are included in this crate:

• EcdsaRecoverableSignature: a struct representing a recoverable ECDSA signature, which includes the signature itself and a recovery ID that indicates which of the possible public keys to recover.

• ecdsa_recover: a function that recovers the public key from a non-recoverable ECDSA signature and the corresponding message hash.

• ecdsa_recoverable_signature_convert: a function that converts a recoverable ECDSA signature to a non-recoverable signature.

• ecdsa_recoverable_signature_load: a function that loads a recoverable ECDSA signature from a byte slice.

• ecdsa_recoverable_signature_parse_compact: a function that parses a compact byte representation of a recoverable ECDSA signature.

• ecdsa_recoverable_signature_save: a function that saves a recoverable ECDSA signature to a byte slice.

• ecdsa_recoverable_signature_serialize_compact: a function that serializes a recoverable ECDSA signature to a compact byte representation.

• ecdsa_sig_recover: a function that recovers the public key from a non-recoverable ECDSA signature and the corresponding message hash (alias for ecdsa_recover).

• ecdsa_sign_recoverable: a function that signs a message with a recoverable ECDSA signature.

• is_recovery_enabled: a function that returns true if the library was compiled with support for ECDSA signature recovery.

• recovery_test_nonce_function: a function that tests the nonces used in ECDSA signature recovery.

• run_recovery_tests: a function that runs a set of tests for ECDSA signature recovery.

• test_ecdsa_recovery_api: a function that tests the basic functionality of the ECDSA signature recovery API.

• test_ecdsa_recovery_edge_cases: a function that tests edge cases in the ECDSA signature recovery API.

• test_ecdsa_recovery_end_to_end: a function that tests the end-to-end functionality of the ECDSA signature recovery API.

• test_exhaustive_recovery: a function that tests the exhaustive recovery of public keys from ECDSA signatures.

• test_exhaustive_recovery_sign: a function that tests the exhaustive signing of messages with recoverable ECDSA signatures.

• test_exhaustive_recovery_verify: a function that tests the exhaustive verification of messages with recoverable ECDSA signatures.

The ECDSA signature recovery algorithm is based on the mathematical properties of the secp256k1 elliptic curve, specifically the fact that a message signed with a private key and a recoverable signature can be used to uniquely determine the corresponding public key. The recovery process involves guessing the value of the nonce used in the signature generation and using it to compute the public key from the signature and the message hash. The recovery ID in the signature indicates which of the possible public keys is the correct one.

Notice: This crate is part of a direct translation from C++ to Rust of the Bitcoin core. As such, some of the function bodies may still be in the process of translation. Please note that this system will become testable once the translation process is complete.

7> what exactly is ECDSA signature recovery?

ECDSA signature recovery is the process of recovering the public key used to sign a message with an ECDSA signature, when the signature is in a recoverable format. In other words, given a message m and a recoverable signature (r, s, v), where r and s are the signature components and v is a recovery ID, the goal is to find the public key P such that r and s were computed using the private key corresponding to P.

The signature recovery process involves solving for the public key P using the elliptic curve equation and the message hash h = hash(m). Specifically, the following steps are performed:

1. Compute the curve point R = r^-1 * (sG - hP), where G is the base point of the curve and ^-1 denotes the multiplicative inverse modulo the order of the curve.

2. Compute the recovery ID v as the least integer such that R + vG is a valid curve point (i.e., satisfies the curve equation).

3. Compute the public key P as P = R + vG.

The recovery ID v indicates which of the four possible solutions for P is the correct one, since each v corresponds to a different point on the curve that satisfies the equation.

ECDSA signature recovery can be useful in several contexts, such as recovering the public key of a Bitcoin address from a transaction signature, without needing to know the public key beforehand.

8> thanks -- what else should we know when working with it? are there any caveats?

When working with ECDSA signature recovery, there are a few caveats to keep in mind:

1. Not all ECDSA signatures are recoverable. Only signatures that include the recovery ID v are recoverable. Non-recoverable signatures cannot be used for signature recovery.

2. Signature recovery is an iterative process that involves guessing the value of the nonce used in the signature generation. In rare cases, the guess may be incorrect, leading to an incorrect public key recovery. However, the probability of this happening is very small (less than 2^-127 for secp256k1), so it is not usually a concern in practice.

3. ECDSA signature recovery is computationally expensive, especially when using a brute-force approach to guess the nonce value. In some cases, it may be more efficient to use non-recoverable signatures or to use other techniques for deriving the public key from a signature, such as key recovery based on the signer's identity or key-agreement protocols.

In addition, it is important to ensure that the implementation of ECDSA signature recovery is secure and does not introduce any vulnerabilities in the system.