11institutetext: Sharif University of Technology,
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>22institutetext: Institute of Science and Technology Austria,
22email: {Krishnendu.Chatterjee , jakub.svoboda<EMAIL_ADDRESS>33institutetext: TU Berlin
33email<EMAIL_ADDRESS>
# Online Admission Control and Rebalancing
in Payment Channel Networks

Mahsa Bastankhah 11 Krishnendu Chatterjee 22 Mohammad Ali Maddah-Ali 11 Stefan
Schmid 33 Jakub Svoboda 22 Michelle Yeo 22

###### Abstract

Payment channel networks (PCNs) are a promising technology to improve the
scalability of cryptocurrencies. PCNs, however, face the challenge that the
frequent usage of certain routes may deplete channels in one direction, and
hence prevent further transactions. In order to reap the full potential of
PCNs, recharging and rebalancing mechanisms are required to provision
channels, as well as an admission control logic to decide which transactions
to reject in case capacity is insufficient. This paper presents a formal model
of this optimisation problem. In particular, we consider an online algorithms
perspective, where transactions arrive over time in an unpredictable manner.
Our main contributions are competitive online algorithms which come with
provable guarantees over time. We empirically evaluate our algorithms on
randomly generated transactions to compare the average performance of our
algorithms to our theoretical bounds. We also show how this model and approach
differs from related problems in classic communication networks.

##  1 Introduction

Blockchain consensus protocols are notoriously inefficient: for instance,
Bitcoin can only support $7$ transactions per second on average which makes it
unrealistic to use in everyday situations. Payment channel networks like
Bitcoin’s Lightning Network [15] and Ethereum’s Raiden [1] have been proposed
as scalability solutions to blockchains. Instead of sending transactions to
the blockchain and waiting for the entire blockchain (which can comprise of
millions of users) to achieve consensus, any two users that wish to transact
with each other can simply open a payment channel between themselves. Opening
a payment channel requires an initial funding transaction on the blockchain
where both users lock some funds only to use in the channel. Once a payment
channel is opened, the channel acts as a local, two-party ledger: payments
between the users of channel simply involve decreasing the balance of the
payer by the payment amount, and increasing the balance of the payee
correspondingly. As these local transactions only involve exchanging
signatures between the two users and do not involve the blockchain at all,
they can be almost instantaneous. As long as there is sufficient balance,
payments can occur indefinitely between two users, until the users decide to
close the channel. This would involve going back to the blockchain and takes,
in the worst case, a small constant number of transactions (in the Lightning
Network this constant is 2). Thus, with only a small constant number of on-
chain transactions, any two users can potentially make arbitrarily many
costless transactions between themselves.

Apart from joining a payment channel network to efficiently transact with
other users, an additional financial incentive to joining the network is to
profit from forwarding transactions. Any two users that are not directly
connected to each other with a payment channel can transact with each other in
a multi-hop fashion as long as they are connected by a path of payment
channels. To incentivise these intermediary nodes on the path to forward the
payment, the network typically allows these nodes to charge a transaction fee.
Thus, it is common for users to join the network specifically to play the role
of an intermediary node that routes transactions, creating channels and fees
optimally and selecting the most profitable transactions to maximise their
profit from transaction fees [4, 8].

However, greedily accepting and routing incoming transactions could rapidly
deplete a user’s balance in their channels. In particular, if certain routes
are primarily used in one direction, their channels can get depleted, making
it impossible to forward further transactions. Accounting for this problem can
be non-trivial, especially since demand patterns are hard to predict and often
also confidential.

To resolve this issue, PCNs typically support two mechanisms:

  * •

_On-chain recharging:_ A user can close and reopen a depleted channel with
more funds on-chain.

  * •

_Off-chain rebalancing:_ An alternative solution is to extend the lifetime of
a depleted channel without involving the blockchain, by finding a cycle of
payment channels in the network to shift funds from one channel to another.

Both cases, however, entail a cost. Intermediaries need to consider the
tradeoff between admitting trasactions and potential costs for recharging and
rebalancing. This decision making process is especially important to big
routers which are the primary maintainers of payment channel networks like the
Lightning Network.

In this work, we focus on the problem of admission control, recharging and
rebalancing in a single payment channel from the perspective of an
intermediary node that seeks to route as many transactions as possible with
minimal costs. Specifically, we address the following research question:

Can we design efficient online algorithms for deciding when to accept/reject
transactions, and when to recharge or rebalance in a single payment channel?

We seek to address this problem with as few restrictions on the actions of the
users as possible in order to ensure that our work is realistic. Thus, we
assume a fixed payment channel network topology with some recharging and
rebalancing costs, and a global fee function that is linear in the transaction
size. We also assume users incur a rejection cost in the form of opportunity
cost when they reject to route a transaction.

We are interested in robust solutions which do not depend on any knowledge or
assumptions on the demand. Accordingly, we assume that transactions can arrive
in an arbitrary order at a channel, and aim to design online algorithms which
provide worst-case guarantees. We are in the realm of competitive analysis,
and assume that an adversary with knowledge of our algorithms chooses the most
pessimal online transaction sequence. Our objective is to optimise the
_competitive ratio_ [6]: we compare the performance of our online algorithms
(to which the transaction sequence is revealed over time) with the optimal
offline algorithm that has access to the entire transaction sequence in
advance.

###  1.1 Our contributions

We initiate the study of a fundamental resource allocation problem in payment
channel networks, from an online algorithms perspective. Our main result is a
competitive online algorithm to admit transaction streams arriving at both
sides of a payment channel, and also to recharge and rebalance the channel, in
order to maximise the throughput over the channel while accounting for costs.
In particular, our algorithm achieves a competitive ratio of $7+2\lceil\log
C\rceil$ where $C+1$ is the length of the rebalancing cycle used to replenish
the funds on the channel off-chain. We also provide lower bounds on the amount
of funds needed in a channel in order to ensure our algorithm is
$c$-competitive for $c<\frac{\log C}{\log\log C}$.

In order to prove our main theorem, we decompose the problem into two simpler
but decreasingly restrictive sub problems that may also be of independent
interest:

  1. 1.

_Sub problem 1:_ The first and most restrictive sub problem considers a
transaction stream coming only from one direction across a payment channel,
and users do not have the option to reject incoming transactions. We present a
$2$-competitive algorithm for this problem, which is optimal in the sense that
no deterministic online algorithm can achieve a lower competitive ratio.

  2. 2.

_Sub problem 2:_ As a relaxation, our second sub problem allows users to
reject transactions although all transactions are still restricted to come
from one direction along a payment channel. We show that our algorithm
achieves a competitive ratio of $2+\frac{\sqrt{5}-1}{2}$ for this sub problem.
We stress that our lower bound of $2$ we achieve in sub problem $1$ also holds
in this sub problem, hence our competitive ratio of $2+\frac{\sqrt{5}-1}{2}$
is close to optimal.

All these intermediate results as well as the result for our main problem are
summarised in Table 1. The algorithms and analysis designed to address these
sub problems are eventually used as building blocks for our main algorithm and
main theorem.

We complement our theoretical worst-case analysis by performing an empirical
evaluation of the performance of our algorithm on randomly generated
transaction sequences. To this end, we also present an exact dynamic
programming algorithm, allowing us to evaluate the competitive ratio. We
observe that our algorithms perform much better on average compared to our
theoretical worst-case bound.

Sub problem | Competitive ratio
---|---
Unidirectional stream without rejection | $2$
Unidirectional stream with rejection | $2+\frac{\sqrt{5}-1}{2}$
Bidirectional stream | $\bm{7+2\lceil\log C\rceil}$
Table 1: Summary of the theoretical results in our paper. The first column
presents each sub problem we analyse in our paper and the second column shows
the competitive ratio achieved by our algorithms for each sub problem

###  1.2 Related work

##### Maintaining balanced payment channels.

As channel balances are typically private, classic transaction routing
protocols on payment channel networks like Flare [16], SilentWhispers [13] and
SpeedyMurmurs [17] focus mainly on throughput and ignore the issue of balance
depletion. Recently, several works shift the focus on maintaining balanced
payment channels for as long as possible while ensuring liveness of the
network. Revive [10] initiated the study rebalancing strategies, Spider[19]
uses multi-path routing to ensure high transaction throughput while
maintaining balanced payment channels, the Merchant[20] utilises fee
strategies to incentivise the balanced use of payment channels, and [11] uses
estimated payment demands along channels to plan the amount of funds to inject
into a channel during channel creation, to just give a few examples. Our work
focuses on minimising costs incurred in the process of handling transactions
across a channel and thus we also indirectly seek to maintain balanced payment
channels. Moreover, in contrast to previous works which typically assume some
form of offline knowledge of the transaction flow in the network, we provide
an algorithm which comes with provable worst-case guarantees.

##### Off-chain rebalancing.

Off-chain rebalancing has been studied as a cheaper alternative to refunding a
channel by closing and reopening it on the blockchain. In the Lightning
Network, there are already several off-chain rebalancing plugins for
c-lightning111https://github.com/lightningd/plugins/tree/master/rebalance and
lnd222https://github.com/bitromortac/lndmanage. An automated approach to
performing off-chain rebalancing using the imbalance measure as a heuristic
has been proposed in [14]. Our work similarly studies when to rebalance
payment channels, however we make the decision in tandem with other decisions
like accepting or rejecting transactions. Recently, [5] and [10] propose a
global approach to off-chain rebalancing where demand for rebalancing cycles
is aggregated across the entire network and translated to an LP which is
subsequently solved to obtain an optimal rebalancing solution. These
approaches are orthogonal and complementary to ours as our focus concerns
decision making in a single payment channel and not the entire network.

##### Online algorithms for payment channel networks.

Online algorithms for payment channel networks have also been studied in [3]
and [9]. Avarikioti et al. [3] establish impossibility results against certain
classes of adversaries, however they only consider a limited problem setting
where their algorithms can only accept or reject transactions (with constant
rejection cost). Fazli et al. [9] considers the problem of optimally
scheduling on-chain recharging given a sequence of transactions. In contrast
to previous work, our work considers a more general problem setting where our
algorithms can not only accept or reject transactions, but also recharge and
rebalance channels off chain. We also extend the cost of rejection to take
into account the size of the transaction.

##### Relationship to classic communication networks.

Admission control problems such as online call admission [2, 12] are
fundamental and have also received much attention in the context of
communication networks. However, in classic communication networks the
available capacity of a link in one direction is independent of the flows
travelling in the other direction, and moreover, link capacities are only
consumed by the currently allocated flows. In contrast, the capacities of
links in payment-channel networks are permanently reduced by transactions
flowing in one direction, but can be topped up by flows travelling in the
other direction. The resulting rebalancing opportunity renders the underlying
algorithmic problem significantly different.

###  1.3 Organisation

The remainder of this paper is organised as follows. In Section 2, we
introduce our model and give a brief overview of the various sub problems we
consider. Section 3 presents some algorithmic building blocks. We describe and
analyse our algorithms for the sub problems in Section 4 and Section 5, and
for the general problem in Section 6. We empirically evaluate our online
algorithms in Section 7, before concluding our contribution in Section 8.

##  2 Model

We introduce preliminaries, and present our model (and its sub problems).

###  2.1 Modelling PCNs

##### Payment channels.

We model the payment channel network as an undirected graph $G=(V,E)$. A
payment channel between users $\ell,r\in V$ is an edge $(\ell,r)\in E$. By
denoting parties in a given channel as $\ell$ (left) and $r$ (right), we
benefit from a visual representation of a channel in which transactions move
funds across the channel from left to right or from right to left. We denote
the balance of user $\ell$ (resp. $r$) in the channel $(\ell,r)$ by
$\emph{b}(\ell)$ (resp. $\emph{b}(r)$). The _capacity_ of the channel is the
total amount of funds locked in the channel. That is, for a channel
$(\ell,r)$, the capacity of $(\ell,r)$ is $\emph{b}(\ell)+\emph{b}(r)$. A
left-to-right transaction of amount $x$ decreases $\ell$’s balance by $x$ and
increases $r$’s balance by $x$ and vice versa for a right-to-left transaction
of $x$.

##### Recharging and rebalancing payment channels.

When a user in a channel does not have sufficient funds to accept a
transaction, the user can either reject the transaction, recharge the channel,
or rebalance the channel. Recharging the channel happens on-chain and
corresponds to closing the payment channel on the blockchain and opening a new
channel with more funds. Refer to Figure 2d for an example. In contrast,
rebalancing the channel happens entirely off-chain. Here, users find a cycle
of payment channels to shift funds from one of their other channels to refund
the depleted channel. Figure 1 depicts a simple example of off-chain
rebalancing where user $\ell$ wishes to refund their depleted $(\ell,r)$
channel with amount $5$.

##### Transactions.

We consider a transaction sequence $X_{t}=(x_{1},...,x_{t})$,
$x_{i}\in\mathbb{R}^{+}$, that arrives at a fixed payment channel online.
Transactions are processed in the order in which they arrive in the sequence.
Each transaction $x_{i}$ in the sequence has both a value and a direction
along a payment channel. The value of a transaction is simply the amount that
is being transferred. The direction of a transaction across a payment channel
$(\ell,r)$ determines who is the sender of the transaction and who is the
receiver. When we have a sequence of transactions that go in both directions
along a payment channel, we use $\overscriptrightarrow{x}$ to denote a
transaction that goes from left-to-right and $\overscriptleftarrow{x}$ to
denote a transaction that goes from right-to-left. We say a user, wlog $\ell$,
_accepts_ a transaction of size $x$ coming from the left to right direction
along the channel $(\ell,r)$ if $\ell$ agrees to forward $x$ to $r$ (see
Figure 2a for an example of $r$ accepting transaction
$\overscriptleftarrow{1}$). Similarly, we say a user $\ell$ _rejects_ a
transaction $x$ coming from the left to right direction along the channel
$(\ell,r)$ when $\ell$ does not forward the transaction to $r$ (see Figure 2b
for an example of $r$ rejecting transaction $\overscriptleftarrow{9}$). When
it is clear which channel and direction we are referring to, we simply say
$\ell$ accepts or rejects $x$.

##### Costs.

We consider three types of costs in our problem setting:

  1. 1.

Rejecting transactions: For any fixed user $\ell$, the revenue in terms of
transaction fees from forwarding a payment of size $x$ is $Rx+f_{2}$, where
$R,f_{2}\in\mathbb{R}^{+}$. Consequently, the cost of rejecting a transaction
of size $x$ is simply the opportunity cost of gaining revenue from accepting
the transaction, i.e. $Rx+f_{2}$.

  2. 2.

On-chain recharging: For any user $\ell$, the cost of recharging a channel on-
chain is $F+f_{1}$, where $F$ is the amount of funds $\ell$ puts into the new
channel and $f_{1}\in\mathbb{R}^{+}$ is an auxiliary cost independent of $F$
which captures the on-chain recharging transaction fee.

  3. 3.

Off-chain rebalancing: For any user $\ell$, the cost of off-chain rebalancing
for an amount $x$ is $C\cdot(Rx+f_{2})$, where $C$ is the length of the cycle
along which funds are sent $-1$. In the example of off-chain rebalancing in
Figure 1, the length of the rebalancing cycle is 3 and thus $C=2$.

Let us denote by OFF the optimal offline algorithm and ON an online
deterministic algorithm. We denote by $\textsc{Cost}_{\textsc{ON}}(X_{t})$
(resp. $\textsc{Cost}_{\textsc{OFF}}(X_{t})$) the total cost of ON (resp. OFF)
given the transaction sequence $X_{t}$.

Figure 1: Example of off-chain rebalancing in a payment channel network with
users $\ell$, $h$, and $r$. $\ell$ transfers $5$ coins along the channels
$(\ell,h)$, $(h,r)$ and $(r,\ell)$ to replenish $\ell$’s balance on the
$(\ell,r)$ channel. The graph on the right depicts the balances of each user
in each channel after performing off-chain rebalancing.

(a) Accepting a transaction

(b) Rejecting a transaction

(c) Off-chain rebalancing

(d) Recharging

Figure 2: Example of actions users $\ell$ and $r$ can take in the general
bidirectional stream setting, and the changes in the balances of both users as
a result of these actions. Each square represents $1$ coin.

##### Competitive ratio.

We say an online algorithm ON is _c-competitive_ if for every transaction
sequence $X_{t}$ generated by the adversary,

$\textsc{Cost}_{\textsc{ON}}(X_{t})\leq
c\cdot\textsc{Cost}_{\textsc{OFF}}(X_{t})$

###  2.2 Main and sub problems

Our main problem is to design a competitive deterministic online algorithm
that determines when to accept/reject transactions and when to recharge or
rebalance the channel given a bidirectional stream of transactions across a
payment channel. More precisely, we consider a stream of transactions that can
arrive from both right to left or left to right in a given payment channel
$(\ell,r)$. $\ell$ (resp. $r$) can choose to accept or reject transactions
coming in the left-to-right (resp. right-to-left) direction in the stream.
Either user would incur a cost of $Rx+f_{2}$ for rejecting a transaction of
size $x$. Both users can also recharge the channel on-chain at any point,
incurring a cost of $F_{\ell}+F_{r}+f_{1}$ where $F_{\ell}$ and $F_{r}$ are
the funds put into the channel by $\ell$ and $r$ respectively. Since
transactions are streaming in both directions in this model, both users would
incur costs in this setting. Thus, we seek to design an algorithm that
minimises the cost of the _entire_ channel. Refer to Figure 2 for examples of
the actions that a user can take in our main bidirectional transaction stream
setting.

To this end, we give a formal definition of two sub problems of decreasing
restrictiveness on the part of user actions. We present these sub problems as
the algorithms and analysis used to solve these sub problems are used in
developing the algorithm and analysis for our main problem.

##### Unidirectional stream without rejection

In this model, we consider the case where transactions stream only in one
direction along a given payment channel. Here, users cannot reject incoming
transactions, or that doing so is not worth it (e.g., when the cost of
rejecting a transaction is larger than recharging the channel). Formally,
given a channel $(\ell,r)$ and a transaction stream from wlog left to right,
user $\ell$ only accepts a transaction $x$ if $\emph{b}(\ell)>x$. Otherwise,
$\ell$ has to recharge the channel on-chain with more funds, incurring a cost
of $F+f_{1}$ where $F$ is the amount of funds $\ell$ adds to the channel. As
we only consider transactions streaming in one direction, only one user would
incur costs in this setting (the user that has to decide whether to accept or
reject transactions). A real world example that motivates this setting is a
company which wants to position itself as a “routing hub” in a payment channel
network, providing a routing service in return for transaction fees. As such,
the company would want to accept as many transactions possible to acquire the
reputation of a hub that is constantly available.

##### Unidirectional stream with rejection

In this model, we still restrict the transaction stream from wlog left to
right in a given payment channel $(\ell,r)$. However, $\ell$ can reject
transactions, incurring a rejection cost of $Rx+f_{2}$ for a transaction of
size $x$. $\ell$ can also recharge the channel on-chain at any point,
incurring a cost of $F+f_{1}$ where $F$ is the amount of funds $\ell$ adds to
the channel.

##  3 Algorithmic Building Blocks

Before we describe and analyse the performance of our algorithms in the
various settings outlined in Section 2.2, we introduce two algorithmic
building blocks that we use extensively in the later sections of our work. The
first building block is an algorithm Funds. It takes a sequence of
transactions as an input and returns the amount of funds that an optimal
algorithm uses on this sequence. The purpose of the algorithm is to track the
funds OFF has in their channel assuming that the sequence of transactions ends
at this point. For first two sub problems we show how to compute Funds. For
the main problem, we propose a dynamic programming approach in Appendix 0.B.
The second building block is a general recharging online algorithm that calls
Funds as a subroutine and uses the output to decide when and how much to
recharge the channel on-chain. The general idea behind the recharging online
algorithm is to recharge whenever the amount of funds in OFF’s channel
“catches up” to the amount of funds ON has in their channel.

###  3.1 Tracking funds of OFF

For a given transaction sequence $X_{t}=(x_{1},\dots,x_{t})$, let us denote
$A(X_{i})$ to be the amount of funds OFF would use in the channel if OFF gets
the sequence $X_{i}=(x_{1},\dots,x_{i})$ (i.e. the length $i$ prefix of
$X_{t}$) as input. By appending subsequent transactions $x_{i+1},\dots,x_{t}$
from $X_{t}$ to $X_{i}$, we can view $A(X_{i})$ as a partial solution to the
online optimisation problem that gets updated whenever a new transaction
arrives online. In the unidirectional transaction stream (with or without
rejection) setting, $A(X_{i})$ refers to all the funds a fixed user locks into
a payment channel. In the bidirectional transaction stream setting, $A(X_{i})$
refers to the total balance of both users in the channel. We assume that given
an input sequence $X_{t}$, $\textsc{Funds}(X_{t})$ performs the necessary
computations and returns $A(X_{t})$. For our main problem, computing
$\textsc{Funds}(X_{t})$ is generally NP-hard, but we can approximate it to a
constant factor, see [18] for more details.

###  3.2 Using tracking for recharging

In Algorithm 1, we describe an online $(\gamma,\delta)$-recharging algorithm
ON that uses Funds as a subroutine to decide when and how much to recharge the
channel. ON is run by one user (wlog $\ell$) in a payment channel $(\ell,r)$.
ON calls Funds after each transaction to check if the new transaction sequence
results in a significant increase in the amount of funds OFF has in their
channel. Whenever ON notices that OFF’s funds have increased above the
threshold (Algorithm 1 in Algorithm 1), ON recharges the channel with an
amount of $\gamma(A(X_{i})+\delta)$ where $A(X_{i})$ is the amount of funds
OFF has in their channel. Table 2 depicts an example sequence of the amount of
funds inside the channel of OFF, the value of the tracking variable, and the
amount of funds inside the channel of ON.

Let us denote $A_{t}\vcentcolon=\max_{i\leq t}A(X_{i})$. Now we state and
prove some important properties of the $(\gamma,\delta)$-recharging algorithm.

Initialise: $F_{\textit{tracker}},X\leftarrow 0,\emptyset$

1 for  _transaction $x$ in order of arrival_ do

2 concatenate $x$ to $X$

3 $F_{\textit{tracker}}^{\prime}\leftarrow\textsc{Funds}(X)$

4 if  _$F_{\textit{tracker}}^{\prime} >F_{\textit{tracker}}$_ then

5 $F_{\textit{tracker}}\leftarrow F_{\textit{tracker}}^{\prime}+\delta$

6 recharge to $\gamma F_{\textit{tracker}}$

7

Algorithm 1 $(\gamma,\delta)$-recharging

###### Lemma 1

Algorithm 1 with parameters $(\gamma,\delta)$ ensures that ON always has at
least $\gamma$ times the amount of funds OFF has and ensures that ON incurs a
cost of at most
$\gamma(A_{t}+\delta)+f_{1}\cdot\lceil\frac{A_{t}}{\delta}\rceil$.

###### Proof

The first part of the claim follows from the fact that the moment
$A(X_{i})>F_{\textit{tracker}}$ for some $i$, $F_{\textit{tracker}}$ gets
updated to $A(X_{i})+\delta>A(X_{i})$ and ON recharges the channel to $\gamma
F_{\textit{tracker}}>\gamma A(X_{i})$.

For the second part of the claim, we note that the cost incurred by ON is
simply the total amount of funds added to the channel with an additional cost
of $f_{1}$ each time ON recharges the channel on-chain. The amount of funds
locked in the channel for ON is always at most $A_{t}+\delta$ and the times
when ON recharges the channel occurs whenever OFF increases its funds by an
amount of at least $\delta$. Thus, the number of rechargings for ON that can
occur is at most $\lceil\frac{A_{t}}{\delta}\rceil$ with a cost of $f_{1}$ for
each recharging instance. The total cost incurred by ON is therefore
$\gamma(A_{t}+\delta)+f_{1}\cdot\lceil\frac{A_{t}}{\delta}\rceil$.

Next, we show a simple lower bound in terms of $A_{t}$ for the cost of OFF
given a sequence of transactions $X_{t}$.

###### Lemma 2

If $A_{t}>0$, then $\textsc{Cost}_{\textsc{OFF}}(X_{t})$ is at least
$A_{t}+f_{1}$.

###### Proof

We first note that the sequence of costs for OFF is monotonically increasing,
i.e.
$\textsc{Cost}_{\textsc{OFF}}(X_{t})\leq\textsc{Cost}_{\textsc{OFF}}(X_{t+1})$.
This comes from the fact that any action of OFF at step $i$ of the sequence
can only increase its cost (i.e. either rejecting $x_{i+1}$ or recharging the
channel and then accepting $x_{i+1}$), or it does not change the cost at all
(i.e. by accepting $x_{i+1}$ without recharging).

Since $A_{t}>0$, we know that OFF recharged on-chain at some point to an
amount $A_{t}$ for a recharging cost of $A_{t}+f_{1}$. Since the sequence of
costs for OFF is monotonically increasing,
$\textsc{Cost}_{\textsc{OFF}}(X_{t})\geq A_{t}+f_{1}$.

$A(X_{i})$ | $F_{\textit{tracker}}$ | Amount locked in the channel for ON
---|---|---
$0$ | $0$ | $0$
$\varepsilon$ | $\delta+\varepsilon$ | $\gamma(\delta+\varepsilon)$
$\delta$ | $\delta+\varepsilon$ | $\gamma(\delta+\varepsilon)$
$\delta+2\varepsilon$ | $2(\delta+\varepsilon)$ | $2\gamma(\delta+\varepsilon)$
Table 2: ON is the $(\gamma,\delta)$\- recharging algorithm as described in
Algorithm 1. An example sequence of the amount locked in the channel of OFF,
the value of the tracker $F_{\textit{tracker}}$, and the amount locked in the
channel of ON after 4 transactions. We assume $\delta>\varepsilon>0$.

##  4 Step 1: Unidirectional transaction stream without rejection

In this section we consider the first sub problem where, given a payment
channel $(\ell,r)$, transactions stream along the channel in only one
direction (wlog left to right). Moreover, $\ell$ has to accept an incoming
transaction of size $x$ and forward it to $r$ if $\ell$’s balance
$\emph{b}(\ell)\geq x$. Otherwise, $\ell$ needs to recharge the channel on-
chain (and accept the transaction after).

The optimal offline algorithm OFF follows a simple strategy: since it knows
the entire stream of transactions in advance, it makes a single recharging
action at the beginning of the transaction sequence $X_{t}$ of size
$\sum_{i=1}^{t}x_{i}$. The cost incurred by OFF is thus
$f_{1}+\sum_{i=1}^{t}x_{i}$.

Initialise: tracker $F_{\textit{tracker}},X\leftarrow 0,\emptyset$

Initialise: balance $b=0$

1 for  _transaction $x$ in order of arrival_ do

2 concatenate $x$ to $X$

3 $F_{\textit{tracker}}^{\prime}\leftarrow\textsc{Funds}(X)$

4 if  _$F_{\textit{tracker}}^{\prime} >F_{\textit{tracker}}$_ then

5 $F_{\textit{tracker}}\leftarrow F_{\textit{tracker}}^{\prime}+f_{1}$

6 recharge to $F_{\textit{tracker}}$

7 Accept $x$

Algorithm 2 Unidirectional transaction stream without rejection

Now, we present a $2$-competitive online algorithm ON for this sub problem
(Algorithm 2). ON uses $(\gamma,\delta)$-recharging with parameters $\gamma=1$
and $\delta=f_{1}$. The recharging ensures that ON always has enough funds to
accept a transaction. The following theorem shows that ON is $2$-competitive.

###### Theorem 4.1

Algorithm 2 is $2$-competitive in the unidirectional transaction stream
without rejection.

###### Proof

From Lemma 1, setting $\gamma=1$ and $\delta=f_{1}$ gives ON a cost of at most
$A_{t}+f_{1}+f_{1}\cdot\lceil\frac{A_{t}}{f_{1}}\rceil$. Since
$f_{1}\cdot\lceil\frac{A_{t}}{f_{1}}\rceil\leq
f_{1}\cdot(\frac{A_{t}}{f_{1}}+1)=A_{t}+f_{1}$, the cost of ON is at most
$2(A_{t}+f_{1})$. From Lemma 2, we know that the cost of OFF is at least
$A_{t}+f_{1}$. Thus, ON is $2$-competitive.

In addition, we note that ON is optimal in this setting. The next theorem
proves that no deterministic algorithm can achieve a strictly smaller
competitive ratio compared to ON. The proof shows that ON cannot lock too much
funds into the channel, otherwise ON’s cost is too high, but if ON locks too
little funds, it needs to recharge often.

###### Theorem 4.2

There is no deterministic algorithm that is $c$-competitive for $c<2$ in the
unidirectional transaction stream without rejection sub problem.

###### Proof

We prove the theorem by contradiction. For the sake of contradiction, suppose
that there exists a $c$-competitive algorithm ON for $c=2-\varepsilon$ for
some $\varepsilon>0$. Consider the following sequence of transactions:
$\frac{\varepsilon}{3},\frac{\varepsilon}{3},\frac{\varepsilon}{3},\dots$. We
note that when the sequence of transactions is of length $k$, the cost of OFF
is $f_{1}+k\cdot\frac{\varepsilon}{3}$ as the optimal solution is to recharge
the channel at the start of the sequence to the total sum of the transactions
in the sequence.

For ON to remain $(2-\varepsilon)$-competitive after processing the first
transaction, ON locked at most $f_{1}-\varepsilon f_{1}+\frac{\varepsilon}{3}$
in the channel ($\textsc{Cost}_{\textsc{ON}}(X_{1})=2f_{1}-\varepsilon
f_{1}+2\frac{\varepsilon}{3}$).

We generalize the above idea and show that either ON has always smaller amount
than $f_{1}-\frac{\varepsilon}{3}$ in the channel or at some point it has at
least $f_{1}-\frac{\varepsilon}{3}$. In both cases, we derive a contradiction
to the $(2-\varepsilon)$ competitive ratio of ON.

First, suppose that ON always recharges to at most
$f_{1}-\varepsilon^{\prime}$ for some $\varepsilon^{\prime}>0$. Then after $t$
transactions, the number of rechargings is at least
$\lceil\frac{t\frac{\varepsilon}{3}}{f_{1}-\varepsilon^{\prime}}\rceil$. So
$\textsc{Cost}_{\textsc{ON}}(X_{t})\geq
t\cdot\frac{\varepsilon}{3}+f_{1}\lceil\frac{t\frac{\varepsilon}{3}}{f_{1}-\varepsilon^{\prime}}\rceil$.
Setting $t=\frac{3k(f_{1}-\varepsilon^{\prime})}{\varepsilon}$ for some $k$
gives
$\textsc{Cost}_{\textsc{OFF}}(X_{t})=f_{1}+k(f_{1}-\varepsilon^{\prime})$ and
$\textsc{Cost}_{\textsc{ON}}(X_{t})=k(f_{1}-\varepsilon^{\prime})+kf_{1}$, but
since
$\lim_{k\to\infty}\frac{2kf_{1}-k\varepsilon^{\prime}}{(k+1)f_{1}-k\varepsilon^{\prime}}=\frac{2f_{1}-\varepsilon^{\prime}}{f_{1}-\varepsilon^{\prime}}$
for any $\varepsilon^{\prime}$, then the competitive ratio is at least $2$.

Now, suppose that $t$ is the first time that after processing a transaction,
ON has at least $f_{1}-\frac{\varepsilon}{3}$ locked in the channel. At time
$t$, $\textsc{Cost}_{\textsc{OFF}}(X_{t})=f_{1}+t\frac{\varepsilon}{3}$. Cost
of ON is $f_{1}+t\frac{\varepsilon}{3}$ for funds locked in the channel plus
any additional recharging cost. But since it is the first time ON recharged by
more than $f_{1}$, the cost for recharging is
$f_{1}\lceil\frac{t\frac{\varepsilon}{3}}{f_{1}-\varepsilon^{\prime}}\rceil\geq
f_{1}+\frac{t\varepsilon}{3}$ for some other positive $\varepsilon^{\prime}$.
So again, $\textsc{Cost}_{\textsc{ON}}(X_{t})\geq
t\frac{\varepsilon}{3}+f_{1}+t\frac{\varepsilon}{3}+f_{1}=2(f_{1}+t\frac{\varepsilon}{3})$
which is twice of $\textsc{Cost}_{\textsc{OFF}}(X_{t})$.

In both cases the cost of ON is at least twice that of OFF which contradicts
the assumption that ON is $(2-\varepsilon)$-competitive.

##  5 Step 2: Unidirectional transaction stream with rejection

In this section we consider the second sub problem where transactions are
still streaming along a given payment channel $(\ell,r)$ in one direction
(wlog left to right). This time though, a user can choose to reject incoming
transactions. We describe an algorithm (detailed in Algorithm 3) with
competitive ratio $2+\frac{\sqrt{5}-1}{2}$. We note that the competitive ratio
for this setting is larger than the competitive ratio we achieve in the
previous setting as OFF has a wider range of decisions.

Let us call a transaction of size $x$ _big_ if $x>Rx+f_{2}$ and _small_
otherwise. We first observe that OFF in this setting always rejects big
transactions.

###### Lemma 3

OFF rejects all big transactions in the unidirectional transaction stream with
rejection.

###### Proof

Accepting a transaction $x$ incurs a cost of $x$ for increasing funds.
Rejecting a transaction $x$ incurs a cost of $Rx+f_{2}$. So any big
transaction should be rejected.

Thus, the strategy of OFF in this setting is to simply reject all big
transactions. Moreover, if there are sufficiently many small transactions in
the sequence to offset the cost of recharging, OFF makes a single recharging
action at the beginning of the sequence of size $\sum_{x\in X_{t},x\text{ is
small }}x$ for a cost of $f_{1}+\sum_{x\in X_{t},x\text{ is small }}x$.

Initialise: tracker $F_{\textit{tracker}},X\leftarrow 0,\emptyset$

Initialise: balance $b=0$

1 for  _transaction $x$ in order of arrival_ do

2 concatenate $x$ to $X$

3 $F_{\textit{tracker}}^{\prime}\leftarrow\textsc{Funds}(X)$

4 if  _$F_{\textit{tracker}}^{\prime} >F_{\textit{tracker}}$_ then

5 $F_{\textit{tracker}}\leftarrow
F_{\textit{tracker}}^{\prime}+\frac{\sqrt{5}-1}{2}f_{1}$

6 recharge to $F_{\textit{tracker}}$

7 if  _ $b\geq x$ and $x$ is small _ then

8 Accept $x$

9 else

10 Reject $x$

11

Algorithm 3 Unidirectional transaction stream with rejection

Algorithm 3 performs $(1,\frac{\sqrt{5}-1}{2}f_{1})$-recharging and it accepts
a transaction $x$ if it has enough funds and $x$ is small. The following
theorem states that ON is $(2+\frac{\sqrt{5}-1}{2})$-competitive in this
problem setting.

###### Theorem 5.1

Algorithm 3 is $(2+\frac{\sqrt{5}-1}{2})$-competitive in the unidirectional
transaction stream with rejectionsub problem.

###### Proof

From Lemma 3, OFF rejects big transactions. Thus, ON should also reject these
transactions.

While $A_{t}=0$, both OFF and ON reject all transactions in the sequence and
both incur the same cost. The moment $A_{t}>0$, we know that OFF recharged
with an amount at least $A_{t}$ to accept all small transactions in the
sequence. Thus $\textsc{Cost}_{\textsc{OFF}}(X_{t})\geq A_{t}+f_{1}$.

At this time ON would have rejected the small transactions in the sequence for
at most a cost of $A_{t}+f_{1}$ together with some additional recharging cost.
From Lemma 1, we know that the recharging cost for ON is at most

$A_{t}+\frac{\sqrt{5}-1}{2}f_{1}+\left\lceil\frac{A_{t}}{\frac{\sqrt{5}-1}{2}f_{1}}\right\rceil
f_{1}\leq
A_{t}+\frac{\sqrt{5}-1}{2}f_{1}+\frac{A_{t}}{\frac{\sqrt{5}-1}{2}}+f_{1}.$

Summing up both costs, we get

$\displaystyle\textsc{Cost}_{\textsc{ON}}(X_{t})\leq$ $\displaystyle
A_{t}+f_{1}+A_{t}+\frac{\sqrt{5}-1}{2}f_{1}+\frac{A_{t}}{\frac{\sqrt{5}-1}{2}}+f_{1}$
$\displaystyle=$
$\displaystyle\left(2+\frac{\sqrt{5}-1}{2}\right)\textsc{Cost}_{\textsc{OFF}}(X_{t})$

Before analysing the optimality of ON, we first observe, as a simple corollary
of Theorem 4.2, that the lower bound of $2$ also holds for this sub problem.

###### Corollary 1

There is no deterministic algorithm that is $c$-competitive for $c<2$ in the
unidirectional transaction stream with rejection sub problem.

We conjecture that no other deterministic algorithm can perform better that ON
in this setting. Moreover, we sketch an approach to prove the conjecture in
Appendix 0.A.

###### Conjecture 1

There is no deterministic algorithm that is $c$-competitive for
$c<2+\frac{\sqrt{5}-1}{2}$ in the unidirectional transaction stream with
rejection setting.

##  6 Final step: Bidirectional transaction stream

In this section, we consider the most general problem setting, where for a
given payment channel $(\ell,r)$, transactions stream along the channel
$(\ell,r)$ in both directions. A user $\ell$ (resp. $r$) can accept or reject
incoming transactions that stream from left to right (resp. right to left).
Either user would incur a cost of $Rx+f_{2}$ for rejecting a transaction of
size $x$. $\ell$ does not need to take any action when encountering
transactions that stream from right to left as they simply increase the
balance of $\ell$ in the channel $(\ell,r)$. Both users can also decide at any
point to recharge their channel on-chain, or rebalance their channel off-
chain.

###  6.1 Main algorithm

Here we present our online algorithm for the bidirectional transaction stream
setting. For simplicity, we assume that $R=0$ in the rejection cost. This
means that the cost of rejecting a single transaction of size $x$ is simply
$f_{2}$. Likewise, since we assume $R=0$, rebalancing an amount of $x$ off-
chain now only incurs a cost of $Cf_{2}$.

The main algorithm ON is detailed in Algorithm 6. It is run by both users on a
payment channel. In a nutshell, ON is composed of three algorithms: the first
is a recharging algorithm to determine when and how much to recharge the
channel on-chain. The second algorithm (Algorithm 4) decides whether to accept
or reject new transactions and when to perform off-chain rebalancing. The last
algorithm (Algorithm 5) describes how to store the funds received from the
other user of the channel.

Figure 3: An example of how funds are transferred across a payment channel and
how buckets are refilled. Both $\ell$ and $r$ start with full buckets. The
first transaction is in the left-to-right direction and is transferred using
funds from $B_{2}^{\ell}$ to $B_{o}^{r}$. The second transaction is in the
right-to-left direction and is small, thus funds from $B^{r}_{s}$ are used.
$B^{r}_{s}$ is immediately refilled using funds from $B^{r}_{o}$. The third
transaction is in the left-to-right direction and uses funds from
$B_{1}^{\ell}$.

####  6.1.1 $(4+2\lceil\log C\rceil,f_{1})$-recharging

ON runs an on-chain recharging algorithm similar to Algorithm 1 (see Algorithm
6 and Algorithm 6 in Algorithm 6) but with parameters $\gamma=4+2\lceil\log
C\rceil$ and $\delta=f_{1}$. Since we are in the bidirectional transaction
stream setting, Funds returns the amount of funds OFF has inside the entire
channel (i.e. $\emph{b}(\ell)+\emph{b}(r)$) given a transaction sequence.

Let us look at the period between the on-chain recharging instances of ON.
From Algorithm 6 in Algorithm 6, we know that ON ensures that it has more than
$4+2\lceil\log C\rceil$ times more funds than OFF locked in the channel. These
funds are distributed in the following way: ON initialises $\lceil\log
C\rceil+2$ “buckets” on each end of the channel. We denote set of left-side
buckets as $B^{\ell}$ and it consists of
$B_{s}^{\ell},B_{1}^{\ell},\dots,B_{\lceil\log C\rceil}^{\ell},B_{o}^{\ell}$.
Likewise, the set of right-side buckets is $B^{r}$ and it consists of
$B_{s}^{r},B_{1}^{r},\dots,B_{\lceil\log C\rceil}^{r},B_{o}^{r}$.

After recharging, users decide how to distribute funds in the channel, so the
buckets $B_{s}^{\ell}$ and $B_{s}^{r}$ are filled with $2F_{\textit{tracker}}$
funds. Buckets $B_{o}^{\ell}$ and $B_{o}^{r}$ are empty ($0$ funds). Other
buckets contain $F_{\textit{tracker}}$ funds.

Looking ahead, the funds in the $i$-th bucket on both sides are used to accept
transactions $x$ with a size in the interval
$\left[\frac{F_{\textit{tracker}}}{2^{i}},\frac{F_{\textit{tracker}}}{2^{i-1}}\right)$.
The funds in $B_{s}$ are used to accept transactions with a size less than
$\frac{F_{\textit{tracker}}}{C}$. Finally, $B_{o}$ stores excess funds coming
from payments from the other side when all other buckets are full.

####  6.1.2 Transaction handling

When a transaction arrives at the channel, based on the direction of the
transaction, either $\ell$ or $r$ executes Algorithm 4 to decide whether to
accept the transaction. Wlog let us assume $\ell$ encounters transaction
$\overscriptrightarrow{x}$. If
$\frac{F_{\textit{tracker}}}{2^{i}}<x\leq\frac{F_{\textit{tracker}}}{2^{i-1}}$
for some $i\in[\lceil\log C\rceil]$ and $B_{i}^{\ell}$ has sufficient funds,
the funds from $B_{i}^{\ell}$ are used to accept the transaction. If
$B_{i}^{\ell}$ lacks sufficient funds for accepting $x$, $\ell$ rejects $x$.

Now, we consider the case where $x\leq\frac{F_{\textit{tracker}}}{C}$. If
$B_{s}^{\ell}$ has sufficient funds, $\ell$ uses the funds from $B_{s}^{\ell}$
to accept $x$. If $B_{s}^{\ell}$ has insufficient funds to accept $x$, $\ell$
performs off-chain rebalancing with an amount such that after deducting $x$
from $B_{s}^{\ell}$, there would still be $2F_{\textit{tracker}}$ funds left
in $B_{s}^{\ell}$. $\ell$ subsequently accepts $x$. The required funds for
off-chain rebalancing are transferred from $B_{o}^{r}$ and $B_{s}^{r}$ (see
Algorithm 4 and Algorithm 4 in Algorithm 4). Whenever $B_{o}^{\ell}>0$ and
some bucket in $B^{\ell}$ gets under its original capacity, funds are
reallocated from $B_{o}^{\ell}$ to fill the bucket. Figure 3 depicts an
example of how funds are used from different buckets to accept transactions.

####  6.1.3 Handling funds coming from the other side

When a transaction $x$ is accepted by wlog $\ell$, ON calls Algorithm 5 to
distribute the transferred funds among $r$’s buckets in the following way: $r$
first uses $x$ to fill $B_{s}^{r}$ up to its capacity of
$2F_{\textit{tracker}}$ (see Algorithm 5 in Algorithm 5). If there are still
funds left, $r$ refills the $B_{i}^{r}$ buckets in descending order from
$i=\lceil\log C\rceil$ to $i=1$. Intuitively, the reason why buckets are
refilled in descending order is due to our simplified cost model for this
problem where we assume the cost of rejection for any transaction is $f_{2}$.
Thus, rejecting three small transactions size $x$ costs thrice as much as
rejecting a larger transaction of size $3x$. Finally, if there are still some
funds left, they are added to $B_{o}^{r}$.

1 _Decide($F_{\textit{tracker}},x,B^{sdr},B^{rcv}$)_

2 $Status\leftarrow\mathtt{Accept}$

3 if  _$\frac{F_{\textit{tracker}}}{2^{i}}
<x\leq\frac{F_{\textit{tracker}}}{2^{i-1}}\;and\;x\leq B_{i}^{sdr}$_ then

4 Accept $x$

5 $X\leftarrow\min(F_{\textit{tracker}},B_{i}^{sdr}-x+B_{o}^{sdr})$

6
$B_{o}^{sdr}\leftarrow\max(0,B_{i}^{sdr}-x+B_{o}^{sdr}-F_{\textit{tracker}})$

7 $B_{i}^{sdr}\leftarrow X$

8

9 else if  _$x_{i}\leq\frac{F_{\textit{tracker}}}{C}\;and\;x\leq B_{s}^{sdr}$_
then

10 Accept $x$

11 $X\leftarrow\min(2F_{\textit{tracker}},B_{s}^{sdr}-x+B_{o}^{sdr})$

12
$B_{o}^{sdr}\leftarrow\max(0,B_{s}^{sdr}-x+B_{o}^{sdr}-2F_{\textit{tracker}})$

13 $B_{s}^{sdr}\leftarrow X$

14 else if  _$x_{i}\leq\frac{F_{\textit{tracker}}}{C}\;and\;x >B_{s}^{sdr}$_
then

15 Do off-chain rebalancing to fill $B_{s}$ and pay $f_{2}C$.

16 $B_{o}^{rcv}\leftarrow B_{o}^{rcv}-(2F_{\textit{tracker}}-B_{s}^{sdr})$.

17 $B_{s}^{rcv}\leftarrow B_{s}^{rcv}-x$.

18 Accept $x$

19 $B_{s}^{sdr}\leftarrow 2F_{\textit{tracker}}$.

20

21 else

22 Reject x

23 $Status\leftarrow\mathtt{Reject}$

24 return $(B^{sdr},B^{rcv},Status)$

Algorithm 4 Decision on transaction

1

2

3 _HandleFunds($F_{\textit{tracker}},x,B$)_

4 $X\leftarrow\min(2F_{\textit{tracker}},B_{s}+x)$

5 $x\leftarrow\max(x+B_{s}-2F_{\textit{tracker}},0)$

6 $B_{s}\leftarrow X$

7 for  _$i\in[\lceil\log C\rceil]$ in decreasing order_ do

8 if  _$x >0$_ then

9 $X\leftarrow\min(F_{\textit{tracker}},B_{i}+x)$

10 $x\leftarrow\max(x+B_{i}-F_{\textit{tracker}},0)$

11 $B_{i}\leftarrow X$

12

13

14 $B_{o}\leftarrow B_{o}+x$ return $(B)$

Algorithm 5 Handling funds coming from the other side

1

Initialise : left side buckets $B^{\ell}$

Initialise : right side buckets $B^{r}$

Initialise : tracker $F_{\textit{tracker}},X\leftarrow 0,\emptyset$

2

3for  _transaction $x$ in order of arrival_ do

4 concatenate $x$ to $X$

5 $F_{\textit{tracker}}^{\prime}\leftarrow\textsc{Funds}(X)$

6 if  _$F_{\textit{tracker}}^{\prime} >F_{\textit{tracker}}$_ then

7 $F_{\textit{tracker}}\leftarrow F_{\textit{tracker}}^{\prime}+f_{1}$

8 recharge to $2(2+\lceil\log C\rceil)F_{\textit{tracker}}$

9 $sdr,rcv\leftarrow\ell,r$

10 if  _$x$ is from right to left _ then

11 $sdr,rcv\leftarrow r,\ell$

12
$B^{sdr},B^{rcv},Status\leftarrow\textsc{Decide}(F_{\textit{tracker}},x,B^{sdr},B^{rcv})$

13 if  _$Status==\mathtt{Accept}$_ then

14 $B^{rcv}\leftarrow\textsc{HandleFunds}(F_{\textit{tracker}},x,B^{rcv})$

15

16

Algorithm 6 Main algorithm

###  6.2 A $7+2\lceil\log C\rceil$ competitive online algorithm

###### Theorem 6.1

Algorithm 6 is $7+2\lceil\log C\rceil$ competitive.

###### Proof

We know that for any $i$,
$\textsc{Cost}_{\textsc{OFF}}(X_{i})\geq\textsc{Cost}_{\textsc{OFF}}(X_{i-1})$.
From Lemma 1 and Lemma 2, we know that cost of ON for recharging (in Algorithm
6) is at most $(5+2\lceil\log C\rceil)\textsc{Cost}_{\textsc{OFF}}(X_{t})$.
Let $t_{1}$ and $t_{2}$ (with $t_{2}>t_{1}$) be the two consecutive times ON
recharges, then we show that the cost of ON for rebalancing and rejection is
smaller than
$2(\textsc{Cost}_{\textsc{OFF}}(X_{t_{2}})-\textsc{Cost}_{\textsc{OFF}}(X_{t_{1}}))$.
Then $\textsc{Cost}_{\textsc{ON}}(X_{t})\leq(7+2\lceil\log
C\rceil)\textsc{Cost}_{\textsc{OFF}}(X_{t})$.

For every strategy of OFF and any two consecutive recharging times $t_{1}$ and
$t_{2}$, we show that the rebalancing and rejection cost of ON between times
$t_{1}$ and $t_{2}$ is at most twice that of OFF as defined by the strategy.
Having the strategy of OFF, we split the time between rechargings even
further, into epochs; we will show that the competitive ratio of $2$ holds for
every epoch.

The left epoch starts with the first transaction that makes some bucket in
$B^{\ell}$ non-full (smaller than the original amount); the left epoch ends
either before ON recharges, or $B_{o}^{\ell}>0$. In a left epoch, every
transaction from the right side is accepted; non-fullness of some buckets on
one side means $B_{o}>0$ on the other side. The right epoch is defined
similarly, but since the epochs are disjoint, we can prove the statement for a
left epoch only.

For transactions below $\frac{F_{\textit{tracker}}}{C}$, we argue that the
cost of ON is at most the cost of OFF. ON accepts everything, so ON pays only
for rebalancing. OFF either rebalances too, in which case the cost is the same
as ON; or it rejected some transactions. Since ON starts with
$2F_{\textit{tracker}}$ funds in $B_{s}$ and refills the bucket with the
highest priority, this means OFF rejected some transactions summing to at
least $F_{\textit{tracker}}$. There are at least $C$ of them, so OFF’s cost is
also above $Cf_{2}$. If there is a counterexample containing a small
transaction that OFF rejects, then we can modify it to a counterexample where
the transaction is increased to $\frac{F_{\textit{tracker}}}{C}$. So we can
show the ratio in the case that no small transactions are coming.

Now that we have the strategy for OFF (decisions before rebalancing), we
define some variables that track the competitive ratio. We will look at
incoming transactions, and prove that the competitive ratio is always below
$2$. We say that a transaction $x$ belongs to a bucket $B_{i}$ if
$\frac{F_{\textit{tracker}}}{2^{i}}<x\leq\frac{F_{\textit{tracker}}}{2^{i-1}}$.
A transaction is red if it is rejected by ON and accepted by OFF and it is
blue if it is accepted by ON and rejected by OFF. Let $\rho_{i}$ ($\beta_{i}$)
be the number of red (blue) transactions in the bucket $B_{i}$. We can
disregard transactions for which ON and OFF make the same decision. If the
transaction is rejected by both, it improves the ratio. If the transaction is
accepted by both, it can be simulated by decreasing $F_{\textit{tracker}}$.

We prove by induction that $\sum_{k\leq j}\rho_{k}\leq 2\sum_{k\leq
j}\beta_{k}$ for all $j$. We show that if the equality holds and OFF has
enough funds to accept incoming transactions, ON accepts too.

Let us examine $j=\lceil\log C\rceil$. We know that the ratio between any two
transaction sizes in $B_{\lceil\log C\rceil}$ is less than $2$, so any two red
transactions are bigger than one blue. Moreover, all funds that arrived from
the right side were put into $B_{\lceil\log C\rceil}$ (if it is not full). So
if $\rho_{\lceil\log C\rceil}=2\beta_{\lceil\log C\rceil}$, ON has at least
the amount of funds in $B_{\lceil\log C\rceil}$ OFF has. To continue the
induction for buckets with smaller indices, we reassign some red or blue
transactions to different buckets. If $\rho_{\lceil\log
C\rceil}<2\beta_{\lceil\log C\rceil}$, we move at most one red and some blue
transactions (in decreasing order of size) to $B_{\lceil\log C\rceil-1}$,
stopping just before $\rho_{\lceil\log C\rceil}\geq 2\beta_{\lceil\log
C\rceil}$.

For general $j$, we know that, due to the reassignment, in every bucket
smaller than $j$, ON rejected exactly twice the number of transactions OFF
did. Moreover, OFF needs to use at least the same amount of funds to accept
red transactions compared to funds needed by ON to accept blue ones. Now, in
the bucket $B_{j}$ holds $\rho_{j}=2\beta_{j}$. Again, we pair every two red
transactions to one blue, such that the sum of red is bigger than blue. Before
the reassignment, the ratio between any two transactions is at most $2$. The
reassignment (if occurred) moved at most one red and at least one blue that is
smaller than any original transaction in the bucket, so we can pair the moved
red to moved blue. In transactions in buckets in $j$ and bigger, OFF used more
funds than ON. Any funds that arrived from the right side were put into some
bucket in $j$ or below, so if OFF has enough funds to accept, ON has too.

The same argument holds for a right-epoch, and we note that epochs are
disjoint and cover the entire transaction sequence between times $t_{1}$ and
$t_{2}$. Since we chose the consecutive recharging times $t_{1}$ and $t_{2}$
arbitrarily, the rebalancing and rejection cost of ON between any two
consecutive rechargings is at most twice that of OFF within the same period.
Therefore, Algorithm 6 is $7+2\lceil\log C\rceil$ competitive.

Moreover, observe that depending on the value of $C$, we can tweak the
algorithm. There can be a smaller number of buckets that accept transactions
in a bigger range.

###  6.3 Lower bound

In this subsection, we show how much funds ON needs to lock in the channel to
have a chance to be $c$ competitive. We make the construction for $A$, the
amount of funds that OFF locked in the channel. Observe that OFF would rather
reject transactions that have average size larger than $\frac{A}{C}$ than
perform off-chain rebalancing to accept them.

###### Lemma 4

For any $A$, if ON’s cost for rejection is at most $c$ times OFF’s cost for
rejection (for $c<\frac{\log C}{\log\log C}$), any deterministic ON needs to
lock at least $\sigma=A\cdot\left(\frac{\frac{1}{c+1}\log C}{\log
c+1}+1\right)$ funds in the channel.

###### Proof

We describe an epoch: OFF starts with $A$ funds left, then some transactions
are sent from left to right and finally one transaction of size $A$ is sent
right to left. If the funds in the channel of ON is smaller than $\sigma$,
then the cost of ON is more than $c$ times that of OFF.

One epoch consists of at most $\frac{\log C}{\log c+1}+1$ phases. In phase $i$
(starting from $i=0$), there are $(c+1)^{i}$ transactions of size
$\frac{A}{(c+1)^{i}}$. OFF always accepts all transactions in the latest
phase. If at the end of any phase, the cost of ON is more than $c$ times of
OFF, then a transaction of size $A$ is sent back and another epoch starts.
Observe that for $c<\frac{\log C}{\log\log C}$, after rebalancing the epoch
ends too (because the cost is $c$ times bigger). We can assume this cannot
happen, ON does not perform off-chain rebalancing.

We compute how much funds ON needs to stay within the competitive ratio until
the last phase (where transactions of sizes $\frac{A}{C}$ are sent). After
phase $i$, OFF accepted $(c+1)^{i}$ transactions and rejected
$\frac{(c+1)^{i}-1}{c}$, so OFF can reject up to $(c+1)^{i}-1$ transactions
among $\frac{(c+1)^{i+1}-1}{c}$. So ON has to accept at least
$\frac{(c+1)^{i+1}-1-c(c+1)^{i}+c}{c}=(c+1)\frac{(c+1)^{i-1}-1}{c}$
transactions.

The size of transactions is decreasing, so optimally, ON accepts transactions
when they are needed. So in phase $i+1$ it needs to accept
$(c+1)\frac{(c+1)^{i}-1}{c}-(c+1)\frac{(c+1)^{i-1}-1}{c}=(c+1)^{i}$
transactions. Of course, it needs to accept the transaction in the phase $0$.

The cost of transactions accepted by ON in phase $i>0$ is
$(c+1)^{i-1}\frac{A}{(c+1)^{i}}=\frac{A}{c+1}$. To maintain the competitive
ratio ON needs to accept transactions worth $A+A\frac{\log C}{\log c+1}$ in
total. Independently of the cost of OFF and ON before, there can be one epoch
after another where the ratio is worse than $c$, so at the end, the ratio
would be above $c$.

###### Theorem 6.2

There is no deterministic $c$-competitive algorithm for $c\in o(\sqrt{\log
C})$.

###### Proof

From Lemma 4 for any $A$, ON needs $A\cdot(\frac{\frac{1}{c+1}\log C}{\log
c+1}+1)$ funds to have its rejection cost $c$-competitive. But ON also needs
to lock some funds in the channel. The total cost is then
$c+A(\frac{\frac{1}{c+1}\log C}{\log c+1}+1)$, which is bigger than
$\mathcal{O}(\sqrt{\log C})$.

##  7 Evaluation

We now complement our theoretical worst-case analysis and study the
performance of our algorithms empirically.

###  7.1 Methodology

In order to study average case behavior, we consider the performance of our
main algorithm ON (Algorithm 6) on randomly generated transaction sequences in
the general bidirectional transaction stream setting. Our benchmark is the
performance of the optimal offline algorithm OFF, however, since computing
optimal solutions is NP-hard [18], computing the achieved competitive ratio in
simulations is computationally expensive. In order to have a baseline
nevertheless, we use dynamic programming to exactly and efficiently compute
the cost of OFF for sequences of reasonable lengths. For ease of presentation,
we defer this algorithm to Appendix 0.B. We additionally conduct experiments
using actual Lightning Network data, and considering realistic parameters.

###  7.2 Comparison of ON to OFF

##### Average performance of ON

We first report on the competitive ratio our online algorithm achieves under
random transaction sequences. We begin by sampling $50$ random transaction
sequences of length $50$ each. In each sequence, transaction sizes are first
sampled independently from the folded normal distribution with mean $0$ and
standard deviation $3$, and then we sample the direction of the transaction
(left-to-right or right-to-left) uniformly at random. Finally, we quantise the
size of the transaction to the closest integer. We then run both OFF and ON on
the generated sequences and compute the average of the following:

  1. 1.

cost (sum of rejection/off-chain rebalancing/on-chain recharging costs)

  2. 2.

sum of funds locked in the channel ($A(X)$)

  3. 3.

acceptance rate (fraction of transactions accepted)

  4. 4.

funds that are transferred across the channel by off-chain rebalancing per
sequence

  5. 5.

number of on-chain rechargings per sequence

We present our results in Table 3. As we can see from the cost of ON vs OFF in
Table 3, the competitive ratio is generally significantly lower than the
$7+2\lceil\log C\rceil$ bound as suggested by our conservative worst-case
analysis in Theorem 6.1.

##### Heuristics to improve the performance of ON

However, we notice in our experiments that ON seems to overcharge the channel.
This is most noticeable when we observe the effect of $C$ on the performance
of ON. From Table 3, increasing $C$ in a range of medium (not too small)
values does not change OFF’s cost noticeably. In contrast, both the average
cost and total amount of locked funds of ON grows with $C$. This is due to the
fact that ON uses $(4+2\lceil\log C\rceil,f_{1})$-recharging to ensure that it
always has significantly more funds than OFF, even though a big fraction of
these funds remain unspent. ON is also limited by the fact that it does not
borrow funds from other buckets when a bucket is depleted. For instance, ON
always charges $B_{s}$ to $2F_{\textit{tracker}}$ and only uses these funds to
accept transactions that are smaller than $\frac{F_{\textit{tracker}}}{C}$.
Thus, as $C$ increases, the number of transactions that fall into the $B_{s}$
bucket decreases and the funds in $B_{s}$ remain unspent.

These observations motivate us to design a less pessimistic version of ON that
we expect will perform better than ON. We introduce ON-I which is a slightly
altered version of ON: ON-I follows the $(\lceil\log
C\rceil,f_{1})$-recharging algorithm and does not divide the funds into
separate buckets. Instead, ON-I accepts all the transactions smaller than
$F_{\textit{tracker}}$ as long as it has funds. Otherwise, if the transaction
is small ($<\frac{F_{\textit{tracker}}}{C}$) it off-chain rebalances to fill
the bucket and accepts the transaction. Similar to ON, ON-I rejects a
transaction if it is larger than $\frac{F_{\textit{tracker}}}{C}$ .

Our empirical results in Table 3 confirms that the average cost of ON-I is
significantly smaller than ON. The acceptance rate of ON-I is slightly smaller
than ON, which is expected as ON-I does not have separate funds for each range
of transactions (as defined by the buckets), and as a result might miss some
transactions. We observe that ON-I performs more off-chain rebalancings
compared to ON on average because ON-I does not reserve separate funds for
small transactions. However, one issue with both ON and ON-I is that they
recharge the channel too often (as soon as $F_{\textit{tracker}}<A(X_{t})$).
As can be seen from Table 3 ($f_{2}=2$), both algorithms perform more than $5$
rechargings on average for transaction sequences of length $50$. This
increases the cost of both algorithms significantly as each recharging
instance incurs a cost of at least $f_{1}$.

We thus design another version of ON-I to address the aforementioned problem.
ON-II works exactly as ON-I except that it does not recharge the channel as
frequently as ON-I does. ON-II only recharges the channel if $\alpha\cdot
F_{\textit{tracker}}<A(X)$, where $\alpha>1$ is some constant that controls
the how often the algorithm recharges the channel and can be fine-tuned
empirically based on $f_{1}$ and $f_{2}$. If we set $\alpha=1$, ON-II becomes
equivalent to ON-I and has higher acceptance rate. This is favorable when
$f_{2}$ is large and $f_{1}$ is small. Conversely, by increasing $\alpha$, ON-
II recharges the channel less frequently but the acceptance rate falls. This
is favorable when $f_{1}$ is large and $f_{2}$ is small. In our experiments,
we observe that for the case $f_{2}=2,C=2$, when all the other parameters are
as Table 3, $\alpha=2$ yields the lowest average cost. Thus, in our evaluation
of ON-II, we use $\alpha=2$ and from Table 3 we note that this choice of
$\alpha$ halves the number of rechargings compared to ON-I, which consequently
leads to lower average cost. Additionally, we note that the total amount of
funds in the channel of ON-II is close to OFF.

##### Varying the distribution of the generated sequences

We also evaluate how the performance of our algorithms is affected by the
variance of the transaction size. We sample $50$ sequences each of length $50$
with each transaction in the sequence independently sampled from the folded
normal distribution with mean 0 and standard deviation $\sigma$, for a range
of $\sigma$ values across $[3,20]$. The transactions are quantised to the
closest integer, and the direction of each transaction is sampled uniformly at
random. We then observe the cost of ON, ON-I,ON-II and OFF. As can be seen
from in Figure 4, the cost of all $4$ algorithms rises as $\sigma$ increases.
This is due to the fact that increasing the variance of the sampled
transactions reduces the probability of getting a similarly sized transaction
coming from the other side, thus increasing the speed at which the balance on
one side gets depleted. We note, however, that Figure 4 shows that even for
large values of $\sigma$, ON’s average cost remains a lot smaller than the
worst case upper bound of $7+2\lceil\log C\rceil$. We also observe that the
cost of ON-I and ON-II is noticeably smaller than ON and grows at a much
slower pace with respect to increases in $\sigma$.

Another factor we look at is how the asymmetry of the transaction flow along a
channel can affect the performance of our algorithms. To do so, we generate
$50$ sequences each of length $50$, and sample the size of each transaction
from a folded normal distribution with mean $0$ and standard deviation $3$,
and then quantise the transaction to the nearest integer. We then sample the
direction of the transactions according to a Bernoulli distribution with
parameter $p$, where $p$ represents the probability of sampling a left-to-
right transaction. We see from Figure 5 that the cost of all algorithms
decrease as $p$ increases from $0$ to $0.5$. As $p$ increases from $0.5$ to
$1$, the cost function increases again. This conforms to our intuition that
extremely asymmetric sequences are harder to handle as the lack of
sufficiently many transactions from one side just increases the speed at which
the balance on the other side gets depleted. We observe that both ON-I and ON-
II nevertheless perform comparatively better than ON when given these
asymmetric transaction sequences (see Figure 5).

Param | OFF | ON
---|---|---
C |  $f_{2}$ |  Cost |  $A(X)$ |  Accept rate |  Off-chain rebalancing |  Rechargings |  Cost |  $A(X)$ |  Accept rate |  Off-chain rebalancing |  Rechargings
$2$ |  $0.5$ |  15.02 |  $6.4$ |  $0.78$ |  $0.8$ |  $1$ |  63.3 |  $44.26$ |  $0.50$ |  $0.9$ |  $2.18$
$8$ |  $0.5$ |  15.21 |  $6.38$ |  $0.77$ |  $0$ |  $1$ |  87.79 |  $69.06$ |  $0.50$ |  $0$ |  $2.04$
$2$ |  $2$ |  23.6 |  $14.26$ |  $0.95$ |  $5.36$ |  $1$ |  127.02 |  $100.2$ |  $0.91$ |  $0.38$ |  $5.86$
$8$ |  $2$ |  24.5 |  $13.9$ |  $0.92$ |  $0$ |  $1$ |  184.32 |  $156.6$ |  $0.9$ |  $0$ |  $5.84$

Param | ON-I | ON-II
---|---|---
C |  $f_{2}$ |  Cost |  $A(X)$ |  Accept rate |  Off-chain rebalancing |  Rechargings |  Cost |  $A(X)$ |  Accept rate |  Off-chain rebalancing |  Rechargings
$2$ |  $0.5$ |  30.74 |  $6.86$ |  $0.44$ |  $11.18$ |  $2.18$ |  26.52 |  $5.56$ |  $0.41$ |  $10.22$ |  $1.2$
$8$ |  $0.5$ |  39.98 |  $19.86$ |  $0.48$ |  $0$ |  $2.04$ |  32.94 |  $15.9$ |  $0.46$ |  $0$ |  $1.18$
$2$ |  $2$ |  66.16 |  $14.42$ |  $0.84$ |  $25.48$ |  $5.86$ |  60.38 |  $11.3$ |  $0.78$ |  $27.16$ |  $2.2$
$8$ |  $2$ |  81.35 |  $42.72$ |  $0.89$ |  $1.5$ |  $5.84$ |  58.38 |  $33.3$ |  $0.83$ |  $1.56$ |  $2.16$

Table 3: Comparison between the performance of OFF, ON, ON-I and ON-II on
randomly generated transaction streams. The result is averaged over $50$
sequences each of length $50$. The size of each transaction is independently
sampled from the folded normal distribution with mean $0$ and standard
deviation $3$, then quantised to the closest integer. We set $f_{1}=3$ and
$R=0$. $A(X)$ is the total amount of funds in the channel from recharging the
channel. “Accept rate” shows the average fraction of transactions that were
accepted. “Off-chain rebalancing” shows how much funds on average was moved
along the channel using off-chain rebalancing. “Rechargings” shows the average
number of rechargings performed. Note that since OFF knows the entire sequence
in advance, it only recharges the channel once at the beginning of each
sequence.  Figure 4: Average cost of our algorithms over $50$ randomly
generated transaction streams, each of length $50$. The size of each
transaction is independently sampled from the folded normal distribution with
mean $0$ and standard deviation $\sigma$. We use the parameters
$f_{1}=3,f_{2}=2,R=0,C=4,\alpha=2$. Figure 5: Average cost of our algorithms
over $50$ randomly generated transaction streams each of length $50$. The size
of each transaction is sampled from the folded normal distribution with mean
$0$ and standard deviation $3$. $p$ is the probability of sampling a left-to-
right transaction. We use the parameters $f_{1}=3,f_{2}=2,R=0,C=4,\alpha=2$.

###  7.3 Case study: Lightning Network

We conclude our evaluation section with a case study of the Lightning network.
We first run our experiments with realistic parameters taken from Lightning
Network data. In the Lightning Network, $f_{1}$ is the on-chain transaction
fee (roughly around $1000$ satoshi) which is a lot larger than $f_{2}$, the
base fee one receives when forwarding a payment (around $1$ satoshi). Thus,
when we evaluate our algorithms using similar parameters for short transaction
sequences, we observe that OFF rejects all transactions and, in fact, will not
even open a channel as it would incur a larger cost as compared to simply
rejecting transactions.

Next, we conduct an empirical estimation of the average rebalancing cycle
length in the Lightning Network using the latest snapshot (September 2021) of
the Lightning Network from the Lightning Network gossip repository [7]. This
is important as $C$ is an integral component of the competitive ratio in our
main theorem, Theorem 6.1. The Lightning Network snapshot contains $117,894$
channels, including pairs of users with more than one channel between them.
After merging these channel pairs, we get $63,820$ channels. We compute the
length of the shortest cycle containing both $\ell$ and $r$ for every pair of
channel holders $(\ell,r)$. Table 4 shows the frequency of each cycle length
(including the channels that are not part of any cycle at all). From Table 4,
we see that a large fraction of channel holders are part of cycles of length
at least $4$. We note, however, that actual cycles might be longer as precise
balance information is hidden in the Lightning Network snapshot.

Cycle length | $4$ | $5$ | $6$ | $7$ | N.A.
---|---|---|---|---|---
Frequency | $49,424$ | $7,758$ | $469$ | $12$ | $6,157$
Table 4: Frequency of the length of shortest cycle between all users in the
Lightning Network. The last column shows the frequency of channels that are
not part of any cycle. The average cycle length is 4.15

##  8 Conclusion

This paper presents competitive strategies to maintain minimise cost while
maximising liquidity and transaction throughput in a payment channel. Our
algorithms come with formal worst-case guarantees, and also perform well in
realistic scenarios in simulations.

We believe that our work opens several interesting avenues for future
research. On the theoretical front, it would be interesting to close the gap
in the achievable competitive ratio, and to explore the implications of our
approach on other classic online admission control problems. Furthermore,
while in our work we have focused on deterministic algorithms, it would be
interesting to study the power of randomised approaches in this context, or to
consider different adversarial models.

## References

  * [1] Raiden network.  https://raiden.network/, 2017.
  * [2] Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., and Waarts, O. On-line routing of virtual circuits with applications to load balancing and machine scheduling.  Journal of the ACM (JACM) 44, 3 (1997), 486–504.
  * [3] Avarikioti, G., Besic, K., Wang, Y., and Wattenhofer, R. Online payment network design.  CoRR abs/1908.00432 (2019).
  * [4] Avarikioti, Z., Heimbach, L., Wang, Y., and Wattenhofer, R. Ride the lightning: The game theory of payment channels.  In Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers (2020), J. Bonneau and N. Heninger, Eds., vol. 12059 of Lecture Notes in Computer Science, Springer, pp. 264–283.
  * [5] Avarikioti, Z., Pietrzak, K., Salem, I., Schmid, S., Tiwari, S., and Yeo, M. HIDE & SEEK: privacy-preserving rebalancing on payment channel networks.  CoRR abs/2110.08848 (2021).
  * [6] Borodin, A., and El-Yaniv, R. Online computation and competitive analysis.  cambridge university press, 2005.
  * [7] Decker, C. Lightning network research; topology, datasets.  https://github.com/lnresearch/topology.  Accessed: 2022-04-01.
  * [8] Ersoy, O., Roos, S., and Erkin, Z. How to profit from payments channels, 2019.
  * [9] Fazli, M., Nehzati, S. M., and Salarkia, M. Building stable off-chain payment networks.  CoRR abs/2107.03367 (2021).
  * [10] Khalil, R., and Gervais, A. Revive: Rebalancing off-blockchain payment networks.  IACR Cryptol. ePrint Arch. (2017), 823.
  * [11] Li, P., Miyazaki, T., and Zhou, W. Secure balance planning of off-blockchain payment channel networks.  In 39th IEEE Conference on Computer Communications, INFOCOM 2020, Toronto, ON, Canada, July 6-9, 2020 (2020), IEEE, pp. 1728–1737.
  * [12] Lukovszki, T., and Schmid, S. Online admission control and embedding of service chains.  In International Colloquium on Structural Information and Communication Complexity (2015), Springer, pp. 104–118.
  * [13] Malavolta, G., Moreno-Sanchez, P., Kate, A., and Maffei, M. Silentwhispers: Enforcing security and privacy in decentralized credit networks.  In 24th Annual Network and Distributed System Security Symposium, NDSS 2017, San Diego, California, USA, February 26 - March 1, 2017 (2017), The Internet Society.
  * [14] Pickhardt, R., and Nowostawski, M. Imbalance measure and proactive channel rebalancing algorithm for the lightning network.  In IEEE International Conference on Blockchain and Cryptocurrency, ICBC 2020, Toronto, ON, Canada, May 2-6, 2020 (2020), IEEE, pp. 1–5.
  * [15] Poon, J., and Dryja, T. The bitcoin lightning network: Scalable off-chain instant payments.  https://lightning.network/lightning-network-paper.pdf, 2015.
  * [16] Prihodko, P., Zhigulin, S. N., Sahno, M., Ostrovskiy, A. B., and Osuntokun, O. Flare : An approach to routing in lightning network white paper.
  * [17] Roos, S., Moreno-Sanchez, P., Kate, A., and Goldberg, I. Settling payments fast and private: Efficient decentralized routing for path-based transactions.  In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018 (2018), The Internet Society.
  * [18] Schmid, S., Svoboda, J., and Yeo, M. Weighted packet selection for rechargeable links: Complexity and approximation, 2022.
  * [19] Sivaraman, V., Venkatakrishnan, S. B., Ruan, K., Negi, P., Yang, L., Mittal, R., Fanti, G. C., and Alizadeh, M. High throughput cryptocurrency routing in payment channel networks.  In 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020, Santa Clara, CA, USA, February 25-27, 2020 (2020), R. Bhagwan and G. Porter, Eds., USENIX Association, pp. 777–796.
  * [20] van Engelshoven, Y., and Roos, S. The merchant: Avoiding payment channel depletion through incentives.  2021 IEEE International Conference on Decentralized Applications and Infrastructures (DAPPS) (2021), 59–68.

##  Appendix 0.A Optimality of deterministic algorithms in a unidirectional
stream with rejection

Sketch proof of Conjecture 1.

######  Proof (Sketch)

The best ON algorithm needs to recharge the channel when OFF does. If it
recharges the channel later, it incurs cost that OFF is not incurring, so the
competitive ratio worsens. If it recharges sooner, there exists a sequence
that either forces OFF to waste funds or incur a big cost.

After OFF recharges, it can reconsider and accept previously rejected
transactions, but ON needs to reject them. Now, the situation is similar as in
the case without rejection. ON needs to recharge, but it already paid for some
rejections whereas OFF pays only for recharging and accepting very small
transactions.

ON disadvantaged in this way cannot achieve a better competitive ratio than
$2+\frac{\sqrt{5}-1}{2}$

##  Appendix 0.B Computing the cost of OFF using dynamic programming

In this section, we describe a dynamic programming algorithm ON that solves
the main problem. We assume that the size of transactions is integer (moreover
the sum of transactions should be small).

Let $\textsc{Cost}_{i}(F_{\ell},F_{r})$ be the minimum cost for rejecting and
off-chain rebalancing in processing sequence $X_{i}$ that ends with
$b(\ell)=F_{\ell}$ and $b(r)=F_{r}$ (For values of $F_{\ell}$ and $F_{r}$
smaller that $0$, we define it to be $\infty$).
$\textsc{Cost}_{i}(F_{\ell},F_{r})$ can be derived from $\textsc{Cost}_{i-1}$
given the decision on the $i$’th transaction.

Let us assume wlog that $i$’th transaction is from $\ell$ to $r$. OFF has
three choices when encountering $x_{i}$. The first option is to reject
$x_{i}$, the the cost is
$A_{1}=\textsc{Cost}_{i-1}(F_{\ell},F_{r})+Rx_{i}+f_{2}$. The second option is
to accept $x_{i}$ which gives cost
$A_{2}=\textsc{Cost}_{i-1}(F_{\ell}+x_{i},F_{r}-x_{i})$. The last option is to
off-chain rebalance before $x_{i}$ and then accept $x_{i}$. Note that any off-
chain rebalancing before rejecting or accepting (while having enough funds)
can be postponed. This gives cost $A_{3}=\min_{a\leq
F_{\ell}+x_{i}}\textsc{Cost}_{i-1}(a,F_{r}+F_{\ell}-a)+C\cdot
R(F_{\ell}+x_{i}-a)+Cf_{2}$. OFF chooses the best option, that means
$\textsc{Cost}_{i}(F_{\ell},F_{r})=\min{\\{A_{1},A_{2},A_{3}\\}}$

We handle right to left transaction in the same way.

Given the previous, ON computes $\textsc{Cost}_{t}$ for all valid pairs
$(F_{\ell},F_{r})$ and the final cost is

$\textsc{Cost}_{\textsc{OFF}}(X_{i})=\min_{F_{\ell},F_{r}}\textsc{Cost}_{t}(F_{\ell},F_{r})+F_{\ell}+F_{r}+f_{1}$

To bound the time complexity of ON, we observe some bounds for
$S=F_{\ell}^{*}+F_{r}^{*}$, where $F_{\ell}^{*}$ and $F_{r}^{*}$ are the
values of $F_{\ell}$ and $F_{r}$ achieving the minimal cost. Observe that
$S\leq\sum_{i\leq t}x_{i}$, it is not worth to have more money than the sum of
the trasactions. We can strenghten the inequality and instead of $\sum_{i\leq
t}x_{i}$, we can compute the minimal amount needed to accept every
transaction. The other option is to reject everything, so we know that
$f_{1}+S\leq\sum_{i\leq t}Rx_{i}+f_{2}$.

Now we can prove the theorem about the described algorithm ON.

###### Theorem 0.B.1

ON computes the optimal cost in time $\mathcal{O}(tS^{3})$, where $S$ is the
bound on the maximal funds in the channel and $t$ the number of transactions.

###### Proof

In the dynamic programming, we take into account all possible decisions ON can
make, by this, correctness follows.

The algorithm ON tries all possible amounts between $1$ and $S$ and starting
distributions. There are $S^{2}$ of them. While computing one value, it needs
to look at at most $S$ precomputed values. And it needs to do it at most $t$
times.

Using dynamic programming for calculating OFF has two advantages. First, we
can easily recover the decisions of OFF. Secondly, dynamic programming
provides us with optimum solution for all subsequences of $X_{t}$. This is
useful for implementing Algorithm 6.