1

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;
}
2
  • If you have one specific question, there should be one question mark, not four. Feb 12, 2021 at 18:11
  • Sorry for that--I think initially I had one "specific" question but when I was trying to draft the question, some more questions may be raised and it turned out better to make them seperately..
    – LeonMSH
    Feb 21, 2021 at 15:16

2 Answers 2

3

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.

5
  • Great thanks for the reply, didn't expect to get the original author helping on this;-) ... it took me some time to think why this number is selected. Waiting for more comments of the code.. for my Q3, from some other post I thought it would be due to when recid=2/3 means (x,y) sit on the location that satisfies (n<x<p)? But I did not understand the function of secp256k1_fe_cmp_var yet.
    – LeonMSH
    Feb 10, 2021 at 2:56
  • if possible, could you please help to explain the logic behind the if secp256k1_ge_set_xo_var(&x, &fx, recid & 1)? this piece of code looks not link to SEC standard document-- is that specific tricky to the secp256k1 curve?
    – LeonMSH
    Mar 14, 2021 at 6:54
  • 1
    Recoverable pubkeys are something we invented for bitcoin message signing. It's not in any standard. Mar 14, 2021 at 8:59
  • I can find the pub key recovery method here: secg.org/sec1-v2.pdf (CH4.1.6) but the detail implementation is not the same (it has no recover id) a recover id indeed help speed up the algorithm, but short of the reference of the algorithm--is there any more documentation can help to understand the logic behind these piece of code?
    – LeonMSH
    Mar 14, 2021 at 13:44
  • I paste one more post below, put all my understanding here if you can help to comment whether they are correct or not... if anything is wrong--would you please suggest the correct understanding?
    – LeonMSH
    Mar 16, 2021 at 4:40
0

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;

}

10
  • 2
    Everything is implicitly mod p. We set infinity=0 because we need to set infinity=0 or infinity1 in the output, and we know the result won't be infinity. Normalize means bring to canonical representation (secp256k1_fe can be temporarily "denormalized" which allows some faster operations, but isn't compatible with fe_is_odd, for example). fe_negate(a,b,n) just computes the negation of b and puts it in a; the n argument gives the maximum magnitude of the input (which is 1, because the input is normalized). Mar 17, 2021 at 4:42
  • 2
    For dealing with recid=2 or recid=3, that means we have r = R.x - n (remember: r = R.x mod n, so either r = R.x or r = R.x - n). We're given r in the signature, but we need to recover the full R.x coordinate. If recid=2 or recid=3, we need to add n: R.x = r + n. Mar 17, 2021 at 4:45
  • 2
    The deal with normalization: field elements are represented as 5 52-bit "limbs" (on 64-bit symbols). Those limbs are allowed to overflow (be larger than 2^52), which permits addition/negation without carry (much faster for some operation); for addition you just add the corresponding limbs; for negation you subtract it from a multiple of limbs representing n... but you need to know how big the input is allowed to be (as you need to make sure no limb can result in a negative number). That's why fe_negate takes in a magnitude argument. Mar 17, 2021 at 4:54
  • 1
    The scalar factor in point multiplication is indeed modulo n. But all variables in this snippet ("fe" types) are modulo p. Mar 20, 2021 at 3:11
  • 2
    1) Yes, computing the sqrt(x^3+7) always gives you the square root that is a square itself, but that could be even or odd. By comparing its parity with recid and conditionally negating, you get the intended result. 2) Yes. Mar 21, 2021 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.