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?)
For how it works the ECDSA,
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithmif (r,s) is a correct signature, (r, N-s) is also a valid signatureBUT 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-signaturesLow 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).
For what concerns Ethereum, the same choice was made:
https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.mdAllowing 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.
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".
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_Algorithm1) 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_AlgorithmNote1)
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 Nx1 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.