key: cord-0059423-hv5tbzht authors: van Dam, Gijs; Kadir, Rabiah Abdul; Nohuddin, Puteri N. E.; Zaman, Halimah Badioze title: Improvements of the Balance Discovery Attack on Lightning Network Payment Channels date: 2020-08-01 journal: ICT Systems Security and Privacy Protection DOI: 10.1007/978-3-030-58201-2_21 sha: d0290a5c123c3be8c67b3ab3cbf0f216a0b11405 doc_id: 59423 cord_uid: hv5tbzht The Lighting Network (LN) is a network of micropayment channels that runs on top of Bitcoin. The balances of payment channels are not broadcasted to the LN network to preserve the privacy of the nodes participating in the network. A balance disclosure attack (BDA) has been proven to be successful in determining the balance of large amounts of channels in the network. In this paper we propose an improved algorithm for the BDA as well as a new type of attack that leverages the differences between LN client software implementations. Our improved algorithm extends the original BDA by performing payments from both sides of the channel. The new attack uses malformed payments to shutdown payment channels an adversary is not part of. Bitcoin, the cryptocurrency with the largest market capitalization, has inherently limited scalability. Bitcoin generates 1 block of transactions every 10 min and the size of that block is limited to 1 MB. With a basic transaction taking up 250 bytes and an average transaction size of 500 bytes the network has a maximum capacity of 4000 transactions per block and an average capacity of 2000 transactions per block. This boils down to 3-7 transactions per second. Increasing this capacity by either increasing the block size or the rate at which blocks are generated reduces the security of the Bitcoin network [1] . Increasing scalability of Bitcoin without abandoning security remains desirable. Firstly because if the amount of transactions being broadcasted exceeds the capacity of the network, the law of supply and demand dictates that the transaction fees will increase [2] Secondly, if we want to achieve a viable alternative to current centralized payment networks we need to achieve comparable throughput which is in the order of magnitude of several thousand transactions per second. It was Satoshi Nakamoto, the mysterious pseudonymous person or group of persons famous for developing Bitcoin, who suggested the use of transaction replacement for something he called high frequency trading [3] . In Nakamoto's proposal a group of parties could keep updating a transaction that had yet to be committed. The order of the updates was kept by a sequence number. Only the last agreed upon transaction needed to be broadcast. By doing so all the transactions prior to the final transaction were kept off-chain. Nakamato's approach couldn't operate in a trustless environment and was never seriously considered. LN is a peer-to-peer (P2P) network of connected nodes that uses Poon-Dryja [4] payment channels. Two connected nodes can open up a payment channel between them. A transaction from node A to node B can only happen if there is enough balance on the side of node A. Likewise, a transaction from node B to node A can only happen if there is enough balance on the side of node B. Both balances added together define the capacity of the channel. To create a transaction between two nodes that don't have a payment channel between them, multiple payment channels can be connected to form a route, as long as the balances along that route allow for the payment. This is known as a multihop payment. To participate in LN you have to run LN client software. Each LN client follows the LN specifications, set out in the Basis of Lightning Technology (BOLT) [5] documents. Balances on the other hand are kept private and are never broadcasted on the network. The only balances known to a node are the balances of the channels that node participates in. Because of this it is impossible to know upfront whether a multi-hop payment will succeed, and there is only one way to find out: executing the payment. By executing multiple (fake) payments it is possible to probe the unknown balance of a payment channel. Disclosing balances this way has been dubbed the balance discovery attack (BDA) [6] . LN uses an onion routing [7] scheme called Sphinx [8] for the routing of payments. In this study we analyzed potential BDA algorithm improvements and the role of LN client software in BDA. We propose an improvement to the basic algorithm for BDA that achieves a two-fold increase of the upper limit of balances that can be disclosed. Furthermore, we found that in certain situations LN client software can be leveraged to remove the upper limit of BDA completely. Finally we describe a specific situation where the interplay between different LN client software types leads to the permanent shutdown of a payment channel. This new attack, dubbed Payment of Death (POD), makes it possible to remotely shut down channels. We will show that POD is a threat to the integrity of LN, as it has the potential for a malicious party to shutdown 17.5% of the network capacity. A formal analysis of privacy in the context of PCNs has been hindered by a lack of a rigorous definition of the PCN protocols, the absence of a threat model, and the ambivalent interpretations of the concept of anonymity [9] . A threat model is necessary to perform a formal analysis of privacy in the setting of trustless PCNs. Malavolta [9] describes a threat model with four notions of interest: -Balance security: participants don't run the risk of losing coins to a malevolent adversary. -Serializability: executions of a PCN are serializable as understood in concurrency control of transaction processing, i.e. for every concurrent processing of payments there exists an equivalent sequential execution. -(Off-path) value privacy: malicious participants in the network cannot learn information about payments they are not part of. -(On-path) relationship anonymity: given at least one honest intermediary, corrupted intermediaries cannot determine the sender and the receiver of a transaction better than just by guessing. In the basic scenario for channel balance discovery [6] it is assumed that there is an open payment channel AB between Alice, A, and Bob, B, with capacity C AB . The goal of the adversary, Mallory, M , is to discover the balances of each node in channel AB: balance AB and balance BA . To do so Mallory opens up a channel with Alice (see Fig. 1 ). Mallory tries to disclose balance AB by routing invalid payments through M ↔ A ↔ B, using the basic BDA algorithm. The inputs for the algorithm are the target node B, the route to the target node, the value range to search in, given by 0 and C AB , and the required accuracy for the algorithm. The algorithm creates invalid payments by using random, invalid payment hashes for each payment. The value for each payment follows a binary search pattern for which the initial lower and upper bounds are given by the value range input. Bob, the recipient of the payment, is the only one who can determine that a payment from Mallory is invalid. Therefore, receiving an error stating the payment hash is invalid, means that balance AB was sufficient to route the payment, because if it was not, Alice would have returned an error stating insufficient funds and Bob would never have known about the payment. This fact is leveraged by updating the lower bound of the binary search to the value of the last payment. If however the failure message states insufficient funds, the upper bound is updated with the value of the last payment. This process repeats itself recursively until the difference between the upper bound and the lower bound of the binary search is within the threshold set by the accuracy input. The algorithm returns a tuple that gives the range within which balance AB sits. Since the capacity of the channel C AB is known, the balance BA can be calculated with balance BA = C BA − balance AB . By periodically executing a BDA, an adversary can monitor balances over time. This allows for tracing transactions. Therefore, this type of attack poses a threat for the value privacy as described in the threat model above. In order to research the role of LN client software in BDA we must first determine which LN clients are available. We used 1ML Lightning Network Search and Analysis Engine 1 to estimate respective proportions of each client in LN. 1ML is a website that publishes the current state of the LN graph and allows for node owners to self-report on a voluntary basis the type of client they use. We chose the three LN clients with the largest network share to run a local cluster of LN nodes, each node running one of three supported clients. All LN nodes used Bitcoin Core's Bitcoind implementation as the Bitcoin backend. Bitcoind ran in regression testing mode, known as regtest mode. This is a local test mode, making it possible to almost instantly create blocks with no real-world value. Using regtest mode, the different implementations could be tested without incurring transaction fees for the on-chain transactions and without having to wait for blocks to be mined. On this cluster we analyzed the basic and improved algorithm having the LN nodes in each possible permutation of supported clients. This helped us determine if the new algorithm was to be considered an improvement and whether client differences could play a role in BDA. The original algorithm [6] is bound by an upper limit set by MAX PAYMENT ALLOWED. This limit makes it impossible to probe balances that are higher than 2 32 − 1 msat. This paper proposes an improved algorithm. Consider a channel AB with capacity C AB . Since C AB = C BA = balance AB + balance BA , the following holds For all channels with a capacity C AB < 2 33 there's always a balance lower than 2 33 2 = 2 32 on one end of the channel. With this knowledge we can extend the algorithm by letting it probe the channel from the other side, once we assess that the balance is higher than MAX PAYMENT ALLOWED on the initial probing side. This setup requires an optional second channel from the adversary Node M to Node B, to be able to probe the channel between Node A and Node B from the side of Node B (See Fig. 2 ). Algorithm 1 describes BDA with optional two-way probing for channels with a capacity above MAX PAYMENT ALLOWED. Algorithm 1 takes the same input parameters as the basic algorithm and returns the same tuple. Data: route, target, maxFlow, minFlow, accuracy treshold Result: bwidth, an array of tuples that gives the range of bandwidth discovered for each channel 1: missingT ests ← T rue 2: bwidth.max ← maxF low 3: bwidth.min ← minF low 4: channelCapacity ← getInf o(target).capacity 5: while missingTests do 6: if bwidth.max − bwidth.min ≤ accuracy threshold then 7: missingT ests ← F alse 8: end if 9: if bwidth.max ≥ 2 32 then 10: flow ← 2 32 − 1 If C AB is higher than MAX PAYMENT ALLOWED, the algorithm will try to send a fake payment with a size of exactly MAX PAYMENT ALLOWED. If that payment is possible, we have assessed that we are on the wrong end of the channel for probing the balance. The algorithm now calls itself with the target node and the final node of the route switched. The algorithm assumes that there is a route from the adversary to this new target node. The return value of that call is balance BA , for calculating balance AB we use the following formula: If C AB > max payment allowed and C AB < 2 × max payment allowed, the value of the first payment will not be exactly in the middle of the value range for the binary search, since it will use the fixed value of MAX PAYMENT ALLOWED for the first payment. That makes this algorithm slightly less computationally efficient then a perfect binary search, but it minimizes the use of the optional second channel. We confirmed the improvements provided by the two-way probing algorithm in two ways. Firstly we confirmed the feasibility of the algorithm in our local testing cluster. Secondly we analyzed LN running on top of Bitcoin mainnet, to estimate the number of channels that can have their balances disclosed by this algorithm and compare this to the earlier version of this attack. We ran the Two-way Probing algorithm with every possible permutation of clients. By analyzing the responses from the clients, and analyzing the code of the respective clients on GitHub, we found that not every client implemented the MAX PAYMENT ALLOWED the same way. On May 23rd, 2017 the BOLT specification was changed 2 by Paul "Rusty" Russel, who authored the majority of the BOLT documents. The variable containing the payment amount, amount msat, was changed from a 32 bit unsigned integer to a 64 bit unsigned integer. This meant that before that change it was impossible to create a payment bigger than 2 32 − 1 whatsoever, but after that change in theory it was possible to create bigger payments. Additional specifications required the sending node to set the four most significant bytes of amount msat to 0. But those additional requirements aren't implemented equally by the three main clients. C-lightning is the only client that fully adheres to the requirements. Eclair has a limit of 5 · 10 9 msat. LND doesn't verify the amount for certain RPC's. By using the unverified RPC in our algorithm we could send fake payments up to the Fig. 3 . Cumulative percentage graph of payment channels ordered by increasing capacity. max payment allowed shows the percentage of channels with disclosable balances using the basic BDA algorithm. 2× max payment allowed shows the percentage of channels with disclosable balances using the two-way probing algorithm. maximal channel capacity. This meant that we can disclose any balance between two LND Nodes, even if the balance is above the upper limit of the two-way probing algorithm. In the scenarios where Alice is a LND node and Bob is an Eclair node or both are Eclair nodes, balances up to 5 · 10 9 msat can be disclosed without making use of two-way probing. The two-way probing algorithm works regardless of the client software. So we can look at the channel capacity of all public channels in the LN graph and determine the proportion of channels that are now susceptible to this type of attack based on a snapshot of the network taken on the 3rd of October, 2019 (see Fig. 3 ). To estimate the number of channels susceptible for BDA above the 2 33 limit set by the Two-way algorithm, we need to know the type of client on either side of a channel. There's no known way of figuring out what kind of client is installed, but if you know the proportion of each client type in the LN, it is possible to estimate the amount of channels for each specific combination of clients. We queried 1ML for each node in our snapshot of the LN. We identified the client type for 273 nodes out of 3608 and estimated the proportion of nodes running different clients based on that data (See Table 1 ). The LN is a graph G, with the number of vertices n = |G(V )| and the number of edges m = |G(E)|. Our analysis yielded the following values for n and m: n = 3608 m = 9438 with 1086 channels having a capacity greater than 2 32 and 540 channels having a capacity greater than 2 33 . The client software defines the type of the vertex. type l for LND nodes, type c for c-lightning nodes and type e for Eclair nodes. An edge is said to be of type (l,c) if it connects a type l vertex and a type c vertex. The graph is without self-loops and undirected, so edge type (l,c) ≡ type (c,l) . Since we know the proportions of the different vertex types we can calculate the probability of an edge being of a specific type. -P (type (l,l) ) = 0.8059 2 -P (type (c,c) ) = 0.1465 2 -P (type (e,e) ) = 0.0403 2 -P (type (l,c) ) = 2 × 0.8059 × 0.1465 -P (type (l,e) ) = 2 × 0.8059 × 0.0403 -P (type (c,e) ) = 2 × 0.1465 × 0.0403 Assuming vertex type and channel capacity have a covariance of zero, the number of edges of each edge type, having a capacity greater than 2 33 is calculated as follows: P (type ([c,e,l],[c,e,l]) ) × 540. We are interested in the type (l,l) and type (l,e) channels, because the type (l,c) channels are susceptible to the Payment of Death explained below, which doesn't allow for discovering the balance. So the amount of channels with a capacity above 2 32 is 540 × P (type (l,l) ) + 540 × P (type (l,e) ) = 386 channels. So a total of 9438 − 540 + 386 = 9284 channels have balances that can be disclosed. This is 98.4% of all channels. In the case where Alice is a LND node and Bob is a C-lightning node, we saw interesting behavior of the C-lightning node which turned out to be a vulnerability of the current LN that can be exploited. If a C-lightning node is being requested to route a payment to another node, or is the receiver of a payment, with an amount that his higher than MAX PAYMENT ALLOWED, it decides to fail the channel with the requesting node and close down that channel. Since LN uses onion routing, the requesting node from the perspective of the c-lightning node, is the one that comes just before it in the route. But that isn't necessarily the node from which the payment originated. Consider the basic scenario (see Fig. 1 ), where Mallory and Alice run LND, and Bob runs c-lightning. Both channels between Mallory and Alice and between Alice and Bob have balances that allow for payments bigger than the MAX PAYMENT ALLOWED limit. If Mallory would create a fake payment with an amount above that limit, Bob would close down it's channel with Alice, without Alice being able to mitigate this in any way. We coined the term Payment of Death (POD) for this attack, after the infamous Ping of Death. For the amount of channels affected by the POD we are interested in all type (l,c) channels, with a balance above MAX PAYMENT ALLOWED. This is 1086× P (type (l,c) ) = 256 channels, meaning that 2.7% of all channels can be shutdown by using malformed payments. We have notified the developers of the LN implementations by means of a responsible disclosure. Herrera-Joancomarti [6] reported that 89.10% of all channels could have their balances exactly disclosed. Our research showed that we can improve this to 98.37% of all channels, a 9.27% point increase (See Table 2 ). The basic BDA performed slightly less in our snapshot of the LN network because in the period between the two snapshots of the 8th of January, 2019 and the 3rd of October, 2019, the percentage of channels with a capacity C of C > 2 32 slightly increased. The properties of the vulnerability make it so that the highly capitalized nodes are more vulnerable, since it are these nodes that have channels with a balance above MAX PAYMENT ALLOWED limit. The average capacity of those 1086 channels is 10196116 msat. Using that average combined with the estimated proportions of affected channels, 17.5% of the total capacity of the network could be taken down with an organized attack. These proportions align with proportions earlier found through alternative methods [10] . It's reasonable to assume that these channels are responsible for routing a disproportionate amount of the payments on the network. Such an attack could have substantial impact on the ability to route payments of the network as a whole. The closing of channels comes at a cost to the victim nodes, since you have to broadcast on-chain transactions for closing a channel and again for reopening it. Those transactions have transaction fees attached to it. Furthermore, channel age is used as heuristic for determining the reliability of a node for routing payments, so routing nodes have an incentive to keep channels open as long as possible. Clients should adhere to the BOLT specification, making it impossible to create payments with a value higher than MAX PAYMENT ALLOWED and deny to consider payments with a value above the MAX PAYMENT ALLOWED for routing. The latter would make it impossible to disclose balances above 2 33 msat. Secondly, clients should not consider a malformed payment a reason for permanently closing down a channel. This would make it impossible to mount a POD attack. Limiting the number of payment requests per unit of time or randomly deny payment requests following a configurable dropping rate [6] are unfeasible. These countermeasures, implemented generically, come at a high cost for usability of the network as a whole. So a selective approach is preferable, identifying nodes that are the source of suspicious payment requests, and limit or deny requests from these nodes. But this selective approach could quite easily be circumvented by inserting different non-malicious nodes with known balances in the route in subsequent payment requests. This way the source of the attack from the point of view of the attacked node is not determinable and each non-malicious node itself doesn't see a pattern that resembles an attack. This paper presented an improvement to the algorithm of the original BDA. We showed that by approaching a payment channel from both sides instead of from one side, payment channels with a higher capacity than in the original BDA are now also susceptible to this attack. Since monitoring balances over time makes it possible to detect payments, it can be used to learn information about payments an adversary isn't part of [9] . We exposed differences in the implementation of the BOLT specification by the main three clients. These differences led us to develop a new attack that closes down remote payment channels. We estimated the proportions of each client in LN, by using self-reported information. Based on these proportions we estimated that this attack can be used to take down an important part of LN's entire network capacity. Secure high-rate transaction processing in bitcoin From mining to markets: the evolution of bitcoin transaction fees Anti DoS for tx replacement The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments On the difficulty of hiding the balance of lightning network channels Anonymous connections and onion routing Sphinx: a compact and provably secure mix format Concurrency and privacy with payment-channel networks LockDown: Balance Availability Attack against Lightning Network Channels We would like to thank the National University of Malaysia, which has funded the publication of this paper with grant ZG-2018-001.