Repository: rust-bitcoin/rust-bitcoin (language: rust)

Issue:
NodeInfo Ord should be explicitly implemented
In our TaprootBuilder::with_huffman_tree function we sort Taproot trees by a tuple (u32, NodeInfo). The u32 is a user-provided "weight" representing the probability a branch will be taken. In case of ties, NodeInfo is used.

This means that if Ord changes on NodeInfo, it will change the shape of Taproot trees, potentially catastrophically changing addresses out from under people. We should make Ord explicit and document this dependence on order.


Discussion / hints:
IIUC the `NodeInfo` struct has members that will be compared as part of `Ord`. Should the types of `NodeInfo`'s members also explicitly implement `Ord`? At least one of the member/nested member types (`TapNodeHash`) is defined in a macro, so stripping Ord out might get a little hairy
I think it's ok to leave the derived `Ord` on `TapNodeHash`. The ordering on hashes is already a "do not change or great evil will come to you" thing.

Fix patch:
diff --git a/bitcoin/src/taproot/mod.rs b/bitcoin/src/taproot/mod.rs
index dbcb65193..88a6f1c55 100644
--- a/bitcoin/src/taproot/mod.rs
+++ b/bitcoin/src/taproot/mod.rs
@@ -7,7 +7,7 @@
 pub mod merkle_branch;
 pub mod serialized_signature;
 
-use core::cmp::Reverse;
+use core::cmp::{Ordering, Reverse};
 use core::fmt;
 use core::iter::FusedIterator;
 
@@ -789,7 +789,7 @@ impl DoubleEndedIterator for LeafNodes<'_> {
 ///
 /// You can use [`TaprootSpendInfo::from_node_info`] to a get a [`TaprootSpendInfo`] from the Merkle
 /// root [`NodeInfo`].
-#[derive(Debug, Clone, PartialOrd, Ord)]
+#[derive(Debug, Clone)]
 pub struct NodeInfo {
     /// Merkle hash for this node.
     pub(crate) hash: TapNodeHash,
@@ -799,6 +799,24 @@ pub struct NodeInfo {
     pub(crate) has_hidden_nodes: bool,
 }
 
+/// Explicitly implement Ord so future changes to NodeInfo (e.g. adding a new field) won't result in
+/// potentially changing addresses out from under users
+impl Ord for NodeInfo {
+    fn cmp(&self, other: &Self) -> Ordering {
+        match self.hash.cmp(&other.hash) {
+            Ordering::Equal => match self.leaves.cmp(&other.leaves) {
+                Ordering::Equal => self.has_hidden_nodes.cmp(&other.has_hidden_nodes),
+                other => other,
+            },
+            other => other,
+        }
+    }
+}
+
+impl PartialOrd for NodeInfo {
+    fn partial_cmp(&self, other: &NodeInfo) -> Option<Ordering> { Some(self.cmp(other)) }
+}
+
 impl PartialEq for NodeInfo {
     fn eq(&self, other: &Self) -> bool { self.hash.eq(&other.hash) }
 }


Test patch: