← Watch feed
Use balance estimates from past payments in path-finding (#2308)
Public commit record
81/100 · Strong
What the developer wrote
Authored by Thomas HUET
Use balance estimates from past payments in path-finding (#2308)
We estimate the probability that a given route can relay a given payment as part of route selection.
Until now this estimate was naively assuming the channel balances to be uniformly distributed.
We will now use data from past payment attempts (both successes and failures) to provide a better estimate, hopefully improving route selection.
✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Links an issue, advisory, or supporting reference
What changed, and why it matters
This commit improves Eclair's Lightning payment routing by optionally using past payment successes and failures to estimate how much money each channel can forward, instead of assuming balances are random. It is a feature enhancement, not a security patch. There is no indication in the commit or supplied references that it fixes a vulnerability.
Recommended action
Review the removed probability-bounds guard to ensure `BalanceEstimate.canSend` cannot return values outside [0,1] under any input; if it can, reintroduce a clamp or invariant check. Monitor for potential probing-based manipulation of the new balance estimator, though this is a normal operational risk rather than an immediate vulnerability.
Security signals we found
01
Removal of a runtime log.error guard in BalanceEstimate.canSend that previously flagged out-of-range probability estimates
02
New heuristic uses historical payment metadata to influence route selection, which could be manipulated if an attacker can induce many failed/successful probes
03
No bounds check is visible in the diff for the probability returned by balance.canSend; the removed guard was the only explicit one
Evidence from the diff
The change adds a new path-finding heuristic flag use-past-relay-data (default false). When enabled and use-ratios = false, the router uses BalanceEstimate data derived from previous relay attempts to compute a per-edge success probability, replacing the prior uniform-balance assumption (1 - amount/capacity). The commit refactors Graph algorithms to accept GraphWithBalanceEstimates and threads BalanceEstimate into addEdgeWeight. It also removes a defensive log.error guard in BalanceEstimate.canSend that warned when the computed probability was outside [0,1].
Changed components
eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scalaeclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scalaeclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scalaeclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scalaeclair-core/src/main/resources/reference.confInspect captured patch +295 / −241
diff --git a/docs/release-notes/eclair-vnext.md b/docs/release-notes/eclair-vnext.md
index 0fa5221..8d5f76b 100644
--- a/docs/release-notes/eclair-vnext.md
+++ b/docs/release-notes/eclair-vnext.md
@@ -49,6 +49,12 @@ eclair.relay.peer-reputation {
}
```
+### Use past payment attempts to estimate payment success
+
+When setting `use-ratios = false` in `eclair.router.path-finding`, we estimate the probability that a given route can relay a given payment as part of route selection.
+Until now this estimate was naively assuming the channel balances to be uniformly distributed.
+By setting `use-past-relay-data = true`, we will now use data from past payment attempts (both successes and failures) to provide a better estimate, hopefully improving route selection.
+
### API changes
- `listoffers` now returns more details about each offer.
diff --git a/eclair-core/src/main/resources/reference.conf b/eclair-core/src/main/resources/reference.conf
index 2c68f5d..efbee29 100644
--- a/eclair-core/src/main/resources/reference.conf
+++ b/eclair-core/src/main/resources/reference.conf
@@ -458,6 +458,11 @@ eclair {
default {
randomize-route-selection = true // when computing a route for a payment we randomize the final selection
+ mpp {
+ min-amount-satoshis = 15000 // minimum amount sent via partial HTLCs
+ max-parts = 5 // maximum number of HTLCs sent per payment: increasing this value will impact performance
+ }
+
boundaries {
max-route-length = 6 // max route length for the 'first pass', if none is found then a second pass is made with no limit
max-cltv = 2016 // max acceptable cltv expiry for the payment (2016 ~ 2 weeks)
@@ -466,7 +471,14 @@ eclair {
max-fee-proportional-percent = 3 // that's 3%
}
- use-ratios = true // if false, will use failure-cost
+ hop-cost {
+ // virtual fee for additional hops: how much you are willing to pay to get one less hop in the payment path
+ fee-base-msat = 500
+ fee-proportional-millionths = 200
+ }
+
+ use-ratios = true // if true, will use `ratios`, if false, will use `failure-cost`, `locked-funds-risk`, `use-log-probability`, `use-past-relay-data`.
+
// channel 'weight' is computed with the following formula: (channelFee + hop-cost) * (ratio-base + cltvDelta * ratio-cltv + channelAge * ratio-channel-age + channelCapacity * ratio-channel-capacity)
// the following parameters can be used to ask the router to use heuristics to find i.e: 'cltv-optimized' routes, **the sum of the four ratios must be 1**
ratios {
@@ -476,17 +488,12 @@ eclair {
channel-capacity = 0.55 // when computing the weight for a channel, consider its CAPACITY in this proportion
}
- hop-cost {
- // virtual fee for additional hops: how much you are willing to pay to get one less hop in the payment path
- fee-base-msat = 500
- fee-proportional-millionths = 200
- }
+ // Everything below is ignored if use-ratio = true.
locked-funds-risk = 1e-8 // msat per msat locked per block. It should be your expected interest rate per block multiplied by the probability that something goes wrong and your funds stay locked.
// 1e-8 corresponds to an interest rate of ~5% per year (1e-6 per block) and a probability of 1% that the channel will fail and our funds will be locked.
// virtual fee for failed payments: how much you are willing to pay to get one less failed payment attempt
- // ignored if use-ratio = true
failure-cost {
fee-base-msat = 2000
fee-proportional-millionths = 500
@@ -497,10 +504,10 @@ eclair {
// probability of success, however is penalizes less the paths with a low probability of success.
use-log-probability = false
- mpp {
- min-amount-satoshis = 15000 // minimum amount sent via partial HTLCs
- max-parts = 5 // maximum number of HTLCs sent per payment: increasing this value will impact performance
- }
+ // When set to false, we assume that the balances of channels are uniformly distributed. That means the
+ // probability that we can send an amount X through a channel of capacity C is 1 - X / C.
+ // When set to true, past payments attempts will be used to compute a better estimate.
+ use-past-relay-data = false
}
// The path-finding algo uses one or more sets of parameters named experiments. Each experiment has a percentage
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala b/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala
index 64b5312..4e835c5 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/NodeParams.scala
@@ -474,6 +474,7 @@ object NodeParams extends Logging {
failureFees = getRelayFees(config.getConfig("failure-cost")),
hopFees = getRelayFees(config.getConfig("hop-cost")),
useLogProbability = config.getBoolean("use-log-probability"),
+ usePastRelaysData = config.getBoolean("use-past-relay-data"),
)
},
mpp = MultiPartParams(
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala b/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala
index f04a143..6c26610 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/remote/EclairInternalsSerializer.scala
@@ -68,7 +68,8 @@ object EclairInternalsSerializer {
("lockedFundsRisk" | double) ::
("failureCost" | relayFeesCodec) ::
("hopCost" | relayFeesCodec) ::
- ("useLogProbability" | bool(8))).as[HeuristicsConstants]
+ ("useLogProbability" | bool(8)) ::
+ ("usePastRelaysData" | bool(8))).as[HeuristicsConstants]
val weightRatiosCodec: Codec[WeightRatios[PaymentPathWeight]] =
discriminated[WeightRatios[PaymentPathWeight]].by(uint8)
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala b/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala
index 21e86b0..7a492e2 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/router/BalanceEstimate.scala
@@ -24,7 +24,7 @@ import fr.acinq.eclair.router.Router.{ChannelDesc, ChannelHop, Route}
import fr.acinq.eclair.wire.protocol.NodeAnnouncement
import fr.acinq.eclair.{MilliSatoshi, MilliSatoshiLong, RealShortChannelId, ShortChannelId, TimestampSecond, TimestampSecondLong, ToMilliSatoshiConversion}
-import scala.concurrent.duration.{DurationInt, FiniteDuration}
+import scala.concurrent.duration.FiniteDuration
/**
* Estimates the balance between a pair of nodes
@@ -216,7 +216,7 @@ case class BalanceEstimate private(low: MilliSatoshi,
* - probability that it can relay a payment of high is decay(high, 0, highTimestamp) which is close to 0 if highTimestamp is recent
* - probability that it can relay a payment of maxCapacity is 0
*/
- def canSend(amount: MilliSatoshi, now: TimestampSecond)(implicit log: LoggingAdapter): Double = {
+ def canSend(amount: MilliSatoshi, now: TimestampSecond): Double = {
val a = amount.toLong.toDouble
val l = low.toLong.toDouble
val h = high.toLong.toDouble
@@ -226,7 +226,7 @@ case class BalanceEstimate private(low: MilliSatoshi,
val pLow = decay(low, 1, lowTimestamp, now)
val pHigh = decay(high, 0, highTimestamp, now)
- val estimate = if (amount < low) {
+ if (amount < low) {
(l - a * (1.0 - pLow)) / l
} else if (amount < high) {
((h - a) * pLow + (a - l) * pHigh) / (h - l)
@@ -235,12 +235,6 @@ case class BalanceEstimate private(low: MilliSatoshi,
} else {
0
}
-
- if (estimate < 0 || estimate > 1) {
- log.error("Could not estimate balance: this={}, amount={}, now={}", this, amount, now)
- }
-
- estimate
}
}
@@ -254,6 +248,8 @@ object BalanceEstimate {
case class BalancesEstimates(balances: Map[(PublicKey, PublicKey), BalanceEstimate], defaultHalfLife: FiniteDuration) {
private def get(a: PublicKey, b: PublicKey): Option[BalanceEstimate] = balances.get((a, b))
+ def get(edge: GraphEdge): BalanceEstimate = get(edge.desc.a, edge.desc.b).getOrElse(BalanceEstimate.empty(defaultHalfLife).addEdge(edge))
+
def addEdge(edge: GraphEdge): BalancesEstimates = BalancesEstimates(
balances.updatedWith((edge.desc.a, edge.desc.b))(balance =>
Some(balance.getOrElse(BalanceEstimate.empty(defaultHalfLife)).addEdge(edge))
@@ -314,7 +310,7 @@ case class BalancesEstimates(balances: Map[(PublicKey, PublicKey), BalanceEstima
}
-case class GraphWithBalanceEstimates(graph: DirectedGraph, private val balances: BalancesEstimates) {
+case class GraphWithBalanceEstimates(graph: DirectedGraph, balances: BalancesEstimates) {
def addOrUpdateVertex(ann: NodeAnnouncement): GraphWithBalanceEstimates = GraphWithBalanceEstimates(graph.addOrUpdateVertex(ann), balances)
def addEdge(edge: GraphEdge): GraphWithBalanceEstimates = GraphWithBalanceEstimates(graph.addEdge(edge), balances.addEdge(edge))
@@ -356,13 +352,6 @@ case class GraphWithBalanceEstimates(graph: DirectedGraph, private val balances:
def channelCouldNotSend(hop: ChannelHop, amount: MilliSatoshi)(implicit log: LoggingAdapter): GraphWithBalanceEstimates = {
GraphWithBalanceEstimates(graph, balances.channelCouldNotSend(hop, amount))
}
-
- def canSend(amount: MilliSatoshi, edge: GraphEdge)(implicit log: LoggingAdapter): Double = {
- balances.balances.get((edge.desc.a, edge.desc.b)) match {
- case Some(estimate) => estimate.canSend(amount, TimestampSecond.now())
- case None => BalanceEstimate.empty(1 hour).addEdge(edge).canSend(amount, TimestampSecond.now())
- }
- }
}
object GraphWithBalanceEstimates {
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala b/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala
index a7e6676..12ca028 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/router/Graph.scala
@@ -84,7 +84,7 @@ object Graph {
* @param currentBlockHeight the height of the chain tip (latest block).
* @param includeLocalChannelCost if the path is for relaying and we need to include the cost of the local channel
*/
- def addEdgeWeight(sender: PublicKey, edge: GraphEdge, prev: RichWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): RichWeight
+ def addEdgeWeight(sender: PublicKey, edge: GraphEdge, balance: BalanceEstimate, prev: RichWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): RichWeight
}
/**
@@ -98,7 +98,7 @@ object Graph {
require(ageFactor >= 0.0, "ratio-channel-age must be nonnegative")
require(capacityFactor >= 0.0, "ratio-channel-capacity must be nonnegative")
- override def addEdgeWeight(sender: PublicKey, edge: GraphEdge, prev: PaymentPathWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): PaymentPathWeight = {
+ override def addEdgeWeight(sender: PublicKey, edge: GraphEdge, balance: BalanceEstimate, prev: PaymentPathWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): PaymentPathWeight = {
val totalAmount = if (edge.desc.a == sender && !includeLocalChannelCost) prev.amount else addEdgeFees(edge, prev.amount)
val fee = totalAmount - prev.amount
val totalFees = prev.fees + fee
@@ -143,12 +143,13 @@ object Graph {
* The fee for a failed attempt and the fee per hop are never actually spent, they are used to incentivize shorter
* paths or path with higher success probability.
*
- * @param lockedFundsRisk cost of having funds locked in htlc in msat per msat per block
- * @param failureFees fee for a failed attempt
- * @param hopFees virtual fee per hop (how much we're willing to pay to make the route one hop shorter)
+ * @param lockedFundsRisk cost of having funds locked in htlc in msat per msat per block
+ * @param failureFees fee for a failed attempt
+ * @param hopFees virtual fee per hop (how much we're willing to pay to make the route one hop shorter)
+ * @param usePastRelaysData use data from past relays to estimate the balance of the channels
*/
- case class HeuristicsConstants(lockedFundsRisk: Double, failureFees: RelayFees, hopFees: RelayFees, useLogProbability: Boolean) extends WeightRatios[PaymentPathWeight] {
- override def addEdgeWeight(sender: PublicKey, edge: GraphEdge, prev: PaymentPathWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): PaymentPathWeight = {
+ case class HeuristicsConstants(lockedFundsRisk: Double, failureFees: RelayFees, hopFees: RelayFees, useLogProbability: Boolean, usePastRelaysData: Boolean) extends WeightRatios[PaymentPathWeight] {
+ override def addEdgeWeight(sender: PublicKey, edge: GraphEdge, balance: BalanceEstimate, prev: PaymentPathWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): PaymentPathWeight = {
val totalAmount = if (edge.desc.a == sender && !includeLocalChannelCost) prev.amount else addEdgeFees(edge, prev.amount)
val fee = totalAmount - prev.amount
val totalFees = prev.fees + fee
@@ -157,7 +158,14 @@ object Graph {
val hopCost = nodeFee(hopFees, prev.amount)
val totalHopsCost = prev.virtualFees + hopCost
// If we know the balance of the channel, then we will check separately that it can relay the payment.
- val successProbability = if (edge.balance_opt.nonEmpty) 1.0 else 1.0 - prev.amount.toLong.toDouble / edge.capacity.toMilliSatoshi.toLong.toDouble
+ val successProbability =
+ if (edge.balance_opt.nonEmpty) {
+ 1.0
+ } else if (usePastRelaysData) {
+ balance.canSend(prev.amount, TimestampSecond.now())
+ } else {
+ 1.0 - prev.amount.toLong.toDouble / edge.capacity.toMilliSatoshi.toLong.toDouble
+ }
if (successProbability < 0) {
throw NegativeProbability(edge, prev, this)
}
@@ -187,7 +195,7 @@ object Graph {
require(ageFactor >= 0.0, "ratio-channel-age must be nonnegative")
require(capacityFactor >= 0.0, "ratio-channel-capacity must be nonnegative")
- override def addEdgeWeight(sender: PublicKey, edge: GraphEdge, prev: MessagePathWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): MessagePathWeight = {
+ override def addEdgeWeight(sender: PublicKey, edge: GraphEdge, balance: BalanceEstimate, prev: MessagePathWeight, currentBlockHeight: BlockHeight, includeLocalChannelCost: Boolean): MessagePathWeight = {
import RoutingHeuristics._
// Every edge is weighted by funding block height where older blocks add less weight. The window considered is 1 year.
@@ -245,7 +253,7 @@ object Graph {
* @param boundaries a predicate function that can be used to impose limits on the outcome of the search
* @param includeLocalChannelCost if the path is for relaying and we need to include the cost of the local channel
*/
- def yenKshortestPaths(graph: DirectedGraph,
+ def yenKshortestPaths(g: GraphWithBalanceEstimates,
sourceNode: PublicKey,
targetNode: PublicKey,
amount: MilliSatoshi,
@@ -259,7 +267,7 @@ object Graph {
includeLocalChannelCost: Boolean): Seq[WeightedPath[PaymentPathWeight]] = {
// find the shortest path (k = 0)
val targetWeight = PaymentPathWeight(amount)
- dijkstraShortestPath(graph, sourceNode, targetNode, ignoredEdges, ignoredVertices, extraEdges, targetWeight, boundaries, Features.empty, currentBlockHeight, wr, includeLocalChannelCost) match {
+ dijkstraShortestPath(g, sourceNode, targetNode, ignoredEdges, ignoredVertices, extraEdges, targetWeight, boundaries, Features.empty, currentBlockHeight, wr, includeLocalChannelCost) match {
case None => Seq.empty // if we can't even find a single path, avoid returning a Seq(Seq.empty)
case Some(shortestPath) =>
@@ -270,7 +278,7 @@ object Graph {
var allSpurPathsFound = false
val shortestPaths = new mutable.Queue[PathWithSpur]
- shortestPaths.enqueue(PathWithSpur(WeightedPath(shortestPath, pathWeight(sourceNode, shortestPath, amount, currentBlockHeight, wr, includeLocalChannelCost)), 0))
+ shortestPaths.enqueue(PathWithSpur(WeightedPath(shortestPath, pathWeight(g.balances, sourceNode, shortestPath, amount, currentBlockHeight, wr, includeLocalChannelCost)), 0))
// stores the candidates for the k-th shortest path, sorted by path cost
val candidates = new mutable.PriorityQueue[PathWithSpur]
@@ -295,12 +303,12 @@ object Graph {
val alreadyExploredEdges = shortestPaths.collect { case p if p.p.path.takeRight(i) == rootPathEdges => p.p.path(p.p.path.length - 1 - i).desc }.toSet
// we also want to ignore any vertex on the root path to prevent loops
val alreadyExploredVertices = rootPathEdges.map(_.desc.b).toSet
- val rootPathWeight = pathWeight(sourceNode, rootPathEdges, amount, currentBlockHeight, wr, includeLocalChannelCost)
+ val rootPathWeight = pathWeight(g.balances, sourceNode, rootPathEdges, amount, currentBlockHeight, wr, includeLocalChannelCost)
// find the "spur" path, a sub-path going from the spur node to the target avoiding previously found sub-paths
- dijkstraShortestPath(graph, sourceNode, spurNode, ignoredEdges ++ alreadyExploredEdges, ignoredVertices ++ alreadyExploredVertices, extraEdges, rootPathWeight, boundaries, Features.empty, currentBlockHeight, wr, includeLocalChannelCost) match {
+ dijkstraShortestPath(g, sourceNode, spurNode, ignoredEdges ++ alreadyExploredEdges, ignoredVertices ++ alreadyExploredVertices, extraEdges, rootPathWeight, boundaries, Features.empty, currentBlockHeight, wr, includeLocalChannelCost) match {
case Some(spurPath) =>
val completePath = spurPath ++ rootPathEdges
- val candidatePath = WeightedPath(completePath, pathWeight(sourceNode, completePath, amount, currentBlockHeight, wr, includeLocalChannelCost))
+ val candidatePath = WeightedPath(completePath, pathWeight(g.balances, sourceNode, completePath, amount, currentBlockHeight, wr, includeLocalChannelCost))
candidates.enqueue(PathWithSpur(candidatePath, i))
case None => ()
}
@@ -338,7 +346,7 @@ object Graph {
* @param wr ratios used to 'weight' edges when searching for the shortest path
* @param includeLocalChannelCost if the path is for relaying and we need to include the cost of the local channel
*/
- private def dijkstraShortestPath[RichWeight <: PathWeight](g: DirectedGraph,
+ private def dijkstraShortestPath[RichWeight <: PathWeight](g: GraphWithBalanceEstimates,
sourceNode: PublicKey,
targetNode: PublicKey,
ignoredEdges: Set[ChannelDesc],
@@ -351,8 +359,8 @@ object Graph {
wr: WeightRatios[RichWeight],
includeLocalChannelCost: Boolean): Option[Seq[GraphEdge]] = {
// the graph does not contain source/destination nodes
- val sourceNotInGraph = !g.containsVertex(sourceNode) && !extraEdges.exists(_.desc.a == sourceNode)
- val targetNotInGraph = !g.containsVertex(targetNode) && !extraEdges.exists(_.desc.b == targetNode)
+ val sourceNotInGraph = !g.graph.containsVertex(sourceNode) && !extraEdges.exists(_.desc.a == sourceNode)
+ val targetNotInGraph = !g.graph.containsVertex(targetNode) && !extraEdges.exists(_.desc.b == targetNode)
if (sourceNotInGraph || targetNotInGraph) {
return None
}
@@ -381,17 +389,17 @@ object Graph {
val neighborEdges = {
val extraNeighbors = extraEdges.filter(_.desc.b == current.key)
// the resulting set must have only one element per shortChannelId; we prioritize extra edges
- g.getIncomingEdgesOf(current.key).collect { case e: GraphEdge if !extraNeighbors.exists(_.desc.shortChannelId == e.desc.shortChannelId) => e } ++ extraNeighbors
+ g.graph.getIncomingEdgesOf(current.key).collect { case e: GraphEdge if !extraNeighbors.exists(_.desc.shortChannelId == e.desc.shortChannelId) => e } ++ extraNeighbors
}
neighborEdges.foreach { edge =>
val neighbor = edge.desc.a
if (current.weight.canUseEdge(edge) &&
!ignoredEdges.contains(edge.desc) &&
!ignoredVertices.contains(neighbor) &&
- (neighbor == sourceNode || g.getVertexFeatures(neighbor).areSupported(nodeFeatures))) {
+ (neighbor == sourceNode || g.graph.getVertexFeatures(neighbor).areSupported(nodeFeatures))) {
// NB: this contains the amount (including fees) that will need to be sent to `neighbor`, but the amount that
// will be relayed through that edge is the one in `currentWeight`.
- val neighborWeight = wr.addEdgeWeight(sourceNode, edge, current.weight, currentBlockHeight, includeLocalChannelCost)
+ val neighborWeight = wr.addEdgeWeight(sourceNode, edge, g.balances.get(edge), current.weight, currentBlockHeight, includeLocalChannelCost)
if (boundaries(neighborWeight)) {
val previousNeighborWeight = bestWeights.get(neighbor)
// if this path between neighbor and the target has a shorter distance than previously known, we select it
@@ -425,7 +433,7 @@ object Graph {
}
}
- def dijkstraMessagePath(g: DirectedGraph,
+ def dijkstraMessagePath(g: GraphWithBalanceEstimates,
sourceNode: PublicKey,
targetNode: PublicKey,
ignoredVertices: Set[PublicKey],
@@ -440,7 +448,7 @@ object Graph {
*
* @param pathsToFind Number of paths to find. We may return fewer paths if we couldn't find more non-overlapping ones.
*/
- def routeBlindingPaths(graph: DirectedGraph,
+ def routeBlindingPaths(g: GraphWithBalanceEstimates,
sourceNode: PublicKey,
targetNode: PublicKey,
amount: MilliSatoshi,
@@ -454,9 +462,9 @@ object Graph {
val verticesToIgnore = new mutable.HashSet[PublicKey]()
verticesToIgnore.addAll(ignoredVertices)
for (_ <- 1 to pathsToFind) {
- dijkstraShortestPath(graph, sourceNode, targetNode, ignoredEdges, verticesToIgnore.toSet, extraEdges = Set.empty, PaymentPathWeight(amount), boundaries, Features(Features.RouteBlinding -> FeatureSupport.Mandatory), currentBlockHeight, wr, includeLocalChannelCost = true) match {
+ dijkstraShortestPath(g, sourceNode, targetNode, ignoredEdges, verticesToIgnore.toSet, extraEdges = Set.empty, PaymentPathWeight(amount), boundaries, Features(Features.RouteBlinding -> FeatureSupport.Mandatory), currentBlockHeight, wr, includeLocalChannelCost = true) match {
case Some(path) =>
- val weight = pathWeight(sourceNode, path, amount, currentBlockHeight, wr, includeLocalChannelCost = true)
+ val weight = pathWeight(g.balances, sourceNode, path, amount, currentBlockHeight, wr, includeLocalChannelCost = true)
paths += WeightedPath(path, weight)
// Additional paths must keep using the source and target nodes, but shouldn't use any of the same intermediate nodes.
verticesToIgnore.addAll(path.drop(1).map(_.desc.a))
@@ -503,9 +511,9 @@ object Graph {
* @param wr ratios used to 'weight' edges when searching for the shortest path
* @param includeLocalChannelCost if the path is for relaying and we need to include the cost of the local channel
*/
- def pathWeight(sender: PublicKey, path: Seq[GraphEdge], amount: MilliSatoshi, currentBlockHeight: BlockHeight, wr: WeightRatios[PaymentPathWeight], includeLocalChannelCost: Boolean): PaymentPathWeight = {
+ def pathWeight(balances: BalancesEstimates, sender: PublicKey, path: Seq[GraphEdge], amount: MilliSatoshi, currentBlockHeight: BlockHeight, wr: WeightRatios[PaymentPathWeight], includeLocalChannelCost: Boolean): PaymentPathWeight = {
path.foldRight(PaymentPathWeight(amount)) { (edge, prev) =>
- wr.addEdgeWeight(sender, edge, prev, currentBlockHeight, includeLocalChannelCost)
+ wr.addEdgeWeight(sender, edge, balances.get(edge), prev, currentBlockHeight, includeLocalChannelCost)
}
}
diff --git a/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala b/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala
index c3df929..dd03794 100644
--- a/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala
+++ b/eclair-core/src/main/scala/fr/acinq/eclair/router/RouteCalculation.scala
@@ -198,9 +198,9 @@ object RouteCalculation {
val tags = TagSet.Empty.withTag(Tags.MultiPart, r.allowMultiPart).withTag(Tags.Amount, Tags.amountBucket(amountToSend))
KamonExt.time(Metrics.FindRouteDuration.withTags(tags.withTag(Tags.NumberOfRoutes, routesToFind.toLong))) {
val result = if (r.allowMultiPart) {
- findMultiPartRoute(d.graphWithBalances.graph, r.source, targetNodeId, amountToSend, maxFee, extraEdges, ignoredEdges, r.ignore.nodes, r.pendingPayments, r.routeParams, currentBlockHeight)
+ findMultiPartRoute(d.graphWithBalances, r.source, targetNodeId, amountToSend, maxFee, extraEdges, ignoredEdges, r.ignore.nodes, r.pendingPayments, r.routeParams, currentBlockHeight)
} else {
- findRoute(d.graphWithBalances.graph, r.source, targetNodeId, amountToSend, maxFee, routesToFind, extraEdges, ignoredEdges, r.ignore.nodes, r.routeParams, currentBlockHeight)
+ findRoute(d.graphWithBalances, r.source, targetNodeId, amountToSend, maxFee, routesToFind, extraEdges, ignoredEdges, r.ignore.nodes, r.routeParams, currentBlockHeight)
}
result.map(routes => addFinalHop(r.target, routes)) match {
case Success(routes) =>
@@ -236,7 +236,7 @@ object RouteCalculation {
weight.length <= ROUTE_MAX_LENGTH &&
weight.cltv <= r.routeParams.boundaries.maxCltv
}
- val routes = Graph.routeBlindingPaths(d.graphWithBalances.graph, r.source, r.target, r.amount, r.ignore.channels, r.ignore.nodes, r.pathsToFind, r.routeParams.heuristics, currentBlockHeight, boundaries)
+ val routes = Graph.routeBlindingPaths(d.graphWithBalances, r.source, r.target, r.amount, r.ignore.channels, r.ignore.nodes, r.pathsToFind, r.routeParams.heuristics, currentBlockHeight, boundaries)
if (routes.isEmpty) {
r.replyTo ! PaymentRouteNotFound(RouteNotFound)
} else {
@@ -250,7 +250,7 @@ object RouteCalculation {
weight.length <= routeParams.maxRouteLength && weight.length <= ROUTE_MAX_LENGTH
}
log.info("finding route for onion messages {} -> {}", r.source, r.target)
- Graph.dijkstraMessagePath(d.graphWithBalances.graph, r.source, r.target, r.ignoredNodes, boundaries, currentBlockHeight, routeParams.ratios) match {
+ Graph.dijkstraMessagePath(d.graphWithBalances, r.source, r.target, r.ignoredNodes, boundaries, currentBlockHeight, routeParams.ratios) match {
case Some(path) =>
val intermediateNodes = path.map(_.desc.a).drop(1)
log.info("found route for onion messages {}", (r.source +: intermediateNodes :+ r.target).mkString(" -> "))
@@ -300,7 +300,7 @@ object RouteCalculation {
* @param routeParams a set of parameters that can restrict the route search
* @return the computed routes to the destination @param targetNodeId
*/
- def findRoute(g: DirectedGraph,
+ def findRoute(g: GraphWithBalanceEstimates,
localNodeId: PublicKey,
targetNodeId: PublicKey,
amount: MilliSatoshi,
@@ -318,7 +318,7 @@ object RouteCalculation {
}
@tailrec
- private def findRouteInternal(g: DirectedGraph,
+ private def findRouteInternal(g: GraphWithBalanceEstimates,
localNodeId: PublicKey,
targetNodeId: PublicKey,
amount: MilliSatoshi,
@@ -379,7 +379,7 @@ object RouteCalculation {
* @param routeParams a set of parameters that can restrict the route search
* @return a set of disjoint routes to the destination @param targetNodeId with the payment amount split between them
*/
- def findMultiPartRoute(g: DirectedGraph,
+ def findMultiPartRoute(g: GraphWithBalanceEstimates,
localNodeId: PublicKey,
targetNodeId: PublicKey,
amount: MilliSatoshi,
@@ -403,7 +403,7 @@ object RouteCalculation {
}
}
- private def findMultiPartRouteInternal(g: DirectedGraph,
+ private def findMultiPartRouteInternal(g: GraphWithBalanceEstimates,
localNodeId: PublicKey,
targetNodeId: PublicKey,
amount: MilliSatoshi,
@@ -418,7 +418,7 @@ object RouteCalculation {
// When the recipient is a direct peer, we have complete visibility on our local channels so we can use more accurate MPP parameters.
val routeParams1 = {
case class DirectChannel(balance: MilliSatoshi, isEmpty: Boolean)
- val directChannels = g.getEdgesBetween(localNodeId, targetNodeId).collect {
+ val directChannels = g.graph.getEdgesBetween(localNodeId, targetNodeId).collect {
// We should always have balance information available for local channels.
// NB: htlcMinimumMsat is set by our peer and may be 0 msat (even though it's not recommended).
case GraphEdge(_, params, _, Some(balance)) => DirectChannel(balance, balance <= 0.msat || balance < params.htlcMinimum)
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/router/BalanceEstimateSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/router/BalanceEstimateSpec.scala
index 15cc094..2ded699 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/router/BalanceEstimateSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/router/BalanceEstimateSpec.scala
@@ -338,20 +338,21 @@ class BalanceEstimateSpec extends AnyFunSuite {
))
val graphWithBalances = GraphWithBalanceEstimates(g, 1 day)
+ val now = TimestampSecond.now()
// NB: it doesn't matter which edge is selected, the balance estimation takes all existing edges into account.
val edge_ab = makeEdge(a, b, 1, 10 sat)
val edge_ba = makeEdge(b, a, 1, 10 sat)
val edge_bc = makeEdge(b, c, 6, 10 sat)
- assert(graphWithBalances.canSend(27500 msat, edge_ab) === 0.75 +- 0.01)
- assert(graphWithBalances.canSend(55000 msat, edge_ab) === 0.5 +- 0.01)
- assert(graphWithBalances.canSend(30000 msat, edge_ba) === 0.75 +- 0.01)
- assert(graphWithBalances.canSend(60000 msat, edge_ba) === 0.5 +- 0.01)
- assert(graphWithBalances.canSend(75000 msat, edge_bc) === 0.5 +- 0.01)
- assert(graphWithBalances.canSend(100000 msat, edge_bc) === 0.33 +- 0.01)
+ assert(graphWithBalances.balances.get(edge_ab).canSend(27500 msat, now) === 0.75 +- 0.01)
+ assert(graphWithBalances.balances.get(edge_ab).canSend(55000 msat, now) === 0.5 +- 0.01)
+ assert(graphWithBalances.balances.get(edge_ba).canSend(30000 msat, now) === 0.75 +- 0.01)
+ assert(graphWithBalances.balances.get(edge_ba).canSend(60000 msat, now) === 0.5 +- 0.01)
+ assert(graphWithBalances.balances.get(edge_bc).canSend(75000 msat, now) === 0.5 +- 0.01)
+ assert(graphWithBalances.balances.get(edge_bc).canSend(100000 msat, now) === 0.33 +- 0.01)
val unknownEdge = makeEdge(42, 40 sat)
- assert(graphWithBalances.canSend(10000 msat, unknownEdge) === 0.75 +- 0.01)
- assert(graphWithBalances.canSend(20000 msat, unknownEdge) === 0.5 +- 0.01)
- assert(graphWithBalances.canSend(30000 msat, unknownEdge) === 0.25 +- 0.01)
+ assert(graphWithBalances.balances.get(unknownEdge).canSend(10000 msat, now) === 0.75 +- 0.01)
+ assert(graphWithBalances.balances.get(unknownEdge).canSend(20000 msat, now) === 0.5 +- 0.01)
+ assert(graphWithBalances.balances.get(unknownEdge).canSend(30000 msat, now) === 0.25 +- 0.01)
}
}
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/router/GraphSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/router/GraphSpec.scala
index c84799c..2d346a5 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/router/GraphSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/router/GraphSpec.scala
@@ -29,6 +29,8 @@ import fr.acinq.eclair.{BlockHeight, FeatureSupport, Features, MilliSatoshiLong,
import org.scalactic.Tolerance.convertNumericToPlusOrMinusWrapper
import org.scalatest.funsuite.AnyFunSuite
+import scala.concurrent.duration.DurationInt
+
class GraphSpec extends AnyFunSuite {
val (priv_a, priv_b, priv_c, priv_d, priv_e, priv_f, priv_g, priv_h) = (randomKey(), randomKey(), randomKey(), randomKey(), randomKey(), randomKey(), randomKey(), randomKey())
@@ -260,9 +262,9 @@ class GraphSpec extends AnyFunSuite {
val edgeDE = makeEdge(6L, d, e, 9 msat, 0, capacity = 200000 sat)
val graph = DirectedGraph(Seq(edgeAB, edgeBC, edgeCD, edgeDC, edgeCE, edgeDE))
- val path :: Nil = yenKshortestPaths(graph, a, e, 100000000 msat,
+ val path :: Nil = yenKshortestPaths(GraphWithBalanceEstimates(graph, 1 day), a, e, 100000000 msat,
Set.empty, Set.empty, Set.empty, 1,
- HeuristicsConstants(1.0E-8, RelayFees(2000 msat, 500), RelayFees(50 msat, 20), useLogProbability = true),
+ HeuristicsConstants(1.0E-8, RelayFees(2000 msat, 500), RelayFees(50 msat, 20), useLogProbability = true, usePastRelaysData = false),
BlockHeight(714930), _ => true, includeLocalChannelCost = true)
assert(path.path == Seq(edgeAB, edgeBC, edgeCE))
}
@@ -284,7 +286,7 @@ class GraphSpec extends AnyFunSuite {
val edgeDE = makeEdge(6L, d, e, 1 msat, 0, capacity = 200000 sat)
val graph = DirectedGraph(Seq(edgeAB, edgeBC, edgeCD, edgeDC, edgeCE, edgeDE))
- val paths = yenKshortestPaths(graph, a, e, 90000000 msat,
+ val paths = yenKshortestPaths(GraphWithBalanceEstimates(graph, 1 day), a, e, 90000000 msat,
Set.empty, Set.empty, Set.empty, 2,
PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)),
BlockHeight(714930), _ => true, includeLocalChannelCost = true)
@@ -310,7 +312,7 @@ class GraphSpec extends AnyFunSuite {
val edgeDE = makeEdge(6L, d, e, 1 msat, 0, capacity = 200000 sat)
val graph = DirectedGraph(Seq(edgeAB, edgeBC, edgeCD, edgeDC, edgeCE, edgeDE))
- val paths = yenKshortestPaths(graph, a, e, 90000000 msat,
+ val paths = yenKshortestPaths(GraphWithBalanceEstimates(graph, 1 day), a, e, 90000000 msat,
Set.empty, Set.empty, Set.empty, 2,
PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)),
BlockHeight(714930), _ => true, includeLocalChannelCost = true)
@@ -343,7 +345,7 @@ class GraphSpec extends AnyFunSuite {
val edgeGH = makeEdge(9L, g, h, 2 msat, 0, capacity = 100000 sat, minHtlc = 1000 msat)
val graph = DirectedGraph(Seq(edgeCD, edgeDF, edgeCE, edgeED, edgeEF, edgeFG, edgeFH, edgeEG, edgeGH))
- val paths = yenKshortestPaths(graph, c, h, 10000000 msat,
+ val paths = yenKshortestPaths(GraphWithBalanceEstimates(graph, 1 day), c, h, 10000000 msat,
Set.empty, Set.empty, Set.empty, 3,
PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)),
BlockHeight(714930), _ => true, includeLocalChannelCost = true)
@@ -384,7 +386,7 @@ class GraphSpec extends AnyFunSuite {
val edgeCB = makeEdge(3L, c, b, 2 msat, 4, capacity = 100000 sat, minHtlc = 1000 msat)
val graph = DirectedGraph(Seq(edgeAB, edgeAC, edgeCB))
- val paths = yenKshortestPaths(graph, a, b, 10000000 msat,
+ val paths = yenKshortestPaths(GraphWithBalanceEstimates(graph, 1 day), a, b, 10000000 msat,
Set.empty, Set.empty, Set.empty, 1,
PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)),
BlockHeight(714930), _ => true, includeLocalChannelCost = true)
@@ -417,7 +419,7 @@ class GraphSpec extends AnyFunSuite {
// All nodes can relay messages, same weight for each channel.
val boundaries = (w: MessagePathWeight) => w.length <= 8
val wr = MessageWeightRatios(1.0, 0.0, 0.0)
- val Some(path) = dijkstraMessagePath(graph, a, d, Set.empty, boundaries, BlockHeight(793397), wr)
+ val Some(path) = dijkstraMessagePath(GraphWithBalanceEstimates(graph, 1 day), a, d, Set.empty, boundaries, BlockHeight(793397), wr)
assert(path.map(_.desc.shortChannelId.toLong) == Seq(4, 5))
}
{
@@ -426,7 +428,7 @@ class GraphSpec extends AnyFunSuite {
val wr = MessageWeightRatios(1.0, 0.0, 0.0)
val g = graph.addOrUpdateVertex(makeNodeAnnouncement(priv_a, "A", Color(0, 0, 0), Nil, Features.empty))
.addOrUpdateVertex(makeNodeAnnouncement(priv_d, "D", Color(0, 0, 0), Nil, Features.empty))
- val Some(path) = dijkstraMessagePath(g, a, d, Set.empty, boundaries, BlockHeight(793397), wr)
+ val Some(path) = dijkstraMessagePath(GraphWithBalanceEstimates(g, 1 day), a, d, Set.empty, boundaries, BlockHeight(793397), wr)
assert(path.map(_.desc.shortChannelId.toLong) == Seq(4, 5))
}
{
@@ -434,28 +436,28 @@ class GraphSpec extends AnyFunSuite {
val boundaries = (w: MessagePathWeight) => w.length <= 8
val wr = MessageWeightRatios(1.0, 0.0, 0.0)
val g = graph.addOrUpdateVertex(makeNodeAnnouncement(priv_e, "E", Color(0, 0, 0), Nil, Features.empty))
- val Some(path) = dijkstraMessagePath(g, a, d, Set.empty, boundaries, BlockHeight(793397), wr)
+ val Some(path) = dijkstraMessagePath(GraphWithBalanceEstimates(g, 1 day), a, d, Set.empty, boundaries, BlockHeight(793397), wr)
assert(path.map(_.desc.shortChannelId.toLong) == Seq(1, 2, 3))
}
{
// Prefer high-capacity channels.
val boundaries = (w: MessagePathWeight) => w.length <= 8
val wr = MessageWeightRatios(0.0, 0.0, 1.0)
- val Some(path) = dijkstraMessagePath(graph, a, d, Set.empty, boundaries, BlockHeight(793397), wr)
+ val Some(path) = dijkstraMessagePath(GraphWithBalanceEstimates(graph, 1 day), a, d, Set.empty, boundaries, BlockHeight(793397), wr)
assert(path.map(_.desc.shortChannelId.toLong) == Seq(1, 2, 3))
}
{
// We ignore E.
val boundaries = (w: MessagePathWeight) => w.length <= 8
val wr = MessageWeightRatios(1.0, 0.0, 0.0)
- val Some(path) = dijkstraMessagePath(graph, a, d, Set(e), boundaries, BlockHeight(793397), wr)
+ val Some(path) = dijkstraMessagePath(GraphWithBalanceEstimates(graph, 1 day), a, d, Set(e), boundaries, BlockHeight(793397), wr)
assert(path.map(_.desc.shortChannelId.toLong) == Seq(1, 2, 3))
}
{
// Target not in graph.
val boundaries = (w: MessagePathWeight) => w.length <= 8
val wr = MessageWeightRatios(1.0, 0.0, 0.0)
- assert(dijkstraMessagePath(graph, a, f, Set.empty, boundaries, BlockHeight(793397), wr).isEmpty)
+ assert(dijkstraMessagePath(GraphWithBalanceEstimates(graph, 1 day), a, f, Set.empty, boundaries, BlockHeight(793397), wr).isEmpty)
}
}
@@ -522,13 +524,13 @@ class GraphSpec extends AnyFunSuite {
.addOrUpdateVertex(makeNodeAnnouncement(priv_h, "H", Color(0, 0, 0), Nil, Features(Features.RouteBlinding -> FeatureSupport.Optional)))
{
- val paths = routeBlindingPaths(graph, a, h, 20_000_000 msat, Set.empty, Set.empty, pathsToFind = 3, PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)), BlockHeight(793397), _ => true)
+ val paths = routeBlindingPaths(GraphWithBalanceEstimates(graph, 1 day), a, h, 20_000_000 msat, Set.empty, Set.empty, pathsToFind = 3, PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)), BlockHeight(793397), _ => true)
assert(paths.length == 2)
assert(paths(0).path.map(_.desc.a) == Seq(a, b))
assert(paths(1).path.map(_.desc.a) == Seq(a, e, f))
}
{
- val paths = routeBlindingPaths(graph, c, h, 20_000_000 msat, Set.empty, Set.empty, pathsToFind = 3, PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)), BlockHeight(793397), _ => true)
+ val paths = routeBlindingPaths(GraphWithBalanceEstimates(graph, 1 day), c, h, 20_000_000 msat, Set.empty, Set.empty, pathsToFind = 3, PaymentWeightRatios(1, 0, 0, 0, RelayFees(0 msat, 0)), BlockHeight(793397), _ => true)
assert(paths.length == 1)
assert(paths(0).path.map(_.desc.a) == Seq(c, a, b))
}
diff --git a/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala b/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala
index d7ad81b..c16e62f 100644
--- a/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala
+++ b/eclair-core/src/test/scala/fr/acinq/eclair/router/RouteCalculationSpec.scala
@@ -37,6 +37,7 @@ import scodec.bits._
import scala.collection.immutable.SortedMap
import scala.collection.mutable
+import scala.concurrent.duration.DurationInt
import scala.util.{Failure, Random, Success}
/**
@@ -47,15 +48,17 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
import RouteCalculationSpec._
+ implicit val log: akka.event.LoggingAdapter = akka.event.NoLogging
+
val (a, b, c, d, e, f) = (randomKey().publicKey, randomKey().publicKey, randomKey().publicKey, randomKey().publicKey, randomKey().publicKey, randomKey().publicKey)
test("calculate simple route") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 10, cltvDelta = CltvExpiryDelta(1), balance_opt = Some(DEFAULT_AMOUNT_MSAT * 2)),
makeEdge(2L, b, c, 1 msat, 10, cltvDelta = CltvExpiryDelta(1)),
makeEdge(3L, c, d, 1 msat, 10, cltvDelta = CltvExpiryDelta(1)),
makeEdge(4L, d, e, 1 msat, 10, cltvDelta = CltvExpiryDelta(1))
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 2 :: 3 :: 4 :: Nil)
@@ -71,12 +74,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val routeParams = DEFAULT_ROUTE_PARAMS.modify(_.boundaries.maxFeeFlat).setTo(1 msat)
val maxFee = routeParams.getMaxFee(DEFAULT_AMOUNT_MSAT)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 10 msat, 10, cltvDelta = CltvExpiryDelta(1)),
makeEdge(2L, b, c, 10 msat, 10, cltvDelta = CltvExpiryDelta(1)),
makeEdge(3L, c, d, 10 msat, 10, cltvDelta = CltvExpiryDelta(1)),
makeEdge(4L, d, e, 10 msat, 10, cltvDelta = CltvExpiryDelta(1))
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, maxFee, numRoutes = 1, routeParams = routeParams, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 2 :: 3 :: 4 :: Nil)
@@ -112,17 +115,17 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val amount = 10000 msat
val expectedCost = 10007 msat
- val graph = DirectedGraph(List(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, feeBase = 1 msat, feeProportionalMillionth = 200, minHtlc = 0 msat),
makeEdge(4L, a, e, feeBase = 1 msat, feeProportionalMillionth = 200, minHtlc = 0 msat),
makeEdge(2L, b, c, feeBase = 1 msat, feeProportionalMillionth = 300, minHtlc = 0 msat),
makeEdge(3L, c, d, feeBase = 1 msat, feeProportionalMillionth = 400, minHtlc = 0 msat),
makeEdge(5L, e, f, feeBase = 1 msat, feeProportionalMillionth = 400, minHtlc = 0 msat),
makeEdge(6L, f, d, feeBase = 1 msat, feeProportionalMillionth = 100, minHtlc = 0 msat)
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(graph, a, d, amount, maxFee = 7 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
- val weightedPath = Graph.pathWeight(a, route2Edges(route), amount, BlockHeight(0), NO_WEIGHT_RATIOS, includeLocalChannelCost = false)
+ val weightedPath = Graph.pathWeight(graph.balances, a, route2Edges(route), amount, BlockHeight(0), NO_WEIGHT_RATIOS, includeLocalChannelCost = false)
assert(route2Ids(route) == 4 :: 5 :: 6 :: Nil)
assert(weightedPath.length == 3)
assert(weightedPath.amount == expectedCost)
@@ -138,25 +141,25 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("calculate route considering the direct channel pays no fees") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 5 msat, 0), // a -> b
makeEdge(2L, a, d, 15 msat, 0), // a -> d this goes a bit closer to the target and asks for higher fees but is a direct channel
makeEdge(3L, b, c, 5 msat, 0), // b -> c
makeEdge(4L, c, d, 5 msat, 0), // c -> d
makeEdge(5L, d, e, 5 msat, 0) // d -> e
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 2 :: 5 :: Nil)
}
test("calculate simple route (add and remove edges") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0),
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(3L, c, d, 0 msat, 0),
makeEdge(4L, d, e, 0 msat, 0)
- ))
+ )), 1 day)
val Success(route1 :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route1) == 1 :: 2 :: 3 :: 4 :: Nil)
@@ -174,12 +177,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"029e059b6780f155f38e83601969919aae631ddf6faed58fe860c72225eb327d7c") // target
)
- val graph = DirectedGraph(List(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, f, g, 1 msat, 0),
makeEdge(2L, g, h, 1 msat, 0),
makeEdge(3L, h, i, 1 msat, 0),
makeEdge(4L, f, h, 50 msat, 0) // more expensive but fee will be ignored since f is the payer
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(graph, f, i, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 4 :: 3 :: Nil)
@@ -193,12 +196,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"029e059b6780f155f38e83601969919aae631ddf6faed58fe860c72225eb327d7c") // target
)
- val graph = DirectedGraph(List(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, f, g, 0 msat, 0),
makeEdge(4L, f, i, 50 msat, 0), // our starting node F has a direct channel with I
makeEdge(2L, g, h, 0 msat, 0),
makeEdge(3L, h, i, 0 msat, 0)
- ))
+ )), 1 day)
val Success(route1 :: route2 :: Nil) = findRoute(graph, f, i, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 2, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route1) == 4 :: Nil)
@@ -213,12 +216,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"029e059b6780f155f38e83601969919aae631ddf6faed58fe860c72225eb327d7c") // I target
)
- val graph = DirectedGraph(List(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, f, g, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT + 50.msat)),
// the maximum htlc allowed by this channel is only 50 msat greater than what we're sending
makeEdge(2L, g, h, 1 msat, 0, maxHtlc = Some(DEFAULT_AMOUNT_MSAT + 50.msat)),
makeEdge(3L, h, i, 1 msat, 0)
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(graph, f, i, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 2 :: 3 :: Nil)
@@ -232,12 +235,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"029e059b6780f155f38e83601969919aae631ddf6faed58fe860c72225eb327d7c") // I target
)
- val graph = DirectedGraph(List(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, f, g, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT + 50.msat)),
// this channel requires a minimum amount that is larger than what we are sending
makeEdge(2L, g, h, 1 msat, 0, minHtlc = DEFAULT_AMOUNT_MSAT + 50.msat),
makeEdge(3L, h, i, 1 msat, 0)
- ))
+ )), 1 day)
val route = findRoute(graph, f, i, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route == Failure(RouteNotFound))
@@ -251,12 +254,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"029e059b6780f155f38e83601969919aae631ddf6faed58fe860c72225eb327d7c") // I target
)
- val graph = DirectedGraph(List(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, f, g, 0 msat, 0),
makeEdge(2L, g, h, 5 msat, 5), // expensive g -> h channel
makeEdge(6L, g, h, 0 msat, 0), // cheap g -> h channel
makeEdge(3L, h, i, 0 msat, 0)
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(graph, f, i, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 6 :: 3 :: Nil)
@@ -270,46 +273,46 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"029e059b6780f155f38e83601969919aae631ddf6faed58fe860c72225eb327d7c") // I target
)
- val graph = DirectedGraph(List(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, f, g, 0 msat, 0),
makeEdge(2L, g, h, 5 msat, 5, balance_opt = Some(DEFAULT_AMOUNT_MSAT + 1.msat)), // expensive g -> h channel with enough balance
makeEdge(6L, g, h, 0 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT - 10.msat)), // cheap g -> h channel without enough balance
makeEdge(3L, h, i, 0 msat, 0)
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(graph, f, i, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 2 :: 3 :: Nil)
}
test("calculate longer but cheaper route") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0),
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(3L, c, d, 0 msat, 0),
makeEdge(4L, d, e, 0 msat, 0),
makeEdge(5L, b, e, 10 msat, 10)
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 2 :: 3 :: 4 :: Nil)
}
test("no local channels") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(4L, d, e, 0 msat, 0)
- ))
+ )), 1 day)
val route = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route == Failure(RouteNotFound))
}
test("route not found") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0),
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(4L, d, e, 0 msat, 0)
- ))
+ )), 1 day)
val route = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route == Failure(RouteNotFound))
@@ -323,10 +326,10 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val e = priv_e.publicKey
val annE = makeNodeAnnouncement(priv_e, "E", Color(0, 0, 0), Nil, Features.empty)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(4L, c, d, 0 msat, 0)
- )).addOrUpdateVertex(annA).addOrUpdateVertex(annE)
+ )).addOrUpdateVertex(annA).addOrUpdateVertex(annE), 1 day)
assert(findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)) == Failure(RouteNotFound))
assert(findRoute(g, b, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)) == Failure(RouteNotFound))
@@ -348,60 +351,60 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(3L, c, d, 0 msat, 0)
)
- val g = DirectedGraph(edgesHi)
- val g1 = DirectedGraph(edgesLo)
+ val g = GraphWithBalanceEstimates(DirectedGraph(edgesHi), 1 day)
+ val g1 = GraphWithBalanceEstimates(DirectedGraph(edgesLo), 1 day)
assert(findRoute(g, a, d, highAmount, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)) == Failure(RouteNotFound))
assert(findRoute(g1, a, d, lowAmount, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)) == Failure(RouteNotFound))
}
test("route not found (balance too low)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 2, minHtlc = 10000 msat),
makeEdge(2L, b, c, 1 msat, 2, minHtlc = 10000 msat),
makeEdge(3L, c, d, 1 msat, 2, minHtlc = 10000 msat)
- ))
+ )), 1 day)
assert(findRoute(g, a, d, 15000 msat, 100 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)).isSuccess)
// not enough balance on the last edge
- val g1 = DirectedGraph(List(
+ val g1 = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 2, minHtlc = 10000 msat),
makeEdge(2L, b, c, 1 msat, 2, minHtlc = 10000 msat),
makeEdge(3L, c, d, 1 msat, 2, minHtlc = 10000 msat, balance_opt = Some(10000 msat))
- ))
+ )), 1 day)
// not enough balance on intermediate edge (taking fee into account)
- val g2 = DirectedGraph(List(
+ val g2 = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 2, minHtlc = 10000 msat),
makeEdge(2L, b, c, 1 msat, 2, minHtlc = 10000 msat, balance_opt = Some(15000 msat)),
makeEdge(3L, c, d, 1 msat, 2, minHtlc = 10000 msat)
- ))
+ )), 1 day)
// no enough balance on first edge (taking fee into account)
- val g3 = DirectedGraph(List(
+ val g3 = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 2, minHtlc = 10000 msat, balance_opt = Some(15000 msat)),
makeEdge(2L, b, c, 1 msat, 2, minHtlc = 10000 msat),
makeEdge(3L, c, d, 1 msat, 2, minHtlc = 10000 msat)
- ))
+ )), 1 day)
Seq(g1, g2, g3).foreach(g => assert(findRoute(g, a, d, 15000 msat, 100 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)) == Failure(RouteNotFound)))
}
test("route to self") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0),
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(3L, c, d, 0 msat, 0)
- ))
+ )), 1 day)
val route = findRoute(g, a, a, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route == Failure(CannotRouteToSelf))
}
test("route to immediate neighbor") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT)),
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(3L, c, d, 0 msat, 0),
makeEdge(4L, d, e, 0 msat, 0)
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, b, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: Nil)
@@ -409,12 +412,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("directed graph") {
// a->e works, e->a fails
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0),
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(3L, c, d, 0 msat, 0),
makeEdge(4L, d, e, 0 msat, 0)
- ))
+ )), 1 day)
val Success(route1 :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route1) == 1 :: 2 :: 3 :: 4 :: Nil)
@@ -446,26 +449,26 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
GraphEdge(ChannelDesc(ShortChannelId(4L), e, d), HopRelayParams.FromAnnouncement(ued), DEFAULT_CAPACITY, None)
)
- val g = DirectedGraph(edges)
+ val g = GraphWithBalanceEstimates(DirectedGraph(edges), 1 day)
val Success(route :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route.hops == channelHopFromUpdate(a, b, uab) :: channelHopFromUpdate(b, c, ubc) :: channelHopFromUpdate(c, d, ucd) :: channelHopFromUpdate(d, e, ude) :: Nil)
}
test("blacklist routes") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0),
makeEdge(2L, b, c, 0 msat, 0),
makeEdge(3L, c, d, 0 msat, 0),
makeEdge(4L, d, e, 0 msat, 0)
- ))
+ )), 1 day)
val route1 = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, ignoredEdges = Set(ChannelDesc(ShortChannelId(3L), c, d)), routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route1 == Failure(RouteNotFound))
// verify that we left the graph untouched
- assert(g.containsEdge(ChannelDesc(ShortChannelId(3), c, d)))
- assert(g.containsVertex(c))
- assert(g.containsVertex(d))
+ assert(g.graph.containsEdge(ChannelDesc(ShortChannelId(3), c, d)))
+ assert(g.graph.containsVertex(c))
+ assert(g.graph.containsVertex(d))
// make sure we can find a route if without the blacklist
val Success(route2 :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -473,11 +476,11 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("route to a destination that is not in the graph (with assisted routes)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 10 msat, 10),
makeEdge(2L, b, c, 10 msat, 10),
makeEdge(3L, c, d, 10 msat, 10)
- ))
+ )), 1 day)
val route = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route == Failure(RouteNotFound))
@@ -489,10 +492,10 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("route from a source that is not in the graph (with assisted routes)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(2L, b, c, 10 msat, 10),
makeEdge(3L, c, d, 10 msat, 10)
- ))
+ )), 1 day)
val route = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route == Failure(RouteNotFound))
@@ -504,12 +507,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("verify that extra hops takes precedence over known channels") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 10 msat, 10),
makeEdge(2L, b, c, 10 msat, 10),
makeEdge(3L, c, d, 10 msat, 10),
makeEdge(4L, d, e, 10 msat, 10)
- ))
+ )), 1 day)
val Success(route1 :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route1) == 1 :: 2 :: 3 :: 4 :: Nil)
@@ -572,7 +575,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
.zipWithIndex // ((0, 1), 0) :: ((1, 2), 1) :: ...
.map { case ((na, nb), index) => makeEdge(index, na, nb, 5 msat, 0) }
- val g = DirectedGraph(edges)
+ val g = GraphWithBalanceEstimates(DirectedGraph(edges), 1 day)
assert(findRoute(g, nodes(0), nodes(18), DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)).map(r => route2Ids(r.head)) == Success(0 until 18))
assert(findRoute(g, nodes(0), nodes(19), DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000)).map(r => route2Ids(r.head)) == Success(0 until 19))
@@ -590,7 +593,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val expensiveShortEdge = makeEdge(99, nodes(2), nodes(48), 1000 msat, 0) // expensive shorter route
- val g = DirectedGraph(expensiveShortEdge :: edges)
+ val g = GraphWithBalanceEstimates(DirectedGraph(expensiveShortEdge :: edges), 1 day)
val Success(route :: Nil) = findRoute(g, nodes(0), nodes(49), DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 0 :: 1 :: 99 :: 48 :: Nil)
@@ -598,14 +601,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("ignore cheaper route when it has more than the requested CLTV") {
val f = randomKey().publicKey
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1, a, b, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(50)),
makeEdge(2, b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(50)),
makeEdge(3, c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(50)),
makeEdge(4, a, e, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9)),
makeEdge(5, e, f, feeBase = 5 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9)),
makeEdge(6, f, d, feeBase = 5 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9))
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.modify(_.boundaries.maxCltv).setTo(CltvExpiryDelta(28)), currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 4 :: 5 :: 6 :: Nil)
@@ -613,27 +616,27 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("ignore cheaper route when it grows longer than the requested size") {
val f = randomKey().publicKey
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1, a, b, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9)),
makeEdge(2, b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9)),
makeEdge(3, c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9)),
makeEdge(4, d, e, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9)),
makeEdge(5, e, f, feeBase = 5 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9)),
makeEdge(6, b, f, feeBase = 5 msat, 0, minHtlc = 0 msat, maxHtlc = None, CltvExpiryDelta(9))
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, f, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.modify(_.boundaries.maxRouteLength).setTo(3), currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 6 :: Nil)
}
test("ignore loops") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 10 msat, 10),
makeEdge(2L, b, c, 10 msat, 10),
makeEdge(3L, c, a, 10 msat, 10),
makeEdge(4L, c, d, 10 msat, 10),
makeEdge(5L, d, e, 10 msat, 10)
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 2 :: 4 :: 5 :: Nil)
@@ -641,7 +644,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("ensure the route calculation terminates correctly when selecting 0-fees edges") {
// the graph contains a possible 0-cost path that goes back on its steps ( e -> f, f -> e )
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 10 msat, 10), // a -> b
makeEdge(2L, b, c, 10 msat, 10),
makeEdge(4L, c, d, 10 msat, 10),
@@ -649,7 +652,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(6L, e, f, 0 msat, 0), // e -> f
makeEdge(6L, f, e, 0 msat, 0), // e <- f
makeEdge(5L, e, d, 0 msat, 0) // e -> d
- ))
+ )), 1 day)
val Success(route :: Nil) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Ids(route) == 1 :: 3 :: 5 :: Nil)
@@ -674,7 +677,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"03fc5b91ce2d857f146fd9b986363374ffe04dc143d8bcd6d7664c8873c463cdfc")
)
- val g1 = DirectedGraph(Seq(
+ val g1 = GraphWithBalanceEstimates(DirectedGraph(Seq(
makeEdge(1L, d, a, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT + 4.msat)),
makeEdge(2L, d, e, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT + 3.msat)),
makeEdge(3L, a, e, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT + 3.msat)),
@@ -682,7 +685,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, e, f, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT)),
makeEdge(6L, b, c, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT + 1.msat)),
makeEdge(7L, c, f, 1 msat, 0, balance_opt = Some(DEFAULT_AMOUNT_MSAT))
- ))
+ )), 1 day)
val fourShortestPaths = Graph.yenKshortestPaths(g1, d, f, DEFAULT_AMOUNT_MSAT, Set.empty, Set.empty, Set.empty, pathsToFind = 4, NO_WEIGHT_RATIOS, BlockHeight(0), noopBoundaries, includeLocalChannelCost = false)
assert(fourShortestPaths.size == 4)
@@ -710,7 +713,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
PublicKey(hex"03fc5b91ce2d857f146fd9b986363374ffe04dc143d8bcd6d7664c8873c463cdfc")
)
- val graph = DirectedGraph(Seq(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(Seq(
makeEdge(10L, c, e, 2 msat, 0),
makeEdge(20L, c, d, 3 msat, 0),
makeEdge(30L, d, f, 4 msat, 5), // D- > F has a higher cost to distinguish it from the 2nd cheapest route
@@ -720,7 +723,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(70L, f, g, 2 msat, 0),
makeEdge(80L, f, h, 1 msat, 0),
makeEdge(90L, g, h, 2 msat, 0)
- ))
+ )), 1 day)
val twoShortestPaths = Graph.yenKshortestPaths(graph, c, h, DEFAULT_AMOUNT_MSAT, Set.empty, Set.empty, Set.empty, pathsToFind = 2, NO_WEIGHT_RATIOS, BlockHeight(0), noopBoundaries, includeLocalChannelCost = false)
@@ -736,7 +739,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val f = randomKey().publicKey
// simple graph with only 2 possible paths from A to F
- val graph = DirectedGraph(Seq(
+ val graph = GraphWithBalanceEstimates(DirectedGraph(Seq(
makeEdge(1L, a, b, 1 msat, 0),
makeEdge(1L, b, a, 1 msat, 0),
makeEdge(2L, b, c, 1 msat, 0),
@@ -750,7 +753,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, e, d, 1 msat, 0),
makeEdge(6L, e, f, 1 msat, 0),
makeEdge(6L, f, e, 1 msat, 0)
- ))
+ )), 1 day)
// we ask for 3 shortest paths but only 2 can be found
val foundPaths = Graph.yenKshortestPaths(graph, a, f, DEFAULT_AMOUNT_MSAT, Set.empty, Set.empty, Set.empty, pathsToFind = 3, NO_WEIGHT_RATIOS, BlockHeight(0), noopBoundaries, includeLocalChannelCost = false)
@@ -770,7 +773,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// A -> B -> C -> D has total cost of 10000005
// A -> E -> C -> D has total cost of 10000103 !!
// A -> E -> F -> D has total cost of 10000006
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, feeBase = 1 msat, 0),
makeEdge(2L, b, c, feeBase = 2 msat, 0),
makeEdge(3L, c, d, feeBase = 3 msat, 0),
@@ -778,12 +781,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, e, f, feeBase = 3 msat, 0),
makeEdge(6L, f, d, feeBase = 3 msat, 0),
makeEdge(7L, e, c, feeBase = 100 msat, 0)
- ))
+ )), 1 day)
for (_ <- 0 to 10) {
val Success(routes) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, strictFee, numRoutes = 3, routeParams = strictFeeParams, currentBlockHeight = BlockHeight(400000))
assert(routes.length == 2, routes)
- val weightedPath = Graph.pathWeight(a, route2Edges(routes.head), DEFAULT_AMOUNT_MSAT, BlockHeight(400000), NO_WEIGHT_RATIOS, includeLocalChannelCost = false)
+ val weightedPath = Graph.pathWeight(g.balances, a, route2Edges(routes.head), DEFAULT_AMOUNT_MSAT, BlockHeight(400000), NO_WEIGHT_RATIOS, includeLocalChannelCost = false)
val totalFees = weightedPath.amount - DEFAULT_AMOUNT_MSAT
// over the three routes we could only get the 2 cheapest because the third is too expensive (over 7 msat of fees)
assert(totalFees == 5.msat || totalFees == 6.msat)
@@ -798,7 +801,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// A -> B -> C -> D is 'fee optimized', lower fees route (totFees = 2, totCltv = 4000)
// A -> E -> F -> D is 'timeout optimized', lower CLTV route (totFees = 3, totCltv = 18)
// A -> E -> C -> D is 'capacity optimized', more recent channel/larger capacity route
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, feeBase = 0 msat, 1000, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(13)),
makeEdge(4L, a, e, feeBase = 0 msat, 1000, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(12)),
makeEdge(2L, b, c, feeBase = 1 msat, 1000, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(500)),
@@ -806,7 +809,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, e, f, feeBase = 2 msat, 1000, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(9)),
makeEdge(6L, f, d, feeBase = 2 msat, 1000, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(9)),
makeEdge(7L, e, c, feeBase = 2 msat, 1000, minHtlc = 0 msat, capacity = largeCapacity, cltvDelta = CltvExpiryDelta(12))
- ))
+ )), 1 day)
val Success(routeFeeOptimized :: Nil) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(route2Nodes(routeFeeOptimized) == (a, b) :: (b, c) :: (c, d) :: Nil)
@@ -833,14 +836,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("prefer going through an older channel if fees and CLTV are the same") {
val currentBlockHeight = BlockHeight(554000)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(ShortChannelId.fromCoordinates(s"${currentBlockHeight.toLong}x0x1").success.value.toLong, a, b, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)),
makeEdge(ShortChannelId.fromCoordinates(s"${currentBlockHeight.toLong}x0x4").success.value.toLong, a, e, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)),
makeEdge(ShortChannelId.fromCoordinates(s"${currentBlockHeight.toLong - 3000}x0x2").success.value.toLong, b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)), // younger channel
makeEdge(ShortChannelId.fromCoordinates(s"${currentBlockHeight.toLong - 3000}x0x3").success.value.toLong, c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)),
makeEdge(ShortChannelId.fromCoordinates(s"${currentBlockHeight.toLong}x0x5").success.value.toLong, e, f, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)),
makeEdge(ShortChannelId.fromCoordinates(s"${currentBlockHeight.toLong}x0x6").success.value.toLong, f, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144))
- ))
+ )), 1 day)
val Success(routeScoreOptimized :: Nil) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT / 2, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = PaymentWeightRatios(
baseFactor = 0.01,
@@ -854,14 +857,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("prefer a route with a smaller total CLTV if fees and score are the same") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1, a, b, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(12)),
makeEdge(4, a, e, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(12)),
makeEdge(2, b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(10)), // smaller CLTV
makeEdge(3, c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(12)),
makeEdge(5, e, f, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(12)),
makeEdge(6, f, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(12))
- ))
+ )), 1 day)
val Success(routeScoreOptimized :: Nil) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = PaymentWeightRatios(
baseFactor = 0.01,
@@ -877,14 +880,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("avoid a route that breaks off the max CLTV") {
// A -> B -> C -> D is cheaper but has a total CLTV > 2016!
// A -> E -> F -> D is more expensive but has a total CLTV < 2016
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1, a, b, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)),
makeEdge(4, a, e, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)),
makeEdge(2, b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(1000)),
makeEdge(3, c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(900)),
makeEdge(5, e, f, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144)),
makeEdge(6, f, d, feeBase = 1 msat, 0, minHtlc = 0 msat, maxHtlc = None, cltvDelta = CltvExpiryDelta(144))
- ))
+ )), 1 day)
val Success(routeScoreOptimized :: Nil) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT / 2, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = PaymentWeightRatios(
baseFactor = 0.01,
@@ -927,7 +930,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
)
)
- val g = DirectedGraph.makeGraph(updates, Seq.empty)
+ val g = GraphWithBalanceEstimates(DirectedGraph.makeGraph(updates, Seq.empty), 1 day)
val params = DEFAULT_ROUTE_PARAMS
.modify(_.boundaries.maxCltv).setTo(CltvExpiryDelta(1008))
.modify(_.heuristics).setTo(PaymentWeightRatios(baseFactor = 0, cltvDeltaFactor = 0.15, ageFactor = 0.35, capacityFactor = 0.5, hopFees = RelayFees(0 msat, 0)))
@@ -962,12 +965,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("calculate multipart route to neighbor (many channels, known balance)") {
val amount = 60000 msat
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(15000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 1 msat, balance_opt = Some(21000 msat)),
makeEdge(3L, a, b, 1 msat, 50, minHtlc = 1 msat, balance_opt = Some(17000 msat)),
makeEdge(4L, a, b, 100 msat, 20, minHtlc = 1 msat, balance_opt = Some(16000 msat)),
- ))
+ )), 1 day)
// We set max-parts to 3, but it should be ignored when sending to a direct neighbor.
val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(2500 msat, 3))
@@ -991,12 +994,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("calculate multipart route to neighbor (single channel, known balance)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(25000 msat)),
makeEdge(2L, a, c, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(50000 msat)),
makeEdge(3L, c, b, 1 msat, 0, minHtlc = 1 msat),
makeEdge(4L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
- ))
+ )), 1 day)
val amount = 25000 msat
val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1006,13 +1009,13 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("calculate multipart route to neighbor (many channels, some balance unknown)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(15000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 1 msat, balance_opt = Some(25000 msat)),
makeEdge(3L, a, b, 1 msat, 50, minHtlc = 1 msat, balance_opt = None, capacity = 20 sat),
makeEdge(4L, a, b, 100 msat, 20, minHtlc = 1 msat, balance_opt = Some(10000 msat)),
makeEdge(5L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
- ))
+ )), 1 day)
val amount = 65000 msat
val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1023,7 +1026,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("calculate multipart route to neighbor (many channels, some empty)") {
val amount = 35000 msat
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(15000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 1 msat, balance_opt = Some(0 msat)),
makeEdge(3L, a, b, 1 msat, 50, minHtlc = 1 msat, balance_opt = None, capacity = 15 sat),
@@ -1031,7 +1034,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, a, b, 100 msat, 20, minHtlc = 1 msat, balance_opt = Some(10000 msat)),
makeEdge(6L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
makeEdge(7L, a, d, 0 msat, 0, minHtlc = 0 msat, balance_opt = Some(0 msat)),
- ))
+ )), 1 day)
{
val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1050,14 +1053,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("calculate multipart route to neighbor (ignored channels)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(15000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 1 msat, balance_opt = Some(25000 msat)),
makeEdge(3L, a, b, 1 msat, 50, minHtlc = 1 msat, balance_opt = None, capacity = 50 sat),
makeEdge(4L, a, b, 100 msat, 20, minHtlc = 1 msat, balance_opt = Some(10000 msat)),
makeEdge(5L, a, b, 1 msat, 10, minHtlc = 1 msat, balance_opt = None, capacity = 10 sat),
makeEdge(6L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
- ))
+ )), 1 day)
val amount = 20000 msat
val ignoredEdges = Set(ChannelDesc(ShortChannelId(2L), a, b), ChannelDesc(ShortChannelId(3L), a, b))
@@ -1071,12 +1074,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val edge_ab_1 = makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(15000 msat))
val edge_ab_2 = makeEdge(2L, a, b, 15 msat, 10, minHtlc = 1 msat, balance_opt = Some(25000 msat))
val edge_ab_3 = makeEdge(3L, a, b, 1 msat, 50, minHtlc = 1 msat, balance_opt = None, capacity = 15 sat)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
edge_ab_1,
edge_ab_2,
edge_ab_3,
makeEdge(4L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
- ))
+ )), 1 day)
val amount = 50000 msat
// These pending HTLCs will have already been taken into account in the edge's `balance_opt` field: findMultiPartRoute
@@ -1088,12 +1091,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("calculate multipart route to neighbor (restricted htlc_maximum_msat)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 25 msat, 15, minHtlc = 1 msat, maxHtlc = Some(5000 msat), balance_opt = Some(18000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 1 msat, maxHtlc = Some(5000 msat), balance_opt = Some(23000 msat)),
makeEdge(3L, a, b, 1 msat, 50, minHtlc = 1 msat, maxHtlc = Some(5000 msat), balance_opt = Some(21000 msat)),
makeEdge(4L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
- ))
+ )), 1 day)
val amount = 50000 msat
val Success(routes) = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1104,12 +1107,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("calculate multipart route to neighbor (restricted htlc_minimum_msat)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 25 msat, 15, minHtlc = 2500 msat, balance_opt = Some(18000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 2500 msat, balance_opt = Some(7000 msat)),
makeEdge(3L, a, b, 1 msat, 50, minHtlc = 2500 msat, balance_opt = Some(10000 msat)),
makeEdge(4L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
- ))
+ )), 1 day)
val amount = 30000 msat
val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(2500 msat, 5))
@@ -1120,13 +1123,13 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("calculate multipart route to neighbor (through remote channels)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 25 msat, 15, minHtlc = 1000 msat, balance_opt = Some(18000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 1000 msat, balance_opt = Some(7000 msat)),
makeEdge(3L, a, c, 1000 msat, 10000, minHtlc = 1000 msat, balance_opt = Some(10000 msat)),
makeEdge(4L, c, b, 10 msat, 1000, minHtlc = 1000 msat),
makeEdge(5L, a, d, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(25000 msat)),
- ))
+ )), 1 day)
val amount = 30000 msat
val maxFeeTooLow = findMultiPartRoute(g, a, b, amount, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1139,12 +1142,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("cannot find multipart route to neighbor (not enough balance)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0, minHtlc = 1 msat, balance_opt = Some(15000 msat)),
makeEdge(2L, a, b, 0 msat, 0, minHtlc = 1 msat, balance_opt = Some(5000 msat)),
makeEdge(3L, a, b, 0 msat, 0, minHtlc = 1 msat, balance_opt = Some(10000 msat)),
makeEdge(4L, a, d, 0 msat, 0, minHtlc = 1 msat, balance_opt = Some(45000 msat)),
- ))
+ )), 1 day)
{
val result = findMultiPartRoute(g, a, b, 40000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1157,23 +1160,23 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("cannot find multipart route to neighbor (not enough capacity)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 0 msat, 0, minHtlc = 1 msat, capacity = 1500 sat),
makeEdge(2L, a, b, 0 msat, 0, minHtlc = 1 msat, capacity = 2000 sat),
makeEdge(3L, a, b, 0 msat, 0, minHtlc = 1 msat, capacity = 1200 sat),
makeEdge(4L, a, d, 0 msat, 0, minHtlc = 1 msat, capacity = 4500 sat),
- ))
+ )), 1 day)
val result = findMultiPartRoute(g, a, b, 5000000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(result == Failure(RouteNotFound))
}
test("cannot find multipart route to neighbor (restricted htlc_minimum_msat)") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 25 msat, 15, minHtlc = 5000 msat, balance_opt = Some(6000 msat)),
makeEdge(2L, a, b, 15 msat, 10, minHtlc = 5000 msat, balance_opt = Some(7000 msat)),
makeEdge(3L, a, d, 0 msat, 0, minHtlc = 5000 msat, balance_opt = Some(9000 msat)),
- ))
+ )), 1 day)
{
val result = findMultiPartRoute(g, a, b, 10000 msat, 1 msat, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1193,14 +1196,14 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// +--- B --- D ---+
val (amount, maxFee) = (30000 msat, 150 msat)
val edge_ab = makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(15000 msat))
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
edge_ab,
makeEdge(2L, b, d, 15 msat, 0, minHtlc = 1 msat, capacity = 25 sat),
makeEdge(3L, d, e, 15 msat, 0, minHtlc = 0 msat, capacity = 20 sat),
makeEdge(4L, a, c, 1 msat, 50, minHtlc = 1 msat, balance_opt = Some(10000 msat)),
makeEdge(5L, a, c, 1 msat, 50, minHtlc = 1 msat, balance_opt = Some(8000 msat)),
makeEdge(6L, c, e, 50 msat, 30, minHtlc = 1 msat, capacity = 20 sat),
- ))
+ )), 1 day)
{
val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1245,13 +1248,13 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// +--- B --- D ---+
// Our balance and the amount we want to send are below the minimum part amount.
val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(5000 msat, 5))
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(1500 msat)),
makeEdge(2L, b, d, 15 msat, 0, minHtlc = 1 msat, capacity = 25 sat),
makeEdge(3L, d, e, 15 msat, 0, minHtlc = 1 msat, capacity = 20 sat),
makeEdge(4L, a, c, 1 msat, 50, minHtlc = 1 msat, balance_opt = Some(1000 msat)),
makeEdge(5L, c, e, 50 msat, 30, minHtlc = 1 msat, capacity = 20 sat),
- ))
+ )), 1 day)
{
// We can send single-part tiny payments.
@@ -1269,11 +1272,11 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("calculate multipart route to remote node (single path)") {
val (amount, maxFee) = (100000 msat, 500 msat)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(500000 msat)),
makeEdge(2L, b, c, 10 msat, 30, minHtlc = 1 msat, capacity = 150 sat),
makeEdge(3L, c, d, 15 msat, 50, minHtlc = 1 msat, capacity = 150 sat),
- ))
+ )), 1 day)
val Success(routes) = findMultiPartRoute(g, a, d, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
checkRouteAmounts(routes, amount, maxFee)
@@ -1289,7 +1292,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// +----- E -------+
val (amount, maxFee) = (400000 msat, 250 msat)
val edge_ab = makeEdge(1L, a, b, 50 msat, 100, minHtlc = 1 msat, balance_opt = Some(500000 msat))
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
edge_ab,
makeEdge(2L, b, c, 10 msat, 30, minHtlc = 1 msat, capacity = 150 sat),
makeEdge(3L, c, d, 15 msat, 50, minHtlc = 1 msat, capacity = 150 sat),
@@ -1297,7 +1300,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, d, f, 5 msat, 50, minHtlc = 1 msat, capacity = 300 sat),
makeEdge(6L, b, e, 15 msat, 80, minHtlc = 1 msat, capacity = 210 sat),
makeEdge(7L, e, f, 15 msat, 100, minHtlc = 1 msat, capacity = 200 sat),
- ))
+ )), 1 day)
{
val Success(routes) = findMultiPartRoute(g, a, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1359,7 +1362,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(100, a, c, 5 msat, 1000, minHtlc = 1 msat, capacity = 25000 sat, balance_opt = Some(20_000_000 msat)),
makeEdge(101, c, d, 5 msat, 1000, minHtlc = 1 msat, capacity = 25000 sat),
)
- val g = DirectedGraph(preferredEdges ++ cheapEdges)
+ val g = GraphWithBalanceEstimates(DirectedGraph(preferredEdges ++ cheapEdges), 1 day)
{
val amount = 15_000_000 msat
@@ -1401,7 +1404,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// | +-------------------+ |
// +---------- E ----------+
val (amount, maxFee) = (25000 msat, 5 msat)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(75000 msat)),
makeEdge(2L, b, c, 1 msat, 0, minHtlc = 1 msat, capacity = 150 sat),
makeEdge(3L, c, f, 1 msat, 0, minHtlc = 1 msat, capacity = 150 sat),
@@ -1412,7 +1415,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(8L, a, f, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(10000 msat)),
makeEdge(9L, a, e, 1 msat, 0, minHtlc = 1 msat, balance_opt = Some(18000 msat)),
makeEdge(10L, e, f, 1 msat, 0, minHtlc = 1 msat, capacity = 15 sat),
- ))
+ )), 1 day)
val ignoredNodes = Set(d)
val ignoredChannels = Set(ChannelDesc(ShortChannelId(2L), b, c))
@@ -1428,7 +1431,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// | |
// +----- D -----+
val (amount, maxFee) = (15000 msat, 5 msat)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
// The A -> B -> E path is impossible because the A -> B balance is lower than the B -> E htlc_minimum_msat.
makeEdge(1L, a, b, 1 msat, 0, minHtlc = 500 msat, balance_opt = Some(7000 msat)),
makeEdge(2L, b, e, 1 msat, 0, minHtlc = 10000 msat, capacity = 50 sat),
@@ -1436,7 +1439,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(4L, c, e, 1 msat, 0, minHtlc = 500 msat, maxHtlc = Some(4000 msat), capacity = 50 sat),
makeEdge(5L, a, d, 1 msat, 0, minHtlc = 500 msat, balance_opt = Some(10000 msat)),
makeEdge(6L, d, e, 1 msat, 0, minHtlc = 500 msat, maxHtlc = Some(4000 msat), capacity = 50 sat),
- ))
+ )), 1 day)
val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
checkRouteAmounts(routes, amount, maxFee)
@@ -1460,7 +1463,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// +---+ | | +---+ |
// | D |-----+ +--->| F |<-----+
// +---+ +---+
- val g = DirectedGraph(Seq(
+ val g = GraphWithBalanceEstimates(DirectedGraph(Seq(
makeEdge(1L, d, a, 100 msat, 1000, minHtlc = 1000 msat, balance_opt = Some(80000 msat)),
makeEdge(2L, d, e, 100 msat, 1000, minHtlc = 1500 msat, balance_opt = Some(20000 msat)),
makeEdge(3L, a, e, 5 msat, 50, minHtlc = 1200 msat, capacity = 100 sat),
@@ -1468,7 +1471,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, e, b, 10 msat, 100, minHtlc = 1100 msat, capacity = 75 sat),
makeEdge(6L, b, c, 5 msat, 50, minHtlc = 1000 msat, capacity = 20 sat),
makeEdge(7L, c, f, 5 msat, 10, minHtlc = 1500 msat, capacity = 50 sat)
- ))
+ )), 1 day)
val routeParams = DEFAULT_ROUTE_PARAMS.copy(mpp = MultiPartParams(1500 msat, 10))
{
@@ -1508,12 +1511,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// A D (---) E (---) F
// +--- C ---+
val (amount, maxFeeE, maxFeeF) = (10000 msat, 50 msat, 100 msat)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 0, minHtlc = 1 msat, maxHtlc = Some(4000 msat), balance_opt = Some(7000 msat)),
makeEdge(2L, b, d, 1 msat, 0, minHtlc = 1 msat, capacity = 50 sat),
makeEdge(3L, a, c, 1 msat, 0, minHtlc = 1 msat, maxHtlc = Some(4000 msat), balance_opt = Some(6000 msat)),
makeEdge(4L, c, d, 1 msat, 0, minHtlc = 1 msat, capacity = 40 sat),
- ))
+ )), 1 day)
val extraEdges = Set(
makeEdge(10L, d, e, 10 msat, 100, minHtlc = 500 msat, capacity = 15 sat),
makeEdge(11L, e, f, 5 msat, 100, minHtlc = 500 msat, capacity = 10 sat),
@@ -1543,7 +1546,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val (amount, maxFee) = (15000 msat, 100 msat)
val edge_ab = makeEdge(1L, a, b, 1 msat, 0, minHtlc = 100 msat, balance_opt = Some(5000 msat))
val edge_be = makeEdge(2L, b, e, 1 msat, 0, minHtlc = 100 msat, capacity = 5 sat)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
// The A -> B -> E route is the most economic one, but we already have a pending HTLC in it.
edge_ab,
edge_be,
@@ -1551,7 +1554,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(4L, c, e, 50 msat, 0, minHtlc = 100 msat, capacity = 25 sat),
makeEdge(5L, a, d, 50 msat, 0, minHtlc = 100 msat, balance_opt = Some(10000 msat)),
makeEdge(6L, d, e, 50 msat, 0, minHtlc = 100 msat, capacity = 25 sat),
- ))
+ )), 1 day)
val pendingHtlcs = Seq(Route(5000 msat, graphEdgeToHop(edge_ab) :: graphEdgeToHop(edge_be) :: Nil, None))
val Success(routes) = findMultiPartRoute(g, a, e, amount, maxFee, pendingHtlcs = pendingHtlcs, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1580,7 +1583,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
for (_ <- 1 to 100) {
val amount = (100 + Random.nextLong(200000)).msat
val maxFee = 50.msat.max(amount * 0.03)
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, d, f, Random.nextLong(250).msat, Random.nextInt(10000), minHtlc = Random.nextLong(100).msat, maxHtlc = Some((20000 + Random.nextLong(80000)).msat), CltvExpiryDelta(Random.nextInt(288)), capacity = (10 + Random.nextLong(100)).sat, balance_opt = Some(Random.nextLong(2 * amount.toLong).msat)),
makeEdge(2L, d, a, Random.nextLong(250).msat, Random.nextInt(10000), minHtlc = Random.nextLong(100).msat, maxHtlc = Some((20000 + Random.nextLong(80000)).msat), CltvExpiryDelta(Random.nextInt(288)), capacity = (10 + Random.nextLong(100)).sat, balance_opt = Some(Random.nextLong(2 * amount.toLong).msat)),
makeEdge(3L, d, e, Random.nextLong(250).msat, Random.nextInt(10000), minHtlc = Random.nextLong(100).msat, maxHtlc = Some((20000 + Random.nextLong(80000)).msat), CltvExpiryDelta(Random.nextInt(288)), capacity = (10 + Random.nextLong(100)).sat, balance_opt = Some(Random.nextLong(2 * amount.toLong).msat)),
@@ -1590,7 +1593,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(7L, e, b, Random.nextLong(250).msat, Random.nextInt(10000), minHtlc = Random.nextLong(100).msat, maxHtlc = Some((20000 + Random.nextLong(80000)).msat), CltvExpiryDelta(Random.nextInt(288)), capacity = (10 + Random.nextLong(100)).sat),
makeEdge(8L, b, c, Random.nextLong(250).msat, Random.nextInt(10000), minHtlc = Random.nextLong(100).msat, maxHtlc = Some((20000 + Random.nextLong(80000)).msat), CltvExpiryDelta(Random.nextInt(288)), capacity = (10 + Random.nextLong(100)).sat),
makeEdge(9L, c, f, Random.nextLong(250).msat, Random.nextInt(10000), minHtlc = Random.nextLong(100).msat, maxHtlc = Some((20000 + Random.nextLong(80000)).msat), CltvExpiryDelta(Random.nextInt(288)), capacity = (10 + Random.nextLong(100)).sat)
- ))
+ )), 1 day)
findMultiPartRoute(g, d, f, amount, maxFee, routeParams = DEFAULT_ROUTE_PARAMS.copy(randomize = true), currentBlockHeight = BlockHeight(400000)) match {
case Success(routes) => checkRouteAmounts(routes, amount, maxFee)
@@ -1607,7 +1610,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// ^ |
// | |
// F <---+
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1000 msat, 1000),
makeEdge(2L, b, c, 1000 msat, 1000),
makeEdge(3L, c, d, 1000 msat, 1000),
@@ -1615,7 +1618,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, b, e, 1000 msat, 1000),
makeEdge(6L, c, f, 1000 msat, 1000),
makeEdge(7L, f, b, 1000 msat, 1000),
- ))
+ )), 1 day)
val Success(routes) = findRoute(g, a, e, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 3, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(routes.length == 2)
@@ -1632,7 +1635,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// | ^
// | |
// F ----+
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, b, a, 1000 msat, 1000),
makeEdge(2L, c, b, 1000 msat, 1000),
makeEdge(3L, d, c, 1000 msat, 1000),
@@ -1640,7 +1643,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, e, b, 1000 msat, 1000),
makeEdge(6L, f, c, 1000 msat, 1000),
makeEdge(7L, b, f, 1000 msat, 1000),
- ))
+ )), 1 day)
val Success(routes) = findRoute(g, e, a, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 3, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(routes.length == 2)
@@ -1676,7 +1679,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
q.toSeq
}
- val g = DirectedGraph(makeEdges(10))
+ val g = GraphWithBalanceEstimates(DirectedGraph(makeEdges(10)), 1 day)
val Success(routes) = findRoute(g, a, b, DEFAULT_AMOUNT_MSAT, 100000000 msat, numRoutes = 10, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(routes.distinct.length == 10)
@@ -1708,7 +1711,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
q.toSeq
}
- val g = DirectedGraph(makeEdges(10))
+ val g = GraphWithBalanceEstimates(DirectedGraph(makeEdges(10)), 1 day)
val Success(routes) = findRoute(g, a, b, DEFAULT_AMOUNT_MSAT, 100000000 msat, numRoutes = 10, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
assert(routes.distinct.length == 10)
@@ -1717,9 +1720,9 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
}
test("can't relay if fee is not sufficient") {
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1000 msat, 7000),
- ))
+ )), 1 day)
assert(findRoute(g, a, b, 10000000 msat, 10000 msat, numRoutes = 3, routeParams = DEFAULT_ROUTE_PARAMS.copy(includeLocalChannelCost = true), currentBlockHeight = BlockHeight(400000)) == Failure(RouteNotFound))
assert(findRoute(g, a, b, 10000000 msat, 100000 msat, numRoutes = 3, routeParams = DEFAULT_ROUTE_PARAMS.copy(includeLocalChannelCost = true), currentBlockHeight = BlockHeight(400000)).isSuccess)
@@ -1734,7 +1737,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// v |
// E ---> F
val start = randomKey().publicKey
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(0L, start, a, 0 msat, 0),
makeEdge(1L, a, b, 1000 msat, 1000),
makeEdge(2L, a, c, 0 msat, 0),
@@ -1743,7 +1746,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
makeEdge(5L, c, e, 0 msat, 0),
makeEdge(6L, e, f, 600 msat, 1000),
makeEdge(7L, f, d, 0 msat, 0),
- ))
+ )), 1 day)
{ // No hop cost
val Success(routes) = findRoute(g, start, b, DEFAULT_AMOUNT_MSAT, 100000000 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = BlockHeight(400000))
@@ -1771,13 +1774,13 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// v |
// C ---> D
val start = randomKey().publicKey
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(0L, start, a, 0 msat, 0),
makeEdge(1L, a, b, 1000 msat, 1000, capacity = (DEFAULT_AMOUNT_MSAT * 1.2).truncateToSatoshi),
makeEdge(2L, a, c, 400 msat, 500, capacity = (DEFAULT_AMOUNT_MSAT * 3).truncateToSatoshi),
makeEdge(3L, c, d, 400 msat, 500, capacity = (DEFAULT_AMOUNT_MSAT * 3).truncateToSatoshi),
makeEdge(4L, d, b, 400 msat, 500, capacity = (DEFAULT_AMOUNT_MSAT * 3).truncateToSatoshi),
- ))
+ )), 1 day)
{
val hc = HeuristicsConstants(
@@ -1785,6 +1788,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
failureFees = RelayFees(1000 msat, 500),
hopFees = RelayFees(0 msat, 0),
useLogProbability = false,
+ usePastRelaysData = true,
)
val Success(routes) = findRoute(g, start, b, DEFAULT_AMOUNT_MSAT, 100000000 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = hc), currentBlockHeight = BlockHeight(400000))
assert(routes.distinct.length == 1)
@@ -1799,6 +1803,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
failureFees = RelayFees(10000 msat, 1000),
hopFees = RelayFees(0 msat, 0),
useLogProbability = true,
+ usePastRelaysData = true,
)
val Success(routes) = findRoute(g, start, b, DEFAULT_AMOUNT_MSAT, 100000000 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = hc), currentBlockHeight = BlockHeight(400000))
assert(routes.distinct.length == 1)
@@ -1813,19 +1818,20 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// v |
// C ---> D
val start = randomKey().publicKey
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(0L, start, a, 0 msat, 0),
makeEdge(1L, a, b, 1000 msat, 1000, cltvDelta = CltvExpiryDelta(1000)),
makeEdge(2L, a, c, 350 msat, 350, cltvDelta = CltvExpiryDelta(10)),
makeEdge(3L, c, d, 350 msat, 350, cltvDelta = CltvExpiryDelta(10)),
makeEdge(4L, d, b, 350 msat, 350, cltvDelta = CltvExpiryDelta(10)),
- ))
+ )), 1 day)
val hc = HeuristicsConstants(
lockedFundsRisk = 1e-7,
failureFees = RelayFees(0 msat, 0),
hopFees = RelayFees(0 msat, 0),
useLogProbability = true,
+ usePastRelaysData = true,
)
val Success(routes) = findRoute(g, start, b, DEFAULT_AMOUNT_MSAT, 100000000 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = hc), currentBlockHeight = BlockHeight(400000))
assert(routes.distinct.length == 1)
@@ -1835,17 +1841,18 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("edge too small to relay payment is ignored") {
// A ===> B ===> C <--- D
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 100 msat, 100),
makeEdge(2L, b, c, 100 msat, 100),
makeEdge(3L, d, c, 100 msat, 100, capacity = 1000 sat),
- ))
+ )), 1 day)
val hc = HeuristicsConstants(
lockedFundsRisk = 1e-7,
failureFees = RelayFees(0 msat, 0),
hopFees = RelayFees(0 msat, 0),
useLogProbability = true,
+ usePastRelaysData = true,
)
val Success(routes) = findRoute(g, a, c, DEFAULT_AMOUNT_MSAT, 100000000 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = hc), currentBlockHeight = BlockHeight(400000))
assert(routes.distinct.length == 1)
@@ -1857,11 +1864,11 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
// A ===> B ===> C
// \___________/
val recentChannelId = ShortChannelId.fromCoordinates("399990x1x2").success.value.toLong
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 1 msat, 1, capacity = 100_000_000 sat),
makeEdge(2L, b, c, 1 msat, 1, capacity = 100_000_000 sat),
makeEdge(recentChannelId, a, c, 1000 msat, 100),
- ))
+ )), 1 day)
val wr = PaymentWeightRatios(
baseFactor = 0,
@@ -1878,7 +1885,7 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("trampoline relay with direct channel to target") {
val amount = 100_000_000 msat
- val g = DirectedGraph(List(makeEdge(1L, a, b, 1000 msat, 1000, capacity = 100_000_000 sat)))
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(makeEdge(1L, a, b, 1000 msat, 1000, capacity = 100_000_000 sat))), 1 day)
{
val routeParams = DEFAULT_ROUTE_PARAMS.copy(includeLocalChannelCost = true, boundaries = SearchBoundaries(100_999 msat, 0.0, 6, CltvExpiryDelta(576)))
@@ -1893,12 +1900,12 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
test("small local edge with liquidity is better than big remote edge") {
// A == B == C -- D
// \_______/
- val g = DirectedGraph(List(
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
makeEdge(1L, a, b, 100 msat, 100, minHtlc = 1000 msat, capacity = 100000000 sat, balance_opt = Some(10000000 msat)),
makeEdge(2L, b, c, 100 msat, 100, minHtlc = 1000 msat, capacity = 100000000 sat),
makeEdge(3L, a, c, 100 msat, 100, minHtlc = 1000 msat, capacity = 100 sat, balance_opt = Some(100000 msat)),
makeEdge(4L, c, d, 100 msat, 100, minHtlc = 1000 msat, capacity = 100000000 sat),
- ))
+ )), 1 day)
val wr = PaymentWeightRatios(
baseFactor = 0,
@@ -1911,6 +1918,38 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
val route :: Nil = routes
assert(route2Ids(route) == 3 :: 4 :: Nil)
}
+
+ test("take past attempts into account") {
+ // C
+ // / \
+ // A -- B E
+ // \ /
+ // D
+ val g = GraphWithBalanceEstimates(DirectedGraph(List(
+ makeEdge(1L, a, b, 100 msat, 100, minHtlc = 1000 msat, capacity = 100000000 sat),
+ makeEdge(2L, b, c, 100 msat, 100, minHtlc = 1000 msat, capacity = 100000000 sat),
+ makeEdge(3L, c, e, 100 msat, 100, minHtlc = 1000 msat, capacity = 100000000 sat),
+ makeEdge(4L, b, d, 1000 msat, 1000, minHtlc = 1000 msat, capacity = 100000 sat),
+ makeEdge(5L, d, e, 1000 msat, 1000, minHtlc = 1000 msat, capacity = 100000 sat),
+ )), 1 day)
+
+ val amount = 50000 msat
+
+ val hc = HeuristicsConstants(
+ lockedFundsRisk = 0,
+ failureFees = RelayFees(1000 msat, 1000),
+ hopFees = RelayFees(500 msat, 200),
+ useLogProbability = true,
+ usePastRelaysData = true
+ )
+ val Success(route1 :: Nil) = findRoute(g, a, e, amount, 100000000 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = hc, includeLocalChannelCost = true), currentBlockHeight = BlockHeight(400000))
+ assert(route2Ids(route1) == 1 :: 2 :: 3 :: Nil)
+
+ val h = g.routeCouldRelay(route1.stopAt(c)).channelCouldNotSend(route1.hops.last, amount)
+
+ val Success(route2 :: Nil) = findRoute(h, a, e, amount, 100000000 msat, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS.copy(heuristics = hc, includeLocalChannelCost = true), currentBlockHeight = BlockHeight(400000))
+ assert(route2Ids(route2) == 1 :: 4 :: 5 :: Nil)
+ }
}
object RouteCalculationSpec {
Risk score
Our methodology →Why this scored 20/100
Human-validated context
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
No validated notes yet.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.