add `secp256k1_ec_pubkey_cmp` method #850

apoelstra · 2020-11-22T17:34:09Z

No description provided.

real-or-random · 2020-11-22T19:30:25Z

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 · 2020-11-23T00:56:15Z

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 · 2020-11-23T00:57:10Z

I don't feel strongly about it, I'm happy to implement the memcmp API if that's what people want.

real-or-random · 2020-11-23T08:41:25Z

if secp256k1_memcmp_var exposed this API

Oh it does.

elichai · 2020-11-23T18:57:49Z

I also think that exposing a memcmp-like single API is somewhat nicer (but this is also ok)

apoelstra · 2020-11-23T19:02:28Z

Oh, neat, I misread the memcmp_var code. Ok, I'll just expose a single function then.

apoelstra · 2020-11-23T19:10:06Z

Replaced with a single _cmp method.

jonasnick · 2020-11-23T20:14:23Z

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

apoelstra · 2020-11-23T20:46:55Z

@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 · 2020-11-23T20:51:04Z

@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 · 2020-11-23T20:56:43Z

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

real-or-random · 2020-11-25T09:35:21Z

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 · 2020-11-25T23:17:44Z

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

elichai · 2020-11-30T11:38:53Z

actually, what about adding these to xonly_pubkey too?

apoelstra · 2020-11-30T18:42:49Z

sure

real-or-random · 2020-12-01T09:48:22Z

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 · 2020-12-03T02:55:39Z

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 · 2020-12-03T11:01:35Z

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 · 2020-12-18T18:16:45Z

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

apoelstra · 2021-03-29T16:32:49Z

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 · 2021-03-29T16:34:33Z

If it would be easier, I can remove the legacy stuff and only add the xonly comparison?

sipa · 2021-03-29T16:53:39Z

utACK 48ac53b

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

roconnor-blockstream · 2021-03-29T21:00:32Z

src/modules/extrakeys/main_impl.h

+
+    VERIFY_CHECK(ctx != NULL);
+    ARG_CHECK(pk1 != NULL);
+    ARG_CHECK(pk2 != NULL);


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.

roconnor-blockstream · 2021-03-29T23:37:59Z

src/modules/extrakeys/main_impl.h

+    ARG_CHECK(pk1 != NULL);
+    ARG_CHECK(pk2 != NULL);
+
+    CHECK(secp256k1_xonly_pubkey_serialize(ctx, out1, pk1));


Not sure why these are CHECK instead of VERIFY_CHECK.

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 · 2021-04-03T22:16:53Z

@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 · 2021-04-13T08:52:04Z

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.

jonasnick

ACK mod nit

include/secp256k1.h

real-or-random · 2021-04-28T15:15:41Z

include/secp256k1.h

+ *  Args: ctx:      a secp256k1 context object.
+ *  In:   pubkey1:  first public key to compare
+ *        pubkey2:  second public key to compare


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

Suggested change

* Args: ctx: a secp256k1 context object.

* In: pubkey1: first public key to compare

* pubkey2: second public key to compare

* Args: ctx: a secp256k1 context object (cannot be NULL).

* In: pubkey1: first public key to compare (cannot be NULL).

* pubkey2: second public key to compare (cannot be NULL).

This is implicit as per the discussion in #783 (comment)

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.

added that line in #926

include/secp256k1.h

src/secp256k1.c

jonasnick · 2021-04-29T15:08:40Z

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 · 2021-04-30T07:57:28Z

@jonasnick Your branch looks good to me, I suggest we merge that one.

apoelstra · 2021-05-06T18:52:51Z

Squashed in jonas' commits.

jonasnick

ACK 6eceec6

elichai · 2021-05-07T09:31:36Z

Code review ACK 6eceec6

real-or-random

ACK 6eceec6

roconnor-blockstream · 2021-05-07T13:40:53Z

include/secp256k1_extrakeys.h

+ *  Returns: <0 if the first public key is less than the second
+ *           >0 if the first public key is greater than the second
+ *           0 if the two public keys are equal
+ *  Args: ctx:      a secp256k1 context object.


non-null comments here too?

unnecessary if #926 gets merged (needs more ACKs :] )

…_cmp` Summary: Allows comparing `secp256k1_pubkey` and `secp256k1_xonly_pubkey` respectively, to establish an order between them. This is a backport of [[ bitcoin-core/secp256k1#850 | secp256k1#850 ]] and [[ bitcoin-core/secp256k1#926 | secp256k1#926 ]]. We need this for porting `rust-secp256k1` to the secp256k1 library of this repo. Test Plan: `ninja check-secp256k1` Reviewers: #bitcoin_abc, Fabien Reviewed By: #bitcoin_abc, Fabien Differential Revision: https://reviews.bitcoinabc.org/D16957

apoelstra force-pushed the 2020-11--pubkey-comparisons branch from 0831038 to edcc076 Compare November 23, 2020 19:09

apoelstra changed the title ~~add secp256k1_ec_pubkey_equal and secp256k1_ec_pubkey_leq methods~~ add secp256k1_ec_pubkey_cmp method Nov 23, 2020

apoelstra mentioned this pull request Nov 23, 2020

Implement lexigraphic ordering for PubKey rust-bitcoin/rust-secp256k1#248

Merged

real-or-random mentioned this pull request Mar 24, 2021

Add MuSig Key Aggregation spec BlockstreamResearch/secp256k1-zkp#120

Merged

roconnor-blockstream reviewed Mar 29, 2021

View reviewed changes

apoelstra force-pushed the 2020-11--pubkey-comparisons branch from c0eaa2a to f86f026 Compare April 20, 2021 17:48

jonasnick reviewed Apr 21, 2021

View reviewed changes

include/secp256k1.h Outdated Show resolved Hide resolved

bitcoin-core deleted a comment from ramsemune Apr 22, 2021

real-or-random reviewed Apr 28, 2021

View reviewed changes

dr-orlovsky mentioned this pull request Apr 28, 2021

impl PartialOrd/Ord for PublicKey rust-bitcoin/rust-bitcoin#524

Closed

apoelstra added 2 commits May 6, 2021 18:36

add secp256k1_ec_pubkey_cmp method

0d9561a

add secp256k1_xonly_pubkey_cmp method

6eceec6

apoelstra force-pushed the 2020-11--pubkey-comparisons branch from f86f026 to 6eceec6 Compare May 6, 2021 18:52

jonasnick reviewed May 6, 2021

View reviewed changes

real-or-random approved these changes May 7, 2021

View reviewed changes

roconnor-blockstream reviewed May 7, 2021

View reviewed changes

jonasnick merged commit 202a030 into bitcoin-core:master May 13, 2021

add secp256k1_ec_pubkey_cmp method #850

add secp256k1_ec_pubkey_cmp method #850

Conversation

apoelstra commented Nov 22, 2020

real-or-random commented Nov 22, 2020

apoelstra commented Nov 23, 2020

apoelstra commented Nov 23, 2020

real-or-random commented Nov 23, 2020

elichai commented Nov 23, 2020

apoelstra commented Nov 23, 2020

apoelstra commented Nov 23, 2020

jonasnick commented Nov 23, 2020

apoelstra commented Nov 23, 2020

sipa commented Nov 23, 2020 • edited Loading

apoelstra commented Nov 23, 2020

real-or-random commented Nov 25, 2020

apoelstra commented Nov 25, 2020

elichai commented Nov 30, 2020

apoelstra commented Nov 30, 2020

real-or-random commented Dec 1, 2020

apoelstra commented Dec 3, 2020

real-or-random commented Dec 3, 2020 • edited Loading

sipa commented Dec 18, 2020

apoelstra commented Mar 29, 2021

apoelstra commented Mar 29, 2021

sipa commented Mar 29, 2021

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jonasnick commented Apr 3, 2021

real-or-random commented Apr 13, 2021

jonasnick left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

jonasnick commented Apr 29, 2021

real-or-random commented Apr 30, 2021

apoelstra commented May 6, 2021

jonasnick left a comment

Choose a reason for hiding this comment

elichai commented May 7, 2021

real-or-random left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

add `secp256k1_ec_pubkey_cmp` method #850

add `secp256k1_ec_pubkey_cmp` method #850

sipa commented Nov 23, 2020 •

edited

Loading

real-or-random commented Dec 3, 2020 •

edited

Loading