What is the first byte in message signature result?

[Coding Enthusiast]

I can't find any documentation on how to sign a message, I get that there is no standard but there should be some wiki page at least on bitcoinwiki explaining it IMO.

The problem is that I don't get how we produce the first byte. I can get this far:
1- Produce r and s
2- Attempt recovering public key from it
3- Do something here
4- Add 27 + (isCompressed ? 4 : 0) + (a number from step 3)!

Now in that "step 3 (and 2)" I am following the steps in section 4.1.6 of Standards for Efficient Cryptography: 1
From j = 0 to h (which is 1 for sec256k1)
* Calculate x and R assuming y is even
From k = 1 to k = 2
* Calculate Q from R if not valid then Q from -R which basically makes y odd

My guess is that the number in step 3 is (j + k-1) for some reason! I guess the libraries don't loop like this, they are looping from 0 to 3 (4 times) and then report that number, am I right?

Also was 27 chosen for "aesthetic" reasons, or is there more to it than meets the eye?

[1714815398]

1714815398

[1714815398]

1714815398

[1714815398]

1714815398

[1714815398]

1714815398

[achow101]

Signed messages use a thing called public key recovery to get the public key and then get the address to compare that against the address provided. In this way, the public key does not need to be provided in the signature which makes it much shorter. However, public key recovery will result in multiple public keys, up to 4 of them. The first byte encodes a number 0 to 3 which is the recovery id. This number is used to determine which of those 4 public keys is the actual public key. There's some mathematical properties in the recovery id which can be used to calculate the actual public key without the use of a loop. And the recovery id can be calculated at signing time due to the same properties.

The first byte also encodes the compression.

I'm pretty sure that the 27 is just a random number that Pieter decided to use when implementing this.

[Coding Enthusiast]

That doesn't quite answer my question though. I understand that it is a "recovery ID" but I am trying to figure out how that number is obtained.
For example to sign "123" with the key to this address "muRAUfvSXQKXJm9sPsAbPsxDTMsMJoDQes"
I add 0 * n to r (first iteration of first loop)
Calculate Q with R, (first iteration of second loop) it is invalid
continue
Calculate Q with -R, (second iteration of second loop) it is valid
break.

The byte should be 32 meaning only 1 is added (27 + 4 + 1). Trying to figure out why 1 was chosen based on above operation?

[darosior]

I may be wrong but I guess you are talking about the "v" in a v,r,s signature which is indeed a recid (Link to Pieter Wuille answer, which is what achow said).

3- Do something here
4- Add 27 + (isCompressed ? 4 : 0) + (a number from step 3)!

Maybe the secp256k1 functions (and especially ecdsa_raw_sign, which returns v, r, s), written by Vitalik Butterin, could help you.

[achow101]

That doesn't quite answer my question though. I understand that it is a "recovery ID" but I am trying to figure out how that number is obtained.
For example to sign "123" with the key to this address "muRAUfvSXQKXJm9sPsAbPsxDTMsMJoDQes"
I add 0 * n to r (first iteration of first loop)
Calculate Q with R, (first iteration of second loop) it is invalid
continue
Calculate Q with -R, (second iteration of second loop) it is valid
break.

The byte should be 32 meaning only 1 is added (27 + 4 + 1). Trying to figure out why 1 was chosen based on above operation?

You can think of the recovery id being a bit field of length two. Bit 0 indicates whether you should use R or -R. Bit 1 indicates whether R.x overflows n. So in this case, you have the bitfield be 01 = 1. Bit 1 is 0 because you do not overflow n (x=x, not x=x+n). Bit 0 is 1 because you are using -R.

Furthermore, this does in fact correspond to the loop. If instead of counting the number of operations that you do, count the number of Q's that you generate. If you put each Q into a list in the order that you generate them (including invalid ones), the recovery id is the index of the correct Q. In this case, Q[0] was invalid, Q[1] is the one you want. So the recovery id is 1.

Another way to look at this is to say the outer for loop is j from 0 to h (h=1 for secp256k1) and the inner loop is k from 0 to 1 (instead of 1 to 2 used in sec1). Then you add j and k together to get the recovery id. In this example, j = 0, and k = 1, so the recovery id is 1.

[Coding Enthusiast]

OK, this is what I have understood so far. There are two methods to get the "recovery ID". I am 99% sure about the first method and have tested it but I am not sure at all about the second so someone please shed some light on it:

Method 1 (Finding recId after signing or from r and s integers):
This is basically working backwards and is the steps defined in section 4.1.6 of Standards for Efficient Cryptography: 1. The recId is the index of the valid public key among all possible public keys that these steps recover if followed exactly as the documentation.

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:

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!

* 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.

[achow101]

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:

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.

[Coding Enthusiast]

Thanks a lot for the explanations.

27 = lower X even Y. 28 = lower X odd Y. 29 = higher X even Y. 30 = higher X odd Y.

That comment didn't make sense mainly because it says nothing about when s is being replaced by -s and I was initially trying to figure out how it is implemented in the code and without that little part the result will be false specially since most of the times s is replaced by -s.

A random example from my unit tests that I kept checking against:

Code:

key=0x4c4a90ace8ef549428b7ad24c8ca8940f130e4a32653bd3e88159ebb8ea0b775
message(utf8)=RDCaaa12234
R.x=111298013310039999727697889470430012371955796234135497681489525089601162729219
R.y=85994739553350295227584036738266368184641250776239259839118099187520698057269
s=63478024937324404321232340287682534731003226978885669652358186946685961083092

lower x + odd y = 28
BUT high s so it should be 27! and it is.

Code:

        public Signature Sign(byte[] data, byte[] key)
        {
            BigInteger e = CalculateE(data);

            // do something about this loop, it is currently pointless
            // possibly change kGenerator so that it can generate the next k value
            for (int i = 0; i < 100; i++)
            {
                Rfc6979 kgen = new Rfc6979(curve.N, hashSize);
                BigInteger k = kgen.GetK(data, key.ToBigInt(true, true));

                EllipticCurvePoint rp = ScalarMult(k, curve.G);
                byte v = (byte)(((rp.X > curve.N) ? 2 : 0) | (rp.Y.IsEven ? 0 : 1));

                BigInteger r = rp.X % curve.N;
                if (r == 0)
                {
                    continue;
                }

                BigInteger s = InverseMod(k, curve.N) * (e + (r * key.ToBigInt(true, true))) % curve.N;

                if (s == 0 || s > curve.N)
                {
                    continue;
                }
                if (s > curve.N / 2)
                {
                    v ^= 1;
                    s = curve.N - s;
                }

                //the following conditions based on that comment alone do not work
                //if (rp.X < curve.N && rp.Y.IsEven)
                //{
                //    v = 0;
                //}
                //else if (rp.X < curve.N && !rp.Y.IsEven)
                //{
                //    v = 1;
                //}
                //else if (rp.X > curve.N && rp.Y.IsEven)
                //{
                //    v = 2;
                //}
                //else if (rp.X > curve.N && !rp.Y.IsEven)
                //{
                //    v = 3;
                //}

                return new Signature(r, s, v);
            }

            throw new Exception("Failed");
        }

[amaclin1]

However, public key recovery will result in multiple public keys, up to 4 of them.

Why not to hash these public keys and compare up to 4 results with provided address?  

OK, i understand that today is too late to change this behavoiur