user136404: 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

user208: 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.

136404: <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>
 208: <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>
