[bug]: routerClient.BuildRoute does not consider inbound fees

[silenzara]

Background

Using routerClient.BuildRoute to create a route does not produce routes that use any fee discounts.

Your environment

• LND 0.18.0-beta commit=v0.18.0-beta (commit: fed7609)

Steps to reproduce

Find a route via lnClient.QueryRoutes until one is found with a hop that has negative inbound fees. Reconstruct same route using the pubkeys from the original route that QueryRoutes returned:

	for _, hop := range originalRoute.Hops {
		pk, _ := hex.DecodeString(hop.PubKey)
		pks = append(pks, pk)
	}

	sameRoute, err := satty.routerClient.BuildRoute(ctx, &routerrpc.BuildRouteRequest{
		AmtMsat:        sats * 1000,
		HopPubkeys:     pks,
		FinalCltvDelta: final,
	})

Expected behaviour

routerClient.BuildRoute should return the same route as the lnClient.QueryRoutes one with the same discounted fees.

Actual behaviour

Code:

fmt.Printf("via lnClient.QueryRoutes\n")
for n, hop := range originalRoute.Hops {
	fmt.Printf("%d - %s | Hop fee: %d\n", n, hop.PubKey, hop.FeeMsat)
}

fmt.Printf("Total fee: %d\n", originalRoute.TotalFeesMsat)

fmt.Printf("\n----\n\n")

fmt.Printf("via routerClient.BuildRoute, same pubkeys\n")
for n, hop := range sameRoute.Route.Hops {
	fmt.Printf("%d - %s | Hop fee: %d\n", n, hop.PubKey, hop.FeeMsat)
}

fmt.Printf("Total fee: %d\n", sameRoute.Route.TotalFeesMsat)

Debug output:

via lnClient.QueryRoutes
0 - 02e46fce29587e4a8d39da2cf21f032536c1ced45e82e4ba04f127ee7337783b38 | Hop fee: 0
1 - 03423790614f023e3c0cdaa654a3578e919947e4c3a14bf5044e7c787ebd11af1a | Hop fee: 0
2 - 033b63e4a9931dc151037acbce12f4f8968c86f5655cf102bbfa85a26bd4adc6d9 | Hop fee: 240771
3 - 037f990e61acee8a7697966afd29dd88f3b1f8a7b14d625c4f8742bd952003a590 | Hop fee: 1185
4 - 027ce055380348d7812d2ae7745701c9f93e70c1adeb2657f053f91df4f2843c71 | Hop fee: 51340
5 - 021c97a90a411ff2b10dc2a8e32de2f29d2fa49d41bfbb52bd416e460db0747d0d | Hop fee: 1000
6 - 03a93b87bf9f052b8e862d51ebbac4ce5e97b5f4137563cd5128548d7f5978dda9 | Hop fee: 0
Total fee: 294296

----

via routerClient.BuildRoute, same pubkeys
0 - 02e46fce29587e4a8d39da2cf21f032536c1ced45e82e4ba04f127ee7337783b38 | Hop fee: 0
1 - 03423790614f023e3c0cdaa654a3578e919947e4c3a14bf5044e7c787ebd11af1a | Hop fee: 0
2 - 033b63e4a9931dc151037acbce12f4f8968c86f5655cf102bbfa85a26bd4adc6d9 | Hop fee: 240945
3 - 037f990e61acee8a7697966afd29dd88f3b1f8a7b14d625c4f8742bd952003a590 | Hop fee: 1185
4 - 027ce055380348d7812d2ae7745701c9f93e70c1adeb2657f053f91df4f2843c71 | Hop fee: 185156
5 - 021c97a90a411ff2b10dc2a8e32de2f29d2fa49d41bfbb52bd416e460db0747d0d | Hop fee: 1000
6 - 03a93b87bf9f052b8e862d51ebbac4ce5e97b5f4137563cd5128548d7f5978dda9 | Hop fee: 0
Total fee: 428286

[silenzara]

While writing this issue I actually found out that this is a known "issue": #7060

Decided to submit it anyway because it might result in unexpected behaviour while using BuildRoute to rebalance.

[bitromortac]

I looked into the problem and checked how BuildRoute works. It would be easy to upgrade it with inbound fees, if there wouldn't be the option to build a route for an unknown, minimal amount.

The minimal amount approach currently requires:

1. a pass from receiver to sender to bump up a small starting amount if min HTLC constraints are encountered, to compute the sender amount
2. a pass from sender to receiver, to determine the new receiver amount
3. call newRoute to build the route with the specified receiver amount

Inbound fees complicate this in the second step, because inbound fees are not (easily?) invertible because they depend recursively on all remaining hops (due to the capping by outbound fees). I haven't found a way to compute an outgoing amount from an incoming amount yet. My current attempt (draft) is to do the first pass, followed by a brute force search within some bounds to determine the receiver amount by incrementally checking if the receiver amount is compatible with the sender amount. This may add lot of iterations compared to the original approach because the search space may be large.

The current approach tries to fulfill min HTLC constraints while maximizing the amount a receiver receives. If we would drop that maximizing requirement, we could express the min HTLC amount bumps in the first pass as hop fees and be done after the first pass, by not using newRoute as postprocessing as suggested here 838975f (from #6920) and to avoid computing the inverse of inbound fees.

A longer term solution could be to let pathfinding itself do the route building, as suggested in #6920, by using hop constraints for the input route. This would require updates to the pathfinding algo to not use newRoute. I think this is a nice opportunity to remove a lot of code, but for that to work with the minimal amount option, we would also need to drop the maximizing receiver amount requirement.

I think the choice boils down to whether we want to drop the requirement of the receiver receiving the max it could when building a route for the minimal amount. The amount to send would stay the same, the receiver would just receive less while the difference goes to fees at the hop where a min HTLC constraint was met.

[feelancer21]

Inbound fees complicate this in the second step, because inbound fees are not (easily?) invertible because they depend recursively on all remaining hops (due to the capping by outbound fees). I haven't found a way to compute an outgoing amount from an incoming amount yet.

I felt challenged. The problem seems to be quite easy to invert, but obviously it is not. Created a small doc and a python prototype. Feel free to check this out and implement in lnd.

https://github.com/feelancer21/lnd/tree/proto-inverse-outbound/prototype

[bitromortac]

I felt challenged. The problem seems to be quite easy to invert, but obviously it is not. Created a small doc and a python prototype. Feel free to check this out and implement in lnd.

Great work and nice presentation @feelancer21, thank you for the thoughtful input 🔥! This would indeed work if policies could be assumed constant, but due possible parallel channels, we need to "synthesize" a unified policy that respects min/max HTLC bounds, which makes the unified policy dependent on the amount that is forwarded. You can see that step in the backward direction here.
When re-scaling the amount in the forward pass, we increase the amounts for the last hops where the amount was bumped because of min HTLC constraints. This could lead to max HTLC violations, which is why the policy in the exact solution is not predetermined. To rephrase, to do the calculation you'd need both, the incoming and outgoing policies, by calls to getEdge. The incoming policy we can in principle determine, getEdge would need to be changed to take the forwarded amount. However, the next hop's unified policy (to compute the outbound fee) depends on the outgoing amount we try to compute, which creates a recursive dependency and thus (I think) it is not possible to compute the exact outgoing amount in straightforward manner.
What we could do is to just take the policies determined in the backward pass and use them to do the inversion. This would not be 100% exact if we bump against a max HTLC constraint for the last hops (but that can also happen today). This may be a good solution because in applications I know of, the path was constructed for a larger amount that is about to be re-scaled to the minimal amount. In the worst case this would lead to an error and manual amount selection would need to be done. I think this is a good tradeoff. Will give this a try and thanks again!

[feelancer21]

However, the next hop's unified policy (to compute the outbound fee) depends on the outgoing amount we try to compute, which creates a recursive dependency and thus (I think) it is not possible to compute the exact outgoing amount in straightforward manner.

Thank you for the explanations. I had that in mind with the unfied edges, but only now realized how strongly the selections of the unfied edges influence each other. I also believe that you don't need the 100% optimal solution for the case. Noderunners should also stop having different feestrategies on channels with the same peer. So far I have only noticed negative effects in this regard.