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. – David Grayson Feb 12 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 at 15:16
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 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 at 6:54
  • 1
    Recoverable pubkeys are something we invented for bitcoin message signing. It's not in any standard. – Pieter Wuille Mar 14 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 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 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). – Pieter Wuille Mar 17 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. – Pieter Wuille Mar 17 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. – Pieter Wuille Mar 17 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. – Pieter Wuille Mar 20 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. – Pieter Wuille Mar 21 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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