From d990f72f9a4cf4bc6f7f32f8b3dc9dd616c5bd33 Mon Sep 17 00:00:00 2001
From: Matt Corallo <git@bluematt.me>
Date: Thu, 7 Mar 2019 13:02:23 -0500
Subject: [PATCH] Fix HTLC-output-in-commitment sorting for duplicate-HTLCs

This resolves both an issue that hits fuzzing due to hash
collisions as well as implements an update to the BOLT spec.
---
 src/ln/channel.rs             | 16 ++++++++++++++--
 src/util/transaction_utils.rs | 18 ++++++++++--------
 2 files changed, 24 insertions(+), 10 deletions(-)

diff --git a/src/ln/channel.rs b/src/ln/channel.rs
index 64da86e58..3d883cd76 100644
--- a/src/ln/channel.rs
+++ b/src/ln/channel.rs
@@ -934,7 +934,19 @@ impl Channel {
 			}, None));
 		}
 
-		transaction_utils::sort_outputs(&mut txouts);
+		transaction_utils::sort_outputs(&mut txouts, |a, b| {
+			if let &Some(ref a_htlc) = a {
+				if let &Some(ref b_htlc) = b {
+					a_htlc.0.cltv_expiry.cmp(&b_htlc.0.cltv_expiry)
+						// Note that due to hash collisions, we have to have a fallback comparison
+						// here for fuzztarget mode (otherwise at least chanmon_fail_consistency
+						// may fail)!
+						.then(a_htlc.0.payment_hash.0.cmp(&b_htlc.0.payment_hash.0))
+				// For non-HTLC outputs, if they're copying our SPK we don't really care if we
+				// close the channel due to mismatches - they're doing something dumb:
+				} else { cmp::Ordering::Equal }
+			} else { cmp::Ordering::Equal }
+		});
 
 		let mut outputs: Vec<TxOut> = Vec::with_capacity(txouts.len());
 		let mut htlcs_included: Vec<(HTLCOutputInCommitment, Option<&HTLCSource>)> = Vec::with_capacity(txouts.len() + included_dust_htlcs.len());
@@ -1010,7 +1022,7 @@ impl Channel {
 			}, ()));
 		}
 
-		transaction_utils::sort_outputs(&mut txouts);
+		transaction_utils::sort_outputs(&mut txouts, |_, _| { cmp::Ordering::Equal }); // Ordering doesnt matter if they used our pubkey...
 
 		let mut outputs: Vec<TxOut> = Vec::new();
 		for out in txouts.drain(..) {
diff --git a/src/util/transaction_utils.rs b/src/util/transaction_utils.rs
index 74ea81adb..b81d3d9d0 100644
--- a/src/util/transaction_utils.rs
+++ b/src/util/transaction_utils.rs
@@ -3,11 +3,13 @@ use bitcoin_hashes::sha256d::Hash as Sha256dHash;
 
 use std::cmp::Ordering;
 
-pub fn sort_outputs<T>(outputs: &mut Vec<(TxOut, T)>) {
+pub fn sort_outputs<T, C : Fn(&T, &T) -> Ordering>(outputs: &mut Vec<(TxOut, T)>, tie_breaker: C) {
 	outputs.sort_unstable_by(|a, b| {
-		a.0.value.cmp(&b.0.value).then(
-			a.0.script_pubkey[..].cmp(&b.0.script_pubkey[..])
-		)
+		a.0.value.cmp(&b.0.value).then_with(|| {
+			a.0.script_pubkey[..].cmp(&b.0.script_pubkey[..]).then_with(|| {
+				tie_breaker(&a.1, &b.1)
+			})
+		})
 	});
 }
 
@@ -58,7 +60,7 @@ mod tests {
 		let txout2_ = txout2.clone();
 
 		let mut outputs = vec![(txout1, "ignore"), (txout2, "ignore")];
-		sort_outputs(&mut outputs);
+		sort_outputs(&mut outputs, |_, _| { unreachable!(); });
 
 		assert_eq!(
 			&outputs,
@@ -81,7 +83,7 @@ mod tests {
 		let txout2_ = txout2.clone();
 
 		let mut outputs = vec![(txout1, "ignore"), (txout2, "ignore")];
-		sort_outputs(&mut outputs);
+		sort_outputs(&mut outputs, |_, _| { unreachable!(); });
 
 		assert_eq!(
 			&outputs,
@@ -105,7 +107,7 @@ mod tests {
 		let txout2_ = txout2.clone();
 
 		let mut outputs = vec![(txout1, "ignore"), (txout2, "ignore")];
-		sort_outputs(&mut outputs);
+		sort_outputs(&mut outputs, |_, _| { unreachable!(); });
 
 		assert_eq!(&outputs, &vec![(txout1_, "ignore"), (txout2_, "ignore")]);
 	}
@@ -131,7 +133,7 @@ mod tests {
 					outputs.reverse(); // prep it
 
 					// actually do the work!
-					sort_outputs(&mut outputs);
+					sort_outputs(&mut outputs, |_, _| { unreachable!(); });
 
 					assert_eq!(outputs, expected);
 				}
-- 
2.39.5