X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=399126c6fd33bc5d4a0f799a1d0bd6145c619452;hb=5df414c25b1b710bea5e48e5183a28751b374659;hp=6bdf59e852f94417eb44dc5e08f0de43c11f7918;hpb=259ceb0ebfe7082e2dfebc39a2ad7edefea56b19;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 6bdf59e8..399126c6 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -89,10 +89,14 @@ macro_rules! define_score { ($($supertrait: path)*) => { /// `ScoreLookUp` is used to determine the penalty for a given channel. /// /// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel. -pub trait ScoreLookUp $(: $supertrait)* { +pub trait ScoreLookUp { + #[cfg(not(c_bindings))] /// A configurable type which should contain various passed-in parameters for configuring the scorer, /// on a per-routefinding-call basis through to the scorer methods, /// which are used to determine the parameters for the suitability of channels for use. + /// + /// Note that due to limitations in many other languages' generics features, language bindings + /// use [`ProbabilisticScoringFeeParameters`] for the parameters on all scorers. type ScoreParams; /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the /// given channel in the direction from `source` to `target`. @@ -103,12 +107,12 @@ pub trait ScoreLookUp $(: $supertrait)* { /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount. /// Thus, implementations should be overflow-safe. fn channel_penalty_msat( - &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams + &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters ) -> u64; } /// `ScoreUpdate` is used to update the scorer's internal state after a payment attempt. -pub trait ScoreUpdate $(: $supertrait)* { +pub trait ScoreUpdate { /// Handles updating channel penalties after failing to route through a channel. fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64); @@ -122,16 +126,30 @@ pub trait ScoreUpdate $(: $supertrait)* { fn probe_successful(&mut self, path: &Path); } -impl, T: Deref $(+ $supertrait)*> ScoreLookUp for T { - type ScoreParams = SP; +/// A trait which can both lookup and update routing channel penalty scores. +/// +/// This is used in places where both bounds are required and implemented for all types which +/// implement [`ScoreLookUp`] and [`ScoreUpdate`]. +/// +/// Bindings users may need to manually implement this for their custom scoring implementations. +pub trait Score : ScoreLookUp + ScoreUpdate $(+ $supertrait)* {} + +#[cfg(not(c_bindings))] +impl Score for T {} + +#[cfg(not(c_bindings))] +impl> ScoreLookUp for T { + #[cfg(not(c_bindings))] + type ScoreParams = S::ScoreParams; fn channel_penalty_msat( - &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams + &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters ) -> u64 { self.deref().channel_penalty_msat(short_channel_id, source, target, usage, score_params) } } -impl $(+ $supertrait)*> ScoreUpdate for T { +#[cfg(not(c_bindings))] +impl> ScoreUpdate for T { fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) { self.deref_mut().payment_path_failed(path, short_channel_id) } @@ -192,7 +210,7 @@ pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {} #[cfg(not(c_bindings))] impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {} #[cfg(not(c_bindings))] -impl<'a, T: 'a + ScoreLookUp + ScoreUpdate> LockableScore<'a> for Mutex { +impl<'a, T: Score + 'a> LockableScore<'a> for Mutex { type ScoreUpdate = T; type ScoreLookUp = T; @@ -209,7 +227,7 @@ impl<'a, T: 'a + ScoreLookUp + ScoreUpdate> LockableScore<'a> for Mutex { } #[cfg(not(c_bindings))] -impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> LockableScore<'a> for RefCell { +impl<'a, T: Score + 'a> LockableScore<'a> for RefCell { type ScoreUpdate = T; type ScoreLookUp = T; @@ -226,7 +244,7 @@ impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> LockableScore<'a> for RefCell { } #[cfg(not(c_bindings))] -impl<'a, SP:Sized, T: 'a + ScoreUpdate + ScoreLookUp> LockableScore<'a> for RwLock { +impl<'a, T: Score + 'a> LockableScore<'a> for RwLock { type ScoreUpdate = T; type ScoreLookUp = T; @@ -244,12 +262,12 @@ impl<'a, SP:Sized, T: 'a + ScoreUpdate + ScoreLookUp> Lockabl #[cfg(c_bindings)] /// A concrete implementation of [`LockableScore`] which supports multi-threading. -pub struct MultiThreadedLockableScore { +pub struct MultiThreadedLockableScore { score: RwLock, } #[cfg(c_bindings)] -impl<'a, SP:Sized, T: 'a + ScoreLookUp + ScoreUpdate> LockableScore<'a> for MultiThreadedLockableScore { +impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore { type ScoreUpdate = T; type ScoreLookUp = T; type WriteLocked = MultiThreadedScoreLockWrite<'a, Self::ScoreUpdate>; @@ -265,17 +283,17 @@ impl<'a, SP:Sized, T: 'a + ScoreLookUp + ScoreUpdate> Lockable } #[cfg(c_bindings)] -impl Writeable for MultiThreadedLockableScore { +impl Writeable for MultiThreadedLockableScore { fn write(&self, writer: &mut W) -> Result<(), io::Error> { self.score.read().unwrap().write(writer) } } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> WriteableScore<'a> for MultiThreadedLockableScore {} +impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore {} #[cfg(c_bindings)] -impl MultiThreadedLockableScore { +impl MultiThreadedLockableScore { /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`]. pub fn new(score: T) -> Self { MultiThreadedLockableScore { score: RwLock::new(score) } @@ -284,14 +302,14 @@ impl MultiThreadedLockableScore { #[cfg(c_bindings)] /// A locked `MultiThreadedLockableScore`. -pub struct MultiThreadedScoreLockRead<'a, T: ScoreLookUp>(RwLockReadGuard<'a, T>); +pub struct MultiThreadedScoreLockRead<'a, T: Score>(RwLockReadGuard<'a, T>); #[cfg(c_bindings)] /// A locked `MultiThreadedLockableScore`. -pub struct MultiThreadedScoreLockWrite<'a, T: ScoreUpdate>(RwLockWriteGuard<'a, T>); +pub struct MultiThreadedScoreLockWrite<'a, T: Score>(RwLockWriteGuard<'a, T>); #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreLookUp> Deref for MultiThreadedScoreLockRead<'a, T> { +impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockRead<'a, T> { type Target = T; fn deref(&self) -> &Self::Target { @@ -300,14 +318,25 @@ impl<'a, T: 'a + ScoreLookUp> Deref for MultiThreadedScoreLockRead<'a, T> { } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate> Writeable for MultiThreadedScoreLockWrite<'a, T> { +impl<'a, T: Score> ScoreLookUp for MultiThreadedScoreLockRead<'a, T> { + #[cfg(not(c_bindings))] + type ScoreParams = T::ScoreParams; + fn channel_penalty_msat(&self, short_channel_id: u64, source: &NodeId, + target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters + ) -> u64 { + self.0.channel_penalty_msat(short_channel_id, source, target, usage, score_params) + } +} + +#[cfg(c_bindings)] +impl<'a, T: Score> Writeable for MultiThreadedScoreLockWrite<'a, T> { fn write(&self, writer: &mut W) -> Result<(), io::Error> { self.0.write(writer) } } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate> Deref for MultiThreadedScoreLockWrite<'a, T> { +impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockWrite<'a, T> { type Target = T; fn deref(&self) -> &Self::Target { @@ -316,12 +345,31 @@ impl<'a, T: 'a + ScoreUpdate> Deref for MultiThreadedScoreLockWrite<'a, T> { } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate> DerefMut for MultiThreadedScoreLockWrite<'a, T> { +impl<'a, T: 'a + Score> DerefMut for MultiThreadedScoreLockWrite<'a, T> { fn deref_mut(&mut self) -> &mut Self::Target { self.0.deref_mut() } } +#[cfg(c_bindings)] +impl<'a, T: Score> ScoreUpdate for MultiThreadedScoreLockWrite<'a, T> { + fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) { + self.0.payment_path_failed(path, short_channel_id) + } + + fn payment_path_successful(&mut self, path: &Path) { + self.0.payment_path_successful(path) + } + + fn probe_failed(&mut self, path: &Path, short_channel_id: u64) { + self.0.probe_failed(path, short_channel_id) + } + + fn probe_successful(&mut self, path: &Path) { + self.0.probe_successful(path) + } +} + /// Proposed use of a channel passed as a parameter to [`ScoreLookUp::channel_penalty_msat`]. #[derive(Clone, Copy, Debug, PartialEq)] @@ -351,8 +399,9 @@ impl FixedPenaltyScorer { } impl ScoreLookUp for FixedPenaltyScorer { + #[cfg(not(c_bindings))] type ScoreParams = (); - fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage, _score_params: &Self::ScoreParams) -> u64 { + fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage, _score_params: &ProbabilisticScoringFeeParameters) -> u64 { self.penalty_msat } } @@ -384,12 +433,45 @@ impl ReadableArgs for FixedPenaltyScorer { } #[cfg(not(feature = "no-std"))] -type ConfiguredTime = crate::util::time::MonotonicTime; -#[cfg(feature = "no-std")] -use crate::util::time::Eternity; -#[cfg(feature = "no-std")] -type ConfiguredTime = Eternity; +/// [`ScoreLookUp`] implementation using channel success probability distributions. +/// +/// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel, +/// we learn that the upper-bound on the available liquidity is lower than the amount of the HTLC. +/// When a payment is forwarded through a channel (but fails later in the route), we learn the +/// lower-bound on the channel's available liquidity must be at least the value of the HTLC. +/// +/// These bounds are then used to determine a success probability using the formula from +/// *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt +/// and Stefan Richter [[1]] (i.e. `(upper_bound - payment_amount) / (upper_bound - lower_bound)`). +///6762, 1070 +/// This probability is combined with the [`liquidity_penalty_multiplier_msat`] and +/// [`liquidity_penalty_amount_multiplier_msat`] parameters to calculate a concrete penalty in +/// milli-satoshis. The penalties, when added across all hops, have the property of being linear in +/// terms of the entire path's success probability. This allows the router to directly compare +/// penalties for different paths. See the documentation of those parameters for the exact formulas. +/// +/// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`]. +/// +/// Further, we track the history of our upper and lower liquidity bounds for each channel, +/// allowing us to assign a second penalty (using [`historical_liquidity_penalty_multiplier_msat`] +/// and [`historical_liquidity_penalty_amount_multiplier_msat`]) based on the same probability +/// formula, but using the history of a channel rather than our latest estimates for the liquidity +/// bounds. +/// +/// # Note +/// +/// Mixing the `no-std` feature between serialization and deserialization results in undefined +/// behavior. +/// +/// [1]: https://arxiv.org/abs/2107.05322 +/// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_multiplier_msat +/// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_amount_multiplier_msat +/// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life +/// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_multiplier_msat +/// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat +pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; +#[cfg(feature = "no-std")] /// [`ScoreLookUp`] implementation using channel success probability distributions. /// /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel, @@ -426,7 +508,7 @@ type ConfiguredTime = Eternity; /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_multiplier_msat /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat -pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; +pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; /// Probabilistic [`ScoreLookUp`] implementation. /// @@ -1299,6 +1381,7 @@ impl, BRT: DerefMut>, L: Deref, T: Time> ScoreLookUp for ProbabilisticScorerUsingTime where L::Target: Logger { + #[cfg(not(c_bindings))] type ScoreParams = ProbabilisticScoringFeeParameters; fn channel_penalty_msat( &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters @@ -1417,6 +1500,10 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob } } +#[cfg(c_bindings)] +impl>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime +where L::Target: Logger {} + mod approx { const BITS: u32 = 64; const HIGHEST_BIT: u32 = BITS - 1; @@ -2133,7 +2220,7 @@ mod tests { use crate::util::ser::{ReadableArgs, Writeable}; use crate::util::test_utils::{self, TestLogger}; - use bitcoin::blockdata::constants::genesis_block; + use bitcoin::blockdata::constants::ChainHash; use bitcoin::hashes::Hash; use bitcoin::hashes::sha256d::Hash as Sha256dHash; use bitcoin::network::constants::Network; @@ -2210,7 +2297,7 @@ mod tests { network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey, node_2_key: SecretKey ) { - let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let genesis_hash = ChainHash::using_genesis_block(Network::Testnet); let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap(); let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap(); let secp_ctx = Secp256k1::new(); @@ -2243,7 +2330,7 @@ mod tests { network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey, flags: u8, htlc_maximum_msat: u64, timestamp: u32, ) { - let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let genesis_hash = ChainHash::using_genesis_block(Network::Testnet); let secp_ctx = Secp256k1::new(); let unsigned_update = UnsignedChannelUpdate { chain_hash: genesis_hash, @@ -2274,6 +2361,7 @@ mod tests { channel_features: channelmanager::provided_channel_features(&config), fee_msat, cltv_expiry_delta: 18, + maybe_announced_channel: true, } }