Repository: lightningnetwork/lnd
Pull request #6934 (2022-09-21 09:54:43)

routing: inbound fees send support
Implements send support for inbound routing fees. The receiver side is implemented in #6703 and this PR is based off of that.

### Implementation details

* The `channel_update` extra opaque data isn't validated before it was stored in the database. This means that everywhere we read this data, a tlv error might be encountered. In this PR, this case is handled in a mostly defensive way, skipping over the channel policy.

Based on #6703. Review first commits there.

Support for inbound fees in `BuildRoute` is explored in #7060.


joostjager: Removed exit hop inbound fees. Previous code saved in https://github.com/lightningnetwork/lnd/compare/master...bottlepay:lnd:inbound-fees-send-support-exit-hop
joostjager: >What would be needed to get his PR out of draft?

I think it is pretty complete as is. Definitely good enough to be moved out of draft, so I did.

>Would you keep the current penalization scheme for failures? It seems like with inbound discounts, the channel partner would also need to be blamed more, as they can offset outbound fees of their peer, where a payment attempt wouldn't have happened otherwise with high outbound fees only.

Afaik when the node with a high inbound discount is not delivering, it is penalized as part of a pair of nodes. Do you think that is insufficient?
alexbosworth: I think it would be safer for people to experiment with if negative fees were scoped out so that no net negative possibility was allowed - lower bound on a fee would be zero basically, this kind of thing could also be added in the proto comments or somewhere to tell people how to play with it
joostjager: One thing to keep in mind is that there are two definitions of the 'total fee':
1. _Node total fee_: the sum of inbound and outbound fee charged by a routing node.
2. _Channel total fee_: the outbound fee charged at the sending end of a channel plus the inbound fee charged at the receiving end of that same channel.

For example in the example below, _channel total fee_ is -2 (negative) but _node total fee_ is 1 (positive).

`[A] out: 5 ---> in: -7 [B] out: 8 --->`

In #6703, a protection is implemented so that nodes only forward when _node total fee_ is non-negative.

Pathfinding however is a channel-based search. Each round the route is extended with another channel based on the _channel total fee_. Negative _channel total fees_ are already treated as being zero, to prevent nodes from making themselves infinitely attractive by means of a deeply negative fee.

When a best route has been found however, as second pass is going to redo the fees and take advantage of any negative fees that might have been rounded up to zero during search.
bitromortac: > Afaik when the node with a high inbound discount is not delivering, it is penalized as part of a pair of nodes. Do you think that is insufficient?

Right, but it wouldn't have an effect on the inbound fee node's reputation as only the outgoing pairs count for that (there would be only incoming info in the scenario here), if I understand correctly. An alternative would be to also fail the reverse direction should (outbound fee + inbound fee) < threshold, in case of a temporary channel failure. The threshold could be dependent on the outbound fee, perhaps half of it?

> One thing to keep in mind is that there are two definitions of the 'total fee'

Great point, thanks for the clarification, I was aware that there are two ways to compute a fee, but not 100% aware that the pathfinder uses the total channel fee as opposed to route construction where the node total fee is used. 

> I think it would be safer for people to experiment with if negative fees were scoped out so that no net negative possibility was allowed - lower bound on a fee would be zero basically, this kind of thing could also be added in the proto comments or somewhere to tell people how to play with it

Just wanted to recap, so it makes sense to limit the node total fees to zero as a safety measure on the forwarding side, which is already the case in the other PR. On the sender side here, only the total channel fees are limited to zero, because a way to deal with negative fees is not obvious (and nodes shouldn't be able to make them too attractive).

This can lead to routes that exhibit negative node total fees if the inbound discounts are not capped as mentioned, which leads to routing failures. The sender doesn't know whether the router allows negative fees, so the sender would be more successful if it always constructs routes with non-negative total node fees. On the other hand, a sender can upgrade any time (and there are different implementations) and once they figure out how they want to exploit negative fees they could opt into that if routers allow for it. This looks like routers would need to signal that they allow negative fees, which then could be used in route construction to decide on whether node total fees should be capped or not?

joostjager: > > Afaik when the node with a high inbound discount is not delivering, it is penalized as part of a pair of nodes. Do you think that is insufficient?
> 
> Right, but it wouldn't have an effect on the inbound fee node's reputation as only the outgoing pairs count for that (there would be only incoming info in the scenario here), if I understand correctly. An alternative would be to also fail the reverse direction should (outbound fee + inbound fee) < threshold, in case of a temporary channel failure. The threshold could be dependent on the outbound fee, perhaps half of it?

In the scenario that we are talking about, the node with the high inbound discount is malicious. But a malicious node is - also without inbound fees - able to direct a penalty to either its incoming or outgoing side depending on the type of failure that it returns.

I don't fully understand what you mean by reverse direction and how a threshold comes into play. I think there is a case to be made for stronger penalization, but that this case is pre-existing. In fact, when building the current penalization scheme, there also was a variant with undirected pair penalties. 

> Just wanted to recap, so it makes sense to limit the node total fees to zero as a safety measure on the forwarding side, which is already the case in the other PR. On the sender side here, only the total channel fees are limited to zero, because a way to deal with negative fees is not obvious (and nodes shouldn't be able to make them too attractive).
> 
> This can lead to routes that exhibit negative node total fees if the inbound discounts are not capped as mentioned, which leads to routing failures. The sender doesn't know whether the router allows negative fees, so the sender would be more successful if it always constructs routes with non-negative total node fees. On the other hand, a sender can upgrade any time (and there are different implementations) and once they figure out how they want to exploit negative fees they could opt into that if routers allow for it. This looks like routers would need to signal that they allow negative fees, which then could be used in route construction to decide on whether node total fees should be capped or not?

I think it is worth going back to the starting point with this. The cap in the other PR was added to prevent routing node operators from accidentally losing money on forwards because of misconfiguration. It is implemented as part of the forwarding logic, but it could also have been part of the policy update logic. Or even just been enforced externally by node mgmt tools.

In the context of this PR, we are discussing adding even more protection for node operators so that in the case that they made a configuration error, they will not only not lose money, but also that senders are adapting to their configuration error by increasing the fee. With this, there is no reason for routing nodes to worry about those config errors anymore. And indeed, if a routing node operator does want a truly negative fee, they'd need to signal.

Zooming out, it feels that all of this is going into the direction of a complex solution for a simple problem. If you are concerned about the footgun, I think it is better to go back to #6703 and fix the update policy logic so that there can never be a combination of in and out channel that makes for a negative total fee.

bitromortac: > In the scenario that we are talking about, the node with the high inbound discount is malicious. But a malicious node is - also without inbound fees - able to direct a penalty to either its incoming or outgoing side depending on the type of failure that it returns.
> 
> I don't fully understand what you mean by reverse direction and how a threshold comes into play. I think there is a case to be made for stronger penalization, but that this case is pre-existing. In fact, when building the current penalization scheme, there also was a variant with undirected pair penalties.

Sorry, I should have been clearer, I was thinking about scenario https://github.com/lightningnetwork/lnd/pull/6703#issuecomment-1797918626. The channel A-B is depleted, A charges high fees to disable the channel, B discounts the channel for whatever reason and this leads the total channel fee to be small. Without inbound fees, the channel would not see any traffic, but with the inbound fees, B is able to attract traffic. The failing pair is attributed to the node pair A->B (because A fails back due to missing liquidity), which influences A's node reputation because it's outgoing from A, but not B's node reputation (if I understand the code correctly). I wonder if we could additionally attribute a failure to B->A in order to worsen B's reputation as well, because it was the culprit of the failure. The question is when to do this, it should probably depend on the relative sizes of the inbound and outbound fees.

> I think it is worth going back to the starting point with this. The cap in the other PR was added to prevent routing node operators from accidentally losing money on forwards because of misconfiguration. It is implemented as part of the forwarding logic, but it could also have been part of the policy update logic. Or even just been enforced externally by node mgmt tools.

So there are two options, the first is that the forwarder doesn't allow forwarding of negative fees. If they want to support negative fees in the future, they would need to signal it via a node feature bit such that senders can exploit it. Without this signaling it makes sense to disable negative fee route construction here, because otherwise there is a possibility that routes get rejected (the motivation was not to protect routing nodes). The second option is to enable negative fees from the start, but it needs the crosschecks you mentioned, but this would enable negative fees already.

> Zooming out, it feels that all of this is going into the direction of a complex solution for a simple problem. If you are concerned about the footgun, I think it is better to go back to https://github.com/lightningnetwork/lnd/pull/6703 and fix the update policy logic so that there can never be a combination of in and out channel that makes for a negative total fee. Something like https://github.com/lightningnetwork/lnd/commit/43cfd243cd6b7079dc2f1c9ae2088350911cda55

Not sure which way is best. Default channel open fees would also need to be taken care of, right? It feels like it is safer to have an explicit check in the switch than relying on the policy state, but it's also great to have negative fees available from the start.
joostjager: > Sorry, I should have been clearer, I was thinking about scenario [#6703 (comment)](https://github.com/lightningnetwork/lnd/pull/6703#issuecomment-1797918626). The channel A-B is depleted, A charges high fees to disable the channel, B discounts the channel for whatever reason and this leads the total channel fee to be small. Without inbound fees, the channel would not see any traffic, but with the inbound fees, B is able to attract traffic. The failing pair is attributed to the node pair A->B (because A fails back due to missing liquidity), which influences A's node reputation because it's outgoing from A, but not B's node reputation (if I understand the code correctly). I wonder if we could additionally attribute a failure to B->A in order to worsen B's reputation as well, because it was the culprit of the failure. The question is when to do this, it should probably depend on the relative sizes of the inbound and outbound fees.

Ah, you are talking about [node probability](https://github.com/lightningnetwork/lnd/blob/d9b88fba67a91583227d1d986deaa05177585bb1/routing/probability_apriori.go#L180) specifically, where pair results are extrapolated to a global node probability? Because the pair penalty on its own is probably not a problem as A might not want to do business with B anyway?

Btw, why would A charge high fees to disable a channel instead of actually disabling it? With high fees, there is still the risk of someone using it and penalizing.

> Not sure which way is best. Default channel open fees would also need to be taken care of, right? It feels like it is safer to have an explicit check in the switch than relying on the policy state, but it's also great to have negative fees available from the start.

Hmm good point. Those default fees make things complicated again. Let's go for disabling negative fees all the way then indeed. I've tacked on a commit that also updates pathfinding to put a floor on _node total fee_ during search.
bitromortac: > Ah, you are talking about [node probability](https://github.com/lightningnetwork/lnd/blob/d9b88fba67a91583227d1d986deaa05177585bb1/routing/probability_apriori.go#L180) specifically, where pair results are extrapolated to a global node probability? Because the pair penalty on its own is probably not a problem as A might not want to do business with B anyway?

Right, I was thinking about the node probability, which effectively is used as a kind of reputation or deterrence against misbehavior. Do you mean that there's no disadvantage for A if the B->A pair is failed as well?

> Btw, why would A charge high fees to disable a channel instead of actually disabling it? With high fees, there is still the risk of someone using it and penalizing.

I see this rather as a continuous process, because ramping up the fee rate goes in hand with increased traffic and whether there's liquidity left, leftovers can still be used at a higher rate, if there's high demand for it, but statistically the channel should get discouraged. Disabling the channel also is a binary process, so one would have to define a fraction at which a channel gets disabled. Also, disabling is often used as a heuristic to judge if some node signals that their channel partner is down.

> With this new addition, maybe your first point is also addressed? The node total fee is now always non-negative in pathfinding, so any kind of mega discount needs to be matched with an equally big outbound fee. That reduces the extent to which a node can make itself attractive to what they can already do today with zero fees?

Route reliability is increased with this :+1:, but I need to check if there are other consequences.
joostjager: >Do you mean that there's no disadvantage for A if the B->A pair is failed as well?

No, that wasn't what I meant. Just that penalizing A->B (ignoring the node reputation for now) affects A in that they will have less traffic going to B, but they probably don't care if B is a bad node.

Penalizing B->A will affect A as well for that specific link, and indeed, you could argue that it doesn't matter because B is malicious.

> I see this rather as a continuous process, because ramping up the fee rate goes in hand with increased traffic and whether there's liquidity left, leftovers can still be used at a higher rate, if there's high demand for it, but statistically the channel should get discouraged. Disabling the channel also is a binary process, so one would have to define a fraction at which a channel gets disabled. Also, disabling is often used as a heuristic to judge if some node signals that their channel partner is down.

But if there is still liquidity left, why wouldn't A want senders to use it? If B makes it more attractive and more likely for A to earn that high fee, I don't really see the downside. I think there is a speculative component here in how the dynamics will work out exactly. I do not oppose a bidirectional penalty, but I wouldn't want to make a change that affects every existing channel too as part of this PR.

> > With this new addition, maybe your first point is also addressed? The node total fee is now always non-negative in pathfinding, so any kind of mega discount needs to be matched with an equally big outbound fee. That reduces the extent to which a node can make itself attractive to what they can already do today with zero fees?
> 
> Route reliability is increased with this 👍, but I need to check if there are other consequences. Also, do we want to already define a flag for nodes to signal to support negative fees?

I don't see the need to define the flag if we don't use it yet. And may never do.
lightninglabs-deploy: @bitromortac: review reminder
@joostjager, remember to re-request review from reviewers when ready
joostjager: Added an evaluatory commit that shows channel-based pathfinding to avoid any recognized or unknown side effects of negative inbound fees.
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
joostjager: Rebased
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
lightninglabs-deploy: @joostjager, remember to re-request review from reviewers when ready
Roasbeef: Needs rebase + conflicts addressed. 

Patch:
diff --git a/channeldb/graph.go b/channeldb/graph.go
index 8ad90f808..2c000f3e7 100644
--- a/channeldb/graph.go
+++ b/channeldb/graph.go
@@ -490,6 +490,16 @@ func (c *ChannelGraph) ForEachNodeDirectedChannel(tx kvdb.RTx,
 			cachedInPolicy.ToNodeFeatures = toNodeFeatures
 		}
 
+		var inboundFee lnwire.Fee
+		if p1 != nil {
+			// Extract inbound fee. If there is a decoding error,
+			// skip this edge.
+			_, err := p1.ExtraOpaqueData.ExtractRecords(&inboundFee)
+			if err != nil {
+				return nil
+			}
+		}
+
 		directedChannel := &DirectedChannel{
 			ChannelID:    e.ChannelID,
 			IsNode1:      node == e.NodeKey1Bytes,
@@ -497,6 +507,7 @@ func (c *ChannelGraph) ForEachNodeDirectedChannel(tx kvdb.RTx,
 			Capacity:     e.Capacity,
 			OutPolicySet: p1 != nil,
 			InPolicy:     cachedInPolicy,
+			InboundFee:   inboundFee,
 		}
 
 		if node == e.NodeKey2Bytes {
diff --git a/channeldb/graph_cache.go b/channeldb/graph_cache.go
index 7bf9c41d9..9bd2a8265 100644
--- a/channeldb/graph_cache.go
+++ b/channeldb/graph_cache.go
@@ -59,6 +59,9 @@ type DirectedChannel struct {
 	// source, so we're always interested in the edge that arrives to us
 	// from the other node.
 	InPolicy *models.CachedEdgePolicy
+
+	// Inbound fees of this node.
+	InboundFee lnwire.Fee
 }
 
 // DeepCopy creates a deep copy of the channel, including the incoming policy.
@@ -220,6 +223,14 @@ func (c *GraphCache) updateOrAddEdge(node route.Vertex, edge *DirectedChannel) {
 func (c *GraphCache) UpdatePolicy(policy *models.ChannelEdgePolicy, fromNode,
 	toNode route.Vertex, edge1 bool) {
 
+	// Extract inbound fee if possible and available. If there is a decoding
+	// error, ignore this policy.
+	var inboundFee lnwire.Fee
+	_, err := policy.ExtraOpaqueData.ExtractRecords(&inboundFee)
+	if err != nil {
+		return
+	}
+
 	c.mtx.Lock()
 	defer c.mtx.Unlock()
 
@@ -240,11 +251,13 @@ func (c *GraphCache) UpdatePolicy(policy *models.ChannelEdgePolicy, fromNode,
 		// policy for node 1.
 		case channel.IsNode1 && edge1:
 			channel.OutPolicySet = true
+			channel.InboundFee = inboundFee
 
 		// This is node 2, and it is edge 2, so this is the outgoing
 		// policy for node 2.
 		case !channel.IsNode1 && !edge1:
 			channel.OutPolicySet = true
+			channel.InboundFee = inboundFee
 
 		// The other two cases left mean it's the inbound policy for the
 		// node.
diff --git a/docs/release-notes/release-notes-0.18.0.md b/docs/release-notes/release-notes-0.18.0.md
index 28ae7dc4e..6f13bb41c 100644
--- a/docs/release-notes/release-notes-0.18.0.md
+++ b/docs/release-notes/release-notes-0.18.0.md
@@ -117,9 +117,8 @@
   node operators to require senders to pay an inbound fee for forwards and
   payments. It is recommended to only use negative fees (an inbound "discount")
   initially to keep the channels open for senders that do not recognize inbound
-  fees. In this release, no send support for pathfinding and route building is
-  added yet. We first want to learn more about the impact that inbound fees have
-  on the routing economy.
+  fees. [Send support](https://github.com/lightningnetwork/lnd/pull/6934) is
+  implemented as well.
 
 * A new config value,
   [sweeper.maxfeerate](https://github.com/lightningnetwork/lnd/pull/7823), is
diff --git a/routing/graph.go b/routing/graph.go
index 7f344f54a..3e466a3df 100644
--- a/routing/graph.go
+++ b/routing/graph.go
@@ -103,7 +103,10 @@ func (g *CachedGraph) FetchAmountPairCapacity(nodeFrom, nodeTo route.Vertex,
 	amount lnwire.MilliSatoshi) (btcutil.Amount, error) {
 
 	// Create unified edges for all incoming connections.
-	u := newNodeEdgeUnifier(g.sourceNode(), nodeTo, nil)
+	//
+	// Note: Inbound fees are not used here because this method is only used
+	// by a deprecated router rpc.
+	u := newNodeEdgeUnifier(g.sourceNode(), nodeTo, false, nil)
 
 	err := u.addGraphPolicies(g)
 	if err != nil {
@@ -116,7 +119,7 @@ func (g *CachedGraph) FetchAmountPairCapacity(nodeFrom, nodeTo route.Vertex,
 			nodeFrom, nodeTo)
 	}
 
-	edge := edgeUnifier.getEdgeNetwork(amount)
+	edge := edgeUnifier.getEdgeNetwork(amount, 0)
 	if edge == nil {
 		return 0, fmt.Errorf("no edge for node pair %v -> %v "+
 			"(amount %v)", nodeFrom, nodeTo, amount)
diff --git a/routing/heap.go b/routing/heap.go
index 261ced8f9..a4c0411d5 100644
--- a/routing/heap.go
+++ b/routing/heap.go
@@ -3,7 +3,6 @@ package routing
 import (
 	"container/heap"
 
-	"github.com/lightningnetwork/lnd/channeldb/models"
 	"github.com/lightningnetwork/lnd/lnwire"
 	"github.com/lightningnetwork/lnd/routing/route"
 )
@@ -19,10 +18,16 @@ type nodeWithDist struct {
 	// outgoing edges (channels) emanating from a node.
 	node route.Vertex
 
-	// amountToReceive is the amount that should be received by this node.
+	// netAmountReceived is the amount that should be received by this node.
 	// Either as final payment to the final node or as an intermediate
-	// amount that includes also the fees for subsequent hops.
-	amountToReceive lnwire.MilliSatoshi
+	// amount that includes also the fees for subsequent hops. This node's
+	// inbound fee is already subtracted from the htlc amount - if
+	// applicable.
+	netAmountReceived lnwire.MilliSatoshi
+
+	// outboundFee is the fee that this node charges on the outgoing
+	// channel.
+	outboundFee lnwire.MilliSatoshi
 
 	// incomingCltv is the expected absolute expiry height for the incoming
 	// htlc of this node. This value should already include the final cltv
@@ -39,7 +44,7 @@ type nodeWithDist struct {
 	weight int64
 
 	// nextHop is the edge this route comes from.
-	nextHop *models.CachedEdgePolicy
+	nextHop *unifiedEdge
 
 	// routingInfoSize is the total size requirement for the payloads field
 	// in the onion packet from this hop towards the final destination.
diff --git a/routing/pathfind.go b/routing/pathfind.go
index 53eb0dfb4..add833ecc 100644
--- a/routing/pathfind.go
+++ b/routing/pathfind.go
@@ -50,7 +50,7 @@ const (
 type pathFinder = func(g *graphParams, r *RestrictParams,
 	cfg *PathFindingConfig, source, target route.Vertex,
 	amt lnwire.MilliSatoshi, timePref float64, finalHtlcExpiry int32) (
-	[]*models.CachedEdgePolicy, float64, error)
+	[]*unifiedEdge, float64, error)
 
 var (
 	// DefaultEstimator is the default estimator used for computing
@@ -119,14 +119,14 @@ type finalHopParams struct {
 // makes calculating the totals during route construction difficult if we
 // include blinded paths on the first pass).
 //
-// NOTE: The passed slice of ChannelHops MUST be sorted in forward order: from
+// NOTE: The passed slice of unified edges MUST be sorted in forward order: from
 // the source to the target node of the path finding attempt. It is assumed that
 // any feature vectors on all hops have been validated for transitive
 // dependencies.
 // NOTE: If a non-nil blinded path is provided it is assumed to have been
 // validated by the caller.
 func newRoute(sourceVertex route.Vertex,
-	pathEdges []*models.CachedEdgePolicy, currentHeight uint32,
+	pathEdges []*unifiedEdge, currentHeight uint32,
 	finalHop finalHopParams, blindedPath *sphinx.BlindedPath) (
 	*route.Route, error) {
 
@@ -149,7 +149,7 @@ func newRoute(sourceVertex route.Vertex,
 	for i := pathLength - 1; i >= 0; i-- {
 		// Now we'll start to calculate the items within the per-hop
 		// payload for the hop this edge is leading to.
-		edge := pathEdges[i]
+		edge := pathEdges[i].policy
 
 		// We'll calculate the amounts, timelocks, and fees for each hop
 		// in the route. The base case is the final hop which includes
@@ -158,7 +158,7 @@ func newRoute(sourceVertex route.Vertex,
 		// we compute the route in reverse.
 		var (
 			amtToForward        lnwire.MilliSatoshi
-			fee                 lnwire.MilliSatoshi
+			fee                 int64
 			totalAmtMsatBlinded lnwire.MilliSatoshi
 			outgoingTimeLock    uint32
 			tlvPayload          bool
@@ -196,7 +196,7 @@ func newRoute(sourceVertex route.Vertex,
 
 			// Fee is not part of the hop payload, but only used for
 			// reporting through RPC. Set to zero for the final hop.
-			fee = lnwire.MilliSatoshi(0)
+			fee = 0
 
 			// As this is the last hop, we'll use the specified
 			// final CLTV delta value instead of the value from the
@@ -245,13 +245,26 @@ func newRoute(sourceVertex route.Vertex,
 			// and its policy for the outgoing channel. This policy
 			// is stored as part of the incoming channel of
 			// the next hop.
-			fee = pathEdges[i+1].ComputeFee(amtToForward)
+			outboundFee := pathEdges[i+1].policy.ComputeFee(
+				amtToForward,
+			)
+
+			inboundFee := pathEdges[i].inboundFees.CalcFee(
+				amtToForward + outboundFee,
+			)
+
+			fee = int64(outboundFee) + inboundFee
+			if fee < 0 {
+				fee = 0
+			}
 
 			// We'll take the total timelock of the preceding hop as
 			// the outgoing timelock or this hop. Then we'll
 			// increment the total timelock incurred by this hop.
 			outgoingTimeLock = totalTimeLock
-			totalTimeLock += uint32(pathEdges[i+1].TimeLockDelta)
+			totalTimeLock += uint32(
+				pathEdges[i+1].policy.TimeLockDelta,
+			)
 		}
 
 		// Since we're traversing the path backwards atm, we prepend
@@ -274,7 +287,7 @@ func newRoute(sourceVertex route.Vertex,
 		// Finally, we update the amount that needs to flow into the
 		// *next* hop, which is the amount this hop needs to forward,
 		// accounting for the fee that it takes.
-		nextIncomingAmount = amtToForward + fee
+		nextIncomingAmount = amtToForward + lnwire.MilliSatoshi(fee)
 	}
 
 	// If we are creating a route to a blinded path, we need to add some
@@ -504,7 +517,7 @@ func getOutgoingBalance(node route.Vertex, outgoingChans map[uint64]struct{},
 // available bandwidth.
 func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 	source, target route.Vertex, amt lnwire.MilliSatoshi, timePref float64,
-	finalHtlcExpiry int32) ([]*models.CachedEdgePolicy, float64, error) {
+	finalHtlcExpiry int32) ([]*unifiedEdge, float64, error) {
 
 	// Pathfinding can be a significant portion of the total payment
 	// latency, especially on low-powered devices. Log several metrics to
@@ -659,13 +672,13 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 	// Don't record the initial partial path in the distance map and reserve
 	// that key for the source key in the case we route to ourselves.
 	partialPath := &nodeWithDist{
-		dist:            0,
-		weight:          0,
-		node:            target,
-		amountToReceive: amt,
-		incomingCltv:    finalHtlcExpiry,
-		probability:     1,
-		routingInfoSize: lastHopPayloadSize,
+		dist:              0,
+		weight:            0,
+		node:              target,
+		netAmountReceived: amt,
+		incomingCltv:      finalHtlcExpiry,
+		probability:       1,
+		routingInfoSize:   lastHopPayloadSize,
 	}
 
 	// Calculate the absolute cltv limit. Use uint64 to prevent an overflow
@@ -702,9 +715,27 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 
 		edgesExpanded++
 
+		// Calculate inbound fee charged by "to" node. The exit hop
+		// doesn't charge inbound fees. If the "to" node is the exit
+		// hop, its inbound fees have already been set to zero by
+		// nodeEdgeUnifier.
+		inboundFee := edge.inboundFees.CalcFee(
+			toNodeDist.netAmountReceived,
+		)
+
+		// Make sure that the node total fee is never negative.
+		// Routing nodes treat a total fee that turns out
+		// negative as a zero fee and pathfinding should do the
+		// same.
+		minInboundFee := -int64(toNodeDist.outboundFee)
+		if inboundFee < minInboundFee {
+			inboundFee = minInboundFee
+		}
+
 		// Calculate amount that the candidate node would have to send
 		// out.
-		amountToSend := toNodeDist.amountToReceive
+		amountToSend := toNodeDist.netAmountReceived +
+			lnwire.MilliSatoshi(inboundFee)
 
 		// Request the success probability for this edge.
 		edgeProbability := r.ProbabilitySource(
@@ -734,10 +765,15 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		// Also determine the time lock delta that will be added to the
 		// route if fromVertex is selected. If fromVertex is the source
 		// node, no additional timelock is required.
-		var fee lnwire.MilliSatoshi
-		var timeLockDelta uint16
+		var (
+			timeLockDelta uint16
+			outboundFee   int64
+		)
+
 		if fromVertex != source {
-			fee = edge.policy.ComputeFee(amountToSend)
+			outboundFee = int64(
+				edge.policy.ComputeFee(amountToSend),
+			)
 			timeLockDelta = edge.policy.TimeLockDelta
 		}
 
@@ -748,17 +784,19 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 			return
 		}
 
-		// amountToReceive is the amount that the node that is added to
-		// the distance map needs to receive from a (to be found)
-		// previous node in the route. That previous node will need to
-		// pay the amount that this node forwards plus the fee it
-		// charges.
-		amountToReceive := amountToSend + fee
+		// netAmountToReceive is the amount that the node that is added
+		// to the distance map needs to receive from a (to be found)
+		// previous node in the route. The inbound fee of the receiving
+		// node is already subtracted from this value. The previous node
+		// will need to pay the amount that this node forwards plus the
+		// fee it charges plus this node's inbound fee.
+		netAmountToReceive := amountToSend +
+			lnwire.MilliSatoshi(outboundFee)
 
 		// Check if accumulated fees would exceed fee limit when this
 		// node would be added to the path.
-		totalFee := amountToReceive - amt
-		if totalFee > r.FeeLimit {
+		totalFee := int64(netAmountToReceive) - int64(amt)
+		if totalFee > 0 && lnwire.MilliSatoshi(totalFee) > r.FeeLimit {
 			return
 		}
 
@@ -774,11 +812,21 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 			return
 		}
 
+		// Calculate the combined fee for this edge. Dijkstra does not
+		// support negative edge weights. Because this fee feeds into
+		// the edge weight calculation, we don't allow it to be
+		// negative.
+		signedFee := inboundFee + outboundFee
+		fee := lnwire.MilliSatoshi(0)
+		if signedFee > 0 {
+			fee = lnwire.MilliSatoshi(signedFee)
+		}
+
 		// By adding fromVertex in the route, there will be an extra
 		// 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(amountToReceive, fee, timeLockDelta)
+		weight := edgeWeight(netAmountToReceive, fee, timeLockDelta)
 
 		// Compute the tentative weight to this new channel/edge
 		// which is the weight from our toNode to the target node
@@ -786,7 +834,10 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		tempWeight := toNodeDist.weight + weight
 
 		// Add an extra factor to the weight to take into account the
-		// probability.
+		// probability. Another reason why we rounded the fee up to zero
+		// is to prevent a highly negative fee from cancelling out the
+		// extra factor. We don't want an always-failing node to attract
+		// traffic using a highly negative fee and escape penalization.
 		tempDist := getProbabilityBasedDist(
 			tempWeight, probability,
 			absoluteAttemptCost,
@@ -853,14 +904,15 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		// The new better distance is recorded, and also our "next hop"
 		// map is populated with this edge.
 		withDist := &nodeWithDist{
-			dist:            tempDist,
-			weight:          tempWeight,
-			node:            fromVertex,
-			amountToReceive: amountToReceive,
-			incomingCltv:    incomingCltv,
-			probability:     probability,
-			nextHop:         edge.policy,
-			routingInfoSize: routingInfoSize,
+			dist:              tempDist,
+			weight:            tempWeight,
+			node:              fromVertex,
+			netAmountReceived: netAmountToReceive,
+			outboundFee:       lnwire.MilliSatoshi(outboundFee),
+			incomingCltv:      incomingCltv,
+			probability:       probability,
+			nextHop:           edge,
+			routingInfoSize:   routingInfoSize,
 		}
 		distance[fromVertex] = withDist
 
@@ -919,9 +971,13 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		nodesVisited++
 
 		pivot := partialPath.node
+		isExitHop := partialPath.nextHop == nil
 
-		// Create unified edges for all incoming connections.
-		u := newNodeEdgeUnifier(self, pivot, outgoingChanMap)
+		// Create unified policies for all incoming connections. Don't
+		// use inbound fees for the exit hop.
+		u := newNodeEdgeUnifier(
+			self, pivot, !isExitHop, outgoingChanMap,
+		)
 
 		err := u.addGraphPolicies(g.graph)
 		if err != nil {
@@ -930,6 +986,11 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 
 		// We add hop hints that were supplied externally.
 		for _, reverseEdge := range additionalEdgesWithSrc[pivot] {
+			// Assume zero inbound fees for route hints. If inbound
+			// fees would apply, they couldn't be communicated in
+			// bolt11 invoices currently.
+			inboundFee := models.InboundFee{}
+
 			// Hop hints don't contain a capacity. We set one here,
 			// since a capacity is needed for probability
 			// calculations. We set a high capacity to act as if
@@ -941,12 +1002,13 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 			u.addPolicy(
 				reverseEdge.sourceNode,
 				reverseEdge.edge.EdgePolicy(),
+				inboundFee,
 				fakeHopHintCapacity,
 				reverseEdge.edge.IntermediatePayloadSize,
 			)
 		}
 
-		amtToSend := partialPath.amountToReceive
+		netAmountReceived := partialPath.netAmountReceived
 
 		// Expand all connections using the optimal policy for each
 		// connection.
@@ -968,7 +1030,8 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 			}
 
 			edge := edgeUnifier.getEdge(
-				amtToSend, g.bandwidthHints,
+				netAmountReceived, g.bandwidthHints,
+				partialPath.outboundFee,
 			)
 
 			if edge == nil {
@@ -1009,7 +1072,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 
 	// Use the distance map to unravel the forward path from source to
 	// target.
-	var pathEdges []*models.CachedEdgePolicy
+	var pathEdges []*unifiedEdge
 	currentNode := source
 	for {
 		// Determine the next hop forward using the next map.
@@ -1024,7 +1087,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 		pathEdges = append(pathEdges, currentNodeWithDist.nextHop)
 
 		// Advance current node.
-		currentNode = currentNodeWithDist.nextHop.ToNodePubKey()
+		currentNode = currentNodeWithDist.nextHop.policy.ToNodePubKey()
 
 		// Check stop condition at the end of this loop. This prevents
 		// breaking out too soon for self-payments that have target set
@@ -1045,11 +1108,11 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 	// route construction does not care where the features are actually
 	// taken from. In the future we may wish to do route construction within
 	// findPath, and avoid using ChannelEdgePolicy altogether.
-	pathEdges[len(pathEdges)-1].ToNodeFeatures = features
+	pathEdges[len(pathEdges)-1].policy.ToNodeFeatures = features
 
 	log.Debugf("Found route: probability=%v, hops=%v, fee=%v",
 		distance[source].probability, len(pathEdges),
-		distance[source].amountToReceive-amt)
+		distance[source].netAmountReceived-amt)
 
 	return pathEdges, distance[source].probability, nil
 }
diff --git a/routing/router.go b/routing/router.go
index 699ee9a33..04502d49b 100644
--- a/routing/router.go
+++ b/routing/router.go
@@ -3161,9 +3161,13 @@ func getRouteUnifiers(source route.Vertex, hops []route.Vertex,
 
 		localChan := i == 0
 
-		// Build unified edges for this hop based on the channels known
-		// in the graph.
-		u := newNodeEdgeUnifier(source, toNode, outgoingChans)
+		// Build unified policies for this hop based on the channels
+		// known in the graph. Don't use inbound fees.
+		//
+		// TODO: Add inbound fees support for BuildRoute.
+		u := newNodeEdgeUnifier(
+			source, toNode, false, outgoingChans,
+		)
 
 		err := u.addGraphPolicies(graph)
 		if err != nil {
@@ -3189,7 +3193,7 @@ func getRouteUnifiers(source route.Vertex, hops []route.Vertex,
 		}
 
 		// Get an edge for the specific amount that we want to forward.
-		edge := edgeUnifier.getEdge(runningAmt, bandwidthHints)
+		edge := edgeUnifier.getEdge(runningAmt, bandwidthHints, 0)
 		if edge == nil {
 			log.Errorf("Cannot find policy with amt=%v for node %v",
 				runningAmt, fromNode)
@@ -3218,16 +3222,16 @@ func getRouteUnifiers(source route.Vertex, hops []route.Vertex,
 // including fees, to send the payment.
 func getPathEdges(source route.Vertex, receiverAmt lnwire.MilliSatoshi,
 	unifiers []*edgeUnifier, bandwidthHints *bandwidthManager,
-	hops []route.Vertex) ([]*models.CachedEdgePolicy,
+	hops []route.Vertex) ([]*unifiedEdge,
 	lnwire.MilliSatoshi, error) {
 
 	// Now that we arrived at the start of the route and found out the route
 	// total amount, we make a forward pass. Because the amount may have
 	// been increased in the backward pass, fees need to be recalculated and
 	// amount ranges re-checked.
-	var pathEdges []*models.CachedEdgePolicy
+	var pathEdges []*unifiedEdge
 	for i, unifier := range unifiers {
-		edge := unifier.getEdge(receiverAmt, bandwidthHints)
+		edge := unifier.getEdge(receiverAmt, bandwidthHints, 0)
 		if edge == nil {
 			fromNode := source
 			if i > 0 {
@@ -3247,7 +3251,7 @@ func getPathEdges(source route.Vertex, receiverAmt lnwire.MilliSatoshi,
 			)
 		}
 
-		pathEdges = append(pathEdges, edge.policy)
+		pathEdges = append(pathEdges, edge)
 	}
 
 	return pathEdges, receiverAmt, nil
diff --git a/routing/unified_edges.go b/routing/unified_edges.go
index c828e9a6e..44efc6314 100644
--- a/routing/unified_edges.go
+++ b/routing/unified_edges.go
@@ -1,6 +1,8 @@
 package routing
 
 import (
+	"math"
+
 	"github.com/btcsuite/btcd/btcutil"
 	"github.com/lightningnetwork/lnd/channeldb"
 	"github.com/lightningnetwork/lnd/channeldb/models"
@@ -21,6 +23,9 @@ type nodeEdgeUnifier struct {
 	// toNode is the node for which the edge unifiers are instantiated.
 	toNode route.Vertex
 
+	// useInboundFees indicates whether to take inbound fees into account.
+	useInboundFees bool
+
 	// outChanRestr is an optional outgoing channel restriction for the
 	// local channel to use.
 	outChanRestr map[uint64]struct{}
@@ -28,14 +33,15 @@ type nodeEdgeUnifier struct {
 
 // newNodeEdgeUnifier instantiates a new nodeEdgeUnifier object. Channel
 // policies can be added to this object.
-func newNodeEdgeUnifier(sourceNode, toNode route.Vertex,
+func newNodeEdgeUnifier(sourceNode, toNode route.Vertex, useInboundFees bool,
 	outChanRestr map[uint64]struct{}) *nodeEdgeUnifier {
 
 	return &nodeEdgeUnifier{
-		edgeUnifiers: make(map[route.Vertex]*edgeUnifier),
-		toNode:       toNode,
-		sourceNode:   sourceNode,
-		outChanRestr: outChanRestr,
+		edgeUnifiers:   make(map[route.Vertex]*edgeUnifier),
+		toNode:         toNode,
+		useInboundFees: useInboundFees,
+		sourceNode:     sourceNode,
+		outChanRestr:   outChanRestr,
 	}
 }
 
@@ -44,8 +50,8 @@ func newNodeEdgeUnifier(sourceNode, toNode route.Vertex,
 // graceful shutdown if it is not provided as this indicates that edges are
 // incorrectly specified.
 func (u *nodeEdgeUnifier) addPolicy(fromNode route.Vertex,
-	edge *models.CachedEdgePolicy, capacity btcutil.Amount,
-	hopPayloadSizeFn PayloadSizeFunc) {
+	edge *models.CachedEdgePolicy, inboundFee models.InboundFee,
+	capacity btcutil.Amount, hopPayloadSizeFn PayloadSizeFunc) {
 
 	localChan := fromNode == u.sourceNode
 
@@ -75,10 +81,16 @@ func (u *nodeEdgeUnifier) addPolicy(fromNode route.Vertex,
 		return
 	}
 
+	// Zero inbound fee for exit hops.
+	if !u.useInboundFees {
+		inboundFee = models.InboundFee{}
+	}
+
 	unifier.edges = append(unifier.edges, &unifiedEdge{
 		policy:           edge,
 		capacity:         capacity,
 		hopPayloadSizeFn: hopPayloadSizeFn,
+		inboundFees:      inboundFee,
 	})
 }
 
@@ -97,9 +109,13 @@ func (u *nodeEdgeUnifier) addGraphPolicies(g routingGraph) error {
 		// to the clear hop payload size function because
 		// `addGraphPolicies` is only used for cleartext intermediate
 		// hops in a route.
+		inboundFee := models.NewInboundFeeFromWire(
+			channel.InboundFee,
+		)
+
 		u.addPolicy(
-			channel.OtherNode, channel.InPolicy, channel.Capacity,
-			defaultHopPayloadSize,
+			channel.OtherNode, channel.InPolicy, inboundFee,
+			channel.Capacity, defaultHopPayloadSize,
 		)
 
 		return nil
@@ -112,8 +128,9 @@ func (u *nodeEdgeUnifier) addGraphPolicies(g routingGraph) error {
 // unifiedEdge is the individual channel data that is kept inside an edgeUnifier
 // object.
 type unifiedEdge struct {
-	policy   *models.CachedEdgePolicy
-	capacity btcutil.Amount
+	policy      *models.CachedEdgePolicy
+	capacity    btcutil.Amount
+	inboundFees models.InboundFee
 
 	// hopPayloadSize supplies an edge with the ability to calculate the
 	// exact payload size if this edge would be included in a route. This
@@ -163,20 +180,41 @@ type edgeUnifier struct {
 // getEdge returns the optimal unified edge to use for this connection given a
 // specific amount to send. It differentiates between local and network
 // channels.
-func (u *edgeUnifier) getEdge(amt lnwire.MilliSatoshi,
-	bandwidthHints bandwidthHints) *unifiedEdge {
+func (u *edgeUnifier) getEdge(netAmtReceived lnwire.MilliSatoshi,
+	bandwidthHints bandwidthHints,
+	nextOutFee lnwire.MilliSatoshi) *unifiedEdge {
 
 	if u.localChan {
-		return u.getEdgeLocal(amt, bandwidthHints)
+		return u.getEdgeLocal(
+			netAmtReceived, bandwidthHints, nextOutFee,
+		)
 	}
 
-	return u.getEdgeNetwork(amt)
+	return u.getEdgeNetwork(netAmtReceived, nextOutFee)
+}
+
+// calcCappedInboundFee calculates the inbound fee for a channel, taking into
+// account the total node fee for the "to" node.
+func calcCappedInboundFee(edge *unifiedEdge, amt lnwire.MilliSatoshi,
+	nextOutFee lnwire.MilliSatoshi) int64 {
+
+	// Calculate the inbound fee charged for the amount that passes over the
+	// channel.
+	inboundFee := edge.inboundFees.CalcFee(amt)
+
+	// Take into account that the total node fee cannot be negative.
+	if inboundFee < -int64(nextOutFee) {
+		inboundFee = -int64(nextOutFee)
+	}
+
+	return inboundFee
 }
 
 // getEdgeLocal returns the optimal unified edge to use for this local
 // connection given a specific amount to send.
-func (u *edgeUnifier) getEdgeLocal(amt lnwire.MilliSatoshi,
-	bandwidthHints bandwidthHints) *unifiedEdge {
+func (u *edgeUnifier) getEdgeLocal(netAmtReceived lnwire.MilliSatoshi,
+	bandwidthHints bandwidthHints,
+	nextOutFee lnwire.MilliSatoshi) *unifiedEdge {
 
 	var (
 		bestEdge     *unifiedEdge
@@ -184,10 +222,20 @@ func (u *edgeUnifier) getEdgeLocal(amt lnwire.MilliSatoshi,
 	)
 
 	for _, edge := range u.edges {
+		// Calculate the inbound fee charged at the receiving node.
+		inboundFee := calcCappedInboundFee(
+			edge, netAmtReceived, nextOutFee,
+		)
+
+		// Add inbound fee to get to the amount that is sent over the
+		// local channel.
+		amt := netAmtReceived + lnwire.MilliSatoshi(inboundFee)
+
 		// Check valid amount range for the channel.
 		if !edge.amtInRange(amt) {
 			log.Debugf("Amount %v not in range for edge %v",
-				amt, edge.policy.ChannelID)
+				netAmtReceived, edge.policy.ChannelID)
+
 			continue
 		}
 
@@ -249,6 +297,7 @@ func (u *edgeUnifier) getEdgeLocal(amt lnwire.MilliSatoshi,
 			policy:           edge.policy,
 			capacity:         edge.capacity,
 			hopPayloadSizeFn: edge.hopPayloadSizeFn,
+			inboundFees:      edge.inboundFees,
 		}
 	}
 
@@ -259,16 +308,27 @@ func (u *edgeUnifier) getEdgeLocal(amt lnwire.MilliSatoshi,
 // given a specific amount to send. The goal is to return a unified edge with a
 // policy that maximizes the probability of a successful forward in a non-strict
 // forwarding context.
-func (u *edgeUnifier) getEdgeNetwork(amt lnwire.MilliSatoshi) *unifiedEdge {
+func (u *edgeUnifier) getEdgeNetwork(netAmtReceived lnwire.MilliSatoshi,
+	nextOutFee lnwire.MilliSatoshi) *unifiedEdge {
+
 	var (
-		bestPolicy       *models.CachedEdgePolicy
-		maxFee           lnwire.MilliSatoshi
+		bestPolicy       *unifiedEdge
+		maxFee           int64 = math.MinInt64
 		maxTimelock      uint16
 		maxCapMsat       lnwire.MilliSatoshi
 		hopPayloadSizeFn PayloadSizeFunc
 	)
 
 	for _, edge := range u.edges {
+		// Calculate the inbound fee charged at the receiving node.
+		inboundFee := calcCappedInboundFee(
+			edge, netAmtReceived, nextOutFee,
+		)
+
+		// Add inbound fee to get to the amount that is sent over the
+		// channel.
+		amt := netAmtReceived + lnwire.MilliSatoshi(inboundFee)
+
 		// Check valid amount range for the channel.
 		if !edge.amtInRange(amt) {
 			log.Debugf("Amount %v not in range for edge %v",
@@ -302,9 +362,12 @@ func (u *edgeUnifier) getEdgeNetwork(amt lnwire.MilliSatoshi) *unifiedEdge {
 		maxTimelock = lntypes.Max(
 			maxTimelock, edge.policy.TimeLockDelta,
 		)
+
+		outboundFee := int64(edge.policy.ComputeFee(amt))
+		fee := outboundFee + inboundFee
+
 		// Use the policy that results in the highest fee for this
 		// specific amount.
-		fee := edge.policy.ComputeFee(amt)
 		if fee < maxFee {
 			log.Debugf("Skipped edge %v due to it produces less "+
 				"fee: fee=%v, maxFee=%v",
@@ -314,7 +377,11 @@ func (u *edgeUnifier) getEdgeNetwork(amt lnwire.MilliSatoshi) *unifiedEdge {
 		}
 		maxFee = fee
 
-		bestPolicy = edge.policy
+		bestPolicy = &unifiedEdge{
+			policy:      edge.policy,
+			inboundFees: edge.inboundFees,
+		}
+
 		// The payload size function for edges to a connected peer is
 		// always the same hence there is not need to find the maximum.
 		// This also counts for blinded edges where we only have one
@@ -337,8 +404,11 @@ func (u *edgeUnifier) getEdgeNetwork(amt lnwire.MilliSatoshi) *unifiedEdge {
 	// get forwarded. Because we penalize pair-wise, there won't be a second
 	// chance for this node pair. But this is all only needed for nodes that
 	// have distinct policies for channels to the same peer.
-	policyCopy := *bestPolicy
-	modifiedEdge := unifiedEdge{policy: &policyCopy}
+	policyCopy := *bestPolicy.policy
+	modifiedEdge := unifiedEdge{
+		policy:      &policyCopy,
+		inboundFees: bestPolicy.inboundFees,
+	}
 	modifiedEdge.policy.TimeLockDelta = maxTimelock
 	modifiedEdge.capacity = maxCapMsat.ToSatoshis()
 	modifiedEdge.hopPayloadSizeFn = hopPayloadSizeFn


Test patch:
diff --git a/channeldb/graph_cache_test.go b/channeldb/graph_cache_test.go
index f2b0c52f9..f7ed5cee6 100644
--- a/channeldb/graph_cache_test.go
+++ b/channeldb/graph_cache_test.go
@@ -75,6 +75,10 @@ func TestGraphCacheAddNode(t *testing.T) {
 			ChannelID:    1000,
 			ChannelFlags: lnwire.ChanUpdateChanFlags(channelFlagA),
 			ToNode:       nodeB,
+			// Define an inbound fee.
+			ExtraOpaqueData: []byte{
+				253, 217, 3, 8, 0, 0, 0, 10, 0, 0, 0, 20,
+			},
 		}
 		inPolicy1 := &models.ChannelEdgePolicy{
 			ChannelID:    1000,
@@ -124,8 +128,18 @@ func TestGraphCacheAddNode(t *testing.T) {
 			edges map[uint64]*DirectedChannel) error {
 
 			nodes[node] = struct{}{}
-			for chanID := range edges {
+			for chanID, directedChannel := range edges {
 				chans[chanID] = struct{}{}
+
+				if node == nodeA {
+					require.NotZero(
+						t, directedChannel.InboundFee,
+					)
+				} else {
+					require.Zero(
+						t, directedChannel.InboundFee,
+					)
+				}
 			}
 
 			return nil
diff --git a/channeldb/graph_test.go b/channeldb/graph_test.go
index 8fe90c545..717b99fd1 100644
--- a/channeldb/graph_test.go
+++ b/channeldb/graph_test.go
@@ -674,7 +674,7 @@ func createChannelEdge(db kvdb.Backend, node1, node2 *LightningNode) (
 		FeeBaseMSat:               4352345,
 		FeeProportionalMillionths: 3452352,
 		ToNode:                    secondNode,
-		ExtraOpaqueData:           []byte("new unknown feature2"),
+		ExtraOpaqueData:           []byte{1, 0},
 	}
 	edge2 := &models.ChannelEdgePolicy{
 		SigBytes:                  testSig.Serialize(),
@@ -688,7 +688,7 @@ func createChannelEdge(db kvdb.Backend, node1, node2 *LightningNode) (
 		FeeBaseMSat:               4352345,
 		FeeProportionalMillionths: 90392423,
 		ToNode:                    firstNode,
-		ExtraOpaqueData:           []byte("new unknown feature1"),
+		ExtraOpaqueData:           []byte{1, 0},
 	}
 
 	return edgeInfo, edge1, edge2
@@ -3929,24 +3929,61 @@ func TestGraphCacheForEachNodeChannel(t *testing.T) {
 	require.Nil(t, err)
 
 	// Create an edge and add it to the db.
-	edgeInfo, _, _ := createChannelEdge(graph.db, node1, node2)
+	edgeInfo, e1, e2 := createChannelEdge(graph.db, node1, node2)
+
+	// Because of lexigraphical sorting and the usage of random node keys in
+	// this test, we need to determine which edge belongs to node 1 at
+	// runtime.
+	var edge1 *models.ChannelEdgePolicy
+	if e1.ToNode == node2.PubKeyBytes {
+		edge1 = e1
+	} else {
+		edge1 = e2
+	}
 
 	// Add the channel, but only insert a single edge into the graph.
 	require.NoError(t, graph.AddChannelEdge(edgeInfo))
 
+	getSingleChannel := func() *DirectedChannel {
+		var ch *DirectedChannel
+		err = graph.ForEachNodeDirectedChannel(nil, node1.PubKeyBytes,
+			func(c *DirectedChannel) error {
+				require.Nil(t, ch)
+				ch = c
+
+				return nil
+			},
+		)
+		require.NoError(t, err)
+
+		return ch
+	}
+
 	// We should be able to accumulate the single channel added, even
 	// though we have a nil edge policy here.
-	var numChans int
-	err = graph.ForEachNodeDirectedChannel(nil, node1.PubKeyBytes,
-		func(_ *DirectedChannel) error {
-			numChans++
+	require.NotNil(t, getSingleChannel())
 
-			return nil
-		},
-	)
-	require.NoError(t, err)
+	// Set an inbound fee and check that it is properly returned.
+	edge1.ExtraOpaqueData = []byte{
+		253, 217, 3, 8, 0, 0, 0, 10, 0, 0, 0, 20,
+	}
+	require.NoError(t, graph.UpdateEdgePolicy(edge1))
+
+	directedChan := getSingleChannel()
+	require.NotNil(t, directedChan)
+	require.Equal(t, directedChan.InboundFee, lnwire.Fee{
+		BaseFee: 10,
+		FeeRate: 20,
+	})
+
+	// Set an invalid inbound fee and check that the edge is no longer
+	// returned.
+	edge1.ExtraOpaqueData = []byte{
+		253, 217, 3, 8, 0,
+	}
+	require.NoError(t, graph.UpdateEdgePolicy(edge1))
 
-	require.Equal(t, numChans, 1)
+	require.Nil(t, getSingleChannel())
 }
 
 // TestGraphLoading asserts that the cache is properly reconstructed after a
diff --git a/itest/lnd_multi-hop-payments_test.go b/itest/lnd_multi-hop-payments_test.go
index 55dddcb83..2da2213d7 100644
--- a/itest/lnd_multi-hop-payments_test.go
+++ b/itest/lnd_multi-hop-payments_test.go
@@ -70,7 +70,7 @@ func testMultiHopPayments(ht *lntest.HarnessTest) {
 	// channel edges to relatively large non default values. This makes it
 	// possible to pick up more subtle fee calculation errors.
 	maxHtlc := lntest.CalculateMaxHtlc(chanAmt)
-	const aliceBaseFeeSat = 1
+	const aliceBaseFeeSat = 20
 	const aliceFeeRatePPM = 100000
 	updateChannelPolicy(
 		ht, alice, chanPointAlice, aliceBaseFeeSat*1000,
@@ -81,8 +81,8 @@ func testMultiHopPayments(ht *lntest.HarnessTest) {
 	// Define a negative inbound fee for Alice, to verify that this is
 	// backwards compatible with an older sender ignoring the discount.
 	const (
-		aliceInboundBaseFeeMsat = -1
-		aliceInboundFeeRate     = -10000
+		aliceInboundBaseFeeMsat = -2000
+		aliceInboundFeeRate     = -50000 // 5%
 	)
 
 	updateChannelPolicy(
@@ -119,12 +119,11 @@ func testMultiHopPayments(ht *lntest.HarnessTest) {
 	ht.AssertAmountPaid("Alice(local) => Bob(remote)", alice,
 		chanPointAlice, expectedAmountPaidAtoB, int64(0))
 
-	// To forward a payment of 1000 sat, Alice is charging a fee of 1 sat +
-	// 10% = 101 sat. Note that this does not include the inbound fee
-	// (discount) because there is no sender support yet.
-	const aliceFeePerPayment = aliceBaseFeeSat +
-		(paymentAmt * aliceFeeRatePPM / 1_000_000)
-	const expectedFeeAlice = numPayments * aliceFeePerPayment
+	// To forward a payment of 1000 sat, Alice is charging a fee of 20 sat +
+	// 10% = 120 sat, plus the inbound fee over 1120 (= 1000 + 120) sat of
+	// -2 sat - 5% = -58 sat. This makes a total of 62 sat per payment. For
+	// 5 payments, it works out to 310 sat.
+	const expectedFeeAlice = 310
 
 	// Dave needs to pay what Alice pays plus Alice's fee.
 	expectedAmountPaidDtoA := expectedAmountPaidAtoB + expectedFeeAlice
@@ -134,12 +133,10 @@ func testMultiHopPayments(ht *lntest.HarnessTest) {
 	ht.AssertAmountPaid("Dave(local) => Alice(remote)", dave,
 		chanPointDave, expectedAmountPaidDtoA, int64(0))
 
-	// To forward a payment of 1101 sat, Dave is charging a fee of
-	// 5 sat + 15% = 170.15 sat. This is rounded down in rpcserver to 170.
-	const davePaymentAmt = paymentAmt + aliceFeePerPayment
-	const daveFeePerPayment = daveBaseFeeSat +
-		(davePaymentAmt * daveFeeRatePPM / 1_000_000)
-	const expectedFeeDave = numPayments * daveFeePerPayment
+	// To forward a payment of 1062 sat, Dave is charging a fee of 5 sat +
+	// 15% = 164.3 sat. For 5 payments this is 821.5 sat. This test works
+	// with sats, so we need to round down to 821.
+	const expectedFeeDave = 821
 
 	// Carol needs to pay what Dave pays plus Dave's fee.
 	expectedAmountPaidCtoD := expectedAmountPaidDtoA + expectedFeeDave
diff --git a/routing/pathfind_test.go b/routing/pathfind_test.go
index 6bf754c82..de4935a81 100644
--- a/routing/pathfind_test.go
+++ b/routing/pathfind_test.go
@@ -417,14 +417,16 @@ func parseTestGraph(t *testing.T, useCache bool, path string) (
 }
 
 type testChannelPolicy struct {
-	Expiry      uint16
-	MinHTLC     lnwire.MilliSatoshi
-	MaxHTLC     lnwire.MilliSatoshi
-	FeeBaseMsat lnwire.MilliSatoshi
-	FeeRate     lnwire.MilliSatoshi
-	LastUpdate  time.Time
-	Disabled    bool
-	Features    *lnwire.FeatureVector
+	Expiry             uint16
+	MinHTLC            lnwire.MilliSatoshi
+	MaxHTLC            lnwire.MilliSatoshi
+	FeeBaseMsat        lnwire.MilliSatoshi
+	FeeRate            lnwire.MilliSatoshi
+	InboundFeeBaseMsat int64
+	InboundFeeRate     int64
+	LastUpdate         time.Time
+	Disabled           bool
+	Features           *lnwire.FeatureVector
 }
 
 type testChannelEnd struct {
@@ -662,6 +664,19 @@ func createTestGraphFromChannels(t *testing.T, useCache bool,
 			return nil, err
 		}
 
+		getExtraData := func(
+			end *testChannelEnd) lnwire.ExtraOpaqueData {
+
+			var extraData lnwire.ExtraOpaqueData
+			inboundFee := lnwire.Fee{
+				BaseFee: int32(end.InboundFeeBaseMsat),
+				FeeRate: int32(end.InboundFeeRate),
+			}
+			require.NoError(t, extraData.PackRecords(&inboundFee))
+
+			return extraData
+		}
+
 		if node1.testChannelPolicy != nil {
 			var msgFlags lnwire.ChanUpdateMsgFlags
 			if node1.MaxHTLC != 0 {
@@ -684,6 +699,7 @@ func createTestGraphFromChannels(t *testing.T, useCache bool,
 				FeeBaseMSat:               node1.FeeBaseMsat,
 				FeeProportionalMillionths: node1.FeeRate,
 				ToNode:                    node2Vertex,
+				ExtraOpaqueData:           getExtraData(node1),
 			}
 			if err := graph.UpdateEdgePolicy(edgePolicy); err != nil {
 				return nil, err
@@ -713,6 +729,7 @@ func createTestGraphFromChannels(t *testing.T, useCache bool,
 				FeeBaseMSat:               node2.FeeBaseMsat,
 				FeeProportionalMillionths: node2.FeeRate,
 				ToNode:                    node1Vertex,
+				ExtraOpaqueData:           getExtraData(node2),
 			}
 			if err := graph.UpdateEdgePolicy(edgePolicy); err != nil {
 				return nil, err
@@ -809,6 +826,9 @@ func TestPathFinding(t *testing.T) {
 	}, {
 		name: "with metadata",
 		fn:   runFindPathWithMetadata,
+	}, {
+		name: "inbound fees",
+		fn:   runInboundFees,
 	}}
 
 	// Run with graph cache enabled.
@@ -1225,7 +1245,7 @@ func runPathFindingWithAdditionalEdges(t *testing.T, useCache bool) {
 	}
 
 	find := func(r *RestrictParams) (
-		[]*models.CachedEdgePolicy, error) {
+		[]*unifiedEdge, error) {
 
 		return dbFindPath(
 			graph.graph, additionalEdges, &mockBandwidthHints{},
@@ -1437,7 +1457,7 @@ func runPathFindingWithRedundantAdditionalEdges(t *testing.T, useCache bool) {
 	require.NoError(t, err, "unable to find path to bob")
 	require.Len(t, path, 1)
 
-	require.Equal(t, realChannelID, path[0].ChannelID,
+	require.Equal(t, realChannelID, path[0].policy.ChannelID,
 		"additional edge for known edge wasn't ignored")
 }
 
@@ -1723,8 +1743,17 @@ func TestNewRoute(t *testing.T) {
 		}
 
 		t.Run(testCase.name, func(t *testing.T) {
+			var unifiedHops []*unifiedEdge
+			for _, hop := range testCase.hops {
+				unifiedHops = append(unifiedHops,
+					&unifiedEdge{
+						policy: hop,
+					},
+				)
+			}
+
 			route, err := newRoute(
-				sourceVertex, testCase.hops, startingHeight,
+				sourceVertex, unifiedHops, startingHeight,
 				finalHopParams{
 					amt:         testCase.paymentAmount,
 					totalAmt:    testCase.paymentAmount,
@@ -1864,7 +1893,7 @@ func runDestTLVGraphFallback(t *testing.T, useCache bool) {
 	require.NoError(t, err, "unable to fetch source node")
 
 	find := func(r *RestrictParams,
-		target route.Vertex) ([]*models.CachedEdgePolicy, error) {
+		target route.Vertex) ([]*unifiedEdge, error) {
 
 		return dbFindPath(
 			ctx.graph, nil, &mockBandwidthHints{},
@@ -2522,7 +2551,7 @@ func TestPathFindSpecExample(t *testing.T) {
 }
 
 func assertExpectedPath(t *testing.T, aliasMap map[string]route.Vertex,
-	path []*models.CachedEdgePolicy, nodeAliases ...string) {
+	path []*unifiedEdge, nodeAliases ...string) {
 
 	if len(path) != len(nodeAliases) {
 		t.Fatalf("number of hops=(%v) and number of aliases=(%v) do "+
@@ -2530,9 +2559,10 @@ func assertExpectedPath(t *testing.T, aliasMap map[string]route.Vertex,
 	}
 
 	for i, hop := range path {
-		if hop.ToNodePubKey() != aliasMap[nodeAliases[i]] {
+		if hop.policy.ToNodePubKey() != aliasMap[nodeAliases[i]] {
 			t.Fatalf("expected %v to be pos #%v in hop, instead "+
-				"%v was", nodeAliases[i], i, hop.ToNodePubKey())
+				"%v was", nodeAliases[i], i,
+				hop.policy.ToNodePubKey())
 		}
 	}
 }
@@ -2606,10 +2636,10 @@ func runRestrictOutgoingChannel(t *testing.T, useCache bool) {
 
 	// Assert that the route starts with channel chanSourceB1, in line with
 	// the specified restriction.
-	if path[0].ChannelID != chanSourceB1 {
+	if path[0].policy.ChannelID != chanSourceB1 {
 		t.Fatalf("expected route to pass through channel %v, "+
 			"but channel %v was selected instead", chanSourceB1,
-			path[0].ChannelID)
+			path[0].policy.ChannelID)
 	}
 
 	// If a direct channel to target is allowed as well, that channel is
@@ -2619,7 +2649,7 @@ func runRestrictOutgoingChannel(t *testing.T, useCache bool) {
 	}
 	path, err = ctx.findPath(target, paymentAmt)
 	require.NoError(t, err, "unable to find path")
-	if path[0].ChannelID != chanSourceTarget {
+	if path[0].policy.ChannelID != chanSourceTarget {
 		t.Fatalf("expected route to pass through channel %v",
 			chanSourceTarget)
 	}
@@ -2658,10 +2688,10 @@ func runRestrictLastHop(t *testing.T, useCache bool) {
 	ctx.restrictParams.LastHop = &lastHop
 	path, err := ctx.findPath(target, paymentAmt)
 	require.NoError(t, err, "unable to find path")
-	if path[0].ChannelID != 3 {
+	if path[0].policy.ChannelID != 3 {
 		t.Fatalf("expected route to pass through channel 3, "+
 			"but channel %v was selected instead",
-			path[0].ChannelID)
+			path[0].policy.ChannelID)
 	}
 }
 
@@ -2941,10 +2971,10 @@ func testProbabilityRouting(t *testing.T, useCache bool,
 	}
 
 	// Assert that the route passes through the expected channel.
-	if path[1].ChannelID != expectedChan {
+	if path[1].policy.ChannelID != expectedChan {
 		t.Fatalf("expected route to pass through channel %v, "+
 			"but channel %v was selected instead", expectedChan,
-			path[1].ChannelID)
+			path[1].policy.ChannelID)
 	}
 }
 
@@ -3005,10 +3035,10 @@ func runEqualCostRouteSelection(t *testing.T, useCache bool) {
 		t.Fatal(err)
 	}
 
-	if path[1].ChannelID != 2 {
+	if path[1].policy.ChannelID != 2 {
 		t.Fatalf("expected route to pass through channel %v, "+
 			"but channel %v was selected instead", 2,
-			path[1].ChannelID)
+			path[1].policy.ChannelID)
 	}
 }
 
@@ -3119,6 +3149,147 @@ func runRouteToSelf(t *testing.T, useCache bool) {
 	ctx.assertPath(path, []uint64{1, 3, 2})
 }
 
+// runInboundFees tests whether correct routes are built when inbound fees
+// apply.
+func runInboundFees(t *testing.T, useCache bool) {
+	// Setup a test network.
+	chanCapSat := btcutil.Amount(100000)
+	features := lnwire.NewFeatureVector(
+		lnwire.NewRawFeatureVector(
+			lnwire.PaymentAddrOptional,
+			lnwire.TLVOnionPayloadRequired,
+		),
+		lnwire.Features,
+	)
+
+	testChannels := []*testChannel{
+		asymmetricTestChannel("a", "b", chanCapSat,
+			&testChannelPolicy{
+				MinHTLC:  lnwire.NewMSatFromSatoshis(2),
+				Features: features,
+			},
+			&testChannelPolicy{
+				Features:           features,
+				InboundFeeRate:     -60000,
+				InboundFeeBaseMsat: -5000,
+			}, 10,
+		),
+		asymmetricTestChannel("b", "c", chanCapSat,
+			&testChannelPolicy{
+				Expiry:      20,
+				FeeRate:     50000,
+				FeeBaseMsat: 1000,
+				MinHTLC:     lnwire.NewMSatFromSatoshis(2),
+				Features:    features,
+			},
+			&testChannelPolicy{
+				Features:           features,
+				InboundFeeRate:     0,
+				InboundFeeBaseMsat: 5000,
+			}, 11,
+		),
+		asymmetricTestChannel("c", "d", chanCapSat,
+			&testChannelPolicy{
+				Expiry:      20,
+				FeeRate:     50000,
+				FeeBaseMsat: 0,
+				MinHTLC:     lnwire.NewMSatFromSatoshis(2),
+				Features:    features,
+			},
+			&testChannelPolicy{
+				Features:           features,
+				InboundFeeRate:     -50000,
+				InboundFeeBaseMsat: -8000,
+			}, 12,
+		),
+		asymmetricTestChannel("d", "e", chanCapSat,
+			&testChannelPolicy{
+				Expiry:      20,
+				FeeRate:     100000,
+				FeeBaseMsat: 9000,
+				MinHTLC:     lnwire.NewMSatFromSatoshis(2),
+				Features:    features,
+			},
+			&testChannelPolicy{
+				Features:           features,
+				InboundFeeRate:     80000,
+				InboundFeeBaseMsat: 2000,
+			}, 13,
+		),
+	}
+
+	ctx := newPathFindingTestContext(t, useCache, testChannels, "a")
+
+	payAddr := [32]byte{1}
+	ctx.restrictParams.PaymentAddr = &payAddr
+	ctx.restrictParams.DestFeatures = tlvPayAddrFeatures
+
+	const (
+		startingHeight = 100
+		finalHopCLTV   = 1
+	)
+
+	paymentAmt := lnwire.MilliSatoshi(100_000)
+	target := ctx.keyFromAlias("e")
+	path, err := ctx.findPath(target, paymentAmt)
+	require.NoError(t, err, "unable to find path")
+
+	rt, err := newRoute(
+		ctx.source, path, startingHeight,
+		finalHopParams{
+			amt:         paymentAmt,
+			cltvDelta:   finalHopCLTV,
+			records:     nil,
+			paymentAddr: &payAddr,
+			totalAmt:    paymentAmt,
+		},
+		nil,
+	)
+	require.NoError(t, err, "unable to create path")
+
+	expectedHops := []*route.Hop{
+		{
+			PubKeyBytes: ctx.keyFromAlias("b"),
+			ChannelID:   10,
+			// The amount that c forwards (105_050) plus the out fee
+			// (5_252) and in fee (5_000) of c.
+			AmtToForward:     115_302,
+			OutgoingTimeLock: 141,
+		},
+		{
+			PubKeyBytes: ctx.keyFromAlias("c"),
+			ChannelID:   11,
+			// The amount that d forwards (100_000) plus the out fee
+			// (19_000) and in fee (-13_950) of d.
+			AmtToForward:     105_050,
+			OutgoingTimeLock: 121,
+		},
+		{
+			PubKeyBytes:      ctx.keyFromAlias("d"),
+			ChannelID:        12,
+			AmtToForward:     100_000,
+			OutgoingTimeLock: 101,
+		},
+		{
+			PubKeyBytes:      ctx.keyFromAlias("e"),
+			ChannelID:        13,
+			AmtToForward:     100_000,
+			OutgoingTimeLock: 101,
+			MPP:              record.NewMPP(100_000, payAddr),
+		},
+	}
+
+	expectedRt := &route.Route{
+		// The amount that b forwards (115_302) plus the out fee (6_765)
+		// and in fee (-12324) of b. The total fee is floored at zero.
+		TotalAmount:   115_302,
+		TotalTimeLock: 161,
+		SourcePubKey:  ctx.keyFromAlias("a"),
+		Hops:          expectedHops,
+	}
+	require.Equal(t, expectedRt, rt)
+}
+
 type pathFindingTestContext struct {
 	t                 *testing.T
 	graph             *channeldb.ChannelGraph
@@ -3168,7 +3339,7 @@ func (c *pathFindingTestContext) aliasFromKey(pubKey route.Vertex) string {
 }
 
 func (c *pathFindingTestContext) findPath(target route.Vertex,
-	amt lnwire.MilliSatoshi) ([]*models.CachedEdgePolicy,
+	amt lnwire.MilliSatoshi) ([]*unifiedEdge,
 	error) {
 
 	return dbFindPath(
@@ -3177,7 +3348,7 @@ func (c *pathFindingTestContext) findPath(target route.Vertex,
 	)
 }
 
-func (c *pathFindingTestContext) assertPath(path []*models.CachedEdgePolicy,
+func (c *pathFindingTestContext) assertPath(path []*unifiedEdge,
 	expected []uint64) {
 
 	if len(path) != len(expected) {
@@ -3186,9 +3357,10 @@ func (c *pathFindingTestContext) assertPath(path []*models.CachedEdgePolicy,
 	}
 
 	for i, edge := range path {
-		if edge.ChannelID != expected[i] {
+		if edge.policy.ChannelID != expected[i] {
 			c.t.Fatalf("expected hop %v to be channel %v, "+
-				"but got %v", i, expected[i], edge.ChannelID)
+				"but got %v", i, expected[i],
+				edge.policy.ChannelID)
 		}
 	}
 }
@@ -3200,7 +3372,7 @@ func dbFindPath(graph *channeldb.ChannelGraph,
 	bandwidthHints bandwidthHints,
 	r *RestrictParams, cfg *PathFindingConfig,
 	source, target route.Vertex, amt lnwire.MilliSatoshi, timePref float64,
-	finalHtlcExpiry int32) ([]*models.CachedEdgePolicy, error) {
+	finalHtlcExpiry int32) ([]*unifiedEdge, error) {
 
 	sourceNode, err := graph.SourceNode()
 	if err != nil {
@@ -3351,11 +3523,11 @@ func TestBlindedRouteConstruction(t *testing.T) {
 	carolDaveEdge := blindedEdges[carolVertex][0]
 	daveEveEdge := blindedEdges[daveBlindedVertex][0]
 
-	edges := []*models.CachedEdgePolicy{
-		aliceBobEdge,
-		bobCarolEdge,
-		carolDaveEdge.EdgePolicy(),
-		daveEveEdge.EdgePolicy(),
+	edges := []*unifiedEdge{
+		{policy: aliceBobEdge},
+		{policy: bobCarolEdge},
+		{policy: carolDaveEdge.EdgePolicy()},
+		{policy: daveEveEdge.EdgePolicy()},
 	}
 
 	// Total timelock for the route should include:
diff --git a/routing/payment_session_test.go b/routing/payment_session_test.go
index 67a285159..75b84a51a 100644
--- a/routing/payment_session_test.go
+++ b/routing/payment_session_test.go
@@ -212,7 +212,7 @@ func TestRequestRoute(t *testing.T) {
 	// Override pathfinder with a mock.
 	session.pathFinder = func(_ *graphParams, r *RestrictParams,
 		_ *PathFindingConfig, _, _ route.Vertex, _ lnwire.MilliSatoshi,
-		_ float64, _ int32) ([]*models.CachedEdgePolicy, float64,
+		_ float64, _ int32) ([]*unifiedEdge, float64,
 		error) {
 
 		// We expect find path to receive a cltv limit excluding the
@@ -221,14 +221,16 @@ func TestRequestRoute(t *testing.T) {
 			t.Fatal("wrong cltv limit")
 		}
 
-		path := []*models.CachedEdgePolicy{
+		path := []*unifiedEdge{
 			{
-				ToNodePubKey: func() route.Vertex {
-					return route.Vertex{}
+				policy: &models.CachedEdgePolicy{
+					ToNodePubKey: func() route.Vertex {
+						return route.Vertex{}
+					},
+					ToNodeFeatures: lnwire.NewFeatureVector(
+						nil, nil,
+					),
 				},
-				ToNodeFeatures: lnwire.NewFeatureVector(
-					nil, nil,
-				),
 			},
 		}
 
diff --git a/routing/router_test.go b/routing/router_test.go
index 12c8ff729..47bdf7a17 100644
--- a/routing/router_test.go
+++ b/routing/router_test.go
@@ -2450,8 +2450,8 @@ func TestFindPathFeeWeighting(t *testing.T) {
 	if len(path) != 1 {
 		t.Fatalf("expected path length of 1, instead was: %v", len(path))
 	}
-	if path[0].ToNodePubKey() != ctx.aliases["luoji"] {
-		t.Fatalf("wrong node: %v", path[0].ToNodePubKey())
+	if path[0].policy.ToNodePubKey() != ctx.aliases["luoji"] {
+		t.Fatalf("wrong node: %v", path[0].policy.ToNodePubKey())
 	}
 }
 
diff --git a/routing/unified_edges_test.go b/routing/unified_edges_test.go
index 043447f52..7b1650c02 100644
--- a/routing/unified_edges_test.go
+++ b/routing/unified_edges_test.go
@@ -18,10 +18,15 @@ func TestNodeEdgeUnifier(t *testing.T) {
 	source := route.Vertex{1}
 	toNode := route.Vertex{2}
 	fromNode := route.Vertex{3}
-	bandwidthHints := &mockBandwidthHints{}
+	bandwidthHints := &mockBandwidthHints{
+		hints: map[uint64]lnwire.MilliSatoshi{
+			100: 150,
+		},
+	}
 
 	// Add two channels between the pair of nodes.
 	p1 := models.CachedEdgePolicy{
+		ChannelID:                 100,
 		FeeProportionalMillionths: 100000,
 		FeeBaseMSat:               30,
 		TimeLockDelta:             60,
@@ -30,6 +35,7 @@ func TestNodeEdgeUnifier(t *testing.T) {
 		MinHTLC:                   100,
 	}
 	p2 := models.CachedEdgePolicy{
+		ChannelID:                 101,
 		FeeProportionalMillionths: 190000,
 		FeeBaseMSat:               10,
 		TimeLockDelta:             40,
@@ -40,28 +46,75 @@ func TestNodeEdgeUnifier(t *testing.T) {
 	c1 := btcutil.Amount(7)
 	c2 := btcutil.Amount(8)
 
-	unifierFilled := newNodeEdgeUnifier(source, toNode, nil)
-	unifierFilled.addPolicy(fromNode, &p1, c1, defaultHopPayloadSize)
-	unifierFilled.addPolicy(fromNode, &p2, c2, defaultHopPayloadSize)
+	inboundFee1 := models.InboundFee{
+		Base: 5,
+		Rate: 10000,
+	}
+
+	inboundFee2 := models.InboundFee{
+		Base: 10,
+		Rate: 10000,
+	}
+
+	unifierFilled := newNodeEdgeUnifier(source, toNode, false, nil)
+
+	unifierFilled.addPolicy(
+		fromNode, &p1, inboundFee1, c1, defaultHopPayloadSize,
+	)
+	unifierFilled.addPolicy(
+		fromNode, &p2, inboundFee2, c2, defaultHopPayloadSize,
+	)
 
-	unifierNoCapacity := newNodeEdgeUnifier(source, toNode, nil)
-	unifierNoCapacity.addPolicy(fromNode, &p1, 0, defaultHopPayloadSize)
-	unifierNoCapacity.addPolicy(fromNode, &p2, 0, defaultHopPayloadSize)
+	unifierNoCapacity := newNodeEdgeUnifier(source, toNode, false, nil)
+	unifierNoCapacity.addPolicy(
+		fromNode, &p1, inboundFee1, 0, defaultHopPayloadSize,
+	)
+	unifierNoCapacity.addPolicy(
+		fromNode, &p2, inboundFee2, 0, defaultHopPayloadSize,
+	)
 
-	unifierNoInfo := newNodeEdgeUnifier(source, toNode, nil)
+	unifierNoInfo := newNodeEdgeUnifier(source, toNode, false, nil)
 	unifierNoInfo.addPolicy(
-		fromNode, &models.CachedEdgePolicy{}, 0, defaultHopPayloadSize,
+		fromNode, &models.CachedEdgePolicy{}, models.InboundFee{},
+		0, defaultHopPayloadSize,
+	)
+
+	unifierInboundFee := newNodeEdgeUnifier(source, toNode, true, nil)
+	unifierInboundFee.addPolicy(
+		fromNode, &p1, inboundFee1, c1, defaultHopPayloadSize,
+	)
+	unifierInboundFee.addPolicy(
+		fromNode, &p2, inboundFee2, c2, defaultHopPayloadSize,
+	)
+
+	unifierLocal := newNodeEdgeUnifier(fromNode, toNode, true, nil)
+	unifierLocal.addPolicy(
+		fromNode, &p1, inboundFee1, c1, defaultHopPayloadSize,
+	)
+
+	inboundFeeZero := models.InboundFee{}
+	inboundFeeNegative := models.InboundFee{
+		Base: -150,
+	}
+	unifierNegInboundFee := newNodeEdgeUnifier(source, toNode, true, nil)
+	unifierNegInboundFee.addPolicy(
+		fromNode, &p1, inboundFeeZero, c1, defaultHopPayloadSize,
+	)
+	unifierNegInboundFee.addPolicy(
+		fromNode, &p2, inboundFeeNegative, c2, defaultHopPayloadSize,
 	)
 
 	tests := []struct {
-		name             string
-		unifier          *nodeEdgeUnifier
-		amount           lnwire.MilliSatoshi
-		expectedFeeBase  lnwire.MilliSatoshi
-		expectedFeeRate  lnwire.MilliSatoshi
-		expectedTimeLock uint16
-		expectNoPolicy   bool
-		expectedCapacity btcutil.Amount
+		name               string
+		unifier            *nodeEdgeUnifier
+		amount             lnwire.MilliSatoshi
+		expectedFeeBase    lnwire.MilliSatoshi
+		expectedFeeRate    lnwire.MilliSatoshi
+		expectedInboundFee models.InboundFee
+		expectedTimeLock   uint16
+		expectNoPolicy     bool
+		expectedCapacity   btcutil.Amount
+		nextOutFee         lnwire.MilliSatoshi
 	}{
 		{
 			name:           "amount below min htlc",
@@ -116,6 +169,57 @@ func TestNodeEdgeUnifier(t *testing.T) {
 			unifier:          unifierNoInfo,
 			expectedCapacity: 0,
 		},
+		{
+			name:           "local insufficient bandwidth",
+			unifier:        unifierLocal,
+			amount:         200,
+			expectNoPolicy: true,
+		},
+		{
+			name:               "local",
+			unifier:            unifierLocal,
+			amount:             100,
+			expectedFeeBase:    p1.FeeBaseMSat,
+			expectedFeeRate:    p1.FeeProportionalMillionths,
+			expectedTimeLock:   p1.TimeLockDelta,
+			expectedCapacity:   c1,
+			expectedInboundFee: inboundFee1,
+		},
+		{
+			name: "use p2 with highest fee " +
+				"including inbound",
+			unifier:            unifierInboundFee,
+			amount:             200,
+			expectedFeeBase:    p2.FeeBaseMSat,
+			expectedFeeRate:    p2.FeeProportionalMillionths,
+			expectedInboundFee: inboundFee2,
+			expectedTimeLock:   p1.TimeLockDelta,
+			expectedCapacity:   c2,
+		},
+		// Choose inbound fee exactly so that max htlc is just exceeded.
+		// In this test, the amount that must be sent is 5001 msat.
+		{
+			name:           "inbound fee exceeds max htlc",
+			unifier:        unifierInboundFee,
+			amount:         4947,
+			expectNoPolicy: true,
+		},
+		// The outbound fee of p2 is higher than p1, but because of the
+		// inbound fee on p2 it is brought down to 0. Purely based on
+		// total channel fee, p1 would be selected as the highest fee
+		// channel. However, because the total node fee can never be
+		// negative and the next outgoing fee is zero, the effect of the
+		// inbound discount is cancelled out.
+		{
+			name:               "inbound fee that is rounded up",
+			unifier:            unifierNegInboundFee,
+			amount:             500,
+			expectedFeeBase:    p2.FeeBaseMSat,
+			expectedFeeRate:    p2.FeeProportionalMillionths,
+			expectedInboundFee: inboundFeeNegative,
+			expectedTimeLock:   p1.TimeLockDelta,
+			expectedCapacity:   c2,
+		},
 	}
 
 	for _, test := range tests {
@@ -125,7 +229,7 @@ func TestNodeEdgeUnifier(t *testing.T) {
 			t.Parallel()
 
 			edge := test.unifier.edgeUnifiers[fromNode].getEdge(
-				test.amount, bandwidthHints,
+				test.amount, bandwidthHints, test.nextOutFee,
 			)
 
 			if test.expectNoPolicy {
@@ -139,6 +243,8 @@ func TestNodeEdgeUnifier(t *testing.T) {
 				policy.FeeBaseMSat, "base fee")
 			require.Equal(t, test.expectedFeeRate,
 				policy.FeeProportionalMillionths, "fee rate")
+			require.Equal(t, test.expectedInboundFee,
+				edge.inboundFees, "inbound fee")
 			require.Equal(t, test.expectedTimeLock,
 				policy.TimeLockDelta, "timelock")
 			require.Equal(t, test.expectedCapacity, edge.capacity,