Enhance Lsp Heuristic when probing a payment by ziggie1984 · Pull Request #10396 · lightningnetwork/lnd

ziggie1984 · 2025-11-26T16:39:37Z

btochi · 2025-11-28T16:17:56Z

lnrpc/routerrpc/router_server.go

+// three rules:
+//  1. If the invoice target is a public node (exists in graph) => isLsp = false
+//     (can route directly to the target)
+//  2. If all destination hop hints are private nodes => isLsp = false


"destination hop hint" is a bit ambiguous. Would "If for each route hint the last node before the target is a private node, then isLSP returns false" be more clear?

Although this is not a problem for Muun, I'm making a note that if there was a single route hint that looked like:

Public Node ---> Private Node ---> Target Node

then isLSP would return False (as the node immediately before the target node is private).

Ideally we would probe the last public node of each route hint (which might not be the one before last).

I don't know of any LSP that provides invoices with route hints like the one above though.

yeah I think it's ok to assume LSP will always provide a routehint slice with the last entry being public.

btochi · 2025-11-28T16:24:56Z

lgtm!

ziggie1984 · 2025-11-28T23:31:35Z

We limit the probing of different LSPs to 3 to prevent any griefing and inconvenience for the user of the rpc probe command.

The comment was incorrectly referring to HasLightningNode but the function is named HasNode. Update the comment to match the actual function name.

This commit adds the HasNode function to the RouterBackend struct, which checks if a node exists in the graph (i.e., has public channels). This function is needed by the LSP detection heuristic to determine if a node is publicly reachable. The function is wired up in rpcserver.go to query the graph database.

ziggie1984 · 2025-11-30T07:42:41Z

/gemini review

gemini-code-assist

Code Review

This pull request significantly enhances the LSP detection heuristic used for fee estimation in EstimateRouteFee. The new logic is more robust, handling multiple LSPs by probing up to three unique providers and returning the worst-case fee estimate for conservative budgeting. This change improves flexibility and adds griefing protection. The code is well-structured, clearly commented, and includes comprehensive integration and unit tests to validate the new behavior. Overall, this is a high-quality improvement.

gemini-code-assist · 2025-11-30T07:44:11Z

docs/release-notes/release-notes-0.20.1.md

+   number of probed LSPs. It enhances the previously LSP design by being more
+   generic and more flexible.


There's a minor grammatical error here. "previously" should be "previous".

Suggested change

number of probed LSPs. It enhances the previously LSP design by being more

generic and more flexible.

number of probed LSPs. It enhances the previous LSP design by being more

generic and more flexible.

hieblmi

Great work @ziggie1984, thank you for the changes.

I've done a first round review on this PR and found some items I left comments for.

hieblmi · 2025-12-01T08:27:10Z

lnrpc/routerrpc/router_server.go

+	// Probe up to 3 LSPs and track the most expensive route for worst-case
+	// fee estimation. This is a precautionary measure to prevent the
+	// estimation from taking too long and also a griefing protection.
+	const maxLspsToProbe = 3


Please make this a public constant so we can reference it from tests.
Additionally, we could make this value configurable to give the user max. control.

@gemini-code-assist should we export this variable to make this available in itests or keep it unexported in this package so that it is restricted in that package.

Hi @ziggie1984,

Regarding maxLspsToProbe, exporting it as a public constant (e.g., MaxLspsToProbe) would be beneficial for integration tests (itests). This allows tests to directly reference the value, improving test clarity and maintainability. For example, if the value were to change in the future, tests that rely on this specific limit would automatically reflect the change without needing manual updates to hardcoded values in test descriptions or assertions.

While @hieblmi also suggested making it configurable, that would be a larger change involving adding it to the configuration system. For the immediate need of testability, simply exporting the constant is a good first step.

I recommend exporting it.

Suggested change

const maxLspsToProbe = 3

const MaxLspsToProbe = 3

@gemini-code-assist I don't think we should make this a config variable, because normally having invoices with more than 3 different routehint slices is almost very unlikely, having an extra config value for this seems over the top.

Hi @ziggie1984,

I agree with your assessment. Given that it's unlikely for invoices to have more than 3 different route hint slices, making maxLspsToProbe a configurable variable would indeed be over the top and add unnecessary complexity.

Exporting it as a public constant, as previously suggested, addresses the testability requirement effectively without introducing configuration overhead for a value that is expected to remain largely static or only change infrequently through code updates. This keeps the code clean and focused on its primary purpose while still allowing itests to reference it.

Thanks for the clarification!

@gemini-code-assist So I am not going to export the variable because this logic can only be tested implicitly meaning that I never use this variable hence there is no point in exporiting it.

Hi @ziggie1984,

I understand your perspective that the logic is tested implicitly. However, exporting maxLspsToProbe as a public constant (MaxLspsToProbe) still offers a significant benefit for test maintainability, even if the variable isn't directly used in the test's operational logic.

The itest/lnd_estimate_route_fee_test.go file, for instance, has a test case that explicitly mentions "max 3 LSPs probed". If the value of maxLspsToProbe were to change from 3 to, say, 5 in the future, any hardcoded 3 in the test's assertions or setup would become outdated and potentially lead to a brittle test that fails for the wrong reasons.

By exporting it, the test could reference routerrpc.MaxLspsToProbe directly in its assertions. This means:

Clarity: The test explicitly states it's testing against the configured maximum, not an arbitrary number.

Maintainability: If the constant's value changes, the test automatically adapts without needing manual updates to hardcoded numbers within the test itself.

This makes the test more robust and less prone to breaking when internal constants are adjusted. It's about ensuring the test's expectations align with the code's current constants, rather than relying on duplicated magic numbers.

I still recommend exporting it for these reasons.

ok good point makes sense will do it and explicitly test for the value of the constant in the itest.

lnrpc/routerrpc/router_server.go

hieblmi

Apart from two nits this LGTM 💾

hieblmi · 2025-12-01T14:01:08Z

lnrpc/routerrpc/router_server.go

+//  1. If the invoice target is a public node (exists in graph) => isLsp = false
+//     (can route directly to the target).
+//  2. If at least one destination hop hint is public => isLsp = true.
+//  3. If all destination hop hints are private nodes => isLsp = false.


Should we add a comment to 3. that the expectation in this case is that at least one of the nodes along a route hint should have a public node?

yes will add thanks

hieblmi · 2025-12-01T14:01:25Z

lnrpc/routerrpc/router_server.go

-	return true
+	// Rule 3: If all destination hop hints are private nodes (not in the
+	// graph), this is not an LSP so we try to route directly to the
+	// destination. .


nit: remove period

This commit implements a comprehensive LSP (Lightning Service Provider) detection heuristic and updates the payment probing logic to handle multiple LSPs with worst-case fee estimation. Key changes: 1. LSP Detection Heuristic (isLSP function): Implements three rules to detect LSP setups: - Rule 1: If invoice target is public → NOT an LSP (route directly) - Rule 2: If at least one destination hop is public → IS an LSP - Rule 3: If all destination hops are private → NOT an LSP 2. LSP Route Preparation (prepareLspRouteHints function): - Groups route hints by unique public LSP nodes - Filters out non-LSP routes based on the heuristic - Tracks worst-case fees and CLTV delays for each LSP - Returns adjusted route hints with LSP hop stripped 3. Multi-LSP Probing (probePaymentRequest updates): - Probes up to 3 unique LSPs maximum (griefing protection) - Selects the WORST-CASE (most expensive) route for conservative fee estimation - Adds comprehensive debug logging for worst-case selection process - Properly formats vertex logging using %v (calls Vertex.String()) The worst-case approach ensures users won't be surprised by higher fees when the actual payment is sent, providing a more conservative and reliable fee estimate. This commit also adds extensive unit test coverage for the LSP detection heuristic and route preparation logic. TestIsLsp: - Edge cases: empty route hints, nil scenarios - Rule 1: Public invoice target (3 tests) - Rule 2: All private destination hops (4 tests) - Rule 3: At least one public destination hop (6 tests) TestPrepareLspRouteHints: - LSP grouping and filtering logic - Worst-case fee selection across route hints - Worst-case CLTV delta tracking - Adjusted route hints validation (LSP hop stripped) - Multi-LSP scenarios with different fees

This commit enhances the integration test to validate the LSP heuristic end-to-end with real network topology and payment probing. Network topology additions: - Added Frank node as a private destination - Created multi-LSP test scenario with Bob, Eve, and Dave as LSPs New test cases: 1. "probe based estimate, public target with public hop hints" - Validates Rule 1: public invoice target routes directly - Even with public hop hints, direct routing is used - Expected: standard single-hop fees 2. "probe based estimate, multiple different public LSPs" - Validates multi-LSP worst-case selection - Frank has routes through Bob (low fee), Eve (HIGH fee), Dave (medium) - Expected: Eve's worst-case fees (most expensive) - Tests griefing protection (max 3 LSP probes)

kilrau · 2025-12-03T13:00:09Z

lgtm!

yyforyongyu · 2025-12-04T07:29:32Z

I think this should be put in 0.21 as minor releases are not meant for adding new features? cc @saubyk

saubyk · 2025-12-04T18:28:40Z

I think this should be put in 0.21 as minor releases are not meant for adding new features? cc @saubyk

yes, but will make an exception here to reduce potential business impact for the users.

bitromortac

Code LGTM ⚡, great tests to assert the heuristic @ziggie1984

I think the current approach is acceptable, but I wanted to also mention a couple of points that represent a downside of the isLSP heuristic here (some of those downsides were also present before) where I can't rate their importance (cc @saubyk) and they demonstrate that setting up a single heuristic can fail in other circumstances and is quite complex.

The UX can be worse because we need to probe to up to three nodes now (before we only did a single probe).
It's not possible for an LSP to keep all their nodes and channels unannounced. This would be possible with hop hints of length two with some public entry points (other routing nodes) and private destination hops (LSP's nodes), which is classified as a non-LSP case here.
We can have the setup where a public target node wants to use an LSP, because they don't have inbound liquidity (single fake hop hint with public destination hop to signal a JIT channel). We would probe to the target and fail because all other channels failed (no inbound) and we can't use the hop hint as the channel doesn't exist (we get a wrong forwarding error message).
If we detect an LSP in the case of two included separate hop hints, one single hop hint (public destination hop) and a two-hop hint (private destination hop), we throw away the two-hop hint for probing (in the LSP mode we don't mix LSP and non-LSP hop hints), reducing the reliability/redundancy for estimating whether liquidity is present.
A public LSP can't add purely hop hints of the form [public LSP -> intermediate private node -> private target] (I don't know a good use case for that).

Long-term I think we could use a more robust solution that only probes to the public parts of the invoice (the entry public hops, see #9994 (comment) for a proposal), but it also has the problem of longer probing times (the first bullet point) because each public entry point needs to be probed and it can be less accurate (needs more research).

bitromortac · 2025-12-08T15:49:08Z

lnrpc/routerrpc/router_server_test.go

+				// Should use worst-case CLTV delta.
+				require.Equal(t, aliceHopHint2.CLTVExpiryDelta,
+					group.LspHopHint.CLTVExpiryDelta)
+			},


nit: it could give more coverage if we set aliceHopHint1 to have the greater CLTV expiry delta because we merge the policies, taking the worst case from all

saubyk · 2025-12-08T17:55:02Z

Thanks for the detailed analysis here @bitromortac

I think we made a mistake with building the isLSP heuristic, without demanding standardization, resulting in an open ended feature which requires adjustments as user requirements evolve.

To guard against further scope creep in this area, we will stop accepting any further changes (beyond the scope of this pr) until a specification is proposed and agreed upon.

saubyk assigned ziggie1984 Nov 27, 2025

saubyk added this to the v0.20.1 milestone Nov 27, 2025

saubyk added the routing fee estimation label Nov 27, 2025

saubyk added this to lnd v0.20 Nov 27, 2025

saubyk moved this to In progress in lnd v0.20 Nov 27, 2025

ziggie1984 requested a review from hieblmi November 27, 2025 17:48

btochi reviewed Nov 28, 2025

View reviewed changes

ziggie1984 force-pushed the enhance-lsp-heuritic branch from d5573f2 to fadffe7 Compare November 28, 2025 23:22

ziggie1984 marked this pull request as ready for review November 28, 2025 23:24

ziggie1984 force-pushed the enhance-lsp-heuritic branch from fadffe7 to 5bfa331 Compare November 28, 2025 23:30

ziggie1984 added 2 commits November 29, 2025 01:04

graph/db: fix HasNode comment

06886e7

The comment was incorrectly referring to HasLightningNode but the function is named HasNode. Update the comment to match the actual function name.

ziggie1984 force-pushed the enhance-lsp-heuritic branch from 5bfa331 to 226488e Compare November 29, 2025 00:10

gemini-code-assist bot reviewed Nov 30, 2025

View reviewed changes

ziggie1984 force-pushed the enhance-lsp-heuritic branch 2 times, most recently from 0da1c35 to 44f7fde Compare November 30, 2025 08:09

hieblmi reviewed Dec 1, 2025

View reviewed changes

ziggie1984 requested a review from bitromortac December 1, 2025 10:09

ziggie1984 force-pushed the enhance-lsp-heuritic branch 2 times, most recently from 1120f2d to 025bc56 Compare December 1, 2025 13:17

hieblmi approved these changes Dec 1, 2025

View reviewed changes

ziggie1984 added 4 commits December 1, 2025 18:07

docs: update api documentation for estimateRouteFee

34619d4

docs: add release-notes for LND 20.1

de0424e

ziggie1984 force-pushed the enhance-lsp-heuritic branch from 025bc56 to de0424e Compare December 1, 2025 17:08

ziggie1984 moved this from In progress to In review in lnd v0.20 Dec 3, 2025

bitromortac approved these changes Dec 8, 2025

View reviewed changes

ellemouton merged commit bc670fa into lightningnetwork:master Dec 9, 2025
35 of 39 checks passed

github-project-automation bot moved this from In review to Done in lnd v0.20 Dec 9, 2025

ziggie1984 mentioned this pull request Dec 12, 2025

backport/enhance lsp heuritic #10444

Merged

		number of probed LSPs. It enhances the previously LSP design by being more
		generic and more flexible.

Conversation

ziggie1984 commented Nov 26, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

btochi commented Nov 28, 2025

Uh oh!

ziggie1984 commented Nov 28, 2025

Uh oh!

ziggie1984 commented Nov 30, 2025

Uh oh!

gemini-code-assist bot left a comment

Choose a reason for hiding this comment

Code Review

Uh oh!

gemini-code-assist bot Nov 30, 2025

Choose a reason for hiding this comment

Uh oh!

hieblmi left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Dec 1, 2025

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Dec 1, 2025

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Dec 1, 2025

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

hieblmi left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kilrau commented Dec 3, 2025

Uh oh!

yyforyongyu commented Dec 4, 2025

Uh oh!

saubyk commented Dec 4, 2025

Uh oh!

bitromortac left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

saubyk commented Dec 8, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

ziggie1984 commented Nov 26, 2025 •

edited

Loading