{"id":"b5396fb3-6893-45fc-9482-1eac835fd014","arxiv_id":"2501.11419","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Dijkstra-based Lightning Network routing algorithm is correct and polynomial for consistent (non-negative-rate) fee functions, and the routing problem is NP-hard for arbitrary fee functions.","lead":"This paper studies the standard path-finding algorithm used in Lightning Network payment routing. It proves that the algorithm is correct and fast when channel fees satisfy a simple monotonicity condition, but that general fee structures make the problem NP-hard.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's fee relaxation on line 9 uses the original payment amount a instead of the accumulated amount a + c(v), contradicting Equation (4); as printed, the algorithm computes incorrect fees even on the paper's own Figure 3 example, so the correctness proofs do not apply to the stated…","rationale":"I read the paper as attempting to prove that the Lightning Network's fee structure (affine, non-negative rates) makes the Dijkstra variant correct and polynomial, and that arbitrary inconsistent fee maps make the problem NP-hard. The strongest supporting chain is Lemma 5 (correctness of the unbounded variant via time-dependent network theory) and Theorem 7 (balance pruning preserves correctness). The single most load-bearing point is the fee relaxation on line 9. Equation (4) is unambiguous: when traversing a transpose arc (v,v') carrying amount x to v, the fee charged is fbr((v,v'), x), and x = a + c(v). The pseudocode instead uses fbr((v,v'), a). This makes the printed algorithm disagree with the paper's own Figure 3 computation by 0.6 units of fee, and the error compounds along a path. It also invalidates Lemma 5, because the TDN algorithm of Kaufman et al. computes arc cost as a function of the arrival time at the tail, not the original departure time. Without Lemma 5, Theorem 7 lacks a correct base algorithm to prune from. The reader's verdict flagged this as a mechanical error and assigned CONDITIONAL; I agree with that outcome because the intended claims are almost certainly recoverable by changing one line and adding a rigorous dominance argument for the pruning step. I do not elevate to REJECT because the conceptual framework (FIFO consistency + dominance) is sound and the empirical bidirectional variant does not depend on the flawed fee formula in a way that would change its measured speedup. The other issues mentioned by the reader (Algorithm 2's termination set, missing Theorem 5 reference) are real but secondary; the line 9 bug is the one that directly falsifies the central correctness claim for the stated algorithm. The proposed concrete test settles the matter immediately: running the printed algorithm on Figure 3 will either reproduce the wrong fee, confirming the bug, or (if some hidden interpretation rescues line 9) produce 7.6, which would force a different reading of c(v). Either way, the test is decisive for the main theorem's validity as written.","tokens_in":18245,"tokens_out":11366,"duration_ms":114365,"concrete_test":"Implement Algorithm 1 exactly as printed and run it on the Figure 3 graph with a=10. Record the fee and path returned for s→t. The printed line 9 should yield total fee 7.0 for the path s-i-t, whereas the true lowest fee computed by Equation (4) is 7.6 (amount 17.6 sent at s). Next, change only line 9 to cv' = c(v) + fbr((v,v'), a + c(v)) and rerun; verify it returns 7.6 and the correct path. To further validate the corrected algorithm, generate random small graphs with affine fees fb≥0, fr≥0 and random balances, compare the corrected Algorithm 1 against brute-force enumeration of all feasible paths for many (s,t,a) triples; if they always agree, the intended claim holds with the fix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Algorithm 1 correctly computes a lowest-fee feasible path when the fee map is consistent (Theorem 7) and runs in O(|E| + |V| log |V|) (Theorem 8). This hinges on line 9, which sets cv' = c(v) + fbr((v,v'), a). But Equation (4) and the surrounding text define the fee on a GT arc (v,v') as evaluated at the amount actually transferred to the tail v, which is a + c(v), not the constant a. The paper's own worked example confirms this: after reaching i with c(i)=3, the next arc (i,s) in GT should charge fbr((s,i), 13) = 2 + 0.2*13 = 4.6, so c(s)=7.6; line 9 as printed computes fbr((s,i), 10)=4 and c(s)=7. This is not a cosmetic typo: because c(v) is underestimated, the balance check on later arcs uses an underestimated amount a+c(v), so the algorithm may declare a path feasible when the true required amount exceeds some arc's balance, and it will generally return paths with incorrect (too low) fees. Definition 2 carries the same bug into Algorithm 1' (it only swaps fbr for fbr∞ on line 9), so Lemma 5's invocation of the time-dependent Dijkstra correctness result from Kaufman et al. does not apply to the algorithm as written: a correct TDN relaxation must evaluate the travel-time function at the departure time from the tail, i.e., at a+c(v). Consequently, the proof chain Lemma 5 → Theorem 7 → Theorem 8 does not establish correctness or complexity for the printed algorithms. The pruning argument in Theorem 7 is also asserted rather than rigorously demonstrated, but the line 9 mismatch is the more fundamental and directly falsifiable defect. The intended algorithm is likely correct if line 9 is fixed to cv' = c(v) + fbr((v,v'), a + c(v)), and the consistency (FIFO) condition then supports a dominance argument for balance-feasible pruning, but the current text does not contain that corrected algorithm or proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes a Dijkstra-style algorithm (Algorithm 1) for path planning in payment channel networks (PCNs), specifically the Lightning Network (LN). It claims that if the fee map is 'consistent' (a FIFO-type condition), the algorithm correctly finds a lowest-fee path satisfying balance constraints and runs in O(|E| + |V| log |V|). For arbitrary inconsistent fee maps, it claims the problem is NP-hard. A second contribution is a 'partial bidirectional' variant (Algorithm 2) with the same asymptotic complexity, plus an empirical evaluation on an LN snapshot. The paper also solves a recurrence for accumulated fees along a path and proves that the LN's linear fee function is consistent.","tokens_in":18582,"tokens_out":11676,"duration_ms":111096,"significance":"If the results were fully correct, this would be a valuable formal analysis of a heuristic widely used in LN implementations (LND, Core Lightning), giving the first correctness and complexity guarantees under a realistic consistency condition, plus a hardness result for the general case. The bidirectional variant is a small but potentially useful practical improvement, and the consistency observation about the LN's fee structure is nontrivial context for protocol design. The paper also provides a closed-form solution to the fee-accumulation recurrence and ships Python code to verify it, which is a strength. However, the central correctness claims do not hold for the algorithms as printed, and several proof steps are asserted rather than demonstrated; these issues must be resolved before the contribution can be accepted.","major_comments":[{"comment":"The relaxation step computes cv' = c(v) + fbr((v,v'), a), but the fee on the transposed arc must be evaluated at the accumulated amount a + c(v), and on the reverse original arc (v',v), not on (v,v'). Equation (4) and the example in Section 4 require this: after reaching i with c(i)=3 in Figure 3, the next fee is fbr((s,i), 13)=4.6, so c(s)=7.6, whereas line 9 yields fbr((s,i),10)=4 and c(s)=7. The same error propagates through Algorithm 1' (Definition 2) and Algorithm 2 (line 11). Because Lemma 5's appeal to Kaufman et al.'s time-dependent Dijkstra requires evaluating the travel-time function at the departure time, the correctness proofs do not apply to the printed algorithms. This is a load-bearing error for Theorem 7 and Theorem 10.","section":"Algorithm 1, line 9; Definition 2; Equation (4)"},{"comment":"The balance condition c(v)+a <= b(v,v') checks the balance of the wrong arc and uses the amount before the fee is added. The amount that must fit in the channel is a + c(v') (the amount at the head of the GT arc), which equals a + c(v) + fbr((v',v), a+c(v)) under the correct relaxation, and the relevant balance is that of the original arc (v',v). As printed, the algorithm can declare a path feasible even when the true required amount exceeds the channel balance, so the feasibility part of Theorem 7's correctness claim is unsupported.","section":"Algorithm 1, line 10; Algorithm 2, line 8"},{"comment":"The pruning argument is asserted, not proven. The proof states that Algorithm 1 prunes precisely the infeasible paths and that the optimal feasible path therefore remains in the pruned search space, but no invariant is established showing that the tentative costs c(v) correctly track the accumulated amount a+c(v) for partially explored paths, nor that the balance checks preserve an optimal feasible path under the order of vertex processing. The boundedness assumption on fbr is not used to bridge this gap. A rigorous proof must relate the pruned search to the (corrected) Algorithm 1' and show the optimal feasible path is not eliminated.","section":"Theorem 7, proof"},{"comment":"The NP-hardness proof is a two-sentence appeal to Lemma 4 and Zeitz [33], and it is not sufficient. Lemma 4's equivalence is not formalized for balance constraints, and the 'forbidden waiting' problem's structure is not shown to be encodable by LN fee maps of the form fb(e)+fr(e)*a with the balance constraints. The proof needs at least a precise reduction or a rigorous statement of how arbitrary non-consistent fee maps simulate the hardness source. As written, Theorem 9 is not established.","section":"Theorem 9, proof"},{"comment":"Algorithm 2's early termination condition is not justified. The proof cites a nonexistent 'Theorem 5' (intended Lemma 5) and does not prove that the first popped neighbor v of s in GT yields a lowest-fee path to s. The text preceding the algorithm relies on a transformation that sets the fees of arcs leaving s to zero, but Algorithm 2 does not apply that transformation, and the proof does not use the consistency property to rule out better paths through vertices with larger c(v). Additionally, the balance check at line 8 uses the pre-fee amount and the wrong balance quantity, as in Algorithm 1. Hence the correctness of the bidirectional variant is not demonstrated.","section":"Theorem 10, proof and Algorithm 2, lines 6-9"}],"minor_comments":[{"comment":"The proof refers to 'Theorem 5' but no Theorem 5 exists; the intended reference appears to be Lemma 5. This should be corrected.","section":"Section 6, Theorem 10 proof"},{"comment":"The sentence 'to transfer an amount a from vi to vj, we must first transfer a plus the fee in question to vi' is correct for the model, but the definition of ei in the recurrence (2) could be stated more explicitly (which of the two arcs is meant) to avoid confusion with the transposed graph used later.","section":"Section 3, Equation (2) discussion"},{"comment":"The experimental results are reported without implementation code or details of the priority-queue and graph representations. Since the printed algorithms contain the fee/balance bugs, it is unclear what implementation was actually benchmarked; the reported vertex counts and wall-clock reductions are therefore hard to reproduce or interpret.","section":"Section 7, experimental setup"},{"comment":"The comment in the code says 'directly using Equation (6)' but the cited equation is (7) in the theorem. Also, the index notation in the proof of Theorem 11 could be simplified; the product limits in equations (10)-(13) are error-prone as written.","section":"Appendix A, Listing 1"},{"comment":"Papers should be checked for typos such as 'Inter i9-14900K' (Intel) and the use of 'Theorem 5' instead of 'Lemma 5'. These are minor but contribute to an impression of insufficient proofreading.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important and timely problem, and its conceptual framework—consistency conditions, TDN equivalence, recurrence solution—is promising. However, the central algorithm as printed is incorrect even on the authors' own example, the balance checks are wrong, and the proofs of Theorems 7, 9, and 10 rely on unsupported assertions or misapplied references. These are not cosmetic; they affect the core claims. The good news is that the errors appear fixable: correcting the relaxation to c(v) + fbr((v',v), a+c(v)) and the balance condition to involve a+c(v') on the reverse arc would align the pseudocode with Equation (4). A revision would need to rework the proofs of Lemmas 4-5, Theorem 7, and Theorem 10 with a proper invariant, and replace the two-sentence NP-hardness proof with a real reduction. I recommend major revision rather than rejection, because the intended results are plausible and significant, but the current manuscript cannot be accepted as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read of Corcoran and Lewis. The paper deserves refereeing, but it's not ready as is.\n\nThe genuinely new contribution is the equivalence between PCN path planning and time-dependent network search (Lemma 4). That's a clean way to import FIFO consistency and NP-hardness results, and it's stated clearly. The consistency condition for the Lightning fee structure (non-negative rates) is trivial but nice to have explicit. The NP-hardness pointer to Zeitz is plausible. The partial bidirectional variant is a reasonable practical idea, and the empirical speedup is suggestive even without released code or significance tests.\n\nThe problem is that the printed Algorithm 1 does not match the paper's own equations. On line 9 it computes cv' = c(v) + fbr((v,v'), a), evaluating the fee at the original payment amount a, whereas Equation (4) and the worked example require evaluating at a + c(v), the amount actually at the tail. Concretely, after reaching i with c(i)=3, the next arc in GT should charge fbr((s,i),13)=4.6, but line 9 gives fbr((i,s),10)=4.0. That underestimates fees and can declare a path feasible when it isn't. So the correctness proof (Theorem 7) doesn't apply to the algorithm as written. The same bug carries into Algorithm 2. This is fixable—change the amount to a + c(v)—but the current text doesn't contain the corrected algorithm.\n\nTwo smaller issues. Theorem 7's pruning argument is asserted rather than proved; the bounded-range assumption is mentioned but not justified. And Theorem 10's proof cites a non-existent Theorem 5; Algorithm 2's correctness needs a real argument. On the other hand, the reader's worry about Algorithm 2 using the wrong neighbor set is unfounded: {u : (u,s) ∈ E} in GT is exactly the set of vertices that can be appended to reach s, so the termination condition is correct.\n\nIf the fees are fixed, the core claims are likely correct: consistent fee maps give polynomial correctness, arbitrary maps give NP-hardness. As written, though, the central theorem is not proven for the stated algorithm. I'd send it to review, with a strong request to fix the pseudocode and tighten the pruning argument.","headline":"The paper's core mapping is solid, but the printed Algorithm 1 computes fees on the wrong amount, so the correctness proof doesn't cover the stated algorithm; fix that and it's a worthwhile contribution.","tokens_in":19209,"tokens_out":8085,"would_cite":true,"duration_ms":72219,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R10","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"A proof shows that the Lightning Network's Dijkstra-style routing algorithm is correct and near-linear exactly when channel fees are consistent, and that arbitrary fee maps make the problem NP-hard.","keywords":["payment channel networks","Lightning Network","path planning","Dijkstra's algorithm","time-dependent networks","NP-hardness","fee consistency","bidirectional search"],"falsifier":"A concrete check: on the paper's own Figure 3 example, compare the fee returned by the pseudocode (which evaluates the arc fee at the constant amount $a$ on line 9) with the fee computed by Equation (4) on the accumulated amount. If the two disagree, the correctness theorem applies to the intended algorithm, not to the literal pseudocode.","tokens_in":17932,"feed_emoji":"⚡","tokens_out":10665,"duration_ms":95223,"temperature":0.7,"pith_summary":"Payment channel networks such as the Lightning Network route payments by finding a low-fee path through a network of channels, each charging a fee that depends on the amount sent to it. This paper proves that the Dijkstra-style algorithm actually used by Lightning implementations is correct and runs in time $O(|E|+|V|\\log|V|)$ exactly when the fee map is 'consistent': sending a larger amount through a channel never results in a smaller amount arriving on the other side. The paper further shows that Lightning's linear base-fee-plus-rate fee formula satisfies this condition, and that if fees are allowed to be arbitrary, the same path planning problem becomes NP-hard. A small modification to the algorithm, a partial bidirectional search, is shown empirically to explore fewer vertices on a real Lightning Network snapshot.","feed_headline":"Lightning routing is provably fast when fees are consistent","feed_subtitle":"Dijkstra-style routing is correct and near-linear when channel fees are consistent; arbitrary fees make it NP-hard.","key_machinery":"The load-bearing mechanism is the consistency (or monotonicity) property of the fee map: $a+f(e,a)\\le a'+f(e,a')$ whenever $a\\le a'$. This condition plays the role of a FIFO / non-decreasing-horizon requirement in time-dependent networks; it guarantees that a greedy, label-setting search never needs to revisit a vertex with a larger accumulated fee. The paper reduces Lightning path planning to a minimum-time problem on a time-dependent network, transfers the classical correctness result for that setting, and then shows that Algorithm 1 prunes the search space of Algorithm 1' to feasible paths, yielding the same near-linear bound. The closed-form solution of the amount recurrence $a_{i-1}=a_i+f_{br}(e_i,a_i)$ supplies the formula for the amount that must be sent at each hop.","core_discovery":"The central claim is that the Lightning Network's path planning algorithm, a variant of Dijkstra's algorithm that reverses the search direction and accumulates fees, is correct and has complexity $O(|E|+|V|\\log|V|)$ precisely when the channel fee map $f_{br}$ is consistent in the sense of Definition 1: for every arc $e$ and amounts $a \\le a'$, $a + f_{br}(e,a) \\le a' + f_{br}(e,a')$. The proof works by equating the payment routing problem with a lowest-time path problem in a time-dependent network whose travel times are the fee amounts, then applying the known correctness and complexity results for Dijkstra-style search in such networks. Under this condition the algorithm returns the true lowest-fee feasible path; if the fee map is arbitrary and inconsistent, the paper proves that the path planning problem is NP-hard. It also proves that the Lightning Network's fee formula $f_{br}(e,a)=f_b(e)+f_r(e)\\,a$ with nonnegative rate is always consistent, and introduces a partial bidirectional search variant whose correctness is established by the same argument and whose practical speedup is demonstrated by simulation.","pith_inferences":["Extending the paper's logic","consistency should become a first-class design requirement for any new PCN fee schedule","so that non-linear or state-dependent fee functions are checked against the condition before deployment. The closed-form recurrence in the appendix could be used to compute the required onward amount exactly without iterating each hop","reducing per-hop arithmetic in future routing engines. Because correctness depends on the amount used at each hop","implementations should verify that their fee computation matches Equation (4) on the accumulated amount","a discrepancy between the published pseudocode and the intended formula is testable on real node software."],"forward_implications":["New payment channel networks that want efficient routing should design their fee schedules to satisfy $a+f(e,a)\\le a'+f(e,a')$ for all $a\\le a'$.","Lightning's existing linear fee formula already meets this condition, giving a theoretical explanation for why its routing search is usually fast.","If a network operator uses a non-consistent fee map, no efficient exact algorithm can be guaranteed; the paper's NP-hardness result applies to the general case.","The partial bidirectional search variant can be dropped into existing implementations without changing asymptotic complexity and offers a measurable reduction in explored vertices on hub-and-spoke topologies.","The correctness guarantee carries over to any payment channel network whose fee map is consistent, not just to Lightning."],"supporting_citations":[{"why":"Supplies the correctness and complexity theorem for Dijkstra-style search in time-dependent networks with consistent travel-time maps, which the paper transfers to payment routing.","marker":"[29]"},{"why":"Defines the 'forbidden waiting' time-dependent shortest-path problem that the LN path planning problem is shown to be equivalent to.","marker":"[32]"},{"why":"Proves that the forbidden waiting problem is NP-hard, which yields the paper's NP-hardness theorem for inconsistent fee maps.","marker":"[33]"},{"why":"Provides the standard technique used to solve the amount recurrence and obtain the closed-form expression for the amount to send at each hop.","marker":"[25]"},{"why":"Gives the branching-factor analysis used to estimate the number of vertices explored by unidirectional and bidirectional searches.","marker":"[34]"},{"why":"Supplies the payment-amount distribution used to construct realistic simulated payments for the empirical evaluation.","marker":"[36]"}],"fun_headline_variants":["Consistent fees keep Lightning routing solvable","Routing in payment channels: easy if fees align, else NP-hard","Payment routing: consistent fees guarantee polynomial time","Lightning's Dijkstra variant is correct only with consistent fees"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that channel fees are consistent: sending a larger amount through a channel never leaves a smaller amount arriving out the other side. The proof of correctness and efficiency collapses if this condition fails.","fun_headline_variants_meta":{"raw":{"variants":["Consistent fees keep Lightning routing solvable","Routing in payment channels: easy if fees align, else NP-hard","Payment routing: consistent fees guarantee polynomial time","Lightning's Dijkstra variant is correct only with consistent fees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000217,"raw_usage":{"total_tokens":1465,"prompt_tokens":1006,"completion_tokens":459,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":395}},"tokens_in":622,"tokens_out":459,"duration_ms":5219,"temperature":1.0,"reasoning_tokens":395,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:18:09.934677+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: on the paper's own Figure 3 example, compare the fee returned by the pseudocode (which evaluates the arc fee at the constant amount $a$ on line 9) with the fee computed by Equation (4) on the accumulated amount. If the two disagree, the correctness theorem applies to the intended algorithm, not to the literal pseudocode.","supporting_citations":[{"cited_title":"Fastest paths in time-dependent networks for intelligent vehicle-highway systems application.Journal of Intelligent Transportation Systems, 1(1):1–11, 1993","cited_arxiv_id":null,"evidence_quote":"Supplies the correctness and complexity theorem for Dijkstra-style search in time-dependent networks with consistent travel-time maps, which the paper transfers to payment routing."},{"cited_title":"Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length.Journal of the ACM, 37(3):607–625, 1990","cited_arxiv_id":null,"evidence_quote":"Defines the 'forbidden waiting' time-dependent shortest-path problem that the LN path planning problem is shown to be equivalent to."},{"cited_title":"NP-hardness of shortest path problems in networks with non-fifo time-dependent travel times.Information Processing Letters, 179:106287, 2023","cited_arxiv_id":null,"evidence_quote":"Proves that the forbidden waiting problem is NP-hard, which yields the paper's NP-hardness theorem for inconsistent fee maps."},{"cited_title":"CRC Press, 2002","cited_arxiv_id":null,"evidence_quote":"Provides the standard technique used to solve the amount recurrence and obtain the closed-form expression for the amount to send at each hop."},{"cited_title":"ArtificialIntelligence:amodernapproach","cited_arxiv_id":null,"evidence_quote":"Gives the branching-factor analysis used to estimate the number of vertices explored by unidirectional and bidirectional searches."},{"cited_title":"Research report: The lightning network grew by 1212% in 2 years, why it’s important to pay attention","cited_arxiv_id":null,"evidence_quote":"Supplies the payment-amount distribution used to construct realistic simulated payments for the empirical evaluation."}],"review_version":1}