Fix computation of path weight (#1794)

There are two cases depending on whether you use weight ratios or not. They used to behave very differently: * Without weight ratios, the weight would be the total amount to send (base amount + fees) * With weight ratios, the ratios would apply to the total amount, not just the fees. The effect is that only the number of hops and then the weight factors matter as the fee itself is negligible compared to the total amount. The code is now shared and the weight is now the sum of the fees (multiplied by a factor if using weight ratios).
ACINQ · May 12, 2021 · c641549 · c641549
1 parent 55b50ec
commit c641549
Show file tree

Hide file tree

Showing 2 changed files with 33 additions and 33 deletions.
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
@@ -264,32 +264,32 @@ object Graph {
    * @param currentBlockHeight the height of the chain tip (latest block).
    * @param weightRatios       ratios used to 'weight' edges when searching for the shortest path
    */
-  private def addEdgeWeight(sender: PublicKey, edge: GraphEdge, prev: RichWeight, currentBlockHeight: Long, weightRatios: Option[WeightRatios]): RichWeight = weightRatios match {
-    case None =>
-      val totalCost = if (edge.desc.a == sender) prev.cost else addEdgeFees(edge, prev.cost)
-      val totalCltv = if (edge.desc.a == sender) prev.cltv else prev.cltv + edge.update.cltvExpiryDelta
-      RichWeight(totalCost, prev.length + 1, totalCltv, totalCost.toLong)
-    case Some(wr) =>
-      import RoutingHeuristics._
-
-      // Every edge is weighted by funding block height where older blocks add less weight, the window considered is 2 months.
-      val channelBlockHeight = ShortChannelId.coordinates(edge.desc.shortChannelId).blockHeight
-      val ageFactor = normalize(channelBlockHeight, min = currentBlockHeight - BLOCK_TIME_TWO_MONTHS, max = currentBlockHeight)
-
-      // Every edge is weighted by channel capacity, larger channels add less weight
-      val edgeMaxCapacity = edge.capacity.toMilliSatoshi
-      val capFactor = 1 - normalize(edgeMaxCapacity.toLong, CAPACITY_CHANNEL_LOW.toLong, CAPACITY_CHANNEL_HIGH.toLong)
-
-      // Every edge is weighted by its cltv-delta value, normalized
-      val cltvFactor = normalize(edge.update.cltvExpiryDelta.toInt, CLTV_LOW, CLTV_HIGH)
-
-      val totalCost = if (edge.desc.a == sender) prev.cost else addEdgeFees(edge, prev.cost)
-      val totalCltv = if (edge.desc.a == sender) prev.cltv else prev.cltv + edge.update.cltvExpiryDelta
-      // NB we're guaranteed to have weightRatios and factors > 0
-      val factor = (cltvFactor * wr.cltvDeltaFactor) + (ageFactor * wr.ageFactor) + (capFactor * wr.capacityFactor)
-      val totalWeight = if (edge.desc.a == sender) prev.weight else prev.weight + totalCost.toLong * factor
-
-      RichWeight(totalCost, prev.length + 1, totalCltv, totalWeight)
+  private def addEdgeWeight(sender: PublicKey, edge: GraphEdge, prev: RichWeight, currentBlockHeight: Long, weightRatios: Option[WeightRatios]): RichWeight = {
+    val totalCost = if (edge.desc.a == sender) prev.cost else addEdgeFees(edge, prev.cost)
+    val fee = totalCost - prev.cost
+    val totalCltv = if (edge.desc.a == sender) prev.cltv else prev.cltv + edge.update.cltvExpiryDelta
+    val factor = weightRatios match {
+      case None =>
+        1.0
+      case Some(wr) =>
+        import RoutingHeuristics._
+
+        // Every edge is weighted by funding block height where older blocks add less weight, the window considered is 2 months.
+        val channelBlockHeight = ShortChannelId.coordinates(edge.desc.shortChannelId).blockHeight
+        val ageFactor = normalize(channelBlockHeight, min = currentBlockHeight - BLOCK_TIME_TWO_MONTHS, max = currentBlockHeight)
+
+        // Every edge is weighted by channel capacity, larger channels add less weight
+        val edgeMaxCapacity = edge.capacity.toMilliSatoshi
+        val capFactor = 1 - normalize(edgeMaxCapacity.toLong, CAPACITY_CHANNEL_LOW.toLong, CAPACITY_CHANNEL_HIGH.toLong)
+
+        // Every edge is weighted by its cltv-delta value, normalized
+        val cltvFactor = normalize(edge.update.cltvExpiryDelta.toInt, CLTV_LOW, CLTV_HIGH)
+
+        // NB we're guaranteed to have weightRatios and factors > 0
+        (cltvFactor * wr.cltvDeltaFactor) + (ageFactor * wr.ageFactor) + (capFactor * wr.capacityFactor)
+    }
+    val totalWeight = prev.weight + fee.toLong * factor
+    RichWeight(totalCost, prev.length + 1, totalCltv, totalWeight)
   }
 
   /**

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
@@ -807,13 +807,13 @@ class RouteCalculationSpec extends AnyFunSuite with ParallelTestExecution {
     // 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(
-      makeEdge(1L, a, b, feeBase = 0 msat, 0, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(13)),
-      makeEdge(4L, a, e, feeBase = 0 msat, 0, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(12)),
-      makeEdge(2L, b, c, feeBase = 1 msat, 0, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(500)),
-      makeEdge(3L, c, d, feeBase = 1 msat, 0, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(500)),
-      makeEdge(5L, e, f, feeBase = 2 msat, 0, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(9)),
-      makeEdge(6L, f, d, feeBase = 2 msat, 0, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(9)),
-      makeEdge(7L, e, c, feeBase = 2 msat, 0, minHtlc = 0 msat, capacity = largeCapacity, cltvDelta = CltvExpiryDelta(12))
+      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)),
+      makeEdge(3L, c, d, feeBase = 1 msat, 1000, minHtlc = 0 msat, capacity = defaultCapacity, cltvDelta = CltvExpiryDelta(500)),
+      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))
     ))
 
     val Success(routeFeeOptimized :: Nil) = findRoute(g, a, d, DEFAULT_AMOUNT_MSAT, DEFAULT_MAX_FEE, numRoutes = 1, routeParams = DEFAULT_ROUTE_PARAMS, currentBlockHeight = 400000)