routing: inbound fees send support #6934

joostjager · 2022-09-21T09:54:43Z

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 · 2022-10-19T21:09:10Z

Removed exit hop inbound fees. Previous code saved in master...bottlepay:lnd:inbound-fees-send-support-exit-hop

joostjager · 2022-11-22T08:08:39Z

routing/pathfind.go

+		signedFee := inboundFee + outboundFee
+		fee := lnwire.MilliSatoshi(0)
+		if signedFee > 0 {
+			fee = lnwire.MilliSatoshi(signedFee)


@halseth you expressed concerns about negative fees being able to cancel out probability penalties for unreliable nodes. I've addressed the issue here by always rounding the fee that is used for the edge weight up to zero.

Perhaps this check must be removed now that the node total fee is guarded against negative. Otherwise pathfinding may return suboptimal routes?

I am actually quite sure of this. Suppose a node has an in fee of -100000 and an out fee of 100000. Those cancel out perfectly and shouldn't lead to pathfinding that is any different from a zero fee?

But... we still need to do this because dijkstra can't handle negative weights 🤷

It is a possibility though to floor at zero the actual edge weight calculated below rather than the fee.

I am actually quite sure of this. Suppose a node has an in fee of -100000 and an out fee of 100000. Those cancel out perfectly and shouldn't lead to pathfinding that is any different from a zero fee?

Do you mean that those fees are on a single channel or on a node with incoming and outgoing channels?

I mean on a node with incoming and outgoing channels. The fee paid to that particular node would be 0, so you'd expect it to be treated no different from a node that actually charges zero fee.

This could still be a problem, looking into that. edit: left a main comment #6934 (review)

bitromortac · 2023-12-12T09:45:28Z

routing/pathfind.go

+		totalFee := toNodeDist.outboundFee +
+			lnwire.MilliSatoshi(inboundFee)
+
+		if lnwire.MilliSatoshi(totalFee) > r.FeeLimit {


I think we still need the total fees for the r.FeeLimit check. Also, lnwire.MilliSatoshi has underlying type of uint64, so it wouldn't work for negative inbound fees. So we would keep the previous code here and use fee := lnwire.MilliSatoshi(int64(toNodeDist.outboundFee) + inboundFee), which is guaranteed to be non-negative?

I think further up, it is already enforced that in > -out. These casts don't really matter I think, because on the lowest level these data types are the same?

This checks only the hop fee, not the total fee accrued over the path, but the fee limit is for the whole path, I think.

routing/pathfind.go

bitromortac

I think that this PR is in really good shape. One issue that came up during previous reviews was that there is a difficulty in computing optimal fees when using a zero fee cutoff for the total channel fee. The cutoff needs to be applied to avoid that channel weights become negative due to negative inbound fees, which otherwise poses a problem for Dijkstra's algorithm. The non-optimality can be seen in this example:

Two competing routes (respecting total node fees to be non-negative)
...-A-[out fee 0 msat | in fee -100 msat]-B-[out 100 msat | in fee 0]-C
and
...-A'-[out fee 100 msat | in fee -100 msat]-B-[out 100 msat | in fee 0]-C
are assigned a virtual cost of 100 msat in pathfinding because of the restriction that total fees per channel are not allowed to become negative (the first hops have zero virtual fees). Both routes are then equivalent, any one may be probabilistically selected over the other. The first one in reality is 100 msat cheaper than the second one, leading to potential overpayment by a sender if the second one is used. The problem arises when B sets their inbound fees to negative values, larger in magnitude than the outbound fees charged by A. B doesn't earn anything in this process here, but they subsidize A'. B has an incentive to enforce the total channel fee by decreasing their inbound discount to 0 msat, because then they can earn the full 100 msat on the A-B-C route, without making the path more expensive in terms of virtual fees.

@joostjager solved this by mapping from the node-based topology to a line graph (https://en.wikipedia.org/wiki/Line_graph), where the pivots of exploration are not the nodes, but the points in between them. The effect of this approach is that distances are tracked on a peer-tuple basis rather than on a per node basis, which I think solves the problem of negative (inbound) fees in conjunction with non-negatively constrained node total fees for Dijkstra's algorithm. This last commit is a larger conceptual change, where we need to be sure that no side effects are introduced, which is why we could start with the non-optimal cutoff solution first (as imo it's incentive compatible) and introduce the exact approach at a later stage, but would be open for the complete solution as well.

bitromortac · 2024-01-22T10:50:58Z

channeldb/graph_cache.go

@@ -240,11 +251,13 @@ func (c *GraphCache) UpdatePolicy(policy *models.ChannelEdgePolicy, fromNode,
 		// policy for node 1.
 		case channel.IsNode1 && edge1:
 			channel.OutPolicySet = true


unrelated to this PR, do you know why OutPolicySet this is needed?

I've traced back a bit and it seems it is a left-over from old times when in this function the channel id was retrieved from the out policy object. #3749 introduced the check when it still seemed to make sense.

bitromortac · 2024-01-22T12:46:40Z

routing/pathfind.go

@@ -956,7 +1017,7 @@ func findPath(g *graphParams, r *RestrictParams, cfg *PathFindingConfig,
 			}

 			edge := edgeUnifier.getEdge(


Do we need to make this dependent on the previous outbound fee as well? We may have two parallel policies [in: -150 msat, out: 200msat] and [in: 0 msat, out: 100 msat] with previous outbound fee of 0 msat. We would take the second policy right now, but it's actually the first policy that leads to more fees because of the total node fee cutoff.

I don't think that parallel policy logic is all that essential, because node operators should know that ambiguous policies may lead to failures. But nevertheless you are right. I am now passing in nextOutFee to edgeUnifier.

routing/unified_edges_test.go

routing/pathfind.go

joostjager · 2024-01-24T09:56:08Z

I am in favour of the non-optimal cutoff solution for now. I think it is sufficiently good to gather feedback on the inbound fees concept, and - as you say - we can revisit node pair search at a later stage. I've archived the relevant commit on a different branch https://github.com/joostjager/lnd/tree/inbound-fees-node-pair-search.

coderabbitai · 2024-01-24T09:58:16Z

Important

Auto Review Skipped

Auto reviews are limited to the following labels: llm-review. Please add one of these labels to enable auto reviews.

Please check the settings in the CodeRabbit UI or the .coderabbit.yaml file in this repository.

To trigger a single review, invoke the @coderabbitai review command.

Thank you for using CodeRabbit. We offer it for free to the OSS community and would appreciate your support in helping us grow. If you find it useful, would you consider giving us a shout-out on your favorite social media?

Share

Tips

Chat

There are 3 ways to chat with CodeRabbit:

Review comments: Directly reply to a review comment made by CodeRabbit. Example:
- I pushed a fix in commit <commit_id>.
- Generate unit testing code for this file.
- Open a follow-up GitHub issue for this discussion.
Files and specific lines of code (under the "Files changed" tab): Tag @coderabbitai in a new review comment at the desired location with your query. Examples:
- @coderabbitai generate unit testing code for this file.
- @coderabbitai modularize this function.
PR comments: Tag @coderabbitai in a new PR comment to ask questions about the PR branch. For the best results, please provide a very specific query, as very limited context is provided in this mode. Examples:
- @coderabbitai generate interesting stats about this repository and render them as a table.
- @coderabbitai show all the console.log statements in this repository.
- @coderabbitai read src/utils.ts and generate unit testing code.
- @coderabbitai read the files in the src/scheduler package and generate a class diagram using mermaid and a README in the markdown format.

Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments.

CodeRabbit Commands (invoked as PR comments)

@coderabbitai pause to pause the reviews on a PR.
@coderabbitai resume to resume the paused reviews.
@coderabbitai review to trigger a review. This is useful when automatic reviews are disabled for the repository.
@coderabbitai resolve resolve all the CodeRabbit review comments.
@coderabbitai help to get help.

Additionally, you can add @coderabbitai ignore anywhere in the PR description to prevent this PR from being reviewed.

CodeRabbit Configration File (`.coderabbit.yaml`)

You can programmatically configure CodeRabbit by adding a .coderabbit.yaml file to the root of your repository.
The JSON schema for the configuration file is available here.
If your editor has YAML language server enabled, you can add the path at the top of this file to enable auto-completion and validation: # yaml-language-server: $schema=https://coderabbit.ai/integrations/coderabbit-overrides.v2.json

CodeRabbit Discord Community

Join our Discord Community to get help, request features, and share feedback.

bitromortac

LGTM 🎉 (tested pathfinding in a small network as well).

joostjager · 2024-01-30T15:17:08Z

Rebased

lightninglabs-deploy · 2024-03-26T20:05:07Z

@joostjager, remember to re-request review from reviewers when ready

Roasbeef

LGTM 🪞

Considering if we should actually also have a hard reject on the RPC level if users try to set a positive inbound fee. In the future we could lift it given sufficient uptake within the core routing network. We can also add more telemetry using the HTLC interceptor (I think we're missing the field there actually?), which'll allow node operators to log the % of incoming payments that are able to observe their negative inbound fees.

Roasbeef · 2024-03-29T23:55:03Z

routing/pathfind.go

+
+			fee = int64(outboundFee) + inboundFee
+			if fee < 0 {
+				fee = 0


Perhaps we should log these occurrences on the Tracef log level?

I am not sure. The zero-floor has now become a feature of inbound fees both on the receiver and sender side. Nodes might use that and it doesn't necessary indicate a configuration mistake - if that was the reason you had in mind for logging?

Roasbeef · 2024-03-30T00:05:51Z

Needs rebase + conflicts addressed.

Preparation so that we can have the inbound fee available in addition to the outgoing policy.

Add sender-side support for inbound fees in pathfinding and route building.

twofaktor · 2024-03-31T21:14:19Z

Will be possible to set the default inbound fees on lnd.conf the same as the existing outbound fees? I can't see any modifications related to this new feature and merged PR in the sample-lnd.conf available on the repo, and any related with this: https://github.com/lightningnetwork/lnd/blob/master/sample-lnd.conf#L626-L633

Roasbeef · 2024-04-01T23:05:57Z

@twofaktor that makes a lot of sense, I've made a tracking issue for your request here: #8610. Thanks!

joostjager mentioned this pull request Sep 21, 2022

htlcswitch: add inbound routing fees receive support #6703

Merged

joostjager force-pushed the inbound-fees-send-support branch 3 times, most recently from f121e4b to 7beb44a Compare September 29, 2022 07:25

joostjager added the routing label Oct 3, 2022

joostjager force-pushed the inbound-fees-send-support branch 7 times, most recently from 859464c to f940c83 Compare October 17, 2022 07:46

joostjager force-pushed the inbound-fees-send-support branch from f940c83 to 73e5422 Compare October 19, 2022 16:51

joostjager mentioned this pull request Oct 19, 2022

router: inbound fees support for BuildRoute #7060

Draft

joostjager force-pushed the inbound-fees-send-support branch from 73e5422 to 99ed58f Compare October 19, 2022 16:56

joostjager added the path finding label Oct 19, 2022

joostjager force-pushed the inbound-fees-send-support branch 3 times, most recently from cbcde71 to cdac2e4 Compare October 19, 2022 20:08

joostjager force-pushed the inbound-fees-send-support branch from cdac2e4 to 5c4d210 Compare October 20, 2022 06:01

joostjager mentioned this pull request Oct 20, 2022

Ability to set inbound and outbound fees lightning/bolts#835

Open

joostjager force-pushed the inbound-fees-send-support branch 3 times, most recently from fc549fa to f9894dc Compare October 25, 2022 10:58

saubyk added the inbound fee Changes related to inbound routing fee label Nov 9, 2022

saubyk added this to the v0.17.0 milestone Nov 9, 2022

joostjager force-pushed the inbound-fees-send-support branch from f9894dc to 3fc276e Compare November 22, 2022 08:07

joostjager commented Nov 22, 2022

View reviewed changes

joostjager force-pushed the inbound-fees-send-support branch from 3fc276e to e662c77 Compare January 25, 2023 13:45

joostjager requested a review from bitromortac December 11, 2023 15:45

bitromortac reviewed Dec 12, 2023

View reviewed changes

bitromortac reviewed Jan 22, 2024

View reviewed changes

joostjager force-pushed the inbound-fees-send-support branch from 54c4988 to 2fb0965 Compare January 24, 2024 09:57

joostjager force-pushed the inbound-fees-send-support branch 3 times, most recently from 96903da to ca5dd90 Compare January 24, 2024 11:27

joostjager requested a review from bitromortac January 24, 2024 11:29

bitromortac approved these changes Jan 30, 2024

View reviewed changes

joostjager force-pushed the inbound-fees-send-support branch from ca5dd90 to 6370bc1 Compare January 30, 2024 15:16

Roasbeef approved these changes Mar 29, 2024

View reviewed changes

Roasbeef enabled auto-merge March 30, 2024 00:05

ziggie1984 mentioned this pull request Mar 31, 2024

Support Inbound Fees when LND 18 is released. rkfg/regolancer#63

Open

joostjager force-pushed the inbound-fees-send-support branch 2 times, most recently from dbdd97c to 49478a6 Compare March 31, 2024 15:17

joostjager added 4 commits March 31, 2024 18:12

routing: track unifiedPolicyEdge

e0a0804

Preparation so that we can have the inbound fee available in addition to the outgoing policy.

routing/test: test local unified edge

9d4251c

channeldb/test: refactor TestGraphCacheForEachNodeChannel

d97e7d3

routing: add inbound fee support to pathfinding

0bae781

Add sender-side support for inbound fees in pathfinding and route building.

joostjager force-pushed the inbound-fees-send-support branch from 49478a6 to 0bae781 Compare March 31, 2024 16:12

Roasbeef merged commit 5599b3c into lightningnetwork:master Mar 31, 2024
26 of 27 checks passed

Roasbeef mentioned this pull request Apr 1, 2024

lnd+config: add config options for inbound fee discount #8610

Open

feelancer21 mentioned this pull request Apr 2, 2024

Support for negative inbound fees after release of lnd 0.18 accumulator/charge-lnd#107

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

routing: inbound fees send support #6934

routing: inbound fees send support #6934

joostjager commented Sep 21, 2022 •

edited

joostjager commented Oct 19, 2022

joostjager Nov 22, 2022

halseth Nov 23, 2022

joostjager Nov 21, 2023

joostjager Nov 22, 2023

joostjager Nov 22, 2023 •

edited

bitromortac Nov 22, 2023 •

edited

joostjager Nov 22, 2023

bitromortac Dec 6, 2023 •

edited

bitromortac Dec 12, 2023

joostjager Dec 12, 2023

bitromortac Jan 22, 2024

bitromortac left a comment

bitromortac Jan 22, 2024

joostjager Jan 24, 2024 •

edited

bitromortac Jan 22, 2024

joostjager Jan 24, 2024

joostjager commented Jan 24, 2024

coderabbitai bot commented Jan 24, 2024 •

edited

Auto Review Skipped

Chat

CodeRabbit Commands (invoked as PR comments)

CodeRabbit Configration File (`.coderabbit.yaml`)

CodeRabbit Discord Community

bitromortac left a comment

joostjager commented Jan 30, 2024

lightninglabs-deploy commented Mar 26, 2024

Roasbeef left a comment

Roasbeef Mar 29, 2024

joostjager Mar 31, 2024

Roasbeef commented Mar 30, 2024

twofaktor commented Mar 31, 2024 •

edited

Roasbeef commented Apr 1, 2024

		@@ -956,7 +1017,7 @@ func findPath(g graphParams, r RestrictParams, cfg *PathFindingConfig,
		}

		edge := edgeUnifier.getEdge(

routing: inbound fees send support #6934

routing: inbound fees send support #6934

Conversation

joostjager commented Sep 21, 2022 • edited

Implementation details

joostjager commented Oct 19, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

joostjager Nov 22, 2023 • edited

Choose a reason for hiding this comment

bitromortac Nov 22, 2023 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bitromortac Dec 6, 2023 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bitromortac left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

joostjager Jan 24, 2024 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

joostjager commented Jan 24, 2024

coderabbitai bot commented Jan 24, 2024 • edited

Auto Review Skipped

Chat

CodeRabbit Commands (invoked as PR comments)

CodeRabbit Configration File (.coderabbit.yaml)

CodeRabbit Discord Community

bitromortac left a comment

Choose a reason for hiding this comment

joostjager commented Jan 30, 2024

lightninglabs-deploy commented Mar 26, 2024

Roasbeef left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Roasbeef commented Mar 30, 2024

twofaktor commented Mar 31, 2024 • edited

Roasbeef commented Apr 1, 2024

joostjager commented Sep 21, 2022 •

edited

joostjager Nov 22, 2023 •

edited

bitromortac Nov 22, 2023 •

edited

bitromortac Dec 6, 2023 •

edited

joostjager Jan 24, 2024 •

edited

coderabbitai bot commented Jan 24, 2024 •

edited

CodeRabbit Configration File (`.coderabbit.yaml`)

twofaktor commented Mar 31, 2024 •

edited