Probing for more reliable route fee estimation

[hieblmi]

This PR implements https://github.com/lightningnetwork/lnd/issues/7916

Overview

In this PR we extend the implementation of the graph basedEstimateRouteFee RPC with a payment probe based approach to obtain a more reliable routing fee estimate.

Notes on implementation

• The new fee estimation API now optionally accepts an invoice from the target node and a probe payment timeout.
• Probing distinguishes two cases, (1) probing to a public destination key specified in the invoice or (2), probing a private invoice destination reachable through public hop hints in the invoice.
• If multiple hop hints are provided then, for each of the public ones, a probe is dispatched and each of the fee estimates is returned. Private hints are skipped.
• lncli adds support to use the graph-based and probe-based fee estimation:

graph-based:

lncli estimateroutefee --dest 0266a18ed969ef95c8a5aa314b443b2b3b8d91ed1d9f8e95476f5f4647efdec079 --amt 100000

probe-based:

lncli estimateroutefee reg_zane estimateroutefee --pay_req lnbcrt1m1pj... --timeout 60s

[JssDWt]

There is currently a problem with prepayment probing in combination with some lightning service providers. Basically prepayment probes are not compatible with the current LSP protocols. Since nodes behind a LSP can be a significant portion of destinations, I think it's good to keep the following considerations in mind. In below context, assume the payee is a lightning node behind a LSP.

In the current state I generally recommend against sending prepayment probes when a LSP is involved. Or if you do really want to probe, probe up to the LSP node, and manually add the fees for the ultimate hop. These fees can be taken from the route hint in the invoice. I guess the question is: how do you determine whether a LSP is involved? Let's outline the protocols and their caveats.

Present: Breez LSP

• Prepayment probes with a random payment hash will, in some situations around just-in-time channels, fail with unknown_next_peer returned by the LSP, even though the actual payment with the real payment hash would succeed.
• There is an option to re-hash the payment hash prefixed with probing-01, like here. When used with the current Breez LSP, the Breez LSP will return incorrect_or_unknown_payment_details in the same situations as where the previous bullet would return unknown_next_peer.

Soon: LSPS2

Very soon Breez and multiple other LSPs will implement the LSPS2 protocol. This is a protocol for just-in-time channels. This initial version of the protocol is incompatible with prepayment probes. There are no payment hash tricks here.

These nodes should have feature bit 729 (option_supports_lsps) set in their node announcement. Recommendation is to send the prepayment probe to the node in the route hint, rather than the destination node, if this feature bit is set for the route hint node and the destination node is only reachable through the route hint node (quite a mouthful, sorry about that).

Medium term: LSPS4

The LSP spec group is currently in the process of designing a LSP protocol LSPS4 for just-in-time channels. When LSPS4 is fully implemented, prepayment probes won't be much of an issue. This is not going to be implemented soon, however.

Other thoughts

Prepayment probes don't work together with MPP very well. At least there is no indication whether you were able to deliver the full amount for the specified fee, even if all payment parts return with incorrect_or_unknown_payment_details. Point is the parts do not all arrive at the same time, like they would in an actual payment. The previous parts locking up liquidity in the route on an actual payment may very well change the path chosen for next parts.

[hieblmi]

Thanks for the detailed rundown on LSP mechanics @JssDWt.

The primary focus of this PR is to improve the currently active graph based method of estimating routing fees. It is unreliable because the gossip announcements might not accurately reflect the network topology or fees at the time when a payment occurs. So in this first step the desired outcome is to improve the fee estimation for payments to publicly known nodes.

Follow-up PRs will focus on MPP/AMP as noted in the linked issue https://github.com/lightningnetwork/lnd/issues/7916. This seems to have gotten possible since the release of AMP by invalidating the last shard of a AMP, see https://github.com/lightningnetwork/lnd/issues/4219#issuecomment-908833773.

I think LSP specific probing protocols will also land with a separate PR.

[saubyk]

assigned @bitromortac for approach ack

[Roasbeef]

Prepayment probes don't work together with MPP very well. At least there is no indication whether you were able to deliver the full amount for the specified fee,

AMP solves that. You can send the N-1 shards, then make the Nth shared fail by giving it an invalid secret share.

[Roasbeef]

@JssDWt

These nodes should have feature bit 729 (option_supports_lsps) set in their node announcement. Recommendation is to send the prepayment probe to the node in the route hint, rather than the destination node, if this feature bit is set for the route hint node and the destination node is only reachable through the route hint node (quite a mouthful, sorry about that).

How will that work if a probing hash is used, and also only a single shard is sent that may be below the actual payment amount? The LSP just decides on a value to use for channel opening? What if the sender doesn't retry again, the LSP just eats the chain fees cost? What about if the user already has a channel open?

[JssDWt]

@Roasbeef

Assuming you're asking about probing all the way to the destination node, and not up until the LSP. Let me answer these one by one.

How will that work if a probing hash is used, and also only a single shard is sent that may be below the actual payment amount?

In that case the single shard is failed back by the LSP after a timeperiod similar to the MPP timeout. The recipient's invoice amount is the threshold for letting htlcs through and trigger channel open.

The LSP just decides on a value to use for channel opening?

The recipient communicates the intended amount to receive to the LSP before creating the invoice. The invoice then contains a route hint with a scid specifically for this payment/channel order.

What about if the user already has a channel open?

In that case there are no issues. The destination works like any other lightning node. Only if the recipient ordered a cchannel for that payment will this LSPS2 spec be used.

[Roasbeef]

@hieblmi is this ready to leave draft?

[hieblmi]

@hieblmi is this ready to leave draft?

@Roasbeef I will move to 'ready' once I have incorporated the hop hint fee estimation and refactor suggestions. Will focus on it.

[lightninglabs-deploy]

@bitromortac: review reminder @hieblmi, remember to re-request review from reviewers when ready

[coderabbitai[bot]]

[!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.

Walkthrough

This update introduces a new estimateroutefee command to the Payments category, enhancing Lightning Network's fee estimation capabilities. It incorporates improvements like payment probe-based routing fee estimation, handling of invoices, and a timeout parameter for fee estimation processes. Additionally, the update includes various test cases to ensure functionality and minor updates across the codebase to support these new features.

Changes

File Path	Change Summary
cmd/lncli/.../cmd_payments.go cmd/lncli/main.go	Added estimateroutefee command for routing fee estimation.
docs/release-notes/release-notes-0.18.0.md	Documented new features and updates in release notes.
itest/...	Added multiple integration tests for new and updated features.
lnrpc/routerrpc/... lntest/...	Enhanced fee estimation logic, added timeout configuration, and updated RPC and testing frameworks.
routing/missioncontrol.go sample-lnd.conf	Introduced default fee estimation timeout and configuration option.
zpay32/hophint.go	Added method for calculating forwarding fees.

Related issues

• lightningnetwork/lnd#7916: The changes in this PR directly address the objectives of enhancing the EstimateRouteFee RPC to improve fee estimation functionality, including adding an invoice parameter and a timeout parameter for fee estimation, which aligns with the issue's description.

Poem

In a network, vast and wide,
Where lightning bolts and data glide,
A rabbit hopped, with code so neat,
To estimate fees, no small feat. 🐰⚡💰

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

• X
• Mastodon
• Reddit
• LinkedIn

---

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-tests 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 tests 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 tests.
  • @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.

[hieblmi]

@coderabbitai review

[hieblmi]

~There are some LSP heuristic improvements that are still pending. I will ping the reviewers once they are pushed.~ For reviewers @bitromortac, @ProofOfKeags and @JssDWt, the LSP heuristic and fee calculation has been refined to handle multiple route hints.

[hieblmi]

@bitromortac, @ProofOfKeags, @champo thanks for your thorough reviews. I think I addressed all comments.

I am still working on the probing timeout test, but imo the review can continue without it for now.

@bitromortac We talked offline about the total cltv delta discrepancy of 3 blocks between graph and probe based estimates. Do harmonize the two I've added the block padding delta to the graph based estimation, see https://github.com/lightningnetwork/lnd/pull/8136/commits/87e0f9f218acd1d16ec0b45e75dc7d95be04fc58#diff-9ced6590b7c4cfad60e1fa1641b602da6fe758092211f30a55b19771e4186842R444

The other uncertainty I had was around handling the MinFinalCLTVExpiryDelta in combination with hop hints. In our LSP case we now add the cltv delta provided in the hop hint to the total cltv delta determined by the probe, but only in case it is greater than the payReq.MinFinalCLTVExpiry(), and payReq.MinFinalCLTVExpiry() otherwise, see https://github.com/lightningnetwork/lnd/pull/8136/commits/87e0f9f218acd1d16ec0b45e75dc7d95be04fc58#diff-9ced6590b7c4cfad60e1fa1641b602da6fe758092211f30a55b19771e4186842R550

EDIT: This has been cleared ~I still have a doubt about the hop cltv determined by our isLsp heuristic, it is here https://github.com/lightningnetwork/lnd/pull/8136/commits/87e0f9f218acd1d16ec0b45e75dc7d95be04fc58#r1479710025~

Thanks again for your time and effort!

[alexbosworth]

The issue with the zero amount invoices made me think if accepting an invoice to the api is really the best choice? There is some flow where a wallet gets a zero-amount invoice and the user fills in the amount. A probe would then be done with that amount. Right now we fail that use-case.

Failing isn't good, but it could also just have a separate amount field to mirror the send payment API, which would match the design pattern of probe with the arguments you want to use for a payment before you actually pay.

I can see the argument for generic probing fields but thinking about the history of this feature what motivated it from a user perspective is that doing this yourself is too hard, even though you can actually do everything yourself with the existing APIs. This API adds zero functionality you couldn't achieve some other way with other APIs and you can already break things down into components if you want to do that. So given that motivating logic, making it easier with just the payment request would be easier and therefore correct for this API.

[saubyk]

This API adds zero functionality you couldn't achieve some other way with other APIs and you can already break things down into components if you want to do that. So given that motivating logic, making it easier with just the payment request would be easier and therefore correct for this API.

+1 Improving usability by just providing a payment request to probe is one of the core reasons for this rpc change. If we are removing the payment request from the arguments that will be counter-productive to the usability by adding additional steps to decode.

Also there will be other invoice formats (e.g. bolt 12) or use cases that we may need to support here

Keeping the API future compatible with bolt12 is a valid concern. Can that be handled internally by checking the format first for the invoice type? I believe a determination can be made my looking at the invoice string if it's bolt11 or 12

[hieblmi]

Thanks for the review @bitromortac!

I get your concern about being flexible with adaptations to the estimation if new requirements like bolt12 come in, without having to come up with a new interface, but yes that reduces the ease to use this API. One benefit of providing all params in the proto that you mentioned would be that they could be filled into the graph based estimation, which currently only allows for pubKey and amount. But for the ease of use of this API we could definitely parse the params based on the invoice format.

[hieblmi]

Once again thanks for the thorough review @ProofOfKeags + @bitromortac, I've addressed all your comments. Most notably I restructured isLsp to only check what its name implies, and added prepareLspRouteHints to handle the extraction of adjustedRouteHints which allow probing the LSP. I've also made the requested changes to tests and itests.

This PR is ready for another review round.

[hieblmi]

Once again thank you @bitromortac for this thorough review journey. The handling of route hints by lnd has been especially insightful for me.