Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
2026-04-09 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to handle transactions in payment channel networks (PCNs), which help speed up cryptocurrency payments by passing transactions through channels instead of the main blockchain. They focus on the challenge of keeping these channels balanced so they can process as many transactions as possible, even when transaction requests come one by one without knowing the future. They model this as a new type of online knapsack problem where transactions can add or remove funds depending on direction. The authors propose a deterministic algorithm that performs well compared to the best possible solutions and prove that no other algorithm, even randomized ones, can do significantly better.
Payment channel networksCryptocurrency transactionsBlockchainChannel balanceOnline algorithmsKnapsack problemDeterministic algorithmCompetitive ratioRandomized algorithmsTransaction throughput
Authors
Marcin Bienkowski, Julien Dallot, Dominik Danelski, Maciej Pacut, Stefan Schmid
Abstract
Payment channel networks (PCNs) are a promising solution to make cryptocurrency transactions faster and more scalable. At their core, PCNs bypass the blockchain by routing the transactions through intermediary channels. However, a channel can forward a transaction only if it possesses the necessary funds: the problem of keeping the channels balanced is a current bottleneck on the PCN's transaction throughput. This paper considers the problem of maximizing the number of accepted transactions 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 (initially allocated funds). We complement this result with an asymptotically matching lower bound of $Ω(\log B)$ which holds for any randomized algorithm, demonstrating our algorithm's optimality.