[bug]: SendPaymentV2 does not respect fee limit setting in relation to inbound discounts

[alexbosworth]

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

[bitromortac]

I think that the fee limit check may be in the wrong place:

lnd/routing/pathfind.go

Lines 782 to 787 in 8c0d786

	// 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
	}

It is done on the net amount, only later the discount is applied which reduces the fee. Will check and try to fix it.

[feelancer21]

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.

[bitromortac]

i feel that we can get into a situation with decreasing tempDist, which causes problems with Dijkstra in some edge cases.

As discussed in chat, I don't think that it is possible for a route to decrease in weight after a new hop was added, since fee and therefore edgeWeight are non-negative, which means that tempDist can't decrease.

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.

This is related to my comment here #6934 (review) (you noted that as well in #8945, which is a better place to discuss it).

[feelancer21]

Yes, Agree about the first point and we should outsource the discussion about the second point,