Does python ecdsa NIST-256p provide recovery code (byte)?

Question

I am using the python ecdsa library for signing messages for blockchain transactions. In the blockchain specification it says, for secp256r1 that the signature should have a length of 65 bytes where:

The signature must be of length 65 bytes in the form of [r, s, v] where the first 32 bytes are r, the second 32 bytes are s and the last byte is v.

and

The v represents the recovery ID, which must be normalized to 0, 1, 2 or 3. Note that unlike EIP-155 chain ID is not used to calculate the v value

I consistently get the first 64 bytes using: sign_deterministic(data, hashfunc=hashlib.sha256)

But not sure where ecdsa holds, or I can compute, the v byte?

I see in the source code (Rust fastcrypto) used on the blockchain it is doing:

// Compute recovery id and normalize signature
        let is_r_odd = y.is_odd();
        let is_s_high = sig.s().is_high();
        let is_y_odd = is_r_odd ^ is_s_high;
        let sig_low = sig.normalize_s().unwrap_or(sig);
        let recovery_id = RecoveryId::new(is_y_odd.into(), false);

But in ecdsa all that is hidden behind the signing function noted above.

Answer 1

Signing with ECDSA is explained e.g. here. In the following, the terms used in this post are applied:

k:                  secret number when generating the signature
R=k*G =(R.x, R.y):  associated point, G: generator
(r=R.x,s):          signature

The ecdsa library does not support the additional determination of the recovery ID when creating the signature. However, it is possible to determine the recovery ID subsequently. To do this, the k value used when creating the signature must first be determined, which is possible since you are using deterministic ECDSA according to RFC 6979. Here k depends defined on the hash, the message and the private signing key.

When running sign_deterministic(data, hashfunc=hashlib.sha256), the following logic is executed to determine k:

from ecdsa import SigningKey, NIST256p, rfc6979, ecdsa
from hashlib import sha256
...
def get_k(signing_key, message, hash):  
    def simple_r_s(r, s, order):
        return r, s, order    
    retry_gen = 0
    while True:
        digest = hash(message).digest()
        k = rfc6979.generate_k(
            NIST256p.generator.order(),
            signing_key.privkey.secret_multiplier,
            hash,
            digest,
            retry_gen=retry_gen,
            extra_entropy=b"")
        try:
            r, s, order = signing_key.sign_digest(
                digest,
                sigencode=simple_r_s,
                k=k,
                allow_truncate=True)
            break
        except ecdsa.RSZeroError:
                retry_gen += 1
    return k

The corresponding code location can be found here. Note that the sign_deterministic(data, hashfunc=hashlib.sha256) call uses the default value for the extra entropy (extra_entropy=b"") and allows too large hashes to be truncated (allow_truncate=True).

With k, R can be determined as the product of k and generator point G. Formally, k can be considered as a raw private key and R as a raw public key, so the existing functionalities for keys can be used and R can be easily determined as follows:

def get_r(signing_key, message, hash):
    k = get_k(signing_key, message, hash)
    r_sk = SigningKey.from_secret_exponent(k, curve=NIST256p)
    r_vk = r_sk.get_verifying_key()
    return (r_vk.pubkey.point.x(), r_vk.pubkey.point.y())

For known R, the recovery ID can be derived as follows:

def get_recovery_id(r):
    r_x, r_y = r
    if r_x > NIST256p.generator.order():
        if r_y % 2 == 0: recId = 2
        else: recId = 3
    else:
        if r_y % 2 == 0: recId = 0
        else: recId = 1
    return recId

For an explanation of the last logic, see here (including the comments). Note that the probability for recovery IDs 2 and 3 is vanishingly small.

A signature including recovery ID can then be generated with the ecdsa library, e.g. as follows:

signing_key = SigningKey.generate(curve=NIST256p)
message = b'This is a text message'
signature = signing_key.sign_deterministic(message, hashfunc=sha256)
R = get_r(signing_key, message, sha256)
rec_id = get_recovery_id(R)
print("Rec-Id:", str(rec_id))
print("r:", signature[:32].hex())
print("s:", signature[32:].hex())

---

To verify the results and also to demonstrate that there are more convenient libraries for generating a signature with recovery ID, the following pycoin code is used, which requires only the library function function sign_with_recid(), which returns a tuple with r, s and the recovery ID. By default, this method internally uses the k derivation from RFC6979 (i.e. the logic also applied in the ecdsa example):

from pycoin.ecdsa.secp256r1 import secp256r1_generator
from hashlib import sha256
...
signing_key = SigningKey.generate(curve=NIST256p)
message = b'This is a text message'
private_key = signing_key.privkey.secret_multiplier 
digest = sha256(message).digest()
(r, s, rec_id) = secp256r1_generator.sign_with_recid(private_key, int.from_bytes(digest, 'big'))
print("Rec-Id:", str(rec_id))
print("r:", r.to_bytes(32, 'big').hex())
print("s:", s.to_bytes(32, 'big').hex())

When using the same signing key, the same message and the same digest, the values are identical.

---

The current question is about deterministic ECDSA. But even for non-deterministic ECDSA, the ecdsa library allows the recovery ID to be determined (and much more easily than in the case of deterministic ECDSA). Since the random k used in signing cannot be accessed, the generation of k is simply moved outside and then the signature is generated with this k (which is supported, see sign()):

import os
import ecdsa
import hashlib

from ecdsa import SigningKey, NIST256p

message = b'This is a text message'
sk = SigningKey.generate(curve=NIST256p)
k = ecdsa.util.randrange(NIST256p.generator.order(), os.urandom) # shift the internal k generation to the outside
signature = sk.sign(message, k=k, hashfunc=hashlib.sha256)

For known k, R and finally the recovery ID can be determined as above.