pub cltv_expiry_delta: u32,
}
+/// (C-not exported)
impl Writeable for Vec<RouteHop> {
fn write<W: ::util::ser::Writer>(&self, writer: &mut W) -> Result<(), ::std::io::Error> {
(self.len() as u8).write(writer)?;
}
}
+/// (C-not exported)
impl Readable for Vec<RouteHop> {
fn read<R: ::std::io::Read>(reader: &mut R) -> Result<Vec<RouteHop>, DecodeError> {
let hops_count: u8 = Readable::read(reader)?;
return result;
}
- // If an amount transferred by the path is updated, the fees should be adjusted. Any other way
- // to change fees may result in an inconsistency. Also, it's only safe to reduce the value,
- // to not violate channel upper bounds.
+ // If the amount transferred by the path is updated, the fees should be adjusted. Any other way
+ // to change fees may result in an inconsistency.
+ //
+ // Sometimes we call this function right after constructing a path which has inconsistent
+ // (in terms of reaching htlc_minimum_msat), so that this function puts the fees in order.
+ // In that case we call it on the "same" amount we initially allocated for this path, and which
+ // could have been reduced on the way. In that case, there is also a risk of exceeding
+ // available_liquidity inside this function, because the function is unaware of this bound.
+ // In our specific recomputation cases where we never increase the value the risk is pretty low.
+ // This function, however, does not support arbitrarily increasing the value being transferred,
+ // and the exception will be triggered.
fn update_value_and_recompute_fees(&mut self, value_msat: u64) {
- if value_msat == self.hops.last().unwrap().route_hop.fee_msat {
- // Nothing to change.
- return;
- }
- assert!(value_msat < self.hops.last().unwrap().route_hop.fee_msat);
+ assert!(value_msat <= self.hops.last().unwrap().route_hop.fee_msat);
let mut total_fee_paid_msat = 0 as u64;
for i in (0..self.hops.len()).rev() {
// match htlc_minimum_msat logic.
let mut cur_hop_transferred_amount_msat = total_fee_paid_msat + value_msat;
if let Some(extra_fees_msat) = cur_hop.htlc_minimum_msat.checked_sub(cur_hop_transferred_amount_msat) {
+ // Note that there is a risk that *previous hops* (those closer to us, as we go
+ // payee->our_node here) would exceed their htlc_maximum_msat or available balance.
+ //
+ // This might make us end up with a broken route, although this should be super-rare
+ // in practice, both because of how healthy channels look like, and how we pick
+ // channels in add_entry.
+ // Also, this can't be exploited more heavily than *announce a free path and fail
+ // all payments*.
cur_hop_transferred_amount_msat += extra_fees_msat;
total_fee_paid_msat += extra_fees_msat;
cur_hop_fees_msat += extra_fees_msat;
// as not sufficient.
// TODO: Explore simply adding fee to hit htlc_minimum_msat
if contributes_sufficient_value && amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat {
+ // Note that low contribution here (limited by available_liquidity_msat)
+ // might violate htlc_minimum_msat on the hops which are next along the
+ // payment path (upstream to the payee). To avoid that, we recompute path
+ // path fees knowing the final path contribution after constructing it.
let hm_entry = dist.entry(&$src_node_id);
let old_entry = hm_entry.or_insert_with(|| {
// If there was previously no known way to access
ordered_hops.last_mut().unwrap().hop_use_fee_msat = 0;
ordered_hops.last_mut().unwrap().route_hop.cltv_expiry_delta = final_cltv;
- let payment_path = PaymentPath {hops: ordered_hops};
+ let mut payment_path = PaymentPath {hops: ordered_hops};
+
+ // We could have possibly constructed a slightly inconsistent path: since we reduce
+ // value being transferred along the way, we could have violated htlc_minimum_msat
+ // on some channels we already passed (assuming dest->source direction). Here, we
+ // recompute the fees again, so that if that's the case, we match the currently
+ // underpaid htlc_minimum_msat with fees.
+ payment_path.update_value_and_recompute_fees(value_contribution_msat);
+
// Since a path allows to transfer as much value as
// the smallest channel it has ("bottleneck"), we should recompute
// the fees so sender HTLC don't overpay fees when traversing
}
}
+
+#[cfg(all(test, feature = "unstable"))]
+mod benches {
+ use super::*;
+ use util::logger::{Logger, Record};
+
+ use std::fs::File;
+ use test::Bencher;
+
+ struct DummyLogger {}
+ impl Logger for DummyLogger {
+ fn log(&self, _record: &Record) {}
+ }
+
+ #[bench]
+ fn generate_routes(bench: &mut Bencher) {
+ let mut d = File::open("net_graph-2021-02-12.bin").expect("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin");
+ let graph = NetworkGraph::read(&mut d).unwrap();
+
+ // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
+ let mut path_endpoints = Vec::new();
+ let mut seed: usize = 0xdeadbeef;
+ 'load_endpoints: for _ in 0..100 {
+ loop {
+ seed *= 0xdeadbeef;
+ let src = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ seed *= 0xdeadbeef;
+ let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ let amt = seed as u64 % 1_000_000;
+ if get_route(src, &graph, dst, None, &[], amt, 42, &DummyLogger{}).is_ok() {
+ path_endpoints.push((src, dst, amt));
+ continue 'load_endpoints;
+ }
+ }
+ }
+
+ // ...then benchmark finding paths between the nodes we learned.
+ let mut idx = 0;
+ bench.iter(|| {
+ let (src, dst, amt) = path_endpoints[idx % path_endpoints.len()];
+ assert!(get_route(src, &graph, dst, None, &[], amt, 42, &DummyLogger{}).is_ok());
+ idx += 1;
+ });
+ }
+}