<pre class="lang-py prettyprint-override"><code>def lift_x(x: int) -&gt; Optional[Point]:
</code></pre>
<p>This is a function that given an X coordinate, computes one of the two corresponding Y coordinates on the curve; specifically, the even one.</p>
<p>Every possible value in the field of coordinates (integers modulo <em>p</em>, where <em>p = 2<sup>256</sup> - 2<sup>32</sup> - 977</em>) has exactly 0 points on the curve <em>y<sup>2</sup> = x<sup>3</sup> + 7</em>, or exactly two. In case there are two points with a given X coordinate, the corresponding Y coordinates will be each other's negation <em>(modulo p)</em>, and one will be even, and one will be odd. This <em>lift_x</em> function returns the one with the even Y.</p>
<pre class="lang-py prettyprint-override"><code>    y_sq = (pow(x, 3, p) + 7) % p #&lt;-the curve
</code></pre>
<p>This computes <em>y_sq = y<sup>2</sup></em>, using the fact that it equals <em>x<sup>3</sup> + 7</em> (<em>mod p</em>), using the curve equation.</p>
<pre class="lang-py prettyprint-override"><code>    y = pow(y_sq, (p + 1) // 4, p) # why is this __floordiv__ 4?
</code></pre>
<p>This computes the square root <em>y</em> of the value <em>y_sq</em> we determined in the previous now. In general, modular square roots can be computed using the <a href="https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm" rel="nofollow noreferrer">Tonelli-Shanks algorithm</a>, but for the secp256k1 modulus, this algorithm simply boils down to computing <em>y_sq<sup>(p+1)/4</sup> mod p</em>. In Python, we need to write this <em>(p+1)/4</em> as <code>(p+1)//4</code> because we want exact integer arithmetic. <code>(p+1)/4</code> would compute an approximate floating point number only.</p>
<pre class="lang-py prettyprint-override"><code>    if pow(y, 2, p) != y_sq:
        return None
</code></pre>
<p>This verifies whether the computed value <em>y</em> is actually the modular square root of <em>y_sq</em>. If the input <em>x</em> value was not a valid X coordinate on the curve, then <em>x<sup>3</sup> + 7</em> won't be a square, and thus won't have a square root. However, the formula <em>y_sq<sup>(p+1)/4</sup></em> always yields a result, even when <em>y_sq</em> doesn't have a square root. So we need to check whether <em>y<sup>2</sup> = y_sq</em>. If not, we return <code>None</code> immediately: the input X has no corresponding Y coordinates.</p>
<pre class="lang-py prettyprint-override"><code>    return (x, y if y &amp; 1 == 0 else p-y) # make y odd if there is a sqrt?
</code></pre>
<p>This simply negates <em>y</em> (modulo <em>p</em>) if <em>y</em> is odd, thereby finding the other (even) solution. This guarantees returning the even Y coordinate out of the two solutions.</p>

CC BY-SA 4.0
2022-10-16T23:09:45.197Z
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?
Kaizen
CC BY-SA 4.0
2022-10-17T18:50:43.667Z
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.
Pieter Wuille
CC BY-SA 4.0
2022-10-18T18:28:59.520Z
Thanks, that really clears things up for me and furthers my understanding.
Kaizen
CC BY-SA 4.0
2022-10-16T05:50:31.280Z
2022-10-17T18:57:48.367Z
2022-10-17T18:57:48.367Z
Pieter Wuille
<p>Couple questions of code that I'm reviewing trying to learn schnorr sigs.</p>
<p>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?</p>
<p>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.</p>
<pre class="lang-py prettyprint-override"><code>def lift_x(x: int) -&gt; Optional[Point]:
    if x &gt;= p:
        return None
    y_sq = (pow(x, 3, p) + 7) % p #&lt;-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 &amp; 1 == 0 else p-y) # make y odd if there is a sqrt?
</code></pre>
<p>Thanks</p>

<python><cryptography><secp256k1><schnorr-signatures><x-only-pubkeys>
How does the BIP340 lift_x algorithm work?
Kaizen
# How does the BIP340 lift_x algorithm work?

(Asked by: username_0 on 2022-10-16)

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.

```py
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

**Tags:** python, cryptography, secp256k1, schnorr-signatures, x-only-pubkeys


---

## 1 answers

### Answer by username_1 on 2022-10-16. Score: 4

```py
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.

```py
    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.

```py
    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](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_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.

```py
    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.

```py
    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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: Thanks, that really clears things up for me and furthers my understanding.  

---

