論文 / 著書情報
Article / Book Information
題目(和文)
Title(English)

Lightweight Offchain Protocols for UtxO Based Ledgers

著者(和文)

JourenkoMaxim

Author(English)

Maxim Jourenko

出典(和文)

学位:博士(理学),学位授与機関:東京工業大学,
報告番号:甲第12061号,
授与年月日:2021年9月24日,
学位の種別:課程博士,
審査員:田中 圭介,伊東 利哉,尾形 わかは,鹿島 亮,首藤 一幸,森 立平

Citation(English)

Degree:Doctor (Science),
Conferring organization: Tokyo Institute of Technology,
Report number:甲第12061号,
Conferred date:2021/9/24,
Degree Type:Course doctor,
Examiner:,,,,,

学位種別(和文)

博士論文

Type(English)

Doctoral Thesis

Powered by T2R2 (Science Tokyo Research Repository)

Lightweight Offchain Protocols for UTxO Based
Ledgers
Maxim Jourenko
Academic Supervisor: Professor Keisuke Tanaka
May 31, 2021

2

Contents
1 Introduction
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77
92 Background: Offchain Protocols
11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 More than Pairwise Channels and State of Knowledge . . 12
2.1.2 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 A Taxonomy for Layer-2 . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2 Functions on Each Level . . . . . . . . . . . . . . . . . . . 14
2.3 Off-Chain Channel Level . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Preliminaries: Transaction Design Review . . . . . . . . . 17
2.3.2 Technical Challenges/Channel Constructions . . . . . . . 18
2.4 Network Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.1 Technical Challenges . . . . . . . . . . . . . . . . . . . . . 24
2.4.2 Construction Function . . . . . . . . . . . . . . . . . . . . 25
2.5 Network Management Level . . . . . . . . . . . . . . . . . . . . . 27
2.5.1 Technical Challenges . . . . . . . . . . . . . . . . . . . . . 27
2.5.2 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 A Framework for UTxO Based Offchain Protocols
33
3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 The UTXO Paradigm . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 The Framework for UTxO Ledgers . . . . . . . . . . . . . . . . . 35
3.3.1 Offchain Protocols . . . . . . . . . . . . . . . . . . . . . . 35
3.3.2 Operations on Transaction Trees . . . . . . . . . . . . . . 35
3.4 The Security Model . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.1 The Adversarial and Computational Model . . . . . . . . 36
4 Lightweight Virtual Payment Channels
39
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Pairwise Payment Channel . . . . . . . . . . . . . . . . . . . . . 42
3

4

CONTENTS
4.2.1 Types of Transactions . . . . . . . . . . . . . . . . . . . .
4.2.2 Pairwise Payment Channel . . . . . . . . . . . . . . . . .
4.3 Overview of the Construction . . . . . . . . . . . . . . . . . . . .
4.3.1 Intuition of the Protocols . . . . . . . . . . . . . . . . . .
4.3.2 Discussion of Attack Scenarios . . . . . . . . . . . . . . .
4.4 Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Types of Transaction . . . . . . . . . . . . . . . . . . . . .
4.4.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 The UC Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1 The Global Clock Functionality GCLOCK . . . . . . . . . . .
4.5.2 The Global Functionality GUTXO−Ledger . . . . . . . . . . .
4.5.3 The signature functionality FSIG . . . . . . . . . . . . . .
4.5.4 The Script functionality . . . . . . . . . . . . . . . . . . .
4.6 The Pairwise Payment Channel Functionality . . . . . . . . . . .
4.6.1 General Behavior of our Functionalities . . . . . . . . . .
4.6.2 The Payment Channel Functionality FPWCH . . . . . . . .
4.6.3 An Extension to the FPWCH Functionality . . . . . . . . .
4.7 The Ideal Virtual Channel Functionality . . . . . . . . . . . . . .
4.8 The Pairwise Payment Channel Protocol . . . . . . . . . . . . . .
4.8.1 General Behavior . . . . . . . . . . . . . . . . . . . . . . .
4.8.2 The PWCH Protocol . . . . . . . . . . . . . . . . . . . . .
4.8.3 An Extension to the PWCH Protocol . . . . . . . . . . . .
4.9 The Formal Virtual Channel Protocol . . . . . . . . . . . . . . .
4.10 Simulation Based Security Proof . . . . . . . . . . . . . . . . . .
4.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42
43
43
44
46
48
48
49
49
49
52
52
53
54
55
55
56
58
59
62
63
63
66
67
70
73

5 Payment Trees75
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.2.1 Hashed Timelock Contracts . . . . . . . . . . . . . . . . . 78
5.2.2 Atomic Multi-Channel Updates . . . . . . . . . . . . . . . 79
5.3 The Channel Closure Attack on AMCU . . . . . . . . . . . . . . 80
5.3.1 The Vulnerability . . . . . . . . . . . . . . . . . . . . . . . 80
5.3.2 Intuition on The Channel Closure Attack . . . . . . . . . 80
5.3.3 The Formal Channel Closure Attack . . . . . . . . . . . . 81
5.4 Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.3 System Goals . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.5 Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.5.1 Split Transactions . . . . . . . . . . . . . . . . . . . . . . 86
5.5.2 Merge Transactions . . . . . . . . . . . . . . . . . . . . . 86
5.5.3 Payout Transactions . . . . . . . . . . . . . . . . . . . . . 87
5.6 Our Payment Tree Construction . . . . . . . . . . . . . . . . . . 88
5.6.1 Helper Functions and Sub-Protocols . . . . . . . . . . . . 89

CONTENTS

5.7

5.8

5.6.2 The Complete Payment Trees Protocol . . . . . . . . . . .
5.6.3 Handling of Fees . . . . . . . . . . . . . . . . . . . . . . .
Collateral Efficiency and Security Analysis . . . . . . . . . . . . .
5.7.1 Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . .
5.7.2 Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7.3 Discussion of Attacks from the Literature . . . . . . . . .
5.7.4 Security Proofs . . . . . . . . . . . . . . . . . . . . . . . .
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
91
93
93
94
94
95
96
97

6 Conclusion
99
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2 Potential Future Work . . . . . . . . . . . . . . . . . . . . . . . . 100
7 Bibliography

101

Publications Included in this Work:
Lightweight virtual payment channels, Maxim Jourenko, Mario Larangeira,and Keisuke Tanaka, In Cryptology and Network Security, pages 365–384, Springer
International Publishing, December 2020, doi:10.1007/978-3-030-65411-5 18
Payment trees: Low collateral payments for payment channel networks, Maxim Jourenko, Mario Larangeira, and Keisuke Tanaka, In International Conference on Financial Cryptography and Data Security. Springer,
March 2021.

6

CONTENTS

Chapter 1

Introduction
1.1

Introduction

Since the introduction of Bitcoin by Nakamoto [100] decentralized digital payment systems enjoyed great popularity. The technology behind Bitcoin, namely
blockchains, inspired derivatives as well as new approaches to blockchain based
payment systems. At the time of writing 8423 blockchains with a market capitalization of a little more than $1.371 trillion exist 1 . This popularity served
to highlight scalability limitations of blockchain based systems. Transactions,e.g. payments, have to be processed through a consensus mechanism by a setof parties called miner to be included in the ledger. However, the number oftransactions that can be processed by the consensus mechanism in any given
time is limited which is necessary to ensure security of the system. Transaction issuers include a fees for the miners to incentivize that their transaction
is processed by the consensus mechanism and included in the ledger. Moreover, this monetary fee additionally serves to incentivize miners to collaboratein the consensus mechanism and by doing this improve the system’s security
as a whole. However, in times of popular demand the number of transactions
issued outpaces the number of transactions that can be processed through theconsensus mechanism, which results in transaction issuer to include higher fees.
For instance, the highest average transaction fee on any given day for Bitcoin
equalled $55.27 2 .
Improving scalability of blockchain based systems is a research focus of thecommunity. Possible solutions range from improving the network infrustructure[75] using dedicated server or improving the network protocol 3 . These proposals
are commonly referred to Layer-0. Layer-1 approaches focus on adjusting theconsensus protocol itself and a plethora of proposals have been introduced [56,73, 52, 125, 22, 59, 107, 106, 134, 84, 77]. Lastly, Layer-2 proposals aim to reduce
1 https://coinmarketcap.com
2 https://ycharts.com/indicators/bitcoin average transaction fee
3 https://en.bitcoin.it/wiki/Stratum mining protocol

7

8

CHAPTER 1. INTRODUCTION

the number of transactions that are issued by creating shared accounts between
parties, having these parties exchange transactions among themselves, and only
submitting transactions that summarize the transaction history between theparties. These shared accounts are commonly called channels [44, 108, 112]
and approaches to concatenate channels into payment channel networks (PCN)
extend this approach. The arguably most prominent PCN is built for the Bitcoin
blockchain and is called the Lightning Network [112].
Scalability proposals on Layer-2, commonly called offchain protocols, areparticularly promising as they potentially reduce the number of transactions
issued to the consensus mechanism by an arbitrary amount. While channels
themselve allow two parties to perform an arbitrary amount of payments withanother, methods as Hash Timelocked Contracts (HTLC) [112] allow parties
to perform payments across a path of payment channels. Parties who join a
PCN using a channel can potentially perform payments with any other party
in the same PCN without issuing any transaction to the ledger. To our knowledge, as of now HTLCs are the only method to perform payments within theLightning Network. It has been shown that HTLCs are vulnerable to denialof service and griefing attacks [99, 109]. Smart contracts, which are programs
that are executed within the consensus mechanism for Ethereum, can be used
to add features and improve operations on channels and PCNs. The payment
protocol Sprites [98] allows for payments across PCNs while mitigating the impacts of denial of service and griefing attacks. Moreover Virtual State Channels[46, 49] use existing channels to allow for the creation of new channels in a PCN
while not requiring any issuing of a transaction which is in contrast to regularchannel constructions. While these works are important contributions to thefamily of Layer-2 protocols, requiring smart contract capability severely limits
the employability of these protocols. The vast majority of blockchains, including Bitcoin, do not possess smart contract capability and as such are barredfrom utilizing these protocols. The Atomic Multi-Channel Updates (AMCU)
protocol [51] attempts to close this gap by providing a payment protocol for
PCNs, that are based on blockchains without smart contract capability, thatmitigates denial of service and griefing attacks, but the protocol itself is shown
to be vulnerable in the face of a malicious adversary.
This work aims to close this gap. Concretely, our contributions are as follows.
• We summarize the related work on Layer-2 scalability solutions and present
a taxonomy.
• We present a novel framework to construct offchain protocols for ledgers
based on the Unspend Transaction Output (UTxO) paradigm and without
smart contract capability such as Bitcoin.
• We present the Channel Closure Attack. An attack on the AMCU protocolthat allows a malicious adversary to steal funds from honest participants.
• We present the Lightweight Virtual Channel protocol that allows for thecreation of virtual channels

1.2. STRUCTURE

9• We prove security of Lightweight Virtual Channels in Canetti’s Universal
Composability (UC) Framework [29]• We present the Payment Trees protocol; an payment protocol for PCNs
that mitigates denial of service and griefing attacks.
Our work presents Layer-2 scalability solutions previously only available forblockchains with smart contract capability. This work reduces the gap between
solutions that require smart contract capability and those that do not, and it
shows resulting trade-offs.

1.2

Structure

In the following, first we give an overview of scalability solutions for blockchainswith particular focus on Layer-2 protocols. Moreover, we structure the existing
body of work and propose a taxonomy in Chapter 2. Afterwards, we formallydefine our model for blockchains operating under the UTxO paradigm, present
our security model and introduce our framework for construction of offchain protocols in Chapter 3. Next, we introduce and discuss two protocols constructedwith our framework, namely Lightweight Virtual Payment Channel in Chapter
4 and Payment Trees in Chapter 5. Lastly, we conclude and present possible
directions for future work in Chapter 6.

10

CHAPTER 1. INTRODUCTION

Chapter 2

Background: Offchain
Protocols
2.1

Introduction

Blockchains are behind the successful rebirth of digital cash from its first attempts [34, 35], firstly by Bitcoin [100] and now with several decentralized cryptocurrencies [52, 125, 59, 56, 132]. Although Bitcoin’s relative success in offering
worldwide payment alternatives to the more traditional mechanisms, like VISA
Network [102] and Paypal [101], is undeniable, it still has a long way ahead interms of handling a larger number of transactions.
The technical challenge of increasing the number of transactions per second (TPS) of a blockchain system is urgent, and it is closely related to theinner workings of the system itself. Namely, to its consensus protocol. As amore concrete example, we refer to the Bitcoin network [100] whose consensus
protocol depends on the joint hash power of its nodes to perform the electionof a block leader, i.e. the new block issuer, which is calibrated by design tohappen every 10 minutes on average. In Proof-of-Stake (PoS) based systems,
like Cardano/Ouroboros [56, 73] and EOS [52], analogous elections exist within
a carefully designed (and strongly dependent on security guarantees) time slot
for the generation of the new block. In order to confirm a transaction a minimum number of blocks has to be added to the ledger resulting in a confirmation
time. The confirmation time, despite its central role in the security and stability of the system, imposes severe restrictions to the TPS rate of the overall
platform. Alternatives had been suggested, such as alternative structures forblockchains [53, 122, 80, 121, 123], change in the size of a block [131], signature
aggregation [24] or different consensus protocols [59, 36, 22, 107, 106]. It is
common to divide these approaches in three cases:• Layer-0 (the network infra-structure): Here, optimization and special
servers are employed to decrease the latency of the network to increase
the TPS. An example of such approach is given by BloXroute [75];1112

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS• Layer-1 (the consensus protocol): Arguably the layer which has more
approaches in literature. There are different consensus architectures [56,73, 52, 125, 22, 59, 107, 106], where a complete taxonomy can be foundin [57], different data-structures for blockchains [122, 121, 123, 53], valid
chain criteria [80], sharding [134, 84, 77] and federation [91];• Layer-2 (the off-chain channel/protocol): Protocols that perform minimal interaction with the blockchain. Typically for opening, paying, closing
and disputing a channel. In the realm of cryptocurrencies, concrete examples are given by Decker and Wattenhofer [44], the Lighting Network(LN) [112], and others. This layer encompasses many more protocols andalgorithms than the channel construction alone, as we review in later sections. One of the contributions of this work is to present a taxonomy, acoherent list of protocols, for different levels in the stack of protocols inthis layer.

Layer-2 channel constructions have few names in literature: off-chain, payment or, yet, state channels, seemingly without consensus among the researchcommunity about their meaning. Here, in the face of the lack of standard terminology, we settle to name payment channels, constructions that do only store
a distribution of coins among two parties, and state channels otherwise. Furthermore, we rely on the term off-chain channel when referring to either one
regardless of its inner workings.
In a nutshell, a payment channel between two players, is when two participants decide to trade several transactions during a period of time, and in theend they, without access to smart-contracts, settle on a final balance based on
the transactions exchanged, then the channel is closed. This transaction method
is suitable for very small amounts, i.e. micropayments, which has a long history of research [130, 83, 96, 115, 54, 128, 103, 133]. A fairly complete survey,
which includes centralized solutions, was done by Ali et al. [15]. More recently,
micropayments were also studied by Pass and Shelat [105] in the setting of decentralized currencies, and for specific applications [65, 37]. The main advantage
of such a setting is that all transactions made during the period of the channel
do not need to be published in the blockchain, which is a clear advantage as
concluded by McCorry et al. [93]. That is a set of transactions can be settled
independently of the confirmation time of the blockchain system.

2.1.1

More than Pairwise Channels and State of Knowledge

The channel constructions themselves are building blocks into a stack of protocols (or algorithms). A simple payment/state channel only paves the way forexchanging funds, which is of limited use since the channel yields a capacity, i.e.
the sum of funds initially deposited by the two players. A more interesting, andrealistic, use is the concatenation of single channels into a payment-channel network (PCN). In this setting, a node A can send payment to C without creating2.1. INTRODUCTION

13

a specific channel from scratch with C, as long as both A and C are connected
to a third node B, which relays transactions, typically by collecting fees.
A practical example of such a network is the already mentioned LN [112],
which has multiple implementations [6, 9, 2, 110]. Although it extends thechannel functionality, a lurking problem persists: how to find suitable routes
within the network ? The resemblance with theory of networks is inevitable,
naturally similar problems appear. For example, a node sending a payment
needs to find a route, similarly to routing problems in computer networks. On
the other hand, payment networks also present differences, for example, the costof the fees in a particular route. Yet, assuming the mentioned routing problem issolved, another one still exists: How about the stability of the channel/network?
Do all nodes need to be online during all the time of the channel? Is the capacityof each pairwise channel a bottleneck for the whole network?
All those questions are legit and relevant, and there are more as we will
see in later sections. Protocols and ideas to tackle them are currently being
considered and studied by the research and practitioner community very often
in an independent fashion without a comprehensive framework or compilation.
Given that these ideas can be scattered through several journals and conference
papers, as well as Internet forums and repositories, compiling them is a majortask, let alone relate them to each other accordingly with their approaches andfunctionalities.

2.1.2

Our Contribution

We provide an extensive coverage payment and state channels, i.e. Layers-2 solutions for scalability, in cryptocurrencies and their related protocols. Namely
the off-chain channel constructions, including probabilistic, simplex, and duplex,
in addition with payment network constructions and network management protocols, i.e. the upper levels protocols that assume the existence of a network ofchannels. More concretely, we introduce a single framework (Table 2.1), which
structures off-chain protocols therefore our contribution somewhat differs of thework in [62], which does not aim to structure the research literature in such away. Furthermore, in comparison, we focus on the general description and thefunctionalities of the protocols.
A Taxonomy for the Layer-2 stack. Our single framework is a taxonomy
with further classification for the three cited levels: off-chain construction, channel network, and network management. The levels compose a stack of protocols
for Layer-2, as illustrated by Table 2.1 in Section 2.2. As expected, different
levels and their respective set of functions define specific technical challenges,
which by the best of our knowledge, were never organized in a comprehensive
framework. A quick look on Table 2.1 reveals intense research on areas andfew works in others, or even no works for specific problems. We believe theseobservations are of strong interest by the research community, which, otherwise,
would have to collect these works through numerous internet forums and repos-

14

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

itories in addition to scientific journals, even to distinguish among very distinct
functionalities, let alone more subtle differences of implementation.

2.2

A Taxonomy for Layer-2

Here we propose a taxonomy for the existing channel based protocols in Layer2. We start by presenting an overview of our approach and justification for our
choices. Later we present our classification illustrated by Table 2.1.

2.2.1

Overview

We organize the different sets of protocols in three levels 1 . Each level gathers
related functions it performs, then we further subdivide the level into “functions”. The intuition is that a protocol deployed on Layer-2, is expected tofulfill a certain function within a level.
In order to illustrate and justify this design, take for example the mostpopular Layer-2 PCN technique: HTLC [112]. Briefly, for the sake of example,
HTLC allows LN nodes to establish connections between themselves in order
to transfer funds. A major challenge in this setting is to find a suitable route
among the nodes, thus the function required is Routing. A routing protocol
for the LN fits into the “Routing” function within the “Network Management”
level. Later, Table 2.1 summarizes our taxonomy and the levels we identify inthe literature. However, first, consider the following levels:• Off-chain Channels: Here are the constructions of the channels. In
other words, how the nodes, relying on the transaction design of a cryptocurrency, can construct single pairwise-channels. These are the building
blocks of the upper levels.
• Network: Here are the techniques employed to create the networks themselves. Typically by concatenating existing pairwise channels, or establishing a network of more than two nodes right from start.
• Network Management: This is the level for the protocols that maintainthe channels and network of channels, and allow their efficient use while
keeping them “alive” and usable.

2.2.2

Functions on Each Level

Given the earlier identified levels, in this section we further break them down
into functions and provide a brief intuition behind the classification.
1 We justify the choice of the term “level”, instead of the more natural “layer”, as analternative to avoid ambiguity with the terms Layer-0, Layer-1 and Layer-2 which permeate
this work.

2.2. A TAXONOMY FOR LAYER-2

15

Off-Chain Channels. The terminology in the literature is not standard.
However it is possible to observe two big functionalities (1) make paymentsand (2) keeping state. The first is the simplest, since it does not require tokeep a state in order to perform a payment, whereas the second is more generaland it does require the aid of smart contracts (typically to support more complex operations). While in our classification (2) cannot be divided, therefore it
represents the state channel variety, we further break down (1) into the three
existing types: Duplex, Simplex, and Probabilistic.
Network. In order to establish PCN, special techniques are required, in addition to carrying out the payments. There are off-chain channels that do notsupport network construction capabilities, therefore this level depends on thecapabilities of the channels. We further discuss this topic on Section 2.4.
Network Management. Over the network of channels, as further discussed
in Section 2.5, several functionalities are required, and we identify the following
main ones in the existing literature:• Routing: The payments can be carried over several nodes, however it isnecessary to select the set of nodes as the route, and several maybe beavailable.
• Re-Balancing: A difference from regular computer networks is that eachpairwise channel has a capacity which may exhaust during the course of
the exchange of transactions, and therefore it needs to be rebalanced.
• Stability: Another difference from regular computer networks, is thatsome constructions require the nodes to be online in order to perform thedispute phase of the protocols. Therefore there are protocols that mitigate
or solve this requirement.
• Anonymity/Privacy: Information of nodes within a network, can beleaked as well as information about the performed transactions. Typically,
the nodes in the middle of the channel can see the flow of funds.
A major difficulty on gathering the information on protocols for Layer-2 isthat, in contrast to scientific community literature, several protocols had been
proposed in forums and Internet repositories, and not in conference proceedings or journals. A unified compilation of issues and open problems is also,
apparently, non existent. We address this with our suggested classification in
Table 2.1, and further discuss them.
Secure multiparty computation. The reader should note that our definition of channel does not cover, for example, secure multiparty computation
protocols, i.e. several users interact off-chain and provide correctness proof ofthe computation. Here, purposely we focus only in protocols that realize a channel between two nodes, and PCNs through concatenation of channels. In other

16

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS
Level

Function
Routing
Section 2.5.2

Network
Management
Section 2.5

Network
Section 2.4

Re-Balancing
Channels
Section 2.5.2
ChannelStability
Section 2.5.2
Anonymity/
Privacy
Section 2.5.2
Construction
Section 2.4.2
State
Section 2.3.2

Off-chain
Channels
Section 2.3

Duplex
Payment
Section 2.3.2
Simplex
Payment
Section 2.3.2
Probabilistic
Payment
Section 2.3.2

Protocols
Silent Whispers [85]Speedy Murmur [118]Spider Routing [120]Flare Routing [113]
Splitting Payments [111]Hoenisch and Weber [64]Atomic Multi-path [104]
REVIVE [69]PISA [92]Avarikioti et al. [19]Fulgor & Rayo [86]Tumblebit [63]HTLC [112]
Sprites [98]State Assertion [27]Virtual Channels [46]Counterfactual [38]Z-Channel [136]Perun [46]
NoCUST [70]Raiden [7]Lightning [112]Decker et. al. [44]BOLT [61]Teechan [81]Burchert et al. [28]TumbleBit [63]Simplex [13]Dimitrienko et al. [45]Takahashi et al. [126]Pass et. al. [105]
Hu and Zhang [65]Table 2.1: The channels stack and concrete protocols.
words, we leave out of our classification protocols with multiuser distribution offunds, as used in [21, 41, 43, 42], given that this is a wide research area.
Network construction technique. The reader should note that Table 2.1
arranges LN [112] in the Off-chain Channels Level, not in the Network Level,
and this can be considered unusual, given that LN is associated with PCN. We
highlight that the construction technique used in both cases is the HTLC, also
introduced in [112], therefore a more accurate setting is to locate the techniquein the Network level instead. Moreover, this arrangement is consistent with theliterature as in [94]. Similarly, we acknowledge that both [46] and [38] could beclassified in the Off-chain channel.
Comparison on the body of work in each level. Briefly, given the similarities with computer networks, researchers realized that techniques can be2.3. OFF-CHAIN CHANNEL LEVEL

17borrowed from currently known network algorithms, albeit the need to adapt
them. This trend is promoted by Hoenisch and Weber [64], for routing, a crucial
functionality within the Network Management Level. This trend contrasts withthe technicalities of the off-chain channel and network levels. Our taxonomy
decouples these different issues, and we further discuss them in Sections 2.3(channels), 2.4 (networks) and 2.5 (management).
As expected the off-chain channels body of work, described in Section 2.3,
presents a greater number of works, in comparison to, for instance, the Network
level as described in Section 2.4. The reason is that most of the protocols in
Section 2.4 derive from a single technique to realize conditional payments, theHTLC, which was recently fully formalized by Kiayias et. al [71]. An example
of derived similar technique is Sprites [98] which employs a derived technique
but with smart-contracts.
On the other hand, the amount of work on off-chain channels is comparable
to that of the Network Management level, because of the significant amount ofeffort put on the functionality of routing among the nodes of the network byresearchers and developers as later illustrated by Table 2.1 and also described in
Section 2.5. It is easy to note that even in this level there are discrepancies on
the attention given by the community on the function within the level, as the
single work on re-balancing the network, i.e. the REVIVE protocol [69], shows.
Security and privacy preserving constructions. In order to illustrate
the type of problems between the levels, we observe that privacy and security
permeates the layers, and some problems are well known in the literature. For
example, exchange of funds, in off-chain channels, needs to be consistent with thepayments, i.e. the channel constructions should not allow parties to steal coinsfrom each other, that is they should provide balance security, which is a property
common to all safe channel constructions. Similar concerns exist for payment
networks, but extended to the intermediate nodes, i.e. the nodes that allow theconnection between two other nodes with not common channel. Furthermore,
PCN should prevent information to be leaked to intermediate nodes. Finally,
network management systems should provide several features such as routing
for payers and payees, rebalancing and others while guaranteeing safety, in thesense of balance security, and preventing information leakage.

2.3

Off-Chain Channel Level

Before reviewing the constructions for off-chain channels, it is convenient toreview the structure of transactions and how they can be issued on typical
cryptocurrency. That clarifies for the reader how channels can be established.

2.3.1

Preliminaries: Transaction Design Review

Payments done on a blockchain are recorded in the form of transactions, as in
Figure 2.5. Each transaction consists of n inputs and m outputs, n ∈ N, m ∈18

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

N0 . Each output consists of coins as well as a spending requirement. A plain
payment has as requirement a signature with the private key of the payee. Inputs
on the other hand consist of a reference to an output of a previous transaction
on the blockchain (which was not referenced by another input before) as well as
a witness for the spending requirement, e.g. a witness is a signature with theprivate key of the payee.
Spending requirements can be more complex than simply asking for the
payee’s signature. A relevant spending requirement for us is the k-out-of-l multisignature supported by Bitcoin with the opcode CHECKMULTISIG within
its scripting language. A witness to such a requirement needs to contain signatures of k out of l specified parties. Channel construction techniques rely on
the k = l = 2 spending requirement. A transaction can specify a timelock to
enforce that miner will not include a transaction before a specified point in time.
Timelocks can either be defined per input or for a whole transaction. Moreover
timelocks can specify an absolute time or a point in time relative to when thereferenced inputs were included in the blockchain. In Bitcoin an absolute timelock for a whole transaction can be specified with the field nTimelock, a relative
timelock can be defined for each input using the field nSequence [1]Lastly, in thefollowing we denote ∆ as the maximum time required for a transaction to becommitted by a party and subsequently be included in the blockchain, which is
critical in the Dispute phase of the channel (outlined in Section 2.3.2).

2.3.2

Technical Challenges/Channel Constructions

Most of the interaction in a pairwise channel happens only between the players
in the channel. Therefore, the players need to keep the balance through all thetransactions performed in the channel, in other words the protocol should offer
balance security. As we see next, very often, in order to have balance security,
the nodes need to be online to take action in the case the partner in the channel
misbehaves.
General Description.
The terminology is fuzzy since both terms, “payment” channel and “state”
channel are used. Both terms refer to the idea of relying on off-chain directcommunication between two players, i.e. a channel. That is, initially, bothparties open the channel by committing a certain amount of coins, which will be
the channel capacity or the maximum amount that is passed from one player tothe other. The state of the channel can be tracked by simple signed transactions
with or without the aid of smart-contracts. Channels utilizing smart-contracts
have the capability to storage arbitrary state thus realizing state-channels.
The simplest form of channel relies on instructions for timelocks, e.g. the one
described in BIP65 [23], and threshold signatures2 using the early mentioned
CHECKMULTISIG opcode. Typically channels have four phases:
2 Often denoted multisig by the Bitcoin community.

2.3. OFF-CHAIN CHANNEL LEVEL

19• Setup: Two parties lock funds into the blockchain which the sum of funds
is the capacity of the channel. It is important to note that the parties needto account for the confirmation time of the chain to start the channel.
• Payment: This phase the parties can exchange funds without interaction
regardless of the confirmation time of the system. During this phase theinitially locked funds cannot be used outside of the channel.
• Dispute: At any moment, a user can start a dispute in the case the otherparty do not follow the protocol.
• Closing: When two players decide to close the channel, they publish
transactions in the blockchain, which reflect the exchange of funds that
happened in the Payment Phase. Again, in this phase the players need torely on the confirmation time of the blockchain. Furthermore, this phase
can also trigger the Dispute Phase, whenever the parties do not agree on
the current state.
Typical Channel.
The current balance of the channel is kept between the parties by directly exchanging mutually signed transactions with the amount being passed from one
player to the other. When the channel is closed the last pair of exchanged transaction are committed to the blockchain, which makes the coins available to beredeemed by parties. A safety mechanism is in place by locally keeping thesigned transactions representing the new state of the channel. When a player
does not correctly perform the protocol, e.g. by not confirming a payment, thus
the protocol enters in the dispute phase. During this phase, for [112], the partner can publish its locally kept (and mutually signed) transaction claiming thecoins of the channel. Alternatively, in Decker and Wattenhofer [44], the channel
is closed in the previous state. The consistency of all signed transactions are assured to be correct due to the use of timelock operation code in the transaction
verification script language [23]. In comparison, state channels rely on smartcontracts since they offer more complex operations. A contract, by design, cankeep track of the balance and transactions made into it. Therefore it can execute payments accordingly based on previously set conditions. In particular,
the execution of a protocol can be triggered by presenting proofs of correctness
on secure multiparty protocols [21, 43, 41, 78, 79]. More formally, given witnessthat a protocol was correctly performed, the contract can be executed.
Payment Channels.
Here we describe the main works on payment channels, from simplex, and probabilistic, to duplex constructions. Afterwards, we review state channels. Finally,
we present constructions for privacy preserving channels.

20

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS
Funding Transaction

Refund Transaction
Timelock & SeqNum1

X BTC
Inputs:X BTC from Alice (Sig) 2-out-of-2 Signature:
Alice & Bob

Signature from
Alice & Bob

Output:X BTC to Alice

Figure 2.1: Setup
Funding Transaction

Refund Transaction
Timelock & SeqNum2

X BTC
Inputs:X BTC from Alice (Sig) 2-out-of-2 Signature:
Alice & Bob

Signature from
Alice & Bob

Output 1:
X - δ BTC to Alice
Output 2:

δ BTC to Bob

Figure 2.2: Payment
Funding Transaction
X BTC
Inputs:X BTC from Alice (Sig) 2-out-of-2 Signature:
Alice & Bob

Refund Transaction

Signature from
Alice & Bob

Output 1:
X - δ BTC to Alice
Output 2:

δ BTC to Bob

Figure 2.3: Updated version of payment
Figure 2.4: Figure 2.1 shows the initial state of a payment channel upon setup.
Figures 2.2 and 2.3 show payments. The former makes use of sequence numbers
and timelocks to replace previous payments. For example, for a channel between
A and B, with capacity CA and CB , the coins committed, respectively, by A
and B, after a transaction with value δ from A to B, therefore the new state
is CA − δ, for A’s balance and CB + δ for B’s balance. In 2013 this protocol
was updated, as illustrated in Figure 2.3. This update removes the use of thesequence number. Moreover the timelock in the initial Refund Transaction is
kept, however, updated Refund Transactions do not contain a timelock.
Simplex Payment. The earliest proposal of payment channels that we could
find was posted on the Bitcoin Wiki [13] and is illustrated in Figure 2.4. Notethat the first proposal mentioned here makes use of a sequence number to replace
previous transactions, however, the respective, and already cited, Bitcoin field,
nSequence has been disabled on 20th August 2010 [1, 13] 3 .
Figure 2.4 illustrates a simplified form of the protocol in [13] between two
parties: The payer and payee, and they initiate the Setup Phase. In order to do
this the payer prepares two transactions as depicted in Figure 2.1. The first is
the so called Funding Transaction which takes as input funds from the payer andspends them within one output that requires the signatures of both payer andpayee to spend. The second is the Refund Transaction which spends the output
3 https://github.com/bitcoin/bitcoin/commit/05454818dc7ed92f577a1a1ef
6798049f17a52e7#diff-118fcbaaba162ba17933c7893247df3aR522

2.3. OFF-CHAIN CHANNEL LEVEL

21

Transaction Tx
Timelock
Input 1:X BTC from Alice(Witness)
Input 2:Y BTC from Bob(Witness)

Output 1:
X + Y BTC
2-out-of-2 Signature:
Alice & Bob…

…

Input n:Z BTC from Charlie(Witness)

Output m:
W BTCSignature:
Alice

Figure 2.5: A simplified illustration of a transaction, with n inputs (left side)and m outputs (right side).
of the Funding Transaction and pays them back to the payer. Moreover thetransaction has the sequence number set to 0, and a timelock in the near futureby adjusting the value of nLocktime. Then, without signing the transactions, thepayer sends both transactions to the payee who signs them and sends them back.
After verifying the payee’s signatures, the payer signs both transactions itself
and sends them back. Then, one of the parties commits the Funding Transaction
to the blockchain.
If the payer wants to pay a certain amount, it happens in the Payment
Phase, it creates a new version of the Refund Transaction that still spends theoutput of the funding transaction but instead of giving all funds back to thepayer, it contains an output that allocates some funds to the payee as depicted
in Figure 2.2. Moreover, the sequence number is set to a higher value to replace
the previous transaction. The payer signs this transaction and sends it to thepayee. This process can be repeated for subsequent payments that all adjust
the funds more and more in Payee’s favor and increase the sequence number
respectively.
Correctly keeping track of balances. The timelock and the sequence numbers prevent the payer to double-spending the funds. If the payer publish its
Refund Transaction, created at Setup Phase which gives all funds back to thepayer, to the blockchain, the payee could commit any Refund Transaction with ahigher sequence number to replace Alice’s committed transaction. However, thepayee needs to commit his Refund Transaction before expiration of the timelockon payer’s Refund Transaction. Since then the protocol has been adjusted on the
Bitcoin-development mailing list [124] and the Bitcoin Wiki entry [13].
Probabilistic Simplex. Pass et al. [105] propose a probabilistic payment system to reduce the number of transactions on the blockchain and subsequently
reduce the amount of transaction fees enabling micropayments. Moreover theirsolution provides near-instantaneous payments without requiring confirmation

22

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

delays. Their work is based on the work of Wheeler [129], Rivest [116] as wellas subsequent work [82, 97], and proposes three protocols. The first is naive,
therefore vulnerable, construction for two parties. The second and third protocols are similar, with both relying on verifiable third party with the difference
that the latter is optimistic, and relies on the verifiable third party in case ofa dispute. In these protocols the payer sets up an escrow address and put anamount a of coins into it. After the payment is performed the payer can potentially use the same escrow to pay another merchant after some time has passed.
This work was improved by Hu and Zhang [65] using a time-locked deposit.
Duplex Payment. In a duplex payment channel both parties can allocate
funds into their mutually shared channel and these funds can be redistributed
between both parties arbitrarily. Both the constructions for duplex channels
proposed by Decker et al. [44] and the LN [112] extend the idea of simplex
payment channel4 . That is, first, parties create a funding transactions in which
both parties allocate their funds by paying coins into it. Moreover the fundingtransaction contains one output which requires signatures of both parties tospend. Second, the parties create a refund transaction which spends the fundingtransaction and has two outputs which pays back the coins to their respective
parties. Note that each party needs to hold off signing the funding transaction
until it holds a fully signed refund transaction since, otherwise, the other party
might hold the funds in the funding transaction as hostage by committing thefunding transaction and refusing to sign the refund transaction. After signing
the refund transaction both parties sign the funding transaction and commit itto the blockchain to lock their funds into the channel, for the setup phase of
the channel. Parties execute a payment by creating a new refund transactionand exchanging signatures. The payment is considered executed when bothparties hold the new fully signed refund transaction and invalidate all previous
refund transactions. If both parties cooperate for channel closure the parties
sign and commit a closing transaction that spends the funding transaction andpays each party the amount of coins that are denoted in the most recent refund
transaction.
Dispute Phase differences. The way previous refund transactions are invalidated differs in [44] and [112]. While in [44], the dispute is solved using
timelocks, to enforce the most recent mutually agreed status, in [112] it is doneby punishing the party by giving all channel coins to the honest party. Briefly,
the former structures channels within a, so-called, invalidation tree. The funding transaction represents the tree’s root and refund transactions are the leavesof the tree. Each payment adds a node in form of a transaction into the tree.
There are two methods that enforce that only one path in the tree, and therefore only one refund transaction, is valid. For one, each node in the tree hasa relative timelock to its parent. A node in the tree can invalidate all of its
siblings by setting its timelock to be ∆ less than the minimal timelock on all of
4 A comparison can be found in [95].

2.3. OFF-CHAIN CHANNEL LEVEL

23

its siblings. Note that refund transactions are always set to the highest locktime
possible as agreed by both parties.
Channel factories. The general framework for channels imposes restrictions
on the creation of channels. Namely, the confirmation time for the Setup
Phase may still be unacceptable for micropayments. Furthermore, upon channel creation the funds are locked for only that channel. The relaxation in theserequirements is the motivation for the creation of channel factories proposedby Burchert et al. [28]. The core idea is to introduce a layer between theblockchain and the payments. This translates into a step where a group ofcollaborators jointly fund a factory. This first step, still requires blockchain interaction, therefore still is subject to the limitations of the consensus algorithm.
However any new pairwise channel can be created, among the initial users, fromthis point, upon communication between the collaborators, hence creating channels. Although the factory creation still requires time and funds locking into theblockchain, the advantage of this design is that it allows reallocation of funds
between the pairwise channels.
Embedding script into signature. An interesting idea to preserve spacein the blockchains, which is the case for major cryptocurrencies, is to embedmore instructions into the signature issuing procedure by relying on a more sophisticated, i.e. one that offers more properties, signature scheme. That is theapproach introduced by Poelstra [5, 10] denoted scriptless script for the Schnorr
signatures and LN, which was recently extended by Malavolta et al. [88] to themore suitable, for cryptocurrencies, ECDSA signature scheme. Alternatively, [5]outlines an approach with the Schnorr signature scheme to embed the value ofthe pre-image x, i.e. for the HTLC hash challenge, into the signature computation algorithm, jointly carried by the payer and the payee of the channel.
Although the formalization effort displayed in [88], the authors point out it
is not the case for other proposals. Furthermore, main cryptocurrencies, e.g.
Bitcoin and Ethereum, may not be compatible to the Schnorr scheme.
Privacy preserving channels. BOLT [61] is a channel construction focusedon anonymity. Assuming either an anonymous blockchain such as Zcash [14] oranonymization techniques such as mixer, the BOLT protocol provides anonymity
for one of both parties. A use case for this is a merchant that receives payments,
however, has no means to learn the identity of the customer. A drawback is thatthe BOLT protocol requires the anonymous customer to be honest as they canotherwise block closure of the channel locking the merchant’s coins indefinitely.
State Channels. Until now, in this work, the channels are built based on
special instructions for transactions, as described in Section 2.3.1. Smart contracts, as in Ethereum, enable more complex offchain structures which has been
investigated in [46, 98]5 . A particular use for smart-contracts aims to enforce
5 We discuss [46] and [98] in more detail in Section 2.4.

24

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

fairness and correctness on distributed systems. The approach of relying inpenalties to guarantee correctness and fairness of computation, in particular,
on secure multiparty computation protocols, has been independently exploredfor efficient protocols on the top of blockchain. For the general case, this idea
has been introduced by Andrychowics et al. [17, 16], and later by Bentov andKumaresan [20]. For specific purposes, e.g. card-games, it was further exploredby Bentov et al. [21] and David et al. [41, 43, 42].
Compared to the previously mentioned constructions for payment-channels,
the state channel can be implemented more straight forwardly. They are opened
by committing the respective smart contract onto the blockchain, whose state
can be changed using a message signed by both parties as well as a sequencenumber. Parties change the state offchain by computing a message to the smart
contract that would make transition into that state including a sequence number
and exchanged signatures for this message but without committing the message
onto the blockchain.
NoCUST [70] is another protocol which relies heavily on smart-contracts.
Here two parties wishing to exchange small amounts create a channel by making
their deposits into a smart-contract, therefore two on-chain operations. All the
payments from that point on, are executed off-chain via a third trusted node
which intermediates the off-chain operations between the two participants, andeach payment requires issuing request payments and receipts. This design has
the advantage, in comparison to regular payment hub over off-chain channels,of not requiring the hub node to allocate/lock a large amount of funds, hence
no custodian, while intermediating payments between large group of pairs of
nodes.

2.4

Network Level

In this level, the goal is to focus on how the channel network can be established,in contrast to how it is managed (which is the topic of Section 2.5). Concretely,
how channels can be concatenated securely to carry payments through several
nodes.

2.4.1

Technical Challenges

The main function of this level is the construction of a payment route. Moreconcretely, how the pairwise “inner” channels can be concatenated and used toprovide a medium for payments between two nodes that are more than one hop
apart. Within this setting, it is important to keep, balance security, speciallyin the inner nodes of the route. Here the challenge is harder than in the earlysections, because in the network cases, the nodes within the route can also
collude against the honest players.

2.4. NETWORK LEVEL

2.4.2

25

Construction Function

The payment networks and related concepts had been previously studied:trust networks [58, 67, 114], credit networks [40], path-based transaction (PBT)[119] and privacy in PCN [86]. Here we are interested in construction techniques
for pairwise channels, in order to concatenate several channels into a channel
network. Such networks can enhance even more the scalability of a system,
because two nodes do not need to contact each other to open a channel. Instead,they can create a “virtual channel”, it the sense of Dziembowski et al. [48] via
a mutually connected node (more on this, later in the section). The most
known technique is the early cited HTLC [112], which is currently being usedin the Bitcoin network and paved the way to new propositions for different
cryptocurrencies, as in the Raiden Network [7] for the Ethereum [132].
HTLC overview and conditional transfers. Nodes can execute a payment
atomically on a set of channels using HTLC. A payment can be routed across asequence of channels without payer and payee having to create a channel between
themselves that would require committing transactions onto the blockchain.
Briefly, in [112], two nodes exchange funds by relying on a middle node, say, B,
and the two channels between A and B, and B and C. Node A wants to sendcoins to C, and, as the first step, C computes a hash value on an arbitrarily
chosen random number x and shares it with A via a direct channel, however
without establishing a payment channel. The actual transaction is carried by
A sending the funds to B, using their mutual channel with the extra condition
that node B shows the secret value x. Analogously, node B forwards the funds
to C in a similar fashion, relying in their mutual channel. Apart from LN based
channels [112], several types of channel constructions support HTLC: Raiden [7],Decker et. al. [44], and Perun [46]. Recently a full formalization of the HTLC
technique was done by Kiayias et al. [71].
Mitigating Dispute Phase costs. In general, the channel networks are optimistic, i.e. they assume the nodes will cooperate, therefore the dispute phase,as outlined in Section 2.3.2, is expected to be rarely triggered. However thisphase execution can be costly both in terms of time complexity and financiallygiven that the arbitrage can involve the execution of smart-contract to compute
penalties. The Sprites Protocol [98] introduced by Miler et al. is designed for
Ethereum’s smart contracts, and has the goal of reducing the time complexityof resolving a dispute. Note that this work is independently done in Raiden [7].
The main observation of [98] is that in case of dispute, all of the internal pairwise channels have to solve the dispute in its own respective HTLC agreement,
i.e. between each of the two consecutive nodes. Hence, [98] substitutes HTLC
values by a single Ethereum smart-contract which solves the dispute. That differs from the HTLC technique since there is no need to increment the time-lockparameter on each hop of the payment route.

26

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

A recent idea introduced by Buckland and McCorry [27] named State Assertion Channels, and it is analogous to [98] but for computational costs. The goalof [27] is to guarantee that during the Dispute Phase, which can also be triggered by closing a channel, the honest party always can be paid back regardlessof the cost of performing the verification of the full state of the application in theblockchain deployed smart contract. What Sprites [98] does for the expiration
time of channels, the State Assertion technique does for the cost of computation, which indeed can be significant if done on chain. The main setting for state
assertion channels is to deploy two smart contracts, the application (AC) andthe assertion (SC) ones, with the requirement that the latter has to receive thefunds before the creation of the channel itself. The states are not disputed in
the AC, but in SC which can pay back the honest user whenever it challenges aninvalid state transition proposed by ta malicious user. The crucial observationis that SC verifies without the full state of the application, but, instead, witha digest of it via hash values. The work in [27] provides a simulation on thisnovel approach, and it is a first step in the rigorous formalization of the idea.
Generalizing State Channels: “Virtual Channels” and “Counterfactuals”. There are approaches to construct more general structures over offchainchannels. More notably, we can find in the literature the works of Dziembowski
et al. [48] and Coleman et al. [38]. The work in [48] extends their virtual statechannel construction in [46] by enabling virtual payment channels exceeding one
intermediary party. It is done by recursively applying their construction on topof state channel as well as a “virtual state channel”, which allows the creation ofa multi-hop state channel across a sequence of single-hop state channels. This
technique allows payer and payee to operate on a shared state channel instead of
having to setup a new HTLC instance for each individual payment. More concretely, consider the scenario where parties Alice, Bob and Charles, such that
Alice and Charles, as well as Charles and Bob share a state channel respectively.
For comparison, in [112] and [44], Alice and Bob can issue payments between
each other relying on the existing infrastructure and without having to create a
new channel between Alice and Bob. However, this requires that Charles joins
the protocol for each executed payment between Alice and Bob. In contrast,
virtual payment channels allow the creation of a payment channel on the top of
the existing state channels, enabling payments between Alice and Bob without
Charles’ participation outside of virtual channel setup, closure and any dispute.
The protocol is proven in the UC framework [29], and requires smart contract
capabilities6 and therefore it is not applicable to cryptocurrencies with limited
smart contracts capabilities as Bitcoin.
In a sense, Coleman et al. [38] also aims to build a richer structure on the
top of the off-chain channels. They introduced the notion of counterfactual,
which is, in a nutshell, all the events of the channel, which can, or cannot,
be committed to the blockchain. In this paradigm, a payment in the off-chain
6A
proof-of-concept
implemented
https://github.com/PERUNnetwork/Perun.

for

Ethereumisavailableat2.5. NETWORK MANAGEMENT LEVEL

27

channel, changes a so-called counterfactual state of the system. In addition, it
is also possible to create counterfactual contracts via commitments and signatures, which generalizes the channels even further. The work in [38] presents aframework, focused on practical implementation.
The Wormhole attack and improved HTLC. The attack introduced by
Malavolta et al. [88] affects all the PCN constructions based on 2-step interaction
between the nodes, therefore HTLC based PCNs are in general, vulnerable to it.
The colluding nodes aim to capture the transaction fee which the inner nodes
on a payment route would expect to receive in order to carry the payments inthe network. Although the gravity of the attack, the authors of [88] succeededin proposing a fix for the main protocol and even warned the LN team about
the protocol weakness, which triggered new developments. In particular the
implementation of the two party ECDSA construction from [88], and its later
incorporation into the system [12]. Briefly, the attack is carried by two colluding
nodes within the same payment route. The two nodes share the pre-image
value of the HTLC, while keeping the nodes in between them oblivious to thepayment condition value. Consequently, in the point of view of the nodes inthe extremities of the path, the payment is carried out, while the nodes in the
middle of the path see it as failed. This condition allows the colluding nodes tojointly receive the transactions fee from the nodes which did not executed thepayment.

2.5

Network Management Level

This is the upmost level in our classification, and, arguably, this level offers agreater variety of technical issues in comparison to the other levels. Thus, before
reviewing the existing protocols, we described the known technical problems.

2.5.1

Technical Challenges

Here we assume that a network of channels is established, and all the nodes
have access to it. Therefore we identify the following main functions:
Routing.
Similarly to a regular computer network, in order the find a payment path, it
is necessary to probe the network for nodes available to route the payments. In
the case of channel networks, variables such as particular availability and fees
can heavily influence routing. A close look into routing in the LN is given by Di
Stasi et al. [60] and McCorry et al. [94]. A more general desiderata for routing
over channel networks is given by Hoenisch and Weber [64] based on similarities
between channels and Mobile Ad Hoc Networks (MANET).

28

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

Re-balancing route.
Each pairwise channel is associated with a channel capacity, which is how muchfunds the channel can handle. A PCN can concatenate several channels, i.e.
different capacities, that need to harmoniously work together. The consequenceis that inner channels in a path have its capacity exhausted forming bottlenecks
in the whole route.
Stability of the route.
The current techniques for channel constructions very often rely on the assumption that the users of the channel, and therefore of a PCN, will be online during
all the lifespan of the channel. This is crucial in the case a Dispute Phase, as
described in Section 2.3.2, when the parties need to act timely. Failing to claim
the correct state of the channel, lead to the honest user to lose funds.
Privacy and anonymity.
Intermediate nodes within a payment route, in principle, watch all the flow oftransactions, since they are intermediating all the payments. Moreover, whenenabling a payment path through, for example routing, information may beleaked about the payer and the payee.

2.5.2

Constructions

For each of the technical challenges detailed earlier, we now detail and discuss
the existing approaches in the literature.
Routing.
Here the challenges are similar to computer networks, however there are important differences due to the payment network nature. For one, routing should be
scalable, i.e. both the stored state per node as well as communication complexity when routing should be logarithmic on the number of nodes. Moreover, theamount of funds that can be routed through a path depends on the capacity of
the channel with the lowest capacity on the path. Furthermore, nodes withina path can be either controlled by a malicious adversary or spontaneously go
offline. Also the network should be able to handle multiple concurrent routing
attempts and payments. In addition to all these challenges intermediate routes
that participate in forwarding a payment can ask for a fee and therefore nodes
need to consider this and might want to optimize for a reduction of payment
fees. Nevertheless, we note that as a fallback nodes can always create a new payment channel between payer and payee, however, this counteracts the scalability
efforts of offchain payment networks so most approaches attempt to accomplish
routing without relying on the fallback method.

2.5. NETWORK MANAGEMENT LEVEL

29

Approaches for routing. A common limitation for long payment channels
is that the intermediate nodes need to be online during the transaction period.
Therefore, often routing algorithms rely on landmark routing techniques [127],
where a landmark, i.e. a node with extra guarantees regarding its connectivity.
Briefly, there are two ways to approach routing in these networks: throughlandmarks, and embeddings. In landmark routing all nodes know the route toa set of landmarks. In such a protocol payments are, first, routed from thepayer to a landmark and, second, routed from the landmark to the payee. Thisapproach promotes centralization of payment channel networks. Nodes close toa landmark would have the advantage of being better connected and might needto pay less fees for routing as well as have a better routing success rate. They
also might get more income through fees because payments would more often
be routed through them compared to nodes far off from landmarks. Anotherapproach is routing using embeddings, where nodes, among themselves decide,on an address space of the network and, then they can find routes using theseaddresses. This approach enables more decentralization however it requires
more communication for maintaining routing tables.
SilentWhispers Protocol [85] proposes using landmark routing, where alllandmarks are publicly known and semi-honest. All routing is done throughthese landmarks by computing the shortest routes. This is done in epochs suchthat node’s routing tables can update to changes within the network. The
work [85] also defines privacy notions for credit networks and provides security
proofs of their construction in the UC framework. The work also proposes multiple extensions. One of these allows for malicious landmarks whereas the otherextension proposes routing through nodes that are offline. In the latter casenodes create secret shares of their long-term private keys and distribute those
across the landmarks who can then impersonate offline parties, however, thisrequires that at least one landmark is honest and does not try to reconstruct
long-term private keys of which it holds secret shares. The author’s of [85]evaluate their work using Ripple’s [8] payment network topology from 2013 and2016 [11]. They compare success ratio, path length of payments and message
complexity between their approach, a protocol based on the Ford-Fulkerson
max-flow algorithm [55], and SilentWhispers [85] among others. They show
a better success ratio as well as smaller paths in average compared to SilentWhispers, albeit a lower success ratio than the one based on [55] which had an
unfeasible message complexity.
Similarly, the SpeedyMurmurs routing protocol [118] is an embedding based
routing protocol, for path-based transaction networks based on the work in [117].
In [118] some nodes are designated landmarks, and are used as roots of respective
spanning trees are computed to create an address space within the network. A
route can be computed using a distance function on nodes’ addresses to findthe next hop on route to the target. In comparison, LN/HTLC [112] relies
on a gossip protocol for channel maintenance and recovery 7 and onion style
7A
description can be foundrfc/blob/master/07-routing-gossip.md

inhttps://github.com/lightningnetwork/lightning-

30

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

routing for privacy 8 . However, it is not clear how nodes can find routes, and an
attempt to tackle this is the routing proposal algorithm for LN: Flare [113]. The
protocol in [113] is probabilistic, and proceeds in two ways: (1) each node stores
the topology of its neighborhood, (2) each node chooses a set of beacon nodes
globally and at random according to a uniform distribution. Routing between
two nodes is done by first checking both peers neighborhoods for intersections,and if this does not work checking whether a beacon node is within the otherpeers neighborhood. The nodes continue by using the neighborhoods of a few
beacon nodes when searching for mutually known nodes to route through.
Hoenisch and Weber [64] pioneered the adaption of techniques from Mobile
Ad Hoc Networks (MANET), by compiling a list of requirements for off-chain
channel networks. An interesting feature of their adapted protocol, named OnDemand Distance Vector (AODV), is that it takes into account the balance andfees of intermediate nodes, a feature not present in MANET but highly relevant
given that these values can change arbitrarily and without coordination in theLayer-2 scenario.
Splitting payments. Routing success does not only rely on whether a routecan be found or not, but also whether the route has enough capacity for thepayment to be executed through it. Large payments have low routing successrates 9 . Approaches to tackle this issue aim to split payments through multiple routes as AMP [104] that provides a protocol to split a payment acrossmultiple paths, Moreover [104] also considers privacy as well as sender/receiveranonymity. The Split Payment Protocol [111] tackles similar problem as in [104],
however [111] allows for payments to complete only partially. Another approachis the Spider Network [120] which employs packet-based routing including congestion control to do payments through multiple paths. Each payment is split-up
into smaller packets which can be routed through separate routes and claimed
atomically by the sender as proposed in [104] or non-atomically. Nodes involved
in routing payments can employ congestion control techniques when multiple
payments are routed concurrently. Channel capacities and possible imbalances
are considered when selecting paths for packages.
The work in [120] compares the success ratio of routing using an approachbased on [55] as well as SpeedyMurmurs [118] and SilentWhispers [85]. Theyevaluated these approaches using network topologies existing in the Internet as
found in [76], and Ripple’s [8] payment network topology from 2013 [11] which
has also been used for the work on SpeedyMurmurs [118], showing that theapproach proposed in the paper works better on the former topologies than thelatter ones where they are outperformed by the algorithm from [55]. Noteworthy
is that they report significantly lower success ratios for SpeedyMurmur thanhave been reported in their paper [118]. Moreover, Speedy Murmurs does notconsider privacy notions or malicious adversaries.
8A
description can be found in https://github.com/lightningnetwork/lightningrfc/blob/master/04-onion-routing.md
9 Reported in https://diar.co/volume-2-issue-25/ and https://thenextweb.com/hardfork/2018/06/26/lighting-network-transactions/2.5. NETWORK MANAGEMENT LEVEL

31

Channel Re-balancing.
Given the limited capacity of a channel, it may be necessary to rebalance a set ofpayment channel to avoid that the channel turns into a simplex one because of
exhausted capacity. For instance, let Alice and Charlie, Charlie and Bob as well
as Charlie and Alice share a payment channel respectively. Moreover assume
that initially everyone has one coin allocated as their funds for each channel.
Now, if Alice sends one coin to Bob, Bob sends one coin to Charlie and Charlie
sends one coin to Alice, all within their respective channels then we would end
up in a situation where in each channel one party has two coins and the otherhas no coin. In this case we would not be able to repeat this payment without
routing the payments over an intermediate node even though the total funds of
all nodes remain unchanged. In order to circumvent the skewness in funds, the
REVIVE protocol [69] relies on an untrusted third party that creates a blockof transactions rebalancing funds. Each peer will lose money on one or more
payment channels but gain an equal amount on others. After each peer verifies
this on the rebalancing transactions they can apply the changes off-chain.
Channel Stability.
The channel between two nodes assume that both stay online on the durationof the channel. Any misbehaviour of any node, can trigger the response andrespective claim of the partner node, which have to be online in order to performthe dispute phase of the network protocol. An approach to address this is to
assume that the receiver can assign a custodian node, sometimes also referred as
watchtower [18, 19], to watch over their payment channel while they are offline.
Similarly, this is the idea of the PISA [92]. The custodian can dispute malicious
commitments of the other peer while its customer is offline. The custodian getsa fee for the service and has a deposit that gets destroyed when it fails to makea dispute on behalf of its customer. However, the custodian’s customer are notpublic and the custodian can use the same deposit as a safety for all customers.
This leads to the problem that if there are enough customers the custodian
can possibly get more funds by cheating on its customers than it would loseby having its deposit destroyed. Moreover, if the deposit is not destroyed andinstead is payed out to all customers a malicious custodian can create customers
for itself to mitigate the funds lost.
Privacy and Anonymity.
The network management layer may leak crucial pieces of information fromnodes belonging to a route to the origin node of a payment. Malavolta etal. [86] investigate privacy notions on PCN and how to enforce them, and propose routing protocols Fulgor and Rayo [86] that consider concurrent routing
processes and attempt to avoid deadlocks in a sense that at least one payment completes. Unfortunately their privacy notions rely on assumptions thatthe underlying routing protocol does not store the state (capacity) of payment

32

CHAPTER 2. BACKGROUND: OFFCHAIN PROTOCOLS

channels within the network, which if done could be used to circumvent theirattempts for privacy.
Fees and node reputation. Since each node in the network can charge an
arbitrary fee in order to conduct the payment along the path, an interestingquestion to investigate is the game-theory behavior of rational nodes within
the network and other economic questions. In comparison to other works, asseen in previous transactions, these questions seem to be, to this day, largely
understudied. A framework to study network topologies and economic aspects
is given by Brânzei et al. [26]. Similarly, a reputation system, which would takeaccount of fees and success payment rate, seems to be missing in the literature
and are highly relevant for practical systems.

2.6

Final Remarks

We provided a major review, as shown in Table 2.1, of the body of work on
off-chain channels, networks and related protocols for Layer-2 solutions, anemerging area targeting scalability of cryptocurrencies. We believe it provides
a significant value for the community because it contains a wide overview of thelandscape on the ideas and approaches present in the scientific literature andInternet repository and forums. We focused this work on providing a throughout overview of the landscape with emphasis on problems and approaches of theavailable protocols.
We highlight the rich literature on routing protocols, for Network Management Level, in comparison to, for instance, channel Re-Balancing protocols.
That difference can be explained by the similarities of the off-chain channel andcomputer networks, which can be seen as a source of already tested ideas to findroutes.
More recently, we can also note a trend on network construction protocols
for the Network Level, in particular the works on Virtual Channels [46] andCounterfactual [38]. In both cases, they distinguish themselves by providing aricher framework for constructions on the top of off-chain channels. Furthermore, we also highlight that the most established technique, i.e. HTLC, wasrecently fully thoroughly studied [71].
Along the same lines, works on the economic aspects of the channels, i.e.
fees charged by nodes, and reputation of nodes seem also to be underreported
in the literature. In both cases, they are important, because they are critical topave the way of more practical systems. Finally, it is important to emphasisethat this work left out the topic of interoperability of systems, e.g. Cosmo [4],XClaim [135] and Comit [3].

Chapter 3

A Framework for UTxO
Based Offchain Protocols
In this chapter, first we introduce the notation that we use throghout this workin section 3.1 we introduce the UTxO model for blockchains in Section 3.2 before
introducing our framework for UTxO based offchain protocols in Section 3.3.
Lastly we present our security model in Section 3.4.

3.1

Notation

Tuples. Throughout this work we make use of tuples and use short-handnotations as follows. Let (a1 , a2 , . . . , an ) be a definition of a tuple of type A andlet α be an instantiation of A. Then α.ai equals the i-th entry of α.
Sets. Let ∪, ∩ and \ denote set union, intersection, subtraction, and ∅ be theempty set.

3.2

The UTXO Paradigm

In the following we define the model of UTxO based ledgers.
Transaction Outputs. A UTXO is a tuple of the form (b, π) where b ∈ N
is an amount of coins and π ∈ {0, 1}∗ is a script. The b coins of the UTXO
are claimed by providing a witness w ∈ {0, 1}∗ s.t. π(w) = True. The state of
the ledger is represented by a set of UTXO Sutxo , which can be changed by atransaction of the form (Uin , Uout , t) where t ∈ N is the (absolute) timelock
represented as a point in time, Uout is the list of unique UTXO for the outputsof the transaction, and Uin is the set of transaction inputs of the form (ref(u),wu ) where ref(u) is the pointer to the UTXO u, and wu is the witness.
33

34CHAPTER 3. A FRAMEWORK FOR UTXO BASED OFFCHAIN PROTOCOLS
Transactions. A transaction (Uin , Uout , t) needs to fulfill the following conditions. (1) The locktime has passed, i.e. t ≤ τ where τ is the current time,(2) all witnesses are valid, i.e. ∀(ref(u), w) ∈ Uin : u.π(w) = True (3) the coins
within the newly created UTXO are less or equal to those in the transaction’s
inputs, i.e. Σ(ref(u),w)∈Uin u.b ≥ Σu∈Uout u.b, (4) all UTXOs in the transaction’s
inputs exist and have not yet been spent, i.e. ∀(ref(u), w) ∈ Uin : u ∈ Sutxo .
The transaction has the following effect on the ledger. All UTXOs referenced
within Uin are removed from Sutxo and all UTXOs defined in Uout are added to
Sutxo . A transaction T is included in the ledger within a duration ∆ ∈ N. Condition (4) implies that no UTXO can be claimed by two different transactions.
After sending T to the ledger, if within time ∆ another transaction T 0 claiming
a subset of the same UTXOs as T is sent to the ledger, it would result in arace condition, in which it is non-deterministic whether T or T 0 will change theledger’s state. We note that while we use ∆ as a ledger parameter in practicethis value has to be estimated for real-world implementations. Special care has
to be taken when selecting a value. A value that is too low breaks our assumptions and the protocol’s security. A value too high increases the collateral andtherefore the impact of attacks such as congestion and lockdown[99, 109].

Scripting. Scripts in this work specify a UTXOs owner by requiring a signature of the transaction that spends the UTXO with the recipient’s verification
key. This is extended to 2-out-of-2 multisignatures that require verification keysof two parties P and P 0 effectively creating a shared wallet between both parties
that can only be spent with consent of both parties.

Simplified UTXO. Throughout this work we simplify scripts by only stating the set of parties which need to provide their signatures to spend the respective UTXO, i.e. UTXO are tuples (b, Party), where b ∈ N is the amountof coins and Party is a set of parties. UTXOs requiring 2-out-of-2 multisignatures are termed Funding UTXO. An instantiation of a Funding UTXO isF UTXO(x, P0 , P1 ) which is of the form (x, {P0 , P1 }) where x ∈ N and P0 , P1
are parties.

Partial Mappings. In the case of working with functionalities, we abstract
away from transactions and represent them as partial mappings of UTXO ofthe form (In, Out) where In, Out are UTXO that represent the transaction’s
inputs and outputs respectively. Informally a partial mapping consists of two
sets of UTXO representing the inputs and outputs of a transaction. Submitting
a partial mapping to a ledger results in a state change where the UTXO in the
inputs are replaced by the in the outputs. We assume there is a function φ thattakes a mapping (In, Out) and time t and outputs a respective transaction withtimelock t. Analogously φ−1 is a function that takes a transaction and outputs
a mapping and timelock.

3.3. THE FRAMEWORK FOR UTXO LEDGERS

3.3

The Framework for UTxO Ledgers

3.3.1

Offchain Protocols

35

Transaction Graphs. All transactions included in the ledger form a directed
and acyclic graph. The set of all transactions form its vertices. An edge (T0 ,T1 ) from transaction T0 to transaction T1 exists, if T1 ’s inputs contain a pointerto one of T0 ’s outputs, i.e. ∃u : u ∈ T0 .Uout ∧ (ref(u), w) ∈ T1 .Uin . Note thata transaction can only be included in a ledger if all of its ancestors have been
included in the ledger before. In the remainder of this work we reference sets oftransactions that are connected to form a sub-tree as transaction trees.
Channels. A channel γ between two parties consists of sub-protocols setup,
closure and dispute. In setup both parties create a transaction T rf containing
a Funding UTXO between each other which locks their funds into the channel. They create a transaction tree with the Funding UTXO as its ancestor
that represents the channel which we reference in the remainder of this work aschannel-tree. Only after the channel-tree is created and either party holds signatures of its transactions, both parties sign and commit T rf to the ledger while
holding off commitment of transactions within the channel-tree. Both parties
can perform closure of the channel by committing a transaction to the ledger
that spends the Funding UTXO unlocking the channel’s funds according to its
most recent state. In case of a dispute, the dispute sub-protocol enforces thechannel’s state by committing the channel-tree’s transactions onto the ledger.
Offchain Protocols perform a state transition of a channel by transforming
its channel-tree. Any honest party must be able to enforce the new channel’s
state which might require an explicit invalidation step that disables commitmentof an older version of the channel-tree or allows for punishment of a party that
does so. An efficiency requirement of offchain protocols is that performing themn ∈ N times grows the channel-tree by at most O(1) transactions.

3.3.2

Operations on Transaction Trees

Updating a Transaction Tree. Timelocks can be used to define at which
point a transaction can be committed to the ledger. Assume there are twotransactions that spend the same UTXO, but which have timelocks that are 1)
in the future and 2) have a difference of at least ∆. In this case parties canenforce commitment of the transaction with the lower timelock to the ledger.
The transaction with the lower timelock invalidates the transaction with thehigher timelock.
Constructing Transaction Trees Atomically. We observe that committing a transaction to the ledger requires that all of its ancestors are committed
to the ledger beforehand. For a transaction to be able to be committed to theledger it needs to contain all required witnesses, i.e. signatures. Therefore,

36CHAPTER 3. A FRAMEWORK FOR UTXO BASED OFFCHAIN PROTOCOLS
we can atomically create a transaction tree rooted in a transaction trroot thatis common ancestor to all other transactions. First, we add signatures to alltransactions except trroot . Afterwards, adding signatures to trroot makes thewhole transaction tree committable to the ledger at the same moment.
Constructing Transaction Trees Atomically Across Two Channels.
We assume two transactions, tr0 and tr1 , that require signatures of Alice andBob, as well as Bob and Charlie respectively. Bob can enforce that both transactions are created atomically by only providing his signature after he received
signatures from Alice and Charlie. We note that techniques (1) and (2) can beused in tandem.

3.4

The Security Model

Communication Model. We assume synchronous communication where timeis split into communication rounds. If any party sends a message to a receiving
party within a round, the message reaches the receiving party at the beginningof the following communication round. The duration of any round has an upper
limit.
Indistinguishability. Let negl(n) denote the negligible function. The standard definition for computational indistinguishability X ≈c Y is that there is
no PPT algorithm D such that D can distinguish between two ensembles ofprobabilistic distributions X = {Xn }n∈N and Y = {Yn }n∈N , in other words
Pr[D(Xn , 1n ) = 1] − Pr[D(Yn , 1n ) = 1]| ≤ negl(n).

3.4.1

The Adversarial and Computational Model

We model the execution of our protocol π via the Universal Composability(UC) Framework with Global Setup by Canetti et al. [31] where all the entities are PPT Interactive Turing Machines (ITM), and the global setup is givenby the global functionality G, and the execution is controlled by the environment Z. In this simulation based model, all parties from π have access tothe auxiliary functionality Faux , i.e. π Faux , in the hybrid world execution
HYBRIDπFaux ,A,Z in the presence of the adversary A which can see and delay the messages within a communication round. Whereas the ideal execution,i.e. IDEALF ,S,Z , is composed by the functionality F in the presence of thesimulator S. In both executions, the environment Z access the global functionality G. Given the randomness r and input z, the environment Z drives
both executions IDEALF ,S,Z and HYBRIDπFaux ,A,Z , and output either 1 or 0.
Therefore, let IDEALF ,S,Z and HYBRIDπFaux ,A,Z be respectively the ensembles{IDEALF ,S,Z (n, z, r)}n∈N,z∈{0,1}∗ and {HYBRIDπFaux ,A,Z (n, z, r)}n∈N,z∈{0,1}∗ ofthe outputs of Z for both executions. Thus, we say that π Faux realizes F in theFaux -Hybrid model when, there exist a PPT simulator S, such that for all PPTZ, we have IDEALF ,S,Z ≈c HYBRIDπFaux ,A,Z .

3.4. THE SECURITY MODEL

37

Corruption. Assuming a protocol is executed between a set of n ∈ N mutually
distinct parties. At the beginning of protocol execution, the adversary canstatically corrupt up to n − 1 of n parties, receiving their internal state andhaving all communication to and from these parties be routed through theadversary. The adversary is malicious and can make any corrupted party deviate
from a protocol.

38CHAPTER 3. A FRAMEWORK FOR UTXO BASED OFFCHAIN PROTOCOLSChapter 4

Lightweight Virtual
Payment Channels
4.1

Introduction

Blockchains implement decentralized ledgers via consensus protocols run bymutually distrustful parties. Despite the novelty of such design, it has inherent limitations, for example, effectively all transactions committed to the ledger
have to be validated by all parties. Croman et al. [39] showed that this severely
limits a blockchain’s throughput. Moreover, there is a minimal delay between
submission of a transaction and verification thereof that is intrinsic to the system’s security, e.g. one hour in the case of Bitcoin.
Layer-2 protocols, such as payment channel networks, allow confirmation oftransactions outside the consensus protocol while using it as fallback. These
protocols are referred as “off-chain” protocols in contrast to processing transactions via the consensus protocol “on-chain”. An elementary protocol realizes
channels and commonly works as follows: Two (or more) parties put together
their funds and lock them on-chain by requiring a 2-out-of-2 (n-out-of-n) multisignature to claim them. Then these funds are spent by another transaction
or a tree of transactions. These transactions represent the distribution of funds
between both parties and are not committed to the blockchain except when parties enforce the fund distribution on-chain and unlock the funds. The parties
can perform a payment, i.e. update the balance distribution within the channel,
by recomputing that tree of transactions while invalidating previous transaction
trees. Payments between parties are processed immediately and only involve interaction between the two parties. Channels can be extended to form channel
networks by using Hashed Time Lock Contracts (HTLC) [44, 112]. Payments
are performed by finding a path from payer to payee within the network andatomically replicating the payment on each channel along that path. A drawback of HTLCs is that a payment requires interaction with all intermediarynodes within a path. Virtual State Channels as proposed by Dziembowski et al.
39

40

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS[46, 49] devise a technique for creation of channels that allow execution of statemachines instead of being limited to payments, and use an off-chain protocolthat expands the network with new channels. The latter reduces the network’s
diameter yielding shorter payment paths, and allowing parties to perform payments without interacting with any intermediary nodes if they are adjacent in
the now extended network. However, this construction requires blockchain withsmart-contract capability, therefore not applicable to Bitcoin. Later we will seethat this work addresses this limitation with a novel construction.
Use cases for virtual channels are manifold. A virtual payment channel
provides the same benefits to the two parties sharing one as pairwise payment
channels without the need to set it up by committing transactions to the ledger
that can incur expensive fees. Payments can be executed offchain, without
interaction with a third party and without incurring any fees, e.g. for routing
an HTLC, making rapid micro-payments viable. This could enable new services
such as a service-gateway. Such a gateway would consist of a node that sets
up payment channels with different service provider that operate using microtransactions, e.g. Video on Demand (VoD) services that bill by watch-time. A
user could then create one payment channel with the gateway node and withthe use of virtual channels created ad-hoc connections to the different (VoD)
services instead of having to set up individual payment channels with eachservice they want to use. A more general use case is that virtual channels allow
payment hubs, that have a high degree within a payment channel network, tointerconnect their individual partners in exchange for a fee.
Related Work. HTLCs allow atomic payments across multiple hops. This isdone by performing a conditional payment in each channel along a path frompayer to payee. Executing a payment requires revealing a secret x ∈ N suchthat H(x) = y where H is a cryptographic hash function. After setup, startingfrom the payee each node within the payment path reveals x to its predecessor.
This proofs that the payment can be enforced on-chain which allows parties toresolve the payment by performing it off-chain. A timelock is used to cancel
the transaction after a preset amount of time which unlocks the funds from theconditional payment. Although our construction can be used to enable payments
across a payment channel network by creating a virtual channel between payer
and payee, we argue that our work is orthogonal to HTLCs and both techniques
can be used in tandem. First our construction is used to expand the underlying
payment channel network with additional virtual channels and then HTLCs canbe used to perform payments across this expanded infrastructure.
Dziembowski et al. introduced Virtual State Channels [46] and State Channel Networks [49]. A state channel depends on a smart contract previously
committed to the blockchain. It contains (1) application specific code, and (2)code for state channel management. More specifically parties can send messages to the smart contract changing its state according to (1), or compute astate-transition message where the resulting state is computed by the parties
and summarized in the state-transition message for (2). The state-transition

4.1. INTRODUCTION

41

message can be kept off-chain, and only committed to the blockchain in caseof parties’ dispute. A virtual state channel can be built on top of two channels that were previously created in this manner. Similar to our work, virtualchannels cannot be open indefinitely but have a fixed lifetime that is decided
upon construction. In contrast to our work this technique requires a blockchain
with smart-contract capability. Chakravarty et al. proposed Enhanced Unspent
Transaction Outputs (EUTxO) [32] and constructed the Hydra Protocol [33].
EUTxO enables running constraint emitting state machines on top of a ledger
which is used to setup a Hydra heads among a set of parties. This allows them totake their funds off-chain and confirm transactions with these funds among theparticipants of the Hydra head. Although parties can interact with each otherusing arbitrary transactions as they would on-chain, no new participants canbe added to the Hydra head which is in contrast to payment channel networks.
Moreover implementing Hydra requires blockchains with EUTxO capability limiting its applicability.

Our Contributions. This work proposes a new variant of Virtual Channels,
we name it Lightweight Virtual Payment Channels, that is based on UTXO
and requires only multisignatures and timelocks, that is, it does not require
smart-contracts, yielding the first virtual channel construction implementableon blockchains such as Bitcoin, which currently has the highest market capitalization of all cryptocurrencies 1 and still is the most widely used, and blockchainsoperating with the recently introduced EUTxO [32] effectively improving thestate of the art in both cases.
In a nutshell, our Layer-2 protocol for Virtual Payment Channels takes two
payment channels between three parties as input, and opens three payment
channels, i.e. one for each pair of parties. Our protocol can be applied iteratively allowing for virtual payment channels across multiple hops of the underlying payment channel network. Our construction (1) can be used to expand apayment channel network with virtual payment channels, (2) allows payments
without interaction with intermediary nodes if payer and payee share a virtual
payment channel, (3) can be used in tandem with HTLCs and (4) can be usedwith different payment channel implementations as Duplex Payment Channel[44], Lightning [112], Eltoo [108]. We formalize our work in Canetti’s Universal Composability (UC) Framework [29] by introducing a functionality forlightweight virtual payment channels FLVPC,FPWCH . Although formalizations forledgers, including Bitcoin, within the UC framework exist [49, 46] we present
the first global functionality GUTXO−Ledger for an Unspent Transaction Output(UTXO) based ledger. Moreover we present an auxilliary functionality FScript
modeling a scripting language modelling access to timelocks and multisignatures. Our construction makes use of GCLOCK by Katz et al. [68], modified by
Kiayias et al. [74, 72] and FSIG by Canetti et al. [30]. We present pseudo-code
protocols Open VC, Close VC and Enforce VC.
1 https://coinmarketcap.com

42

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

Structure of this Work. In the remainder of this work, first, we briefly
introduce notation and the model used in this work in Section ??. Next weformalize a UTXO based ledger and their components in Section ?? and review pairwise payment channel in Section 4.2. Afterwards we give a high-leveldescription and analysis of our approach in Section 4.3 before presenting pseudocode protocols in Section 4.4. Following this we formalize our approach in the
UC framework by, first, introducing auxiliary functionalities in Section 4.5.4,
then the pairwise payment channel functionality FPWCH in Section 4.6.3 andthe virtual channel functionality FLVPC,FPWCH in Section 4.7. Next we introduce
formal protocols implementing FPWCH and FLVPC,FPWCH namely protocols PWCH
and LVPCvPWCH in Section 4.8.3 and Section 4.9 respectively. We provide simulation based proofs that the protocols implement the respective functionalities
in Section 4.10. Lastly we discuss directions for future work in Section 4.11.

4.2

Pairwise Payment Channel

A pairwise payment channel allows two parties to exchange funds without committing a transaction to the ledger for the individual payments. Such a channel
is setup by having parties commit a transaction on the ledger that collects someof each party’s UTXO and spends all of it within a Funding UTXO. Committing
this transaction on the ledger locks these funds. The Funding UTXO is spent
by a transaction subtree representing the channel’s state where committing itto the ledger unlocks and returns all of the parties’ funds, however, instead,the parties hold off committing them. When executing a payment, they update the transaction subtree to represent the new state while invalidating theprevious subtree. Invalidation can be done by spending the Funding UTXO
with a transaction that has a timelock of at least ∆ less than the previous subtree. We remark that alternative invalidation methods do exist [44, 108, 112].
The channel is closed by committing the transaction subtree or a transaction
summarizing it onto the ledger.

4.2.1

Types of Transactions

We design our construction to be agnostic of the underlying pairwise payment
channel construction, however, for the sake of having a complete formal treatment we formalize a simple pairwise payment channel construction based ontimelocks. This construction consists of two types of transactions called Funding and Refund transactions.
Funding. A Funding transaction is parametrized with (x, P0 , P1 ) where x ∈ N
is an amount of coins and P0 , P1 are parties where P0 6= P1 . It is an arbitrary
valid transaction Tr for which holds that there exists a Funding UTXO f out ∈Tr.Out parametrized with (x, P0 , P1 ) and its timelock is 0.

4.3. OVERVIEW OF THE CONSTRUCTION
Funding
Alice : X
Bob : Y0

Alice
& Bob :

X+Y

RefundFundingt

Alice: X − δ
Bob : Y + δ(a) Simple Payment Channel.

43

Alice : X

0

Bob : YAlice
& Bob :

X+Y

ChannelAlice : X − δ
Bob : Y + δ(b) Abstract representation.

Figure 4.1: Figure 4.1a depicts a possible implementation of a simple pairwise
payment channel whereas Figure 4.1b depicts an implementation independent
abstraction.

Refund. A Refund transaction is parametrized with (ref, tr , xr , yr ) where
ref is a reference to a Funding UTXO f out = F UTXO(xf , P0 , P1 ), tr ∈ N is apoint in time, and xr , yr ∈ N are amounts of coins. It is a transaction Tr of form({ref}, Out, tr ) where Out = {(x, f out.P0 ), (y, P1 )}, xf ≥ x + y. In the following
we denote a Refund transaction with these parameters with REFUND TR(f out,
tr , xr , yr ) and an analogous mapping with REFUND MAP(f out, xr , yr ).

4.2.2

Pairwise Payment Channel

The implementation of a timelock-based pairwise payment channel is depicted
in Figure 4.1a. It consists of a Funding transaction that locks both parties funds
into the channel as well as a Refund transaction that holds the current state,i.e. fund distribution, of the channel. Two parties who want to create sucha channel proceed as follows. (1) Create and exchange Funding and Refund
transactions, (2) sign and exchange signatures of Refund transaction, (3) signand commit Funding transaction to the blockchain.
As soon as the Funding transaction is included in the blockchain, a payment
can be done by creating a copy of the Refund transaction with a new balance
distribution, a timelock that is smaller by at least ∆ to the previous Refund
transaction’s timelock, but higher than the current time, and exchanging signatures for it. The channel is closed by either party by committing the latest
refund transaction to the blockchain at expiration of its timelock. Alternativelya channel can be closed by creating a Refund transaction with a timelock of 0
and committing it to the blockchain.

4.3

Overview of the Construction

The construction consists of three protocols, Open VC, Close VC and Enforce VC
used for setup, tear-down and dispute of virtual channels respectively. We remark that the executions of Open VC and Close VC require consent between
all involved parties, and Enforce VC can be executed by a party unilaterally.

44

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
Merge

Split

Punisht+Δt

Alice & Bob :
X−Y
Alice
& Bob : X Alice & Bob :Y

Alice & Bob :Y

Bob & Charlie :Y

Alice & Charlie :Y

Bob : Yt + 2ΔAlice& Bob :Y

Alice:Y

Figure 4.2: Illustrations of transactions used through out this work represented
as nodes of a transaction graph. A transaction’s inputs are listed on the lefthand-side whereas a transaction’s outputs are on the right-hand-side. The value
on top represents the transaction’s timelock.
Types of Transactions. We use three types of transactions, they are are
Split, Merge and Punish transactions as illustrated in Figure 4.2. A Split transaction spends a Funding UTXO and creates two new Funding UTXO between
the same pair of parties. A Merge transaction takes two Funding UTXO between three parties and equal balance as input, and creates two UTXO with thesame amount of funds as the inputs each. One is a Funding UTXO between thetwo parties that do not share a Funding UTXO within the inputs, and one is a
UTXO that gives funds to the third party. Lastly the Punish transaction takes
a Funding UTXO as input and creates an UTXO that gives it all to one of theparties.
Assumptions. Timelocks are used to invalidate transactions. That is, atransaction invalidates another one if it spends the same UTXO within its inputs, but has a timelock that is lower by at least ∆. We assume that the original
payment channel between Alice and Bob has a timelock of at least t0 + ∆, andthe one between Bob and Charlie has a timelock of at least t1 + ∆. After teardown of our construction the timelocks of both channels will be t0 −∆ and t1 −∆respectively. We note that this does not make the construction incompatible
with pairwise payment channel constructions that do not rely on timelocks fortransaction invalidation, such as lightning network style channels. Such channels can perform a state updates using their invalidation method that introduce
a timelock before construction, and remove the timelock after tear-down.
Malicious Behavior. Parties abort protocols Open VC and Close VC when
they observe another party deviating from the protocol, or if a party delays execution until expiration of the virtual channel, i.e. t0 − ∆ and t1 − ∆ respectively.

4.3.1

Intuition of the Protocols

Open VC takes an amount of coins δ ∈ N and two pairwise payment channel
between three parties as input and creates three new pairwise payment channels,
one between each pair of parties. In the following we assume the parties are
Alice, Bob and Charlie with payment channels between Alice and Bob, andbetween Bob and Charlie. Our construction creates a set of transactions as4.3. OVERVIEW OF THE CONSTRUCTION

45

illustrated in Figure 4.3. In a nutshell, the purpose of the construction is to allow
parties to enforce payout of all of their funds distributed among the offchain
channels, while providing fall-back security of their funds in case all other parties
misbehave.
First, two Split transactions are created, each spending one of the Funding UTXO that are spent by the original pairwise payment channels. Theirtimelocks are t0 and t1 respectively s.t. they invalidate the original payment
channels. One of the UTXO of each Split transaction contains δ coins and isused as input into a Merge transaction. The other UTXO of each Split transaction is used as Funding UTXO to re-create the original payment channels, albeit
each party has δ/2 coins less in these channels. The Merge transaction takes theUTXO with δ coins as input, creates a Funding UTXO for a channel between
Alice and Charlie where each possess initially δ/2 coins, and another UTXO
gives δ coins to only Bob which represents his collateral. Lastly, two Punishtransactions spend the same UTXO as the Merge transaction but give all coins
to Alice and Charlie respectively. They have a timelock of max(t0 , t1 ) + 2∆ suchthat they are invalidated by the Merge transaction.

Close VC takes a virtual channel construction as input and closes them whilesetting up the original pairwise payment channel but with a balance distribution reflecting the balances in the three payment channel built on-top of theconstruction. Effectively Alice pays Bob the funds she owes Charlie while Bob
forwards these funds to Charlie - and vice versa. The channels have timelocks
t0 − ∆ and t1 − ∆ respectively to invalidate the Split transactions. Note thata virtual channel construction can only be closed until time min(t0 , t1 ) − ∆ asotherwise the newly constructed payment channels cannot invalidate the Split
transactions. Note that having Bob take out δ/2 coins out of both of his original
channels within the construction ensures that no party has a negative balance
within a pairwise payment channel upon tear-down.

Enforce VC lets a party enforce the current state by having it commit atransaction to the blockchain as soon as its timelock expires.

Atomic Construction. We require that all transactions within our construction are created and respectively invalidated atomically. This is enforced by theorder in which transactions are signed. First, parties have to exchange signatures for all transactions except of those spending the original Funding UTXO,
i.e. the Split transactions in Open VC and the root of the pairwise payment
channel sub-trees in Close VC. Afterwards, Alice and Charlie sign these remaining transactions and send the signatures to Bob. Lastly Bob signs them andsends his signatures to Alice and Charlie. Only if a party holds all signatures for
all transactions it is involved in, it will consent in performing payments. This
ensures security as we will discuss in the following.

46

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
Channel Alice & Bob
Split
Funding UTXO
Alice& Bob :XA + YAt0

Alice & Bob :(XA + YA) − δ
Alice & Bob :δPunish𝗆𝖺𝗑(t0, t1)+2Δ
Merge

𝗆𝖺𝗑(t0, t1)+Δ
Bob : δFunding UTXO
Bob
& Charlie :XB + YB

Channel Alice & Charlie
Alice : δ/2 − δA,C

Charlie : δ/2 + δA,C

Punisht1

𝗆𝖺𝗑(t0, t1)+2Δ

δCharlie: δ

Bob & Charlie:

Bob : (XA + YA) − δ/2 + δA,B

Alice: δAlice & Charlie : δ

Split

Alice : (XA + YA) − δ/2 − δA,B

Bob & Charlie:(XB + YB) − δ

Channel Bob & Charlie
Bob : (XB + YB) − δ/2 − δB,C

Charlie : (XB + YB) − δ/2 + δB,C

Figure 4.3: Overview of the virtual channel construction as a transaction tree.
On the left-hand side are Funding UTXO either on the ledger or within previous
virtual channels. Boxes with round corners represent the transactions of ourconstruction while the boxes on the right-hand side abbreviate pairwise payment
channel’s transaction sub-trees. We omit stating inputs explicitly as they areclear from context.

Only Alice is honest. (1) As Bob is the last one to sign, he might interrupt
the protocol before Alice receives a signature for the Split transaction. In thiscase Alice will not consent to any payments and the construction does not change
her total balance. Alice can receive her funds by waiting for expiration of her
original payment channel’s timelock or commitment of the Split transaction by
Bob. (2) Bob and Charlie can collude and spend the Funding UTXO that isreferenced by their Split transaction. As such the whole transaction sub-treewith the Split transaction as root cannot be committed to the ledger, including
the Merge transaction. In that case Alice can commit the Split transaction,and subsequently the Punish transaction. Alice will receive δ coins which is the
maximum amount of coins she can receive within her pairwise payment channel
with Charlie, as such she does not lose coins. Note that Alice’s channel with Bob
is unaffected as it is not within the sub-tree that Bob and Charlie invalidated.

4.3.2

Discussion of Attack Scenarios

Only Bob is honest. (1) As Bob is the last to sign transactions, he can assure either both Split transactions are fully signed and they can be committed
to the ledger, or none. Moreover he can assure that either both Split transactions will be invalidated upon lockdown or none. (2) Spending the Funding
UTXO referenced by the Split transactions always require Bob’s consent by requiring a signature such that Alice and Charlie cannot invalidate any part of4.3. OVERVIEW OF THE CONSTRUCTION47

the construction’s transaction sub-tree, making Bob to pay out his collateral
via a Punish transaction.
Iterative Construction. The pairwise payment channels used as input caneither have a Funding UTXO located on a ledger, or a Funding UTXO createdby a previous virtual channel construction. In that case timelocks have to bechosen such that within its transaction sub-tree any transaction has a timelock
larger than its predecessor’s timelock by at least ∆ in order to ensure there issufficient time to commit them to the ledger. Moreover virtual channel constructions have to be torn-down in reverse order in which they were setup. Iterative
constructions requires further analysis of security. The key part to make iterative construction work is the design of the Punish transactions as they secure aparty’s funds, including potential collateral payments, while not over-punishinga potentially honest intermediary party: The punishment amount cannot exceed
a party’s collateral. Assume the channel between Bob and Charlie is createdusing a virtual channel construction with channels between Bob and Ingrid andbetween Ingrid and Charlie. In that case Ingrid and Charlie can collude byspending their Funding UTXO invalidating the Split transaction between Bob
and Charlie making Bob have to pay coins within the Punish transaction between him and Alice. However, these funds as well as the funds Bob has inhis channel between him and Charlie are covered by a Punish transaction hehas between him and Charlie. Indeed this is the reason why the same amountof coins δ has to be paid into the Merge transaction from both of its Funding
UTXO and only those coins are covered by the Punish transaction. This ensuresthat all funds are covered while not over-punishing the intermediary party incase of iterative virtual channel construction.
Mitigating Wormhole attacks. Malavolta et al. [89] showed an attack inwhich two colluding parties skip intermediary parties within a HTLC payment
within a payment channel network (1) withholding fees that would have been
paid to the intermediary parties and (2) obtaining the fees themselves instead.
A variant of this attack could be applied to our construction as we do not requireparties to verify that all pairwise payment channel but the ones they participate in were validly constructed. We discuss how to mitigate possible attacks.
Although detailed discussion about payout of fees is beyond the scope of thiswork, we suggest that fees are paid to the intermediary party as compensation
for locking up collateral. We note that due to this attacker cannot obtain more
fees than they are owed (2). However, attackers could still collude to withhold fees of intermediary parties (1). A mitigation to this attack is that parties
would need to proof that such a payment channel was previously constructed,
but showing the Funding UTXO that were used and are located on the ledger
as well as the whole transaction subtree originating those. A party that receives
this information can do a sanity check and store the sub-tree in case they haveto do the same proof. This poof serves to show that fees have been paid to theintermediate parties, however, we note that the information might be out-of-

48

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

date as malicious parties can close their pairwise channel effectively invalidating
the whole subtrees.

4.4

Protocols

Here we informally introduce the constructions for Open VC, Close VC andEnforce VC for setup, tear-down and dispute protocols of virtual channels. To
help intuition these are heavily simplified but derived from the formal protocol LVPCPWCH in Section 4.9 that implements Functionality FLVPC,FPWCH from
Section 4.7.
In the following protocols we assume that: When executing any protocol all
involved honest parties check that execution with the given parameters is permissible, i.e. it will not result in transactions with negative balances, timelocks
in the past and that the pairwise payment channel in Open VC or the virtualchannel in Close VC are not currently in use with another virtual channel construction. Moreover, for protocols Open VC and Close VC they check that all
parties consent execution. Lastly, they abort execution if they observe a party
deviating from the protocol including when their signatures fail verification orwhen execution times-out. For details we refer to Functionality FLVPC,FPWCH .

4.4.1

Types of Transaction

Before introducing the protocols, first we define the individual types of transactions used in our construction as well as pairwise payment channel and virtual
payment channel.
Punish. A Punish transaction takes a Funding UTXO as input but gives all
funds to one party. It is parametrized with (ref, P, tp ) where ref is a reference
to a Funding UTXO f out, P ∈ f out.Party is a party and tp ∈ N is a roundnumber. It is of form ({ref}, {out}, tp ) where out = (f out.b, P). In the following
we denote a Punish transaction with these parameter by PUNISH TR(f out, P,
tp ), and an analogous mapping by PUNISH MAP(f out, P).
Split. A Split transaction takes a Funding UTXO as input and splits funds
across two funding UTXO. It is parametrized with (ref, δ, tS ) where ref is areference to a Funding UTXO f out, δ ∈ N, δ ≤ f out.b is a balance and tS ∈ N isa point in time. It is of form ({ref}, {outch , outδ }, tS ) where outch = (f out.b −δ, f out.Party) and outδ = (δ, f out.Party). In the following we denote a Split
transaction with these parameter by SPLIT TR(f out, δ, tS ) and an analogous
mapping by SPLIT MAP(f out, δ). The routines OUT CH and OUT DELTA takeeither a Split transaction or analogous mapping as input and return outch andoutδ respectively.
Merge. A Merge transaction takes two funding UTXO by three parties andcreates a new Funding UTXO. It is parametrized with (tM , f outA , f outB , b)

4.5. THE UC SETTING

49

where tM ∈ N is a round number, f outA , f outB are two Funding UTXO andb ∈ N, b = f outA .b = f outA .b is an amount of coins. Moreover for the involved
parties PA , PB , PC holds PA , PB ∈ f outA .Party, PB , PC ∈ f outB .Party. Given,outch = (b, {PA , PC }) and outB = (b, {PB }), then a Merge transaction is of
the form ({ref(f outA ), ref(f outB )}, {outch , outB }, tM ). We denote a Mergetransaction with these parameter by MERGE TR(f outA , f outB , b, tM ) and ananalogous mapping by MERGE MAP(f outA , f outB , b). The routine OUT CH
takes a Merge transaction or analogous mapping as input and returns outch .

4.4.2

Definitions

Function open virtual(f, P, P 0 , b, b0 , t) is used to open a pairwise payment channel
with the provided, Funding UTXO f , between the two parties P, P 0 , respectivebalance distribution b, b0 and optional timelock t. See Section 4.6.3 and Section
4.8.3 for details.
Definition 4.4.1. A pairwise payment channel γ is a tuple of form γ = (id,f , PA , PB , bA , bB , t, t0 ) where id ∈ N is a unique identifier, f is a funding
UTXO, PA , PB are parties, bA , bB ∈ N are balances of PA , PB respectively.
Definition 4.4.2. A lightweight virtual payment channel γ v is a tuple of form
(id, γ0 , γ1 , γA,B , γB,C , γA,C , PA , PB , PC , δ, t) where PA , PB , PC are threeparties, γ0 , γ1 are pairwise payment channel between PA , PB and PB , PC respectively provided as inputs, γA,B , γB,C , γA,C are pairwise payment channel
created by the construction between each pair of parties, δ is the capacity of channel γA,C between PA , PC and t ∈ N is a point in time until which the channel
can be closed.
For simplicity we omit stating id explicitly.

4.4.3

Protocols

We present opening of a virtual channel in Figure 4.4 and closure of a virtualchannel in Figure 4.5. A protocol for resolving dispute is presented in Figure
4.6.

4.5

The UC Setting

While focusing on the intuition and readability of our approach up until thispoint, the remainder of this work is about formal treatment of our protocol in
the UC framework including, potentially harder to read, but necessary detail.
First we give an overview of the setting followed by introduction of all auxiliary functionalities used throughout this work. We follow up by detailing the
pairwise payment channel functionality FPWCH the lightweight virtual channel
functionality FLVPC in the following sections.

50

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

Algorithm 1 Open Virtual Channel
1: function Open VC(γ0 , γ1 , δ)2:
tr0,S ← SPLIT TR(γ0 .f , δ, γ0 .t − ∆)3:
tr1,S ← SPLIT TR(γ1 .f , δ, γ1 .t − ∆)4:
tr0,p ← PUNISH TR(OUT DELTA(tr0,S ), PA , max(γ0 .t, γ1 .t) + ∆)5:
tr1,p ← PUNISH TR(OUT DELTA(tr1,S ), PC , max(γ0 .t, γ1 .t) + ∆)6:
trmrg ← MERGE TR(OUT DELTA(tr0,S ), OUT DELTA(tr0,S ), δ,max(γ0 .t, γ1 .t))7:
(γA,B , trroot,A,B ) ← open virtual(OUT CH(tr0,S ), PA , PB ,balance(γ0 , PA ) − δ/2, balance(γ0 , PB ) − δ/2)
8:
(γB,C , trroot,B,C ) ← open virtual(OUT CH(tr1,S ), PB , PC ,balance(γ1 , PB ) − δ/2, balance(γ1 , PC ) − δ/2)
9:(γA,C , trroot,A,C ) ← open virtual(OUT CH(trmrg ), PA , PC , δ/2, δ/2)
10:
∀ transactions except Split: Exchange signatures
11:
PA and PC : send Split transactions’ signatures to PB
12:
PB : Send Split transactions’ signatures to PA and PC
13:
return γ v = (γ0 , γ1 , γA,B , γB,C , γA,C , PA , PB , PC , δ, min(γ0 .t, γ1 .t) −2∆)
14: end function

Figure 4.4: Creation of a virtual channel. Takes two pairwise payment channel
γ0 and γ1 , and an amount of coins δ as input, and outputs a virtual channel γ v .

Algorithm 2 Close Virtual Channel
1: function Close VC(γ v )2:sumA = γ v .γA,B .bA + γ v .γA,C .bA
3:
sumB = γ v .γA,B .bB + γ v .γA,C .bB
4:
sum0B = γ v .γB,C .bA + γ v .γA,C .bA
5:
sumC = γ v .γB,C .bB + γ v .γA,C .bB
6:(γ0 , trroot,A,B ) ← open virtual(γ v .γ0 .f, PA , PB , sumA , sumB , γ v .t)7:(γ1 , trroot,B,C ) ← open virtual(γ v .γ1 .f, PB , PC , sum0B , sumC , γ v .t)
8:∀ transactions except trroot,A,B and trroot,B,C : Exchange signatures
9:
PA signs trroot,A,B , PC signs trroot,B,C . Send signatures to PB
10:
PB signs trroot,A,B and trroot,B,C . Sends signatures to PA and PC respectively
11:
return (γ0 , γ1 )12: end function
Figure 4.5: Closing of a virtual channel γ v by recreating the original channels
γ0 and γ1 . The constructions Split transactions are invalidated by having theroots of the pairwise payment channels have timelocks of at most γ v .t.

4.5. THE UC SETTING

51

Algorithm 3 Enforce Virtual Channel
1: function Enforce VC(γ v )2:for all tr in transactions of γ v do
3:
if tr.t < τ ∧ ∀o ∈ tr.In : o is on the ledger then4:
Commit tr to the ledger
5:
end if
6:
end for
7: end function

Figure 4.6: Parties enforce the state presented by the virtual payment channel
construction by committing transactions to the ledger whenever possible, i.e. assoon as their timelocks expire and UTXO referenced in their inputs are present
on the ledger.

𝒢𝖴𝖳𝖷𝖮−𝖫𝖾𝖽𝗀𝖾𝗋

Ideal Worldℱ𝖫𝖵𝖯𝖢,ℱv𝖯𝖶𝖢𝖧ℱv𝖯𝖶𝖢𝖧

𝒫𝖣𝗎𝗆𝗆𝗒𝒫𝖣𝗎𝗆𝗆𝗒𝒫𝖣𝗎𝗆𝗆𝗒CAB

𝒢𝖢𝖫𝖮𝖢𝖪ℱ𝖲𝖼𝗋𝗂𝗉𝗍 ℱ𝖲𝖨𝖦

Simulator
𝒫𝖲𝗂𝗆
𝒫𝖲𝗂𝗆
A
B

Hybrid Worldℱ𝖲𝖼𝗋𝗂𝗉𝗍 ℱ𝖲𝖨𝖦

𝒫𝖲𝗂𝗆
C

𝒫A 𝒫B 𝒫C

𝒜
𝒵

Figure 4.7: Overview of our setup within the UC framework.

52

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

Overview. Figure 4.7 depicts an overview of our construction. The settingis split up in an Ideal world and a (GCLOCK , GUTXO−Ledger , FSIG , FScript ) - hybrid world. The global functionality GUTXO−Ledger is associated with the global
GCLOCK functionality and accessible from either world. The lightweight virtualchannel functionality FLVPC is associated with the pairwise payment channel
functionality FPWCH receiving access to its internal state and helper functions.
FPWCH includes and replicates the interfaces and behavior of FSIG , FScript .

4.5.1

The Global Clock Functionality GCLOCK .

We adapt the global clock functionality formalized by Katz et al. [68], modified
by Kiayias et al. [74, 72] and is depicted in Figure 4.5.1. The functionality
keeps track of a round number τ that can be read by any party. After finishingcomputations a party sends a clock update request to the functionality. The
round number is incremented after the functionality receives update requests
from all parties as well as the ledger functionality. Parties agree upon a startingtime of their protocol as well as a duration for each round, such that time canbe derived from the round number.
Functionality GCLOCK
The functionality is accessible by any entity and associated with a global
functionality GUTXO Ledger .
State: Stores time τ ∈ N, a set of parties P, bit dGUTXO Ledger ∈ {0, 1} as wellas bits dP for each party in P.
Initialization: Sets τ = dGUTXO Ledger = 0 and P = ∅.
Register: Upon receiving message (register, sid) from party P, set P =P ∪ {P}, store a bit dP ∈ {0, 1} initialized with dP = 0 and send message(register, sid, P) to the adversary.
Clock Update Ledger: Upon receiving message (clock-update, sid) fromGUTXO Ledger set dGUTXO Ledger = 1 and send message(clock-update, sid, P) to the adversary.
Clock Update Party: Upon receiving message (clock-update, sid) fromparty P set dP = 1. If dGUTXO Ledger = 1 and dP = 1 for all honest parties
in P, set τ = τ + 1, dGUTXO Ledger = 0 and dP = 0 for all honest parties in P.
Lastly send message (clock-update, sid, GUTXO Ledger ) to the adversary.
Clock Read: Upon receiving message (clock-read, sid) from any entity reply
with message (clock-read, sid, τ ).

4.5.2

The Global Functionality GUTXO−Ledger

models a UTXO based ledger maintaining a publicly readable set of UTXO.
The ledger maintains a set U that holds all UTXO. The interface Transaction
is used to modify U by providing a UTXO mapping. It can be called by Z
modeling transactions done by parties outside the protocol, however, parties
themselves are only able to change U indirectly by interacting with the FScript
functionality. When receiving a request the functionality checks that all coins4.5. THE UC SETTING

53

within the Outputs of the mapping are covered by the coins referenced in the
Inputs. Any party can read U by calling the Check UTXO sub-function.
The differences between GUTXO−Ledger and the ledger functionality by Kiayias
et al. [74] are twofold. For one instead of using a verification predicate to checkthe validity of transactions, we move this verification into a second functionality
FScript representing required parts of a blockchains scripting language similar
to the separation of ledger and smart contract functionalities in the work of
Dziembowski et al. [49, 46]. For another we explicitly make use of UTXO as
required in our construction.
Functionality GUTXO−Ledger
State: Stores set of UTXO U.
Initialization: Z sends the initial state U0 . Sets U := U0 .
Additional interface: The functionality wraps the FScript and FSIG functionalities internally and replicates their interface. Any messages to thesefunctionalities are processed according to their definition.
Transaction: Upon receiving, from either Z or functionalities, the message(transaction, sid, M ) where M is P
a partial UTXO
mapping, do : LetP(In, Out) = M . Check that In ⊆ U, i∈In i.b ≥ o∈Out o.b. Upon successwithin ∆ rounds set U = (U \ In) ∪ Out.
Check UTXO: Upon receiving (check, sid, out) where out ∈ Output reply(check okay, sid, out) if out ∈ U and (check failure, sid, out) otherwise.

4.5.3

The signature functionality FSIG

by Canetti et. al. [30] as depicted in Figure 4.5.3 provides access to signature
generation and verification as well as facilities to create verification keys.
Functionality FSIGState: Stores set K which contain tuples of form (P, v) where P is a party
and v is a verification key. Set S with entries of form (m, σ, v, b) where mis a message, σ as signature, v a verification key and b ∈ {0, 1}.
Key Generation: Upon receiving message (KeyGen, sid) from party P verify
that sid = (P, sid0 ) for some sid0 . In that case hand (KeyGen, sid) to theadversary. Upon receiving (VerificationKey, sid, v) from the adversary,
forward the message to P and store (P, v) in K.
Signature Generation: Upon receiving message (Sign, sid, m) from party
P verify that sid = (P, sid0 ) for some sid0 . If that is true, send (Sign, sid, m)to the adversary. Upon receiving (Signature, sid, m, σ) from the adversary, if (m, σ, v, 0) 6∈ S send an error message to P and halt. Otherwise
store (m, σ, v, 0) in S and send (Signature, sid, m, σ) to P.

54

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
Signature Verification: Upon receiving message (Verify, sid, m, σ, v 0 ) froma party P forward it to the adversary. Upon receiving(Verified, sid, m, φ) from the adversary do:
1. If v 0 = v and (m, σ, v, 1) ∈ S set f = 1.
2. Else if v 0 = v, (m, σ 0 , v, 1) 6∈ S for any σ 0 and P is not corrupted by
the adversary, store (m, σ, v, 0) in S and set f = 0.
3. Else if (m, σ, v 0 , f 0 ) ∈ S for any v 0 , f 0 set f = f 0 .
4. Else store (m, σ, v 0 , φ) in S and set f = φ.
Send (Verified, sid, m, f ) to P.

4.5.4

The Script functionality

represents the elements of a blockchain’s scripting language we need to enable
our construction. Parties interact with it using the Transaction interface providing a transaction as input. Then it does two checks: (1) the time specified in thetransaction is lower than the current time. For this matter it interacts with the
GCLOCK functionality to derive the current time. (2) It checks whether all parties
mentioned in the transaction’s referenced UTXO provided as inputs, provide asignature of the transaction. For this it interacts with the FSIG functionality.
Functionality FScript
State: Stores set K with entries of form (P, v) where P is a party and v isa verification key.
Registering Verification Key: Upon receiving(VerificationKey, sid, v) from a party P store (P, v) in K.
Transaction: Upon receiving (transaction, sid, tr) from P, let (In, Out,t, Σ) = tr and stub = In0 , Out, t where In0 = {(u)|(u, w) ∈ In}, i.e. thetransaction with omitted witnesses.
• Update time: Send (get-time, sid, ·) to GCLOCK and receive(get-time, sid, τ )• Verify that ∀utxo ∈ In: t ≤ τ . Halt, otherwise.
• Verify ∀ref ∈ In: For each P ∈ ref.u.Party retrieve (P, v) from K.
Verify that ref.w contains a signature of stub from P. For each σ ∈ref.w send (Verify, sid, stub, σ, v) to FSig and verify that FSIG replies
with (Verified, sid, stub, 1) exactly once.
• Send (transaction, sid, Removes, Adds) to GUTXO−Ledger

4.6. THE PAIRWISE PAYMENT CHANNEL FUNCTIONALITY

4.6

55

The Pairwise Payment Channel Functionality

The FPWCH functionality creates, maintains and closes pairwise payment channel between two parties. For simplicity we opt to model a simple payment
channel that uses timelocks to update a channel’s state. The functionality consists of functions Open, Close, Channel Update and Enforce. The Open function
creates a Funding transaction based on a Funding transaction stub provided as
input, commits it to the blockchain by interacting with GUTXO−Ledger and, after
verifying that the mapping was applied on the ledger, stores the channel’s state.
The State Update function redistributes the channel’s funds while reducing its
timelock by at least ∆ whereas Close removes the channel’s timelock while disabling any further updates on it. Lastly Enforce takes a channel as input andchecks whether its timelock is lower or equal than the current round number.
If that is the case a mapping representing a refund transaction is committed to
the ledger.

4.6.1

General Behavior of our Functionalities

General Behavior. Before we detail the functionality’s interface, we describe common non function-specific behavior of both functionalities FPWCH
and FLVPC,FPWCH , which is described in the next section.
Update time: At beginning of each round in which functionality is activatedsend message (clock-read, sid) to GCLOCK and receive the reply(clock-read, sid, τ 0 ). Set internal variable τ = τ 0 .
Interactions with simulator: Whenever the functionality receives a message
msg from any party or from GUTXO−Ledger it leaks the message to the simulator
and appends sender and receiver.
Synchronization with the simulation: Interactions with the ledger are used toread its state as well as trigger a state change. The state on the ledger as well as
whether a state change is permissible depends on the moment they are done astransactions that change the set of UTXO on the ledger can be sent by a party at
any time. Therefore we need to ensure that the functionality’s interaction withthe ledger are at the same time as they happen in the simulation to achieve thesame results and receive the same replies. Whenever the functionality sends a
message msg to the ledger it waits for the simulator to leak a similar message bya honest party. Note that a TRANSACTION tagged message from the simulator
is processed by the FScript functionality first. Then the functionality sends themessage only once and forwards any replies to the simulator.
Handling corrupted parties: We assume static corruption by a malicious adversary. At the beginning of execution the functionality asks the simulator which
parties are controlled by the adversary and stores this information in set COR.
The functionality ignores requests from any party in the ideal world of whichcounterpart in the simulation is corrupted by the adversary. The functionality needs to learn whether a party corrupted by the adversary misbehaved or

56

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

delayed execution of a protocol beyond a channel’s lifetime. For this matteras soon as the simulator leaks that any simulated honest party Ph0 sends message (failure, sid, msg) to Z the functionality aborts execution of the function
triggered by receiving msg and sends (failure, sid, msg) to Ph0 ’s dummy-party
counterpart Ph in the ideal world.

4.6.2

The Payment Channel Functionality FPWCH

Functionality FPWCHState: Current time τ . Set Γ of existing pairwise payment channel, set
ΓA of active pairwise payment channel. Set CONS with entries of form
(P 0 , msg) where P 0 is a party and msg is a message.
Initialization: Sets τ = 0, Γ = ΓA = COR = CONS = ∅.
Helper subfunctions:consent: A call of this sub-function is of form consent(P, Parties, msg) where
P is a party, Parties is a set of parties and msg is a message. Let Partiesh =Parties \ COR.
1. If P 6∈ COR, add (P, msg) to CONS
2. If ∀Ph ∈ Partiesh : (Ph , msg) ∈ CONS,
then set CONS = CONS \ {(Ph0 , msg)|Ph0 ∈ Partiesh } and returnis consent;
Else return no consent
state update: A call of this sub-function is of form
state update(γ, PA , bA , PB , bB , δt ).
1. Checks: γ ∈ ΓA , δt ≥ ∆, γ.t−δt > max(γ.t0 , τ ), bA +bB = γ.bB +γ.bA ;If any check fails halt
2. Update channel: γ = (γ.f, PA , PB , bA , bB , γ.t − δt , γ.t0 )Revoke: A call of this sub-function is of form revoke(γ). Set Γ = Γ \ {γ}.
Activate: A call of this sub-function is of form activate(γ). Set Γ = Γ ∪ {γ}.
Balance: A call of this sub-function is of form balance(γ, P) where γ is apairwise payment channel and P a party.
1. if P 6∈ {γ.PA , γ.PB } halt
2. if P = γ.PA return γ.bA
3. else P = γ.PB return γ.bB
Open: Upon receiving message msg = (open, sid, m, PA , PB , bA , bB , t)from P ∈ {PA , PB } where m is a map, bA , bB ∈ N are amounts of coins
and t ∈ N is a round number do:4.6. THE PAIRWISE PAYMENT CHANNEL FUNCTIONALITY
1. Let (In, Out) = m, Partiesh = {PA , PB } \ COR.
2. if consent(P, {PA , PB }, msg) = no consent: halt
3. Verify; if any verification fails send (failure, sid, msg) to all in Ph :• No overspending: Σo∈Out o.b ≤ bA + bB + Σo∈In• Sufficient funds: ∪o∈{In} o.Party = {PA , PB }• Parties contribute sufficiently: For i ∈ {A, B} holds
Σo∈In,o.Party=Pi o.b ≥ bi
• Valid timelock: t ≥ τ + ∆ + 1• ∀o ∈ In send (check, sid, o) to GUTXO−Ledger . If GUTXO−Ledger
replies with (check okay, sid, o) for each o ∈ In continue, otherwise halt
4. Funding: mf = (In, Out ∪ {f }) where f = (bA + bB , {PA , PB }) is afunding output
5. Send message (transaction, sid, mf ) to GUTXO−Ledger
6. For all o ∈ (Out ∪ {f }) send message (check, sid, o) to GUTXO−Ledger .
If it replies (check okay, sid, o) for all o ∈ (Out ∪ {f }) continue;
otherwise halt and repeat this step next round
Upon receiving message (success, sid, msg) from all parties in Partiesh :1. Update internal state: Γ = Γ ∪ {γ}, ΓA = ΓA ∪ {γ} where γ =(f, PA , PB , bA , bB , t, 0)
2. Return message (success, sid, msg) to P ∈ Partiesh
Channel Update: Upon receiving msg =(channel update, sid, γ, P0 , b0 , P1 , b1 , δt ) from P ∈ {γ.PA , γ.PB } wherebA , bB , δt ∈ N. Do:
1. Let Partiesh = {γ.PA , γ.PB } \ COR
2. if consent(P, {PA , PB }, msg) = no consent: halt
3. Verify: {P0 , P1 } = {PA , PB }. Send (failure, sid, msg) to all in Ph
if it fails
Upon receiving message (success, sid, msg) from all parties in Partiesh :1. Execute state update(γ, (P0 , b0 ), (P1 , b1 ), δt )2. Return message (success, sid, msg) to all P ∈ Partiesh

57

58

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
Close: Upon receiving msg = (close, sid, γ) from P ∈ {PA , PB } where
PA = γ.PA and PB = γ.PB do:
1. Let Partiesh = {γ.PA , γ.PB } \ COR.
2. if consent(P, {PA , PB }, msg) = no consent: halt
3. Verify: {P0 , P1 } = {PA , PB }. Send (failure, sid, msg) to all in Ph
if it fails
Upon receiving message (success, sid, msg) from all parties in Partiesh :1. Execute state update(γ, (γ.PA , γ.bA ), (γ.PB , γ.bB ), γ.t − γ.t0 )2. ΓA = ΓA \ {γ}
3. Return message (success, sid, msg) to all P ∈ Partiesh
Enforce: Upon receiving msg = (enforce, sid, γ) from party P do: Let
PA = γ.PA and PB = γ.PB .
1. Do the following. If any check or verification fails, immediately return
message (enforce, sid, f ailure) to P and halt.
• Check: P ∈ {PA , PB }; γ.t ≤ τ• Send message (check, sid, γ.f ) to GUTXO−Ledger . If it replies(check okay, sid, o) continue, otherwise if it replies(check failure, sid, o) halt
2. mr = REFUND MAP(γ.f , γ.bA , γ.bB )3. Send message (transaction, sid, mr ) to GUTXO−Ledger
4. Γ = Γ \ {γ}; ΓA = ΓA \ {γ}
5. Return message (success, sid, msg) to P

4.6.3

An Extension to the FPWCH Functionalityv
Functionality FPWCH
is an extension of functionality FPWCH by providing analternative function to open a pairwise payment channel which is required forthe virtual payment channel functionality. This function takes a Funding UTXO
instead of a Funding transaction stub as input and creates a pairwise payment
channel without committing a Funding transaction to the ledger.

4.7. THE IDEAL VIRTUAL CHANNEL FUNCTIONALITY

59v
Functionality FPWCH
Functionality that behaves as FPWCH but includes the following helper
function to facilitate use with virtual channels.
Open Virtual: A call of this sub-function by an associated functionality
is of form open virtual(f, PA , PB , bA , bB , t, t0 ) where f is a funding output,
bA , bB ∈ N are amounts of coins and t, t0 ∈ N is a round number. Then:

1. mr = REFUND MAP(f , bA , bB )2. Channel: γ = (f, PA , PB , bA , bB , t, t0 )3. Update internal state: M = M ∪ {(γ, mr , t)}; Γ = Γ ∪ {γ}; ΓA =
ΓA ∪ {γ}4. Return γ

4.7

The Ideal Virtual Channel Functionality

In the following we present formal treatment of our protocol in the UC framework by introducing a functionality for lightweight virtual payment channel
FLVPC,FPWCH , associated with functionality FPWCH . For this we make use of
auxiliary functionality FScript , global UTXO ledger functionality GUTXO−Ledger ,global clock functionality GCLOCK , and functionality FSIG . These functionalities
are defined in Section 4.5.4.
The Ideal Virtual Channel Functionality. The lightweight virtual payment channel functionality FLVPC,FPWCH is used to create and close virtual payment channel between three parties. It provides access to functions VC-Open,VC-Close and VC-Enforce. Function VC-Open takes two pairwise payment channel between three parties as input, disables state updates on those, and creates
three new pairwise payment channel, one between each pair of parties. To beable to enforce these channels it creates and stores mappings that represent
Split, Merge and Punish transactions together with the time at which they
become valid. Function VC-Close takes a virtual channel as input. First it
checks whether no virtual channel have been created using the pairwise payment channel created with it. If positive it disables state updates on thesechannels, re-enables state updates for the original channels, updates their balance to reflect the latest balance distribution among the three channels and sets
the channel’s timelocks to be lower than the one of the Split mappings by ∆.
Function Enforce is used to commit any mapping representing Split, Merge or
Punish transactions if their timelocks have expired. This disables closure of thevirtual channel because the funding UTXO of the original pairwise payment
channels are removed from the ledger.
The functionality shares the same non-function specific behavior as FPWCH ,i.e. time management, interactions with the simulator and handling of corrupted

60

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

parties. We refer to the previous section for details.
v
Functionality FLVPC,F
PWCHv
Has access to FPWCH ’s helper functions.
v

State: Set of closable virtual payment channel Γ of virtual payment channels. List M v of entries (γ 0v , m, t) where γ 0v is a virtual payment channel,
m is a partial mapping and t is a round number. It has access to the interv
nal state of FPWCH
including set Γ of pairwise payment channels. Moreoverv
it shares common state with FPWCH
which is the current round number τ ,list of corrupted parties COR and set of consent giving parties CONS.
v
Initialization: Initializes FPWCH
and shared state τ, COR, CONS. Sets Γv =v
M = ∅.
VC-Open: Execute upon receiving message msg =(open, sid, γ0 , γ1 , δ, t, PA , PB , PC ) from P ∈ {PA , PB , PC } where
γ0 , γ1 ∈ Γ, δ ∈ N is an amount of coins and t ∈ N is a round number. Let
Partiesh = {PA , PB , PC } \ COR:
1. if cns = consent(P, {PA , PB , PC }, msg) = no consent: halt
2. Verify; if any verification fails send (failure, sid, msg) to all in Ph :• {PA , PB } = {γ0 .PA , γ0 .PB } and {PB , PC } = {γ1 .PA , γ1 .PB }• for each γ ∈ {γ0 , γ1 }: if {γ.PA , γ.PB } \ COR 6= ∅ then– γ ∈ Γ; γ.t > τ + 2∆; γ.t0 > τ + 2∆; γ.bA ≥ δ/2 andγ.bB ≥ δ/2
Upon receiving message (success, sid, msg) from all parties in Partiesh :1. Create Mappings• Split: m0,S = SPLIT MAP(γ0 .f , δ); m1,S = SPLIT MAP(γ1 .f ,δ)
• Merge: mmrg = MERGE MAP(OUT DELTA (m0,S ),OUT DELTA( m1,S ), δ)• Punish: m0,p = PUNISH MAP(OUT DELTA(m0,S ), PA )• m1,p = PUNISH MAP ( OUT DELTA(m1,S ), PC )2. Create new channel, revoke old• γA,B = open virtual(fA,B , PA , PB , balance(γ0 , PA ) − δ/2,
balance(γ0 , PB ) − δ/2, t, γ0 .t)• γB,C = open virtual(fB,C , PB , PC , balance(γ1 , PB ) − δ/2,
balance(γ1 , PC ) − δ/2, t, γ1 .t)

4.7. THE IDEAL VIRTUAL CHANNEL FUNCTIONALITY

61• γA,C = open virtual(fA,C , PA , PC , δ/2, δ/2, t, max(γ0 .t, γ1 .t) +∆)• Revoke old channel: revoke(γ0 ) and revoke(γ1 )Virtual channel: γ v = (γ0 , γ1 , γA,B , γB,C , γA,C , PA , PB , PC , δ,
3. min(γ0 .t, γ1 .t) − 2∆)
4. Update: Γv = Γv ∪ {γ v } and M v = M v ∪ {(γ v , m0,S , γ0 .t − ∆),(γ v , m1,S , γ1 .t − ∆), (γ v , mmrg , max(γ0 .t, γ1 .t)), (γ v , m0,p , max(γ0 .t,
γ1 .t) + ∆), (γ v , m1,p , max(γ0 .t, γ1 .t) + ∆)}5. Return message (success, sid, msg) to P
VC-Close: Upon receiving message msg = (close, sid, γ v , ) from P ∈{PA , PB , PC } where PA = γ v .PA , PB = γ v .PB and PC = γ v .PC . Let(γ0 , γ1 , γA,B , γB,C , γA,C , PA , PB , PC , δ, t) = γ v . Moreover let Partiesh ={PA , PB , PC } \ COR. Do:
1. if cns = consent(P, {PA , PB , PC }, msg) = no consent: halt
2. Verify; if any verification fails send (failure, sid, msg) to all in Ph :v
• γ v ∈ Γv ; {γA,B , γB,C , γA,C } ⊆ FPWCH.Γ; t > τ ; γ0 .t0 > τ + 2∆,
γ1 .t0 > τ + 2∆

Upon receiving message (success, sid, msg) from all parties in Partiesh :1. Revoke old channel, reactivate and update original channel:• activate(γ0 ), activate(γ1 )• state update(γ0 , PA , bA , PB , bB , 2∆) and state update(γ1 , PB , b0B ,PC , bC , 2∆) where bA = γA,B .bA + γA,C .bA ; bB = γA,B .bB +γA,C .bB ; b0B = γB,C .bA + γA,C .bA ; bC = γB,C .bB + γA,C .bB .
• revoke(γA,B ), revoke(γB,C ), revoke(γA,C )2. Update internal state: Γv = Γv \ {γ v }3. Return message (success, sid, msg) to P
VC-Enforce: Triggered upon receiving msg = (enforce, sid, γ v ) fromparty P where γ v is a lightweight virtual payment channel. Let PA =γ v .PA , PB = γ v .PB and PC = γ v .PC .
1. Check if P ∈ {PA , PB , PC }, γ ∈ Γ
2. Let Mγ = {(γ 0v , m0 , t0 )|(γ 0v , m0 , t0 ) ∈ M v ; γ 0v = γ v ; t0 ≤ τ, ∃utxo ∈m0 .In : P ∈ utxo.Party}

62

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
3. for each m ∈ Mγ
• Let (In, Out) = m. For all o ∈ In send message (check, sid, o)
to GUTXO−Ledger . If it replies (check okay, sid, o) for all o ∈ In:– Send message (transaction, sid, m) to GUTXO−Ledger– Channel cannot be closed: Γv = Γv \ {γ v }4. Return message (success, sid, msg) to P

Definition 4.7.1. Balance Security: The sum of a honest party’s funds onlychanges with its consent.
Definition 4.7.2. Liveness: Eventually all of a party’s funds are unlocked andcommitted to the ledger within UTXO that are spendable by the party alone.
Security of Funds and Liveness. In the following we briefly argue thatfunctionality FLVPC,FPWCH fulfills these two properties for honest parties by design. We expect a honest party to call sub-function VC-Enforce as soon as theywould lead to submission of a mapping to the ledger, i.e. at times γ v .γ0 .t − ∆,γ v .γ1 .t − ∆, max(γ v .γ0 .t, γ v .γ1 .t) and in case a punish transaction has to becommitted at time max(γ v .γ0 .t, γ v .γ1 .t) + ∆. Eventually all funds that a honest
party holds will be accessible over UTXOs on the ledger such that liveness holds.
Balance Security holds since only FPWCH ’s channel update function, which requires the party’s consent, changes a honest parties’ balance.

4.8

The Pairwise Payment Channel Protocol

Analogous to the functionalities we define protocols PWCH and it’s extension
PWCHv for pairwise payment channel, as well as a protocol for virtual payment
channel LVPCPWCHv in the following section. They are designed similar to theirfunctionality counterparts, however, parties involved in such a protocol need toadditionally do:• Instead of abstract mappings, transactions need to be created. Parties
need to exchange signatures as ways to provide consent• In the Channel Update method, in addition to updating an internal state,parties need to create a transaction to make it enforceable• Order matters: The root of a transaction subtree spending the Funding
UTXO needs to be signed last. In VC-Open and VC-Close the intermediary
party is allowed to sign the root of the transactions subtree only after
receiving signatures of those from the other parties

4.8. THE PAIRWISE PAYMENT CHANNEL PROTOCOL

4.8.1

63

General Behavior

The following behavior is always performed by any honest party and for either
protocol and is the analogous component of the functionalities’ common nonfunction specific behavior:
Update time: Sub-function that is executed at the beginning of each round.
Send message (clock-read, sid) to GCLOCK and receive reply(clock-read, sid, τ 0 ). Set internal variable τ = τ 0 .
Handling corrupted parties: During execution as soon as another party is observed deviating from a protocol send message (failure, sid, msg) to Z and
halt.
Timeouts: Upon receiving message(open, sid, m, PA , PB , bA , bB , t),(state update, sid, γ, δ) or (close, sid, γ 0 ), if the execution of the subprotocol triggered by these messages does not finish until round number t, γ.tor γ 0 .t respectively the counterparty is considered to be unresponsive. Send
(failure, sid, msg) to Z and halt the sub-protocol’s execution.

4.8.2

The PWCH Protocol

Protocol PWCH
State: Each party stores current time τ , verification key v, set of otherparty’s verification keys V , set Γ of created pairwise payment channel andΓA of active pairwise payment channel, set CONS with entries of form
(P, msg), Refund transactions RFND(γ) for each created channel γ ∈ Γ.
Initialization: Send message (register, sid) to GCLOCK followed by(clock-read, sid) to receive (clock-read, sid, τ 0 , fast). Initialize τ = τ 0 .
Set Γ = ΓA = CONS = ∅. Lastly send message (KeyGen, sid) to FSIG
and wait for reply (Verification Key, sid, v 0 ). Set verification key v =v 0 . Send message (Verification Key, sid, v) to FScript and broadcast(Verification Key, sid, v) to all parties.
Verification Keys: Whenever receiving a message(Verification Key, sid, v) from another party P store tuple (P, v) in V .
Subprotocol sign broadcast: Takes as input signing parties PartiesS , transaction tr, set of receiving parties PartiesR .
1. Set stub = (tr.t, tr.Ref, tr.Out)2. Each P ∈ PartiesS :• send message (Sign, sid, stub) to FSIG and receive reply(Signature, sid, stub, σ)• ∀(out,Σ)∈Tr.UIn : if P ∈ out.Party set Σ = Σ ∪ {σ}• send message (Signature, sid, stub, σ) to all parties in Parties

64

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
3. Each party in Parties upon receiving (Signature, sid, stub, σ) does:• Lookup entry (P, v 0 ) ∈ V and send (Verify, sid, m, σ 0 , v 0 ) to
FSIG
• if such an entry does not exist, or if FSIG replies with
(Verified, sid, m, f ) where f = 0 then return failure• else ∀(out,Σ)∈Tr.UIn : if P ∈ out.Party set Σ = Σ ∪ {σ}4. Return success
Consent: Whenever a party receives a message of form (req, sid, msg)
from a party P 00 they store tuple (P 00 , msg) in CONS.
Subprotocol consent verification:
Inputs: Parties, msg
1. Send message (req, sid, msg) to all P ∈ Parties
2. If ∃(P, msg) 6∈ CONS wait; proceed upon receiving (req, sid, msg)
from P
3. Set CONS = CONS \ {req}
Request Verifications: Upon receiving message msg from Z triggering
execution of a subprotocol below, if any verifications fails send
(failure, sid, msg) to Z.
Revoke: A call of this sub-protocol is of form revoke(γ). Set ΓA = ΓA \{γ}.
Activate: A call of this sub-protocol is of form activate(γ, tr). Set ΓA =
ΓA ∪ {γ}; RFND(γ) = tr.
Balance: A call of this sub-protocol is of form balance(γ, P) where γ is apairwise payment channel and P a party.
1. if P 6∈ {γ.PA , γ.PB } halt
2. if P = γ.PA return γ.bA
3. else P = γ.PB return γ.bB
Open: A party P upon receiving msg = (open, sid, m, PA , PB , bA , bB , t)from Z where PA and PB are parties, m is a map, bA , bB ∈ N are amountsof coins and t ∈ N is a round number does:
1. Party is addressed: Check P ∈ {PA , PB }. Otherwise ignore request.
In the following let Pc be P’s counterparty.
2. Consent: Execute sub-protocol consent verification({Pc }, msg)

4.8. THE PAIRWISE PAYMENT CHANNEL PROTOCOL
3. Let (In, Out) = m. Verify:• Σo∈Out o.b ≤ bA + bB + Σo∈In ; ∪o in{In} o.Party = {PA , PB }; fori ∈ {A, B} holds Σo∈In,o.Party=Pi o.b ≥ bi ; t ≥ τ + ∆ + 1• ∀o ∈ In, after sending message (check, sid, o) to GUTXO−Ledger(check okay, sid, o) is returned
4. If check of verification fails the party sends (failure, sid, msg) to Z
5. Funding: mf = (In, Out∪{f }) where f = (bA +bB , {PA , PB }). Transaction trf = φ(mf , 0)
6. Refund: trr = REFUND TR(f , t, bA , bB )7. Perform sign broadcast({PA , PB }, trr , {PA , PB })8. Perform sign broadcast({PA , PB }, trf , {PA , PB })9. Send (transaction, sid, trf ) to FScript .
10. Poll result: Send message (check, sid, f ) to GUTXO−Ledger . If it returns (check okay, sid, f ) continue; otherwise if it returns(check failure, sid, f ) halt and repeat next round
11. Set γ = (f, PA , PB , bA , bB , t, 0)
12. Update state: Γ = Γ ∪ {γ}; ΓA = ΓA ∪ {γ}; RFND(γ) = trr
13. Return message (success, sid, msg) to Z
Channel Update: A party P, upon receiving msg =(state update, sid, γ, P0 , b0 , P1 , b1 , δt ) from Z does: Let PA = γ.PA and
PB = γ.PB .
1. Party is addressed: Check P ∈ {PA , PB }. Otherwise ignore request.
In the following let Pc be P’s counterparty
2. Verify P ∈ {PA , PB }. Otherwise ignore request. In the following let
Pc be P’s counterparty
3. Perform consent verification({Pc }, msg)
4. if P0 = PA then bA = b0 , bB = b1 else bA = b1 , bB = b0
5. Verify (PA , PB , γ) ∈ Γ; γ ∈ Γ; δt ≥ ∆; γ.t − δt > max(γ.t0 , τ );bA + bB = γ.bB + γ.bA
6. Refund: trr = trr = REFUND TR(γ.f , γ.t − δt , bA , bB )7. Perform sign broadcast({PA , PB }, trr , {PA , PB })

65

66

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
8. Update state: γ = (γ.f, PA , PB , bA , bB , γ.t − δt , γ.t0 ); RFND(γ) = trr
9. Send message (success, sid, msg) to Z
Close: A party P, upon receiving msg = (close, sid, γ) from Z does: Let
PA = γ.PA and PB = γ.PB .
1. Verify P ∈ {PA , PB }. Otherwise ignore request. In the following let
Pc be P’s counterparty.
2. Execute consent verification({Pc }, msg)
3. Verify (PA , PB , γ) ∈ Γ
4. Refund: trr = trr = REFUND TR(γ.f , γ.t, γ.bA , γ.bB )5. Perform sign broadcast({PA , PB }, trr , {PA , PB })6. Update state: γ = (γ.f, PA , PB , γ.bA , γ.bB , 0); RFND(γ) = trr
7. Return message (success, sid, msg) to Z
Enforce: A party P upon receiving msg = (enforce, sid, γ) from party Z
does: Let PA = γ.PA and PB = γ.PB .
1. Verify:• γ ∈ ΓA ; γ.t ≤ τ . In the following let φ−1 (RFND(γ)) = (m, t, Σ),(In, Out) = m
2. Let (In, Out) = m. For all o ∈ In send message (check, sid, o) to
GUTXO−Ledger . If it replies (check okay, sid, o) for all o ∈ In continue,
otherwise if it replies (check failure, sid, o) for any o ∈ In halt
3. Set Γ = Γ \ {γ}, ΓA = ΓA \ {γ}
4. Send (transaction, sid, tr) to FScript
5. Return message (success, sid, msg) to Z.

4.8.3

An Extension to the PWCH Protocol

Similar to the functionality we provide an extension of our protocol which is
PWCHv that includes an interface of opening a pairwise payment channel thatcan be used with the virtual channel construction. More specifically it allows
for the Funding UTXO to not be committed to the ledger.

4.9. THE FORMAL VIRTUAL CHANNEL PROTOCOL

67

Protocol PWCHv
Protocol that behaves as PWCH but is modified to facilitate use with
virtual channels by providing following sub-protocol:
Open Virtual: A call of this sub-protocol is of form
open virtual(f, PA , PB , bA , bB , t, t0 ) where f is a funding output, bA , bB ∈ N
are amounts of coins and t, t0 ∈ N are round numbers. Let P be caller ofthis function. Then:
1. Set trr = REFUND TR(f , t, bA , bB )2. Perform sign broadcast({PA , PB }, trr , {PA , PB })3. Channel: γ = (f, PA , PB , bA , bB , t, t0 )4. Update internal state: Γ = Γ ∪ {γ}5. Return γ, trr

4.9

The Formal Virtual Channel Protocol

Protocol LVPCPWCHv utilizes protocols PWCHv to implement FLVPC,FPWCH . In
addition to the sub-protocols stated below, parties perform non-function specificbehavior to track time, and handle misbehaving parties. This behavior is sharedwith protocol LVPCPWCHv and we refer to the previous section for details.
Analogous to protocol PWCHv the protocols’ design is derived from functionality FLVPC,FPWCH and follows its structure, however, in turn it has to handle
creation and storage of transactions and it has to handle signatures of transactions as well as their order to enforce atomic setup of our construction.
Protocol LVPCPWCHv
Has access to PWCHv ’s internal state and helper sub-protocols.
State: Each party P stores the following state. Set of closable virtual payment channel Γv , set Trv of entries (γ 0v , tr) where γ 0v is a virtual payment
channel, tr is a transaction. It has access to the internal state and helper
protocols of PWCHv and shares common state with PWCHv which is thecurrent round number τ , verification key v list of other parties’ verification
keys V and set of consent giving parties CONS.
Initialization: Execute PWCHv ’s Initialization sub-protocol. Moreover set
Γv = Trv = ∅.
VC-Open: Executed upon receiving message msg =(open, sid, γ0 , γ1 , δ, t, PA , PB , PC ) where γ0 , γ1 ∈ Γ, δ ∈ N is an amountof coins and t ∈ N is a point in time. In the following let PCM P ={PA , PB , PC } \ {P} and Partiesh = {PA , PB , PC } \ COR.

68

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
1. Party is addressed: Check P ∈ {PA , PB , PC }, otherwise ignore request
2. Perform consent verification(PCM P , msg)
3. Verify:• {PA , PB } = {γ0 .PA , γ0 .PB } and {PB , PC } = {γ1 .PA , γ1 .PB }• for each γ ∈ {γ0 , γ1 }: if P ∈ {γ.PA , γ.PB } thenv
– γ ∈ FPWCH.Γ; γ.t > τ + 2∆; γ.t0 > τ + 2∆; γ.bA ≥ δ/2 andγ.bB ≥ δ/2

4. PA and PB : tr0,S = SPLIT TR(γ0 .f , δ, γ0 .t − ∆)tr0,p = PUNISH TR(OUT DELTA(tr0,S ), PA , max(γ0 .t, γ1 .t) + ∆)5. PB and PC : tr0,S = SPLIT TR(γ1 .f , δ, γ1 .t − ∆)tr1,p = PUNISH TR(OUT DELTA(tr1,S ), PC , max(γ0 .t, γ1 .t) + ∆)6. trmrg = MERGE TR(OUT DELTA(tr0,S ), OUT DELTA(tr0,S ), δ,max(γ0 .t, γ1 .t))
7. PA and PB :γA,B , trA,B = open virtual(OUT CH(tr0,S ), PA , PB , balance(γ0 , PA ) −δ/2, balance(γ0 , PB ) − δ/2, t, γ0 .t)
8. PB and PC : γB,C , trB,C = open virtual(OUT CH(tr1,S ), PB , PC ,balance(γ1 , PB ) − δ/2, balance(γ1 , PC ) − δ/2, t, γ1 .t)
9. PA and PC : γA,C , trA,C = open virtual(OUT CH(trmrg ), PA , PC , δ/2,
δ/2, t, max(γ0 .t, γ1 .t) + ∆)10. Perform sign broadcast({PA , PB , PC }, trmrg , {PA , PB , PC })11. Perform sign broadcast({PA , PB }, tr0,p , {PA , PB })12. Perform sign broadcast({PB , PC }, tr1,p , {PB , PC })13. Perform sign broadcast({PA }, tr0,S , {PA , PB })14. Perform sign broadcast({PC }, tr1,S , {PB , PC })15. Perform sign broadcast({PB }, tr0,S , {PA , PB })16. Perform sign broadcast({PB }, tr1,S , {PB , PC })17. PA , PB : Γ = Γ ∪ {γA,B }; activate(γA,B , trA,B ); revoke(γ0 )18. PB , PC : Γ = Γ ∪ {γB,C }; activate(γB,C , trB,C ); revoke(γ1 )4.9. THE FORMAL VIRTUAL CHANNEL PROTOCOL

69

19. PA , PC : Γ = Γ ∪ {γA,C }; activate(γA,C , trA,C )20. Setup virtual channel: γ v = (γ0 , γ0 .t, γ1 .f , γ1 .t, γA,B , γB,C , γA,C ,PA , PB , PC ), δ, min(γ0 .t, γ1 .t) − 2∆)
21. State Update: Γv = Γv ∪ {γ v } and Trv = Trv ∪ {(γ v , tr0,S , tr0,S .t),(γ v , tr1,S , tr1,S .t), (γ v , trmrg , trmrg .t), (γ v , tr0,p , tr0,p .t), (γ v , tr1,p , tr1,p .t)}
22. Return message (success, sid, msg) to Z
VC-Close: Executed upon receiving message msg = (close, sid, γ v , ) from
Z. Let PA = γ v .PA , PB = γ v .PB and PC = γ v .PC . Let (γ0 , γ1 , γA,B ,γB,C , γA,C , PA , PB , PC , δ, t) = γ v ; PCM P = {PA , PB , PC } \ {P}. Do:
1. Party is addressed: Check P ∈ {PA , PB , PC }. Otherwise ignore request.
2. Perform consent verification(PCM P , msg)
3. Verify:v• γ v ∈ Γv ; {γA,B , γB,C , γA,C } ⊆ FPWCH.Γ; t > τ ; γ0 .t0 > τ + 2∆,
γ1 .t0 > τ + 2∆

4. revoke(γA,B ), revoke(γB,C ), revoke(γA,C )5. For PA , PB do: tr0,r = REFUND TR(γ0 .f , γ0 .t − 2∆, sumA , sumB )where sumA = γA,B .bA + γA,C .bA and sumB = γA,B .bB + γA,C .bB
6. For PB , PC do: tr1,r = REFUND TR(γ1 .f , γ1 .t − 2∆, sum0B , sumC )where sum0B = γB,C .bA + γA,C .bA and sumC = γB,C .bB + γA,C .bB
7. Perform sign broadcast({PA }, tr0,r , {PA , PB })8. Perform sign broadcast({PC }, tr1,r , {PB , PC })9. Perform sign broadcast({PB }, tr0,r , {PA , PB })10. Perform sign broadcast({PB }, tr1,r , {PB , PC })11. PA , PB :(a) γ0 = (γ0 .f, PA , PB , bA , bB , γ0 .t − 2∆, γ0 .t0 )(b) activate(γ0 , tr0,r )12. PB , PC :(a) γ1 = (γ1 .f, PB , PC , bB , bC , γ1 .t − 2∆, γ1 .t0 )(b) activate(γ1 , tr1,r )13. Update internal state: Γv = Γv \ {γ v }70

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS
14. Return message (success, sid, msg) to Z
VC-Enforce: Triggered upon receiving msg = (enforce, sid, γ v ) fromparty Z where γ v is a lightweight virtual payment channel. Let PA =γ v .PA , PB = γ v .PB and PC = γ v .PC .
1. Check there is an enforceable mapping: Let TRγ = (γ, tr) ∈ {(γ 0 , tr0 )| (γ 0 , tr0 ) ∈ TRv , γ 0 = γ, tr0 .t ≤ τ }.
2. ∀(γ, tr) ∈ TRγ :• Let φ−1 (tr) = (m, t, Σ), (In, Out) = m.
• ∀o ∈ In send message (check, sid, o) to GUTXO−Ledger• if ∀o ∈ In it replies (check okay, sid, o) then send message(transaction, sid, tr) to FScript .
• Set Γv = Γv \ {γ v }3. Return message (success, sid, msg) to Z

4.10

Simulation Based Security Proof

In the following we provide simulation based proof of the security of our protocols. First we construct simulators SP W CH and SV LP C . Thereafter, using
those we introduce and prove security as stated in Theorems 4.10.1 and 4.10.2
below.
Simulator SP W CH
State: Simulates protocol PWCH creating the internal states of each party
and maintaining their view. Moreover it stores a set of corrupted parties
COR.
Initialization: Creates and initializes internal state of each of the simulatedparties. At beginning of execution the adversary can corrupt any parties
in which case the simulator will leak the corrupted parties’ internal state
to the adversary and stores their identities in COR. Upon request from thefunctionality, the simulator responds with the set of corrupted parties COR.
Behavior: Whenever the functionality leaks a message with sender andreceiver appended, SP W CH simulates sending of that message by the sender
to the receiver. If the message’s receiver is a corrupted party, SP W CH
forwards the message to the respective party. Whenever any simulated
party or the adversary send a message to a functionality, i.e. FScript ,FSIG , GU T XO−Ledger , GCLOCK or to Z, the simulator leaks it to FPWCH
annotating sender and receiver. If the sending entity expects a reply thesimulator waits for FPWCH to leak it.

4.10. SIMULATION BASED SECURITY PROOF

71

Simulator SV LP C
State: Simulates protocol LVPCPWCHv creating the internal states of eachparty and maintaining their view. Moreover it stores a set of corrupted
parties COR.
Initialization and Behavior are analogous to SP W CH , however it interactsv
with FLVPC,FPWCH
instead of FPWCH .
Theorem 4.10.1. Protocol PWCH realizes FPWCH in the (GCLOCK , GUTXO−Ledger ,FSIG , FScript ) - hybrid world
Sketch of Proof. First, we show that the probability that the simulatedparties and parties in the hybrid world have different state changes with thesame requests from Z is in O(negl(n)). The probability that the channel states
stored by FPWCH is different to those stored by the parties is in O(negl(n)).
The probability that the global functionality GUTXO−Ledger has different statechanges depending on whether Z sends the same requests to either the ideal or
the hybrid world is in O(negl(n)). We argue that following this the simulation
by SP W CH is indistinguishable from the execution in the hybrid world and
IDEALF ,S,Z ≈c HYBRIDπFaux ,A,Z .
We briefly handle the case that two parties corrupted by the adversary are
instructed to setup a pairwise payment channel. Note that FPWCH is aware on
which parties are corrupted by the adversary by inquiring this information from
SP W CH . In this case FPWCH forwards requests from Z to SP W CH where they
are handed to the adversary, but ignores them otherwise. Any communication
between corrupted parties and GCLOCK , GUTXO−Ledger , FSIG , FScript or Z are forwarded by SP W CH and FPWCH to the appropriate interfaces, resulting in thesame state changes in GUTXO−Ledger and the same messages received by corrupted
parties and the adversary as in the hybrid world.
In the following we assume that all pairwise payment channel created byinstructions of Z have at least one party participating that is not corrupted by
the adversary. Any requests sent by Z are forwarded by FPWCH to SP W CH tobe simulated such that all requests are received in the simulation. The same
requests are permissible in either world, either by having access to the samefunctionalities, as FSIG , or by FPWCH providing an interface for the sub-protocols
in PWCH. Each request is subject to the same checks in either world. Upon
each request, the functionality as well as the protocol verify consent between
all honest parties. Consent of corrupted parties is implicit by their cooperation or lack thereof. Afterwards checks on the parameter within a request
are performed which are the same. Attention has to be paid to verificationthat an utxo ∈ UTXO is logged on the ledger. These require sending messages
to GUTXO−Ledger tagged with check. The replies on these messages are timedependent as messages tagged to GUTXO−Ledger tagged transaction can alter its
state at any time and the adversary might try to delay execution of the protocol
to provoke receiving different replies from GUTXO−Ledger . However, FPWCH waits
with sending any such message for the simulation to catch up such that they are

72

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

sent at the same time and the same replies are processed by functionality andsimulation. The same holds for messages sent to GUTXO−Ledger tagged transaction
in sub-functions open and enforce to account for delays created by the adversary. At the end of execution, successful checks have to lead to the same statechanges to be applied between the simulated parties and the analogous state in
FPWCH . However, a corrupted party might deviate from the protocol in whichcase any honest party will abort the sub-protocol. If such behavior is observed
any honest party will send a message (failure, sid, msg) to Z where msg isthe message with Z’s request which is forwarded to FPWCH by the simulator.
Respectively FPWCH will abort execution of the respective sub-function and forward the message to the respective dummy party. However, if no such behavior
was observed any simulated honest party will output a message to Z of form
(success, sid, msg) which indicates to FPWCH that the respective party finishedexecution by the sub-protocol including performing a state change. Only then
FPWCH performs an analogous state change.
In the enforce sub-function a refund mapping is created on the fly dependingon the channel’s state. This is not possible in the protocol as a corrupted party
could refuse collaboration. Respectively, in the protocol when a channel is setup
as well as when a channel changes state, a refund transaction representing thelatest state has to be created and signed by both involved parties to be able
to execute enforce unilaterally by any honest party. We note that whether
execution of enforce results in applying a state change to the ledger depends
on when it is executed. A honest party always attempts to apply a channel’slatest state to the ledger. If enforce is instructed as soon as a channel γ’s
lifetime expires, i.e. at time γ.t, this will always result in the appropriate statechange as there is no transaction with timelock of less than γ.t + ∆. However, if
enforce is executed later, a corrupted party might attempt to send a transaction
representing an older channel’s state applying it to the ledger. Nevertheless, assuch a transaction would be simply forwarded by FPWCH this would be the samein either ideal or hybrid world.
Lastly, an adversary can attempt to forge the signature of a honest party tocreate a transaction that spends a channel’s Funding utxo. However it is shownthat the probability for this is in O(negl(n)) [30].
Theorem 4.10.2. Protocol LVPCPWCH realizes FLVPC,FPWCH in the(GCLOCK , GUTXO−Ledger , FSIG , FScript ) - hybrid world.
Sketch of Proof. The proof is analogous to the proof of Theorem 4.10.1,
however, in addition we need to analyze the interaction between the parties
because we moved from a protocol between two parties to a protocol between
three parties.
v
Functionality FLVPC,FPWCH
creates and stores all mappings of a virtual channel
construction and creates, re-activates and disables pairwise payment channels
simultaneously. However, corrupted parties might try to create only a subset oftransactions by selectively providing or withholding signatures of transactions.
In the protocol, the order in which transactions are signed enforces that from

4.11. CONCLUSION73

the perspective of a honest party, either all transactions they hold are fully
signed or none of the transaction created in a sub-protocol can be committed
to the ledger before it successfully terminates.
In the case of the VC-Open protocol, all transactions a honest party is involved in creating depends on whether the split transactions it holds can becommitted to the ledger. Respectively the party needs to make sure that it
holds all other transactions fully signed before proceeding to sign any split
transactions. As the intermediate party holds two split transactions, it has tomake sure that either all or no split transaction is signed. For this reason it
has to wait signing split transactions and broadcasting these signatures until
it received signatures for each split transaction from the respective counterparties. For the same reason, in the case of the VC-Close protocol, the intermediate
party has to make sure that it holds the signatures of refund transactions of
the reactivated pairwise payment channel before signing any of these itself toensure that either both or no pairwise payment channel is reactivated.

4.11

Conclusion

We use timelocks to create an order in which transactions in our constructions
are valid. However, different techniques for invalidating transactions or replacing transactions offchain might be used instead to have less restrictions on the
lifetime of a virtual channel. For this we can adapt techniques as introduced for
the Lightning Network [112] or eltoo [108].
Lastly we argue that our construction provides incentive for research into
route discovery protocols that yield multiple paths. We reason that while virtualchannel expand the payment channel network topology, they also reduce thetotal capacity of the channels involved. Even though virtual channel allow for
shorter paths as well as increase the number of possible paths from a source toa target, larger payments that exceed the capacity of a virtual channel have to
be routed through multiple paths to be able to ulitize this, for instance using
the AMP protocol [104].

74

CHAPTER 4. LIGHTWEIGHT VIRTUAL PAYMENT CHANNELS

Chapter 5

Payment Trees
5.1

Introduction

Blockchain based decentralized ledgers as introduced by Nakamoto [100] haveenjoyed popularity and received interest from the research community and practitioners. Consensus protocols allow these ledgers to be operated by mutuallydistrustful parties at the cost of limited throughput. For example, Visa as acentralized system can process orders of magnitude more transactions within agiven time frame than the most prominent blockchains as Bitcoin and Ethereum.
The main motivation for the development of offchain protocols is to close
the gap in transaction throughput. The idea is to allow parties to interact witheach other without interacting with the ledger, while still being able to use
it to resolve disputes. Offchain protocols operate on channels that are createdbetween two parties. Channels hold a state which can be enforced on the ledger.
Payment channels [44, 108, 112] store the number of coins the two parties havelocked inside that channel. Offchain protocols provide a means to alter thisstate arbitrarily often and thus improving the transaction throughput in theoverall system.
Individual channels can be extended to channel networks, e.g. PCNs Lightning [112] and Raiden [7]. This is done using techniques, such as HTLC [25, 112],that allow for payments of b ∈ N coins across a path of payment channels oflength n ∈ N. This is performed by executing the same payment on each channel
within the payment path atomically. All parties on the payment path have tolock the payment amount for a duration of up to locktime. The opportunity costa party has to invest is the collateral [98] which equals the payment amount b
multiplied by the locktime. In turn, parties can impose fees to invest collateral.
In the case of HTLC, a party’s collateral equals O(nb∆) in the worst-case where∆ is a parameter of the underlying ledger and is the upper limit of the time ittakes for a transaction to be included in the ledger.
High collateral investments can be exploited by malicious adversaries to perform grieving and denial-of-service attacks[99, 109]. For example, an attacker
75

76

CHAPTER 5. PAYMENT TREES

might operate a channel to collect fees by forwarding payments. However, payments might be routed through competing channels instead. To sabotage thecompetitor, the attacker can route a payment through these channels without
the intent of executing it, locking the competing channel’s coins for the entiretyof the locktime. These channels experience a denial-of-service scenario by being
unable to forward any other payments, losing fees that the attacker can collectthrough their own channel. Performing this attack on a large scale can result
in denial-of-service for the whole PCN. On a lower scale, a griever might force
parties to lock away their funds for as long as possible by delaying their cooperation until the last moment. An alternative form of this attack involves
routing multiple low value payments through a competing channel, up until apoint where the channel cannot add any further HTLCs even though it contains
enough coins. In the case of the Lightning network, these types of denial-ofservice attacks can lock all of a channel’s coins for up to around 2 weeks [99].
1

For HTLC the total collateral locked over a whole payment path is O(n2 b∆)
and therefore quadratic in the payment paths length. Sprites [98] reduce thecollateral of each party to O(b(n + ∆)) and the total collateral to O(bn(n + ∆))by utilizing a smart contract. This is considered to be constant and linear respectively, since n << ∆ such that n + ∆ < 2∆. Sprites mitigate the damage
done by a possible attacker but its implementation is limited to ledgers withsmart contract capability. The Atomic Multi-Channel Updates (AMCU) protocol [51] is an attempt to close this gap and enable payments with constantcollateral on ledgers without smart contract capabilities. However, even though
AMCU is formalized as a functionality within Canetti’s UC Framework [31],the very last, but crucial step, of the updateState function does not seem to bepresented in the description of the AMCU protocol, and neither addressed by
the simulator [51]. This gap results in a vulnerability that can be exploited bya malicious adversary to steal funds from honest parties.
Related Work. Payment channels [44, 108, 112] themselves allow only foroffchain payments between two parties. Offchain protocols such as HTLCs[25, 112] and Sprites [98] allow to perform payments across paths of channels allowing for the implementation of PCNs. Prominent examples are theLightning Network [112] and Raiden [7]. Although offchain protocols exist thatcreate new virtual channels out of two existing channels as Perun [47, 50] andLightweight Virtual Payment Channels [66], this work focuses on performing
individual payments across a PCN. In the following we consider a payment ofb ∈ N coins across a path of n ∈ N channels involving parties P0 , . . . , Pn .
The most prominent technique is based on HTLCs [25, 112], which are scriptsthat perform conditional payments within a channel: The payer locks funds
into the contract that are paid out if the payee can present a secret x such thaty = H(x) where H is a cryptographic hash function. Otherwise, after time
1 https://cointelegraph.com/news/developer-reveals-biggest-unsolvable-lightning-attackvector.

5.1. INTRODUCTION

77

locktime the payment times-out and the payer can reclaim their funds. This
contract is replicated along all channels within a payment path. The payment
is performed as soon as Pn reveals x to their predecessor who then learns thevalue of x allowing them to claim the payment from their predecessor in turn.
An attacker Pi , 0 < i ≤ n might attempt to delay revelation of x to theirpredecessor until briefly before expiration of the locktime. To allow Pi−1 toforward x in time, their locktime needs to be increased by at least ∆. This
results in a locktime in O(n∆) and a total locktime in Θ(n2 ∆).
Sprites [98] aim to reduce the locktime of a party up to a constant O(n + ∆)where n << ∆. This is done by setting up a smart contract entity called PreimageManager, s.t. submitting x to the PreimageManager allows to broadcast it
to all nodes within a payment path in at most n communication rounds. The
protocol requires creation of a smart contract, making it unavailable to script
based ledgers as Bitcoin. AMCU [51] attempts to close this gap, i.e. compatibility with Bitcoin, by introducing an approach for constant locktime payments
without the need of smart contracts. AMCU sets up payments on each channel within a payment path that are performed on the condition that an Enabletransaction is created, upon which all payments are performed atomically. However, this Enable transactions results in several issues. For one, its size grows
linearly in the payment path’s length, making its implementation prohibitive forledgers which have an upper limit for block size and transaction size. Moreover,no party has control over all of the Enable transaction’s inputs. A malicious
adversary can make two parties collaborate to double spend one of the Enabletransaction’s inputs, such that no party is able to enforce the payment on theledger. If the double-spending is timed appropriately, this can lead to an attacker stealing funds from honest parties. Details are shown in Appendix 5.3.3.
Jourenko et al. [66] proposed an offchain protocol that takes two channels γAand γB as input, one between PA and PI and one between PI and PB and createsa new channel γ v between PA and PB . As this approach is not optimized forindividual payments, using it for this purpose would result in excessive collateralas parties would need to lock away more coins for a longer duration as in existing
approaches. However, we re-use techniques from the lightweight virtual payment
channel construction for the Payment Tree protocol.
Our Contributions. Our contributions are threefold. 1) We present an attack on AMCU performed by a malicious adversary. 2) We present Payment
Trees that allow for payments across paths within a PCN without the needof smart contracts, requiring only logarithmic individual collateral O(b∆ log n)
while requiring only linear total collateral O(nb∆) such that its performance iscomparable to Sprites. 3) We provide efficiency and security analysis of Payment
Trees, proving the properties Balance Security and Liveness.
Structure. In the remainder of this work, first, we provide background to thiswork in Section 5.2. We give an outline of the Channel Closure attack in Section
5.3 while supplementing a formal description in Appendix 5.3.3. Next, we give

78

CHAPTER 5. PAYMENT TREES

an informal overview of the Payment Tree protocol in Section 5.4. Afterwards,
we introduce the types of transactions used for our construction in Section
5.5 before introducing Payment Trees in Section 5.6 followed by efficiency andsecurity analysis in Section 5.7. We conclude in Section 5.8.

5.2

Background

5.2.1

Hashed Timelock Contracts

Hashed Timelock Contracts. Let P0 , P1 , . . . , Pn , n ∈ N be parties whereparties Pi−1 and Pi , i ∈ {1, . . . , n} control channel γi . HTLCs are used toperform payments of b ∈ N coins from P0 to Pn by replicating the payment
on each channel γi within a payment path γ1 , . . . , γn from P0 to Pn . (1) On achannel γj , j ∈ {1, . . . , n} the payment is performed by extending the channeltree with a conditional payment: If the payee Pj can show the pre-image x ∈N of a hashed value y = H(x), where H is a cryptographic hash function,
they will receive b coins from the payer Pj−1 . However, after expiration ofa locktime tj the payment expires and the payer Pj−1 will have their coins
refunded instead. (2) Only after the conditional payments are set up on all
channels, the payment is executed atomically by having Pn show the pre-image
x to Pn−1 , proving that they have the capability to claim the coins on the ledger
through the conditional payment. In turn, Pn−1 learns the pre-image x s.t.
they can show it to party Pn−2 reclaiming the coins they forwarded to Pn . The
information on x propagates through the whole payment path in this manner.
(3) Lastly, to keep the payment offchain, the parties need to consolidate thepayment on each channel respectively. This is done by updating the channeltree. The conditional-payment is removed and the b coins that were locked into
the channel are credited to the payee. At this point the channel-tree has thesame form as before the payment, but with updated balance distribution toaccount for the payment. This ensures that the channel-tree does not grow insize with each payment, thus fulfilling the efficiency requirements of an offchain
protocol. Note that, if the payer Pj−1 does not cooperate with consolidation,
payee Pi can reclaim their coins by resolving the conditional payment on theledger instead. Due to this the timelock tj has to be chosen s.t. Pi has enoughtime to do so before the conditional payment expires, even if they learn the preimage from Pi+1 at the last moment just shortly before expiration of timelock
tj+1 . Thus the relation ti ≥ ti+1 + ∆ has to hold, making the locktime growlinearly with the payment path’s length. This results in a collateral cost ofbti ∈ O(bn2 ∆) which is quadratic in the path’s length.
The Wormhole Attack. The HTLC protocol is vulnerable to the wormhole
attack [90]. An adversary controlling two parties Pi , Pj , 1 ≤ i ≤ j + 2 ≤ n − 1within a payment path can prevent intermediaries k, i < k < j to participate at
the payment and receive their fees by having Pi forward pre-image x to Pi−1
after Pj learns it from Pj+1 and without forwarding it to party Pj−1 .

5.2. BACKGROUND
Funding UTXOs

u𝖿𝗎𝗇𝖽𝗂𝗇𝗀,𝒫0,𝒫1

1) Setup
Setup Tx

2) Lock
Lock Tx

4) Enable

3) Consume

Enable Tx

Consume Tx

After time T𝗅𝗈𝖼𝗄:b coins to 𝒫1

b coins to 𝒫0

Setup Txu𝖿𝗎𝗇𝖽𝗂𝗇𝗀,𝒫1,𝒫2

Lock Tx

Consume Tx

After time T𝗅𝗈𝖼𝗄:b coins to 𝒫2

Lock Tx

Consume Tx

After time T𝗅𝗈𝖼𝗄:b coins to 𝒫nb coins to 𝒫1

Setup Txu𝖿𝗎𝗇𝖽𝗂𝗇𝗀,𝒫n−1,𝒫n79b coins to 𝒫n−1

Figure 5.1: Informal illustration of AMCU as a transaction-tree.

5.2.2

Atomic Multi-Channel Updates

Although the Sprites protocol reduces a party’s collateral to O(b(n+∆)), AMCU
is the first proposal to reduce the collateral for UTXO based ledger that do notuse smart contracts.
To perform an offchain payment AMCU operates in four phases in which
the transaction tree shown in Figure 5.1 is created. 1) In a Setup phase b coinsfrom Pi−1 ’s balance are split up from the channel using the Setup transaction.
2) In the Lock phase the Lock transaction is created which spends Pi−1 ’s b coinsfrom the Setup transaction and pays out all coins back to Pi−1 after expirationof time Tlock . 3) In the Consume phase the parties create a Consume transaction
paying the b coins to Pi , however, instead of spending the Setup transaction
it spends a not-as-of-yet created Enable transaction. 4) In the Finalize phase,first a Disable transaction is created that spends the Enable transaction after
expiration of time Tlock and returns the b coins to Pi−1 in the same manner as
the Lock transaction does. Lastly the Enable transaction is created spending b
coins of all Setup transactions on the payment path and creating the UTXOs
that are spent by each channel’s Consume and Disable transactions.
AMCU achieves atomic payment across the whole payment path by creating
the Consume transactions to have the Enable transaction as common ancestor.
As soon as it is signed, all Consume transactions can be committed to the ledger,
thus rendering each payment on the payment path enforceable. However, thisapproach is impractical. The size of the Enable transaction grows as the numberof its inputs and outputs increases and therefore its size grows linearly with thepayment path’s length n. Payments across long parts cannot be performed if it
exceeds the limits of a transaction’s size.

80

CHAPTER 5. PAYMENT TREESThe security of the AMCU protocol is attempted to be proven within Canettis UC Framework [31] by presenting a simulator that shows that the AMCU
protocol realizes an ideal functionality PCN+ . However, while its updateState
function, that is used to perform payments across a payment path, concludes
with a consolidation step that atomically applies the payment on each individual channel within the payment path, this step is skipped within the AMCU
protocol and not addressed by the simulator. Exactly this gap between ideal
functionality and protocol is the vulnerability that allows a malicious adversary
to have corrupted parties potentially steal funds from honest parties. We introduce the Channel Closure attack formally in Appendix 5.3.3, in which a pair ofintermediate parties within a payment path can steal funds from honest parties
executing the AMCU protocol.

5.3

The Channel Closure Attack on AMCU

In the following we present the Channel Closure attack informally to present an
overview of the approach. A formal definition, discussion and cost analysis of
the attack is provided in Section 5.3.3.

5.3.1

The Vulnerability

While the Enable transaction is the core of the AMCU construction, it also
seems to be its vulnerability. While the Enable transaction receives inputs fromeach channel, no party has control over all channels within the payment path.
At any time, two parties sharing a channel can maliciously spend a UTXO thatis provided as input of the transaction, or as input to any of its ancestors within
the transaction tree. When this happens, the Enable transaction cannot becommitted to the ledger and all parties have their coins refunded through Locktransactions. Effectively, no party can enforce payment after execution of the
AMCU protocol. On top of that, an adversary can take this further, performinga Channel Closure attack to steal funds from honest parties. We remark that
PCN payments require a consolidation step in which a payment is included
within the parties’ individual channels. While the functionality PCN+ modeling
AMCU performs a consolidation step atomically on all channels, this step isomitted by the AMCU protocol. Second, performing the consolidation step
atomically on all channels is highly non-trivial as atomic operations on multiple
channels is exactly the problem statement that protocols such as HTLCs, Sprites
and AMCU themselves attempt to solve.

5.3.2

Intuition on The Channel Closure Attack

The attack is performed by abusing exactly the two observation from the previous section. First, the adversary corrupts two parties within a payment path
Pi and Pi+1 . These parties cooperate in execution of the AMCU protocol rightup until the consolidation step. Then, Pi performs the consolidation step with

5.3. THE CHANNEL CLOSURE ATTACK ON AMCU

81

Pi−1 on channel γi−1 while Pi+1 does not cooperate with Pi+2 to consolidate
the payment on channel γi+1 . Next, Pi and Pi+1 close their channel γi such that
the Enable transaction cannot be committed to the ledger. This allows Pi+1
to reclaim coins from Pi+2 using their shared Lock transaction. Effectively, Pi
received the payment amount from Pi−1 on γi through consolidation, while Pi+1
did not forward the payment.

5.3.3

The Formal Channel Closure Attack

Informally, an adversary can attack AMCU by corrupting two parties Pi and
Pi+1 that share channel γi along a payment path. First, parties cooperatein execution of the protocol right until after creation of the Enable transaction at which point the protocol concludes. We observe that if the protocol is
not followed up by a consolidation step as in the ideal functionality PCN+ , Pi
and Pi+1 can close their channel γi maliciously, e.g. by double-spending theUTXO used as input into their Setup transaction. This prohibits commitmentof the Setup transaction to the ledger and, as it is the ancestor of the Enabletransaction which in-turn is common ancestor of all Consume transactions, noConsume transaction can be committed to the ledger, effectively reverting thepayment. After the execution of the protocol, no party can enforce the payment
by committing the Consume transactions. Performing the payment requires a
final consolidation step, as defined in functionality PCN+ , allowing any party to
enforce the payment on their ledger through the channels they participate in.
It is essential that the consolidation step is done atomically on all channels
within a payment path, as otherwise this could lead to honest parties losing
funds. However, this step is non-trivial as performing a state transition on
multiple channels atomically is the very problem statement HTLCs, Sprites
and AMCU approach to solve. In the following we present the Channel Closureattack that allows a malicious adversary to have corrupted parties steal funds
from honest parties as long as at most n − 2 out of n channels are consolidated
atomically.
In the following let P0 , . . . , Pn be parties where parties Pi−1 and Pi , i ∈{1, . . . , n} control channel γi . Let Si be the setup transaction and Li be theLock transaction for channel γi respectively. The parties perform a payment ofb ∈ N coins over the payment channel path γ1 , . . . , γn using the AMCU protocol.
If the adversary can influence the order of channel consolidation then the attack
can be performed with n ≥ 2 where at most n − 1 channels are consolidated
atomically. Otherwise, we require n ≥ 3 where at most n − 2 channels areconsolidated atomically.
The Channel Closure Attack
The Adversary. The adversary is created according to AMCU’s adversarialmodel. At beginning of the protocol, the adversary can corrupt n − 1 parties s.t.
it receives the party’s internal state and all subsequent incoming and outgoing
communication is routed through them instead. This corruption is static and82

CHAPTER 5. PAYMENT TREES

the adversary cannot switch corrupted parties or corrupt any additional parties
during execution of the protocol. The adversary is malicious and can deviate from the protocol arbitrarily, however, it is computationally polynomiallybounded.
The adversary succeeds if the set of corrupted parties holds strictly more
funds compared to when all Consume transactions are committed to the ledger.
The Approach. The corrupted parties steal coins by, first, executing theprotocol correctly until the consolidation phase. They pick a party Pi , i ∈{1, . . . , n} where channel γi is consolidated before γi+1 . After they receive
coins through consolidation of γi , two parties γj−1 and γj close channel j suchthat Pi has their money returned through the Lock transaction Li+1 instead offorwarding the coins. There are a few edge cases: (1) If i = j + 1 then channel
γi+1 is controlled by the corrupted parties, so we require γi is consolidated before
γi+2 instead; (2) if i = n then Pi is already the payment’s recipient. In thiscase, we require P0 to be corrupted as well, such that Pn receives their funds
before P0 pays them out.
Channel Closure Attack. The adversary picks i, j ∈ {1, . . . , n}, i 6= j suchthat following conditions hold: (1) If i 6= j − 1, then γi is consolidated before
γ(i+1) mod n , otherwise γi is consolidated before γ(i+2) mod n ; (2) if γ(j+1) mod n
is consolidated before γ(i+1) mod n then γ(j−1) mod n is consolidated before thechannel γ(i+1) mod n . The adversary corrupts Pi , Pj−1 and Pj . If i = n theadversary also corrupts P0 . Upon starting the protocol, the adversary behaves
honestly and collaborates with the execution of the AMCU protocol up until the
Consolidation step. After Pi receives funds through consolidation of γi , they
do not respond to any parties requesting consolidation of their channels, butinstead the adversary orders Pj−1 and Pj to close γj by spending the UTXO
that is the input of their Setup transaction Sj .
Discussion
In the general case the adversary needs to corrupt at least 4 parties, thus theattack requires n ≥ 4. However, if the adversary can influence the order inwhich channels are consolidated, in the case of n ≥ 3 they can always pick
1 ≤ i = j −1 ≤ n−2 and reduce the parties they need to corrupt to 2. Moreover,note that if the order in which channels are consolidated is not known a-priori,
the adversary has to guess values for i and j. We assume the adversary picks
values for i and j randomly out of a uniform distribution of all possible values,
i.e. 1, . . . , n. The probability to guess one out of n parties for the value for iequals at least 1/n. As i 6= j, the value of j has to be guessed out of n − 1parties which equals a probability of at least 1/(n − 1). Thus the probability
for the adversaries success is at least 1/((n − 1)n) which is not negligible.
Cost Analysis. Performing the attack requires the adversary to commit transactions to the ledger which incurs costs to the adversary. As such the attack

5.4. PROTOCOL OVERVIEW

83

is only attractive to a rational adversary if it would not result in a net loss.
In the following we denote the adversary’s cost by the amount of transactions
that have to be committed to the ledger. We observe that, to perform the attack the adversary picks two channels γi and γj and succeeds if they guessed
the order in which channels are consolidated correctly. If the adversary fails toguess correctly they can abort the attack and proceed with the protocol honestly and avoid cost. Otherwise the adversary has to spent the Funding UTXO
of γj requiring one transaction. In the highest cost scenario the adversary has
to commit all Lock transactions they are involved in to the ledger. In the worst
case the adversary has to corrupt 4 parties, i.e. Pi , Pi+1 , Pj−1 , Pj , such thatthey are involved in up to three Lock transactions, i.e. Li+2 , Lj−1 , Lj+1 . As γi
itself is already consolidated Li is not committed to the ledger. Moreover since
the adversary controls channels γi+1 and γj they can opt to modify the channel
states arbitrarily offchain and avoid commitment of Li+1 and Lj . Committinga Lock transaction requires commitment of two transactions, i.e. the Setup andthe Lock transaction itself. Overall, the adversary’s cost equals committing up
to 1 + 2 · 3 = 7 transactions to the ledger.

5.4

Protocol Overview

In the following, we define communication and adversarial models, before giving
an overview of the protocol. Lastly we define the properties of our construction.

5.4.1

System Model

Communication Model. Communication between parties occurs in rounds.
Any message sent within one round is available to the recipient at the beginningof the next round. The duration of any round has an upper limit.
Adversarial Model. We define an Adversary A consistent with related work
[66, 51, 98]: At the beginning of protocol execution, the adversary can staticallycorrupt up to n of n + 1 parties, receiving their internal state and having allcommunication to and from these parties be routed through the adversary. The
adversary is malicious and can make any corrupted party deviate from theprotocol. Moreover, within each communication round, the adversary can delay
and re-order all messages sent.

5.4.2

Overview

We illustrate the life-cycle of the Payment Tree protocol for a payment of 2 coinsfrom Alice to Charlie across two channels using Figure 5.2 and Figure 5.3. The
protocol’s approach is to take two channels, one between parties Alice and Bob,
one between parties Bob and Charlie and construct a transaction tree that effectively creates a virtual channel [66] optimized for a one-time payment between
Alice and Charlie. Our construction utilizes two approaches to perform updates

84

CHAPTER 5. PAYMENT TREES

LedgerChannel A
Alice : 5

Funding UTXO
Bob
& Charlie :Channel B
Bob : 4

5

Split
Transactions
Alice & Bob : 5

7

Funding UTXO
Alice& Bob :

7

LedgerFunding UTXO
Alice& Bob :

Bob : 2

Funding UTXO
Bob
& Charlie :5

Ledger

7

Split
Transactions
Alice & Bob : 5

Alice & Bob : 2

5

Bob & Charlie: 3

Bob : 2(b) Split of funds
LedgerChannel A
Alice : 3

Funding UTXO
Alice& Bob :

Bob : 2Merge
2

Bob & Charlie: 2Channel B
Bob : 2

Alice : 2

Charlie : 1

Alice & Charlie :Funding UTXO
Bob
& Charlie :Bob : 2

Bob & Charlie: 2

Bob & Charlie: 3Charlie : 1(a) Original State
Funding UTXO
Alice& Bob :

Alice & Bob : 2

RefundChannel A
Alice : 3

Bob : 2

RefundAlice : 2

Channel B
Bob : 2

Charlie : 1(c) Merge of trees

7

Split
Transactions
Alice & Bob : 5

Alice & Bob : 2

Channel A
Alice : 3
Bob : 2

Merge
Alice & Charlie :Funding UTXO
Bob
& Charlie :52

Bob & Charlie: 2

Bob & Charlie: 3

Bob : 2Channel B
Bob : 2

Charlie : 1

PunishAlice : 2

RefundAlice : 2

PunishCharlie : 2(d) Securing funds

Figure 5.2: Stepwise construction of a Payment Tree across two channels. Boxes
with straight corners represent channel trees displaying their state. Boxes withround corners represent transactions displaying output UTXOs. Edges indicate
which transactions spend the UTXO at their origin.

to transaction trees atomically. On the one hand, we use these techniques toempower the intermediary Bob to ensure correctness of the protocol, while on
the other hand, we incentivise Bob to actually do so by means of punishment.
Our construction consists of multiple transaction tree updates. Updates aredone using the invalidation by timelock technique, but for simplicity we leave
the details to Section 5.6.
Payment Tree Construction. Figure 5.2 depicts construction of a Payment
Tree between Alice, Bob and Charlie. Construction consists of three atomic
transaction tree updates. We note that the balance distribution between theparties remains unchanged between the updates and no payment is executed.
Alice and Bob as well as Bob and Charlie share a channel as depicted in Figure
5.2a. (1) Then, as shown in Figure 5.2b we update both trees by introducing a
Split transaction that spends the channels’ Funding UTXOs and creates two new
Funding UTXOs each. One UTXO contains the payment amount and is fundedby coins from Alice, who is payer, and Bob, who is intermediary, respectively.
The other UTXO contains the remaining coins and is used as Funding UTXO
to reopen both channels which can be used for further payments within thechannels or further Payment Tree constructions. (2) Next as shown in Figure
5.2c both separate transaction trees are combined using a Merge transaction.
This transaction creates two UTXOs. One UTXO requires Bob’s signature to
be spent and contains his collateral. The other UTXO is a Funding UTXO
requiring the signatures of Alice and Charlie and it contains Alice’s payment
to Charlie. At this point, the coins are given to Alice. (3) Lastly, as shown5.4. PROTOCOL OVERVIEW
LedgerFunding UTXO
Alice& Bob :

7

Split
Transactions
Alice & Bob : 5

Alice & Bob : 2

Channel A
Alice : 3

Alice & Charlie :Funding UTXO
Bob
& Charlie :52

Bob & Charlie: 2

Bob & Charlie: 3

PunishLedgerAlice : 2

Split
Transactions

Funding UTXO
Alice& Bob :

Alice & Bob : 5

Bob : 2Merge
Bob : 285

Payment
Charlie : 2

Channel B
Bob : 2

Charlie : 1(a) Payment

PunishCharlie : 2

7

Funding UTXO
Bob
& Charlie :5

Alice & Bob : 2

Consolidation
Channel A
Alice : 3
Bob : 2

Bob & Charlie: 2

Bob & Charlie: 3Channel B
Bob : 2

Bob : 2

Charlie : 2

Charlie : 1(b) Consolidation

Figure 5.3: Payment and Consolidation using Payment Trees. Figure 5.3a modifies the Payment Tree to forward the funds in the Merge transaction’s Funding
UTXO to the payee. Figure 5.3b splits up the Payment Tree and distributes
funds according to the Payment Tree’s state in Figure 5.3a.
in Figure 5.2d, before we can proceed with a payment, the funds within the
Merge transaction’s Funding UTXOs need to be secured in case two parties, forexample Bob and Charlie, collude to spend their Merge transaction’s or Split
transaction’s input with a different transaction. This attack is similar to the
Channel Closure attack described in Section 5.3 and would disable commitmentof the Merge transaction. However, we observe that all UTXOs that can bespent for this attack require Bob’s signature. Respectively, in this scenario we
can uniquely identify Bob as malicious. In order to punish Bob and secure thefunds of Alice and Charlie respectively we create Punish transactions. Thesetransactions spend the same Funding UTXOs as the Merge transaction but
have a timelock that is higher than that of the Merge transaction by at least∆. Due to this, Bob can always avoid commitment of a Punish transaction
by committing the Merge transaction to the ledger. However, in case Bob
acted maliciously such that the Merge transaction cannot be committed to theledger, Alice and Charlie can reclaim their coins from Bob through the Punishtransactions.
Payment and Consolidation. Figure 5.3 depicts payment and consolidation
using a Payment Tree. Assuming a fully constructed Payment Tree as shown in
Figure 5.2d a payment is executed by giving the coins within the Merge transaction’s Funding UTXO to Charlie instead of Alice. As shown in Figure 5.3a thischanges the balance distribution represented by the transaction tree, reducing
Alice’s coins by 2 and adding those to Charlie’s balance. A consolidation requires one atomic transaction tree update as shown in Figure 5.3b. This update
spends the UTXOs within the Merge transaction’s inputs and gives the coins to
Bob and Charlie respectively. Note that this step does not change the balance
distribution between the parties. Bob needs to make sure that this update isdone atomically s.t. he avoids commitment of a Punish transaction. At thispoint the transaction trees are separate and in control of each channels’ members respectively. Both pair of parties can now perform a last transaction tree
update that replaces the respective transaction tree with a channel as shown in
Figure 5.2a but that now represents the new balance distribution instead.

86

5.4.3

CHAPTER 5. PAYMENT TREES

System Goals

In the following we define the desired properties of our protocol.
Theorem 5.4.1 (Balance Security). Outside of performing the intended payment, the sum of a honest party’s coins is not reduced by participation in the
Payment Tree protocol.
Theorem 5.4.2 (Liveness). Eventually any honest party receives access to theircoins through UTXOs spendable with a witness consisting of a signature corresponding to their verification key.

5.5

Transactions

We use three types of transactions. Split transactions are used to split off
coins from one channel, making them available to our construction in form of aFunding UTXO. Payout transactions take a Funding UTXO as input and pay
the money to one of the two parties involved in it. Lastly, the Merge transaction
is used to combine the Funding UTXOs that were split off two channels by taking
them as input, paying out the intermediary’s coins out as collateral and creating
a Funding UTXO between the two remaining non-intermediary parties.

5.5.1

Split Transactions

Split transactions are of form T rsplit = (Uin , Uout , t) where Uin = {ref(fγ )} consistof one Funding UTXO provided by the channel-tree of γ, Uout = {fchange , fpay }consists of two Funding UTXOs. It holds that fchange .b + fpay .b = fγ andfpay .b = b. Moreover, fγ .π = fchange .π = fpay .π, i.e. all Funding UTXOs areshared between the same parties. The function call SPLIT(γ, b, t) creates a Split
transaction as described above and returns fpay . A function call to UNSPLIT(γ)
consolidates the transaction into the channel by updating the channel’s balance
distribution with the split off balance. Additionally it sets up a channel between
both parties by constructing a channel-tree with Funding UTXO fchange as root.
Split transactions are used to take off b coins from each channel to be used forour construction. They are used to avoid that the existing channels are affectedin case a corrupted intermediary misbehaves. Although we represent this byusing a Split transactions as done with Virtual Channels and AMCU, it could
be included similarly as conditional payments from HTLCs by placing a Funding
UTXO instead of a HTLC contract.

5.5.2

Merge Transactions

Merge transactions are of form T rmerge = (Uin , Uout , t) where Uin = {fpay,0 , fpay,1 }and Uout = {fpay , ucollateral }. The two Funding UTXOs that are provided as
input fpay,0 and fpay,1 are shared between parties PA and PB as well as between
parties PB and PC respectively. The newly created Funding UTXOs fpay inthe output is shared between parties PA and PC . The other UTXO within

5.6. OUR PAYMENT TREE CONSTRUCTION

87

the outputs is ucollateral which pays out funds to PB . Lastly it holds that thecoins in all UTXOs are equal, i.e. fpay,0 .b = fpay,1 .b = fpay .b = ucollateral .b = b.
The function call MERGE(fpay,0 , fpay,1 , t) is a short-hand notation to construct
a Merge transaction. We extend helper function OUT UTXO to accept a Mergetransaction as input as well. In this case it returns UTXO fpay . The helper
function IN UTXO takes a Merge transaction as input and outputs the UTXOs
that are used within its inputs, i.e. fpay,0 , fpay,1 . Merge transactions are used
to combine transaction trees into one, essentially opening up a virtual channel
between Alice and Charlie that can be used for a one-time payment.

5.5.3

Payout Transactions

Payout transactions are of form T rpayout = (Uin , Uout , t) where Uin = {f } is a
Funding UTXO and Uout = {upayout }. It holds that upayout pays out funds toa party P and f.b = upayout .b. The function call PAYOUT(f, P, t) constructs a
Payout transaction as described above. We extend helper function IN UTXO
to take a Payout transaction as input in which case it outputs the UTXO f .
Payout transactions are used at several points within our construction to serve
different roles as shown in Figure 5.4. Refund transactions are used wheneverFunding UTXOs are created. They are used to ensure that no funds are lockedaway within Funding UTXOs indefinitely even when any other party stops collaboration, which is essential to ensure the liveness property. Punish transactions are used to incentivise an intermediary to collaborate and ensure Mergetransactions can be committed to the ledger. Without those, in case a Mergetransaction is not committed to the ledger it could result in the loss of coins forCharlie in case the Refund transaction between Bob and Charlie is committed
to the ledger instead and after the payment between Alice and Charlie has been
performed. The Payment transaction is used to perform a change of the state,i.e. balance distribution, represented by the transaction tree, effectively performing a payment. Lastly, Consolidation transactions are used to deconstruct
the transaction tree by applying the payment on both original transaction trees
atomically. Without these, we cannot enforce the payment outside of committing the transaction tree to the ledger itself because of which the protocol would
not fulfill the efficiency requirements for offchain protocols and thus not beingclassified as such. We note that the Refund and Punish transactions between
Alice and Bob represent the same state s.t. the Punish transaction is redundant. However, for simplicity we opted to include both transactions making
the construction symmetric. Whereas similarly the Consolidation and Punishtransactions between Bob and Charlie do represent the same state in Figure
5.4, it is not possible to remove any of the transactions in the case where feesare paid to Bob which would be included within the Consolidation but not the
Punish transactions.

88

CHAPTER 5. PAYMENT TREES
1) Split

1) Channel Alice & Bob

Channel Tree

Alice & Bob :Alice : bA − b

Alice
& Bob

Alice & Bob :(bA + bB) − b

Bob : bBb5) Consolidation

3) Punish

1) Refund

Alice: b

Alice: b

3Δ

Δ

Bob: b4Δ2) Merge

2Δ

Alice & Charlie : b
Bob : b2) Refund

2Δ+4Δ4) Payment / Consolidation

2Δ+Δ

Alice: b

Charlie: b5) Consolidation

3) Punish

1) RefundCharlie: bCharlie: b

Bob: bΔ1) Split
Channel Tree

Bob & Charlie:

Bob& Charlie

Bob & Charlie:

3Δ

4Δ1) Channel Bob & Charlieb(b′B + bC) − b

Bob : b′B − bCharlie : bC

Figure 5.4: Transaction tree of a payment of b coins across 2 hops. Beforehand,
the respective balances are bA and bB for Alice and Bob, b0B and bC for Bob
in Charlie within their channels. Transactions are boxes with round corners
containing the UTXOs they create, whereas referenced UTXOs in inputs areindicated implicitly by arrows originating from the UTXO that is spent. Red
numbers indicate timelocks. Numbers atop the transaction indicate order of
construction whereas transactions with same numbers are constructed atomically. Channel trees are boxes with straight edges forming a black box.

5.6

Our Payment Tree Construction

We describe the construction of a payment tree in respect to our running example. Let P0 , P1 , . . . , Pn , n ∈ N, be parties where parties Pi−1 and Pi , i ∈{1, . . . , n} control channel γi . The protocol performs a payment of b ∈ N coinsfrom P0 to Pn . The value τ ∈ N represents the current time, whereas ∆ ∈ N is
the maximum time it takes for a transactions to be included in the ledger aftercommitting it. We illustrate our approach in Figure 5.4 for a two-hop payment,
i.e. for the case of n = 2. It is designed such that it can be extended to payment paths of arbitrary lengths. The construction is based on the overview given
in Section 5.4. Numbers indicate the order in which transactions are created,
whereas transactions with the same numbers are created atomically.

The Payment Tree Protocol. The protocol for constructing a Payment
Tree across a path of n channels is depicted in Algorithm 7. It makes use of
Algorithm 4 that allows an intermediary to atomically create two transactions,
Algorithm 5 that performs a construction step of the Payment Tree, and Algorithm 6 that performs a consolidation step of the Payment Tree.

5.6. OUR PAYMENT TREE CONSTRUCTION

89

Algorithm 4 Atomically signing two Payout transaction
1: function ATOMIC SIGN(T r0 , T r1 )Require: T r0 , T r1 are Payout transactions between three parties.
2:
f0 , f1 ← FUTXO(T r0 ), FUTXO(T r1 )3:
PI ← INTERMEDIARY(f0 , f1 )4:
PA , PB ← COUNTERPARY(f0 , PI ), COUNTERPARY(f1 , PI )5:
SIGN(T r0 , {PA }, {PI }), SIGN(T r1 , {PB }, {PI })6:
SIGN(T r0 , {PI }, {PA }), SIGN(T r1 , {PI }, {PB })7: end function

Figure 5.5: Algorithm that takes two Payout transactions as input and allows
the intermediary party to enforce that either both or no transactions are fully
signed.

5.6.1

Helper Functions and Sub-Protocols

Helper Functions. Function SIGN(T r, PS , PR ) is used to sign and exchange
signatures of transactions. It takes a transaction T r and two sets of parties PS
and PR as input. Each party in PS signs T r and sends the signature to eachparty in PR . This includes verification of signatures by the recipients. Function PARTIES takes a Funding UTXO as input and outputs a set containing
the two parties of which a signature is required to spend the UTXO. Function
INTERMEDIARY(f0 , f1 ) takes two Funding UTXOs f0 , f1 as input, if an intermediary exists, i.e. |PARTIES(f0 ) ∩ PARTIES(f1 )| = 1, then it returns theintermediary P ∈ PARTIES(f0 ) ∩ PARTIES(f1 ). Otherwise it returns ⊥. Function COUNTERPARY(f, P) takes a Funding UTXO and a party as input, if
P ∈ PARTIES(f ), then it returns its counterparty PC ∈ (PARTIES(f )) \ {P}.
Atomic Signatures. We assume a setting with two channels between threeparties. Protocol ATOMIC SIGN is shown in Algorithm 4. It enables theintermediary party to enforce that two transactions – one on each channel –are created atomically. This is done by having the intermediary party provide
signatures to both transactions only after they received all signatures from its
counterparties.
Merging Channels. Protocol MERGE as shown in Algorithm 5 takes two
Funding UTXOs f0 , f1 , an amount of coins b and a time t as input where f0
is shared between parties PA and PI , f1 is shared between parties PI and PB
and it holds that f0 .b = f1 .b = b. It creates a Merge transactions with timelock tm = t + 2∆ spending both Funding UTXOs, paying out b coins to PI
and containing a Funding UTXO holding b coins, which are paid out to PA
after time tm + 4∆ by means of a Payout transaction. This transaction tree
is created atomically as its root, which is the Merge transaction, is signed last.

90

CHAPTER 5. PAYMENT TREES

Algorithm 5 Construction Step of a Payment Tree
1: function MERGE(f0 , f1 , b, t)
2:
PI ← INTERMEDIARY(f0 , f1 )3:
PA , PB ← COUNTERPARY(f0 , PI ), COUNTERPARY(f1 , PI )4:
T rmrg ← MERGE(f0 , f1 , t + 2∆)
5:
T rref und ← PAYOUT(OUT UTXO(T rmrg ), PA , t + 6∆)
6:
T rpunish,A ← PAYOUT(f0 , PA , t + 3∆)
7:
T rpunish,B ← PAYOUT(f1 , PC , t + 3∆)
8:
SIGN(T rref und , {PA , PB }, {PA , PB })9:
SIGN(T rmrg , {PA , PB , PI }, {PA , PB , PI })10:
ATOMIC SIGN(T rpunish,A , T rpunish,B ) return T rmrg
11: end function

Figure 5.6: Creation of a Funding UTXO between two counterparties. Theintermediary can enforce atomic construction while Punish transactions provide
incentive.
Only after each party holds a fully signed instance of the Merge transaction, two
Punish transactions spending f0 and f1 and paying out b coins to PA and PB
respectively are created atomically using ATOMIC SIGN. These have timelocks
equal to t + 3∆. Note that the creation of the Merge transaction must not redistribute funds, i.e. the funds in f0 are paid by PA and the funds in f1 are paid
by PI . The Punish transactions are used to secure the funds within the Mergetransaction by paying out funds to PA and PB , if the Merge transaction cannot
be committed to the ledger. Timelocks are selected to perform transformations
on the existing transaction through the invalidation by timelock technique andalso to allow the construction to be performed iteratively. Timelock tm is selected s.t. a Consolidation transaction can be placed with timelock t + ∆ during
the protocol’s consolidation phase. Timelocks of the Punish transactions are
selected s.t. they are invalidated by the Merge transaction conditionally, i.e.
only if the Merge transaction can be committed to the ledger, the Punish transactions are invalid. The Payout transaction acts as a Refund transaction for
the new Merge transaction. Respectively we assign it a timelock of tm + 4∆
such that Consolidation, Merge and Punish transactions can be placed withtimelocks tm + ∆, tm + 2∆ and tm + 3∆ respectively. Note that if the Mergetransaction is on top of the Payment Tree s.t. it is not used for further channelmerges, the Refund transaction’s timelock can be reduced to tm + 2∆. Lastly, if
a transaction spends another transaction, its timelock needs to be larger by atleast ∆ to ensure that all transactions can be committed to the ledger as soon
as their timelocks expire.
Consolidation. Algorithm 6 takes a Merge transaction as input, invalidates
it by creating two Payout transactions atomically using the ATOMIC SIGN

5.6. OUR PAYMENT TREE CONSTRUCTION

91

Algorithm 6 Deconstructing Step of a Payment Tree
1: function CONSOLIDATE(T rmrg )2:
f0 , f1 ← IN UTXO(T rmrg )3:
PI ← INTERMEDIARY(f0 , f1 )4:
PA , PB ← COUNTERPARY(f0 , PI ), COUNTERPARY(f1 , PI )5:
T rA ← PAYOUT(f0 , PB , t + ∆)6:
T rB ← PAYOUT(f1 , PC , t + ∆)7:
ATOMIC SIGN(T rA , T rB )8: end function

Figure 5.7: Invalidating a Merge transactions and atomically updating the stateon the two original Funding UTXOs.

protocol that spend the Merge transaction’s inputs. Both consolidation transactions perform a payment by giving the funds to the payee. Note that the
protocol can be adjusted to cancel a payment by refunding the funds to thepayer instead.

5.6.2

The Complete Payment Trees Protocol

Algorithm 7 performs a payment from P0 to Pn by iteratively merging Funding
UTXOs, s.t. the Merge transactions form the nodes of a balanced binary tree
as illustrated in Figure 5.9. The algorithm takes the following inputs: (1) The
payment path γ1 , . . . , γn , (2) the payment amount b, and (3) time tmin . The
value tmin is negotiated by the parties and represents the maximum amount oftime the parties have to execute the protocol. The dispute protocol starts if
the protocol is not concluded until tmin . Note that even existing methods as
HTLCs have to account for tmin .
In the following we refer to a certain depth within this binary tree as level,
beginning with Split transactions on level 0. The algorithm maintains lists ofFunding UTXOs F U T XOi for each level i ≥ 0 of the binary tree, as well aslists of Merge transactions M RGj for each level j ≥ 1 of the binary tree. The
algorithm proceeds as follows. Add a Funding UTXO from each Split transaction to F U T XO0 in order (4 - 7) and create the Payment Tree by iterativeuse of the MERGE protocol level-by-level (8 - 18). The Merge transactions andFunding UTXOs created on level j are added to lists M RGj and F U T XOj
respectively and in order (12 - 13). Note that if there is an uneven amount ofFunding UTXOs within a level, we leave the odd one to be used in the level
above instead (15 - 17). The payment is executed after construction is concluded (19). Afterwards the payment tree is deconstructed in reverse order byexecuting the CONSOLIDATE protocol on each Merge transaction (20 - 24).
Lastly the Split transactions are removed and consolidation within all original
channels concludes (25 - 27).

92

CHAPTER 5. PAYMENT TREES

Algorithm 7 Payment Tree Construction
1: function PaymentTree(γ1 , γ2 , . . . , γn , b, tmin )2:
F U T XOi ← [], 0 ≤ i ≤ d(log n) − 1e3:
M RGi ← [], 1 ≤ i ≤ dlog ne
4:
for 1 ≤ i ≤ n do
5:fi ← SPLIT(γi , b, tmin )6:
Append fi to F U T XO0
7:
end for8:
for i = 0 until i = d(log n − 1)e do
9:
for 0 ≤ j ≤ b|F U T XOi |/2c do
10:Retrieve f2j , f2j+1 from F U T XOi
11:
T rmrg,j ← MERGE(f2j , f2j+1 , b, tmin + 2i∆)
12:
Append OUT UTXO(T rmrg,j ) to F U T XOi+1
13:
Append T rmrg,j to M RGi+1
14:
end for15:
if |F U T XOi | mod 2 = 1 then16:
Remove last entry of F U T XOi and append to F U T XOi+1
17:
end if18:
end for
19:
T rP ayment←
PAYOUT(OUT UTXO(M RGdlog ne [0]), Pn , tmin +2∆ log n + ∆)20:
for i = dlog ne until i = 1 do
21:
for T rmrg in M RGi do
22:
CONSOLIDATE(T rmrg )23:
end for24:
end for25:
for 1 ≤ i ≤ n do
26:
UNSPLIT(γi )27:
end for
28: end function

Figure 5.8: The full Payment Tree protocol from construction to consolidation.

Dispute. This protocol is executed at time tmin if the payment tree protocol
has not come to conclusion in an orderly manner. Every honest party submits
their transactions to the ledger as soon as their respective timelocks expire. This
will result in commitment of the payment tree onto the ledger where transactions are committed in order of their priority. If a Merge transaction cannot becommitted to the ledger, refunds and payments are done via Punish transactions.

5.7. COLLATERAL EFFICIENCY AND SECURITY ANALYSIS

93

…

Merge
A, N

…

Merge
A, E
Merge
A, C

Split

Split

A

…

Merge
C, E

B

…

Split

Split

C

Merge
(N-2), N

D

E

Split

…

N

Figure 5.9: Payment tree in the shape of a balanced binary tree.

5.6.3

Handling of Fees

Fees can be paid by the payer P0 and payee Pn or either of them alone tothe intermediaries to compensate for their invested collateral. Our approach tohandling fees is similar to the approach used for HTLCs, however, adapted to thebinary tree structure of Payment Trees. Any party acting as intermediary whencreating a Merge transaction receives cumulative fees from the other two parties
participating in the Merge transaction’s construction. The cumulative fee paid
to the intermediary is composed of two parts. For one, it contains the fees paid
to the intermediary themselves, and for another, it contains coins the party has
to forward to the parties who act as intermediaries of Merge transactions on thelower levels of the Payment Tree. For simplicity, in the following we assume thatthe path’s length is a power of 2, i.e. n = 2i , i ∈ N, the paid fees f are equal foreach intermediary and all fees are shared between payer P0 and payee Pn equally.
Then, a party that acts as intermediary of level i of the Payment Tree receives
fi = f + 2 fi−1
2 = f + fi−1 coins, where f1 = f . The fee fi is paid equally by theother two parties involved in the Merge transaction’s construction. Paymentof fees happens within Merge transactions by adding a fee to the collateral theintermediary receives. However, this raises the challenge that we have to ensurethat all transactions receive sufficient funding: The coins within a transaction’s
inputs have to cover all coins within their outputs. Moreover, to ensure that theconsolidation step can be performed, the collateral of the intermediary withina Merge transaction has to be at least as high as the coins within the Mergetransaction’s Funding UTXO [66]. Therefore, when performing the merge stepPhon level i every party has to have an additional balance of fi,cum = j=i fj ,whereas the collateral of a Merge transaction’s intermediary equals b+fi,cum +fi
where fi is paid equally from balances brought by the other two parties.

5.7

Collateral Efficiency and Security Analysis

In this section we discuss properties of the Payment Tree construction.

94

5.7.1

CHAPTER 5. PAYMENT TREES

Efficiency Analysis

Figure 5.10 depicts the efficiency properties of Payment Trees, comparing it
to existing approaches. We compare two metrics: (1) The collateral, and (2)the number of transactions that have to be committed to the ledger in case of
dispute. We do this for individual parties, as well as for the whole payment.
Commitment of each Merge transaction unlocks the collateral of one party.
To commit a Merge transaction located on level i of the payment tree it needs
to commit i transactions beforehand, i.e. i − 1 Merge transaction as well as a
Split transaction. This will happen at time 2∆i. As the height of the Payment
tree is limited by dlog ne it follows that any party invests b2∆i ∈ O(b∆ log n)collateral and has to commit i + 1 ∈ O(log n) transactions. Regarding the total
payment, we observe that there are 2ni Merge transactions on level i of the payPdlog nement tree. It follows that the total collateral equals the sum i=1 b2∆i 2ni =P∞Pdlog neb2∆n i=1 2ii . As i=1 2ii = 2 and each part of the sum is positive, it folPdlog nelows that the total collateral b2∆n i=1 2ii < 4b∆n ∈ O(b∆n) is linear in
the length of the payment path n. The number of transactions can be computed in a similar fashion, however, an intuitive approach is to recall that thetransactions form a balanced binary tree of height 1 + dlog ne which has at most
21+dlog ne ≤ 2n ∈ O(n) nodes. Although the collateral any individual party has
to invest is logarithmic, therefore higher than Sprites but lower than HTLCs, thetotal collateral incurred over the whole payment is linear in the path’s length.
This is comparable to the performance of Sprites and is by a factor of n lower
than the total collateral of HTLCs. A trade-off of Payment Trees is that anindividual party might have to commit up to O(log n) many transactions. Nevertheless the total number of transactions over the whole payment is comparable
to both, HTLCs and Sprites. Payment Trees provide a performance comparable
to Sprites without requiring a ledger with smart contract capability.

5.7.2

Anonymity

There are two metrics for anonymity for offchain payments. (1) Sender andReceiver privacy denotes whether sender and receiver of a payment are unknown for any intermediary, (2) path privacy denotes whether intermediaries
are anonymous to other intermediaries within a payment path. We compare
these privacy notions of existing approaches in Figure 5.11. While HTLCs inthemselves do not provide privacy guarantees, further work [87] introduced adjustments to provide privacy notions. Similarly, smart contracts do not provide
privacy guarantees and Sprites does explicitly not address any privacy notions,however, privacy might be addressed in future work.
The Payment Trees protocol leaks no information on intermediaries withina path if all intermediaries use pseudonyms when creating the transaction anddo not re-use their identities within the network. However, if the intermediaryat the topmost node of the Payment Tree is forcing a dispute that leads tothe commitment of all merge transactions to the ledger, all intermediaries, i.e.

5.7. COLLATERAL EFFICIENCY AND SECURITY ANALYSIS
MethodHTLC [112, 25]
Sprites [98]Payment Treepp CollateralO(b∆n)
O(b(n + ∆))O(b∆ log n)

pp Tr.
O(1)O(1)
O(log n)Total CollateralO(b∆n2 )O(b(n + ∆)n)O(b∆n)

95
Total Tr.
O(n)
O(n)
O(n)

Figure 5.10: Comparison of the performance of Payment Trees across the whole
payment (Total) and individually per party (pp).
MethodHTLC [112, 25]
Sprites [98]Payment Tree

Sender / Receiver Pr.
Yes
No
Yes

Path Pr.
O(1)O(n)O(1) / O(n)Smart Contracts
No
Yes
No

Figure 5.11: Comparison of the performance of Payment Trees regarding
anonymity and ledger requirements.

O(n), are leaked. However, if any part of the tree is committed to the ledger noinformation is leaked on whether it is the topmost node of the tree s.t. Senderand Receiver of the payment remain private. Thus Payment Trees has Senderand Receiver privacy.
Nevertheless, we denote that if an adversary attempts to learn the balancesof the channels within a channel network they can potentially observe any payments done within the network, breaking all privacy independent of the protocol
used.

5.7.3

Discussion of Attacks from the Literature

Denial of Service Attacks. The Payment Tree protocol mitigates existing
attacks such as the congestion and lockdown attacks[99, 109] on HTLCs that
aim to lock a channel’s coins within unfulfilled HTLCs. This is done by reducing
the total and individual collateral of payments. While a large scale DoS attack
on multiple channels is difficult as the total collateral of Payment Trees is linear
in the payment path’s length, a specific intermediary can be targeted to act
a intermediary on the highest level of the Payment Tree to pay a logarithmiccollateral. Another aspect of the Lockdown attack is that a channel is blockedby saturating the number of HTLCs applicable to a channel which is limited by
the maximum size of a transaction. The Payment Trees protocol mitigates thisby using Split transactions. Each pending payment requires the construction ofa Split transaction. This prevents that there is any transaction that increases insize depending on the number of pending transactions. However, a tradeoff tousing Payment Trees is the increased number of transactions that would need
to be committed to the ledger in case of a dispute.

96

CHAPTER 5. PAYMENT TREES

Wormhole Attacks. The Payment Tree protocol pays coins to intermediaries of a Merge transaction and they include fees for all intermediaries on lower
levels of respective sub-trees. An attack similar to the wormhole attack can be
performed by a corrupted intermediary when creating a Merge transaction byreplacing the Merge transaction’s inputs with UTXOs they control. Doing thisthey could take all fees that were intended to be forwarded to other parties while
preventing them to participate in the protocol. In contrast to the wormhole attack on HTLCs a wormhole-like attack on the Payment Trees protocol requires
making changes to the transaction tree which in-turn can be detected and prevented. We assume that either P0 and Pn are honest. Otherwise, if both arecorrupted the attack would only redistribute coins between corrupted parties
resulting in no net gain to the adversary. During creation of the Payment Treeall intermediaries send their view of the protocol to P0 and Pn , i.e. the Mergetransactions they are involved in. Having this information P0 and Pn can verify
correctness of the construction and abort the payment in the negative case.

5.7.4

Security Proofs

In the following we prove the protocol’s security properties defined in Section
5.4.3.
Theorem 5.4.1 (Balance Security). Outside of performing the intended
payment, the sum of a honest party’s coins is not reduced by participation in the
Payment Tree protocol.
Sketch of Proof. First, we consider the case in which the adversary does
not deviate from the protocol, but stops collaboration mid-way. We observethat due to the order in which transactions are (atomically) created, the funds
accessible for any party within Merge- and Payment transaction is unchanged,
except when executing the payment between P0 and P1 explicitly. Any party
receives their Funds by having the transaction tree be committed to the ledger.
Even if a corrupted party acts as intermediary and stops collaboration after
receiving signatures and before providing signatures themselves. As only theyrisk losing funds due to Punish transactions, having them selectively commit andwithhold transactions does not result in the loss of funds of their counterparties.
Next, we consider the case where the adversary corrupts two parties todouble-spend a Funding UTXO that is the input of a Merge transaction. Assume P ∈ {P1 , . . . , Pn−1 } is neither payer or payee of the overall payment andis honest. Moreover, the adversary double spends a Funding UTXO that is the
input of a Merge transaction T rmrg,A on level i. Note that for this to happen,
the party that acts as intermediary of T rmrg,A must be corrupted as either
Funding UTXO that is input of T rmrg,A requires its signature to spend it. If P
is not part of a transaction that is descendant of T rmrg,A they are unaffected
and do not lose funds. Otherwise, if they are part of T rmrg,A they are not theintermediary party as they are honest and they will receive b coins through a
Punish transaction. If they are not part of T rmrg,A , let j, i < j ≥ log n be the5.8. CONCLUSION

97

lowest level on which they are part of a Merge transaction that has T rmrg,Aas descendant. Then they must not be the intermediary, as otherwise, theywould have a descendant of T rmrg,A on a lower level. Therefore they are notintermediary and receive b coins through a Punish transaction on that level.
However, as they are neither P0 nor Pn they act as intermediary of a Mergetransaction on level k, j < k < log n which is descendant of T rmrg,A . On thatlevel P has to pay out b coins through one Punish transaction. Note that P does
not pay out b coins through two Punish transactions as otherwise they couldcommit the Merge transaction instead to avoid payout of any Punish transaction. Moreover, any party is intermediary of a Merge transaction only once
within the transaction. Overall, P’s balance equals b − b = 0 s.t. they do not
lose funds. The reasoning for P0 and Pn is analogous. As they are on the top
level of the Payment Tree, they have a Merge transaction that is descendant of
T rmrg,A and therefore do receive b coins. However, they are never intermediaryof a Merge transaction, s.t. their balance is b coins. Therefore, P0 and Pn do
not lose coins independently of whether they performed the payment between
each other or not.

Theorem 5.4.2 (Liveness). Eventually any honest party receives accessto their coins through UTXO spendable with a witness consisting of a signaturecorresponding to their verification key.
Sketch of Proof. All honest parties commit the transactions they are involved in as soon as their timelocks expire. First, we note that any transaction containing a Funding UTXO is created atomically with a Payout transaction that pays out the funds to a party that receives exclusive access to
it. Therefore, the adversary cannot have funds being locked within a Funding UTXO they share control of indefinitely. Although all transactions haveincreasingly higher timelocks, all transactions can be committed to the ledger
by time tmin +2∆ log n+4∆. By this time, no funds are locked within a Funding
UTXO and any funds can be claimed by one party exclusively through Payouttransactions. As Balance Security holds, no party loses funds when all Payouttransactions are committed to the ledger s.t. for any party it holds that by time
tmin + 2∆ log n + 4∆ they have exclusive access to all their funds.

5.8

Conclusion

Payment Trees provide competitive performance to state-of-the-art approaches
as Sprites, while having fewer restrictions to its employability by not requiring
smart contract capability. Thus providing the first secure alternative to HTLCs
for the Lightning Network.

98

CHAPTER 5. PAYMENT TREESChapter 6

Conclusion
In the following we conclude our work in the context of the related work in
Section 6.1, and highlight possible directions for future work in Section 6.2.

6.1

Conclusion

In this work we present a framework for Offchain Protocols for UTxO basedledger. We used this protocol to construct two protocols. (1) We constructeda protocol to create Lightweight Virtual Payment Channels and (2) we constructed a protocol for low collateral payments in PCNs. Both protocols are
the first secure solutions for virtual channel construction and low collateral payments that do not rely on Smart Contracts. Thus we show the feasibility of
our framework to deduct protocols that otherwise would only be possible to be
implemented on ledgers with smart contract capability. Moreover we presented
the first secure alternative to HTLCs for UTxO Ledger based PCNs.
However, this comes with tradeoffs. The largest trade-off is the size of thetransaction trees, i.e. the number of transactions they contain, that our constructions require, in contrast to solutions based on smart contracts. We notethat the total amount of transactions is linear with the payment path for Payment Trees and similarly linear for the number of hops a lightweight virtualchannel spans across the underlying PCN, is both comparable to the related
work. However, practically the number of transactions that would need to becommitted to the ledger in case of a dispute is larger than in the related work bya small constant. Moreover, while the virtual channel construction by Dziembowski et. al [46, 49] can be extended to use state channels our construction islimited to payment channels alone. However, we note that, to our knowledge,
there exists no construction for state channels that does not require smart contracts. Overall our work succeeded in reducing the gap between solutions for
UTxO based ledger and solutions relying on smart contracts, however, we do
not completely bridge the difference.
99

100

6.2

CHAPTER 6. CONCLUSION

Potential Future Work

There are several future directions of our work. (1) We argue that our framework can be used to re-visit problem statements in the related work and used
to present alternative constructions with different trade-offs. (2) The framework could be used to further present alternatives to protocols previously only
available for smart contract based ledgers. (3) While the Payment Trees protocol presents an approach with total collateral similar to Sprites, the individual
collateral of any party is up to logarithmic. We argue that it constitutes an interesting research question to verify whether this collateral is a limit for PCNs
on UTxO based ledgers. (4) While EUTxOs [32] are strict extensions of the
UTxO model such that our approach can be used directly with EUTxO without any changes, the higher expressiveness of the EUTxO model might improve
the performance of our protocols. Adapting our protocols to the EUTxO model
might present the first solution that allows inter-head communication for Hydra[33].

Chapter 7

Bibliography[1] Bip68.
https://github.com/bitcoin/bips/blob/master/bip0068.mediawiki. Accessed: 2018-11-28.
[2] c-lightningalightning
network
implementation
https://github.com/ElementsProject/lightning.
Accessed:
26.

in
c.
2019-03-[3] Comit whitepaper. https://www.comit.network/doc/
COMIT/white/paper/v1.0.2.pdf. Accessed: 2019-03-27.
[4] Cosmo. cosmos.network. Accessed: 2019-03-27.
[5] Lightningin
scriptless
script.
Mailinglist
https://github.com/lightningnetwork/lnd. Accessed: 2019-03-26.

port:[6] Ligthing network daemon. https://github.com/lightningnetwork/lnd. Accessed: 2019-03-26.
[7] Raiden network. raiden.network. Accessed: 2018-09-03.
[8] Ripple. ripple.com. Accessed: 2018-10-17.
[9] A
scala
implementationofthelightninghttps://github.com/ACINQ/eclair. Accessed: 2019-03-26.

network.

[10] Scriptless
script.
Presentation
slides:https://download.wpsoftware.net/bitcoin/wizardry/mw-slides/201705-milan-meetup/slides.pdf. Accessed: 2019-03-26.
[11] Speedymurmurs. https://crysp.uwaterloo.ca/software/speedymurmurs.
Accessed: 2018-10-17.
[12] tpec:
2p-ecdsa
signatures.
Githubrepository,
https://github.com/cfromknecht/tpec. Accessed: 2019-03-27.
101

102

CHAPTER 7. BIBLIOGRAPHY[13] Rapidly-adjusted (micro)payments to a pre-determined
https://en.bitcoin.it/wiki/Contract, 2011. Accessed: 2018-09-03.

party.

[14] Zcash. https://z.cash, 2016. Accessed: 2018-09-26.
[15] Syed Taha Ali, Dylan Clarke, and Patrick McCorry. The nuts and boltsof micropayments: A survey. CoRR, abs/1710.02964, 2017.
[16] Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, andLukasz Mazurek. Fair two-party computations via bitcoin deposits. In
Rainer Böhme, Michael Brenner, Tyler Moore, and Matthew Smith, editors, FC 2014 Workshops, volume 8438 of LNCS, pages 105–121. Springer,
Heidelberg, March 2014.
[17] Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, andLukasz Mazurek. Secure multiparty computations on bitcoin. In 2014
IEEE Symposium on Security and Privacy, pages 443–458. IEEE Computer Society Press, May 2014.
[18] Georgia Avarikioti, Felix Laufenberg, Jakub Sliwinski, Yuyi Wang, andRoger Wattenhofer. Incentivizing payment channel watchtowers. In Scaling Bitcoin, 2018.
[19] Georgia Avarikioti, Felix Laufenberg, Jakub Sliwinski, Yuyi Wang, andRoger Wattenhofer. Towards secure and efficient payment channels. arXiv
preprint arXiv:1811.12740, 2018.
[20] Iddo Bentov and Ranjit Kumaresan. How to use bitcoin to design fair protocols. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014,
Part II, volume 8617 of LNCS, pages 421–439. Springer, Heidelberg, August 2014.
[21] Iddo Bentov, Ranjit Kumaresan, and Andrew Miller. Instantaneous decentralized poker. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, pages 410–440. Springer,
Heidelberg, December 2017.
[22] Iddo Bentov, Rafael Pass, and Elaine Shi. Snow white: Provably secure
proofs of stake. Cryptology ePrint Archive, Report 2016/919, 2016. http://eprint.iacr.org/2016/919.
[23] Bitcoin Bip. Bip-0065. https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki, 2018. [Online; accessed 30-October-2018].
[24] Dan Boneh, Manu Drijvers, and Gregory Neven. Compact multisignatures for smaller blockchains. Cryptology ePrint Archive, Report
2018/483, 2018. https://eprint.iacr.org/2018/483.
[25] Sean Bowe and Daira Hopwood. Hashed Time-Locked Contract transactions. https://github.com/bitcoin/bips/blob/master/bip-0199.mediawiki,
2017. [Online; accessed 29-August-2020].

103[26] Simina Brânzei, Erel Segal-Halevi, and Aviv Zohar. How to charge lightning. arXiv preprint arXiv:1712.10222, 2017.
[27] Chris Buckland and Patrick McCorry. Two-party state channels withassertions. Third Workshop on Trusted Smart Contracts, 2019.
[28] Conrad Burchert, Christian Decker, and Roger Wattenhofer. Scalable
funding of bitcoin micropayment channel networks-regular submission. In
SSS, pages 361–377, 2017.
[29] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136–145. IEEE Computer Society Press, October 2001.
[30] Ran Canetti. Universally composable signature, certification, and authentication. In Proceedings. 17th IEEE Computer Security Foundations
Workshop, 2004., pages 219–233. IEEE, 2004.
[31] Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally composable security with global setup. In Salil P. Vadhan, editor,
TCC 2007, volume 4392 of LNCS, pages 61–85. Springer, Heidelberg,
February 2007.
[32] Manuel MT Chakravarty, James Chapman, Kenneth MacKenzie, Orestis
Melkonian, Michael Peyton Jones, and Philip Wadler. The extended utxo
model. In 4th Workshop on Trusted Smart Contracts, 2020.
[33] Manuel MT Chakravarty, Sandro Coretti, Matthias Fitzi, Peter Gazi,
Philipp Kant, Aggelos Kiayias, and Alexander Russell. Hydra: Fast isomorphic state channels.
[34] David Chaum. Blind signature system. In David Chaum, editor,
CRYPTO’83, page 153. Plenum Press, New York, USA, 1983.
[35] David Chaum, Amos Fiat, and Moni Naor. Untraceable electronic cash.
In Shafi Goldwasser, editor, CRYPTO’88, volume 403 of LNCS, pages
319–327. Springer, Heidelberg, August 1990.
[36] Jing Chen, Sergey Gorbunov, Silvio Micali, and Georgios Vlachos. ALGORAND AGREEMENT: Super fast and partition resilient byzantine
agreement. Cryptology ePrint Archive, Report 2018/377, 2018. https://eprint.iacr.org/2018/377.
[37] Alessandro Chiesa, Matthew Green, Jingcheng Liu, Peihan Miao, Ian
Miers, and Pratyush Mishra. Decentralized anonymous micropayments.
In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part II, volume 10211 of LNCS, pages 609–642. Springer,
Heidelberg, April / May 2017.

104

CHAPTER 7. BIBLIOGRAPHY[38] Jeff Coleman, Liam Horne, and Li Xuanji. Counterfactual: Generalizedstate channels, 2018.
[39] Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels,
Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin GünSirer, et al. On scaling decentralized blockchains. In International Conference on Financial Cryptography and Data Security, pages 106–125.
Springer, 2016.
[40] Pranav Dandekar, Ashish Goel, Ramesh Govindan, and Ian Post. Liquidity in credit networks: A little trust goes a long way. In Proceedings of the
12th ACM Conference on Electronic Commerce, EC ’11, pages 147–156,
New York, NY, USA, 2011. ACM.
[41] Bernardo David, Rafael Dowsley, and Mario Larangeira. Kaleidoscope:
An efficient poker protocol with payment distribution and penalty enforcement. Cryptology ePrint Archive, Report 2017/899, 2017. http://eprint.iacr.org/2017/899.
[42] Bernardo David, Rafael Dowsley, and Mario Larangeira. 21 - bringing
down the complexity: Fast composable protocols for card games without
secret state. In Willy Susilo and Guomin Yang, editors, ACISP 18, volume10946 of LNCS, pages 45–63. Springer, Heidelberg, July 2018.
[43] Bernardo David, Rafael Dowsley, and Mario Larangeira. ROYALE: A
framework for universally composable card games with financial rewards
and penalties enforcement. Cryptology ePrint Archive, Report 2018/157,
2018. https://eprint.iacr.org/2018/157.
[44] Christian Decker and Roger Wattenhofer. A fast and scalable payment
network with bitcoin duplex micropayment channels. In Symposium on
Self-Stabilizing Systems, pages 3–18. Springer, 2015.
[45] Alexandra Dmitrienko, David Noack, and Moti Yung. Secure walletassisted offline bitcoin payments with double-spender revocation. In
Ramesh Karri, Ozgur Sinanoglu, Ahmad-Reza Sadeghi, and Xun Yi, editors, ASIACCS 17, pages 520–531. ACM Press, April 2017.
[46] Stefan Dziembowski, Lisa Eckey, Sebastian Faust, and Daniel Malinowski.
PERUN: Virtual payment channels over cryptographic currencies. Cryptology ePrint Archive, Report 2017/635, 2017. http://eprint.iacr.
org/2017/635.
[47] Stefan Dziembowski, Lisa Eckey, Sebastian Faust, and Daniel Malinowski.
Perun: Virtual payment hubs over cryptocurrencies. In 2019 IEEE Symposium on Security and Privacy (SP), pages 106–123. IEEE, 2019.
[48] Stefan Dziembowski, Sebastian Faust, and Kristina Hostakova. Foundations of state channel networks. Cryptology ePrint Archive, Report
2018/320, 2018. https://eprint.iacr.org/2018/320.

105[49] Stefan Dziembowski, Sebastian Faust, and Kristina Hostáková. Generalstate channel networks. In David Lie, Mohammad Mannan, Michael
Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 949–966.
ACM Press, October 2018.
[50] Stefan Dziembowski, Sebastian Faust, and Kristina Hostáková. Generalstate channel networks. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 949–966. ACM,
2018.
[51] Christoph Egger, Pedro Moreno-Sanchez, and Matteo Maffei. Atomic
multi-channel updates with constant collateral in bitcoin-compatible
payment-channel networks. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 801–
815. ACM Press, November 2019.
[52] EOS. EOS. https://eos.io/, 2018. [Online; accessed 6-May-2018].
[53] Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse.
Bitcoin-ng: A scalable blockchain protocol. In Proceedings of the 13th
Usenix Conference on Networked Systems Design and Implementation,
NSDI’16, pages 45–59, Berkeley, CA, USA, 2016. USENIX Association.
[54] Simon N. Foley. Using trust management to support transferable hashbased micropayments. In Rebecca Wright, editor, FC 2003, volume 2742
of LNCS, pages 1–14. Springer, Heidelberg, January 2003.
[55] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399404, 1956.
[56] Cardano Foundation. Cardano Hub. https://www.cardano.org/, 2018.
[Online; accessed 28-March-2018].
[57] Juan Garay and Aggelos Kiayias. Sok: A consensus taxonomy in theblockchain era. Cryptology ePrint Archive, Report 2018/754, 2018.
https://eprint.iacr.org/2018/754.
[58] Arpita Ghosh, Mohammad Mahdian, Daniel M. Reeves, David M. Pennock, and Ryan Fugger. Mechanism design on trust networks. In Xiaotie
Deng and Fan Chung Graham, editors, Internet and Network Economics,
pages 257–268, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
[59] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. Cryptology ePrint Archive, Report 2017/454, 2017. http://eprint.iacr.org/2017/454.
[60] Roberto Canonico Giovanni Di Stasi, Stefano Avallone andGiorgio Ventre.
Routing payments on the lightning network.
http://wpage.unina.it/giovanni.distasi/pub/blockchain2018-main.pdf,
2018. Accessed: 2019-03-28.

106

CHAPTER 7. BIBLIOGRAPHY[61] Matthew Green and Ian Miers. Bolt: Anonymous payment channels fordecentralized currencies. In Bhavani M. Thuraisingham, David Evans, Tal
Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 473–489. ACM
Press, October / November 2017.
[62] Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, Patrick McCorry,and Arthur Gervais. Sok: Off the chain transactions. Cryptology ePrint
Archive, Report 2019/360, 2019. https://eprint.iacr.org/2019/360.
[63] Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro,and Sharon Goldberg. Tumblebit: An untrusted bitcoin-compatible
anonymous payment hub. In Network and Distributed System Security
Symposium, 2017.
[64] Philipp Hoenisch and Ingo Weber. Aodv–based routing for payment channel networks. In Shiping Chen, Harry Wang, and Liang-Jie Zhang, editors,
Blockchain – ICBC 2018, pages 107–124, Cham, 2018. Springer International Publishing.
[65] Kexin Hu and Zhenfeng Zhang. Fast lottery-based micropayments for decentralized currencies. In Willy Susilo and Guomin Yang, editors, ACISP
18, volume 10946 of LNCS, pages 669–686. Springer, Heidelberg, July
2018.
[66] Maxim Jourenko, Mario Larangeira, and Keisuke Tanaka. Lightweightvirtual payment channels. Cryptology ePrint Archive, Report 2020/998,
2020. https://eprint.iacr.org/2020/998.
[67] Dean Karlan, Markus Mobius, Tanya Rosenblat, and Adam Szeidl. Trustand social collateral. The Quarterly Journal of Economics, 124(3):1307–
1361, 2009.
[68] Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. Universally composable synchronous computation. In Theory of Cryptography
Conference, pages 477–498. Springer, 2013.
[69] Rami Khalil and Arthur Gervais. Revive: Rebalancing off-blockchain
payment networks. In Proceedings of the 2017 ACM SIGSAC Conference
on Computer and Communications Security, pages 439–453. ACM, 2017.
[70] Rami Khalil and Arthur Gervais. NOCUST - A non-custodial 2nd-layer
financial intermediary. Cryptology ePrint Archive, Report 2018/642, 2018.
https://eprint.iacr.org/2018/642.
[71] Aggelos Kiayias and Orfeas Stefanos Thyfronitis Litos. A composable
security treatment of the lightning network. Cryptology ePrint Archive,
Report 2019/778, 2019. https://eprint.iacr.org/2019/778.

107[72] Aggelos Kiayias and Orfeas Stefanos Thyfronitis Litos. A composable
security treatment of the lightning network. IACR Cryptology ePrint
Archive, 2019:778, 2019.
[73] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman
Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017,
Part I, volume 10401 of LNCS, pages 357–388. Springer, Heidelberg, August 2017.
[74] Aggelos Kiayias, Hong-Sheng Zhou, and Vassilis Zikas. Fair and robust
multi-party computation using a global transaction ledger. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, pages 705–734, Berlin, Heidelberg, 2016. Springer Berlin
Heidelberg.
[75] Uri Klarman, Soumya Basu, Aleksandar Kuzmanovic, and Emin GünSirer. bloxroute: A scalable trustless blockchain distribution network
whitepaper.
[76] S. Knight, H.X. Nguyen, N. Falkner, R. Bowden, and M. Roughan. Theinternet topology zoo. Selected Areas in Communications, IEEE Journal
on, 29(9):1765 –1775, october 2011.
[77] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas
Gailly, Ewa Syta, and Bryan Ford. OmniLedger: A secure, scale-out,
decentralized ledger via sharding. In 2018 IEEE Symposium on Security
and Privacy, pages 583–598. IEEE Computer Society Press, May 2018.
[78] Ranjit Kumaresan and Iddo Bentov. Amortizing secure computation withpenalties. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel,
Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 418–
429. ACM Press, October 2016.
[79] Ranjit Kumaresan, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. Improvements to secure computation with penalties. In Edgar R.
Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers,
and Shai Halevi, editors, ACM CCS 2016, pages 406–417. ACM Press,
October 2016.
[80] Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive blockchain protocols. In Rainer Böhme and Tatsuaki Okamoto, editors, FC
2015, volume 8975 of LNCS, pages 528–547. Springer, Heidelberg, January
2015.
[81] Joshua Lind, Ittay Eyal, Peter Pietzuch, and Emin Gün Sirer. Teechan:
Payment channels using trusted execution environments. arXiv preprint
arXiv:1612.07766, 2016.

108

CHAPTER 7. BIBLIOGRAPHY[82] Richard J Lipton and Rafail Ostrovsky. Micro-payments via efficient coinflipping. In International Conference on Financial Cryptography, pages
1–15. Springer, 1998.
[83] Richard J. Lipton and Rafail Ostrovsky. Micropayments via efficient coinflipping. In Rafael Hirschfeld, editor, FC’98, volume 1465 of LNCS, pages
1–15. Springer, Heidelberg, February 1998.
[84] Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, SethGilbert, and Prateek Saxena. A secure sharding protocol for open
blockchains. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher
Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016,
pages 17–30. ACM Press, October 2016.
[85] Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, and Matteo Maffei. Silentwhispers: Enforcing security and privacy in credit networks.
NDSS, 2017.
[86] Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, Matteo Maffei,
and Srivatsan Ravi. Concurrency and privacy with payment-channel networks. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, andDongyan Xu, editors, ACM CCS 2017, pages 455–471. ACM Press, October / November 2017.
[87] Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, Matteo Maffei,
and Srivatsan Ravi. Concurrency and privacy with payment-channel networks. In Proceedings of the 2017 ACM SIGSAC Conference on Computerand Communications Security, CCS ’17, pages 455–471, New York, NY,
USA, 2017. ACM.
[88] Giulio Malavolta, Pedro Moreno-Sanchez, Clara Schneidewind, Aniket
Kate, and Matteo Maffei. Multi-hop locks for secure, privacy-preserving
and interoperable payment-channel networks. Cryptology ePrint Archive,
Report 2018/472, 2018. https://eprint.iacr.org/2018/472.
[89] Giulio Malavolta, Pedro Moreno-Sanchez, Clara Schneidewind, Aniket
Kate, and Matteo Maffei. Anonymous multi-hop locks for blockchain scalability and interoperability. In NDSS, 2019.
[90] Giulio Malavolta, Pedro Moreno-Sanchez, Clara Schneidewind, Aniket
Kate, and Matteo Maffei. Anonymous multi-hop locks for blockchain scalability and interoperability. In Network and Distributed Systems Security
Symposium, 2019.
[91] David Mazieres. The stellar consensus protocol: A federated model forinternet-level consensus. Stellar Development Foundation, 2015.
[92] Patrick McCorry, Surya Bakshi, Iddo Bentov, Andrew Miller, and Sarah
Meiklejohn. Pisa: Arbitration outsourcing for state channels. Cryptology ePrint Archive, Report 2018/582, 2018. https://eprint.iacr.org/
2018/582.

109[93] Patrick McCorry, Chris Buckland, Surya Bakshi, Karl Wüst, and Andrew
Miller. You sank my battleship! a case study to evaluate state channels
as a scaling solution for cryptocurrencies.
[94] Patrick McCorry, Malte Möser, Siamak Fayyaz Shahandashti, and Feng
Hao. Towards bitcoin payment networks. In Joseph K. Liu and Ron
Steinfeld, editors, ACISP 16, Part I, volume 9722 of LNCS, pages 57–76.
Springer, Heidelberg, July 2016.
[95] Patrick McCorry, Malte Möser, Siamak F Shahandasti, and Feng Hao.
Towards bitcoin payment networks. In Australasian Conference on Information Security and Privacy, pages 57–76. Springer, 2016.
[96] Silvio Micali and Ronald L. Rivest. Micropayments revisited. In Bart
Preneel, editor, CT-RSA 2002, volume 2271 of LNCS, pages 149–163.
Springer, Heidelberg, February 2002.
[97] Silvio Micali and Ronald L Rivest. Micropayments revisited. In Cryptographers Track at the RSA Conference, pages 149–163. Springer, 2002.
[98] Andrew Miller, Iddo Bentov, Surya Bakshi, Ranjit Kumaresan, andPatrick McCorry. Sprites and state channels: Payment networks thatgo faster than lightning. In Ian Goldberg and Tyler Moore, editors, FC
2019, volume 11598 of LNCS, pages 508–526. Springer, Heidelberg, February 2019.
[99] Ayelet Mizrahi and Aviv Zohar. Congestion attacks in payment channel
networks. arXiv preprint arXiv:2002.06564, 2020.
[100] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.
[101] Paypal Network. Paypal Network. https://www.paypal.com/jp/home,2018. [Online; accessed 17-October-2018].
[102] Visa Network. Visa Network. https://www.visa.ca/, 2018. [Online;
accessed 17-October-2018].
[103] Andrew M. Odlyzko. The case against micropayments. In Rebecca Wright,
editor, FC 2003, volume 2742 of LNCS, pages 77–83. Springer, Heidelberg,
January 2003.
[104] Olaoluwa Osuntokun. [lightning-dev] amp: Atomic multi-path payments
over lightning.
https://lists.linuxfoundation.org/pipermail/lightningdev/2018-February/000993.html. Accessed: 2018-10-11.
[105] Rafael Pass and abhi shelat. Micropayments for decentralized currencies.
In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS
2015, pages 207–218. ACM Press, October 2015.

110

CHAPTER 7. BIBLIOGRAPHY[106] Rafael Pass and Elaine Shi. The sleepy model of consensus. In Tsuyoshi
Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume10625 of LNCS, pages 380–409. Springer, Heidelberg, December 2017.
[107] Rafael Pass and Elaine Shi. Thunderella: Blockchains with optimistic
instant confirmation. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 3–33.
Springer, Heidelberg, April / May 2018.
[108] Christian PDecker, Rusty Russel, and Olaoluwa Osuntokun. eltoo: A
simple layer2 protocol for bitcoin. See https://blockstream.com/eltoo.pdf,
2017.
[109] Cristina Pérez-Solà, Alejandro Ranchal-Pedrosa, Jordi HerreraJoancomartı́, Guillermo Navarro-Arribas, and Joaquin Garcia-Alfaro.
Lockdown: Balance availability attack against lightning network channels. In International Conference on Financial Cryptography and Data
Security, pages 245–263. Springer, 2020.
[110] Dennis Peterson.
Sparky:A lightning network in two pagesof solidity. http://wpage.unina.it/giovanni.distasi/pub/blockchain2018main.pdf, 2018. Accessed: 2019-03-30.
[111] Dmytro Piatkivskyi and Mariusz Nowostawski. Split payments in payment
networks. In Data Privacy Management, Cryptocurrencies and Blockchain
Technology, pages 67–75. Springer, 2018.
[112] Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments. See https://lightning. network/lightningnetwork-paper. pdf, 2016.
[113] Pavel Prihodko, Slava Zhigulin, Mykola Sahno, Aleksei Ostrovskiy, and Olaoluwa Osuntokun.
Flare: An approach to routing
in lightning network.
White Paper (bitfury. com/content/5-whitepapers-research/whitepaper flare an approach to routing in lightning n
etwork 7 7 2016. pdf ), 2016.
[114] Paul Resnick and Rahul Sami. Sybilproof transitive trust protocols. In
Proceedings of the 10th ACM Conference on Electronic Commerce, EC’09, pages 345–354, New York, NY, USA, 2009. ACM.
[115] Ronald L. Rivest. Electronic lottery tickets as micropayments. In Rafael
Hirschfeld, editor, FC’97, volume 1318 of LNCS, pages 307–314. Springer,
Heidelberg, February 1997.
[116] Ronald L Rivest. Electronic lottery tickets as micropayments. In International Conference on Financial Cryptography, pages 307–314. Springer,
1997.

111
[117] Stefanie Roos, Martin Beck, and Thorsten Strufe. Anonymous addresses
for efficient and resilient routing in f2f overlays. In Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International
Conference on, pages 1–9. IEEE, 2016.
[118] Stefanie Roos, Pedro Moreno-Sanchez, Aniket Kate, and Ian Goldberg.
Settling payments fast and private: Efficient decentralized routing forpath-based transactions. arXiv preprint arXiv:1709.05748, 2017.
[119] Stefanie Roos, Pedro Moreno-Sanchez, Aniket Kate, and Ian Goldberg.
Settling payments fast and private: Efficient decentralized routing forpath-based transactions. arXiv preprint arXiv:1709.05748, 2017.
[120] Vibhaalakshmi Sivaraman, Shaileshh Bojja Venkatakrishnan, Mohammad
Alizadeh, Giulia Fanti, and Pramod Viswanath. Routing cryptocurrency
with the spider network. arXiv preprint arXiv:1809.05088, 2018.
[121] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. SPECTRE: A
fast and scalable cryptocurrency protocol. Cryptology ePrint Archive,
Report 2016/1159, 2016. http://eprint.iacr.org/2016/1159.
[122] Yonatan Sompolinsky and Aviv Zohar. Accelerating Bitcoin’s transaction
processing. Fast money grows on trees, not chains. Cryptology ePrint
Archive, Report 2013/881, 2013. http://eprint.iacr.org/2013/881.
[123] Yonatan Sompolinsky and Aviv Zohar.
PHANTOM: A scalable
BlockDAG protocol. Cryptology ePrint Archive, Report 2018/104, 2018.
https://eprint.iacr.org/2018/104.
[124] Jeremy Spilman.
[bitcoin-development] anti dos for tx replacement.
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013April/002433.html, 2013. Accessed: 2018-09-03.
[125] Steemit. Steemit. https://steemit.com/, 2018. [Online; accessed 6May-2018].
[126] Taisei Takahashi and Akira Otsuka. Short paper: Secure offline payments
in bitcoin. Third Workshop on Trusted Smart Contracts, 2019.
[127] P. F. Tsuchiya. The landmark hierarchy: A new hierarchy for routing invery large networks. SIGCOMM Comput. Commun. Rev., 18(4):35–42,
August 1988.
[128] Nicko van Someren, Andrew M. Odlyzko, Ronald L. Rivest, Tim Jones,
and Duncan Goldie-Scot. Does anyone really need micropayments? In
Rebecca Wright, editor, FC 2003, volume 2742 of LNCS, pages 69–76.
Springer, Heidelberg, January 2003.
[129] David Wheeler. Transactions using bets. In International Workshop on
Security Protocols, pages 89–92. Springer, 1996.

112

CHAPTER 7. BIBLIOGRAPHY[130] David Wheeler. Transactions using bets. In Mark Lomas, editor, Security Protocols, pages 89–92, Berlin, Heidelberg, 1997. Springer Berlin
Heidelberg.
[131] Bitcoin Wiki. Block size limit controversy. https://en.bitcoin.
it/wiki/Block_size_limit_controversy, 2018. [Online; accessed 17October-2018].
[132] Gavin Wood. Ethereum: A secure decentralised generalised transaction
ledger. Ethereum project yellow paper, 151:1–32, 2014.
[133] Beverly Yang and Héctor Garcı́a-Molina. PPay: Micropayments for peerto-peer systems. In Sushil Jajodia, Vijayalakshmi Atluri, and Trent
Jaeger, editors, ACM CCS 2003, pages 300–310. ACM Press, October
2003.
[134] Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. RapidChain:
Scaling blockchain via full sharding. In David Lie, Mohammad Mannan,
Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages
931–948. ACM Press, October 2018.
[135] Alexei Zamyatin, Dominik Harz, Joshua Lind, Panayiotis Panayiotou,
Arthur Gervais, and William J. Knottenbelt. XCLAIM: Interoperability
with cryptocurrency-backed tokens. Cryptology ePrint Archive, Report
2018/643, 2018. https://eprint.iacr.org/2018/643.
[136] Yuncong Zhang, Yu Long, Zhen Liu, Zhiqiang Liu, and Dawu Gu. Zchannel: Scalable and efficient scheme in zerocash. In Willy Susilo andGuomin Yang, editors, ACISP 18, volume 10946 of LNCS, pages 687–705.
Springer, Heidelberg, July 2018.