secp256k1 recovery id and how does the code work

Question

Here I have some questions regarding the recovery id (recid) defined in secp256k1 implementation. I had found few posts about how the recid is defined and what does it mean, also the source code (https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h).

As explain by bitcoin developers like Peter Wuille the recid is [27~30] for compressed pubkey and [31~34] for non-compressed pubkey. my question are:

1). from the secp256k1 code I did not find 27~34 value, all I found are 0~3; so where the difference come from?

2). I guess [27~30 and [31~34] such value set does not come from nonsense, but why using these two value set to map to [0~3]? Guess some tricky hidden inside--is that because of some trick on bit-level operation?

3). can someone help to explain this piece of code (come from https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h#L104-L112)

looks for me recid &2 (0x10) actually select recid=2/3 case.

and if recid !=2/3 all left code will be executed--is that understanding correct?

if (recid & 2) {
    if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
        return 0;
    }
    secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
}
if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
    return 0;
}

Answer 1

1). from the secp256k1 code I did not find 27~34 value, all I found are 0~3; so where the difference come from?

The serialization as a 65-byte signature + recovery byte happens on the Bitcoin Core side, not in libsecp256k1. See key.cpp:

vchSig[0] = 27 + rec + (fCompressed ? 4 : 0);

2). I guess [27~30 and [31~34] such value set does not come from nonsense, but why using these two value set to map to [0~3]? Guess some tricky hidden inside--is that because of some trick on bit-level operation?

There is nothing special about it. I just picked an arbitrary offset so the signature byte arrays wouldn't be confused with public keys or other signatures. But there is no special meaning to the number 27 (and in retrospect, it's a rather strange choice).

I'll try to expand this answer later to explain the code.

Answer 2

Put some comments embedded with code, still, some questions remain, hopefully, to be improved time by time.

The below code used in public key recovery method, is aiming for recover the R (rx, ry) from provided r and recid (0 or 1), for recid (2or3) case, simply reduce (provided r)-n.

{    if (recid & 2) {    /* if recid=2 or 3 */
    if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
        /* if fx >= p-n, not a valid signature */
        return 0;
    }
    /* else if fx < p-n, do fx=fx+n  */

    secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
}

next call up secp256k1_ge_set_xo_var(), for the recid=0/1 (recid 2/3 result will also be passed in?)

static int secp256k1_ge_set_xo_var(secp256k1_ge_t *r, const secp256k1_fe_t *x, int odd) {
/* for all below operation on Field (p), implicitly mod p */ 
secp256k1_fe_t x2, x3, c;
/* directly get rx */
r->x = *x;
/* calculate x2 = x^2 */
secp256k1_fe_sqr(&x2, x);
/* calculate x3 = x^2 *x = x^3 */
secp256k1_fe_mul(&x3, x, &x2);
/* set up infinity flag =0 as won't be 1 for below operation */
r->infinity = 0;
/* calculate c=x^3 +7 */
secp256k1_fe_set_int(&c, 7);
secp256k1_fe_add(&c, &x3);
/* calculate sqrt(c), put to ry*/
if (!secp256k1_fe_sqrt_var(&r->y, &c)) {
    return 0;
}
/* what does normalize mean ? */
secp256k1_fe_normalize_var(&r->y);
/* odd (recid passed in) could be 0(ry=even) or 1(ry=odd) */
/* exp: if odd=0, but odd(ry)=1 !=0, then do reverse*/
/* exp: if odd=1, also odd(ry)=1 == 1, then simply return */
if (secp256k1_fe_is_odd(&r->y) != odd) {
    /* for getting -R, i.e. -(r.y) one can simply do p-(r.y) */
    /* below likely does p*2*(1+1)-(r.y), why??*/
    secp256k1_fe_negate(&r->y, &r->y, 1);
}
return 1;

}