Repository: lightningnetwork/lnd (language: go)

Issue:
[bug]: SendPaymentV2 does not respect fee limit setting in relation to inbound discounts
### Background

When paying to a payment request the caller can specify a fee limit for the maximum allowable fees to pay, with the assumption that if there is a route that has a fee within that constraint it will be used for the payment.

With the introduction of inbound discounts for routing fees, the fee limit does not respect these discounts and therefore will return no route found even when there is in fact a route that would fulfill the fee limit constraint after inbound discounts are applied.

This is problematic for probe-first payment flows that use the routing fee found in the probe as an input to the fee limit argument of SendPaymentV2

Describe your issue here.

### Your environment

- lnd 0.18.2

### Steps to reproduce

- Create A B C nodes, default routing fees to 1 sat
- Have B set an inbound discount on AB to allow traffic to be zero-fee when coming from A
- Probe or attempt paying A->C without a fee limit to confirm that the route from A to C would be zero fee
- Create an invoice on C and attempt to pay from A to C, with a fee limit of zero

### Expected behavior

- The fee limit should recognize the inbound discount and allow payment

### Actual behavior

- Payment fails with a no route error



Discussion / hints:
I think that the fee limit check may be in the wrong place:
https://github.com/lightningnetwork/lnd/blob/8c0d7862c210ea6db5dc90ebfe9c3236962e68d4/routing/pathfind.go#L782-L787

It is done on the net amount, only later the discount is applied which reduces the fee. Will check and try to fix it.
I have two concerns with current path algo. We should take a closer look at them:
1. i feel that we can get into a situation with decreasing tempDist, which causes problems with Dijkstra in some edge cases. 

2. also, I think the signedFee check doesn't really make sense. For example, we have three edges E_1, E_2 and E_3. E_3 has a high outbound fee to a sink, e.g. 2000ppm. The last hop has an inbound fee to E_2 of -1000ppm. Let us now assume that the outbound fee is 0 on E_2. The signedFee check does not check whether 2000 + (-1000) > 0, which would be the correct check in a line graph. It checks if 0 + (-1000) >0. This can explain why my routing node uses more inbound discounts on channels where the peer has a higher remote outbound fee. 

Fix patch:
diff --git a/docs/release-notes/release-notes-0.18.3.md b/docs/release-notes/release-notes-0.18.3.md
index 4cb59b76d9..6672a6e584 100644
--- a/docs/release-notes/release-notes-0.18.3.md
+++ b/docs/release-notes/release-notes-0.18.3.md
@@ -36,6 +36,10 @@
 * [Fixed a bug](https://github.com/lightningnetwork/lnd/pull/8896) that caused
   LND to use a default fee rate for the batch channel opening flow.
 
+* The fee limit for payments [was made
+  compatible](https://github.com/lightningnetwork/lnd/pull/8941) with inbound
+  fees.
+
 # New Features
 ## Functional Enhancements
 ## RPC Additions
@@ -150,6 +154,7 @@
 # Contributors (Alphabetical Order)
 
 * Andras Banki-Horvath
+* bitromortac
 * Bufo
 * Elle Mouton
 * Matheus Degiovani
diff --git a/routing/pathfind.go b/routing/pathfind.go
index 086b816929..d76c5ea22f 100644
--- a/routing/pathfind.go
+++ b/routing/pathfind.go
@@ -697,7 +697,6 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 	// processEdge is a helper closure that will be used to make sure edges
 	// satisfy our specific requirements.
 	processEdge := func(fromVertex route.Vertex,
-		fromFeatures *lnwire.FeatureVector,
 		edge *unifiedEdge, toNodeDist *nodeWithDist) {
 
 		edgesExpanded++
@@ -724,6 +723,24 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		amountToSend := toNodeDist.netAmountReceived +
 			lnwire.MilliSatoshi(inboundFee)
 
+		// Check if accumulated fees would exceed fee limit when this
+		// node would be added to the path.
+		totalFee := int64(amountToSend) - int64(amt)
+
+		log.Trace(lnutils.NewLogClosure(func() string {
+			return fmt.Sprintf(
+				"Checking fromVertex (%v) with "+
+					"minInboundFee=%v, inboundFee=%v, "+
+					"amountToSend=%v, amt=%v, totalFee=%v",
+				fromVertex, minInboundFee, inboundFee,
+				amountToSend, amt, totalFee,
+			)
+		}))
+
+		if totalFee > 0 && lnwire.MilliSatoshi(totalFee) > r.FeeLimit {
+			return
+		}
+
 		// Request the success probability for this edge.
 		edgeProbability := r.ProbabilitySource(
 			fromVertex, toNodeDist.node, amountToSend,
@@ -780,13 +797,6 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		netAmountToReceive := amountToSend +
 			lnwire.MilliSatoshi(outboundFee)
 
-		// Check if accumulated fees would exceed fee limit when this
-		// node would be added to the path.
-		totalFee := int64(netAmountToReceive) - int64(amt)
-		if totalFee > 0 && lnwire.MilliSatoshi(totalFee) > r.FeeLimit {
-			return
-		}
-
 		// Calculate total probability of successfully reaching target
 		// by multiplying the probabilities. Both this edge and the rest
 		// of the route must succeed.
@@ -813,7 +823,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		// weight composed of the fee that this node will charge and
 		// the amount that will be locked for timeLockDelta blocks in
 		// the HTLC that is handed out to fromVertex.
-		weight := edgeWeight(netAmountToReceive, fee, timeLockDelta)
+		weight := edgeWeight(amountToSend, fee, timeLockDelta)
 
 		// Compute the tentative weight to this new channel/edge
 		// which is the weight from our toNode to the target node
@@ -1035,7 +1045,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 
 			// Check if this candidate node is better than what we
 			// already have.
-			processEdge(fromNode, fromFeatures, edge, partialPath)
+			processEdge(fromNode, edge, partialPath)
 		}
 
 		if nodeHeap.Len() == 0 {


Test patch:
diff --git a/itest/list_on_test.go b/itest/list_on_test.go
index 02fc3919f1..c5d63bd2dd 100644
--- a/itest/list_on_test.go
+++ b/itest/list_on_test.go
@@ -354,6 +354,10 @@ var allTestCases = []*lntest.TestCase{
 		Name:     "route fee cutoff",
 		TestFunc: testRouteFeeCutoff,
 	},
+	{
+		Name:     "route fee limit after queryroutes",
+		TestFunc: testFeeLimitAfterQueryRoutes,
+	},
 	{
 		Name:     "rpc middleware interceptor",
 		TestFunc: testRPCMiddlewareInterceptor,
diff --git a/itest/lnd_routing_test.go b/itest/lnd_routing_test.go
index 1e627c7d70..0b1cfebe84 100644
--- a/itest/lnd_routing_test.go
+++ b/itest/lnd_routing_test.go
@@ -1331,6 +1331,80 @@ func testRouteFeeCutoff(ht *lntest.HarnessTest) {
 	ht.CloseChannel(carol, chanPointCarolDave)
 }
 
+// testFeeLimitAfterQueryRoutes tests that a payment's fee limit is consistent
+// with the fee of a queried route.
+func testFeeLimitAfterQueryRoutes(ht *lntest.HarnessTest) {
+	// Create a three hop network: Alice -> Bob -> Carol.
+	chanAmt := btcutil.Amount(100000)
+	chanPoints, nodes := createSimpleNetwork(
+		ht, []string{}, 3, lntest.OpenChannelParams{Amt: chanAmt},
+	)
+	alice, bob, carol := nodes[0], nodes[1], nodes[2]
+	chanPointAliceBob, chanPointBobCarol := chanPoints[0], chanPoints[1]
+
+	// We set an inbound fee discount on Bob's channel to Alice to
+	// effectively set the outbound fees charged to Carol to zero.
+	expectedPolicy := &lnrpc.RoutingPolicy{
+		FeeBaseMsat:             1000,
+		FeeRateMilliMsat:        1,
+		InboundFeeBaseMsat:      -1000,
+		InboundFeeRateMilliMsat: -1,
+		TimeLockDelta: uint32(
+			chainreg.DefaultBitcoinTimeLockDelta,
+		),
+		MinHtlc:     1000,
+		MaxHtlcMsat: lntest.CalculateMaxHtlc(chanAmt),
+	}
+
+	updateFeeReq := &lnrpc.PolicyUpdateRequest{
+		Scope: &lnrpc.PolicyUpdateRequest_ChanPoint{
+			ChanPoint: chanPointAliceBob,
+		},
+		BaseFeeMsat:   expectedPolicy.FeeBaseMsat,
+		FeeRatePpm:    uint32(expectedPolicy.FeeRateMilliMsat),
+		TimeLockDelta: expectedPolicy.TimeLockDelta,
+		MaxHtlcMsat:   expectedPolicy.MaxHtlcMsat,
+		InboundFee: &lnrpc.InboundFee{
+			BaseFeeMsat: expectedPolicy.InboundFeeBaseMsat,
+			FeeRatePpm:  expectedPolicy.InboundFeeRateMilliMsat,
+		},
+	}
+	bob.RPC.UpdateChannelPolicy(updateFeeReq)
+
+	// Wait for Alice to receive the channel update from Bob.
+	ht.AssertChannelPolicyUpdate(
+		alice, bob, expectedPolicy, chanPointAliceBob, false,
+	)
+
+	// We query the only route available to Carol.
+	queryRoutesReq := &lnrpc.QueryRoutesRequest{
+		PubKey: carol.PubKeyStr,
+		Amt:    paymentAmt,
+	}
+	routesResp := alice.RPC.QueryRoutes(queryRoutesReq)
+
+	// Verify that the route has zero fees.
+	require.Len(ht, routesResp.Routes, 1)
+	require.Len(ht, routesResp.Routes[0].Hops, 2)
+	require.Zero(ht, routesResp.Routes[0].TotalFeesMsat)
+
+	// Attempt a payment with a fee limit of zero.
+	invoice := &lnrpc.Invoice{Value: paymentAmt}
+	invoiceResp := carol.RPC.AddInvoice(invoice)
+	sendReq := &routerrpc.SendPaymentRequest{
+		PaymentRequest: invoiceResp.PaymentRequest,
+		TimeoutSeconds: 60,
+		FeeLimitMsat:   0,
+	}
+
+	// We assert that a route compatible with the fee limit is available.
+	ht.SendPaymentAssertSettled(alice, sendReq)
+
+	// Once we're done, close the channels.
+	ht.CloseChannel(alice, chanPointAliceBob)
+	ht.CloseChannel(bob, chanPointBobCarol)
+}
+
 // computeFee calculates the payment fee as specified in BOLT07.
 func computeFee(baseFee, feeRate, amt lnwire.MilliSatoshi) lnwire.MilliSatoshi {
 	return baseFee + amt*feeRate/1000000
diff --git a/lntest/node/watcher.go b/lntest/node/watcher.go
index 7656cb3c5a..f7672b825a 100644
--- a/lntest/node/watcher.go
+++ b/lntest/node/watcher.go
@@ -221,7 +221,7 @@ func (nw *nodeWatcher) WaitForChannelPolicyUpdate(
 		select {
 		// Send a watch request every second.
 		case <-ticker.C:
-			// Did the event can close in the meantime? We want to
+			// Did the event chan close in the meantime? We want to
 			// avoid a "close of closed channel" panic since we're
 			// re-using the same event chan for multiple requests.
 			select {