# Image Animation with Keypoint Mask

Or Toledano  Yanir Marmor  Dov Gertz

###### Abstract

Motion transfer is the task of synthesizing future video frames of a single
source image according to the motion from a given driving video. In order to
solve it, we face the challenging complexity of motion representation and the
unknown relations between the driving video and the source image. Despite its
difficulty, this problem attracted great interests from researches at the
recent years, with gradual improvements. The goal is often thought as the
decoupling of motion and appearance, which is may be solved by extracting the
motion from keypoint movement. We chose to tackle the generic, unsupervised
setting, where we need to apply animation to any arbitrary object, without any
domain specific model for the structure of the input. In this work, we extract
the structure from a keypoint heatmap, without an explicit motion
representation. Then, the structures from the image and the video are
extracted to warp the image according to the video, by a deep generator. We
suggest two variants of the structure from different steps in the keypoint
module, and show superior qualitative pose and quantitative scores.

Machine Learning, ICML

Table 1: Motion transfer example: Given a YouTube clip of a Thai-Chi artist
(top), and an image of another one, our method transfers the one’s performance
onto the other (bottom).
|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |

##  1 Introduction

Take a look at Figure 1 for two video sequences. The input is a YouTube clip
of a Thai-Chi artist (the driving subject) performing a series of complex
motions at the top row. Our algorithm’s output is shown at the bottom row. It
refers to frames that appear to show a different person (the source subject)
executing the same motions. The crux is that the source individual has never
performed the same exact sequence of motions as the driver video - they were
photographed doing another movement with no clear reference to the driving’s
actions. By observing the figure, we can see that the source and the driving
are of different appearances, have different backgrounds, and are dressed
differently - a totally different style that we need to ignore when we extract
the structure.

In this study, we propose a simple, however surprisingly efficient approach to
the general motion transfer problem, which can be applied to any domain,
similarly to (Siarohin et al., 2019), (Siarohin et al., 2020): Given a source
image of a person with the wanted appearance, and a driving video with the
wanted structure/geometry, we synthesize a video by applying a deep motion
generator per-frame. We assist the generator by feeding it with compact
structural representations of the source and each frame of the driving video.
That way, we obtain the target of a video of the source appearance and the
driving motion, given any domain. Keeping the generator as a frame processor
enables it to be simple and fast to train and evaluate, but note that there
are works which take into account temporal information, such as (Villegas et
al., 2017) which make a use of LSTM.

Researchers of some notable works (Section 2) observe that keypoint-based pose
preserves motion signatures over time, while abstracting subject identities.
We therefore use the keypoint-based pattern without any other motion priors.
We obtain the keypoints and use them to animate images in a way that doesn’t
need any external information about the subject or any assumption or prior
about the scene.

Our contribution is twofold: first, we demonstrate that removing the explicit
motion prior from works such as FOMM is feasible to the task of image
animation, and creates a compact, faster to train and evaluate model; And
second, we make progress to achieve a better structure during animation,
although further work (Section 5) is required to refine our model. We also
split our approach by the proposal of two methods for absolute and relative
motion transfer (Section 3.2), which covers both needs (when the source isn’t
aligned well with the driving and needs to be matched to the current driving
explicitly, and when it is aligned and it is wanted and more natural to only
add the relative difference between the current driving and the driving during
the first frame).

##  2 Related Work

Motion transfer has gained a lot of coverage over the last twenty years. Early
approaches based on manipulating existing video footage to generate new
content. These included searching for frames in which the body position
corresponds to a desired motion and using them to generate a new content
(Bregler et al., 1997). Our approach is equally designed for videos, but
rather than manipulating existing images, we learn to synthesize new movements
that were never seen before with the new identities.

A number of techniques are based on calibrated multi camera systems to scan a
target player and use an adapted 3D model of the target to control their
motion in a new frame (Cheung et al., 2004). Our solution instead examines the
transition of movement between 2D video subjects and refrains from using data
calibration, 3D space information or any other domain specific prior.

Latest approaches concentrate on the disentanglement of appearance and
activity and synthesizing of new motion videos (Tulyakov et al., 2018).
Similarly, we apply our representation of motion to different target subjects
to generate new motions. However, In contrast to these works, we did not use
GAN but an encoder-decoder approach.

Contrary to image animation approaches that were common up until recently,
keypoint-based methods are now thought to have the ability to achieve high
performance in the field of video reanimation. Some notable works in this area
are (Siarohin et al., 2020), (Siarohin et al., 2019), (Kim et al., 2019),
(Balakrishnan et al., 2018), (Ma et al., 2017) (Chan et al., 2019).

Our work does not depend on a strong motion prior directly, but rather on a
structure mask derived from a keypoint detector of a motion-based model, such
as (Siarohin et al., 2020). The idea of using drawn keypoints as a geometry
representation (structural mask) was already used in image-to-image
translation works such as TransGaGa (Wu et al., 2019), in addition to some of
the video reanimation works mentioned earlier.

The concept of using a structural mask in the context of image animation is
demonstrated in (Shalev & Wolf, 2020). However, the current work differs by
basing the mask off a motion related keypoint module. By doing so, we create a
bottleneck for the network which is dependent on the keypoint bottleneck used
when training the keypoint module, in order to achieve generalization. In
addition, it simplifies the network, makes it modular to the mask, and saves
us the hassle of perturbing the input hoping to achieve an identity-less mask.

We purpose an heatmap mask (Section 3.1) for absolute animation, which differs
from the drawn keypoint masks mentioned in previous works, in addition to a
classical keypoint mask (Section 3.2) for relative animation w.r.t. difference
between the current and first frames in the driving video.

##  3 Methodology

The network can be divided into two parts: obtaining the mask, and generating
the synthesized frame. The generator architecture is constant amongst all of
our variations, and can be described as low resolution generation from the
source image, source mask and driving mask; Followed by up-scaling of the low
scale synthesized prediction by passing it with the source frame to a high
resolution generator. We created two different versions for the mask
generator: the first, heatmap based mask, which is limited to absolute motion
transfer; the second, keypoint based mask, which enables an optional relative
motion transfer. The performance drop for our second version was expected
because its mask contained less structural information. The first version is
referred as a ”keypoint heatmap mask” while the second is referred as a
”circles mask” or ”keypoints after softmax” mask.

###  3.1 First mask version for absolute motion transfer (with warping)

Our main mask for the project is obtained from carefully observing the
keypoint module from (Siarohin et al., 2020). U-Net based keypoint modules of
this form, work by extracting features, which pass through a conv layer to
form a heatmap image $K$ channels, where $K$ is the number of keypoints. Then,
a softmax is performed over the channels, and keypoints are extracted from the
mean location of each heatmap channel. By carefully debugging the code, and
the expectation for a segmentation map out of U-Net, we obtain Figure 1.

Figure 1:  $K$ channels of the keypoint detector network used in (Siarohin et
al., 2020), before the softmax activation. Our main motion prior in this
project.

Summing over the channels, we get Figure 2.

Figure 2:  The sum of the $K$ channels which is fed as a structural mask into
the generator.

which is our output mask, aka the heatmap, pre softmax mask.

###  3.2 Second mask version for relative motion transfer

We purposes an additional ”circles” only mask which can be used in the context
of relative motion transfer during animation, as in (Siarohin et al., 2020),
which isn’t possible with the previous heatmap mask. The mask captures the
image’s geometry representation (Wu et al., 2019), and by requiring it to be
represented as keypoints with a center, we can use the relative coordinates
for the animation. This is done by replacing the driving keypoints with the
source keypoints moved according to the driving displacement from the first
frame, during animation. This module, though, did not do as well as our
heatmap mask module in the video reconstruction task (Table 2), but did
generalize and managed to preserve the background during animation, due to to
the small mask (Table 3).

While relative motion transition is not always desired, this work shows that a
keypoint-only-prior-based module is feasible for the task. Since the only
information contained in the pair of masks is the keypoint displacement, our
deep network can only attempt to approximate a zero order approximation, we
can anticipate results that are more close to (Siarohin et al., 2019).

By taking the softmax over the heatmap, we get Figure 3.

Figure 3:  $K$ channels of the keypoint detector network used in (Siarohin et
al., 2020), after the softmax activation and Gaussian fit.

Summing over the channels, we get Figure 4.

Figure 4:  The sum of the $K$ channels which is fed as a structural mask into
the generator.

which is our output mask, aka the keypoints after softmax mask.

###  3.3 Architecture

Figure 5: Architecture of the model. The keypoint mask can be either a
keypoint heatmap such as in Figure 2, or drawn keypoint circles as in Figure
4.

Our architecture follows (Siarohin et al., 2020) without the dense motion
module, after changing its keypoint generation module to return our mask.
After the mask is obtained, we follow the encoder decoder approach as (Shalev
& Wolf, 2020), which had success in similar tasks (Newell et al., 2016).

Namely, the encoder of the low resolution generator consists of
$\textit{conv}_{7\times 7}$, batch_norm, relu, followed by six residual blocks
of batch_norm, relu, $\textit{conv}_{3\times 3}$ ,batch_norm, relu,
$\textit{conv}_{3\times 3}$, (and a sum with the source). The residual blocks
help to maintain the identity of the source image (He et al., 2015). The
decoder consists of two blocks, each is a sequence of
$\textit{up\\_sample}_{2\times 2}$, batch_norm, relu. The decoder is followed
by a $\textit{conv}_{7\times 7}$ and a sigmoid activation. For the high
resolution generator, use an encoder (decoder) with five encoding (decoding)
blocks, where each block is a sequence of $\textit{conv}_{3\times 3}$,
batch_norm, relu $\textit{avg\\_pool}_{2\times 2}$, and each decoding block is
a sequence of $\textit{up\\_sample}_{2\times 2}$, $\textit{conv}_{3\times 3}$,
batch_norm, relu. We add skip connections from each of the encoding layers to
its corresponding encoding layer, to form a U-Net architecture (Ronneberger et
al., 2015).

###  3.4 Losses

We use the same perceptual loss as in (Siarohin et al., 2020) which is based
on the implementation of (Wang et al., 2018). With the input driving frame $D$
and the corresponding reconstructed frame $\hat{D}$, the reconstruction loss
is written as: $L_{rec}(\hat{D},D)=\sum_{i=1}^{I}|N_{i}(\hat{D})-N_{i}(D)|$,
where $N_{i}(\cdot)$ is the $i^{th}$ channel feature extracted from a specific
VGG-19 layer (Simonyan & Zisserman, 2015) and $I$ is the number of feature
channels in this layer. Additionally we use this loss on a number of
resolutions, forming a pyramid obtained by down-sampling $\hat{D}$ and $D$,
similarly to MS-SSIM (Wang et al., 2003), (Tang et al., 2019). The resolutions
are $256\times 256$, $128\times 128$, $64\times 64$ and $32\times 32$.

##  4 Experiments

###  4.1 Datasets

The Tai-chi-HD dataset, which includes brief videos of people doing Tai-chi
exercises, was used for training and evaluation. Following (Siarohin et al.,
2020), 3,141 Tai-chi videos were downloaded from YouTube. The videos were
cropped and resized to a resolution of $256^{2}$, while the aspect ratio was
preserved. There are 3,016 training videos and 125 evaluation videos.

###  4.2 Comparison with Previous Works

In order to compare our work to previous works (Table 2) we used metrics
previously used in similar papers. Average Key-points Distance (Cao et al.,
2017) (AKD) measures the average key-points distance between the generated
video and the source video. Average Euclidean Distance (Zheng et al., 2019)
(AED) measures the average euclidean distance between the representations of
the ground-truth and generated videos in some embedding space. In addition, we
added the L1 distance as well. Our AED and AKD metrics were calculated using
the following repository: https://github.com/AliaksandrSiarohin/pose-
evaluation
Note that these metrics aren’t optimal as one can easily improve
reconstruction by increasing the bottleneck, and we can see our artifacts in
animation results (Table 3). However, our approach did follow the structure of
driving video well and better than the others, and to improve the identity and
background artifacts, we suggest some fixes in Section 5. Due to the smaller
bottleneck of the second (softmax) mask, the pose worsened, but the
generalization for the background improved (which also has to do with the low
but non zero grayscale values given to the background in the heatmap mask
representation, which can be solved with thresholding - see Section 5).

Table 2: Accuracy Metrics
Method | AKD | AED | L1
---|---|---|---
X2Face | 17.654 | 0.272 | 0.080
Monkey-Net | 10.798 | 0.228 | 0.077
FOMM | 6.872 | 0.167 | 0.063
Perturbed Mask | 4.239 | 0.147 | 0.047
Ours (circles mask) | 14.760 | 0.245 | 0.077
Ours | 5.551 | 0.141 | 0.045
Improvement (FOMM) | 19.2% | 15.5% | 28.5%

####  4.2.1 Qualitative comparison

When comparing our work visually to (Siarohin et al., 2020), we can argue that
we obtained a better pose which is almost the same with the original. We can
observe a closer synthesized leg in the second frame (to the original
driving), and a better pose (specifically the hands) on the third and forth
frames. However, the background generated is damaged, due to the lack of
thresholding in our mask which means we will always have noise to the
background generation. See Section 5 for future suggestions. We can also see
that the softmax (circular keypoint mask) version worked fine, preserved the
background, but with a worse pose, due to less information in this type of
mask.

Table 3: Images comparison
Source image |  Driving |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
FOMM |  |  |  |  |
Ours (circles) |  |  |  |  |
Ours (mask) |  |  |  |  |

##  5 Future work

We would like to test our module on more datasets, and compare them to the
state of the art. In addition, summing the heatmap channels might not be
optimal, and there is certainly some space to try something deeper with the
features extracted in the keypoint detector as an input, or feed all of the
channels separately into the generator. We want to experiment with mask
thresholds due to the distortions in the animation background, similarly to
(Shalev & Wolf, 2020). We may also increase the number of keypoints, but that
would probably be more beneficent to the second type of mask, and would
increase the required GPU memory proportionally. We also suggest (in the
second, circles only mask) coloring matching keypoints with the same color to
help the module to learn a motion flow.

##  6 Conclusions

We constructed a novel method for image animation by moving the need for a
strong motion prior (optical flow) to the assumption of a pre-trained keypoint
detector/keypoint heatmaps prior to activation, which might be based on a
motion prior. By doing so, we encapsulated motion to a motion mask, which is
bottlenecked by the prior training which has the keypoint bottleneck. The
motion masks are then fed into a generator, which combines the appearance of
the source image and the mask which represents the structure, decoupled from
any appearance naturally by the assumption that during the training of the
keypoint detector, the heatmap mask went into a keypoint bottleneck. After
evaluation, we can conclude that our method is feasible and improves the pose
although with some artifacts.

## Software Data and more result videos

Detailed in our repository:
https://github.com/or-toledano/animation-with-keypoint-mask

## References

  * Balakrishnan et al. (2018) Balakrishnan, G., Zhao, A., Dalca, A. V., Durand, F., and Guttag, J.  Synthesizing images of humans in unseen poses.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 8340–8348, 2018.
  * Bregler et al. (1997) Bregler, C., Covell, M., and Slaney, M.  Video rewrite: Driving visual speech with audio.  In _Proceedings of the 24th annual conference on Computer graphics and interactive techniques_ , pp. 353–360, 1997.
  * Cao et al. (2017) Cao, Z., Simon, T., Wei, S.-E., and Sheikh, Y.  Realtime multi-person 2d pose estimation using part affinity fields.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Chan et al. (2019) Chan, C., Ginosar, S., Zhou, T., and Efros, A. A.  Everybody dance now, 2019.
  * Cheung et al. (2004) Cheung, G. K., Baker, S., Hodgins, J., and Kanade, T.  Markerless human motion transfer.  In _Proceedings. 2nd International Symposium on 3D Data Processing, Visualization and Transmission, 2004. 3DPVT 2004._ , pp. 373–378. IEEE, 2004.
  * He et al. (2015) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition, 2015.
  * Kim et al. (2019) Kim, Y., Nam, S., Cho, I., and Kim, S. J.  Unsupervised keypoint learning for guiding class-conditional video prediction.  _arXiv preprint arXiv:1910.02027_ , 2019.
  * Ma et al. (2017) Ma, L., Jia, X., Sun, Q., Schiele, B., Tuytelaars, T., and Van Gool, L.  Pose guided person image generation.  _arXiv preprint arXiv:1705.09368_ , 2017.
  * Newell et al. (2016) Newell, A., Yang, K., and Deng, J.  Stacked hourglass networks for human pose estimation.  In _European conference on computer vision_ , pp. 483–499. Springer, 2016.
  * Ronneberger et al. (2015) Ronneberger, O., Fischer, P., and Brox, T.  U-net: Convolutional networks for biomedical image segmentation, 2015\.
  * Shalev & Wolf (2020) Shalev, Y. and Wolf, L.  Image animation with perturbed masks, 2020.
  * Siarohin et al. (2019) Siarohin, A., Lathuilière, S., Tulyakov, S., Ricci, E., and Sebe, N.  Animating arbitrary objects via deep motion transfer, 2019.
  * Siarohin et al. (2020) Siarohin, A., Lathuilière, S., Tulyakov, S., Ricci, E., and Sebe, N.  First order motion model for image animation, 2020.
  * Simonyan & Zisserman (2015) Simonyan, K. and Zisserman, A.  Very deep convolutional networks for large-scale image recognition, 2015\.
  * Tang et al. (2019) Tang, H., Xu, D., Wang, W., Yan, Y., and Sebe, N.  Dual generator generative adversarial networks for multi-domain image-to-image translation, 2019.
  * Tulyakov et al. (2018) Tulyakov, S., Liu, M.-Y., Yang, X., and Kautz, J.  Mocogan: Decomposing motion and content for video generation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 1526–1535, 2018.
  * Villegas et al. (2017) Villegas, R., Yang, J., Zou, Y., Sohn, S., Lin, X., and Lee, H.  Learning to generate long-term future via hierarchical prediction.  In _international conference on machine learning_ , pp. 3560–3569. PMLR, 2017.
  * Wang et al. (2018) Wang, T.-C., Liu, M.-Y., Zhu, J.-Y., Liu, G., Tao, A., Kautz, J., and Catanzaro, B.  Video-to-video synthesis, 2018.
  * Wang et al. (2003) Wang, Z., Simoncelli, E. P., and Bovik, A. C.  Multiscale structural similarity for image quality assessment.  In _The Thrity-Seventh Asilomar Conference on Signals, Systems Computers, 2003_ , volume 2, pp. 1398–1402 Vol.2, 2003.  doi: 10.1109/ACSSC.2003.1292216.
  * Wu et al. (2019) Wu, W., Cao, K., Li, C., Qian, C., and Loy, C. C.  Transgaga: Geometry-aware unsupervised image-to-image translation, 2019\.
  * Zheng et al. (2019) Zheng, Z., Yang, X., Yu, Z., Zheng, L., Yang, Y., and Kautz, J.  Joint discriminative and generative learning for person re-identification.  _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.


# Building Stable Off-chain Payment Networks

MohammadAmin Fazli, Seyed Moeen Nehzati, MohammadAmin Salarkia  Sharif
University of Technology, Tehran, Iran.

###### Abstract

Payment channel is a protocol which allows cryptocurrency users to route
multiple transactions through network without committing them to the main
blockchain network (mainnet). This ability makes them the most prominent
solution to blockchains’ scalability problem. Each modification of payment
channels requires a transaction on the mainnet and therefore, big transaction
fees. In this paper, we assume that a set of payment transactions are given
(batch or online) and we study the problem of scheduling modificiations on
payment channels to route all of the transactions with minimum modification
cost.

We investigate two cost models for aforementioned problem: the step cost
function in which every channel modification has a constant cost and the
linear cost function in which modification costs are proportional to the
amount of change. For the step cost function model, we prove impossibility
results for both batch and online case. Moreover, some heuristic methods for
the batch case are presented and compared. For the linear cost we propose a
polynomial time algorithm using linear programming for the batch case.

###### keywords:

Payment Channels , Off-chain Payment Networks , Network Modification ,
Scheduling

††journal: Future Generation Computer Systems

##  1 Introduction

Recently, blockchain-based decentralized cryptocurrencies like Bitcoin,
Ethereum, and Zcash have got much popularity and attention. In these
decentralized cryptocurrencies, transactions don’t need to be managed by third
parties [1], but the problem with these currencies is their performance and
scalability. Since their transaction throughput is bounded by maximum block
size in the chain, they are not scalable for the high number of transactions
[2]. For example, for bitcoin, the best known bound for average transaction
throughput is seven transactions per second [3]. This value is an order of
magnitude lesser than the transaction rate in everyday payments, such as Visa
cards. Therefore, it will not be possible to use bitcoin in people’s daily
life. Moreover, this low transaction rate has resulted in competition between
users to finalize their transactions faster, which resulted in higher
transaction fees.

Many solutions have been provided to solve the scalability problem in
blockchain networks. Kim et al. [4] and Zhou et al. [1] provide surveys on
these solutions. Some of these solutions are on-chain methods, which try to
solve the problem within the main blockchain, for example, by modifying some
elements in the chain to increase the maximum block size. Other solutions are
non-on-chain methods such as off-chain, side-chain, cross-chain, etc. These
solutions use another network or chain to improve scalability outside the
blockchain. One of these non-on-chain solutions, which was very promising in
recent years, is payment channels. With this solution, some transactions will
transfer to a temporary off-chain network to reduce the number of transactions
on the main chain. Lightning network for Bitcoin and Raiden network for
Ethereum are examples of such payment channel networks.

A payment channel is a cryptocurrency transaction on blockchain that deposits
some money on the blockchain for exchange between two specific users [5]. For
instance, Alice can deposit 1 BTC into a multi-signature transaction (meaning
that the signatures of both parties is needed for withdrawing) for sending to
Bob. Setting up this transaction follows the common mechanism of transactions
on blockchain and needs to be committed on main net. From now on, Alice can
send money up to 1 BTC to Bob as many times as she wants by sending signed
transctions from the deposit account. Bob can close payment channel by signing
the last transaction and broadcasting it into the main net. This whole process
just needs two commits on blockchain. The first one for setting up the payment
channel and the second one for closing it.

However, payment channels can only handle transactions between two users. So,
it won’t solve the scalability problem if everyone has to set up a payment
channel to another user to provide fast payments to him. For this purpose,
offchain networks of payment channels are proposed [6]. With these networks,
This is where the Lightning Network comes up. With this network, every two
users can make transactions if there is a path of payment channels between
them.

In this paper, we target the problem of building stable payment networks. In
this problem, every channel has a specific deposit. That means it can route
transactions with values less than its deposit. We call this deposit channel
capacity, and it decreases with routing every transaction. Also, we assume
that every node in this network has a finite capital which means the sum of
channels’ capacities sourcing from that node must be less than its capital. As
a result, channels can’t have infinite capacity. Every change in channel
capacities needs a transaction commit on the mainnet, and it is costly. In the
target problem of this paper, a network of payment channels and a set of
transactions on the network are given. Then, we want to schedule capacity
changes on payment channels to minimize the cost of commitments on the
mainnet.

To evaluate different scheduling algorithms, we investigate two cost models.
The first one is the linear cost model. In this case, the change cost of a
channel’s capacity is linearly dependent on the value of the change. The
second one is the step cost model, which means the cost of capacity change is
constant. Moreover, we check out two cases for transactions: the batch case
and the online case. In the batch case, we assume that all the input
transactions are given at time zero. In the online case, we suppose that at
each time, we only know the next transaction. This paper proposes a
polynomial-time algorithm to find the optimum solution for the linear cost
model and the batch input case. For the step cost model and the batch input
case, we prove the NP-completeness of the solution. For the step cost model
and the online input case, we show no c-competitive algorithm such that
$c\leq\delta$, where $\delta$ is the maximum degree of nodes in our network.
Finally, we propose some heuristic algorithms for the step cost model and the
batch input case and compare their performance in a simulation.

This section will explain payment channels and the payment network concepts in
more detail and then survey the literature. In the next section, we will
propose the formal statement of our problem. After that, we will state the
aforementioned theoretical results in finding optimum solutions. Next, we will
present our report on heuristic algorithms and their performance. We will
conclude this paper by reviewing the achievements made in this paper and the
possible future works.

###  1.1 Payment channels

The Payment channel can be mono-directional or bi-directional. First, let’s
see the mono-directional form. Imagine the case that Alice wants to open a
payment channel with Bob with the capacity of 1 BTC. She has to deposit this
money in a multi-signature address. All the transactions on this address need
the signature of both Alice and Bob to be performed. If Alice wants to pay 0.1
BTC to Bob, she creates a transaction that gives 0.9 BTC from that specific
address to Alice and gives 0.1 BTC to Bob. She signs this transaction and
gives it to Bob. Sometime later, when Alice wants to pay another 0.2 BTC to
Bob, she writes a transaction that gives 0.7 BTC to herself and gives 0.3 BTC
to Bob. Again, she signs this transaction and gives it to Bob. Whenever Bob
wants to withdraw his money, he can sign the transaction (complete the needed
signatures), and then, this transaction will broadcast on the main blockchain
and close the channel. Note that he can’t commit any other transaction after
Bob has committed the last transaction. In Figure 1, you can see this
scenario.

The problem here is that if Alice wants her 0.7 BTC, she depends on Bob’s
action. Thus, there must be a deadline for Bob to withdraw the money;
otherwise, all the money will turn back to Alice. A transaction that gives all
the money to Alice after some time will do this aim. Before Alice funds the
address, Bob will write and sign this transaction and gives it to Alice. Then,
Alice will fund the channel.

However, mono-directional payment channels do not look promising because they
only allow one-way payments. So there is a need for bi-directional channels.
In a bi-directional channel, both Alice and Bob create guarantee transactions
and give them to each other. After that, they both fund the channel, for
example, by $V_{a}$ and $V_{b}$ values. Now, if Alice wants to pay Bob
$v_{1}$, she can create a transaction that gives herself $V_{a}-v_{1}$ and
gives Bob $V_{b}+v_{1}$, sign it and give it to Bob. Then, if Bob wants to
give Alice $v_{2}$, he can write a transaction which gives Alice
$V_{a}-v_{1}+v_{2}$ and gives himself $V_{b}+v_{1}-v_{2}$ and so on.

Since these channels (both mono-directional and bi-directional) only need two
transactions on the main blockchain (one for opening and one for closing),
they look very promising for solving the scalability problem of blockchain-
based payments.

Figure 1: The Payment Channel Mechanism

###  1.2 Payment Networks

Although payment channels need just two transactions on the blockchain, if
everyone has to create a payment channel with another one, it doesn’t solve
the scalability problem. Creating these many channels and closing them needs a
lot of time and locks many coins only for future payments. Here the solution
of payment networks comes up. Payment networks are graphs in which users are
the nodes, and payment channels between them are edges. If some user Alice
wants to pay some money to user Carol and there is a path between them in the
graph, they can do their transaction only if the value of the transaction is
less than the channels’ capacities in this path (See Figure 2).

Figure 2: A Payment Network; Alice wants to pay 0.2 bitcoin to Carol. This
payment is impossible through the Alice-Will-Scarlet-Carol path because the
channel between Scarlet and Carol has not enough capacity. However the Alice-
Bob-Carlo path makes it possible. First, Alice pays 0.2 BTC to Bob through her
channel to him. Then Bob pays this money to Carol through his channel to him.

One of the main problems with payment networks is how to incentivize
intermediate nodes to route other nodes’ transactions. This problem can be
solved by giving a routing fee to all users in the path. With routing fees,
the users in the network tend to create more channels with higher capacities
to achieve more fees.

Another problem with this network is that intermediate users can steal the
routing coins. Hash-locked contracts can prevent this. Hash locked contracts
are transactions that can only be finalized by providing a specific proof. For
instance, assume Alice wants to pay Carol, and there is a path of length 2
(Alice-Bob-Carol) between them. First, Carol has to generate a private key and
a public key and give the public key to Alice. Then, Alice makes a transaction
with Bob, which needs the private key to be done. Also, Bob makes a similar
transaction with Carol. Now Carol provides the private key and does the
transaction between herself and Bob. After that, Bob will know the private
key, and he can also give the private key and do the transaction between
herself and Alice.

The Lightning Network is the payment channel network for bitcoin. The Raiden
Network is the Ethereum version. It is very similar to the Lightning Network
except that it supports different types of transactions while the lightning
network supports only bitcoin transactions.

###  1.3 Related Work

Kim et al. [4], and Zhou et al. [1] provide surveys on solutions to the
scalability problem on blockchain-based payments. As one of the most promising
solutions, researchers have proposed various payment channel protocols
(networks) which present how to create a payment channel [7, 8, 6, 9].
However, the current work is independent of channel protocols and applies to
all such solutions. The Lightning Network, which is the most famous payment
channel, was first introduced in [6].

Most of the optimization and algorithmic research works done by a team resided
in the ETH university. Avarikioti et al. [10] study the optimal structure of
the channels’ network and the allocation of charges to them to maximize the
profit of the payment service provider (PSP). In their other work [11],
proposes three optimization problems in the context of payment network design.
All of those problems are variants of the General Network Design problem. In
this problem, a set of transactions, a capital, and a profit are given. The
problem asks to design a network and a strategy to route the transaction
through the network. The first target problem gets a set of transactions and
asks whether it is possible to route all of them from a single bidirectional
channel between two users. The second problem gets a set of transactions and
asks to return a graph with the minimum possible capital. The third problem
receives a set of transactions, a graph, and a capital and asks whether there
is a capital assignment to the graph’s edges that can route all the
transactions. They present hardness results and approximation algorithms for
the batch case of these three problems. For the online case, they give an
impossibility result for the first problem and a competitive algorithm for the
second problem.

The ETH team has also focused on some other aspects of payment channels. For
example, in [12], they explore the game theory of payment networks. They
assume that the users in the network are selfish players, and they compete to
earn more. Then study the Nash equilibrium of the network creation game, which
are the topologies that emerge from their interactions. For investigating the
topology, they consider betweenness and closeness centrality as the central
concept. At last, they determine the social optima for the network topology.

There are some other works targetting payment channels and the Lightning
Network. Most of these works are unrelated to this paper, but some of them are
surveyed as examples. Sivaraman et al. [5] Claim that shortest-path routing is
not a good idea for routing transactions on payment networks (because of the
limited capacity of channels, some important channels may get exhausted, and
the system will stop working). Then, it provides a new routing solution of
transactions to achieve high throughput. Prihodko et al. [13] provide another
routing algorithm of transactions in the Lightning network called Flare. Seres
et al. [14] analyze the effects of the Lightning network’s topology on its
security and its robustness against failures and attacks. Herrera et al. [15]
mention that the precise balance of the pair of nodes in payment networks has
to be kept secret due to privacy problems. Then, they investigate the problem
of hiding this balance and having working routing algorithms simultaneously
and proposes an attack to reveal the balance of a channel.

##  2 The Problem Statement

Here we will go with the formal definition of our problem. We are given a
payment network $G=(V,E)$, Where V stands for a set of nodes that are
cryptocurrency users (more precisely, addresses) and can have payment
transactions between themselves. $E$ is the set of $G$’s payment channels.
Each $e\in E$, is a directed pair $e=(u,v),u,v\in V$. These channels can be
used for money transfers. The capacity of each channel is defined by a
function $c_{e}:T\rightarrow\mathds{R}^{+}$, where $T$ is the set of times.
Without loss of generality, we can assume that times are positive integers
from 1 to $n$, which means: $T=\\{1,2,...,n\\}$.

######  Definition 1.

For every channel $e\in E$ in graph $G=(V,E)$ the capacity of channel at time
$t$ is represented by $c_{e}(t)$, where $c_{e}:T\rightarrow\mathds{R}^{+}$ is
the capacity function and $T=\\{i|1\leq i\leq n\\}$ and $n$ is the number of
time steps.

Now, suppose that a set of transactions $\Gamma$ is given. Without loss of
generality we can assume that in each time $i\in T$ we have exactly one input
transaction $t_{i}\in\Gamma$. Thus, the number of input transactions is equal
to n. Each transaction is defined like this:
$t_{i}=<s_{i},d_{i},p_{i},v_{i}>$, where $s_{i},d_{i}\in V$ are the source and
the destination of the transactions, $p_{i}$ is a path (an ordered set of
channels) in $G$ between $s_{i}$ and $d_{i}$ and finally, $v_{i}$ is the value
of transaction $t_{i}$. In practical settings most of the times this path is
the shortest path between $s_{i}$ and $d_{i}$ in $G$ (but sometimes it is not
a good idea to use the shortest path, See [5]). The transaction $t_{i}$ can be
executed in $G$ if:

$c_{e}(i)\geq v_{i}\;;\;\forall e\in p_{i}$

.

In this paper, we want to schedule the modifications of $G$’s channels’
capacity in a way that can route all the input transactions with minimum cost.
Each channel’s capacity is constrained by its connected nodes’ capital. We
define the capital of each node $u\in V$ as a function
$C_{u}:T\rightarrow\mathds{R}^{+}$, where $C_{u}(t)$ represents $u$’s capital
at time $t$.

######  Definition 2.

For every node $u\in V$ in graph $G=(V,E)$, the capital of node in time step
$t$ is represented by $C_{u}(t)$, where $C_{u}:T\rightarrow\mathds{R}^{+}$ is
the capital function and $T=\\{i|1\leq i\leq n\\}$ and $n$ is the number of
time steps.

We assume that no node can change its capital while processing payment
transactions. Therefore, $C_{u}$ can only be increased or decreased by
transactions. $C_{u}$ decreases when $u$ is the source of a transaction, i.e.,
$u$ wants to pay some amount of money to someone. In the same way, $C_{u}$
increases when $u$ is the destination of a transaction, i.e., someone wants to
pay $u$ some money.

######  Lemma 1.

With set of transactions $\Gamma=\\{<s_{i},d_{i},p_{i},v_{i}>|1\leq i\leq
n\\}$, the capital of node $u$ at time $t$ can be represented in this way:

$C_{u}(t)=C_{u}(0)-\sum_{j\leq t,s_{j}=u}v_{j}+\sum_{j\leq t,d_{j}=u}v_{j}$

Our desired scheduling plan consists of a scheme for each channel. The scheme
for each channel $e$ is defined as a sequence of channel modifications
$f_{e}=\\{(\tau_{i}^{e},\lambda_{i}^{e})\\}_{i=0}^{k_{e}}$ , where $k_{e}$ is
the number of modifications by our plan on channel $e$, $\tau_{i}^{e}\in T$ is
the scheduled time for $i$th modification (with $\tau_{0}^{e}=0$) and
$\lambda_{i}^{e}$ is the new amount which $e$ gets after this modification.
Note that its initial value $\lambda_{0}^{e}$ equals to the initial capcity of
channel $c_{e}(0)$.

######  Definition 3.

A channels modification scheme
$f_{e}=\\{(\tau_{i}^{e},\lambda_{i}^{e})\\}_{i=0}^{k_{e}}$ for edge $e$ is
defined in a way that $\lambda_{i}^{e}$ is the value of capacity of channel
$e$ between times $\tau_{i}^{e}$ and $\tau_{i+1}^{e}$. We can represent this
definition by this formula:

$\tau_{i}^{e}\leq t<\tau_{i+1}^{e}\rightarrow
c_{e}(t)=\lambda_{i}^{e}-\sum_{\tau_{j}^{e}\leq j<\tau_{j+1}^{e},e\in
p_{j}}v_{j}+\sum_{\tau_{j}^{e}\leq j<\tau_{j+1}^{e},e\in\bar{p_{j}}}v_{j},$

where $\bar{p_{j}}$ is the path $p_{j}$ in reverse direction.

This paper defines the problem of designing a plan for scheduling the input
payment transactions on a given payment network as an optimization problem
with a set of constraints and an objective function. The constraints are
defined based on the fact that each node $u$ must provide the capacity of its
outgoing channels, and the sum of its outgoing channels capacities should be
less than its capital. more formally: $\sum_{e\in O(u)}c_{e}(t)\leq C_{u}(t)$,
where $O(u)$ is the set of edges sourced by $u$, i.e. $O(u)=\\{(u,v)|(u,v)\in
E\\}$.

For the optimization objective, we consider two different functions, the
linear cost function, and the step cost function. The linear cost function
measures the cost of each channel modification by its amount of change in its
capital.

######  Definition 4.

For a given graph $G$ and a set of transactions $\Gamma$ and a channels
modifications scheme
$f_{e}=\\{(\tau_{i}^{e},\lambda_{i}^{e})\\}_{i=0}^{k_{e}}$, we can define the
linear cost function of channels modifications as follows:

$LC(G,\Gamma)=\sum_{e\in
E(G)}\sum_{i=1}^{k_{e}}|\lambda_{i}^{e}-c_{e}(\tau_{i}^{e})|.$

The step cost function computes the cost as the number of changes to the
capacities.

######  Definition 5.

For given graph $G$ and set of transactions $\Gamma$ and channels
modifications scheme
$f_{e}=\\{(\tau_{i}^{e},\lambda_{i}^{e})\\}_{i=0}^{k_{e}}$, we can define the
step cost function of the channels modifications as follows:

$SC(G,\Gamma)=\sum_{e\in E(G)}k_{e}$

Finally, with these definitions, we can propose the formal statement of our
problem.

######  Problem 1.

Scheduling capacity changes on payment networks with linear cost
Given a graph $G(V,E)$ and a set of transactions
$\Gamma=\\{<s_{i},d_{i},p_{i},v_{i}>|1\leq i\leq n\\}$, we want to propose
$f_{e}=\\{(\tau_{i}^{e},\lambda_{i}^{e})\\}_{i=0}^{k_{e}}$ for every $e\in E$
in a way that minimizes $LC(G,\Gamma)$ and meets these constraints:

$c_{e}(i)\geq v_{i};\forall 1\leq i\leq n,\forall e\in p_{i},$ $\sum_{e\in
O(u)}c_{e}(t)\leq C_{u}(t),$

where $c_{e}$ is capacity function of edge $e$, $C_{u}$ is capital function of
node $u$ and $O(u)$ is set of outgoing channels from $u$.

######  Problem 2.

Scheduling capacity changes on payment network with step cost
Given a graph $G(V,E)$ and a set of transactions
$\Gamma=\\{<s_{i},d_{i},p_{i},v_{i}>|1\leq i\leq n\\}$, we want to propose
$f_{e}=\\{(\tau_{i}^{e},\lambda_{i}^{e})\\}_{i=0}^{k_{e}}$ for every $e\in E$
in a way that minimizes $SC(G,\Gamma)$ and meets these constraints:

$c_{e}(i)\geq v_{i};\forall 1\leq i\leq n,\forall e\in p_{i},$ $\sum_{e\in
O(u)}c_{e}(t)\leq C_{u}(t),$

where $c_{e}$ is capacity function of edge $e$, $C_{u}$ is capital function of
node $u$ and $O(u)$ is set of outgoing channels from $u$.

We face these two problems with two types for $\Gamma$, batch and online. In
the batch form, all $t_{i}\in\Gamma$ are given at first, But, in the online
form in every time step $i$ we just have $t_{j}\in\Gamma;1\leq j\leq i$ and we
don’t know the future transactions.

##  3 Theoretical Results

In this section, we are going to investigate the optimal solution to the
problems stated in Section 2. For the problem 1, which used the linear cost
function, we propose a linear programming algorithm for scheduling
modifications in polynomial time. For the problem 2, we investigate both batch
and online cases. For the batch input case, we reduce a well-known fault
caching problem to our problem. Moreover, as it is proved that fault caching
is an NP-Complete algorithm, we can conclude that the problem 2 is NP-Complete
either. For the online input case, we define the competitiveness, and then we
prove that there are no c-competitive algorithms for our problem where
$c\leq\Delta$ and $\Delta$ equals the maximum degree of nodes in the graph.
For that purpose, for each algorithm, we devise a graph in which the cost of
the algorithm will be greater than the optimal cost multiplied by $\Delta$.

###  3.1 Batch Input - Linear Cost

The following theorem shows that this case of the problem is solvable in
polynomial time by a linear programming.

######  Theorem 1.

The problem 1 with batch input can be solved in polynomial time.

###### Proof.

The following LP can model the problem. The first condition ensures that the
scheduling plan is executable at each time. The second condition guarantees
changes will not set the capacity of edges to a negative value. The third
constraint ensures that the payment network can route all the incoming
transactions. Th final condition guarantees the validity of nodes’ capitals.

$\begin{array}[]{llll@{}llll}\text{minimize}&\sum\limits_{e\in
E}\sum\limits_{i=1}^{k_{e}}|\lambda_{i}^{e}-c_{e}(\tau_{i}^{e})|&\\\ \\\
\text{subject
to}&c_{e}(i)=\lambda_{i}^{e}-\sum\limits_{\begin{subarray}{c}\tau_{i}^{e}\leq
j<\tau_{i+1}^{e}\\\ e\in
p_{j}\end{subarray}}v_{j}+\sum\limits_{\begin{subarray}{c}\tau_{i}^{e}\leq
j<\tau_{i+1}^{e}\\\ e\in\bar{p}_{j}\end{subarray}}v_{j}&\forall i\in T,e\in
E\\\ \\\ &\lambda_{i}^{e}\geq 0,&\forall i\in T,e\in E\\\ \\\ &c_{e}(t)\geq
v_{i}&\forall i\in T,e\in p_{i}\\\ \\\ &\sum\limits_{e\in O(u)}c_{e}(t)\leq
C_{u}(t)&\forall i\in T,v\in V\\\ \\\ \end{array}$

As all the constraints are met and the algorithm minimizes the cost function,
it finds the optimal solution. This linear programming problem can be solved
in polynomial time and gives the optimal solution.

∎

###  3.2 Batch Input - Step Cost

In this subsection, we show that the problem of scheduling capacity changes on
payment networks with the step cost function is NP-complete. To this aim, we
use a reduction from another NP-complete problem called the Fault Caching
problem ([16]).

######  Problem 3.

Fault Caching problem
Assume that we are given set of pages $\\{pg_{0},pg_{1},...,pg_{k-1}\\}$ with
sizes $\\{size(pg_{i})\\}_{0}^{k}$. Assume that we have a cache of size $W$.
In each time we can store a set of pages in the cache if the sum of their
sizes is less than $W$. A series of page requests will come in an order
$\sigma_{0},\sigma_{1},...,\sigma_{n-1}$ where
$\sigma_{i}\in\\{pg_{0},pg_{1},...,pg_{k-1}\\}$ and $\sigma_{i}$ is requested
at time $i$. If at time $i,\sigma_{i}$ is not available in cache we say that a
fault happens. The Fault Caching problem asks for a replacement policy that
makes responding to $\sigma_{i}$s with at most $F$ faults.

######  Theorem 2.

The problem of scheduling capacity changes on payment networks with the step
cost function is NP-complete.

###### Proof.

We want to make a reduction from the Fault Caching problem to our target
problem. To this aim, consider the graph $G=(V,E)$ with $V=\\{v_{1},v_{2}\\}$
and $E=\\{e_{1},e_{2},...,e_{k}\\}$ where all $e_{i}$s are from $v_{1}$ to
$v_{2}$ and $C_{v_{1}}(0)=W$. Now we construct transactions $\Gamma$ like
this:

$t_{i}=<v_{1},v_{2},e_{I(\sigma_{i})},size(\sigma_{i})>,$

where $I$ gives index of the requested page.

We show that the answer to the Fault Caching problem is yes if and only if we
can find a modification schedule for $G$ and $\Gamma$ with cost less than or
equal to $F$.

First, we prove the if part. Consider a solution of the Fault Caching problem
like this: $d_{i}$ pages that are dropped in time $i$ and $b_{i}$ set of pages
that are brought to the cache in time $i$. Also set $b_{0}$ set of pages that
are brought to the cache at time $0$. we construct the solution
$f_{e}=\\{\tau_{i}^{e},\lambda_{i}^{e}\\}_{i=0}^{k_{e}}$ in this way:

$\displaystyle f_{e_{i}}=\\{(\tau,0)|\forall\tau,pg_{i}\in
d_{\tau}\\}\cup\\{(\tau,size(pg_{i}))|\forall\tau,pg_{i}\in b_{\tau}\\}$
$\displaystyle\sum_{i=0}^{n-1}(|d_{i}|+|b_{i}|)\leq
F\rightarrow\sum_{i=0}^{k-1}|f_{e_{i}}|\leq F$

So the cost of this modification schedule is at most $F$.

Secondly, we prove the only if part. Suppose we have solution $f_{e}$ for the
scheduling problem. For each time step $\tau_{i}^{e}$that e is not same as
$e_{I(\sigma_{i})}$ we change $\tau_{i}^{e}$ to $\tau_{i}^{e}+1$ if
$\tau_{i}^{e}+1\notin f_{e}$ and remove $(\tau_{i}^{e},\lambda_{i}^{e})$ from
$f_{e}$ if $\tau_{i}^{e}+1\in f_{e}$. (we do this sequentially ordered by
$\tau$, starting from 1). The resulting schedule is valid and the sum of sizes
of $f_{e}$s is less than its value for original schedule.

Then, at each time step $\tau_{i}^{e}$, starting from 1, we decrease
$\lambda_{i}^{e}$ to $size(\sigma_{i})$. The resulting schedule still
satisfies the question and has a cost of at most $F$.

Now we construct the solution of Fault Caching problem in this way:

$\displaystyle b_{t}=\\{pg_{i}|\forall i;\exists(t,\lambda)\in
f_{e_{i}},\lambda-c_{e_{i}}(t-1)>0\\}$ $\displaystyle d_{t}=\\{pg_{i}|\forall
i;\exists(t,\lambda)\in f_{e_{i}},\lambda-c_{e_{i}}(t-1)<0\\},$

and the reduction is complete. We know that the Fault Caching is NP-complete
and it’s reduced to scheduling problem above in polynomial time, thus, we can
infer that scheduling problem with Batch input and step cost is NP-complete. ∎

###  3.3 Online Input - Step Cost

In this subsection, we study the problem of scheduling capacity changes on
payment network with the step cost function and online input. With this type
of input, in every time step $i$ we just have $t_{j}\in\Gamma;1\leq j\leq i$
and we don’t have any information about the future transactions. In this
context, we deal with online algorithms and competetive analysis.

In competitive analysis, an online algorithm $A$ is compared to an optimal
offline algorithm. An optimal offline algorithm knows the entire request
sequence in advance and can serve it with minimum cost. Given a request
sequence $\sigma$, let $C_{A}(\sigma)$ denote the cost incurred by $A$ and let
$C_{OPT}(\sigma)$ denote the cost incurred by an optimal offline algorithm
$OPT$. The algorithm $A$ is called $c$-competitive if there exists a constant
$a$ such that:

$C_{A}(\sigma)\leq c.C_{OPT}(\sigma)+a,$

for all request sequences $\sigma$. Here we assume that $A$ is a deterministic
online algorithm. The factor $c$ is also called the competitive ratio of $A$
([17]).

######  Theorem 3.

Given a graph $G=(V,E)$ and a set of online transactions $\Gamma$. There is no
deterministic $c$-competitive online scheduling algorithm $f=\\{f_{e}\\}_{e\in
E}$ such that $c\leq\Delta$ (maximum degree of nodes in $G$) for finding the
minimum cost modification schedule with the step cost function $SC(G,\Gamma)$:

$\displaystyle SC(G,\Gamma)=\sum_{e}|f_{e}|$

###### Proof.

Let $g$ be the optimal batch solution. For each deterministic algorithm $f$ we
devise a network and a series of transactions such that:

$\displaystyle\Delta\times SC_{g}(G,\Gamma)\leq SC_{f}(G,\Gamma)$

Consider a graph $G(V,E),V=\\{v_{1},v_{2}\\}$ and
$E=\\{e_{1},e_{2},...,e_{\Delta}\\}$ where all $e_{i}$s are edges from $v_{1}$
to $v_{2}$. For algorithm $f$ we have:

$\displaystyle\sum_{e\in E}c_{e}^{i}\leq C_{v_{1}}(i);\;\forall i\in
T\rightarrow$ $\displaystyle\exists
j:c^{i}_{e_{j}}\leq\frac{C_{v_{1}}(i)}{\Delta}+\epsilon;\forall i\in
T,\forall\epsilon>0$

We devise $t_{i}$ such that:

$\displaystyle t_{i}=<v_{1},v_{2},e_{j},\frac{C_{v_{1}}(i)}{\Delta}+\epsilon)$

With this input for every $i$ we have $(i,\frac{C_{v_{1}}(i)}{\Delta})$ in
$f_{e_{j}}$. Thus, for every time step we have at least one changes so:

$\displaystyle SC_{f}(G,\Gamma)\geq n,$

but for optimal solution, $g$, when we need an increase to $e_{j}$ at time
step i we decrease $e_{k}$ such that $e_{k}\in p_{i+\Delta}$. Thus, $g$ needs
a change for every $\Delta$ step. So:

$\displaystyle\Delta\times SC_{g}(G,\Gamma)\leq SC_{f}(G,\Gamma)$

∎

##  4 Heuristic Algorithms

In previous sections, we approached the problem of finding the minimum cost
modification schedule for a given payment network and set of transactions in
four different cases: Batch input-linear cost, Batch input-step cost, Online
input-step cost, Online input-linear cost.

For the batch input-step cost case, we proved that finding the optimum
solution is NP-complete. This section will try some heuristic algorithms for
this case, and we will compare their performances to find out the best
heuristic. First of all, we will give a model of the problem of implementing
heuristics for that. Then, we will introduce the heuristic algorithms we want
to try. Finally, We will show empirical results and compare them.

###  4.1 Model

Suppose that we have a graph $G$ with $n$ channels and a set of transactions
$T$, over $G$, with $m$ transactions. Again, according to the definition of
the problem, each channel and node has a capacity. Node capacities cannot
change, but channels’ capacity can change with cost $1$ for each modification.
The sum of capacities of all channels of a specific node can’t be greater than
the capacity of that node. Now, assume that we have found a solution $S$ for
the problem.

The procedure of the algorithm will be in this way: At each step $i$, $S$ will
do some modifications on channels’ capacities, and the cost will increase by
the number of modifications. Then, transaction $t_{i}$ of $T$ will be
executed, and the capacity of channels in the path of $t_{i}$, the capacity of
the source node, and capacity of target node will decrease by the value of
$t_{i}$. If limits of capacities cannot route the transaction, the solution
will get some penalty, and the cost will increase by that, and $t_{i}$ will be
skipped. This procedure will repeat from $i=0$ to $i=m$.

We want to use an array to represent solution $S$ and then try to change that
array with heuristic algorithms to find better solutions. The first and the
most straightforward way to represent $S$ is to use a 2D matrix. The number in
row $i$ and column $j$ of the matrix will be the value of modification on
channel $i$ in step $j$. The cost of the solution will be the number of non-
zero elements plus the penalty for the number of skipped transactions.

However, there are some problems with this way of solution modeling. One
problem is that the number of parameters in the solution matrix array is
$m\times n$, i.e., the number of channels times the number of transactions.
This number of parameters will increase our heuristic algorithms’ time and
complexity and increase randomness in our algorithms.

Another problem is the way we represent the numbers in the matrix. If the
numbers are absolute values of increase or decrease to capacities, those
values may depend on every capacity and transaction’s values. Also, these
values have no bound and can change from minus infinity to plus infinity.
These problems can make the progress of the algorithm hard and slow. However,
if, in some way, we can use normalized coefficients from 0 to 1 instead of
these absolute values, that can make our problem easier.

For finding a better way to represent a solution of an algorithm in an array,
we will use some lemmas. Here we will discuss these lemmas.

######  Lemma 2.

Assume that in step $i$ we have transaction $t_{i}$ that uses path $p_{i}$.
Define $N_{i}$ the set of all nodes in path $p_{i}$. If two nodes $v_{1}$ and
$v_{2}$ are not in $N_{i}$, there is no need to change capacity of edge $e$
between $v_{1}$ and $v_{2}$, in step $i$.

This lemma is quite intuitive because we can push changes to irrelevant edges
to the next steps, and the resulting cost will be less than or equal to the
first solution.

######  Lemma 3.

If a transaction $t_{i}$ in step $i$ has value $v_{i}$ and there is channel
$e$ in path $p_{i}$ of $t_{i}$ and capacity of $e$ is greater than $v_{i}$,
there is no need to change the capacity of $e$ in step $i$.

The intuition behind this lemma is just like before. We can push changes to
edges that have enough capacity for now to the next steps.

Now we can provide another model for our solution $S$. We will have an array
of numbers between $0$ and $1$ to represent this solution. Every step a
transaction needs to pass through a channel, we check that if the channel’s
capacity is enough for that value, we let it go and do not change the channel
capacity. But, if the channel’s capacity is not enough, there can be two
states.

First, the source node’s capacity is enough, but the channel’s capacity is not
enough. We increase the channel’s capacity as much as it can pass the
transaction; then, we increase it by the amount that it can increase
multiplied by a coefficient from the solution array.

Another state is when both the channel’s capacity and the source node’s
capacity are not enough. In this state, we need to decrease the capacity of
other channels connected to the source node so that its capacity will
increase, and then we can act like before. Therefore, we go through all other
channels connected to the source node and multiply them by a coefficient from
the solution array. Whenever the node capacity is enough for the transaction
to pass, we change the channel’s capacity like the former state.

There is a problem with this model, and that is the length of the array. If
the array’s length is too long, then there would be some parameters that are
not useful. If the length of the array is too short, then we lack some
coefficients for our solution. To tackle this problem, we assumed that if we
ran out of coefficients in the solution, we use 0 as the coefficient. Also, we
consider the length of the solution array as a hyper-parameter to our
heuristic model that can be tuned, and different values can be checked to find
the best one.

###  4.2 Algorithms

After providing a model for our algorithm and its solution, we will test some
heuristic algorithms to find the best solution and compare their performance.
Here we’ll explain these algorithms.

  * 1.

Alg1. This algorithm is based on Genetic Algorithms [18]. First, we create
random solution arrays to the number of population. Then, in each generation,
we calculate the fitness function for each solution and find the best ones as
parents. Then we do a crossover between those selected solutions and do some
random mutations on resulting arrays. The resulting arrays after crossover and
mutation plus the parent arrays will form the next population. This process
will repeat until the algorithm converges or the maximum number of generations
exceeds.

  * 2.

Alg2. This algorithm is based on Random Hill Climbing. At each step, we move
our solution to a new random state. That means we increase or decrease some
random elements of our array by a constant step. After each move, we calculate
the fitness function of our array, and if it has improved, we stay; otherwise,
we step back to the previous solution. This process repeats until the maximum
number of steps exceeds.

  * 3.

Alg3. This algorithm is based on Late Acceptance Hill-Climbing [19].
Researches have shown the superiority of this algorithm over other
optimization methods in many application fields. It is similar to the previous
algorithm, but it has a history array. After each step, it checks the
solution’s fitness with the previous step and with fitness in specific steps
before from our history array. For example, if we are in step 52 and the
history array’s length is 30, our algorithm compares the fitness of the next
step with the previous one and the number in the index of 22 in our history
array. If it is better than any of them, it will move to the next step.
Moreover, if new fitness is better than the fitness in our history, it will
replace it in the history array. This process repeats until the maximum number
of steps exceeds.

  * 4.

Alg4. This algorithm is based on the PSO algorithm [18]. It initiates a
population of swarms with a position in search space and a velocity. At each
step, this algorithm updates the velocity of each particle using the PSO well-
known formula depending on its current position, its best-known position, and
the best-known position of the entire swarm. Then, it updates the particle’s
position depending on this new velocity. If this new position’s fitness is
better than this particle’s best-known position or the entire swarm’s best-
known position, updates them. This process repeats until the algorithm
converges or the maximum number of generations exceeds.

  * 5.

Alg5. This algorithm is based on Simulated Annealing [20]. It initiates the
algorithm with a state and a temperature. Each step moves the state (like
movements we had in Alg3 or Alg2) and calculates its fitness. Then calculates
the probability of acceptance of the new state with this formula:
$e^{(old\\_fitness-new\\_fitness)/T}$. Then, it compares acceptance
probability with a random number, and if it is greater than that, it moves to
the new state. After each step, the temperature decreases by being multiplied
by a constant. This process repeats until the temperature goes below some
specific number.

###  4.3 Empirical Results

In this subsection, we present the results of experimenting with the
heuristics mentioned above on real-world data. For data of nodes and channels,
we used [21] API and crawled data from that. This data was massive, So for
making it smaller, we sampled a connected graph from it.

There is no open dataset for transactions over the Lightning network. So we
generated a random transaction dataset by choosing some random paths in our
graph and some random values from the uniform distribution. We used the number
of changes in channel capacities as our objective function. For each
algorithm, some hyper-parameters must be tuned—for example, the length of the
solution array or the coefficient of temperature in simulated annealing. We
ran many simulations and tests on algorithms to find the best hyper-parameters
for each one of them.

The result of growth and convergence of algorithms can be seen in Figure 3.
From this simulation, these results can be concluded:

  * 1.

The best overall efficiency was obtained from Alg3, which is based on the Late
Acceptance Hill Climbing, with the second-best being Alg4, which is based on
the classic PSO algorithm. Late Acceptance Hill Climbing has shown to be very
effective in many other applications.

  * 2.

Alg4 and Alg5 converge after few steps, but Alg1, Alg5, and Alg2 took much
more time to converge.

  * 3.

Alg3 is not having improvements at the first steps, but it starts at the
ending steps. Maybe it depends on the length of the history array in our Late
Acceptance Hill climbing algorithm

  * 4.

All the algorithms were stable and converged.

Figure 3: Simulation results for the Stable network problem with 5 different
algorithms.

##  5 Conclusion

We formalized the problem of capacity changes scheduling on payment networks
while minimizing the cost of maintaining the network.

We have considered different types of this problem, depending on the input
type of transactions and the cost function type. We proposed a polynomial-time
algorithm for the batch input and the linear cost case for finding the optimal
solution using linear programming. We proved the NP-completeness of finding
the optimal modification scheme for the batch input and the step cost
function. For the online input and step cost case, we proved no deterministic
c-competitive online scheduling algorithm such that $c\leq\Delta$, where
$\Delta$ is the maximum degree of the nodes in our payment network.

After that, we proposed some heuristic algorithms for the batch input and step
cost case. We ran some simulations on those algorithms and compared them in an
empirical experiment. This paper’s results and algorithms can be used in all
off-chain payment networks like the Lightning Network or the Raiden Network.

We have not addressed other cost functions. Moreover, we have not considered
the general form of the problem, the problem in which a general function $f$
is assumed as a cost function.

For the heuristic part, we have not implemented heuristic algorithms for other
cases, such as online input and step cost. Additionally, There are more
heuristic algorithms we could investigate.

These are the problems that need to be addressed in the future.

## References

  * Zhou et al. [2020] Q. Zhou, H. Huang, Z. Zheng, J. Bian,  Solutions to scalability of blockchain: A survey,  IEEE Access 8 (2020) 16440–16455.
  * Croman et al. [2016] K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. Kosba, A. Miller, P. Saxena, E. Shi, E. G. Sirer, et al.,  On scaling decentralized blockchains,  in: International conference on financial cryptography and data security, Springer, pp. 106–125.
  * Georgiadis [2019] E. Georgiadis, How many transactions per second can bitcoin really handle ? theoretically., Cryptology ePrint Archive, Report 2019/416, 2019\. Https://eprint.iacr.org/2019/416.
  * Kim et al. [2018] S. Kim, Y. Kwon, S. Cho,  A survey of scalability solutions on blockchain,  in: 2018 International Conference on Information and Communication Technology Convergence (ICTC), pp. 1204–1207.
  * Sivaraman et al. [2020] V. Sivaraman, S. B. Venkatakrishnan, K. Ruan, P. Negi, L. Yang, R. Mittal, G. Fanti, M. Alizadeh,  High throughput cryptocurrency routing in payment channel networks,  in: 17th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 20), pp. 777–796.
  * Poon and Dryja [2016] J. Poon, T. Dryja, The bitcoin lightning network: Scalable off-chain instant payments, 2016\.
  * Avarikioti et al. [2020] Z. Avarikioti, O. S. T. Litos, R. Wattenhofer,  Cerberus channels: incentivizing watchtowers for bitcoin,  in: International Conference on Financial Cryptography and Data Security, Springer, pp. 346–366.
  * Decker and Wattenhofer [2015] C. Decker, R. Wattenhofer,  A fast and scalable payment network with bitcoin duplex micropayment channels,  in: Symposium on Self-Stabilizing Systems, Springer, pp. 3–18.
  * Green and Miers [2017] M. Green, I. Miers,  Bolt: Anonymous payment channels for decentralized currencies,  in: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 473–489.
  * Avarikioti et al. [2018a] G. Avarikioti, G. Janssen, Y. Wang, R. Wattenhofer,  Payment network design with fees,  in: Data Privacy Management, Cryptocurrencies and Blockchain Technology, Springer, 2018a, pp. 76–84.
  * Avarikioti et al. [2018b] G. Avarikioti, Y. Wang, R. Wattenhofer,  Algorithmic blockchain channel design,  arXiv preprint arXiv:1810.07603 (2018b).
  * Avarikioti et al. [2020] Z. Avarikioti, L. Heimbach, Y. Wang, R. Wattenhofer,  Ride the lightning: The game theory of payment channels,  in: Financial Cryptography.
  * Prihodko et al. [2016] P. Prihodko, S. Zhigulin, M. Sahno, A. Ostrovskiy, O. Osuntokun,  Flare: An approach to routing in lightning network,  White Paper (2016).
  * Seres et al. [2020] I. A. Seres, L. Gulyás, D. A. Nagy, P. Burcsi,  Topological analysis of bitcoin’s lightning network,  in: Mathematical Research for Blockchain Economy, Springer, 2020, pp. 1–12.
  * Herrera-Joancomartí et al. [2019] J. Herrera-Joancomartí, G. Navarro-Arribas, A. Ranchal-Pedrosa, C. Pérez-Solà, J. Garcia-Alfaro,  On the difficulty of hiding the balance of lightning network channels,  in: Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security, Asia CCS ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. 602–612.
  * Chrobak et al. [2012] M. Chrobak, G. J. Woeginger, K. Makino, H. Xu,  Caching is hard—even in the fault model,  Algorithmica 63 (2012) 781–794.
  * Albers [1996] S. Albers, Competitive online algorithms, Computer Science Department, University of Aarhus, 1996\.
  * Yang [2020] X.-S. Yang,  Nature-inspired optimization algorithms: Challenges and open problems,  Journal of Computational Science 46 (2020) 101104.
  * Burke and Bykov [2017] E. K. Burke, Y. Bykov,  The late acceptance hill-climbing heuristic,  European Journal of Operational Research 258 (2017) 70–78.
  * Delahaye et al. [2019] D. Delahaye, S. Chaimatanan, M. Mongeau,  Simulated annealing: From basics to applications,  in: Handbook of metaheuristics, Springer, 2019, pp. 1–35.
  * https://github.com/fiatjaf [2020] https://github.com/fiatjaf, Bigsun lightning network api, https://ln.bigsun.xyz/, 2020\. [Online; accessed April-2020].