Method 2 (Finding recId during signing or from R which is the point, and s which is the integer):I still don't understand what the mathematical logic behind this is yet.
During signing when R is produced (multiplication result of k * G), we use R.y and the value of s to get the recId. Here is the c# code:
int recid = ((R.X > curve.N) ? 2 : 0) | (R.Y.IsEven ? 0 : 1);
recid = (s > curve.N / 2) ? recid ^1 : recid;
* This is a more complete version of the link posted above by @darosior since it is considering the rare case of R.X being bigger than curve order.
* This seems to be working but I am not sure.
* I believe
this is the function in bitcoin core that is responsible for signing messages (recoverable sigs) but I am not sure if I understood it correctly specially the
overflow part!
This is correct, and that is the function that is used.
Overflow just means that R.x > curve.N. Again, viewing the recid as a bitfield, what this code does is set bit 1 to 1 if it overflows, i.e. R.x > curve.N. It sets the entire recid to the number 2 because 2 is 10 in binary. This sets bit 1. The 0th bit is set by the
| (R.Y.IsEven ? 0 : 1). This is because we choose a 0 or 1 for the 0th bit, and Bitwise OR it with the number 2. This will make sure that bit 0 is set, and if bit 1 was set, that will also be included in the final recid.
* Additionally there is this comment by Pieter Wuille which doesn't make any sense
27 = lower X even Y. 28 = lower X odd Y. 29 = higher X even Y. 30 = higher X odd Y.
Sure it does. The first byte is just 27 + recid + compression. Ignoring compression for now (so it's 0), you have 27 + recid. If the recid is 0, then 27 + 0 = 27. A recid of 0 means that there is no overflow (lower X) and y is even (even Y). So 28 = 27 + 1. Recid 1 means low X, odd Y. 29 = 27 + 2. Recid 2 means high X (R.X > curve.N) and even y. Lastly 30 = 27 + 3. Recid 3 means high X and odd y.