use bitcoin::secp256k1::{PublicKey, Secp256k1, self};
use crate::blinded_path::{BlindedHop, BlindedPath, Direction, IntroductionNode};
-use crate::blinded_path::payment::{ForwardNode, ForwardTlvs, PaymentConstraints, PaymentRelay, ReceiveTlvs};
-use crate::ln::PaymentHash;
-use crate::ln::channelmanager::{ChannelDetails, PaymentId, MIN_FINAL_CLTV_EXPIRY_DELTA};
+use crate::blinded_path::message;
+use crate::blinded_path::payment::{ForwardTlvs, PaymentConstraints, PaymentRelay, ReceiveTlvs, self};
+use crate::ln::{PaymentHash, PaymentPreimage};
+use crate::ln::channel_state::ChannelDetails;
+use crate::ln::channelmanager::{PaymentId, MIN_FINAL_CLTV_EXPIRY_DELTA, RecipientOnionFields};
use crate::ln::features::{BlindedHopFeatures, Bolt11InvoiceFeatures, Bolt12InvoiceFeatures, ChannelFeatures, NodeFeatures};
use crate::ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
+use crate::ln::onion_utils;
use crate::offers::invoice::{BlindedPayInfo, Bolt12Invoice};
use crate::onion_message::messenger::{DefaultMessageRouter, Destination, MessageRouter, OnionMessagePath};
use crate::routing::gossip::{DirectedChannelInfo, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees};
max_cltv_expiry: tlvs.payment_constraints.max_cltv_expiry + cltv_expiry_delta,
htlc_minimum_msat: details.inbound_htlc_minimum_msat.unwrap_or(0),
};
- Some(ForwardNode {
+ Some(payment::ForwardNode {
tlvs: ForwardTlvs {
short_channel_id,
payment_relay,
fn create_blinded_paths<
T: secp256k1::Signing + secp256k1::Verification
> (
- &self, recipient: PublicKey, peers: Vec<PublicKey>, secp_ctx: &Secp256k1<T>,
+ &self, recipient: PublicKey, peers: Vec<message::ForwardNode>, secp_ctx: &Secp256k1<T>,
) -> Result<Vec<BlindedPath>, ()> {
self.message_router.create_blinded_paths(recipient, peers, secp_ctx)
}
pub fn from_payment_params_and_value(payment_params: PaymentParameters, final_value_msat: u64) -> Self {
Self { payment_params, final_value_msat, max_total_routing_fee_msat: Some(final_value_msat / 100 + 50_000) }
}
+
+ /// Sets the maximum number of hops that can be included in a payment path, based on the provided
+ /// [`RecipientOnionFields`] and blinded paths.
+ pub fn set_max_path_length(
+ &mut self, recipient_onion: &RecipientOnionFields, is_keysend: bool, best_block_height: u32
+ ) -> Result<(), ()> {
+ let keysend_preimage_opt = is_keysend.then(|| PaymentPreimage([42; 32]));
+ onion_utils::set_max_path_length(
+ self, recipient_onion, keysend_preimage_opt, best_block_height
+ )
+ }
}
impl Writeable for RouteParameters {
// The median hop CLTV expiry delta currently seen in the network.
const MEDIAN_HOP_CLTV_EXPIRY_DELTA: u32 = 40;
+/// Estimated maximum number of hops that can be included in a payment path. May be inaccurate if
+/// payment metadata, custom TLVs, or blinded paths are included in the payment.
// During routing, we only consider paths shorter than our maximum length estimate.
// In the TLV onion format, there is no fixed maximum length, but the `hop_payloads`
// field is always 1300 bytes. As the `tlv_payload` for each hop may vary in length, we have to
// (payment_secret and total_msat) = 93 bytes for the final hop.
// Since the length of the potentially included `payment_metadata` is unknown to us, we round
// down from (1300-93) / 61 = 19.78... to arrive at a conservative estimate of 19.
-const MAX_PATH_LENGTH_ESTIMATE: u8 = 19;
+pub const MAX_PATH_LENGTH_ESTIMATE: u8 = 19;
/// Information used to route a payment.
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
/// Defaults to [`DEFAULT_MAX_PATH_COUNT`].
pub max_path_count: u8,
+ /// The maximum number of [`Path::hops`] in any returned path.
+ /// Defaults to [`MAX_PATH_LENGTH_ESTIMATE`].
+ pub max_path_length: u8,
+
/// Selects the maximum share of a channel's total capacity which will be sent over a channel,
/// as a power of 1/2. A higher value prefers to send the payment using more MPP parts whereas
/// a lower value prefers to send larger MPP parts, potentially saturating channels and
(8, *blinded_hints, optional_vec),
(9, self.payee.final_cltv_expiry_delta(), option),
(11, self.previously_failed_blinded_path_idxs, required_vec),
+ (13, self.max_path_length, required),
});
Ok(())
}
(8, blinded_route_hints, optional_vec),
(9, final_cltv_expiry_delta, (default_value, default_final_cltv_expiry_delta)),
(11, previously_failed_blinded_path_idxs, optional_vec),
+ (13, max_path_length, (default_value, MAX_PATH_LENGTH_ESTIMATE)),
});
let blinded_route_hints = blinded_route_hints.unwrap_or(vec![]);
let payee = if blinded_route_hints.len() != 0 {
expiry_time,
previously_failed_channels: previously_failed_channels.unwrap_or(Vec::new()),
previously_failed_blinded_path_idxs: previously_failed_blinded_path_idxs.unwrap_or(Vec::new()),
+ max_path_length: _init_tlv_based_struct_field!(max_path_length, (default_value, unused)),
})
}
}
expiry_time: None,
max_total_cltv_expiry_delta: DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA,
max_path_count: DEFAULT_MAX_PATH_COUNT,
+ max_path_length: MAX_PATH_LENGTH_ESTIMATE,
max_channel_saturation_power_of_half: DEFAULT_MAX_CHANNEL_SATURATION_POW_HALF,
previously_failed_channels: Vec::new(),
previously_failed_blinded_path_idxs: Vec::new(),
expiry_time: None,
max_total_cltv_expiry_delta: DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA,
max_path_count: DEFAULT_MAX_PATH_COUNT,
+ max_path_length: MAX_PATH_LENGTH_ESTIMATE,
max_channel_saturation_power_of_half: DEFAULT_MAX_CHANNEL_SATURATION_POW_HALF,
previously_failed_channels: Vec::new(),
previously_failed_blinded_path_idxs: Vec::new(),
where L::Target: Logger {
let payment_params = &route_params.payment_params;
+ let max_path_length = core::cmp::min(payment_params.max_path_length, MAX_PATH_LENGTH_ESTIMATE);
let final_value_msat = route_params.final_value_msat;
// If we're routing to a blinded recipient, we won't have their node id. Therefore, keep the
// unblinded payee id as an option. We also need a non-optional "payee id" for path construction,
true
} else if let Some(payee) = payee_node_id_opt {
network_nodes.get(&payee).map_or(false, |node| node.announcement_info.as_ref().map_or(false,
- |info| info.features.supports_basic_mpp()))
+ |info| info.features().supports_basic_mpp()))
} else { false };
let max_total_routing_fee_msat = route_params.max_total_routing_fee_msat.unwrap_or(u64::max_value());
- log_trace!(logger, "Searching for a route from payer {} to {} {} MPP and {} first hops {}overriding the network graph with a fee limit of {} msat",
+ let first_hop_count = first_hops.map(|hops| hops.len()).unwrap_or(0);
+ log_trace!(logger, "Searching for a route from payer {} to {} {} MPP and {} first hops {}overriding the network graph of {} nodes and {} channels with a fee limit of {} msat",
our_node_pubkey, LoggedPayeePubkey(payment_params.payee.node_id()),
if allow_mpp { "with" } else { "without" },
- first_hops.map(|hops| hops.len()).unwrap_or(0), if first_hops.is_some() { "" } else { "not " },
+ first_hop_count, if first_hops.is_some() { "" } else { "not " },
+ network_graph.nodes().len(), network_graph.channels().len(),
max_total_routing_fee_msat);
+ if first_hop_count < 10 {
+ if let Some(hops) = first_hops {
+ for hop in hops {
+ log_trace!(
+ logger,
+ " First hop through {}/{} can send between {}msat and {}msat (inclusive).",
+ hop.counterparty.node_id,
+ hop.get_outbound_payment_scid().unwrap_or(0),
+ hop.next_outbound_htlc_minimum_msat,
+ hop.next_outbound_htlc_limit_msat
+ );
+ }
+ }
+ }
+
// Step (1).
// Prepare the data we'll use for payee-to-payer search by
// inserting first hops suggested by the caller as targets.
// Verify the liquidity offered by this channel complies to the minimal contribution.
let contributes_sufficient_value = available_value_contribution_msat >= minimal_value_contribution_msat;
// Do not consider candidate hops that would exceed the maximum path length.
- let path_length_to_node = $next_hops_path_length + 1;
- let exceeds_max_path_length = path_length_to_node > MAX_PATH_LENGTH_ESTIMATE;
+ let path_length_to_node = $next_hops_path_length
+ + if $candidate.blinded_hint_idx().is_some() { 0 } else { 1 };
+ let exceeds_max_path_length = path_length_to_node > max_path_length;
// Do not consider candidates that exceed the maximum total cltv expiry limit.
// In order to already account for some of the privacy enhancing random CLTV
// around again with a higher amount.
if !contributes_sufficient_value {
if should_log_candidate {
- log_trace!(logger, "Ignoring {} due to insufficient value contribution.", LoggedCandidateHop(&$candidate));
-
- if let Some(details) = first_hop_details {
- log_trace!(logger,
- "First hop candidate next_outbound_htlc_limit_msat: {}",
- details.next_outbound_htlc_limit_msat,
- );
- }
+ log_trace!(logger, "Ignoring {} due to insufficient value contribution (channel max {:?}).",
+ LoggedCandidateHop(&$candidate),
+ effective_capacity);
}
num_ignored_value_contribution += 1;
} else if exceeds_max_path_length {
} else if may_overpay_to_meet_path_minimum_msat {
if should_log_candidate {
log_trace!(logger,
- "Ignoring {} to avoid overpaying to meet htlc_minimum_msat limit.",
- LoggedCandidateHop(&$candidate));
-
- if let Some(details) = first_hop_details {
- log_trace!(logger,
- "First hop candidate next_outbound_htlc_minimum_msat: {}",
- details.next_outbound_htlc_minimum_msat,
- );
- }
+ "Ignoring {} to avoid overpaying to meet htlc_minimum_msat limit ({}).",
+ LoggedCandidateHop(&$candidate), $candidate.htlc_minimum_msat());
}
num_ignored_avoid_overpayment += 1;
hit_minimum_limit = true;
}
let features = if let Some(node_info) = $node.announcement_info.as_ref() {
- &node_info.features
+ &node_info.features()
} else {
&default_node_features
};
};
let path_min = candidate.htlc_minimum_msat().saturating_add(
compute_fees_saturating(candidate.htlc_minimum_msat(), candidate.fees()));
- add_entry!(&first_hop_candidate, blinded_path_fee,
- path_contribution_msat, path_min, 0_u64, candidate.cltv_expiry_delta(),
- candidate.blinded_path().map_or(1, |bp| bp.blinded_hops.len() as u8));
+ add_entry!(&first_hop_candidate, blinded_path_fee, path_contribution_msat, path_min,
+ 0_u64, candidate.cltv_expiry_delta(), 0);
}
}
}
if !features_set {
if let Some(node) = network_nodes.get(&target) {
if let Some(node_info) = node.announcement_info.as_ref() {
- ordered_hops.last_mut().unwrap().1 = node_info.features.clone();
+ ordered_hops.last_mut().unwrap().1 = node_info.features().clone();
} else {
ordered_hops.last_mut().unwrap().1 = default_node_features.clone();
}
use crate::routing::test_utils::{add_channel, add_or_update_node, build_graph, build_line_graph, id_to_feature_flags, get_nodes, update_channel};
use crate::chain::transaction::OutPoint;
use crate::sign::EntropySource;
- use crate::ln::ChannelId;
+ use crate::ln::channel_state::{ChannelCounterparty, ChannelDetails, ChannelShutdownState};
+ use crate::ln::types::ChannelId;
use crate::ln::features::{BlindedHopFeatures, ChannelFeatures, InitFeatures, NodeFeatures};
use crate::ln::msgs::{ErrorAction, LightningError, UnsignedChannelUpdate, MAX_VALUE_MSAT};
use crate::ln::channelmanager;
#[cfg(c_bindings)]
use crate::util::ser::Writer;
+ use bitcoin::amount::Amount;
use bitcoin::hashes::Hash;
- use bitcoin::network::constants::Network;
+ use bitcoin::network::Network;
use bitcoin::blockdata::constants::ChainHash;
use bitcoin::blockdata::script::Builder;
use bitcoin::blockdata::opcodes;
use crate::sync::Arc;
fn get_channel_details(short_channel_id: Option<u64>, node_id: PublicKey,
- features: InitFeatures, outbound_capacity_msat: u64) -> channelmanager::ChannelDetails {
- channelmanager::ChannelDetails {
+ features: InitFeatures, outbound_capacity_msat: u64) -> ChannelDetails {
+ ChannelDetails {
channel_id: ChannelId::new_zero(),
- counterparty: channelmanager::ChannelCounterparty {
+ counterparty: ChannelCounterparty {
features,
node_id,
unspendable_punishment_reserve: 0,
inbound_htlc_maximum_msat: None,
config: None,
feerate_sat_per_1000_weight: None,
- channel_shutdown_state: Some(channelmanager::ChannelShutdownState::NotShuttingDown),
+ channel_shutdown_state: Some(ChannelShutdownState::NotShuttingDown),
pending_inbound_htlcs: Vec::new(),
pending_outbound_htlcs: Vec::new(),
}
fn simple_route_test() {
let (secp_ctx, network_graph, _, _, logger) = build_graph();
let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
- let payment_params = PaymentParameters::from_node_id(nodes[2], 42);
+ let mut payment_params = PaymentParameters::from_node_id(nodes[2], 42);
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();
assert_eq!(err, "Cannot send a payment of 0 msat");
} else { panic!(); }
- let route_params = RouteParameters::from_payment_params_and_value(payment_params, 100);
+ payment_params.max_path_length = 2;
+ let mut route_params = RouteParameters::from_payment_params_and_value(payment_params, 100);
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths[0].hops.len(), 2);
assert_eq!(route.paths[0].hops[1].cltv_expiry_delta, 42);
assert_eq!(route.paths[0].hops[1].node_features.le_flags(), &id_to_feature_flags(3));
assert_eq!(route.paths[0].hops[1].channel_features.le_flags(), &id_to_feature_flags(4));
+
+ route_params.payment_params.max_path_length = 1;
+ get_route(&our_id, &route_params, &network_graph.read_only(), None,
+ Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap_err();
}
#[test]
});
// If all the channels require some features we don't understand, route should fail
- let route_params = RouteParameters::from_payment_params_and_value(payment_params, 100);
+ let mut route_params = RouteParameters::from_payment_params_and_value(payment_params, 100);
if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id,
&route_params, &network_graph.read_only(), None, Arc::clone(&logger), &scorer,
&Default::default(), &random_seed_bytes) {
// If we specify a channel to node7, that overrides our local channel view and that gets used
let our_chans = vec![get_channel_details(Some(42), nodes[7].clone(),
InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
+ route_params.payment_params.max_path_length = 2;
let route = get_route(&our_id, &route_params, &network_graph.read_only(),
Some(&our_chans.iter().collect::<Vec<_>>()), Arc::clone(&logger), &scorer,
&Default::default(), &random_seed_bytes).unwrap();
} else { panic!(); }
}
- let payment_params = PaymentParameters::from_node_id(nodes[6], 42)
+ let mut payment_params = PaymentParameters::from_node_id(nodes[6], 42)
.with_route_hints(last_hops_multi_private_channels(&nodes)).unwrap();
+ payment_params.max_path_length = 5;
let route_params = RouteParameters::from_payment_params_and_value(payment_params, 100);
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
let random_seed_bytes = keys_manager.get_secure_random_bytes();
// Test through channels 2, 3, 0xff00, 0xff01.
- // Test shows that multiple hop hints are considered.
+ // Test shows that multi-hop route hints are considered and factored correctly into the
+ // max path length.
// Disabling channels 6 & 7 by flags=2
update_channel(&gossip_sync, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
excess_data: Vec::new()
});
- let route_params = RouteParameters::from_payment_params_and_value(payment_params, 100);
+ let mut route_params = RouteParameters::from_payment_params_and_value(payment_params, 100);
+ route_params.payment_params.max_path_length = 4;
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths[0].hops.len(), 4);
assert_eq!(route.paths[0].hops[3].cltv_expiry_delta, 42);
assert_eq!(route.paths[0].hops[3].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet
assert_eq!(route.paths[0].hops[3].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
+ route_params.payment_params.max_path_length = 3;
+ get_route(&our_id, &route_params, &network_graph.read_only(), None,
+ Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap_err();
}
#[test]
.push_slice(&PublicKey::from_secret_key(&secp_ctx, &privkeys[0]).serialize())
.push_slice(&PublicKey::from_secret_key(&secp_ctx, &privkeys[2]).serialize())
.push_opcode(opcodes::all::OP_PUSHNUM_2)
- .push_opcode(opcodes::all::OP_CHECKMULTISIG).into_script().to_v0_p2wsh();
+ .push_opcode(opcodes::all::OP_CHECKMULTISIG).into_script().to_p2wsh();
*chain_monitor.utxo_ret.lock().unwrap() =
- UtxoResult::Sync(Ok(TxOut { value: 15, script_pubkey: good_script.clone() }));
+ UtxoResult::Sync(Ok(TxOut { value: Amount::from_sat(15), script_pubkey: good_script.clone() }));
gossip_sync.add_utxo_lookup(Some(chain_monitor));
add_channel(&gossip_sync, &secp_ctx, &privkeys[0], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(3)), 333);
fee_proportional_millionths: 0,
excess_data: Vec::new()
});
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[3], UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 5,
+ timestamp: 2,
+ flags: 3, // disable direction 1
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: 200_000,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
// Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
// Add 100 sats to the capacities of {12, 13}, because these channels
fee_proportional_millionths: 0,
excess_data: Vec::new()
});
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[3], UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 5,
+ timestamp: 2,
+ flags: 3, // disable direction 1
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: 200_000,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
// Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
// Add 100 sats to the capacities of {12, 13}, because these channels
fee_proportional_millionths: 0,
excess_data: Vec::new()
});
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[3], UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 5,
+ timestamp: 2,
+ flags: 3, // Disable direction 1
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: 100_000,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
// Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
// All channels should be 100 sats capacity. But for the fee experiment,
let payment_params = PaymentParameters::from_node_id(nodes[6], 42);
add_channel(&gossip_sync, &secp_ctx, &our_privkey, &privkeys[1], ChannelFeatures::from_le_bytes(id_to_feature_flags(6)), 6);
- update_channel(&gossip_sync, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
- chain_hash: ChainHash::using_genesis_block(Network::Testnet),
- short_channel_id: 6,
- timestamp: 1,
- flags: 0,
- cltv_expiry_delta: (6 << 4) | 0,
- htlc_minimum_msat: 0,
- htlc_maximum_msat: MAX_VALUE_MSAT,
- fee_base_msat: 0,
- fee_proportional_millionths: 0,
- excess_data: Vec::new()
- });
+ for (key, flags) in [(&our_privkey, 0), (&privkeys[1], 3)] {
+ update_channel(&gossip_sync, &secp_ctx, key, UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 6,
+ timestamp: 1,
+ flags,
+ cltv_expiry_delta: (6 << 4) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ }
add_or_update_node(&gossip_sync, &secp_ctx, &privkeys[1], NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0);
add_channel(&gossip_sync, &secp_ctx, &privkeys[1], &privkeys[4], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
- update_channel(&gossip_sync, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
- chain_hash: ChainHash::using_genesis_block(Network::Testnet),
- short_channel_id: 5,
- timestamp: 1,
- flags: 0,
- cltv_expiry_delta: (5 << 4) | 0,
- htlc_minimum_msat: 0,
- htlc_maximum_msat: MAX_VALUE_MSAT,
- fee_base_msat: 100,
- fee_proportional_millionths: 0,
- excess_data: Vec::new()
- });
+ for (key, flags) in [(&privkeys[1], 0), (&privkeys[4], 3)] {
+ update_channel(&gossip_sync, &secp_ctx, key, UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 5,
+ timestamp: 1,
+ flags,
+ cltv_expiry_delta: (5 << 4) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 100,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ }
add_or_update_node(&gossip_sync, &secp_ctx, &privkeys[4], NodeFeatures::from_le_bytes(id_to_feature_flags(4)), 0);
add_channel(&gossip_sync, &secp_ctx, &privkeys[4], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(4)), 4);
- update_channel(&gossip_sync, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
- chain_hash: ChainHash::using_genesis_block(Network::Testnet),
- short_channel_id: 4,
- timestamp: 1,
- flags: 0,
- cltv_expiry_delta: (4 << 4) | 0,
- htlc_minimum_msat: 0,
- htlc_maximum_msat: MAX_VALUE_MSAT,
- fee_base_msat: 0,
- fee_proportional_millionths: 0,
- excess_data: Vec::new()
- });
+ for (key, flags) in [(&privkeys[4], 0), (&privkeys[3], 3)] {
+ update_channel(&gossip_sync, &secp_ctx, key, UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 4,
+ timestamp: 1,
+ flags,
+ cltv_expiry_delta: (4 << 4) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ }
add_or_update_node(&gossip_sync, &secp_ctx, &privkeys[3], NodeFeatures::from_le_bytes(id_to_feature_flags(3)), 0);
add_channel(&gossip_sync, &secp_ctx, &privkeys[3], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(3)), 3);
- update_channel(&gossip_sync, &secp_ctx, &privkeys[3], UnsignedChannelUpdate {
- chain_hash: ChainHash::using_genesis_block(Network::Testnet),
- short_channel_id: 3,
- timestamp: 1,
- flags: 0,
- cltv_expiry_delta: (3 << 4) | 0,
- htlc_minimum_msat: 0,
- htlc_maximum_msat: MAX_VALUE_MSAT,
- fee_base_msat: 0,
- fee_proportional_millionths: 0,
- excess_data: Vec::new()
- });
+ for (key, flags) in [(&privkeys[3], 0), (&privkeys[2], 3)] {
+ update_channel(&gossip_sync, &secp_ctx, key, UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 3,
+ timestamp: 1,
+ flags,
+ cltv_expiry_delta: (3 << 4) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ }
add_or_update_node(&gossip_sync, &secp_ctx, &privkeys[2], NodeFeatures::from_le_bytes(id_to_feature_flags(2)), 0);
add_channel(&gossip_sync, &secp_ctx, &privkeys[2], &privkeys[4], ChannelFeatures::from_le_bytes(id_to_feature_flags(2)), 2);
- update_channel(&gossip_sync, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
- chain_hash: ChainHash::using_genesis_block(Network::Testnet),
- short_channel_id: 2,
- timestamp: 1,
- flags: 0,
- cltv_expiry_delta: (2 << 4) | 0,
- htlc_minimum_msat: 0,
- htlc_maximum_msat: MAX_VALUE_MSAT,
- fee_base_msat: 0,
- fee_proportional_millionths: 0,
- excess_data: Vec::new()
- });
+ for (key, flags) in [(&privkeys[2], 0), (&privkeys[4], 3)] {
+ update_channel(&gossip_sync, &secp_ctx, key, UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 2,
+ timestamp: 1,
+ flags,
+ cltv_expiry_delta: (2 << 4) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ }
add_channel(&gossip_sync, &secp_ctx, &privkeys[4], &privkeys[6], ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), 1);
- update_channel(&gossip_sync, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
- chain_hash: ChainHash::using_genesis_block(Network::Testnet),
- short_channel_id: 1,
- timestamp: 1,
- flags: 0,
- cltv_expiry_delta: (1 << 4) | 0,
- htlc_minimum_msat: 100,
- htlc_maximum_msat: MAX_VALUE_MSAT,
- fee_base_msat: 0,
- fee_proportional_millionths: 0,
- excess_data: Vec::new()
- });
+ for (key, flags) in [(&privkeys[4], 0), (&privkeys[6], 3)] {
+ update_channel(&gossip_sync, &secp_ctx, key, UnsignedChannelUpdate {
+ chain_hash: ChainHash::using_genesis_block(Network::Testnet),
+ short_channel_id: 1,
+ timestamp: 1,
+ flags,
+ cltv_expiry_delta: (1 << 4) | 0,
+ htlc_minimum_msat: 100,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ }
add_or_update_node(&gossip_sync, &secp_ctx, &privkeys[6], NodeFeatures::from_le_bytes(id_to_feature_flags(6)), 0);
{
#[test]
#[cfg(feature = "std")]
fn generate_routes() {
- use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters};
+ use crate::routing::scoring::ProbabilisticScoringFeeParameters;
let logger = ln_test_utils::TestLogger::new();
- let graph = match super::bench_utils::read_network_graph(&logger) {
- Ok(f) => f,
+ let (graph, mut scorer) = match super::bench_utils::read_graph_scorer(&logger) {
+ Ok(res) => res,
Err(e) => {
eprintln!("{}", e);
return;
};
let params = ProbabilisticScoringFeeParameters::default();
- let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
let features = super::Bolt11InvoiceFeatures::empty();
super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 0, 2);
#[test]
#[cfg(feature = "std")]
fn generate_routes_mpp() {
- use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters};
+ use crate::routing::scoring::ProbabilisticScoringFeeParameters;
let logger = ln_test_utils::TestLogger::new();
- let graph = match super::bench_utils::read_network_graph(&logger) {
- Ok(f) => f,
+ let (graph, mut scorer) = match super::bench_utils::read_graph_scorer(&logger) {
+ Ok(res) => res,
Err(e) => {
eprintln!("{}", e);
return;
};
let params = ProbabilisticScoringFeeParameters::default();
- let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
let features = channelmanager::provided_bolt11_invoice_features(&UserConfig::default());
super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 0, 2);
#[test]
#[cfg(feature = "std")]
fn generate_large_mpp_routes() {
- use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters};
+ use crate::routing::scoring::ProbabilisticScoringFeeParameters;
let logger = ln_test_utils::TestLogger::new();
- let graph = match super::bench_utils::read_network_graph(&logger) {
- Ok(f) => f,
+ let (graph, mut scorer) = match super::bench_utils::read_graph_scorer(&logger) {
+ Ok(res) => res,
Err(e) => {
eprintln!("{}", e);
return;
};
let params = ProbabilisticScoringFeeParameters::default();
- let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger);
let features = channelmanager::provided_bolt11_invoice_features(&UserConfig::default());
super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 1_000_000, 2);
pub(crate) mod bench_utils {
use super::*;
use std::fs::File;
- use std::time::Duration;
use bitcoin::hashes::Hash;
use bitcoin::secp256k1::SecretKey;
use crate::chain::transaction::OutPoint;
- use crate::routing::scoring::ScoreUpdate;
+ use crate::routing::scoring::{ProbabilisticScorer, ScoreUpdate};
use crate::sign::KeysManager;
- use crate::ln::ChannelId;
- use crate::ln::channelmanager::{self, ChannelCounterparty};
+ use crate::ln::channel_state::{ChannelCounterparty, ChannelShutdownState};
+ use crate::ln::channelmanager;
+ use crate::ln::types::ChannelId;
use crate::util::config::UserConfig;
use crate::util::test_utils::TestLogger;
+ use crate::sync::Arc;
/// Tries to open a network graph file, or panics with a URL to fetch it.
- pub(crate) fn get_route_file() -> Result<std::fs::File, &'static str> {
- let res = File::open("net_graph-2023-01-18.bin") // By default we're run in RL/lightning
- .or_else(|_| File::open("lightning/net_graph-2023-01-18.bin")) // We may be run manually in RL/
- .or_else(|_| { // Fall back to guessing based on the binary location
- // path is likely something like .../rust-lightning/target/debug/deps/lightning-...
- let mut path = std::env::current_exe().unwrap();
- path.pop(); // lightning-...
- path.pop(); // deps
- path.pop(); // debug
- path.pop(); // target
- path.push("lightning");
- path.push("net_graph-2023-01-18.bin");
- File::open(path)
- })
- .or_else(|_| { // Fall back to guessing based on the binary location for a subcrate
- // path is likely something like .../rust-lightning/bench/target/debug/deps/bench..
- let mut path = std::env::current_exe().unwrap();
- path.pop(); // bench...
- path.pop(); // deps
- path.pop(); // debug
- path.pop(); // target
- path.pop(); // bench
- path.push("lightning");
- path.push("net_graph-2023-01-18.bin");
- File::open(path)
- })
- .map_err(|_| "Please fetch https://bitcoin.ninja/ldk-net_graph-v0.0.113-2023-01-18.bin and place it at lightning/net_graph-2023-01-18.bin");
+ pub(crate) fn get_graph_scorer_file() -> Result<(std::fs::File, std::fs::File), &'static str> {
+ let load_file = |fname, err_str| {
+ File::open(fname) // By default we're run in RL/lightning
+ .or_else(|_| File::open(&format!("lightning/{}", fname))) // We may be run manually in RL/
+ .or_else(|_| { // Fall back to guessing based on the binary location
+ // path is likely something like .../rust-lightning/target/debug/deps/lightning-...
+ let mut path = std::env::current_exe().unwrap();
+ path.pop(); // lightning-...
+ path.pop(); // deps
+ path.pop(); // debug
+ path.pop(); // target
+ path.push("lightning");
+ path.push(fname);
+ File::open(path)
+ })
+ .or_else(|_| { // Fall back to guessing based on the binary location for a subcrate
+ // path is likely something like .../rust-lightning/bench/target/debug/deps/bench..
+ let mut path = std::env::current_exe().unwrap();
+ path.pop(); // bench...
+ path.pop(); // deps
+ path.pop(); // debug
+ path.pop(); // target
+ path.pop(); // bench
+ path.push("lightning");
+ path.push(fname);
+ File::open(path)
+ })
+ .map_err(|_| err_str)
+ };
+ let graph_res = load_file(
+ "net_graph-2023-12-10.bin",
+ "Please fetch https://bitcoin.ninja/ldk-net_graph-v0.0.118-2023-12-10.bin and place it at lightning/net_graph-2023-12-10.bin"
+ );
+ let scorer_res = load_file(
+ "scorer-2023-12-10.bin",
+ "Please fetch https://bitcoin.ninja/ldk-scorer-v0.0.118-2023-12-10.bin and place it at lightning/scorer-2023-12-10.bin"
+ );
#[cfg(require_route_graph_test)]
- return Ok(res.unwrap());
+ return Ok((graph_res.unwrap(), scorer_res.unwrap()));
#[cfg(not(require_route_graph_test))]
- return res;
+ return Ok((graph_res?, scorer_res?));
}
- pub(crate) fn read_network_graph(logger: &TestLogger) -> Result<NetworkGraph<&TestLogger>, &'static str> {
- get_route_file().map(|mut f| NetworkGraph::read(&mut f, logger).unwrap())
+ pub(crate) fn read_graph_scorer(logger: &TestLogger)
+ -> Result<(Arc<NetworkGraph<&TestLogger>>, ProbabilisticScorer<Arc<NetworkGraph<&TestLogger>>, &TestLogger>), &'static str> {
+ let (mut graph_file, mut scorer_file) = get_graph_scorer_file()?;
+ let graph = Arc::new(NetworkGraph::read(&mut graph_file, logger).unwrap());
+ let scorer_args = (Default::default(), Arc::clone(&graph), logger);
+ let scorer = ProbabilisticScorer::read(&mut scorer_file, scorer_args).unwrap();
+ Ok((graph, scorer))
}
pub(crate) fn payer_pubkey() -> PublicKey {
inbound_htlc_maximum_msat: None,
config: None,
feerate_sat_per_1000_weight: None,
- channel_shutdown_state: Some(channelmanager::ChannelShutdownState::NotShuttingDown),
+ channel_shutdown_state: Some(ChannelShutdownState::NotShuttingDown),
pending_inbound_htlcs: Vec::new(),
pending_outbound_htlcs: Vec::new(),
}
let nodes = graph.read_only().nodes().clone();
let mut route_endpoints = Vec::new();
- // Fetch 1.5x more routes than we need as after we do some scorer updates we may end up
- // with some routes we picked being un-routable.
- for _ in 0..route_count * 3 / 2 {
+ for _ in 0..route_count {
loop {
seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
let src = PublicKey::from_slice(nodes.unordered_keys()
get_route(&payer, &route_params, &graph.read_only(), Some(&[&first_hop]),
&TestLogger::new(), scorer, score_params, &random_seed_bytes).is_ok();
if path_exists {
- // ...and seed the scorer with success and failure data...
- seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
- let mut score_amt = seed % 1_000_000_000;
- loop {
- // Generate fail/success paths for a wider range of potential amounts with
- // MPP enabled to give us a chance to apply penalties for more potential
- // routes.
- let mpp_features = channelmanager::provided_bolt11_invoice_features(&UserConfig::default());
- let params = PaymentParameters::from_node_id(dst, 42)
- .with_bolt11_features(mpp_features).unwrap();
- let route_params = RouteParameters::from_payment_params_and_value(
- params.clone(), score_amt);
- let route_res = get_route(&payer, &route_params, &graph.read_only(),
- Some(&[&first_hop]), &TestLogger::new(), scorer, score_params,
- &random_seed_bytes);
- if let Ok(route) = route_res {
- for path in route.paths {
- if seed & 0x80 == 0 {
- scorer.payment_path_successful(&path, Duration::ZERO);
- } else {
- let short_channel_id = path.hops[path.hops.len() / 2].short_channel_id;
- scorer.payment_path_failed(&path, short_channel_id, Duration::ZERO);
- }
- seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
- }
- break;
- }
- // If we couldn't find a path with a higher amount, reduce and try again.
- score_amt /= 100;
- }
-
route_endpoints.push((first_hop, params, amt_msat));
break;
}
}
}
- // Because we've changed channel scores, it's possible we'll take different routes to the
- // selected destinations, possibly causing us to fail because, eg, the newly-selected path
- // requires a too-high CLTV delta.
- route_endpoints.retain(|(first_hop, params, amt_msat)| {
- let route_params = RouteParameters::from_payment_params_and_value(
- params.clone(), *amt_msat);
- get_route(&payer, &route_params, &graph.read_only(), Some(&[first_hop]),
- &TestLogger::new(), scorer, score_params, &random_seed_bytes).is_ok()
- });
- route_endpoints.truncate(route_count);
- assert_eq!(route_endpoints.len(), route_count);
route_endpoints
}
}
use crate::ln::channelmanager;
use crate::ln::features::Bolt11InvoiceFeatures;
use crate::routing::gossip::NetworkGraph;
- use crate::routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters};
+ use crate::routing::scoring::{FixedPenaltyScorer, ProbabilisticScoringFeeParameters};
use crate::util::config::UserConfig;
use crate::util::logger::{Logger, Record};
use crate::util::test_utils::TestLogger;
pub fn generate_routes_with_zero_penalty_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, _) = bench_utils::read_graph_scorer(&logger).unwrap();
let scorer = FixedPenaltyScorer::with_penalty(0);
generate_routes(bench, &network_graph, scorer, &Default::default(),
Bolt11InvoiceFeatures::empty(), 0, "generate_routes_with_zero_penalty_scorer");
pub fn generate_mpp_routes_with_zero_penalty_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, _) = bench_utils::read_graph_scorer(&logger).unwrap();
let scorer = FixedPenaltyScorer::with_penalty(0);
generate_routes(bench, &network_graph, scorer, &Default::default(),
channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0,
pub fn generate_routes_with_probabilistic_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap();
let params = ProbabilisticScoringFeeParameters::default();
- let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, ¶ms, Bolt11InvoiceFeatures::empty(), 0,
"generate_routes_with_probabilistic_scorer");
}
pub fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap();
let params = ProbabilisticScoringFeeParameters::default();
- let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, ¶ms,
channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0,
"generate_mpp_routes_with_probabilistic_scorer");
pub fn generate_large_mpp_routes_with_probabilistic_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap();
let params = ProbabilisticScoringFeeParameters::default();
- let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, ¶ms,
channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 100_000_000,
"generate_large_mpp_routes_with_probabilistic_scorer");
pub fn generate_routes_with_nonlinear_probabilistic_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap();
let mut params = ProbabilisticScoringFeeParameters::default();
params.linear_success_probability = false;
- let scorer = ProbabilisticScorer::new(
- ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, ¶ms,
channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0,
"generate_routes_with_nonlinear_probabilistic_scorer");
pub fn generate_mpp_routes_with_nonlinear_probabilistic_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap();
let mut params = ProbabilisticScoringFeeParameters::default();
params.linear_success_probability = false;
- let scorer = ProbabilisticScorer::new(
- ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, ¶ms,
channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0,
"generate_mpp_routes_with_nonlinear_probabilistic_scorer");
pub fn generate_large_mpp_routes_with_nonlinear_probabilistic_scorer(bench: &mut Criterion) {
let logger = TestLogger::new();
- let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap();
let mut params = ProbabilisticScoringFeeParameters::default();
params.linear_success_probability = false;
- let scorer = ProbabilisticScorer::new(
- ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, ¶ms,
channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 100_000_000,
"generate_large_mpp_routes_with_nonlinear_probabilistic_scorer");
score_params: &S::ScoreParams, features: Bolt11InvoiceFeatures, starting_amount: u64,
bench_name: &'static str,
) {
- let payer = bench_utils::payer_pubkey();
- let keys_manager = KeysManager::new(&[0u8; 32], 42, 42);
- let random_seed_bytes = keys_manager.get_secure_random_bytes();
-
// First, get 100 (source, destination) pairs for which route-getting actually succeeds...
let route_endpoints = bench_utils::generate_test_routes(graph, &mut scorer, score_params, features, 0xdeadbeef, starting_amount, 50);
// ...then benchmark finding paths between the nodes we learned.
+ do_route_bench(bench, graph, scorer, score_params, bench_name, route_endpoints);
+ }
+
+ #[inline(never)]
+ fn do_route_bench<S: ScoreLookUp + ScoreUpdate>(
+ bench: &mut Criterion, graph: &NetworkGraph<&TestLogger>, scorer: S,
+ score_params: &S::ScoreParams, bench_name: &'static str,
+ route_endpoints: Vec<(ChannelDetails, PaymentParameters, u64)>,
+ ) {
+ let payer = bench_utils::payer_pubkey();
+ let keys_manager = KeysManager::new(&[0u8; 32], 42, 42);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+
let mut idx = 0;
bench.bench_function(bench_name, |b| b.iter(|| {
let (first_hop, params, amt) = &route_endpoints[idx % route_endpoints.len()];
projects / rust-lightning / blobdiff