add `secp256k1_ec_pubkey

apoelstra commented at 5:34 pm on November 22, 2020: contributor

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.

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.

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.

real-or-random commented at 8:41 am on November 23, 2020: contributor

if secp256k1_memcmp_var exposed this API

Oh it does.

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)

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.

apoelstra force-pushed on Nov 23, 2020

apoelstra renamed this:
~~add `secp256k1_ec_pubkey_equal` and `secp256k1_ec_pubkey_leq` methods~~
add `secp256k1_ec_pubkey_cmp` method
on Nov 23, 2020

apoelstra commented at 7:10 pm on November 23, 2020: contributor

Replaced with a single _cmp method.

jonasnick commented at 8:14 pm on November 23, 2020: contributor

@apoelstra may I ask what you intend to use this for?

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)

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).

apoelstra commented at 8:56 pm on November 23, 2020: contributor

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

apoelstra cross-referenced this on Nov 23, 2020 from issue Implement lexigraphic ordering for PubKey by justinmoon

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…

apoelstra commented at 11:17 pm on November 25, 2020: contributor

Ironically, sorting by uncompressed encoding would be compatible with x-only keys.

elichai commented at 11:38 am on November 30, 2020: contributor

actually, what about adding these to xonly_pubkey too?

apoelstra commented at 6:42 pm on November 30, 2020: contributor

sure

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.

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.

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)

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.

real-or-random cross-referenced this on Mar 24, 2021 from issue Add MuSig Key Aggregation spec by jonasnick

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.

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?

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.

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.

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.

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.

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.

apoelstra force-pushed on Apr 20, 2021

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.

jonasnick commented at 3:05 pm on April 21, 2021: contributor

ACK mod nit

bitcoin-core deleted a comment on Apr 22, 2021

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

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.

real-or-random commented at 7:56 am on April 30, 2021:

Resolved in https://github.com/jonasnick/secp256k1/tree/2020-11--pubkey-comparisons-jn

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.

real-or-random commented at 7:56 am on April 30, 2021:

Resolved in https://github.com/jonasnick/secp256k1/tree/2020-11--pubkey-comparisons-jn

dr-orlovsky cross-referenced this on Apr 28, 2021 from issue impl PartialOrd/Ord for PublicKey by sanket1729

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

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.

add `secp256k1_ec_pubkey_cmp` method 0d9561ae87

add `secp256k1_xonly_pubkey_cmp` method 6eceec6d56

apoelstra force-pushed on May 6, 2021

apoelstra commented at 6:52 pm on May 6, 2021: contributor

Squashed in jonas’ commits.

jonasnick commented at 9:26 pm on May 6, 2021: contributor

ACK 6eceec6d566898a5c157630e47f95b260767026b

elichai commented at 9:31 am on May 7, 2021: contributor

Code review ACK 6eceec6d566898a5c157630e47f95b260767026b

real-or-random approved

real-or-random commented at 9:48 am on May 7, 2021: contributor

ACK 6eceec6d566898a5c157630e47f95b260767026b

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 :] )

jonasnick merged this on May 13, 2021

jonasnick closed this on May 13, 2021

jonasnick cross-referenced this on Jun 14, 2021 from issue Upstream PRs 831, 907, 903, 889, 918, 906, 928, 922, 933, Merge bitcoin-core/secp256k1#936: Fix gen_context/ASM build on ARM, 925, 937, 926, Merge bitcoin-core/secp256k1#940: contrib: Explain explicit header guards, 850, 930, 941, 846, 947, 662, 950 by jonasnick

add secp256k1_ec_pubkey_cmp method #850

add `secp256k1_ec_pubkey_cmp` method #850