Pith. sign in

REVIEW 3 major objections 4 minor 27 references

Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that payment channel network design and transaction selection can be approximated within O(p), and within O(sqrt(p)) when transaction patterns are clustered, using star and double-star topologies with LP-based accept/reject

desk verdict The problem framing is new and the star capacity lemma is clean, but the O(√p) theorem is unproved (Lemma 7's proof is a copy-paste) and the O(p) claim lacks the needed global comparison, so the advertised contributions are not supported as written. read the letter →

arxiv 2508.14524 v1 pith:CHX2OKBA submitted 2025-08-20 cs.DC cs.CR

Krishnendu Chatterjee , Jan Matyáš Křišťan , Stefan Schmid , Jakub Svoboda , Michelle Yeo This is my paper
classification cs.DCcs.CR
keywords BlockchainsCryptocurrenciesPaymentChannelNetworksThroughputOptimisationGraphAlgorithmsApproximation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies a two-stage optimization problem in payment channel networks: how p cooperating parties should open channels and allocate capacity, and then which payment requests they should accept or reject, to minimize the combined cost of channel creation, locked-in capacity, and rejected transactions. The authors prove that the problem is NP-hard, that a star topology costs at most twice the optimal capacity cost of any topology, and that an LP-guided algorithm on a star approximates the overall optimum within O(p). Under a stochastic-block-model assumption that transactions cluster into about sqrt(p) communities with at least 24 sqrt(p) times as much within-community as between-community volume, a double-star variant improves the guarantee to O(sqrt(p)). An empirical study of the Lightning Network estimates a within/between cluster volume ratio near 193, which the authors read as supporting the clustering assumption. If the bounds hold, network designers get a principled reason to use sparse, hub-based topologies with capacity reserves instead of dense meshes.

What carries the argument

The central object is the star topology, and its two-level variant the double star. A star has diameter 2 and only p-1 channels, so its capacity cost is within a factor 2 of any topology (Theorem 2); a double star has diameter 4 and incurs a factor 4. The LP relaxation for a star (Equation 1) fixes capacities on each side of every channel and outputs fractional accept/reject amounts. Algorithm 1 adds pairwise reserves scaled by sqrt(3)/2 times the largest LP-observed balance change, with a heap-based rule that accepts all fully accepted transactions and keeps rejection cost within (sqrt(3)+1) of optimal. For the improved bound, the double-star lets the algorithm handle inter-cluster transact

What would settle it

Take p parties split into sqrt(p) clusters of size sqrt(p) with uniform random transaction endpoints (clustering ratio 1), run Algorithm 2, and compare its total cost to the optimal cost; if the ratio grows faster than C sqrt(p) for any constant C, Theorem 10 fails. Alternatively, obtain actual Lightning Network transaction logs and compute the within-cluster to between-cluster volume ratio for sqrt(p)-sized clusters; if it falls below 24 sqrt(p), the theorem's precondition does not hold in practice.

Watch

Extended reading notes

Core claim

The paper shows that the joint problem of choosing a payment channel network topology over p cooperating parties and deciding which transactions to forward, while minimizing channel creation, capacity, and rejection costs, admits polynomial-time approximation algorithms with provable worst-case guarantees. The star graph is a 2-approximation for the capacity cost of any topology (Theorem 2 and Corollary 3). Extending the single-channel algorithm of [27], Algorithm 1 on a star is an O(p) approximation: its rejection cost is at most (sqrt(3)+1) times the optimal star rejection cost and its capacity cost is at most (1+(p-1)sqrt(3)) times the optimal star capacity cost (Theorem 6). If the transa

Load-bearing premise

The bounds hold only if the optimal solution's cost is well approximated by a star or double-star topology, and, for the improved O(sqrt(p)) result, if real transaction streams are actually as strongly clustered as the model requires, which the paper's Lightning measurement infers from topology rather than observes.

Editorial extensions

If this is right

  • A payment channel network over p parties can be designed within O(p) of optimal total cost using only a star topology, which has the minimum number of channels, p-1.
  • When transactions are strongly clustered, Algorithm 2 on a double star achieves O(sqrt(p)) approximation, so per-cluster local processing plus a central star is provably near-optimal.
  • Corollary 11 extends the guarantee: for any (m,k,t)-clustered sequence with t at least 24 sqrt(p), the algorithm is an O(max(m,k))-approximation, so the bound adapts to the actual number and size of clusters.
  • The algorithm accepts every transaction that the LP fully accepts, so the rejection cost is driven only by partially accepted transactions, a property that holds regardless of the volume of fully accepted or rejected transactions.
  • Because the single-channel transaction selection problem is NP-hard, the network problem is NP-hard as well; these algorithms provide worst-case approximation guarantees rather than exact solutions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same LP-plus-reserve machinery could likely be adapted to the online setting: reserves act as a hedge against unknown future transactions, so the pairwise accept/reject rule may yield a bounded competitive ratio.
  • The O(sqrt(p)) bound implies a design rule: partition parties into clusters of roughly sqrt(p) size and spend capacity on a star per cluster plus a central star, making between-cluster traffic the real bottleneck and giving network designers a target for encouraging local payments.
  • Because the empirical clustering ratio (~193) was estimated from network topology rather than observed transactions, the practical validity of the O(sqrt(p)) guarantee would need real Lightning transaction logs to confirm; until then it remains conditional.
  • If the clustering strength t drops below 24 sqrt(p), the approximation factor degrades, suggesting a continuous tradeoff between traffic locality and optimality that the paper does not fully quantify.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the joint problem of designing a payment channel network (PCN) topology among p parties and deciding which transactions in a given sequence to accept or reject, with channel creation, capacity, and rejection costs. The authors first give an LP lower bound for the capacity cost of serving all demands over a fixed graph (Section 3.1) and prove that a star is a 2-approximation for capacity cost (Theorem 2 / Corollary 3). They then adapt a single-channel algorithm from [27] to a star topology, claiming an O(p) approximation for general graphs (Algorithm 1, Theorem 6). Under an additional clustering assumption on the transaction distribution, they propose Algorithm 2 on a double-star topology and claim an O(√p) approximation (Theorem 10). The paper closes with an empirical study of the Lightning Network, claiming that the observed within-cluster vs. between-cluster transaction volume ratio supports the clustering assumption.

Significance. The problem is well motivated and the extension from a single channel to a network topology design is a natural next step. The LP lower bound in Lemma 1 and the diameter-based capacity bound in Theorem 2 are clean and appear sound. If the O(p) and O(√p) approximation guarantees were fully established, this would be a valuable contribution to the theory of payment channel networks. The paper also provides an empirical case study, which is refreshing, though its conclusiveness is limited by the issues described below. The main theoretical results are not yet convincingly proven as written.

major comments (3)
  1. [Appendix A.4, Lemma 7; Appendix A.5, A.6; Theorem 10] The proof of Lemma 7 is verbatim identical to the proof of Theorem 6 in Appendix A.3. Lemma 7 claims that a fractional transaction (s,t,x_i,y_i) can be altered to (s,t,x_i,y_i±α) to simulate moving α reserves, but the 'proof' discusses channel sizes, reserves √3 times, and rejection cost bounds—none of which addresses the stated claim. Since Lemmas 8 and 9 rely on Lemma 7, and Theorem 10 relies on Lemmas 8 and 9, the O(√p) guarantee is not established. Additionally, Lemma 8's proof invokes 'condition 3' and Appendix C.1 invokes 'condition 2' of the clustering conditions, but only condition 1 is defined in Section 5. The theorem statement and proof are therefore not fully specified.
  2. [Abstract, Section 4, Theorem 6] The abstract claims an O(p) approximation for the general problem with p parties, but Theorem 6 only bounds the cost of Algorithm 1 relative to the optimal star solution. To obtain an approximation for general graphs, one needs a comparison between the star-constrained optimum and the global optimum for the full objective (capacity plus rejection cost). Theorem 2 / Corollary 3 provide such a comparison only for the capacity cost of accepting all transactions, not for the combined objective with rejection costs. Without this missing step, the O(p) claim for unrestricted topologies does not follow from the current text.
  3. [Section 6, Table 1 and Fig. 6] The empirical study claims to validate the clustering assumption used in Theorem 10, namely (√p,√p,24√p)-clustering. The paper reports an aggregate within-to-between volume ratio of 193.2. For the network size considered, 24√p is likely larger than 193 (e.g., even for p=1000 it would be ≈759), so the stated threshold is not met. Moreover, individual clusters show ratios as low as 0.8 and 1.0. The statement that the results 'confirm our experimental hypothesis' is therefore not supported as written. The paper should report p explicitly, compare the ratio against 24√p, and discuss why the assumption is still reasonable or adjust the theoretical parameters.
minor comments (4)
  1. [Appendix A.5, proof of Lemma 8] The sentence 'From the condition3 of the clustering conditions' should read 'condition 3', and the missing condition should be supplied. Also, 'Algorithm 5' is referenced but no Algorithm 5 appears; presumably Algorithm 2 is meant.
  2. [Appendix A.3, proof of Theorem 6] The phrase 'the algorithm ensures that the in every channel' contains a typo ('the in'). More importantly, the proof is a high-level sketch that does not explain how the reserve mechanism of Algorithm 1 (details deferred to Appendix B.1) yields the stated capacity bound for the star. Please spell out the composition argument.
  3. [Section 5, clustering conditions] Condition 1 is introduced as 'The volume of transactions inside the cluster is t-times the volume of transactions that go outside the cluster.' The displayed formula appears to have a subscript typo: the first sum should likely range over pairs s',t' both in C_i, and the second over pairs with exactly one endpoint in C_i. Also, conditions 2 and 3 should be stated before they are used.
  4. [Section 4.2 and Appendix B.1] The description of Algorithm 1 says it uses a heap and threshold √3−1/2 M, but the notation M is not defined at that point. It is defined in the preceding paragraph only informally. Please state the definition of M explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivations are genuine extensions of prior single-channel work; the flagged issues are proof gaps and empirical weaknesses, not definitional self-reference.

full rationale

Under the circularity rubric, I find no step where a claimed prediction or first-principles result is equivalent by construction to its inputs. The main O(p) result (Theorem 6) is a concrete algorithm: it solves a star LP, allocates capacities C_v and pairwise reserves (sqrt(3)/2)M, and composes per-pair single-channel decisions. The approximation factors (sqrt(3)+1)R and (1+(p-1)sqrt(3))C are derived by counting p-1 channels and invoking [27]'s single-channel rejection bound; [27] is a separate published theorem about a strictly smaller model (single channel), so under Rule 4 it counts as independent support rather than circular self-citation. No parameter is fitted to the target quantity and then renamed a prediction. The O(sqrt(p)) section does not short-circuit either: it defines clustering by an inside/outside volume ratio and attempts to prove Lemmas 7-9 and Theorem 10 through LP movement and reserve arguments. Even though I flag that Lemma 7's proof is verbatim identical to Theorem 6's proof and that clustering conditions 2 and 3 are never defined in Section 5, these are correctness/completeness defects, not circularity—they do not make the theorem equal to its assumptions. The Lightning case study estimates transaction volumes from topology and then reports a within/between ratio of 193.2; this is weak or partly self-fulfilling empirical validation, but it is not an input to the theorem and does not convert a definition into a derivation. The reader's higher score conflates unproved lemmas and empirical weaknesses with circularity; under the specified rubric, the correct score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central theoretical results rest on the PCN channel model, the coordination assumption, the single-channel algorithm from [27], and, for the improved bound, a stochastic block model clustering condition with hand-chosen parameters (sqrt(p),sqrt(p),24 sqrt(p)). The empirical section adds a volume-estimation heuristic that is not independently validated. No new physical entities are introduced; reserves and cluster reserves are algorithmic buffers, not model entities.

free parameters (3)
  • clustering strength t = 24 sqrt(p) = 24 sqrt(p)
    Chosen by hand in Section 5 to make the O(sqrt(p)) proof close; not estimated from data.
  • cluster count m = sqrt(p) and cluster size k = sqrt(p) = sqrt(p)
    Assumed in Theorem 10; the double star is built around these values.
  • fixed transaction amount in volume estimation = 100 milli-satoshi
    Section 6 assumes all transactions have a fixed size of 100 msat when estimating volumes from routing cost; this is an arbitrary normalizing constant for the empirical analysis.
assumptions (5)
  • domain assumption Payment channels are fixed-capacity undirected edges; capacity is splittable between endpoints but total capacity is invariant and a node cannot transfer balance between its channels.
    Section 2 model properties 1-3; this is the standard PCN model and is load-bearing for the LP and the reserve arguments.
  • domain assumption The p parties cooperate in the network creation stage to minimize total cost.
    Section 1.1 explicitly assumes coordination; without it, unilateral network creation games such as [5,6,14] are the relevant model.
  • ad hoc to paper The transaction sequence is (sqrt(p),sqrt(p),24 sqrt(p))-clustered, i.e., intra-cluster volume is at least 24 sqrt(p) times inter-cluster volume and additional per-node volume conditions hold.
    Introduced in Section 5 to obtain the O(sqrt(p)) ratio; the constant 24 sqrt(p) is chosen to make the proof work and is not derived from data or independent first principles.
  • standard math The single-channel admission algorithm of [27] achieves the claimed (sqrt(3)+1) rejection-cost approximation and its per-pair composition does not lose more than the stated factors.
    Invoked in the proof of Theorem 6 (Section 4.2 and Appendix A.3). It is a peer-reviewed external result co-authored by three of the five current authors, but no formal certificate or reproduction is provided in this preprint.
  • ad hoc to paper In the empirical study, the volume of transactions between users i and j is 1/(c_{i,j}+1), where c_{i,j} is the minimum cost of a 100 milli-satoshi payment, and all transactions have the same fixed volume.
    Section 6: this heuristic substitutes for actual transaction data; it is unverified and drives the clustering-validation result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection." pith.science (2026). https://pith.science/paper/CHX2OKBA

@misc{pith2026250814524,
  author       = {Pith},
  title        = {Pith review of: Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CHX2OKBA}},
  note         = {Machine review of arXiv:2508.14524}
}
abstract

Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over $p$ parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the $p$ cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an $\mathcal{O}(p)$ approximation algorithm for the problem with $p$ parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to $\mathcal{O}(\sqrt{p})$. We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 25 canonical work pages

  1. [27]

    Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation

    Stefan Schmid, Jakub Svoboda, and Michelle Yeo. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In SIROCCO , volume 13892 of Lecture Notes in Computer Science , pages 576--594. Springer, 2023

    work page 2023

  2. [1]

    URL: https://github.com/lnresearch/topology

    Lightning network topology datasets. URL: https://github.com/lnresearch/topology

    work page

  3. [2]

    https://raiden.network/, 2017

    Raiden network. https://raiden.network/, 2017

    work page 2017

  4. [3]

    Transactional contention management as a non-clairvoyant scheduling problem

    Hagit Attiya, Leah Epstein, Hadas Shachnai, and Tami Tamir. Transactional contention management as a non-clairvoyant scheduling problem. Algorithmica , 57(1):44--61, 2010

    work page 2010

  5. [4]

    Online payment network design

    Georgia Avarikioti, Kenan Besic, Yuyi Wang, and Roger Wattenhofer. Online payment network design. In DPM/CBT@ESORICS , volume 11737 of Lecture Notes in Computer Science , pages 307--320. Springer, 2019

    work page 2019

  6. [5]

    Ride the lightning: The game theory of payment channels

    Zeta Avarikioti, Lioba Heimbach, Yuyi Wang, and Roger Wattenhofer. Ride the lightning: The game theory of payment channels. In Financial Cryptography , volume 12059 of Lecture Notes in Computer Science , pages 264--283. Springer, 2020

    work page 2020

  7. [6]

    Lightning Creation Games

    Zeta Avarikioti, Tomasz Lizurej, Tomasz Michalak, and Michelle Yeo. Lightning creation games. CoRR , abs/2306.16006, 2023

    work page Pith review arXiv 2023

  8. [7]

    R2: boosting liquidity in payment channel networks with online admission control

    Mahsa Bastankhah, Krishnendu Chatterjee, Mohammad Ali Maddah - Ali, Stefan Schmid, Jakub Svoboda, and Michelle Yeo. R2: boosting liquidity in payment channel networks with online admission control. In FC (1) , volume 13950 of Lecture Notes in Computer Science , pages 309--325. Springer, 2023

    work page 2023

Show all 27 references
  1. [8]

    Blockchain and scalability

    Anamika Chauhan, Om Prakash Malviya, Madhav Verma, and Tejinder Singh Mor. Blockchain and scalability. In QRS Companion , pages 122--128. IEEE , 2018

    2018

  2. [9]

    The all-or-nothing multicommodity flow problem

    Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. The all-or-nothing multicommodity flow problem. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC) , pages 156--165, 2004

    2004

  3. [10]

    Anne Condon and Richard M. Karp. Algorithms for graph partitioning on the planted partition model. Random Struct. Algorithms , 18(2):116--140, 2001

    2001

  4. [11]

    Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin G \" u n Sirer, Dawn Song, and Roger Wattenhofer

    Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed E. Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin G \" u n Sirer, Dawn Song, and Roger Wattenhofer. On scaling decentralized blockchains - (A position paper). In Financial Cryptography Worksho...

    2016

  5. [12]

    eltoo: A simple layer2 protocol for bitcoin

    Christian Decker, Rusty Russell, and Olaoluwa Osuntokun. eltoo: A simple layer2 protocol for bitcoin. https://blockstream.com/eltoo.pdf, 2018

    2018

  6. [13]

    A fast and scalable payment network with bitcoin duplex micropayment channels

    Christian Decker and Roger Wattenhofer. A fast and scalable payment network with bitcoin duplex micropayment channels. In Symposium on Self-Stabilizing Systems (SSS) , pages 3--18. Springer, 2015

    2015

  7. [14]

    How to profit from payments channels

    Oguzhan Ersoy, Stefanie Roos, and Zekeriya Erkin. How to profit from payments channels. In Financial Cryptography , volume 12059 of Lecture Notes in Computer Science , pages 284--303. Springer, 2020

    2020

  8. [15]

    Lightning network economics: Topology

    Paolo Guasoni, Gur Huberman, and Clara Shikhelman. Lightning network economics: Topology. SSRN Electronic Journal , 2023. https://doi.org/10.2139/ssrn.4439190 doi:10.2139/ssrn.4439190

    2023 doi

  9. [16]

    Lightning network economics: Channels

    Paolo Guasoni, Gur Huberman, and Clara Shikhelman. Lightning network economics: Channels. Manag. Sci. , 70(6):3827--3840, 2024

    2024

  10. [17]

    Polymorphic contention management

    Rachid Guerraoui, Maurice Herlihy, and Bastian Pochon. Polymorphic contention management. In Pierre Fraigniaud, editor, Distributed Computing , pages 303--323, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg

    2005

  11. [18]

    Towards a theory of transactional contention managers

    Rachid Guerraoui, Maurice Herlihy, and Bastian Pochon. Towards a theory of transactional contention managers. In PODC , pages 316--317. ACM , 2006

    2006

  12. [19]

    The consensus number of a cryptocurrency

    Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos - Adrian Seredinschi. The consensus number of a cryptocurrency. In PODC , pages 307--316. ACM , 2019

    2019

  13. [20]

    The capacity of wireless networks

    Piyush Kumar Gupta and Panganamala Ramana Kumar. The capacity of wireless networks. IEEE Trans. Inf. Theory , 46:388--404, 2000

    2000

  14. [21]

    Wait-free synchronization

    Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst. , 13(1):124–149, January 1991. https://doi.org/10.1145/114005.102808 doi:10.1145/114005.102808

    1991

  15. [22]

    Laskey, and Samuel Leinhardt

    Paul Holland, Kathryn B. Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks , 5:109--137, 1983. URL: https://api.semanticscholar.org/CorpusID:34098453

    1983

  16. [23]

    We might walk together, but I run faster: Network fairness and scalability in blockchains

    Anurag Jain, Shoeb Siddiqui, and Sujit Gujar. We might walk together, but I run faster: Network fairness and scalability in blockchains. In AAMAS , pages 1539--1541. ACM , 2021

    2021

  17. [24]

    Pisa: Arbitration outsourcing for state channels

    Patrick McCorry, Surya Bakshi, Iddo Bentov, Sarah Meiklejohn, and Andrew Miller. Pisa: Arbitration outsourcing for state channels. In AFT , 2019. URL: 10.1145/3318041.3355461

    2019

  18. [25]

    The bitcoin lightning network: Scalable off-chain instant payments

    Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments. https://lightning.network/lightning-network-paper.pdf, 2015

    2015

  19. [26]

    Provably good routing in graphs: regular arrays

    Prabhakar Raghavan and Clark D Thompson. Provably good routing in graphs: regular arrays. In Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages 79--87, 1985

    1985

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.