Applied Science, Faculty of
Engineering, School of (Okanagan)
DSpace
UBCO
Guo, Yuwei
Master of Applied Science - MASc
University of British Columbia
As a promising method to enable fast and scalable Bitcoin transactions, Bitcoin Lightning Network (LN) has experienced rapid development since the end of 2017. LN utilizes the so-called "payment channels" to provide fast off-chain transactions, thereby offloading on-chain burden and enabling instant payments. With many new protocols proposed to improve the performance of LN, little is known about the current state of the network such as its topology, channel characteristics and application performance. This thesis conducts a measurement study on the performance of LN and provides some guide on improvement.
A Measurement Study of Bitcoin Lightning NetworkbyYuwei GuoB.Eng, Beihang University, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Electrical Engineering)The University of British Columbia(Okanagan)December 2019c© Yuwei Guo, 2019The following individuals certify that they have read, and recommend to the Col-lege of Graduate Studies for acceptance, the thesis entitled:A Measurement Study of Bitcoin Lightning Networksubmitted by Yuwei Guo in partial fulfillment of the requirements of the degree ofMaster of Applied Science.Chen Feng, School of EngineeringSupervisorYang Cao, School of EngineeringSupervisory Committee MemberNarayan Apurva, School of EngineeringSupervisory Committee MemberEric Li, Faculty of ManagementUniversity ExamineriiAbstractAs a promising method to enable fast and scalable Bitcoin transactions, BitcoinLightning Network (LN) has experienced rapid development since the end of 2017.LN utilizes the so-called “payment channels” to provide fast off-chain transactions,thereby offloading on-chain burden and enabling instant payments. With many newprotocols proposed to improve the performance of LN, little is known about thecurrent state of the network such as its topology, channel characteristics and appli-cation performance. This thesis conducts a measurement study on the performanceof LN and provides some guide on improvement.iiiLay SummaryIn this thesis, a systematic measurement on LN was conducted based on the datacollected over a period of fifteen months. This measurement studied the paymentsuccess rate and how the network performs under attack. Payment channels werealso analyzed regarding their functions. This work provides an in-depth under-standing of network mechanisms and helps to explore future implications of LN.ivPrefaceThe work outlined in this thesis was conducted in the School of Engineering atthe University of British Columbia, Okanagan Campus, under the supervision ofDr. Chen Feng. The main content in this thesis is based on our conference paperaccepted by the 2nd IEEE International Conference on Blockchain (Blockchain-2019) with an acceptance rate of 15.9%.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . 62 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1 Bitcoin Blockchain . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.1 Bitcoin Blockchain Key Principles . . . . . . . . . . . . . 72.1.2 Challenges of Bitcoin Blockchain . . . . . . . . . . . . . 92.2 Lightning Network . . . . . . . . . . . . . . . . . . . . . . . . . 11vi2.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.2 Payments in Lightning Network . . . . . . . . . . . . . . 123 Data Collection and Abstraction . . . . . . . . . . . . . . . . . . . . 153.1 Data Collection of LN . . . . . . . . . . . . . . . . . . . . . . . 163.2 Graph Construction . . . . . . . . . . . . . . . . . . . . . . . . . 173.3 Network Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 184 Network Performance Analysis . . . . . . . . . . . . . . . . . . . . . 224.1 Network Routing Performance . . . . . . . . . . . . . . . . . . . 224.1.1 Effective Eccentricity . . . . . . . . . . . . . . . . . . . . 234.1.2 Channel Capacity Distribution . . . . . . . . . . . . . . . 234.1.3 Network Routing Efficiency . . . . . . . . . . . . . . . . 244.1.4 Routing Evolution . . . . . . . . . . . . . . . . . . . . . 264.2 Network Resilience Under Attack . . . . . . . . . . . . . . . . . 274.2.1 Identifying Important Nodes . . . . . . . . . . . . . . . . 294.2.2 Network Anti-Attack Performance . . . . . . . . . . . . . 324.2.3 Resilience Evolution . . . . . . . . . . . . . . . . . . . . 335 Channel Characteristic Analysis . . . . . . . . . . . . . . . . . . . . 365.1 Channel Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . 365.2 Pair Communication Performance . . . . . . . . . . . . . . . . . 375.2.1 Pair Communication Ability . . . . . . . . . . . . . . . . 385.2.2 Pair Communication Stability . . . . . . . . . . . . . . . 395.2.3 Multi-channel Pair Communication Performance . . . . . 406 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . 426.1 Improving Routing Efficiency . . . . . . . . . . . . . . . . . . . 426.2 Enhancing Network Resilience . . . . . . . . . . . . . . . . . . . 436.3 Node Evaluation System . . . . . . . . . . . . . . . . . . . . . . 436.4 Protocol Simulation . . . . . . . . . . . . . . . . . . . . . . . . . 44Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45viiList of TablesTable 1.1 List of Some Famous Cryptocurrencies . . . . . . . . . . . . . 1Table 1.2 Throughput of some payment technologies . . . . . . . . . . . 3Table 3.1 Statistic of G and G′LCC . . . . . . . . . . . . . . . . . . . . . 19Table 4.1 Top 10 Important Nodes . . . . . . . . . . . . . . . . . . . . . 31Table 5.1 Channel Statistics . . . . . . . . . . . . . . . . . . . . . . . . 37viiiList of FiguresFigure 1.1 Illustration of blockchain . . . . . . . . . . . . . . . . . . . . 2Figure 2.1 Blockchain structure . . . . . . . . . . . . . . . . . . . . . . 8Figure 2.2 Alice-Bob payment channel . . . . . . . . . . . . . . . . . . 13Figure 2.3 HTLC in payment routing . . . . . . . . . . . . . . . . . . . 14Figure 3.1 An overview of our work . . . . . . . . . . . . . . . . . . . . 15Figure 3.2 Degree distribution . . . . . . . . . . . . . . . . . . . . . . . 21Figure 4.1 Cumulative distribution of effective eccentricity . . . . . . . . 24Figure 4.2 Cumulative distribution of channel capacity . . . . . . . . . . 25Figure 4.3 An example of routing efficiency . . . . . . . . . . . . . . . . 26Figure 4.4 Network routing efficiency . . . . . . . . . . . . . . . . . . . 27Figure 4.5 Network routing efficiency evolution . . . . . . . . . . . . . . 28Figure 4.6 Node importance evaluation . . . . . . . . . . . . . . . . . . 32Figure 4.7 Network resilience . . . . . . . . . . . . . . . . . . . . . . . 33Figure 4.8 Network resilience evolution . . . . . . . . . . . . . . . . . . 35Figure 5.1 Cumulative Distribution of Pair Channel Numbers . . . . . . 38Figure 5.2 Pair Communication Performance . . . . . . . . . . . . . . . 39Figure 5.3 Channel temporal distribution: 5.3a shows communicationperformance for all node pairs, solid lines for ρa, dotted linesfor ρs, red, black and blue lines correspond to S1, S2 and S3;5.3b shows communication performance for multi-channel pairs. 41ixList of SymbolsCC connected componentDAG directed acyclic graphLN Lightning NetworkLCC largest connected componentLQC largest qualified componentPOS Proof of StakePOW Proof of WorkPR PageRank algorithmQC qualified componentxAcknowledgmentsIt was just like yesterday when I got my bachelor’s degree from Beihang Universityand came to Canada. But now, my graduate study is coming to an end. Lookingback at the past two year’s life, there were times with depression, confusion andanxiety, but what’s truly important is about self reflection, setting the goals andlearning how to deal with obstacles independently. During this process, I receiveda lot of help and there are many people I must give thanks to.First, I want to express my gratitude to my supervisor, Dr. Chen Feng. I’mreally impressed by his insightful thinking on many research problems. Withouthis help, I could never finish my research and graduate studies.Second, I want to thank my parents. They are always by my side when I makedecisions. Their selfless love and support helps me go further.In the end, I want to thank my friends: Chunpu Wang, Renming Qi, YonghuiLv, Jianyu Niu, Fangyu Gai, Junyuan Leng, Jinfeng Tong, Pengxia Wu and XuetingYang. Thanks for all your company and I’ll never forget the happy times we spenttogether.xiChapter 1Introduction1.1 MotivationBitcoin is the first decentralized cryptocurrency [17] created in 2009 by pseudony-mous developer Satoshi Nakamoto. Since the release of Bitcoin, the cryptocur-rency area has entered an era of prosperity. According to statistics1, there are 30thousand cryptocurrencies and the total market capitalization is 220 billion as ofOct 15, 2019. We list some of the most famous cryptocurrencies at that time inTable 1.1.Table 1.1: List of Some Famous CryptocurrenciesName Released Symbol Market Cap (billion)Bitcoin 2009 BTC $145.00Ethereum 2015 ETH $19.12XRP 2012 XRP $12.85The decentralized control of each cryptocurrency works through distributedledger technology, typically a blockchain, that serves as a public financial trans-action database. The simplified process is shown in Figure 1.1. Alice sends apayment to Bob and submits the transaction to the blockchain, once it is accepted1CoinMarketCap1Figure 1.1: Illustration of blockchainSource: CB Insightsby the network, all nodes will have a copy and this record will become immutable.Though with such great development, the current blockchain technology stillfaces a pressing challenge - achieving high throughput. Why is this a problem?Let’s first take a look at the basic principles of blockchain (more detailed expla-nations can be found in Section 2.1). Roughly speaking, the Bitcoin blockchainis comprised of a chain of blocks which store transactions. To ensure security, thegrowth rate of the chain is limited using Proof of Work (POW) consensus algorithm.Typically it takes 10 minutes on average to generate a new 1MB block. This natureof blockchain leads to scalability issue. From Table 1.2 we can see that Bitcoincan only write 7 transactions per second (TPS). In the meantime, Visa can handle2,000 TPS on average.Scaling has long been the focus of developers and many methods are proposedto improve the throughput. Some focused on the blockchain itself (i.e., “Layer 1”),while others intended to build a “Layer 2” system on top of the original blockchain.There exist several exciting “Layer 1” technologies like Algorand and Prism [1, 9].Algorand adopts Proof of Stake (POS) consensus algorithm and achieves through-put of over 1,000 TPS. Prism uses multiple parallel chains instead of just one andcan push the throughput to physical limits.2Table 1.2: Throughput of some payment technologiesName Visa Bitcoin Ethereum Layer 2 of blockchainThroughput(TPS)2,000 7 15optimal(according to bandwidth)In spite of the performance, most “Layer 1” technologies are still at the R&Dstage and the community haven’t built enough experience. Shifting attention to“Layer 2”, we note that one of the most promising solutions is an off-chain systemcalled the Bitcoin Lightning Network (LN) [25] which can also achieve optimalthroughput. Furthermore, since implemented in late year 2017, there are now about3,000 active nodes and 840 BTC (6.7 million USD) in the network.The cornerstone of LN is the payment channel. A payment channel allowstwo users to send multiple payments to each other and only touches the blockchaintwice: at channel opening and closing time. Local payments inside the channelare settled instantly with no fees, and guaranteed that the rightful states can bebroadcasted to the global blokchain at any time. Separate channels form a networkby using Hashed TimeLock Contracts (HTLCs), which ensure that payments canbe routed through intermediaries. In Section 2.2, we describe LN in more details.LN has attracted a great attention from both academia and industry. Researchershave proposed protocols to improve routing efficiency [29], network liquidity [16]and rebalance channels [11]. The Bitcoin community recently launched an exper-iment called “lightning torch” to show the value and expand the influence of LN.There are also some individual projects. For example, a private project namedLNBIG2 has set up tens of nodes in LN and injected more than 300 BTC (the unitof Bitcoin). Moreover, the LNBIG adjusted its channel settings to help rebalance.In spite of its great success in offloading on-chain burdens, the current LN it-self still remains to be further investigated. First, little work has been done to studythe topology of LN, therefore many significant questions remain unanswered. Forexample, how is Bitcoin distributed in this network? How efficiently can we make2The website of the project is https://lnbig.com3a transaction through routing between any two users without a direct channel? Arethere any important nodes in the network and to what extent does the network relyon them? The answers to the above questions can not only help us better under-stand the characteristics of LN, but also provide insights for future protocol design.Second, payment channels in LN are special: unlike connections in the Internet,establishing channels in LN will be charged. However, it’s impractical to maintaina channel as long as possible. Because it decreases liquidity by locking depositsinside the channel. Exploring the opening and closing of channels helps providebetter user experience. Third, most of the existing protocols lack simulations ona real-world offchain network topology. The need of an easy-access platform forsimulation is urgent.In this thesis, we answer the above questions by conducting a systematic mea-surement study on LN. Our contributions are as follows:• We study the topology of the LN and provide an in-depth understanding. Inparticular, we apply graph theory to evaluate the network performance andthen define metrics for demonstrating features of the payment channel.• Our analysis reveals several issues of LN. Specifically, we show that thecurrent LN does not perform well in routing and prove that it is vulnerableto attacks.• The issues we observe and the metrics we introduce shed light on user guid-ance and future protocol design.• We provide an easy-to-use LN topology for protocol simulations3. Ourtopology can not only better reflect the real situation, but also help to com-pare the performance of different algorithms.1.2 Related WorkSince J. Poon and T. Dryja [25] proposed LN based on duplex micro-paymentchannels, there have been many works focusing on designing new protocols andimproving network performance.3For the purpose of reproducibility, data and codes of our work are available athttps://github.com/measureln/measurement study on ln.4In the LN, depleted payment channels only have balance on one side and needto be closed. Khalil et al. [11] introduces REVIVE protocol to maintain networkbalance equilibrium without closing and reopening depleted channels. SpeedyMur-mus protocol [29] allows efficient routing for completely decentralized path-basedtransactions. In the LN payment routing process, intermediaries might collude torecover identities of the payment owners. Green et al. [10] construct anonymouspayment channels to prevent privacy leaks of user identity. Though LN reducesmany on-chain transactions, the channel deposits are locked as collateral and lacksliquidity. Sprites protocol [16] aims to reduce total collateral costs.Though many new protocols are brought up, there is almost no paper focus-ing on the performance measurement of the current LN. Flash [31] utilizes pay-ment characteristics to improve routing performance. However, it focuses on eachnode’s local view and the measurement of the overall network is not covered. An-other work [30] displays various attacking strategies and quantifies the networkresilience. However, both work only use discrete snapshot graphs. By contrast,our work is among the first to reveal the evolution of network performance and theunique characteristics of payment channels.There exists some analysis about the Ethereum network and Bitcoin network.The work of Chen, Ting et al. [5] characterizes Ethereum through graph analysisand provides many insights. Lischke et al. [14] mainly investigates the businessdistribution and business model of the Bitcoin Network based on IP addresses ofnodes and business tags of transactions. AddressProbe technique [15] reconstructsBitcoin network topologies through broadcasted messages and identify some influ-ential nodes. Ron et al. [28] examine the structure of Bitcoin network and concludethat most of the bitcoins are in dormant status. They also find that large transac-tions are extremely rare in the network and most of the transactions are small-valuetransactions. Timing analysis [18] discusses the delay of the network and nodes la-tency.Some work focuses on the anonymity of the Bitcoin network specifically. Oberet al. [23] point out the anonymity of the Bitcoin network increases overtime. Reidet al. [26] indicate that part of the anonymity of known nodes can be discoveredusing proper analysis tools with available information online. Koshy et al. [12]demonstrate the possibility to link the Bitcoin addresses with IPs only based on5transaction relay traffic. Biryukov et al. [2] deanonymize the Bitcoin network byidentifying nodes the target nodes connect to. Dandelion designed by [15] canavoid privacy disclosure by spreading message through a random line and hop thenspreading using diffusion to the whole network.1.3 Organization of the ThesisThis thesis contains six chapters and the rest of the chapters are structured as fol-lows.In Chapter 2, the background knowledge of blockchain and Lightning Networkis provided.In Chapter 3, data collecting and processing methods are introduced. The wayof constructing network graphs is also presented.In Chapter 4, two important properties of the payment network are measuredbased on its topology. In Section 4.1, the routing efficiency is studied. In Sec-tion 4.2, the network resilience when some important nodes are under attack isevaluated.In Chapter 5, the behavior of payment channels are investigated.In Chapter 6, the entire thesis is concluded.6Chapter 2BackgroundThe purpose of this chapter is to provide the reader with a general understanding ofblockchain technology and the Lightning Network (LN). We start by introducingBitcoin and principles of blockchain. Then, we talk about some current issuesof blockchain and a few proposed solutions, especially for the scalability issue.Finally, we focus on one promising solution - LN, which is the study object of thisthesis.2.1 Bitcoin Blockchain2.1.1 Bitcoin Blockchain Key PrinciplesBitcoin is the first electronic cash system where mutually distrusting peers cantrade, without relying on a trusted third party, such as a bank. The fundamentalinfrastructure of Bitcoin is blockchain, a public distributed ledger maintained bythe community to record and verify all the transactions.Paying with Bitcoin on blockchain has attracted more and more attention as ithas several huge advantages. First, the system is purely peer to peer so no banks orfinancial intermediaries can interrupt user transactions or freeze Bitcoin addresses.Second, it provides privacy as Bitcoin addresses are anonymous and not associatedwith personal identities. Third, standard wire transfers and foreign purchase typi-cally involve fees and exchange costs, since Bitcoin transactions don’t go through7intermediary institutions or needs to be exchanged, the fee is relatively small. Thisis particularly helpful for international trade.However, constructing such a distributed ledger is not trivial. First, it has tobe tamper-proof so nobody can modify transaction histories. Second, it needs tobe agreed by the community so peers can reach consensus on the states. Third, itmust tolerate some evil nodes that are not following the system protocol as long asthe majority are honest. Next we explain how these features are ensured from thestructure of blockchain and the way it works.As shown in Figure 2.1, blockchain is represented by a chain of blocks. blockscan be composed of the block header and the block body which includes a list oftransactions. The block header contains various fields like a version number usedto track software or protocol upgrades, a merkle root as the hash root of the block’stransactions which makes it easier to verify the transactions, a timestamp, a nonceand difficulty target used for consensus algorithm and a reference to the hash of theprevious block, serving as a backward pointer (more details can be found blow).Thus, if the data in any given block is altered, so does the hash of this given block,then so does the next block as it stores this hash and so on. Therefore, no data canbe modified without changing all subsequent blocks.Figure 2.1: Blockchain structureSource: ResearchGate8With this chain-like structure, the next issue that needs to be addressed is bywhom and when new blocks are added to the tail of the blockchain. Here we firstexplain the hashes. A hash is a string of random numbers generated by putting agiven set of data into a deterministic hash function (in Bitcoin is SHA-256). Thehash function is one-way as we can not recover the original data from the hashresults.In Bitcoin blockchain, a block is “mined” - added to the blockchain if its hashis smaller than some target (the level of difficulty). Once a node first makes a blockwith a valid hash, it broadcasts to the network and others will start mining on top ofthis block. How can nodes alter their block hashes? Well, they include an integercalled “nonce” in their blocks and try different nonce values until the block hashis below the target. Due to the random nature of hash, the smaller the target, themore computation nodes need to do. In Bitcoin blockchain, the target is adjustedso that on average a block is generated every ten minutes, note the block proposercan be anyone and is non-predictable. Since the mining process is computationallyexpensive and requires a lot of work, the consensus algorithm is called Proof ofWork (PoW).With small chances, two miners can find a block at nearly the same time, whichwill cause the blockchain to diverge into two potential paths forward (the so-called“fork”). The fork is resolved when subsequent blocks are added and one of thechains becomes longer than the alternatives. The network then abandons the blocksthat are not in the longest chain (i.e., longest chain rule). This also explains whythe block interval is ten minutes instead of seconds. Due to network latency, thesmaller the block interval, the more likely duplicate blocks are generated beforeminers receive the latest block.In summary, mining is a competitive process. It’s extremely difficult to alter anexisting block in the chain, since such alteration would require huge computationpower to re-mine all subsequent blocks.2.1.2 Challenges of Bitcoin BlockchainThough blockchain has achieved great success, it has some issues and limitations.(a) Energy consumption: In PoW, the mining process costs vast amounts of9electricity to compute hash puzzles. It is estimated that the Bitcoin’s an-nual electricity consumption is 70 TWh, which can power 6.7 million U.S.households according to Bitcoin Energy Consumption Index1.(b) Latency issue: Network latency is the amount of time it takes from the cre-ation of a transaction until the first confirmation of it being included in ablock. Moreover, to avoid the situation where the block is abandoned dueto fork, it is recommended to wait for some longer time. Usually 6 con-firmation blocks will significantly reduce the probability that the branch isoutcompeted by a conflicting branch. However, this also greatly increasedthe network latency as users have to wait around 1 hour to make sure theirtransaction is valid.(c) Transaction costs: In Bitcoin blockchain, miners spend a lot of efforts (e.g.,computing power and energy) to mine blocks for a financial reward: withevery block added to the blockchain comes a bounty called a block reward,as well as all fees sent with the transactions that were confirmed and includedin the block. As a result, the current Bitcoin blockchain network does notfavor micropayments because the fee might even exceed the payment itself.(d) Scalability issue: From the above introduction, we can see that the Bitcoinblockchain network can only support very limited number of transactions.While this was enough at the very beginning, the system has been congestedfor a few years now. For further development of Bitcoin blockchain network,the scalability performance must be improved.Of all the issues described above, throughput matters the most to a payment net-work. Current scaling proposals can be roughly divided into three categories: (i)Replacing the underlying consensus algorithms (i.e., PoW) to reduce the blockgeneration interval. A popular variant is Proof of Stake (PoS), which however,raises some other issues like censorship. (ii) Changing the single chain-like struc-ture to parallel chain or directed acyclic graph (DAG) to support more transactions.But these graph structures need to address conflicting transactions as transactions1https://digiconomist.net/bitcoin-energy-consumption10are not ordered linearly. (iii) Developing “Layer 2” solutions which removes mosttransaction from the blockchain to off-chain.In this thesis, we focus on one particular “Layer 2” solution - Lightning Net-work (LN). The idea behind is quite intuitive: we don’t really need to keep a recordof every single transaction on blockchain. Instead, we only need to publish the finalstates after two parties have completed multiple transactions while the intermedi-ate transactions are recorded locally (in the so-called channel). By doing so, theadvantage is big. First, it’s simple and secure. We only need to handle the off-chaintransactions, the security is still ensured by the underlying PoW. Second, transac-tions between peers in their channels are settled instantly and the fees are negligiblesince they don’t enter blockchain. What’s more important is that network through-put can be greatly improved with the help of channels.It is natural to ask, how are channels established and how are they used in LN?We will answer these questions in Section 2.2.2.2 Lightning Network2.2.1 DefinitionsBelow are a few important definitions in Lightning Network (LN) that will be usedin this thesis.• Channel: a communication channel that allows two parties to make anysecure payments between each other in exchange for making only a fewtransactions on the blockchain.• Contract: an agreement between two or more entities to use Bitcoin trans-actions in a certain way, usually a way that allows Bitcoin’s automated con-sensus to enforce some or all terms in the contract. Often called a smartcontract.• Pre-image/R: data input into a hash function, which produces a hash of thepre-image. Inputting the same pre-image into the same hash function willalways produce the same hash; Lightning uses this feature to create hashlocks.11• Hash Lock: an encumbrance to a transaction output that requires the pre-image used to generate a particular hash be provided in order to spend theoutput. In Lightning, this is used to allow payments to be routable withoutneeding to trust the intermediaries.• HTLC: (Hashed TimeLocked Contract) a contract such as that used in aLightning Channel where both a hash lock and a time lock are used, thehash lock being used to allow Alice to route payments to Bob even througha Carol that neither of them trust, and the time lock being used to preventCarol from stealing back any payments he made to Alice within the channel(provided Alice enforces the contract).• Intermediary: When Bob has one channel open with Alice and anotherchannel open with Charlie, Bob can serve as an intermediary for transfer-ring payments between Alice and Charlie. With Lightning payments beingsecured with a hash lock, Bob can’t steal the payment from Alice to Charliewhen it travels through Bob’s node. Lightning payments can securely travelthrough a theoretically unlimited number of intermediaries.• Multisig: a transaction output that requires signatures from at least one of aset of two or more different private keys. Used in Lightning to give both Al-ice and Bob control over their individual funds within a channel by requiringboth of them sign commitment transactions.• Unilateral: any action performed by only one of the participants in a channelwithout requesting or needing permission from the other participant. Light-ning allows channels to be closed unilaterally (so Alice can close the channelby herself if Bob becomes unresponsive) and attempted fraud can be penal-ized unilaterally (so Alice can take any bitcoins Carol tried to steal when hebroadcast an old commitment transaction).2.2.2 Payments in Lightning NetworkThe process of creating a payment channel in LN is shown in Figure 2.2. Aliceopens a channel with Bob by sending a deposit of 1 BTC to the 2-of-2 multi-signature address on the blockchain. The fund at the multi-signature address can12only be used with both parties’ signature. Besides, the deposit is locked for somedesignated time (i.e., channel life) so in the meanwhile the two users can sendmultiple payments to each other. For example, in Figure 2.2, Alice first sends 0.3BTC to Bob, Bob then sends 0.1 BTC back to Alice, and Alice again sends 0.4BTC to Bob. These balance updates are settled instantly as they do not need toenter the blockchain. Moreover, each state is signed by both parties and updated inthe offline channel in the form of contracts. The contract also includes a timestampto ensure the local transaction order.Finally, Alice and Bob can close this channel collaboratively by publishing thelatest state (i.e., Alice 0.4 BTC, Bob 0.6 BTC) on the blockchain and claim theirmoney from the multi-signature address. If one party, say Alice is malicious andtries to publish a previous state (e.g., Alice 0.8 BTC, Bob 0.2 BTC), Bob can justsend the latest state to the blockchain as a proof and take away all Alice’s moneyin the channel as a punishment. The channel can also be closed unilaterally by anyparty, just by submitting the latest state at the closing time to the blockchain.Figure 2.2: Alice-Bob payment channelThe bi-directional payment channel can only ensure secure payments betweenits two peers. If two parties don’t have a direct channel, they can still make transac-tions via payment routing using HTLC. An HTLC claims that the receiver can onlypull money from the sender if he can produce an unknown data R from a knownhash H within some lock time. Figure 2.3 shows an example. Alice wants to payBob 1 BTC without opening a new channel with him. If Alice just sends money to13Carol, there is no enforcement for Carol to forward the money to Bob. With HTLC,Bob first generates a pair of H and secret R, and shows Alice H. Then Alice canmake an HTLC using the H and send it to Carol, claiming that Carol can pull 1BTC from Alice if she can show Alice the corresponding R in 3 days. Carol thenmakes another HTLC through H, claiming that Bob can pull 1 BTC from Carol ifhe can provide R in 1 day. Thus, Bob can get the money from Carol by exposingsecret R in time and Carol can get the money from Alice in the same way. TheHTLC expires if the receiver fails to provide R in the pre-defined time. This de-creasing lock time from 3 days to 1 day ensures that Bob cannot steal money fromCarol by showing R and pulling money from Carol after Carol’s HTLC with Aliceexpires.Figure 2.3: HTLC in payment routing14Chapter 3Data Collection and AbstractionThe first step of analyzing LN is to collect node and channel data. In this chapter,we construct a snapshot graph G to represent LN for further analysis including net-work structure and graph metrics. We also study the network performance throughG and the communication performance through pair channel characteristics. Fig-ure 3.1 is an overview of our method.Figure 3.1: An overview of our work153.1 Data Collection of LNThe network data is composed of information of nodes and channels. Node infor-mation includes node public key, node alias, join time and node capacity, whichare explained as follows.• Node public key: a unique 66-byte long string composed of number andletter which represents the node identity. It is generated from user’s privatekey and is needed to open or close the channel on LN.• Node alias: a user-defined name of the node for ease of use.• Node join time: the time a user joins LN by opening the first channel.• Node capacity: the sum of capacities of all channels on that node, regardlessof the channel was established from the node or to it.Channel information includes channel id, channel nodes, channel open timeand close time, channel open fee and close fee, channel capacity. Detailed infor-mation are as follows.• Channel id: a set of numbers of length 16 which represents channel identity.• Channel nodes: the two owners of the channel.• Channel open/close time: the time the open/close channel transaction ispublished on the blockchain.• Channel open/close fee: the fee paid for processing the open/close channeltransaction on the blockchain.• Channel capacity: the deposit of the channel at opening time.Note that current channel balance is only visible to owners of the channel for pri-vacy reasons.The current LN is a P2P network that uses a gossip protocol to discover anddisseminate information of nodes and channels. Messages include node announce-ment message, channel announcement message and channel update message. Weexplain them below.16• Node announcement message: it broadcasts or updates node informationlike public key, port and addresses so that other nodes can connect to it.• Channel announcement and update message: it contains information aboutthe channel creation and maintenance so that a node can find routes to itsdesired destination.Unlike Bitcoin network where every node has a copy of the full transactionrecord, there is no such record in LN. Hence, it is hardly possible to monitor theglobal network. Instead, we can use passive application-level monitoring to retrievenetwork information. That is, we can set up multiple nodes in LN and connect themto other nodes. Our nodes can participate in message exchange and log messagesreceived from their peers. Typically the more nodes we are connected to, the morecompleted views we have.Except for setting up our own listening nodes, we can crawl the network datashared by existing nodes. There are several such websites like https://hashxp.org/lightning/, https://1ml.com and https://graph.lndexplorer.com/. They serve as LNsearch engines and publish their gathered view of nodes and channels from multiplenodes. In this project, we crawled and processed the data until April 1, 2019 fromhttps://hashxp.org/lightning/ as it has the most comprehensive information. One ofthe listening node it uses is “rompert.com”, which is one of the top 5 nodes havingmost channels.3.2 Graph ConstructionTo investigate the structure and performance of LN, we build an undirected snap-shot graph G. We ignore channel direction in our graph construction because di-rection is often unknown and changes all the time. Specifically, a channel is fromA to B if user A has a balance. A channel can be bidirectional if both users havetheir balance. However, user balance state is updated via HTLC off the blockchainand is not broadcasted. We can only obtain the initial balance state when channelwas funded and the latest balance assignment when channel was closed. Therefore,at any other time between the open time and close time, the balance assignment inthe channel could be arbitrary.17As another reason, our work mainly focuses on the connectivity of the networkrather than the specific payment direction. In cases where channel direction cannotbe neglected like channel routing, we can assume all channel deposits are assignedto the user who needs to make payments to the other side, which achieves the max-imal payment flow in that direction. Under this assumption, we can consider thenetwork as undirected again. Below is the construction of our weighted undirectedgraph G at any specific time.Definition: G = (V,E,ω), where V is a set of nodes, E is a set of edges, ω isweight function and E ={(vi,v j)|vi,v j ∈V}. An edge represents there are one ormore active channels between node vi and v j at a given time. Here ω : E → R+associates each edge with a weight, which is the biggest payment amount betweennode vi and v j at that time.To construct G, we filter existing nodes and active channels at a given timein the following manner. For each channel, if there is no edge between the twonodes, we add one and set the edge’s weight to be the channel capacity. If an edgealready exists, we increase its weight by the channel capacity. Graph G makes itconvenient for us to study network connectivity or node reachability as it abstractsthe “is-connected” relationship between nodes.3.3 Network StructureWe study some descriptive statistics of the network graph G at three specific timeinstances: June 20, 2018 at 12:00, December 5, 2018 at 12:00 and April 1, 2019at 12:00. More details can be found in Table 3.1. We can see around 30% of thenodes in G are isolated. Probably those nodes just joined LN out of curiosity anddid not open new channels after their first one expired. We remove those isolatednodes as they do not communicate in the network and consider the resulting graphdenoted by G′.Figure 3.2a and Figure 3.2b demonstrate the degree distribution of G′ on April1, 2019. Figure 3.2a shows that it follows the power law, indicating there are manysmall-degree nodes and a few large-degree nodes [20]. The fitting line is y ∝ x−α .The larger the α , the less variable of a node’s degree. In G′ node degree representsthe number of direct neighbors. Note that at this time the node with the most18Table3.1:StatisticofGandG′ LCCTimeGG′ LCCnodeschannelscapacityisolatesnodes%ofGchannels%ofGcapacity%ofGclusterassortativity2018-06-202,6047,68625.417391,84570.857,67699.8725.3999.920.20-0.302018-12-054,41115,913462.701,5872,80463.5715,90399.94462.6899.990.23-0.252019-04-017,79641,7051,102.662,4095,34568.5641,67999.941,102.2299.960.28-0.3119neighbors is “powernode.io”, which has 1,249 direct neighbors. More specifically,Figure 3.2b displays the empirical cumulative distribution of node degrees. Theresult shows that 23% nodes have only one edge and 73% nodes have less than 10edges. This means that most nodes in LN can only send direct payments to veryfew neighbors, which is consistent with Figure 3.2a.In order to obtain more insights, we consider G′’s largest connected compo-nent (LCC) denoted by G′LCC. Recall that connected component (CC) is a subgraphwhere any two nodes u, v are connected to each other by certain paths [27]. Notethat nodes in different CC’s cannot reach each other. From Table 3.1 we can seethat G′LCC contains about 99% non-isolated nodes, 99.9% edges and network ca-pacity of G′. This indicates that G′LCC is a giant component that fills most of thenetwork, while the rest of the network is divided into a large number of small CC’s.A possible reason is that a majority of nodes in LN want to be able to communicateto each other, therefore they need to be part of LCC. There are very few nodes out-side G′LCC in G′, possibly these nodes just use LN for making direct point-to-pointpayments to a few specific neighbors. Hence, we focus on G′LCC in terms of graphmetrics and also in Chapter 4 when analyzing network connectivity performance.Table 3.1 provides some metrics of G′LCC. The clustering coefficient of G′LCC islarge (i.e, 0.20, 0.23, 0.28), revealing that if two users A and B both have channelswith C, A and B are likely to have a channel with each other. The three clusteringcoefficients on different days are very close, indicating that the tendency barelychanges with time. The assortativity coefficient [19] reveals preference for nodesto connect to similar nodes. Here it is negative, indicating a large degree user tendsto open channel with a small degree user rather than a large degree one. A possiblereason is that famous users (large degree nodes) tend to serve small users (smalldegree nodes) as intermediaries.20(a) Power law fitting(b) Cumulative distribution of degreesFigure 3.2: Degree distribution21Chapter 4Network Performance AnalysisIn this chapter we evaluate the performance of LN based on graph G. We firststudy network efficiency in terms of routing success rate, then network resilienceunder attack, both on April 1, 2019 at 12:00. In addition, we study the performanceevolution over time.4.1 Network Routing PerformanceRouting is the process of selecting a path between two nodes in the network. Since99.9% of the edges and deposits are contained in G′LCC as shown in Section 3.3,nodes and edges outside G′LCC barely participate in routing. So we focus on G′LCCin this section.Routing is very important in LN. Given the analysis of degree distribution inSection 3.3, most nodes have limited neighbors so they can make direct paymentswith very few nodes. However, two nodes might not want to open a channel whenthey need to make transactions. The reason is that adding edges (i.e., openingchannels) in LN costs money so it’s wasteful to open a new channel that will not befrequently used. Thus it’s necessary to use existing channels, especially for smallnodes (i.e., nodes with very small edges or capacities). Fortunately, payments canbe routed by using HTLC to ensure state consistency along the path as explainedbefore.We evaluate the network routing performance from three perspectives: network22connectivity, channel capacity and routing efficiency, which evaluate the routingpath lengths, routing transaction amount and routing success rate, respectively.4.1.1 Effective EccentricityNetwork routing performance is affected by the connectivity of the network. Toanalyze the length of shortest paths between a node and others, we define effectiveeccentricity as the least number of hops for a node to reach certain fraction ofthe network. Figure 4.1 gives the effective eccentrity of G′LCC with fraction α =0.7,0.9,1 on April 1, 2019 at 12:00. We can learn that effective eccentricity growswith α as it typically takes more steps to reach more nodes. The diameter of G′LCCis 11, which is the maximum shortest path lengths of the graph. Around 87% of thenodes can reach all other nodes within 8 steps, around 90% nodes can reach 90%of the network in 4 steps and around 72% nodes can reach 70% of the networkin 3 steps. This result suggests the network has the potential to perform efficientrouting.4.1.2 Channel Capacity DistributionThe capacity of a sequence of edges is restricted to the minimal edge capacity alongthe path. To perform routing, every edge on the path should have enough deposits.So we will investigate the channel capacity distribution. Before further analysis,we address the problem of channel direction and clarify a subtle difference betweenchannel capacities and edge capacities.As explained in Section 3.2, we neglect the channel direction by assumingall the channel balance belongs to the payment sender. Hence, we consider thebest routing performance. Recall the construction of G in Section 3.2, the edgeweight is the sum of capacities of all the channels between the same two nodes. Toachieve best routing performance, the maximal routing amount should depend onthe edge capacity instead of the channel capacity. That’s to say, two nodes can useall their channels for routing at the same time. The reason is that multiple channelsbetween two nodes can use several HTLC’s that share the same secret key R to23Figure 4.1: Cumulative distribution of effective eccentricityensure money in these channels is pulled correctly by the receiver.Figure 4.2 demonstrates the empirical cumulative distribution (CDF) of chan-nel capacity and edge capacity. The two CDFs are extremely close, indicating thatthe number of node pairs having multiple channels is really small. Interestingly, weobserve that the capacity does not follow uniform distribution. Instead, there aresome obvious jumps at certain capacities including 0.005,0.05,0.1, . . . ,0.2, reveal-ing that nodes like to choose these amounts when opening channels, probably forease and simplicity. We can see 90% of the channel capacity is below 0.10 BTC,indicating that for a payment amount bigger than 0.10 BTC, routing is unlikely tobe successful as only 10% channels are available.4.1.3 Network Routing EfficiencyBefore explaining network routing efficiency, we define the qualified component(QC) as a CC of the original network after removing all edges whose capacity is less24Figure 4.2: Cumulative distribution of channel capacitythan the targeted routing amount. Of all the QC’s, the largest one and second largestone (in terms of node numbers) is denoted by largest qualified component (LQC)and SQC. Here the LQC and SQC of G′LCC is represented by G′LQC and G′SQC. Asa simple example, in Figure 4.3, we want to perform a routing of 0.005 BTC andremove edges whose weights are less than 0.005. Then the LQC is formed by thenodes in the dashed circle, and the SQC is formed by the green nodes. Note thatthe QC’s depend on the routing amount.For any two nodes in the same QC, a path can be found with all edge weightsgreater than or equal to the routing amount. That’s to say, a routing of a targetamount is always successful in the QC. To consider the best routing performanceof LN, we focus on G′LQC. Thus network routing efficiency is defined as the fractionof G′LQC size over the network size. The routing efficiency reflects the success rateof a routing. In Figure 4.3, the network routing efficiency of 0.005 BTC is 5/11.Figure 4.4 gives the routing efficiency under different amounts. The horizon-tal axis is the routing amount percentile β of all edge weights. The black line25Figure 4.3: An example of routing efficiencywith circle markers represents the efficiency. We also plot the G′SQC size fractionusing the red line with triangle markers. The G′SQC is close to 0, indicating thatalthough nodes in other smaller QC’s can also perform routing inside themselves,it’s reasonable to consider only G′LQC for network routing efficiency. For a routingwith amount β of 50th percentile, the successful rate is 0.59. The efficiency isapproximately inversely proportional to amount except for some drastic change atsome points. This matches our observation in Section 4.1.2, that users prefer somespecific amounts as channel deposits.4.1.4 Routing EvolutionOur analysis above only studies the routing performance on April 1, 2019 at 12:00.To evaluate the evolution of routing performance over time, we plot the routingefficiency from April, 2018 to April, 2019 in Figure 4.5a. The blue, orange andgreen bars denote routing efficiency with routing amount β of 20th, 50th and 80th26Figure 4.4: Network routing efficiencypercentile, respectively. We can see the routing efficiency declines over time inyear 2018 and rises in 2019. A possible reason is that exchange markets or hubsemerge or play a more important role in LN.Figure 4.5b demonstrates the diameter of G′LQC with three different routingamount β ’s, which represents the longest routing path length. The result shows thatG′LQC diameter fluctuates from 6 to 11, and the smaller the β , the larger the G′LQCdiameter. This shows that the G′LQC under a large β is more densely connectedcompared to the G′LQC with a small β (i.e., nodes with higher channel capacitiesare more closely connected).4.2 Network Resilience Under AttackNetwork resilience is an important factor which reflects network’s anti-attack abil-ity. There exists some “big nodes” (e.g., nodes that have many channels) in LN.These nodes can serve as exchange markets and make it easier for small nodes to27(a) Routing efficiency(b) G′LQC diameter for routingFigure 4.5: Network routing efficiency evolution28use LN. (This is because small users cannot afford to open channels with everyother user as explained in Section 4.1.) Meanwhile, such important nodes may in-fluence network resilience. The problem is, how does the network perform whenunder attack (i.e., taking down important nodes)?To answer this question, we first rank nodes using three common algorithmsin graph theory, then evaluate which algorithm describes node importance the bestthrough network efficiency [13]. Furthermore, we analyze the anti-attack perfor-mance in terms of network capacity and G′LCC size.4.2.1 Identifying Important NodesWe select three common metrics or algorithms in graph theory that evaluate nodeimportance: closeness centrality, betweeness centrality and PageRank algorithm(PR) [3, 24, 32]. We then compare these three metrics using network efficiency.Network efficiency is the sum of the reciprocal of all shortest path lengths and itmeasures the efficiency of a network when exchanging information.Closeness centrality describes how close a node is to all other nodes. It iscalculated as the reciprocal of the sum of the length of the shortest paths betweenthe node and all other nodes in the graph. Thus, the more central a node is, thecloser it is to all other nodes. Betweeness centrality represents the degree to whichnodes stand between each other. A node with higher betweenness centrality wouldhave more control over the network, because information would pass through thatnode. PageRank algorithm evaluates the number and quality of the edges of a node.It was originally designed as an algorithm to rank web pages and calculated basedon the structure of the incoming links.We can attack a network by randomly or intentionally removing nodes or edges[6, 8]. Note that in LN, channels are kept locally between two users so the attackto a node will not spread out to its neighbors. Hence, we simulate attacks to LNby removing nodes from the most important to the least important one by one.Figure 4.6 shows the network performance under attack with nodes evaluated usingthe above three metrics. The horizontal axis denotes the fraction of removed nodesγ and the vertical axis denotes the resulting network efficiency. We can see that29efficiency decreases the fastest when nodes are ranked by PageRank algorithm,revealing that PageRank algorithm describes nodes importance the best. Therefore,we use PageRank algorithm to rank nodes in the rest of this section.Table 4.1 lists the 10 most important nodes evaluated by PageRank algorithm.For the ease of presentation, we use the first three bytes of a node’s public key todenote it. The aliases of these 10 nodes are listed below:• powernode.io• LightningPowerUsers.com• rompert.com• ACINQ• 1ML.comnodeALPHA• ln1.satoshilabs.com• BitMEXResearch• SLEEPYARK-v0.7.0• tippin.me• BOLTENING.clubWe can see the channel number is not necessarily consistent with the PageRankvalue. A possible reason is that a node connected to many unimportant nodesmight be less influential than a node connected to a few but important nodes. Thethird and fourth rows list the node capacity and node channel numbers. The lastrow shows the category of nodes. Some play the role of exchange markets andencourage others to connect to them. Some collect LN information and serve assearch and analysis engines. The tippin.me 1 is a project node that helps users toreceive tips by allowing others to use their channels in routing.1https://tippin.me/30Table4.1:Top10ImportantNodespubkey02809e0331f802ad6f03864e0217890279c203950302f67203c2ab02529dpr0.01290.01180.01170.01140.00940.00850.00750.00670.00630.0058capacity/BTC4.457325.22349.912932.41697.627027.034934.83191.300510.47209.6110channel1,2499351,082929833819732211589568categoryexchangeexchangesearchcompanysearchresearchresearch/companyresearch31Figure 4.6: Node importance evaluation4.2.2 Network Anti-Attack PerformanceWe evaluate LN resilience from network capacity and G′LCC size. Network capacityrepresents the total amount of money the network holds and G′LCC size reflects thebest routing efficiency (i.e., the routing amount is below the minimum channel ca-pacity so all edges are qualified). Before further analysis, we elaborate the detailedsituation of attacks to LN.When node A is taken down, it becomes uncooperative (i.e., unresponsive orfraudulent). Here taken down means that A does not respond because its underDDoS attack or offline, or it is a malicious node that doesn’t follow the protocol.If A refuses to response, all of its neighbors will have to wait until their channelsexpire and then can get their money back. If A claims a fake balance state, theother party can submit a proof (i.e., the last valid HTLC state) to the blockchainand claim the correct state. That’s to say, though there will be no actual loss in theend, all of A’s channels become unavailable and the deposits are locked for some32time. Thus, it’s reasonable for us to simulate an attack to a node by removing allits edges.Figure 4.7 demonstrates the network capacity and G′LCC size under attack, bothnormalized using original values. The results show that the network loses around94% capacity and 46% G′LQC nodes after removing just top 5% nodes and the net-work almost paralyzes if removing top 20% important nodes. This indicates thatLN relies heavily on a few important nodes, which is similar to the “robust yetfragile” structure of the Internet topology [7]. Moreover, we learn that there existsa trade-off between network resilience and the ease of use. That’s to say, on theone hand, hubs can make it more efficient for users to send transactions in LN, onthe other hand, they reduce the degree of decentralization of the network.Figure 4.7: Network resilience4.2.3 Resilience EvolutionPreviously, we focused on the network resilience on April 1, 2019 at 12:00. To33evaluate the evolution of resilience over time, we plot the G′LCC size and networkcapacity under attack from April, 2018 to April, 2019 in Figure 4.8a and Figure4.8b. In Figure 4.8a, the blue, orange and green bars denote G′LCC size (normal-ized using the original network size) after removing top 1%, 5% and 10% nodes,respectively. We can see G′LCC size decreases over time, especially in 2019. Recallin Section 4.1.4, we deduced the arise of of hubs in the same period. This sug-gests that hubs weaken LN’s ability to resist attacks, which is in consistent withour analysis in Section 4.2.2.Figure 4.8b shows that the network capacity under attack also decreases overtime. However, it experienced a clear “up and down” period in mid-July as wellas a sudden jump in mid-November. This indicates changes of network struc-ture, especially among important nodes. Actually this reflects appearance of newinfluential nodes. The LNBIG nodes as mentioned in Chapter 1 started to joinLN from November 13, 2018 and injected hundreds of bitcoins into the networkrapidly. At first these LNBIG nodes are not connected to existing hubs, whichmakes them less important when evaluated by PageRank algorithm. Thus they pre-serve some network capacity when other hubs are removed. The drop in Augustand mid-November is possibly caused by the strengthen of the connections amongimportant nodes.34(a) G′LCC size under attack(b) Network capacity under attackFigure 4.8: Network resilience evolution35Chapter 5Channel Characteristic AnalysisIn this chapter, we move from graph topology to channel characteristics betweennode pairs. We first analyze some channel descriptive statistics and then study paircommunication performance in terms of channel temporal distribution.5.1 Channel StatisticsTable 5.1 lists the statistics of all collected channels, including channel life, channelcapacity and channel costs (i.e., channel open fee and channel close fee). In LN, aslong as the two parties of a channel agree to cooperate, the channel can stay openwithout a mandatory timeout period. The channel can be closed unilaterally orbilaterally. If both parties decide to close the channel (because of channel depletionfor example), the channel will be closed immediately. If fraud happens or one partybecomes unresponsive, the other party can close the channel unilaterally.Channel life is the duration from channel open time to channel close time. Wecan see the average channel life is 29.89 days and the average channel capacityis 0.0196 BTC. Both have a large variance. This is intuitive as channel life andcapacity are decided by the two owners of the channel.Channel open or close fee is the fee of the broadcasted on-chain transactionthat opens or closes the channel. The higher the transaction fee a user offers, themore likely miners will add the transaction into their blocks and so the faster thetransaction will be confirmed. We can see the channel close fee is a little higher36Table 5.1: Channel Statisticsindexchannellife /daychannelcapacity /BTCchannel openfee /e-5 BTCchannel closefee /e-5 BTCaverage 29.89 0.0196 2.34 2.63median 12.44 0.0040 1.11 1.67COV 1,943.65 0.0015 0.00027 0.00037than the channel open fee, revealing that users tend to pay higher fees to close thechannel. Since higher fees can accelerate the process of blockchain transactions,a possible reason is that the channel close process is more urgent than the openprocess. This is intuitive as users want to close their channels under 3 conditions:the channel is depleted and unavailable; both users have agreed on the final balanceand want to claim their Bitcoin on the blockchain; there is a fraud and the honestparty needs to declare the true balance states in time. Thus it’s better to publish theclosing transaction on the blockchain faster.5.2 Pair Communication PerformanceThis section studies communication performance among pairs. We first analyzechannel number distribution of node pairs (i.e., how many channels a pair of nodesown) and then define communication ability and communication stability. Fur-thermore, we investigate these two metrics among multi-channel pairs. The threeobservation time we use are S1: June 20, 2018 at 12:00, S2: December 5, 2018 at12:00 and S3: April 1, 2019 at 12:00, respectively.Some node pairs in LN have more than one channels until the observationtime and are denoted by multi-channel pairs. Figure 5.1 shows the CDF of allpair channel numbers until S3. We can see that 85% pairs only have one channeland 11% pairs (i.e., 0.96-0.85) have two channels in total. The top three pairsthat have most channels are also listed here. Node BOLTENING.club and 038247opened 473 channels from February 16, 2019 to March 16, 2019, all with a depositof 0.0002 BTC. Most of their channels remain open until S3. Meanwhile, mostof the channels among the second and the third pairs are already closed. These37pairs are possibly maintaining multiple channels for testing the network functionor for future use, which we can tell from the aliases of the last pair (cln-test-01,cln-test-02).Figure 5.1: Cumulative Distribution of Pair Channel Numbers5.2.1 Pair Communication AbilityThe communication of a pair of nodes depends on all the channels they own. Thetime interval of these channels can be overlapping or non-overlapping. We definecommunication ability as the fraction of total time two nodes can communicate (viaat least one active channel) over the duration from the moment the two nodes firstopen a channel to the observation time. Nodes communication availability evalu-ates the probability that two nodes can make transactions since first connected.Definition: Pair communication ability, ρa(i, j) =∑m′i jk=1|s′k|ts−to1 , where ts is the ob-servation time, mi j is the total number of channels opened before ts between nodei and j, tok and tck is the open and close time of the kth channel between i and j,channel is sorted in ascending order of tok , so to1 is the open time of the first channel38between i and j, sk = (tok ,min{tck , ts}),k= 1,2 · · ·mi j, sk is the time interval of kthchannel, |sk| = min(tck , ts)− tok , (s′1,s′2 · · ·s′m′i j) = (s1∪ s2 · · · ∪ smi j) is the union ofall multi-channel intervals.As a simple example, in Figure 5.2, the communication ability until ts is ρa(1,2)=tc2(1,2)−to1(1,2)ts−to1(1,2) for node pair (1, 2), ρa(1,4)= 1, ρa(2,3)=(tc1(2,3)−to1(2,3))+(tc2(2,3)−to2(2,3))ts−to1(2,3) .Figure 5.2: Pair Communication PerformanceIn Figure 5.3a, the solid lines show the CDF of communication ability ρaamong all pairs. The red, black and blue lines correspond to S1, S2 and S3. Wecan see the overall ρa decreases from S1 to S2, indicating that many pairs losethe ability to send payments. It then increases from S2 to S3, possibly becausesome pairs maintained a long-lasting channel. Until S3, only 60% of the pairs cancommunicate for more than 30% of the time and about 41% of the pairs can keepcommunicating all the time (i.e., ρa = 1) since opening their first channel. Thisdemonstrates that the communication status among pairs is not quite reliable.5.2.2 Pair Communication StabilityCommunication between two nodes is interrupted if their multi-channel intervalsare not overlapping (i.e., a new channel is opened after the old channel is closed).To describe the continuous communication ability, we define pair communicationstability as the fraction of the longest continuous communication time over theduration from the pair are firstly connected to the observation time. It evaluatesthe probability that two nodes can continuously make transactions since their first39connection.Definition: Pair communication stability ρs(i, j) =maxk|s′k|ts−to1 . This is similar toρa(i, j) except that the denominator is the longest unioned channel interval. Henceρs(i, j)<= ρa(i, j).For example, in Figure 5.2, the communication stability until ts is ρs(1,2) =tc2(1,2)−to1(1,2)ts−to1(1,2) for node pair (1, 2), ρs(1,4)= 1, ρs(2,3)=max{tc1(2,3)−to1(2,3), tc2(2,3)−to2(2,3)}ts−to1(2,3) .The dotted lines in Figure 5.3a demonstrate the CDF of communication stabil-ity ρs among all pairs until S1, S2 and S3. We can see ρs is quite close to ρa for thesame observation time. This is because most pairs own only one channel as shownin Figure Figure 5.1.5.2.3 Multi-channel Pair Communication PerformanceThe characteristics of multi-channel pairs are important. This is because with thedevelopment of LN, more and more existing channels will be closed or depleted,thus new channels are needed among node pairs. To obtain further insights aboutcurrent multi-channel pairs and their channel temporal distribution, we study theirρa and ρs in Figure 5.3b.Figure 5.3b shows that ρa of multi-channel pairs is significantly higher thanρs for the same observation time, indicating their channel intervals are not over-lapping. The reason is that ρa = ρs if multi-channel intervals are overlapping. Forexample in Figure 5.2, ρa(2,3)> ρs(2,3) and ρa(1,2) = ρs(1,2) as the two chan-nels for pair (2, 3) are non-overlapping while the two channels of pair (1, 2) areoverlapping. This is intuitive as it’s unnecessary to maintain several channels withthe same peer at the same time.40(a)(b)Figure 5.3: Channel temporal distribution: 5.3a shows communication per-formance for all node pairs, solid lines for ρa, dotted lines for ρs, red,black and blue lines correspond to S1, S2 and S3; 5.3b shows communi-cation performance for multi-channel pairs.41Chapter 6Conclusions and Future WorkLN is a “Layer 2” system that aims to increase throughput of current Bitcoin net-work. We conduct a measurement study on LN in this thesis. Our graph construc-tion of LN provides some insights behind the user behavior. Through routing anal-ysis, we demonstrate the routing success rate relies heavily on the routing amount.Through resilience analysis, We identify a “robust yet fragile” structure in LN. Be-sides, our investigation of channel characteristics shows more efficient ways to useLN. The above observations indicate several issues of the current LN and suggestways of future protocol design. Below we conclude our findings in this thesis andenumerate some directions for future work.6.1 Improving Routing EfficiencyOur routing analysis in Section 4.1.3 and Section 4.1.4 revealed that for a largeamount transaction (e.g., above the median of all channel capacities), the successrate of payment routing is low and is decreasing over time. Therefore, users whowant to send large amount payments through LN should open a channel directlywith their receivers. Besides, our analysis of pair payment channels in Section 5.2indicated that the communication among most pairs are not stable. Hence, we sug-gest that some important nodes can serve as exchange markets maintaining stablecommunication and other users only need to connect to these hubs. In this way, therouting success rate can be greatly improved and the length of routing path can be42reduced.As directions for future work, we propose studying all paths between a peer.For a large transaction, we can split it to multiple small-amount transactions andsend them through different paths separately. In this way, we can make full useof those channels with small deposits and increase the success rate of routing.Another factor we can take account of is the channel fee. Nodes usually need topay some fees to use others’ channels as intermediaries for routing. A more generalrouting algorithm should not only find a path between users, but minimize the feesalong the path.6.2 Enhancing Network ResilienceThough the underlying Bitcoin Network is ideally decentralized, we found that thecurrent LN relies heavily on some important nodes in Section 4.2.2. Users shouldbe aware of such potential risks even if they can recover their balances after theattack. Furthermore, our work demonstrated that the topology among those im-portant hubs can affect network resilience. Hence, it would be an interesting topicto adjust connections of exchange markets in order to get the best performance interms of both routing efficiency and resilience.In this thesis we simulated attacks to the LN just by removing top importantnodes. Another interesting question that can be studied is to design more powerfulattacking vectors. For example, attackers may collude to isolate some importantnodes and partition the network.6.3 Node Evaluation SystemNodes have many properties such as node capacity, channel numbers, node uptimeand channel stability (metrics we defined in Section 5.2). As future work, we canapply the trust computation mechanisms [4, 21, 22] in Internet of Thing area to thescenario of LN and build a more reliable and efficient system based on the attributesof nodes. For example, we can build a node evaluation system in both subjectiveand objective ways. In the subjective model, each node computes the score of itsneighbors locally on the basis of its own experience. In the objective model, theinformation about each node is distributed and stored making use of a distributed43hash table structure so that any node can make use of the same information.Such node evaluation system can be maintained through a weighted combina-tion of node properties. By giving higher weights to attributes of interest, userscan select their neighbors more efficiently. In addition, such rating system can beextended to evaluate different channels. Nodes can score channels they have usedfor routing or rebalancing and send that score to others. This will helps others tochoose paths when multiple ones are available.6.4 Protocol SimulationSeveral existing protocols in LN are closely related to the network topology [11,29]. Thus, the use of real-world offchain network topology can better examine theperformance of those protocols. In addition, the network topology we provide canbe taken as a unified test platform for comparing similar protocols.44Bibliography[1] V. Bagaria, S. Kannan, D. Tse, G. Fanti, and P. Viswanath. Deconstructingthe blockchain to approach physical limits. arXiv preprintarXiv:1810.08092, 2018. → page 2[2] A. Biryukov, D. Khovratovich, and I. Pustogarov. Deanonymisation ofclients in bitcoin p2p network. In Proceedings of the 2014 ACM SIGSACConference on Computer and Communications Security, pages 15–29.ACM, 2014. → page 6[3] U. Brandes. A faster algorithm for betweenness centrality. Journal ofmathematical sociology, 25(2):163–177, 2001. → page 29[4] D. Chen, G. Chang, D. Sun, J. Li, J. Jia, and X. Wang. Trm-iot: A trustmanagement model based on fuzzy reputation for internet of things.Comput. Sci. Inf. Syst., 8(4):1207–1228, 2011. → page 43[5] T. Chen, Y. Zhu, Z. Li, J. Chen, X. Li, X. Luo, X. Lin, and X. Zhange.Understanding ethereum via graph analysis. In IEEE INFOCOM 2018-IEEEConference on Computer Communications, pages 1484–1492. IEEE, 2018.→ page 5[6] G. Dong, J. Gao, R. Du, L. Tian, H. E. Stanley, and S. Havlin. Robustness ofnetwork of networks under targeted attack. Physical Review E, 87(5):052804, 2013. → page 29[7] J. C. Doyle, D. L. Alderson, L. Li, S. Low, M. Roughan, S. Shalunov,R. Tanaka, and W. Willinger. The “robust yet fragile” nature of the internet.Proceedings of the National Academy of Sciences, 102(41):14497–14502,2005. → page 33[8] J. Gao, S. V. Buldyrev, S. Havlin, and H. E. Stanley. Robustness of a networkof networks. Physical Review Letters, 107(19):195701, 2011. → page 2945[9] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand:Scaling byzantine agreements for cryptocurrencies. In Proceedings of the26th Symposium on Operating Systems Principles, pages 51–68. ACM,2017. → page 2[10] M. Green and I. Miers. Bolt: Anonymous payment channels fordecentralized currencies. In Proceedings of the 2017 ACM SIGSACConference on Computer and Communications Security, pages 473–489.ACM, 2017. → page 5[11] R. Khalil and A. Gervais. Revive: Rebalancing off-blockchain paymentnetworks. In Proceedings of the 2017 ACM SIGSAC Conference onComputer and Communications Security, pages 439–453. ACM, 2017. →pages 3, 5, 44[12] P. Koshy, D. Koshy, and P. McDaniel. An analysis of anonymity in bitcoinusing p2p network traffic. In International Conference on FinancialCryptography and Data Security, pages 469–485. Springer, 2014. → page 5[13] V. Latora and M. Marchiori. Efficient behavior of small-world networks.Physical review letters, 87(19):198701, 2001. → page 29[14] M. Lischke and B. Fabian. Analyzing the bitcoin network: The first fouryears. Future Internet, 8(1):7, 2016. → page 5[15] A. Miller, J. Litton, A. Pachulski, N. Gupta, D. Levin, N. Spring, andB. Bhattacharjee. Discovering bitcoin’s public topology and influentialnodes. 2015. → pages 5, 6[16] A. Miller, I. Bentov, S. Bakshi, R. Kumaresan, and P. McCorry. Sprites andstate channels: Payment networks that go faster than lightning. InInternational Conference on Financial Cryptography and Data Security,pages 508–526. Springer, 2019. → pages 3, 5[17] S. Nakamoto et al. Bitcoin: A peer-to-peer electronic cash system. 2008. →page 1[18] T. Neudecker, P. Andelfinger, and H. Hartenstein. Timing analysis forinferring the topology of the bitcoin peer-to-peer network. In UbiquitousIntelligence & Computing, Advanced and Trusted Computing, ScalableComputing and Communications, Cloud and Big Data Computing, Internetof People, and Smart World Congress(UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld), 2016 Intl IEEEConferences, pages 358–367. IEEE, 2016. → page 546[19] M. E. Newman. Mixing patterns in networks. Physical Review E, 67(2):026126, 2003. → page 20[20] M. E. Newman. Power laws, pareto distributions and zipf’s law.Contemporary physics, 46(5):323–351, 2005. → page 18[21] M. Nitti, R. Girau, L. Atzori, A. Iera, and G. Morabito. A subjective modelfor trustworthiness evaluation in the social internet of things. In 2012 IEEE23rd international symposium on personal, indoor and mobile radiocommunications-(PIMRC), pages 18–23. IEEE, 2012. → page 43[22] M. Nitti, R. Girau, and L. Atzori. Trustworthiness management in the socialinternet of things. IEEE Transactions on knowledge and data engineering,26(5):1253–1266, 2013. → page 43[23] M. Ober, S. Katzenbeisser, and K. Hamacher. Structure and anonymity ofthe bitcoin transaction graph. Future internet, 5(2):237–250, 2013. → page5[24] K. Okamoto, W. Chen, and X.-Y. Li. Ranking of closeness centrality forlarge-scale social networks. In International Workshop on Frontiers inAlgorithmics, pages 186–195. Springer, 2008. → page 29[25] J. Poon and T. Dryja. The bitcoin lightning network: Scalable off-chaininstant payments. 2016. → pages 3, 4[26] F. Reid and M. Harrigan. An analysis of anonymity in the bitcoin system. InSecurity and privacy in social networks, pages 197–223. Springer, 2013. →page 5[27] M. Rigo. Advanced graph theory and combinatorics. John Wiley & Sons,2016. → page 20[28] D. Ron and A. Shamir. Quantitative analysis of the full bitcoin transactiongraph. In International Conference on Financial Cryptography and DataSecurity, pages 6–24. Springer, 2013. → page 5[29] S. Roos, P. Moreno-Sanchez, A. Kate, and I. Goldberg. Settling paymentsfast and private: Efficient decentralized routing for path-based transactions.arXiv preprint arXiv:1709.05748, 2017. → pages 3, 5, 44[30] I. A. Seres, L. Gulya´s, D. A. Nagy, and P. Burcsi. Topological analysis ofbitcoin’s lightning network. arXiv preprint arXiv:1901.04972, 2019. →page 547[31] P. Wang, H. Xu, X. Jin, and T. Wang. Flash: Efficient dynamic routing foroffchain networks. arXiv preprint arXiv:1902.05260, 2019. → page 5[32] W. Xing and A. Ghorbani. Weighted pagerank algorithm. InCommunication Networks and Services Research, 2004. Proceedings.Second Annual Conference on, pages 305–314. IEEE, 2004. → page 2948
Thesis/Dissertation
eng
Electrical Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
A measurement study of Bitcoin Lightning Network
Text