use crate::ln::channelmanager::{ChannelDetails, PaymentId};
use crate::ln::features::{Bolt12InvoiceFeatures, ChannelFeatures, InvoiceFeatures, NodeFeatures};
use crate::ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
-use crate::offers::invoice::BlindedPayInfo;
+use crate::offers::invoice::{BlindedPayInfo, Invoice as Bolt12Invoice};
use crate::routing::gossip::{DirectedChannelInfo, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees};
use crate::routing::scoring::{ChannelUsage, LockableScore, Score};
use crate::util::ser::{Writeable, Readable, ReadableArgs, Writer};
///
/// The `final_cltv_expiry_delta` should match the expected final CLTV delta the recipient has
/// provided.
- pub fn for_keysend(payee_pubkey: PublicKey, final_cltv_expiry_delta: u32) -> Self {
- Self::from_node_id(payee_pubkey, final_cltv_expiry_delta).with_bolt11_features(InvoiceFeatures::for_keysend()).expect("PaymentParameters::from_node_id should always initialize the payee as unblinded")
+ ///
+ /// Note that MPP keysend is not widely supported yet. The `allow_mpp` lets you choose
+ /// whether your router will be allowed to find a multi-part route for this payment. If you
+ /// set `allow_mpp` to true, you should ensure a payment secret is set on send, likely via
+ /// [`RecipientOnionFields::secret_only`].
+ ///
+ /// [`RecipientOnionFields::secret_only`]: crate::ln::channelmanager::RecipientOnionFields::secret_only
+ pub fn for_keysend(payee_pubkey: PublicKey, final_cltv_expiry_delta: u32, allow_mpp: bool) -> Self {
+ Self::from_node_id(payee_pubkey, final_cltv_expiry_delta)
+ .with_bolt11_features(InvoiceFeatures::for_keysend(allow_mpp))
+ .expect("PaymentParameters::from_node_id should always initialize the payee as unblinded")
+ }
+
+ /// Creates parameters for paying to a blinded payee from the provided invoice. Sets
+ /// [`Payee::Blinded::route_hints`], [`Payee::Blinded::features`], and
+ /// [`PaymentParameters::expiry_time`].
+ pub fn from_bolt12_invoice(invoice: &Bolt12Invoice) -> Self {
+ Self::blinded(invoice.payment_paths().to_vec())
+ .with_bolt12_features(invoice.features().clone()).unwrap()
+ .with_expiry_time(invoice.created_at().as_secs().saturating_add(invoice.relative_expiry().as_secs()))
+ }
+
+ fn blinded(blinded_route_hints: Vec<(BlindedPayInfo, BlindedPath)>) -> Self {
+ Self {
+ payee: Payee::Blinded { route_hints: blinded_route_hints, features: None },
+ expiry_time: None,
+ max_total_cltv_expiry_delta: DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA,
+ max_path_count: DEFAULT_MAX_PATH_COUNT,
+ max_channel_saturation_power_of_half: 2,
+ previously_failed_channels: Vec::new(),
+ }
}
- /// Includes the payee's features. Errors if the parameters were initialized with blinded payment
- /// paths.
+ /// Includes the payee's features. Errors if the parameters were not initialized with
+ /// [`PaymentParameters::from_bolt12_invoice`].
+ ///
+ /// This is not exported to bindings users since bindings don't support move semantics
+ pub fn with_bolt12_features(self, features: Bolt12InvoiceFeatures) -> Result<Self, ()> {
+ match self.payee {
+ Payee::Clear { .. } => Err(()),
+ Payee::Blinded { route_hints, .. } =>
+ Ok(Self { payee: Payee::Blinded { route_hints, features: Some(features) }, ..self })
+ }
+ }
+
+ /// Includes the payee's features. Errors if the parameters were initialized with
+ /// [`PaymentParameters::from_bolt12_invoice`].
///
/// This is not exported to bindings users since bindings don't support move semantics
pub fn with_bolt11_features(self, features: InvoiceFeatures) -> Result<Self, ()> {
}
/// Includes hints for routing to the payee. Errors if the parameters were initialized with
- /// blinded payment paths.
+ /// [`PaymentParameters::from_bolt12_invoice`].
///
/// This is not exported to bindings users since bindings don't support move semantics
pub fn with_route_hints(self, route_hints: Vec<RouteHint>) -> Result<Self, ()> {
Self { max_path_count, ..self }
}
- /// Includes a limit for the maximum number of payment paths that may be used.
+ /// Includes a limit for the maximum share of a channel's total capacity that can be sent over, as
+ /// a power of 1/2. See [`PaymentParameters::max_channel_saturation_power_of_half`].
///
/// This is not exported to bindings users since bindings don't support move semantics
pub fn with_max_channel_saturation_power_of_half(self, max_channel_saturation_power_of_half: u8) -> Self {
fn htlc_minimum_msat(&self) -> u64 {
match self {
- CandidateRouteHop::FirstHop { .. } => 0,
+ CandidateRouteHop::FirstHop { details } => details.next_outbound_htlc_minimum_msat,
CandidateRouteHop::PublicHop { info, .. } => info.direction().htlc_minimum_msat,
CandidateRouteHop::PrivateHop { hint } => hint.htlc_minimum_msat.unwrap_or(0),
}
liquidity_msat: details.next_outbound_htlc_limit_msat,
},
CandidateRouteHop::PublicHop { info, .. } => info.effective_capacity(),
- CandidateRouteHop::PrivateHop { .. } => EffectiveCapacity::Infinite,
+ CandidateRouteHop::PrivateHop { hint: RouteHintHop { htlc_maximum_msat: Some(max), .. }} =>
+ EffectiveCapacity::HintMaxHTLC { amount_msat: *max },
+ CandidateRouteHop::PrivateHop { hint: RouteHintHop { htlc_maximum_msat: None, .. }} =>
+ EffectiveCapacity::Infinite,
}
}
}
EffectiveCapacity::ExactLiquidity { liquidity_msat } => liquidity_msat,
EffectiveCapacity::Infinite => u64::max_value(),
EffectiveCapacity::Unknown => EffectiveCapacity::Unknown.as_msat(),
- EffectiveCapacity::MaximumHTLC { amount_msat } =>
+ EffectiveCapacity::AdvertisedMaxHTLC { amount_msat } =>
amount_msat.checked_shr(saturation_shift).unwrap_or(0),
+ // Treat htlc_maximum_msat from a route hint as an exact liquidity amount, since the invoice is
+ // expected to have been generated from up-to-date capacity information.
+ EffectiveCapacity::HintMaxHTLC { amount_msat } => amount_msat,
EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat } =>
cmp::min(capacity_msat.checked_shr(saturation_shift).unwrap_or(0), htlc_maximum_msat),
}
}
}
+#[inline]
+fn sort_first_hop_channels(
+ channels: &mut Vec<&ChannelDetails>, used_channel_liquidities: &HashMap<(u64, bool), u64>,
+ recommended_value_msat: u64, our_node_pubkey: &PublicKey
+) {
+ // Sort the first_hops channels to the same node(s) in priority order of which channel we'd
+ // most like to use.
+ //
+ // First, if channels are below `recommended_value_msat`, sort them in descending order,
+ // preferring larger channels to avoid splitting the payment into more MPP parts than is
+ // required.
+ //
+ // Second, because simply always sorting in descending order would always use our largest
+ // available outbound capacity, needlessly fragmenting our available channel capacities,
+ // sort channels above `recommended_value_msat` in ascending order, preferring channels
+ // which have enough, but not too much, capacity for the payment.
+ //
+ // Available outbound balances factor in liquidity already reserved for previously found paths.
+ channels.sort_unstable_by(|chan_a, chan_b| {
+ let chan_a_outbound_limit_msat = chan_a.next_outbound_htlc_limit_msat
+ .saturating_sub(*used_channel_liquidities.get(&(chan_a.get_outbound_payment_scid().unwrap(),
+ our_node_pubkey < &chan_a.counterparty.node_id)).unwrap_or(&0));
+ let chan_b_outbound_limit_msat = chan_b.next_outbound_htlc_limit_msat
+ .saturating_sub(*used_channel_liquidities.get(&(chan_b.get_outbound_payment_scid().unwrap(),
+ our_node_pubkey < &chan_b.counterparty.node_id)).unwrap_or(&0));
+ if chan_b_outbound_limit_msat < recommended_value_msat || chan_a_outbound_limit_msat < recommended_value_msat {
+ // Sort in descending order
+ chan_b_outbound_limit_msat.cmp(&chan_a_outbound_limit_msat)
+ } else {
+ // Sort in ascending order
+ chan_a_outbound_limit_msat.cmp(&chan_b_outbound_limit_msat)
+ }
+ });
+}
+
/// Finds a route from us (payer) to the given target node (payee).
///
/// If the payee provided features in their invoice, they should be provided via `params.payee`.
// unblinded payee id as an option. We also need a non-optional "payee id" for path construction,
// so use a dummy id for this in the blinded case.
let payee_node_id_opt = payment_params.payee.node_id().map(|pk| NodeId::from_pubkey(&pk));
- const DUMMY_BLINDED_PAYEE_ID: [u8; 33] = [42u8; 33];
+ const DUMMY_BLINDED_PAYEE_ID: [u8; 33] = [2; 33];
let maybe_dummy_payee_pk = payment_params.payee.node_id().unwrap_or_else(|| PublicKey::from_slice(&DUMMY_BLINDED_PAYEE_ID).unwrap());
let maybe_dummy_payee_node_id = NodeId::from_pubkey(&maybe_dummy_payee_pk);
let our_node_id = NodeId::from_pubkey(&our_node_pubkey);
let mut already_collected_value_msat = 0;
for (_, channels) in first_hop_targets.iter_mut() {
- // Sort the first_hops channels to the same node(s) in priority order of which channel we'd
- // most like to use.
- //
- // First, if channels are below `recommended_value_msat`, sort them in descending order,
- // preferring larger channels to avoid splitting the payment into more MPP parts than is
- // required.
- //
- // Second, because simply always sorting in descending order would always use our largest
- // available outbound capacity, needlessly fragmenting our available channel capacities,
- // sort channels above `recommended_value_msat` in ascending order, preferring channels
- // which have enough, but not too much, capacity for the payment.
- channels.sort_unstable_by(|chan_a, chan_b| {
- if chan_b.next_outbound_htlc_limit_msat < recommended_value_msat || chan_a.next_outbound_htlc_limit_msat < recommended_value_msat {
- // Sort in descending order
- chan_b.next_outbound_htlc_limit_msat.cmp(&chan_a.next_outbound_htlc_limit_msat)
- } else {
- // Sort in ascending order
- chan_a.next_outbound_htlc_limit_msat.cmp(&chan_b.next_outbound_htlc_limit_msat)
- }
- });
+ sort_first_hop_channels(channels, &used_channel_liquidities, recommended_value_msat,
+ our_node_pubkey);
}
log_trace!(logger, "Building path from {} to payer {} for value {} msat.",
( $candidate: expr, $src_node_id: expr, $dest_node_id: expr, $next_hops_fee_msat: expr,
$next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr,
$next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr, $next_hops_path_length: expr ) => { {
- // We "return" whether we updated the path at the end, via this:
- let mut did_add_update_path_to_src_node = false;
+ // We "return" whether we updated the path at the end, and how much we can route via
+ // this channel, via this:
+ let mut did_add_update_path_to_src_node = None;
// Channels to self should not be used. This is more of belt-and-suspenders, because in
// practice these cases should be caught earlier:
// - for regular channels at channel announcement (TODO)
{
old_entry.value_contribution_msat = value_contribution_msat;
}
- did_add_update_path_to_src_node = true;
+ did_add_update_path_to_src_node = Some(value_contribution_msat);
} else if old_entry.was_processed && new_cost < old_cost {
#[cfg(all(not(ldk_bench), any(test, fuzzing)))]
{
for details in first_channels {
let candidate = CandidateRouteHop::FirstHop { details };
let added = add_entry!(candidate, our_node_id, payee, 0, path_value_msat,
- 0, 0u64, 0, 0);
+ 0, 0u64, 0, 0).is_some();
log_trace!(logger, "{} direct route to payee via SCID {}",
if added { "Added" } else { "Skipped" }, candidate.short_channel_id());
}
let mut aggregate_next_hops_path_penalty_msat: u64 = 0;
let mut aggregate_next_hops_cltv_delta: u32 = 0;
let mut aggregate_next_hops_path_length: u8 = 0;
+ let mut aggregate_path_contribution_msat = path_value_msat;
for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() {
let source = NodeId::from_pubkey(&hop.src_node_id);
})
.unwrap_or_else(|| CandidateRouteHop::PrivateHop { hint: hop });
- if !add_entry!(candidate, source, target, aggregate_next_hops_fee_msat,
- path_value_msat, aggregate_next_hops_path_htlc_minimum_msat,
- aggregate_next_hops_path_penalty_msat,
- aggregate_next_hops_cltv_delta, aggregate_next_hops_path_length) {
+ if let Some(hop_used_msat) = add_entry!(candidate, source, target,
+ aggregate_next_hops_fee_msat, aggregate_path_contribution_msat,
+ aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat,
+ aggregate_next_hops_cltv_delta, aggregate_next_hops_path_length)
+ {
+ aggregate_path_contribution_msat = hop_used_msat;
+ } else {
// If this hop was not used then there is no use checking the preceding
// hops in the RouteHint. We can break by just searching for a direct
// channel between last checked hop and first_hop_targets.
.saturating_add(1);
// Searching for a direct channel between last checked hop and first_hop_targets
- if let Some(first_channels) = first_hop_targets.get(&NodeId::from_pubkey(&prev_hop_id)) {
+ if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&prev_hop_id)) {
+ sort_first_hop_channels(first_channels, &used_channel_liquidities,
+ recommended_value_msat, our_node_pubkey);
for details in first_channels {
- let candidate = CandidateRouteHop::FirstHop { details };
- add_entry!(candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id),
- aggregate_next_hops_fee_msat, path_value_msat,
- aggregate_next_hops_path_htlc_minimum_msat,
- aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta,
- aggregate_next_hops_path_length);
+ let first_hop_candidate = CandidateRouteHop::FirstHop { details };
+ add_entry!(first_hop_candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id),
+ aggregate_next_hops_fee_msat, aggregate_path_contribution_msat,
+ aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat,
+ aggregate_next_hops_cltv_delta, aggregate_next_hops_path_length);
}
}
// Note that we *must* check if the last hop was added as `add_entry`
// always assumes that the third argument is a node to which we have a
// path.
- if let Some(first_channels) = first_hop_targets.get(&NodeId::from_pubkey(&hop.src_node_id)) {
+ if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hop.src_node_id)) {
+ sort_first_hop_channels(first_channels, &used_channel_liquidities,
+ recommended_value_msat, our_node_pubkey);
for details in first_channels {
- let candidate = CandidateRouteHop::FirstHop { details };
- add_entry!(candidate, our_node_id,
+ let first_hop_candidate = CandidateRouteHop::FirstHop { details };
+ add_entry!(first_hop_candidate, our_node_id,
NodeId::from_pubkey(&hop.src_node_id),
- aggregate_next_hops_fee_msat, path_value_msat,
+ aggregate_next_hops_fee_msat,
+ aggregate_path_contribution_msat,
aggregate_next_hops_path_htlc_minimum_msat,
aggregate_next_hops_path_penalty_msat,
aggregate_next_hops_cltv_delta,
balance_msat: 0,
outbound_capacity_msat,
next_outbound_htlc_limit_msat: outbound_capacity_msat,
+ next_outbound_htlc_minimum_msat: 0,
inbound_capacity_msat: 42,
unspendable_punishment_reserve: None,
confirmations_required: None,
assert!(route.is_ok());
}
+ #[test]
+ fn abide_by_route_hint_max_htlc() {
+ // Check that we abide by any htlc_maximum_msat provided in the route hints of the payment
+ // params in the final route.
+ let (secp_ctx, network_graph, _, _, logger) = build_graph();
+ let netgraph = network_graph.read_only();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ let max_htlc_msat = 50_000;
+ let route_hint_1 = RouteHint(vec![RouteHintHop {
+ src_node_id: nodes[2],
+ short_channel_id: 42,
+ fees: RoutingFees {
+ base_msat: 100,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: 10,
+ htlc_minimum_msat: None,
+ htlc_maximum_msat: Some(max_htlc_msat),
+ }]);
+ let dest_node_id = ln_test_utils::pubkey(42);
+ let payment_params = PaymentParameters::from_node_id(dest_node_id, 42)
+ .with_route_hints(vec![route_hint_1.clone()]).unwrap()
+ .with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap();
+
+ // Make sure we'll error if our route hints don't have enough liquidity according to their
+ // htlc_maximum_msat.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id,
+ &payment_params, &netgraph, None, max_htlc_msat + 1, Arc::clone(&logger), &scorer, &(),
+ &random_seed_bytes)
+ {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+
+ // Make sure we'll split an MPP payment across route hints if their htlc_maximum_msat warrants.
+ let mut route_hint_2 = route_hint_1.clone();
+ route_hint_2.0[0].short_channel_id = 43;
+ let payment_params = PaymentParameters::from_node_id(dest_node_id, 42)
+ .with_route_hints(vec![route_hint_1, route_hint_2]).unwrap()
+ .with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap();
+ let route = get_route(&our_id, &payment_params, &netgraph, None, max_htlc_msat + 1,
+ Arc::clone(&logger), &scorer, &(), &random_seed_bytes).unwrap();
+ assert_eq!(route.paths.len(), 2);
+ assert!(route.paths[0].hops.last().unwrap().fee_msat <= max_htlc_msat);
+ assert!(route.paths[1].hops.last().unwrap().fee_msat <= max_htlc_msat);
+ }
+
+ #[test]
+ fn direct_channel_to_hints_with_max_htlc() {
+ // Check that if we have a first hop channel peer that's connected to multiple provided route
+ // hints, that we properly split the payment between the route hints if needed.
+ let logger = Arc::new(ln_test_utils::TestLogger::new());
+ let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger)));
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ let our_node_id = ln_test_utils::pubkey(42);
+ let intermed_node_id = ln_test_utils::pubkey(43);
+ let first_hop = vec![get_channel_details(Some(42), intermed_node_id, InitFeatures::from_le_bytes(vec![0b11]), 10_000_000)];
+
+ let amt_msat = 900_000;
+ let max_htlc_msat = 500_000;
+ let route_hint_1 = RouteHint(vec![RouteHintHop {
+ src_node_id: intermed_node_id,
+ short_channel_id: 44,
+ fees: RoutingFees {
+ base_msat: 100,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: 10,
+ htlc_minimum_msat: None,
+ htlc_maximum_msat: Some(max_htlc_msat),
+ }, RouteHintHop {
+ src_node_id: intermed_node_id,
+ short_channel_id: 45,
+ fees: RoutingFees {
+ base_msat: 100,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: 10,
+ htlc_minimum_msat: None,
+ // Check that later route hint max htlcs don't override earlier ones
+ htlc_maximum_msat: Some(max_htlc_msat - 50),
+ }]);
+ let mut route_hint_2 = route_hint_1.clone();
+ route_hint_2.0[0].short_channel_id = 46;
+ route_hint_2.0[1].short_channel_id = 47;
+ let dest_node_id = ln_test_utils::pubkey(44);
+ let payment_params = PaymentParameters::from_node_id(dest_node_id, 42)
+ .with_route_hints(vec![route_hint_1, route_hint_2]).unwrap()
+ .with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap();
+
+ let route = get_route(&our_node_id, &payment_params, &network_graph.read_only(),
+ Some(&first_hop.iter().collect::<Vec<_>>()), amt_msat, Arc::clone(&logger), &scorer, &(),
+ &random_seed_bytes).unwrap();
+ assert_eq!(route.paths.len(), 2);
+ assert!(route.paths[0].hops.last().unwrap().fee_msat <= max_htlc_msat);
+ assert!(route.paths[1].hops.last().unwrap().fee_msat <= max_htlc_msat);
+ assert_eq!(route.get_total_amount(), amt_msat);
+
+ // Re-run but with two first hop channels connected to the same route hint peers that must be
+ // split between.
+ let first_hops = vec![
+ get_channel_details(Some(42), intermed_node_id, InitFeatures::from_le_bytes(vec![0b11]), amt_msat - 10),
+ get_channel_details(Some(43), intermed_node_id, InitFeatures::from_le_bytes(vec![0b11]), amt_msat - 10),
+ ];
+ let route = get_route(&our_node_id, &payment_params, &network_graph.read_only(),
+ Some(&first_hops.iter().collect::<Vec<_>>()), amt_msat, Arc::clone(&logger), &scorer, &(),
+ &random_seed_bytes).unwrap();
+ assert_eq!(route.paths.len(), 2);
+ assert!(route.paths[0].hops.last().unwrap().fee_msat <= max_htlc_msat);
+ assert!(route.paths[1].hops.last().unwrap().fee_msat <= max_htlc_msat);
+ assert_eq!(route.get_total_amount(), amt_msat);
+ }
+
#[test]
fn blinded_route_ser() {
let blinded_path_1 = BlindedPath {
user_channel_id: 0,
balance_msat: 10_000_000_000,
outbound_capacity_msat: 10_000_000_000,
+ next_outbound_htlc_minimum_msat: 0,
next_outbound_htlc_limit_msat: 10_000_000_000,
inbound_capacity_msat: 0,
unspendable_punishment_reserve: None,