The following content was written by StraightCedar on May 19, 2020, 05:04:26 PM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)
I’m trying to understand how does “recid” (Recovery ID) variable work in libspec256k1 library (with C language).
(https://github.com/bitcoin-core/secp256k1)
I’m sorry if my question was too primitive or inappropriate on this forum.
I would appreciate any advice on the correct sites, the correct forums or etc.
I’d like to understand the relationship between “recid” (Recovery ID) , recovered-public-key and verification, so I tried following steps with modifying “secp256k1_ecdsa_sign_recoverable” function in main_impl.h.
Step1: Original signing operation. (no modification)
I use “secp256k1_ecdsa_sign_recoverable” function in main_impl.h to get recoverable signature.
In that function, “secp256k1_ecdsa_sig_sign” function is called and it returns “sign” and “recid”.
Step2: Recover public key with recid, and verify.
I wanted to get the recovered public-key using “recid”, which was given by “secp256k1_ecdsa_sig_sign function” in Step 1, and to verify the signed data.
I got the recovered public-key from “secp256k1_ecdsa_recover” function, and it returned the result “1 (recovery success)”.
Then “secp256k1_ecdsa_verify” function returned the result “1 (verification success)”.
Step3: Expect “verification failure” with wrong “recid”, but…
I tried the public-key recovery with wrong “recid”, and expected that verification failed.
“recid” range is 0 to 3, but actually in this experiment, the “recid” value output by the secp256k1_ecdsa_sig_sign function was 0 or 1.
So, if “recid” was 0, I intentionally changed it to 1, and if it was 0, changed to 1.
I got the recovered public-key from “secp256k1_ecdsa_recover” function with wrong “recid”, and it returned the result “1 (recovery success)”.
Then “secp256k1_ecdsa_verify” function returned the result “1 (verification success)”, even though used public-key was recovered with wrong “recid”.
Why verification succeeded with the public-key recovered with wrong “recid”?
The reason why I want to do something like Step3 is that I am strongly considering an experiment using a signature function of another library instead of secp256k1_ecdsa_sig_sign of libspec256k1 as a signature function.
The alternative signature function is designed only for ECDSA signatures, so it does not output “recid”.
Also, its implementation is completely hidden along with the private-key, and it is not possible to retrieve the value in the internal calculation process.
But I need “recid” to construct appropriate blockchain transaction data to send, so I considered Step3 sequence.
Sorry for the long sentence.
Thank you.
—————–
Following is overview of my code at each step.
(It’s a little simplified.)
Step1 original “secp256k1_ecdsa_sign_recoverable” basic process is
Code:
<… some processes …>
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL); /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL); /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
Step2 modified “secp256k1_ecdsa_sign_recoverable” basic process is
Code:
<… some processes …>
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL); /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
/*****************************************/
/**** Step2 Added: Recover public-key ****/
/*****************************************/
int res_pubkey_recover;
static secp256k1_pubkey pubkey_buf;
res_pubkey_recover = secp256k1_ecdsa_recover(ctx, &pubkey_buf, signature, msg32);
/* “&pubkey_buf” is output recovered public key. “signature” is input, which has “sign”s and “recid”. “msg32” is the hash created from original message data (given as a input argument of “secp256k1_ecdsa_sign_recoverable”) */
/*****************************************/
/**** Step2 Added: Verify signed data ****/
/*****************************************/
int res_sig_conv;
static secp256k1_ecdsa_signature normal_sig_buf;
/* Convert recoverable-signature-data into normal-type-signature-data to be used for verification function.
res_sig_conv = secp256k1_ecdsa_recoverable_signature_convert(ctx, &normal_sig_buf, signature);
/* “&normal_sig_buf” is output converted signature data. “res_sig_conv” is always 1. */
/* Verification */
int res_verify;
res_verify = secp256k1_ecdsa_verify(ctx, &normal_sig_buf, msg32, &pubkey_buf);
/* “res_verify = 1” is verification success. “res_verify = 0” is verification failure. */
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL); /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
/*****************************************/
/**** Step2 Added: Recover public-key ****/
/*****************************************/
int res_pubkey_recover;
static secp256k1_pubkey pubkey_buf;
res_pubkey_recover = secp256k1_ecdsa_recover(ctx, &pubkey_buf, signature, msg32);
/* “&pubkey_buf” is output recovered public key. “signature” is input, which has “sign”s and “recid”. “msg32” is the hash created from original message data (given as a input argument of “secp256k1_ecdsa_sign_recoverable”) */
/*****************************************/
/**** Step2 Added: Verify signed data ****/
/*****************************************/
int res_sig_conv;
static secp256k1_ecdsa_signature normal_sig_buf;
/* Convert recoverable-signature-data into normal-type-signature-data to be used for verification function.
res_sig_conv = secp256k1_ecdsa_recoverable_signature_convert(ctx, &normal_sig_buf, signature);
/* “&normal_sig_buf” is output converted signature data. “res_sig_conv” is always 1. */
/* Verification */
int res_verify;
res_verify = secp256k1_ecdsa_verify(ctx, &normal_sig_buf, msg32, &pubkey_buf);
/* “res_verify = 1” is verification success. “res_verify = 0” is verification failure. */
Step3 modified “secp256k1_ecdsa_sign_recoverable” basic process is
Code:
<… some processes …>
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL); /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
/**************************************/
/**** Step3 Added: Use wrong recid ****/
/**************************************/
recid = (recid == 0 ? 1 : 0); /* Intentionally use wrong recid. */
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
/*****************************************/
/**** Step2 Added: Recover public-key ****/
/*****************************************/
int res_pubkey_recover;
static secp256k1_pubkey pubkey_buf;
res_pubkey_recover = secp256k1_ecdsa_recover(ctx, &pubkey_buf, signature, msg32);
/* “&pubkey_buf” is output recovered public key. “signature” is input, which has “sign”s and “recid”. “msg32” is the hash created from original message data (given as a input argument of “secp256k1_ecdsa_sign_recoverable”) */
/*****************************************/
/**** Step2 Added: Verify signed data ****/
/*****************************************/
int res_sig_conv;
static secp256k1_ecdsa_signature normal_sig_buf;
/* Convert recoverable-signature-data into normal-type-signature-data to be used for verification function.
res_sig_conv = secp256k1_ecdsa_recoverable_signature_convert(ctx, &normal_sig_buf, signature);
/* “&normal_sig_buf” is output converted signature data. “res_sig_conv” is always 1. */
/* Verification */
int res_verify;
res_verify = secp256k1_ecdsa_verify(ctx, &normal_sig_buf, msg32, &pubkey_buf);
/* “res_verify = 1” is verification success. “res_verify = 0” is verification failure. */
/* Convert some input arguments of “secp256k1_ecdsa_sign_recoverable” into the “secp256k1_scalar type” to be used for signing function. */
secp256k1_scalar sec, non, msg;
secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Secret-key “seckey” was converted into “&sec” */
secp256k1_scalar_set_b32(&msg, msg32, NULL); /* Hash “msg32”, which was created from original message data, was converted into “&msg” */
secp256k1_scalar_set_b32(&non, nonce32, &overflow); /* Nonce data “nonce32” was converted into “&non” */
<… some processes …>
/* make “sign” and “recid” as following*/
secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid);
/* “&r” and “&s” are ouput sign-r and sign-s. “recid” is ouput recovery id (0, 1, 2 or 3). The others are given from the input arguments of “secp256k1_ecdsa_sign_recoverable”. “ctx” (secp256k1 context object) was created for signing and verification. */
<… some processes …>
/* Combine “sign”s and “recid”. It will be decomposed into “sign”s and “recid” again by higher processing, and they will be used to construct bitcoin transaction data.
/**************************************/
/**** Step3 Added: Use wrong recid ****/
/**************************************/
recid = (recid == 0 ? 1 : 0); /* Intentionally use wrong recid. */
secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid);
/* “signature” is ouput recoverable-signature-data (“secp256k1_ecdsa_recoverable_signature” type), which is consisting of the inputs “&r”, “&s”, and “recid”. It is also the output of “secp256k1_ecdsa_sign_recoverable” function. */
/*****************************************/
/**** Step2 Added: Recover public-key ****/
/*****************************************/
int res_pubkey_recover;
static secp256k1_pubkey pubkey_buf;
res_pubkey_recover = secp256k1_ecdsa_recover(ctx, &pubkey_buf, signature, msg32);
/* “&pubkey_buf” is output recovered public key. “signature” is input, which has “sign”s and “recid”. “msg32” is the hash created from original message data (given as a input argument of “secp256k1_ecdsa_sign_recoverable”) */
/*****************************************/
/**** Step2 Added: Verify signed data ****/
/*****************************************/
int res_sig_conv;
static secp256k1_ecdsa_signature normal_sig_buf;
/* Convert recoverable-signature-data into normal-type-signature-data to be used for verification function.
res_sig_conv = secp256k1_ecdsa_recoverable_signature_convert(ctx, &normal_sig_buf, signature);
/* “&normal_sig_buf” is output converted signature data. “res_sig_conv” is always 1. */
/* Verification */
int res_verify;
res_verify = secp256k1_ecdsa_verify(ctx, &normal_sig_buf, msg32, &pubkey_buf);
/* “res_verify = 1” is verification success. “res_verify = 0” is verification failure. */
The following content was written by arulbero on May 19, 2020, 07:06:14 PM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)
https://bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v
Quote
The (r, s) is the normal output of an ECDSA signature, where r is computed as the X coordinate of a point R, modulo the curve order n.
In Bitcoin, for message signatures, we use a trick called public key recovery. The fact is that if you have the full R point (not just its X coordinate) and s, and a message, you can compute for which public key this would be a valid signature. What this allows is to ‘verify’ a message with an address, without needing to know the full key (we just do public key recovery on the signature, and then hash the recovered key and compare it with the address).
However, this means we need the full R coordinates. There can be up to 4 different points with a given “X coordinate modulo n”. (2 because each X coordinate has two possible Y coordinates, and 2 because r+n may still be a valid X coordinate). That number between 0 and 3 we call the recovery id, or recid. Therefore, we return an extra byte, which also functions as a header byte, by using 27+recid (for uncompressed recovered pubkeys) or 31+recid (for compressed recovered pubkeys).
Strictly speaking the recid is not necessary, as we can just cycle through all the possible coordinate pairs and check if any of them match the signature. The recid just speeds up this verification.
@PeterWuille There can be up to 4 different points with a given “X coordinate modulo n”. (2 because each X coordinate has two possible Y coordinates, and 2 because r+n may still be a valid X coordinate). I understand the former (2 y values for each x, because of the symmetry)… But how does the latter work? ie r+n may still be a valid X coordinate??
X and Y coordinates are numbers modulo p, the field size, which is around 2^256 – 2^32 for secp256k1. The value r and s in the signature however are modulo n, the group order, which is around 2^256 – 2^128. When R.x is between n and p, r is reduced to R.x-n. Thus, if you have an r value below 2^128-2^32, there may be 2 valid R.x values corresponding to it. â Pieter Wuille
27 = lower X even Y. 28 = lower X odd Y. 29 = higher X even Y. 30 = higher X odd Y. Note that 29 and 30 are exceedingly rarely, and will in practice only ever be seen in specifically generated examples. There are only two possible X values if r is between 1 and (p mod n), which has a chance of about 0.000000000000000000000000000000000000373 % to happen randomly.
In Bitcoin, for message signatures, we use a trick called public key recovery. The fact is that if you have the full R point (not just its X coordinate) and s, and a message, you can compute for which public key this would be a valid signature. What this allows is to ‘verify’ a message with an address, without needing to know the full key (we just do public key recovery on the signature, and then hash the recovered key and compare it with the address).
However, this means we need the full R coordinates. There can be up to 4 different points with a given “X coordinate modulo n”. (2 because each X coordinate has two possible Y coordinates, and 2 because r+n may still be a valid X coordinate). That number between 0 and 3 we call the recovery id, or recid. Therefore, we return an extra byte, which also functions as a header byte, by using 27+recid (for uncompressed recovered pubkeys) or 31+recid (for compressed recovered pubkeys).
Strictly speaking the recid is not necessary, as we can just cycle through all the possible coordinate pairs and check if any of them match the signature. The recid just speeds up this verification.
@PeterWuille There can be up to 4 different points with a given “X coordinate modulo n”. (2 because each X coordinate has two possible Y coordinates, and 2 because r+n may still be a valid X coordinate). I understand the former (2 y values for each x, because of the symmetry)… But how does the latter work? ie r+n may still be a valid X coordinate??
X and Y coordinates are numbers modulo p, the field size, which is around 2^256 – 2^32 for secp256k1. The value r and s in the signature however are modulo n, the group order, which is around 2^256 – 2^128. When R.x is between n and p, r is reduced to R.x-n. Thus, if you have an r value below 2^128-2^32, there may be 2 valid R.x values corresponding to it. â Pieter Wuille
27 = lower X even Y. 28 = lower X odd Y. 29 = higher X even Y. 30 = higher X odd Y. Note that 29 and 30 are exceedingly rarely, and will in practice only ever be seen in specifically generated examples. There are only two possible X values if r is between 1 and (p mod n), which has a chance of about 0.000000000000000000000000000000000000373 % to happen randomly.
The following content was written by StraightCedar on June 01, 2020, 10:57:42 AM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)
Thanks to your kind instruction.
I still don’t understand, but result of various trials, I could get the correct “recid” from “sign r”, “sign s” and “original public key”, in the following process,
Step 1. Make sign data by an ECDSA signing function.
(It is not included in libsecp256k1. A third party provided one, so it is not arranged for Bit Coin and it doesn’t output “recid”.)
Step 2. Recover public-key from “sign r”, “sign s” and “recid = 0” with secp256k1_ecdsa_recover function.
Step 3. Compare the recovered public-key with original public-key.
Step 4. If they are matched, recid = 0. If not matched, recid = 1.
(According to some articles for Ethereum, I assumed recid is 0 or 1.)
Then I made transaction data from above result and sent it to the Brock Chain (Ethereum) built on cloud for my test, but often error messages were sent back.
When I executed the verify function of libsecp256k1 for the transaction data going to send, I found that when the validation function returned an error, the Brock Chain also sent an error message back.
Strictly speaking, if sign-s is “higher than the group order divided by 2” (quoted from the commnet in libsecp256k1, secp256k1_scalar_is_high function), the Block Chain will sent an error message back.
So I added range check for sign-s with secp256k1_scalar_is_high function, and if it is “higher”, signing process will be retried until the “sign-s” will become “not higher”.
It works and the Brock Chain no longer returns errors.
From these results, I assumed as follows,
1. Comparation of public keys determine that it is “even Y” or “odd Y”.
2. Higher “sign-s” is not allowed for Etherium.
(I don’t understant about it.
Maybe, the “third party signing function” doesn’t avoid overflowed Rx, so it generates the “sign-s” values corresponding to recid = 2 or 3?)
In any case, apparently I found that it is possible to identify the “recid” from “sign-r”, “sign-s” and “original public key”.
Thank you again.
The following content was written by arulbero on June 01, 2020, 03:13:29 PM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)
2. Higher “sign-s” is not allowed for Etherium.
(I don't understant about it.
Maybe, the “third party signing function” doesn't avoid overflowed Rx, so it generates the “sign-s” values corresponding to recid = 2 or 3?)
(I don't understant about it.
Maybe, the “third party signing function” doesn't avoid overflowed Rx, so it generates the “sign-s” values corresponding to recid = 2 or 3?)
For how it works the ECDSA, https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
if (r,s) is a correct signature, (r, N-s) is also a valid signature
BUT this fact has created issues (transaction malleability) therefor, from Bitcoin Core 0.11, only the lower value of s is allowed:
https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#low-s-values-in-signatures
Quote
Low S values in signatures
The value S in signatures must be between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive). If S is too high, simply replace it by S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 – S.
Signatures produced by the OpenSSL library are not guaranteed to be consistent with this constraint. Version 0.9.3 of the reference client provides an example for detection and correction.
The constraints on the value R are unchanged w.r.t. ECDSA, and values can be between 0x1 and 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 (inclusive).
The value S in signatures must be between 0x1 and 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 (inclusive). If S is too high, simply replace it by S' = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 – S.
Signatures produced by the OpenSSL library are not guaranteed to be consistent with this constraint. Version 0.9.3 of the reference client provides an example for detection and correction.
The constraints on the value R are unchanged w.r.t. ECDSA, and values can be between 0x1 and 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 (inclusive).
For what concerns Ethereum, the same choice was made:
https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.md
Quote
Allowing transactions with any s value with 0 < s < secp256k1n, as is currently the case, opens a transaction malleability concern, as one can take any transaction, flip the s value from s to secp256k1n - s, flip the v value (27 -> 28, 28 -> 27), and the resulting signature would still be valid. This is not a serious security flaw, especially since Ethereum uses addresses and not transaction hashes as the input to an ether value transfer or other transaction, but it nevertheless creates a UI inconvenience as an attacker can cause the transaction that gets confirmed in a block to have a different hash from the transaction that any user sends, interfering with user interfaces that use transaction hashes as tracking IDs. Preventing high s values removes this problem.
The issue is the same for Bitcoin and Ethereum, the solution is the same.
Strictly speaking, if sign-s is “higher than the group order divided by 2” (quoted from the commnet in libsecp256k1, secp256k1_scalar_is_high function), the Block Chain will sent an error message back.
So I added range check for sign-s with secp256k1_scalar_is_high function, and if it is “higher”, signing process will be retried until the “sign-s” will become “not higher”.
It works and the Brock Chain no longer returns errors.
So I added range check for sign-s with secp256k1_scalar_is_high function, and if it is “higher”, signing process will be retried until the “sign-s” will become “not higher”.
It works and the Brock Chain no longer returns errors.
It is enough this check:
if (s > N/2) then s = N – s
you don't need to retry from the start the entire process.
result of various trials, I could get the correct “recid” from “sign r”, “sign s” and “original public key”, in the following process,
Step 1. Make sign data by an ECDSA signing function.
(It is not included in libsecp256k1. A third party provided one, so it is not arranged for Bit Coin and it doesn't output “recid”.)
Step 2. Recover public-key from “sign r”, “sign s” and “recid = 0” with secp256k1_ecdsa_recover function.
Step 3. Compare the recovered public-key with original public-key.
Step 4. If they are matched, recid = 0. If not matched, recid = 1.
(According to some articles for Ethereum, I assumed recid is 0 or 1.)
…
In any case, apparently I found that it is possible to identify the “recid” from “sign-r”, “sign-s” and “original public key”.
Step 1. Make sign data by an ECDSA signing function.
(It is not included in libsecp256k1. A third party provided one, so it is not arranged for Bit Coin and it doesn't output “recid”.)
Step 2. Recover public-key from “sign r”, “sign s” and “recid = 0” with secp256k1_ecdsa_recover function.
Step 3. Compare the recovered public-key with original public-key.
Step 4. If they are matched, recid = 0. If not matched, recid = 1.
(According to some articles for Ethereum, I assumed recid is 0 or 1.)
…
In any case, apparently I found that it is possible to identify the “recid” from “sign-r”, “sign-s” and “original public key”.
The recid value serves to speedup the verification, usually you generate it when you create the signature but you want to derive the recid from (r, s) instead.
For the notation –> https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
1) compute (u1 x G + u2 x Qa) = (x'_1, y'_1)
2) if x'_1 = r the recid value is 0 or 1 for sure
a) if y'_1 is even, then recid = 0
b) if y'_1 is odd, then recid = 1
3) if x'_1 = r+N the recid value is 2 or 3 for sure
a) if y'_1 is even, then recid = 2
b) if y'_1 is odd, then recid = 3
4) if x'_1 != r and x'_1 != r+N, then the signature is not verified
I still don't understand
If you want more details, I'll use the notation https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
Note1)
choose random (or pseudorandom) k in [1,N-1] and compute k*G = (x1, y1)
then you get the first part of the signature r = x1 mod N
x1 is a number that lies in field Fp, x1 is less than p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = about 2^256 – 2^32
while r is less than N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 = about 2^256 – 2^128
note that N < P;
if N < x1 < P, then r = x1 mod N --> 0 < r < 2^128 - 2^32
for example (x1 = N + 5)
N < N + 5 < P ---> 0 < 5 < 2^128 - 2^32
but the number x1 = 5 too has the same value mod N:
0 < 5 < N , then x1 mod N = 5, in this case x1 mod N = x1 = r
To sum up: the same value of 'r' could refer to 2 different points (x1, y1):
(r, y1) and (r+N, y1) if 0 < r <2^128 - 2^32 (very rare case)
instead if r > 2^128 – 2^32 –> r+N > p there is only 1 possibility for (x1,y1):
(r, y1)
Moreover there are other 2 possibilities: for each x1, there are 2 points with the same x-coordinate and opposite y-values: y1 an n-y1 (for the symmetry).
When you derive the second part of the signature, s, you get 2 opposite values for (x1, y1) and (x1, N-y1):
s = k^-1 (z + rd) mod N
because s depends on k (and k*G = (x1, y1))
For the BIP 62 you have to choose the low value of s in Bitcoin, therefor s is determined by its value, not by your initial choice of k. You may have (x1, y1) or (x1, N-y1).
Note2)
when you perform the signature verification algorithm, starting from r, s^-1, Qa and the hash of the message (the transaction) you have to get the original x1 again:
u1 x G + u2 x Qa = (x'_1, y'_1)
you should get again the point (x1, y1), but there are actually 4 possibilities:
1) x'_1 = r (0 < x1 < N, r = x1) and y is even --> recid 0 –> verified
2) x'_1 = r (0 < x1 < N, r = x1) and y is odd --> recid 1 –> verified
3) x'_1 > r (N < x1 < P, r = x1 - N) and y is even --> recid 2 –> verified
4) x'_1 > r (N < x1 < P, r = x1 - N) and y is odd --> recid 3 –> verified
since you don't want to store the y1 value you got from k*G (the signature contains only r, almost always r = x-coordinate of k*G, and s), you want to know if the original y1 is even or odd and if the original x1 is greater or less than N.
The following content was written by StraightCedar on July 09, 2020, 08:16:33 AM in the thread How does “recid” variable work in libspec256k1 library?. All content is owned by the author of the bitcointalk.org post. (original)
Thanks to your kind instruction again, and I’m sorry for late reply.
According to your advice about the conversion “Higher sign-s” to “Lower sign-s”, I could calculate appropriate sign-s without retry, and it was able to be used for Ethereum communication.
I had a deeper understanding of it, so I could also optimize some process flows .
Thank you for your continued support.
