Repository: rust-bitcoin/rust-bitcoin (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.

Pull request description:
Explicitly define Ord for NodeInfo
Fixes #3654 by explicitly defining Ord so that we avoid potentially catastrophically changing addresses out from under users

Patch:
diff --git a/bitcoin/src/blockdata/transaction.rs b/bitcoin/src/blockdata/transaction.rs
index 35c0ff60..6a91bcc5 100644
--- a/bitcoin/src/blockdata/transaction.rs
+++ b/bitcoin/src/blockdata/transaction.rs
@@ -1709,6 +1709,12 @@ fn effective_value_weight_does_not_overflow() {
         assert!(eff_value.is_none());
     }
 
+    #[test]
+    fn effective_value_value_does_not_overflow() {
+        let eff_value = effective_value(FeeRate::ZERO, Weight::ZERO, Amount::MAX);
+        assert!(eff_value.is_none());
+    }
+
     #[test]
     fn txin_txout_weight() {
         // [(is_segwit, tx_hex, expected_weight)]
diff --git a/bitcoin/src/psbt/mod.rs b/bitcoin/src/psbt/mod.rs
index 6de326a1..e1e64dde 100644
--- a/bitcoin/src/psbt/mod.rs
+++ b/bitcoin/src/psbt/mod.rs
@@ -2159,7 +2159,7 @@ fn test_fee() {
         let output_1_val = Amount::from_sat(100_000_000);
         let prev_output_val = Amount::from_sat(200_000_000);
 
-        let t = Psbt {
+        let mut t = Psbt {
             unsigned_tx: Transaction {
                 version: transaction::Version::TWO,
                 lock_time: absolute::LockTime::from_consensus(1257139),
@@ -2253,6 +2253,13 @@ fn test_fee() {
             Error::NegativeFee => {}
             e => panic!("unexpected error: {:?}", e),
         }
+        // overflow
+        t.unsigned_tx.output[0].value = Amount::MAX;
+        t.unsigned_tx.output[1].value = Amount::MAX;
+        match t.fee().unwrap_err() {
+            Error::FeeOverflow => {}
+            e => panic!("unexpected error: {:?}", e),
+        }
     }
 
     #[test]
diff --git a/bitcoin/src/taproot/mod.rs b/bitcoin/src/taproot/mod.rs
index dbcb6519..88a6f1c5 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 @@ fn next_back(&mut self) -> Option<Self::Item> { self.leaf_iter.next_back() }
 ///
 /// 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) }
 }
diff --git a/units/src/amount/unsigned.rs b/units/src/amount/unsigned.rs
index 9b96c4d5..fd5b0613 100644
--- a/units/src/amount/unsigned.rs
+++ b/units/src/amount/unsigned.rs
@@ -65,7 +65,7 @@ impl Amount {
     /// The minimum value of an amount.
     pub const MIN: Amount = Amount::ZERO;
     /// The maximum value of an amount.
-    pub const MAX: Amount = Amount::MAX_MONEY;
+    pub const MAX: Amount = Amount(u64::MAX);
     /// The number of bytes that an amount contributes to the size of a transaction.
     pub const SIZE: usize = 8; // Serialized length of a u64.
 
@@ -120,11 +120,6 @@ pub fn from_str_in(s: &str, denom: Denomination) -> Result<Amount, ParseAmountEr
                 OutOfRangeError::negative(),
             )));
         }
-        if satoshi > Self::MAX.0 {
-            return Err(ParseAmountError(ParseAmountErrorInner::OutOfRange(
-                OutOfRangeError::too_big(false),
-            )));
-        }
         Ok(Amount::from_sat(satoshi))
     }
 
@@ -219,7 +214,7 @@ pub fn to_string_with_denomination(self, denom: Denomination) -> String {
     pub const fn checked_add(self, rhs: Amount) -> Option<Amount> {
         // No `map()` in const context.
         match self.0.checked_add(rhs.0) {
-            Some(res) => Amount(res).check_max(),
+            Some(res) => Some(Amount(res)),
             None => None,
         }
     }
@@ -241,7 +236,7 @@ pub const fn checked_sub(self, rhs: Amount) -> Option<Amount> {
     pub const fn checked_mul(self, rhs: u64) -> Option<Amount> {
         // No `map()` in const context.
         match self.0.checked_mul(rhs) {
-            Some(res) => Amount(res).check_max(),
+            Some(res) => Some(Amount(res)),
             None => None,
         }
     }
@@ -337,15 +332,6 @@ pub fn to_signed(self) -> Result<SignedAmount, OutOfRangeError> {
             Ok(SignedAmount::from_sat(self.to_sat() as i64))
         }
     }
-
-    /// Checks if the amount is below the maximum value.  Returns `None` if it is above.
-    const fn check_max(self) -> Option<Amount> {
-        if self.0 > Self::MAX.0 {
-            None
-        } else {
-            Some(self)
-        }
-    }
 }
 
 impl default::Default for Amount {


Test patch:
diff --git a/units/src/amount/tests.rs b/units/src/amount/tests.rs
index dd4eb2e1..0b22ea2f 100644
--- a/units/src/amount/tests.rs
+++ b/units/src/amount/tests.rs
@@ -80,6 +80,10 @@ fn test_signed_amount_try_from_amount() {
     let ua_positive = Amount::from_sat(123);
     let sa_positive = SignedAmount::try_from(ua_positive).unwrap();
     assert_eq!(sa_positive, SignedAmount::from_sat(123));
+
+    let ua_max = Amount::MAX;
+    let result = SignedAmount::try_from(ua_max);
+    assert_eq!(result, Err(OutOfRangeError { is_signed: true, is_greater_than_max: true }));
 }
 
 #[test]
@@ -150,6 +154,9 @@ fn amount_checked_div_by_weight_ceil() {
     // round up to 864
     assert_eq!(fee_rate, FeeRate::from_sat_per_kwu(864));
 
+    let fee_rate = Amount::MAX.checked_div_by_weight_ceil(weight);
+    assert!(fee_rate.is_none());
+
     let fee_rate = Amount::ONE_SAT.checked_div_by_weight_ceil(Weight::ZERO);
     assert!(fee_rate.is_none());
 }
@@ -168,6 +175,9 @@ fn amount_checked_div_by_weight_floor() {
     // round down to 863
     assert_eq!(fee_rate, FeeRate::from_sat_per_kwu(863));
 
+    let fee_rate = Amount::MAX.checked_div_by_weight_floor(weight);
+    assert!(fee_rate.is_none());
+
     let fee_rate = Amount::ONE_SAT.checked_div_by_weight_floor(Weight::ZERO);
     assert!(fee_rate.is_none());
 }
@@ -220,6 +230,9 @@ fn floating_point() {
     assert_eq!(sf(-184467440738.0, D::Bitcoin), Err(OutOfRangeError::too_small().into()));
     assert_eq!(f(18446744073709551617.0, D::Satoshi), Err(OutOfRangeError::too_big(false).into()));
 
+    // Amount can be grater than the max SignedAmount.
+    assert!(f(SignedAmount::MAX.to_float_in(D::Satoshi) + 1.0, D::Satoshi).is_ok());
+
     assert_eq!(
         f(Amount::MAX.to_float_in(D::Satoshi) + 1.0, D::Satoshi),
         Err(OutOfRangeError::too_big(false).into())
@@ -270,7 +283,7 @@ fn parsing() {
         Err(E::from(InvalidCharacterError { invalid_char: '.', position: 5 }))
     );
     #[cfg(feature = "alloc")]
-    let more_than_max = format!("{}", Amount::MAX.to_sat() + 1);
+    let more_than_max = format!("1{}", Amount::MAX);
     #[cfg(feature = "alloc")]
     assert_eq!(p(&more_than_max, btc), Err(OutOfRangeError::too_big(false).into()));
     assert_eq!(p("0.000000042", btc), Err(TooPreciseError { position: 10 }.into()));
@@ -287,9 +300,20 @@ fn parsing() {
     assert_eq!(p("1.1", btc), Ok(Amount::from_sat(1_100_000_00)));
     assert_eq!(p("100", sat), Ok(Amount::from_sat(100)));
     assert_eq!(p("55", sat), Ok(Amount::from_sat(55)));
-    assert_eq!(p("2100000000000000", sat), Ok(Amount::from_sat(21_000_000__000_000_00)));
-    assert_eq!(p("2100000000000000.", sat), Ok(Amount::from_sat(21_000_000__000_000_00)));
-    assert_eq!(p("21000000", btc), Ok(Amount::from_sat(21_000_000__000_000_00)));
+    assert_eq!(p("5500000000000000000", sat), Ok(Amount::from_sat(55_000_000_000_000_000_00)));
+    // Should this even pass?
+    assert_eq!(p("5500000000000000000.", sat), Ok(Amount::from_sat(55_000_000_000_000_000_00)));
+    assert_eq!(p("12345678901.12345678", btc), Ok(Amount::from_sat(12_345_678_901__123_456_78)));
+
+    // make sure satoshi > i64::MAX is checked.
+    #[cfg(feature = "alloc")]
+    {
+        let amount = Amount::from_sat(i64::MAX as u64);
+        assert_eq!(Amount::from_str_in(&amount.to_string_in(sat), sat), Ok(amount));
+        assert!(SignedAmount::from_str_in(&(amount + Amount::from_sat(1)).to_string_in(sat), sat)
+            .is_err());
+        assert!(Amount::from_str_in(&(amount + Amount::from_sat(1)).to_string_in(sat), sat).is_ok());
+    }
 
     // exactly 50 chars.
     assert_eq!(
@@ -499,14 +523,14 @@ fn $test_name() {
 fn test_unsigned_signed_conversion() {
     let sa = SignedAmount::from_sat;
     let ua = Amount::from_sat;
-    let max_sats: u64 = Amount::MAX.to_sat();
 
-    assert_eq!(ua(max_sats).to_signed(), Ok(sa(max_sats as i64)));
+    assert_eq!(Amount::MAX.to_signed(), Err(OutOfRangeError::too_big(true)));
+    assert_eq!(ua(i64::MAX as u64).to_signed(), Ok(sa(i64::MAX)));
     assert_eq!(ua(i64::MAX as u64 + 1).to_signed(), Err(OutOfRangeError::too_big(true)));
 
-    assert_eq!(sa(max_sats as i64).to_unsigned(), Ok(ua(max_sats)));
+    assert_eq!(sa(i64::MAX).to_unsigned(), Ok(ua(i64::MAX as u64)));
 
-    assert_eq!(sa(max_sats as i64).to_unsigned().unwrap().to_signed(), Ok(sa(max_sats as i64)));
+    assert_eq!(sa(i64::MAX).to_unsigned().unwrap().to_signed(), Ok(sa(i64::MAX)));
 }
 
 #[test]
@@ -614,7 +638,7 @@ fn to_from_string_in() {
         ua_str(&ua_sat(1_000_000_000_000).to_string_in(D::MilliBitcoin), D::MilliBitcoin),
         Ok(ua_sat(1_000_000_000_000))
     );
-    assert!(ua_str(&ua_sat(Amount::MAX.to_sat()).to_string_in(D::MilliBitcoin), D::MilliBitcoin).is_ok());
+    assert!(ua_str(&ua_sat(u64::MAX).to_string_in(D::MilliBitcoin), D::MilliBitcoin).is_ok());
 
     assert_eq!(sa_str(&sa_sat(-1).to_string_in(D::MicroBitcoin), D::MicroBitcoin), Ok(sa_sat(-1)));
 
@@ -694,12 +718,12 @@ struct T {
     }
 
     let orig = T {
-        amt: Amount::from_sat(20_000_000__000_000_01),
-        samt: SignedAmount::from_sat(-20_000_000__000_000_01),
+        amt: Amount::from_sat(21_000_000__000_000_01),
+        samt: SignedAmount::from_sat(-21_000_000__000_000_01),
     };
 
-    let json = "{\"amt\": 20000000.00000001, \
-                \"samt\": -20000000.00000001}";
+    let json = "{\"amt\": 21000000.00000001, \
+                \"samt\": -21000000.00000001}";
     let t: T = serde_json::from_str(json).unwrap();
     assert_eq!(t, orig);