add secp256k1_ec_pubkey_cmp method #850

pull apoelstra wants to merge 2 commits into bitcoin-core:master from apoelstra:2020-11--pubkey-comparisons changing 6 files +176 −5
  1. apoelstra commented at 5:34 pm on November 22, 2020: contributor
  2. real-or-random commented at 7:30 pm on November 22, 2020: contributor

    Concept ACK

    I would be easier to simply have a compare function which returns <0, ==0, or >0. Not sure which API is better. Did you think about this possibility?

    Implementation is then just a call to memcmp.

  3. apoelstra commented at 0:56 am on November 23, 2020: contributor
    I did think about this possibility, and if secp256k1_memcmp_var exposed this API then I probably would’ve just done a thin wrapper around that. But given that I had to do some extra work anyway, I felt that this API was more consistent than the libc one.
  4. apoelstra commented at 0:57 am on November 23, 2020: contributor
    I don’t feel strongly about it, I’m happy to implement the memcmp API if that’s what people want.
  5. real-or-random commented at 8:41 am on November 23, 2020: contributor

    if secp256k1_memcmp_var exposed this API

    Oh it does.

  6. elichai commented at 6:57 pm on November 23, 2020: contributor
    I also think that exposing a memcmp-like single API is somewhat nicer (but this is also ok)
  7. apoelstra commented at 7:02 pm on November 23, 2020: contributor
    Oh, neat, I misread the memcmp_var code. Ok, I’ll just expose a single function then.
  8. apoelstra force-pushed on Nov 23, 2020
  9. apoelstra renamed this:
    add `secp256k1_ec_pubkey_equal` and `secp256k1_ec_pubkey_leq` methods
    add `secp256k1_ec_pubkey_cmp` method
    on Nov 23, 2020
  10. apoelstra commented at 7:10 pm on November 23, 2020: contributor
    Replaced with a single _cmp method.
  11. jonasnick commented at 8:14 pm on November 23, 2020: contributor
    @apoelstra may I ask what you intend to use this for?
  12. apoelstra commented at 8:46 pm on November 23, 2020: contributor
    @jonasnick it’s needed for the sortedmulti descriptor and to use publickeys as keys in ordered sets (e.g. for PSBTs which should round-trip deterministically)
  13. sipa commented at 8:51 pm on November 23, 2020: contributor
    @apoelstra The sortedmulti descriptor sorts lexicographically by the pubkey serialization, which means that uncompressed keys will sort after compressed ones (BIP67 doesn’t support uncompressed keys whatsoever, but sortedmulti extends the definition to all keys).
  14. apoelstra commented at 8:56 pm on November 23, 2020: contributor
    sigh, ok, I guess we cannot support comparisons in this library
  15. apoelstra cross-referenced this on Nov 23, 2020 from issue Implement lexigraphic ordering for PubKey by justinmoon
  16. real-or-random commented at 9:35 am on November 25, 2020: contributor

    sigh, ok, I guess we cannot support comparisons in this library

    I’m not sure that sortedmulti stops us from exporting a comparison function that is compatible with compressed keys. This can be helpful for new applications which won’t use the uncompressed serialization anyway, e.g., sorting keys in multisig. Moreover, orderings are in general helpful for some data structures, e.g., if you want to binary searches in a large set of keys.

    A sad thing is that this ordering won’t be compatible with the lexicographical ordering on x-only keys…

  17. apoelstra commented at 11:17 pm on November 25, 2020: contributor
    Ironically, sorting by uncompressed encoding would be compatible with x-only keys.
  18. elichai commented at 11:38 am on November 30, 2020: contributor
    actually, what about adding these to xonly_pubkey too?
  19. apoelstra commented at 6:42 pm on November 30, 2020: contributor
    sure
  20. real-or-random commented at 9:48 am on December 1, 2020: contributor

    A week ago I argued that this is helpful but I’m not so sure anymore.

    If these functions are just serializing and memcmp’ing, they’re not essential, so we could leave this to the user.

    Pro: The user has to make a deliberate choice on an ordering, which may be good a thing here as things are complicated. Con: We may end up with many different orderings in the wild.

  21. apoelstra commented at 2:55 am on December 3, 2020: contributor
    As a user I find it extremely irritating to need to serialize in order to compare keys for equality, so I think we should expose that….and then it’s only epsilon more work to expose a total order.
  22. real-or-random commented at 11:01 am on December 3, 2020: contributor

    As a user I find it extremely irritating to need to serialize in order to compare keys for equality, so I think we should expose that….

    Agreed, equality is a no-brainer.

    and then it’s only epsilon more work to expose a total order.

    Indeed. But I think in common cases when you want an order, you need it because you’re going to serialize anyway, so the user probably won’t be extremely irritated in that case. @sipa @jonasnick @elichai What do you think? Should we expose a total order? (And if yes, which one? :P)

  23. sipa commented at 6:16 pm on December 18, 2020: contributor
    @apoelstra Would it be useful to just have an equality test function? That avoids the rathole of trying to predict what ordering the user needs.
  24. real-or-random cross-referenced this on Mar 24, 2021 from issue Add MuSig Key Aggregation spec by jonasnick
  25. apoelstra commented at 4:32 pm on March 29, 2021: contributor

    Is there any actual opposition to merging this? Or just uncertainty about what ordering hypothetical users might want?

    We could definitely use the xonly stuff (which is unambiguous) downstream now for MuSig so it would be cool to merge this.

  26. apoelstra commented at 4:34 pm on March 29, 2021: contributor
    If it would be easier, I can remove the legacy stuff and only add the xonly comparison?
  27. sipa commented at 4:53 pm on March 29, 2021: contributor

    utACK 48ac53b38068eb96474b785aaed4dbf1dc3dc586

    This ordering is sufficiently natural that we can just merge it, I think.

  28. in src/modules/extrakeys/main_impl.h:64 in 48ac53b380 outdated
    59+    unsigned char out1[32];
    60+    unsigned char out2[32];
    61+
    62+    VERIFY_CHECK(ctx != NULL);
    63+    ARG_CHECK(pk1 != NULL);
    64+    ARG_CHECK(pk2 != NULL);
    


    roconnor-blockstream commented at 9:00 pm on March 29, 2021:
    ARG_CHECK returns 0 for failure here, which isn’t an appropriate return condition for a cmp function. You can use ARG_CHECK_NO_RETURN, but you won’t have a post-condition that the pointer is non-NULL, and you will still need to handle that case. This can be done by zeroing the out1 and out2 buffers and only calling secp256k1_xonly_pubkey_serialize when pk is non NULL.
  29. in src/modules/extrakeys/main_impl.h:66 in 48ac53b380 outdated
    61+
    62+    VERIFY_CHECK(ctx != NULL);
    63+    ARG_CHECK(pk1 != NULL);
    64+    ARG_CHECK(pk2 != NULL);
    65+
    66+    CHECK(secp256k1_xonly_pubkey_serialize(ctx, out1, pk1));
    


    roconnor-blockstream commented at 11:37 pm on March 29, 2021:
    Not sure why these are CHECK instead of VERIFY_CHECK.

    jonasnick commented at 11:39 am on March 30, 2021:
    CHECK and VERIFY_CHECK are both not right here because they abort if the check fails, making it impossible to test the function with illegal keys. I’d suggest to remove the CHECK and instead make sure that out1 is all 0 if pubkey_serialize fails.
  30. jonasnick commented at 10:16 pm on April 3, 2021: contributor
    @apoelstra I wrote a fixup for this PR that makes the cmp functions define a consistent order even when dealing with NULL or illegal pubkeys by treating them as 0. It’s used in libsecp-zkp’s musig aggregation PR to add a sorting function for public keys.
  31. real-or-random commented at 8:52 am on April 13, 2021: contributor
    Oh CI fails again because this PR is too old and we switched to Cirrus CI. @apoelstra Can you quickly rebase this? This should solve it.
  32. apoelstra force-pushed on Apr 20, 2021
  33. in include/secp256k1.h:374 in f86f026b5a outdated
    370@@ -370,6 +371,21 @@ SECP256K1_API int secp256k1_ec_pubkey_serialize(
    371     unsigned int flags
    372 ) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
    373 
    374+/** Compare two public keys using lexicographic (of compressed serialization) sort
    


    jonasnick commented at 3:04 pm on April 21, 2021:
    nit: s/sort/order ? Same for xonly_pubkeys.
  34. jonasnick commented at 3:05 pm on April 21, 2021: contributor
    ACK mod nit
  35. bitcoin-core deleted a comment on Apr 22, 2021
  36. in include/secp256k1.h:381 in f86f026b5a outdated
    376+ *  Returns: <0 if the first public key is less than the second
    377+ *           >0 if the first public key is greater than the second
    378+ *           0 otherwise
    379+ *  Args: ctx:      a secp256k1 context object.
    380+ *  In:   pubkey1:  first public key to compare
    381+ *        pubkey2:  second public key to compare
    


    real-or-random commented at 3:15 pm on April 28, 2021:

    We should add “(cannot be NULL)” here (and nit: full stops), same below

    0 *  Args: ctx:      a secp256k1 context object (cannot be NULL).
    1 *  In:   pubkey1:  first public key to compare (cannot be NULL).
    2 *        pubkey2:  second public key to compare (cannot be NULL).
    

    jonasnick commented at 4:34 pm on April 28, 2021:
    This is implicit as per the discussion in #783 (comment)

    real-or-random commented at 4:39 pm on April 28, 2021:
    Okay, yes. Strictly speaking, we first need to add the line Unless explicitly stated all pointer arguments must not be NULL. in the header file (as done in #783) because currently we promise that the illegal_callback is only called for violations explicitly mentioned in the header.

    jonasnick commented at 5:03 pm on April 28, 2021:
    added that line in #926
  37. in include/secp256k1.h:378 in f86f026b5a outdated
    370@@ -370,6 +371,21 @@ SECP256K1_API int secp256k1_ec_pubkey_serialize(
    371     unsigned int flags
    372 ) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
    373 
    374+/** Compare two public keys using lexicographic (of compressed serialization) sort
    375+ *
    376+ *  Returns: <0 if the first public key is less than the second
    377+ *           >0 if the first public key is greater than the second
    378+ *           0 otherwise
    


    real-or-random commented at 3:16 pm on April 28, 2021:
    nit: maybe say 0 if the two public keys are equal… seems more readable.

  38. in src/secp256k1.c:343 in f86f026b5a outdated
    334+            memset(out[i], 0, sizeof(out[i]));
    335+        }
    336+        VERIFY_CHECK(out_size == sizeof(out[i]));
    337+    }
    338+    return secp256k1_memcmp_var(out[0], out[1], sizeof(out[0]));
    339+}
    


    real-or-random commented at 4:07 pm on April 28, 2021:

    I think we should call the illegal_callback also if a pubkey is non-null but invalid. This will almost always crash the program, which is much cleaner than trying to include invalid keys in the order.

    Independently of that question, I’m not sure if it’s a good idea to continue reading user-provided values if we know that something is wrong in the code of the user, so we should return immediately when we see an invalid value (after the illegal_callback).

    According to the description in the header, should the illegal_callback ever return (which is not recommended), then the return value of our function is undefined. So ARG_CHECK would be fine, even if it returns 0. If we still don’t like the return value of 0 in that case, we could something like

     0int secp256k1_ec_pubkey_cmp(const secp256k1_context* ctx, const secp256k1_pubkey* pubkey0, const secp256k1_pubkey* pubkey1) {
     1    unsigned char out[2][33];
     2    size_t out_size = sizeof(out[0]);
     3    const secp256k1_pubkey* pk[2];
     4    int i;
     5
     6    VERIFY_CHECK(ctx != NULL);
     7    pk[0] = pubkey0; pk[1] = pubkey1;
     8    for (i = 0; i < 2; i++) {
     9        int valid_pk;
    10        /* A public key that is NULL or invalid is treated as being smaller than
    11           any valid or invalid public key */
    12        ARG_CHECK_NO_RETURN(pk[i] != NULL);
    13        if (pk == NULL) return (i == 1 ? -1 : 1);
    14         
    15        valid_pk = secp256k1_ec_pubkey_serialize(ctx, out[i], &out_size, pk[i], SECP256K1_EC_COMPRESSED);
    16        ARG_CHECK_NO_RETURN(valid_pubkey);
    17        if (!valid_pubkey) return (i == 1 ? -1 : 1);
    18        
    19        VERIFY_CHECK(out_size == sizeof(out[i]));
    20    }
    21    return secp256k1_memcmp_var(out[0], out[1], sizeof(out[0]));
    22}
    

    This also has the advantage that we’ll never fire the illegal_callback more than once. I don’t think we promise that it will fire only once but so far we have adhered to that convention, which is helpful when writing tests.


    jonasnick commented at 4:35 pm on April 28, 2021:

    I think we should call the illegal_callback also if a pubkey is non-null but invalid.

    ec_pubkey_serialize will do that through pubkey_load. Or are you suggesting to do that explicitly here?

    So ARG_CHECK would be fine, even if it returns 0

    Yes, the lib doesn’t promise a proper return value in that case but if you give an inconsistent comparator to a sorting algorithm, it may never terminate. The goal was therefore to give a consistent response even if the keys are invalid. As far as I can see, your suggested code change doesn’t achieve that because for two invalid pubkeys A and B we have A < B and B < A.


  39. dr-orlovsky cross-referenced this on Apr 28, 2021 from issue impl PartialOrd/Ord for PublicKey by sanket1729
  40. jonasnick commented at 3:08 pm on April 29, 2021: contributor
    Tim and I noticed that the comparison functions can be simplified because pubkey_serialize already ARG_CHECKs pk != NULL. We can rely on that because we check it in the API tests. I pushed fixups that also add comments on the rationale and fix the nits mentioned in this thread. @apoelstra if you think that makes sense, feel free to cherry-pick and squash. https://github.com/jonasnick/secp256k1/tree/2020-11--pubkey-comparisons-jn
  41. real-or-random commented at 7:57 am on April 30, 2021: contributor
    @jonasnick Your branch looks good to me, I suggest we merge that one.
  42. add `secp256k1_ec_pubkey_cmp` method 0d9561ae87
  43. add `secp256k1_xonly_pubkey_cmp` method 6eceec6d56
  44. apoelstra force-pushed on May 6, 2021
  45. apoelstra commented at 6:52 pm on May 6, 2021: contributor
    Squashed in jonas’ commits.
  46. jonasnick commented at 9:26 pm on May 6, 2021: contributor
    ACK 6eceec6d566898a5c157630e47f95b260767026b
  47. elichai commented at 9:31 am on May 7, 2021: contributor
    Code review ACK 6eceec6d566898a5c157630e47f95b260767026b
  48. real-or-random approved
  49. real-or-random commented at 9:48 am on May 7, 2021: contributor
    ACK 6eceec6d566898a5c157630e47f95b260767026b
  50. in include/secp256k1_extrakeys.h:75 in 6eceec6d56
    66@@ -67,6 +67,21 @@ SECP256K1_API int secp256k1_xonly_pubkey_serialize(
    67     const secp256k1_xonly_pubkey* pubkey
    68 ) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
    69 
    70+/** Compare two x-only public keys using lexicographic order
    71+ *
    72+ *  Returns: <0 if the first public key is less than the second
    73+ *           >0 if the first public key is greater than the second
    74+ *           0 if the two public keys are equal
    75+ *  Args: ctx:      a secp256k1 context object.
    


    roconnor-blockstream commented at 1:40 pm on May 7, 2021:
    non-null comments here too?

    jonasnick commented at 4:16 pm on May 7, 2021:
    unnecessary if #926 gets merged (needs more ACKs :] )
  51. jonasnick merged this on May 13, 2021
  52. jonasnick closed this on May 13, 2021


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-10-30 03:15 UTC

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