# How does the BIP340 lift_x algorithm work?

Couple questions of code that I'm reviewing trying to learn schnorr sigs.

Why do we want an odd private key? I see even tests on the private key and then subtract it from the SECP256K1 Order to get an odd point?

Schnorr verify seems to need the square root of a point ,specifically this code here, why and what is this doing? I'm confused on what is happening conceptually.

``````def lift_x(x: int) -> Optional[Point]:
if x >= p:
return None
y_sq = (pow(x, 3, p) + 7) % p #<-the curve
y = pow(y_sq, (p + 1) // 4, p) # why is this __floordiv__ 4?
if pow(y, 2, p) != y_sq:
return None
return (x, y if y & 1 == 0 else p-y) # make y odd if there is a sqrt?
``````

Thanks

``````def lift_x(x: int) -> Optional[Point]:
``````

This is a function that given an X coordinate, computes one of the two corresponding Y coordinates on the curve; specifically, the even one.

Every possible value in the field of coordinates (integers modulo p, where p = 2256 - 232 - 977) has exactly 0 points on the curve y2 = x3 + 7, or exactly two. In case there are two points with a given X coordinate, the corresponding Y coordinates will be each other's negation (modulo p), and one will be even, and one will be odd. This lift_x function returns the one with the even Y.

``````    y_sq = (pow(x, 3, p) + 7) % p #<-the curve
``````

This computes y_sq = y2, using the fact that it equals x3 + 7 (mod p), using the curve equation.

``````    y = pow(y_sq, (p + 1) // 4, p) # why is this __floordiv__ 4?
``````

This computes the square root y of the value y_sq we determined in the previous now. In general, modular square roots can be computed using the Tonelli-Shanks algorithm, but for the secp256k1 modulus, this algorithm simply boils down to computing y_sq(p+1)/4 mod p. In Python, we need to write this (p+1)/4 as `(p+1)//4` because we want exact integer arithmetic. `(p+1)/4` would compute an approximate floating point number only.

``````    if pow(y, 2, p) != y_sq:
return None
``````

This verifies whether the computed value y is actually the modular square root of y_sq. If the input x value was not a valid X coordinate on the curve, then x3 + 7 won't be a square, and thus won't have a square root. However, the formula y_sq(p+1)/4 always yields a result, even when y_sq doesn't have a square root. So we need to check whether y2 = y_sq. If not, we return `None` immediately: the input X has no corresponding Y coordinates.

``````    return (x, y if y & 1 == 0 else p-y) # make y odd if there is a sqrt?
``````

This simply negates y (modulo p) if y is odd, thereby finding the other (even) solution. This guarantees returning the even Y coordinate out of the two solutions.

• Thanks a lot. I think I see it now, it looks like it is for consistency. When we do ecc point add, the result will be significantly different for the point that has a 'negative' 7 than the point with a 'positive'? Or does it have something to do with key compression? Commented Oct 16, 2022 at 23:09
• Given a fixed X coordinate, the two curve points with that coordinate are each other's negation (in ECC logic, `-(x,y) = (x,-y)`). So the choice very much matters: `point1 + lift_x_odd(x2) = point1 - lift_x(x2)` (so it'd be negation instead of addition), where `lift_x_odd` is a hypothetical variant of `lift_x` which maps to the odd Y coordinate rather than the even one. Note that it's not a negative/positive 7 (changing the sign of the 7 would be changing the curve equation, rendering it entirely insecure). All we're doing is choosing which of the solutions for Y to pick. Commented Oct 17, 2022 at 18:50
• Thanks, that really clears things up for me and furthers my understanding. Commented Oct 18, 2022 at 18:28