bip-0340: clarify that lift_x fails with out-of-range inputs #1334

pull jonasnick wants to merge 1 commits into bitcoin:master from jonasnick:liftx changing 1 files +3 −2
  1. jonasnick commented at 1:18 PM on June 20, 2022: contributor

    Without this commit, it's not defined what happens if x is not in range 0..p-1. However, lift_x may easily be called with out of range values. The reference implementation of lift_x correctly returns failure in such cases.

    CC: @real-or-random @sipa

  2. in bip-0340.mediawiki:112 in 5dfe3cce93 outdated
     108 | @@ -109,8 +109,9 @@ The following conventions are used, with constants as defined for [https://www.s
     109 |  ** The function ''bytes(P)'', where ''P'' is a point, returns ''bytes(x(P))''.
     110 |  ** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is ''x''.
     111 |  ** The function ''has_even_y(P)'', where ''P'' is a point for which ''not is_infinite(P)'', returns ''y(P) mod 2 = 0''.
     112 | -** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x''<ref>
     113 | -    Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = &plusmn;c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''.</ref> and ''has_even_y(P)'', or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode:
     114 | +** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..2<sup>256</sup>-1'', returns the point ''P'' for which ''x(P) = x''<ref>
    


    real-or-random commented at 1:40 PM on June 20, 2022:

    nit:

    ** The function ''lift_x(x)'', where ''x'' is a 256-bit unsigned integer, returns the point ''P'' for which ''x(P) = x''<ref>
    

    Simpler and consistent with two lines above. Or just "unsigned integer" would also be fine, that's even simpler.


    jonasnick commented at 1:45 PM on June 20, 2022:

    The size of the input is a helpful hint for implementors. Therefore went with your original suggestion.

  3. real-or-random commented at 1:40 PM on June 20, 2022: contributor

    ACK mod nit

  4. bip-0340: clarify that lift_x fails with out-of-range inputs
    Without this commit, it's not defined what happens if x is not in range 0..p-1.
    However, lift_x may easily be called with out of range values. The reference
    implementation of lift_x correctly returns failure in such cases.
    0144413e91
  5. jonasnick force-pushed on Jun 20, 2022
  6. real-or-random approved
  7. real-or-random commented at 1:53 PM on June 20, 2022: contributor

    ACK 0144413e91bf5d71b54126783acaf339422abe7e

  8. sipa commented at 3:15 PM on June 20, 2022: member

    ACK 0144413e91bf5d71b54126783acaf339422abe7e

  9. luke-jr merged this on Jul 25, 2022
  10. luke-jr closed this on Jul 25, 2022


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bips. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-04-19 11:10 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me