1

I'm reading the spending section of BIP47:

Alice calculates a scalar shared secret using the x value of S: s = SHA256(Sx). If the value of s is not in the secp256k1 group, Alice MUST increment the index used to derive Bob's public key and try again.

Where S is a point on the elliptic curve and s is an integer to be used as a private key in subsequent sections.

My question is

  • What does it mean for the integer s to be in a group of points?

2 Answers 2

4

I believe it simply means: if s, when interpreted as an integer, is larger or equal to the curve order, one needs to restart and increment. The probability for this happening is negligible, as the curve order for secp256k1 is very close to 2256.

5
  • Thanks, it makes sense now. Is there any particular reason that we don't do a mod n in case the integer s happens to be greater than n? (n being the order of the group)
    – Merri
    Feb 7, 2023 at 16:34
  • 2
    I suspect the rationale is avoiding a bias towards the numbers in range 0...(2^256-N); the authors may have taken this from BIP32 which has a similar rule (which I'm the author of). In retrospect, this is dumb, because the number is so close to 2^256 that hitting a number in that range at all (much less resulting in an observable bias) only has a negligible probability. Feb 7, 2023 at 16:46
  • clearly explained and sorry, my reputation is too low to cast a +1 vote to the answer.
    – Merri
    Feb 7, 2023 at 16:54
  • One last question. I was viewing the source code for the two famous implementations of this standard, and I came across something I cannot understand; they are both comparing the bitlength of s to the bitlength of n (instead of comparing the numerical value). Do you have any comments on that? Impl 1 and, Impl 2
    – Merri
    Feb 8, 2023 at 5:13
  • 1
    That makes no sense to me; if the integer is the result of SHA256 output, it'll never exceed 256 bits. But again, all of this is unobservable anyway. Feb 8, 2023 at 14:46
-2

For any curve over any field, algebraic geometers are interested in an associated group called the Picard group. It is a certain quotient of the free abelian group on points of the curve. It consists of formal sums of points on the curve modulo those formal sums that come from looking at the zeroes and poles of rational functions. It is a very important tool in the study of algebraic curves. Why is an elliptic curve a group?

The smaller p2pkh addresses in Bitcoin are derived from a larger public key. This key is made from a scalar private key, the public key is basically an x and y coordinate on the secp256k1 elliptic curve derived from the scalar private key. If the private key is not within the curve group you cannot derive a valid x and y coordinate aka public key from it. In the case you presented s, the scalar shared secret, needs to be within the elliptic curve group because they are deriving a public key that someone could claim funds with from s. Deeper explanation: What is the math behind Bitcoin's elliptic curve?

Edit: The scalar and the curve order are integers, their elements are points.

10
  • Thank you for the answer. "If the private key is not within the curve group you cannot derive a valid x and y coordinate aka public key from it." I understand that secp256k1 forms a group. But the elements of this group are a set of planar points: (x,y). The private key s is a scalar/integer. What I do not understand is that how could an integer be part of a set whose elements are not integers but rather a bunch of ordered pairs (x,y).
    – Merri
    Feb 7, 2023 at 6:15
  • This basically explains it, the ordered pairs are derived from the scalar through this complex elliptic curve math. I can't really go much deeper into it as I am not an expert.
    – Poseidon
    Feb 7, 2023 at 6:37
  • to find the public key Q corresponding to a private key k, you have to "walk" k generator steps from the base point: Q = G+G+…+G [k-times] = kG Now secp256k1 is defined as y² = x³+7 mod P where P is P = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1 In secp256k1, the base point is G(Gx,Gy), where Gx = 550662... Gy = 326705... The addition of two points is defined as P + Q = R (xp, yp) + (xq, yq) = (xr, yr) Which works out to be xr = (yq - yp) / (xq - xp) - xp - xq yr = ((yq - yp) / (xq - xp)) × (xp - xr) - yp
    – Poseidon
    Feb 7, 2023 at 6:43
  • 2
    The curve order (= the number of points on the curve) is an integer. The elements of the curve are not integers. Feb 7, 2023 at 16:57
  • 1
    Every integer can be converted to a group element by multiplication with the generator. The language used is confusing, because there is no "in" the group or not, integers are integers and not group elements, and every integer can be converted to one (it loops around every (group order) steps, because cyclic group). The rule isn't there to make sure you end up in the group (that's always the case); it's there to prevent some group elements from being reached more frequently than others (but as I explain in my answer, this effect is so negligible it's also not actually worth caring about). Feb 7, 2023 at 21:35

Your Answer

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

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