Compare `COutPoints` lexicographically

josibake commented at 9:05 am on May 6, 2024: member

Broken out from #28122

BIP352 requires the smallest output lexicographically, which is my primary motivation for adding this as the default way of compare COutPoints (e.g. https://github.com/bitcoin/bitcoin/blob/5b06ccf1dc63f56dbc35368a37b9a72af671f15f/src/common/bip352.cpp#L149)

Outside of needing this for #28122 , I think it makes more sense to compare COutPoints by their serialization for any use case that needs ordering since the serialization is what appears in the final transaction. I also didn’t see any existing places in the code where we order outpoints, so this change doesn’t conflict with any current use cases that I can see. If there is a need to order inputs by their vout field (e.g. for an RPC output), something like

0std::sort(outpoints.begin(), outpoints.end(), [](const COutPoint& a, const COutPoint& b) { return a.vout < b.vout; });

seems preferable, rather than first comparing a.hash < b.hash.

DrahtBot commented at 9:05 am on May 6, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

in src/primitives/transaction.h:50 in e623d8a05a outdated

43@@ -43,7 +44,10 @@ class COutPoint
44 
45     friend bool operator<(const COutPoint& a, const COutPoint& b)
46     {
47-        return std::tie(a.hash, a.n) < std::tie(b.hash, b.n);
48+        DataStream ser_a, ser_b;
49+        ser_a << a;
50+        ser_b << b;
51+        return Span{ser_a} < Span{ser_b};

darosior commented at 9:18 am on May 6, 2024:

I fail to see how it’s not functionally equivalent? (but much less efficient)

josibake commented at 9:33 am on May 6, 2024:

See https://github.com/bitcoin/bitcoin/blob/246e2a24c5460504c799fbc6312ef075f0ca4e72/src/test/data/bip352_send_and_receive_vectors.json#L383 for an example of how the old method (a.hash < b.hash, a.vout < b.vout) will yield a different ordering than comparing outpoints lexicographically.

josibake commented at 10:15 am on May 6, 2024:

Although, to your point, a.hash < b.hash is doing a lexicographic comparison:

https://github.com/bitcoin/bitcoin/blob/e623d8a05ad4e2b81e19c4f10b22e2ce4db35b8d/src/uint256.h#L54

So maybe it would be more efficient to just serialize a.vout, b.vout as little-endian here, rather than serializing the whole COutPoint?

darosior commented at 11:29 am on May 6, 2024:

But 1 sorts before 256 lexicographically? So it’s lexicographical serialized order, i see.

josibake commented at 12:55 pm on May 6, 2024:

Yep, good point. I added a comment to clarify that this is a lexicographic sort on the serialized outpoint. I think this is preferable to what we were doing before since its based on the protocol definition of an outpoint: <32-byte txid, little-endian>:<4-byte vout, little-endian>.

laanwj added the label Wallet on May 6, 2024

Sjors commented at 11:03 am on May 6, 2024: member

Don’t forget to add a source comment that BIP352 depends on this exact ordering. Either in this PR or as a commit in #28122.

Compare COutPoints lexicographically

Comparing outpoints lexicographically is required for BIP352, but also
generally a less ambigious way to compare outpoints considering this
will match any orderings applied to the serialized transaction.

e11d764a6c

josibake force-pushed on May 6, 2024

josibake commented at 1:00 pm on May 6, 2024: member

Don’t forget to add a source comment that BIP352 depends on this exact ordering. Either in this PR or as a commit in #28122.

Hm, I don’t think we need a BIP352 specific comment here? I’d argue if we are going to sort outpoints, we should be sorting them based on their protocol definition, regardless of BIP352. In fact, when writing BIP352 we already assumed this was the case which is why we defined the outpoint sorting in BIP352 to be done lexicographically on the outpoint serialization. It was only recently that someone pointed out that Bitcoin Core wasn’t sorting lexicographically based on the serialization and instead was comparing the txids lexicographically but comparing the vouts as integers.

sipa commented at 1:25 pm on May 6, 2024: member

This seems unnecessarily unnatural and inefficient to use as a default sort order for this type.

If BIP352 defines its own normative sort order, I think it’s better to have a specialized BIP352Comparator class that implements it, and use that in the BIP352 code?

That also has the advantage of not tying the two together; someone might come in and change the order back to the current ordering for performance or simplicity reasons, and break the BIP352 code.

josibake commented at 2:39 pm on May 6, 2024: member

This seems unnecessarily unnatural and inefficient to use as a default sort order for this type.

If BIP352 defines its own normative sort order, I think it’s better to have a specialized BIP352Comparator class that implements it, and use that in the BIP352 code?

That also has the advantage of not tying the two together; someone might come in and change the order back to the current ordering for performance or simplicity reasons, and break the BIP352 code.

Personally, I find it more confusing that we have three different ways we can compare outpoints, so lexicographic comparison based on the 36-byte serialization seemed the simplest default. Fair points regarding efficiency and not tightly coupling the default sort with a specific use case, though. Happy to close this in favor of a BIP352Comparator.

josibake closed this on May 6, 2024

josibake deleted the branch on May 6, 2024

bitcoin deleted a comment on May 7, 2024

Compare COutPoints lexicographically #30046

Code Coverage

Reviews

Compare `COutPoints` lexicographically #30046