pith. sign in

arxiv: 2604.08205 · v2 · pith:UNC5RGEKnew · submitted 2026-04-09 · 💻 cs.DS

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items

Marcin Bienkowski , Julien Dallot , Dominik Danelski , Maciej Pacut , Stefan Schmid This is my paper

Pith reviewed 2026-05-21 09:35 UTC · model grok-4.3

classification 💻 cs.DS
keywords online algorithmsknapsack problempayment channel networkscompetitive analysistransaction admissioncryptocurrenciesresource allocation
0
0 comments X

The pith

A deterministic online algorithm for transaction admission in payment channels is O(log B)-competitive and asymptotically optimal.

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

This paper models deciding which transactions to accept on a single payment channel as an online knapsack problem in which each arriving transaction is either a positive or negative item depending on its direction. It gives a deterministic algorithm that accepts a number of transactions within an O(log B) factor of the best possible offline solution, where B is the maximum channel balance. The paper also proves that no randomized online algorithm can achieve a better asymptotic ratio, establishing optimality. A sympathetic reader cares because payment channel networks rely on quick local decisions to keep funds flowing without waiting for future transaction knowledge.

Core claim

The problem of maximizing the number of accepted transactions on a payment channel, where proposals arrive one by one and each changes the balance either positively or negatively, admits a deterministic online algorithm with competitive ratio O(log B) for knapsack capacity B. This ratio is asymptotically tight: every randomized online algorithm has competitive ratio Omega(log B) on some input sequences.

What carries the argument

The online knapsack variant with both positive and negative items, solved by a deterministic algorithm that adjusts acceptance decisions according to the current balance and remaining capacity to maintain the O(log B) guarantee.

If this is right

  • A single channel can maintain high transaction throughput by using the algorithm even when future requests are completely unknown.
  • The competitive ratio scales with the logarithm of the balance limit, so larger B values require proportionally more careful threshold management.
  • The positive-negative item model captures any online decision problem where actions can either consume or restore a limited resource.
  • The matching lower bound shows that log B is the inherent price of online decision-making for this class of problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The single-channel focus leaves open whether the same ratio holds when admission decisions must also respect end-to-end path constraints across multiple hops.
  • In practice the algorithm could be combined with periodic rebalancing routines to reduce the frequency of forced channel resets.
  • Similar online techniques might apply to other reversible-resource settings such as inventory restocking or battery charge management.

Load-bearing premise

That each transaction decision depends only on the current channel balance and the single arriving request, without any information or constraints from other channels or the network topology.

What would settle it

An explicit sequence of transaction requests (with sizes and directions) on which every online algorithm accepts fewer than c times OPT / log B transactions for some constant c and large B, where OPT is the maximum number any offline solution could accept.

read the original abstract

Payment channel networks (PCNs) are a promising approach to making cryptocurrency transactions faster and more scalable. At their core, PCNs bypass the blockchain by routing transactions through intermediary channels. However, a channel can forward a transaction only if it has the necessary funds: the problem of keeping the channels balanced is a current bottleneck for the PCN's transaction throughput. This paper considers the problem of maximizing the number of transactions accepted by a channel in a PCN. Previous works either considered the associated optimization problem with all transactions known in advance or developed heuristics tested on particular transaction datasets. This work, however, considers the problem in its purely online form where the transactions are arbitrary and revealed one after the other. We show that the problem can be modeled as a new online knapsack variant where the items (transaction proposals) can be either positive or negative depending on the direction of the transaction. The main contribution of this paper is a deterministic online algorithm that is $O(\log B)$-competitive, where $B$ is the knapsack capacity (maximum allowed channel balance). We complement this result with an asymptotically matching lower bound of $\Omega(\log B)$ which holds for any randomized algorithm, demonstrating our algorithm's optimality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper models the transaction admission problem in payment channel networks (PCNs) as a new online knapsack variant in which items (transactions) may be positive or negative depending on direction, with the objective of maximizing the number of accepted transactions subject to a balance capacity B. It presents a deterministic online algorithm that is O(log B)-competitive and proves a matching Ω(log B) lower bound that holds even against randomized algorithms.

Significance. If the analysis holds, the result establishes asymptotic optimality of the competitive ratio for this online decision problem whose feasible region is the interval [0, B]. The positive/negative distinction turns the load into a random walk inside the interval rather than a monotone sum, yet the standard doubling or potential-function argument still yields the logarithmic ratio, and the lower-bound construction (sequences forcing rejection at each scale) remains valid. This supplies the first tight competitive analysis for purely online transaction admission in PCNs and gives a clean theoretical benchmark for channel-management heuristics.

major comments (2)
  1. [§3] §3 (Algorithm): the O(log B) upper bound is stated to follow from a deterministic online algorithm, but the precise potential function or doubling threshold used to decide acceptance when the current balance is near 0 or B is not visible in the abstract; the proof must be checked to confirm it correctly handles sign-alternating sequences without violating the capacity constraint.
  2. [§4] §4 (Lower bound): the Ω(log B) lower bound is claimed to hold for any randomized algorithm, yet the adversary construction (sequences that force the algorithm to reject half the items at each scale) must be verified to remain valid when positive and negative items can be interleaved arbitrarily; if the construction assumes a particular ordering of signs, the bound may weaken.
minor comments (2)
  1. Clarify the exact definition of an 'item' (transaction size and sign) and the update rule for channel balance after acceptance; the abstract mentions 'arbitrary' amounts but does not state whether sizes are assumed to be smaller than B or can be arbitrary.
  2. Add a short paragraph contrasting the new model with classical online knapsack (unit-value, positive-only items) to highlight where the sign alternation changes the analysis.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation of minor revision. We address the two major comments below, providing clarifications from the manuscript while noting where we will expand the presentation.

read point-by-point responses

  1. Referee: [§3] §3 (Algorithm): the O(log B) upper bound is stated to follow from a deterministic online algorithm, but the precise potential function or doubling threshold used to decide acceptance when the current balance is near 0 or B is not visible in the abstract; the proof must be checked to confirm it correctly handles sign-alternating sequences without violating the capacity constraint.

    Authors: Section 3 presents the full deterministic algorithm together with its analysis. The algorithm maintains a potential function that is the sum of two logarithmic terms, one measuring the distance from the current balance to 0 and the other to B; acceptance occurs only when the item would increase the potential by at most a constant factor. This doubling-style threshold is applied symmetrically for positive and negative items and is shown in the proof to keep the balance inside [0, B] for any sequence, including arbitrary alternations of signs. The capacity constraint is never violated because the potential penalizes moves that would approach either boundary too closely. To improve visibility we will add a one-sentence description of the potential function to the abstract in the revised version. revision: yes

  2. Referee: [§4] §4 (Lower bound): the Ω(log B) lower bound is claimed to hold for any randomized algorithm, yet the adversary construction (sequences that force the algorithm to reject half the items at each scale) must be verified to remain valid when positive and negative items can be interleaved arbitrarily; if the construction assumes a particular ordering of signs, the bound may weaken.

    Authors: The lower-bound construction in Section 4 is fully adaptive: at each scale the adversary chooses both the magnitude and the sign of the next item on the basis of the algorithm’s current balance and previous decisions. Consequently the construction does not presuppose any fixed ordering of signs; the adversary can interleave positive and negative items arbitrarily while still forcing the algorithm (even a randomized one) to reject a constant fraction of items at each of the Θ(log B) scales. The analysis therefore already accounts for the worst-case interleaving, and the Ω(log B) bound remains valid. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper models the PCN transaction admission problem as an online knapsack variant with positive/negative items and presents a deterministic O(log B)-competitive algorithm together with a matching Ω(log B) lower bound for randomized algorithms. These claims rest on direct competitive analysis (standard potential or doubling arguments applied to the feasible interval [0,B]) and an explicit adversarial construction for the lower bound; neither reduces to a fitted parameter, a self-definitional equivalence, nor a load-bearing self-citation. The derivation is therefore self-contained against external benchmarks of online-algorithm theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard online decision model and the reduction to a knapsack with signed items; no free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • domain assumption Transactions arrive in an arbitrary online sequence with no distributional assumptions.
    Stated in the abstract as the purely online form of the problem.
  • domain assumption Each transaction affects channel balance by a fixed amount that is known upon arrival and can be treated as a positive or negative knapsack item.
    Core modeling step described in the abstract.

pith-pipeline@v0.9.0 · 5755 in / 1326 out tokens · 45461 ms · 2026-05-21T09:35:07.091273+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

  1. [1]

    3 Nitin Awathare, Suraj, Akash, Vinay Joseph Ribeiro, and Umesh Bellur

    doi:10.4230/LIPICS.APPROX-RANDOM.2019.22. 3 Nitin Awathare, Suraj, Akash, Vinay Joseph Ribeiro, and Umesh Bellur. REBAL: channel balancing for payment channel networks. In29th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, MASCOTS 2021, pages 1–8, 2021.doi:10.1109/MASCOTS53633.2021.9614304. 4 Hans-...

    work page doi:10.4230/lipics.approx-random.2019.22 2019

  2. [2]

    Boosting payment channel network liquidity with topology optimization and transaction selection

    7 Krishnendu Chatterjee, Jan Matyás Kristan, Stefan Schmid, Jakub Svoboda, and Michelle Yeo. Boosting payment channel network liquidity with topology optimization and transaction selection. In39th International Symposium on Distributed Computing (DISC), pages 23:1–23:22, 2025.doi:10.4230/LIPICS.DISC.2025.23. 8 Anamika Chauhan, Om Prakash Malviya, Madhav V...

    work page doi:10.4230/lipics.disc.2025.23 2025

  3. [3]

    10 Marek Cygan, Lukasz Jez, and Jirí Sgall

    doi:10.1007/978-3-662-53357-4\_8. 10 Marek Cygan, Lukasz Jez, and Jirí Sgall. Online knapsack revisited.Theory Comput. Syst., 58(1):153–190, 2016.doi:10.1007/S00224-014-9566-4. 11 Christian Decker. Lightning network research; topology datasets. https://github.com/ lnresearch/topology. Accessed: 2025-07-21.doi:10.5281/zenodo.4088530. 12 Felix Engelmann, He...

    work page doi:10.1007/978-3-662-53357-4 2016

  4. [4]

    Deciding DPDA equivalence is primitiv e recursive

    doi: 10.1007/3-540-45465-9\_26. 16 Anurag Jain, Shoeb Siddiqui, and Sujit Gujar. We might walk together, but I run faster: Network fairness and scalability in blockchains. In20th International Confer- ence on Autonomous Agents and Multiagent Systems (AAMAS), pages 1539–1541,

    work page doi:10.1007/3-540-45465-9

  5. [5]

    17 Alberto Marchetti-Spaccamela and Carlo Vercellis

    doi:10.5555/3463952.3464152. 17 Alberto Marchetti-Spaccamela and Carlo Vercellis. Efficient on-line algorithms for the knapsack problem (extended abstract). In14th International Colloquium on Automata, Languages and Programming (ICALP), pages 445–456, 1987.doi:10.1007/3-540-18088-5\_38. 18 Mempool. Mempool rest api documentation,

    work page doi:10.5555/3463952.3464152 1987

  6. [6]

    20 Joseph Poon and Thaddeus Dryja

    doi: 10.1016/J.COMCOM.2020.12.009. 20 Joseph Poon and Thaddeus Dryja. The bitcoin lightning network.Scalable o-chain instant payments, pages 20–46,

    work page doi:10.1016/j.comcom.2020.12.009 2020

  7. [7]

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

    21 Stefan Schmid, Jakub Svoboda, and Michelle Yeo. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In30th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 576–594, 2023.doi:10.1007/978-3-031-32733-9\_26. 22 Vibhaalakshmi Sivaraman, Shaileshh Bojja Ve...

    work page doi:10.1007/978-3-031-32733-9 2023

  8. [9]

    URL:https://arxiv.org/abs/2109.11665,arXiv:2109.11665

    work page arXiv