Tuesday, January 7, 2020

Bitcoin's Lightning Network (updated)

Discussions of cryptocurrencies and other blockchain technologies are bedeviled by a nearly universal assumption that attributes that are possible to achieve in theory are guaranteed to be realized in practice. Examples include decentralization and anonymity.

Back in June David Gerard asked:
How good a business is running a Lightning Network node? LNBig provides 49.6% ($3.7 million in bitcoins) of the Lightning Network’s total channel liquidity funding — that just sits there, locked in the channels until they’re closed. They see 300 transactions a day, for total earnings on that $3.7 million of … $20 a month. They also spent $1000 in channel-opening fees.
Even if the Lightning Network worked (which it doesn't), and were decentralized (which it isn't), Gerard's point was that the transaction fees were woefully inadequate to cover the costs of running a node. Now, A Cryptoeconomic Traffic Analysis of Bitcoin’s Lightning Network by the Hungarian team of Ferenc Béres, István A. Seres, and András A. Benczúr supports Gerard's conclusion with a detailed analysis.

Below the fold, some commentary.

As usual, Bitcoin enthusiasts are taken in by the hype. As Béres et al write:
LN’s core value proposition is that Bitcoin users can send low-value payments instantly in a privacy-preserving manner with negligible fees, which has led to quite a widespread adoption of LN among Bitcoin users.
Béres et al built a simulation and calibrated it against the public information they could find about the Lightning Network. Experiments they ran using their simulation led them to conclude that the "negligible fees" are massively subsidized by the large Lightning nodes. From their abstract:
Our findings on the estimated revenue from transaction fees are in line with the widespread opinion that participation is economically irrational for the majority of the large routing nodes who currently hold the network together. Either traffic or transaction fees must increase by orders of magnitude to make payment routing economically viable. We give worst-case estimates for the potential fee increase by assuming strong price competition among the routers. We also estimate how current channel structures and pricing policies respond to a potential increase in traffic, and show examples of nodes who are estimated to operate with economically feasible revenue.
And, because the Lightning Network isn't decentralized, "privacy-preserving" is a myth. Béres et al's second conclusion is:
Our second set of findings considers privacy. Even if transactions are onion routed, strong statistical evidence on payment source and destination can be inferred, as many transaction paths only consist of a single intermediary by the side effect of LN’s small-world nature.

Negligible Fees

Because Bitcoin failed to achieve Satoshi Nakamoto's goal of supporting "small, casual payments", the major goal of the Lightning Network was to impose much lower fees than the Bitcoin blockchain. But Béres et al find that the only non-subsidized major node charges fees similar to those for Bitcoin itself:
Based on our findings, the annual RoI is way below 5% for almost all relevant entities. The only exception is rompert.com, who indeed applies orders of magnitude higher fees than others. It is interesting to see that despite its high transaction fees, it has the highest daily traffic in the simulation. Note that rompert.com applies base fees close to on chain fees, which may invalidate the assumptions of our simulator if participants fall back to on-chain rather than paying rompert.com routing fees.
And again:
The reason behind low annual RoI is low transaction fees. Table 1 shows that for forwarding α= 60,000 Satoshis, most of these entities ask for less then 100 Satoshis, which is less than 0.2% of the payment value. Very low fees may uphold LN’s core value proposition, but they are economically irrational for the central routers holding the network together. Based on our simulations, for several routers (e.g., LNBIG.com, yalls.org, ln1.satoshilabs.com, etc.), fees should be in the range of a few thousand Satoshis to reach a 5% annual RoI, that is approximately the magnitude of on-chain transaction fees (1,000-2,000 Satoshis)
In other words, most transactions pay only around 10% of the cost of their routing. This greater than Uber level of subsidy could make business sense only in the context of investing in a future monopoly capable of massively raising prices. But prices are capped by transaction fees on the Bitcoin blockchain, making it impossible.

Even with this level of subsidy, the network doesn't work well. Béres et al estimate that the network attempts about 7,000 transactions per day. They simulated lower and higher transaction rates and summarize the rates of failed transactions in Figure 22. Note that at 7,000 transactions per day one-third of them fail. This is not a practical payment system.


Why do so many transactions fail? Presumably, the reason is that their selected route was incapable of transmitting them. Ideally, the network would dynamically re-route them along paths that were capable. But dynamic routing, such as IP's, in networks such as Lightning is an exceptionally difficult computational problem. Because as each transaction passes through a channel it changes the ability of the channel to accept subsequent transactions, it is a version of the Canadian Traveller Problem. Finding the best path is PSPACE-complete.

So the Lightning Network punts on the routing problem. As Béres et al write:
LN applies source routing, meaning that it is always the sender who decides the payment route towards the intended recipient. Packets are onion routed, which means that intermediary nodes only know the identity of their immediate predecessor and successor in the route. Therefore, from a privacy perspective, nodes are incentivized to avoid single-intermediary paths, as in those cases intermediaries are potentially able to identify both the sender and the receiver.
Because the sender has imperfect information as to the state of the network, and even more so as to the state each of their selected hops will be in when the transaction arrives there, their incentives are inimical to privacy. As Béres et al note:
By our discussion, high node degrees and long payment paths are compulsory for privacy. First, payments from low degree nodes are vulnerable,as the immediate predecessor or successor set is too small and can allow privacy attacks for example by investigating possible channel balances. Second, the majority of payments should be long, otherwise an intermediary has strong statistical evidence for the source or the destination of a large number its routed payments.
Even in theory, the combination of source and onion routing provides a fairly weak version of privacy, similar to that provided by coin mixing:
Although the intermediary knows the sender and receiver if it knows that the payment is single-hop, the onion routing technique used in LN provides a weaker notion privacy called plausible deniability. By onion routing, an intermediary has no information on its position in the path and the sender node can claim that the payment was routed from one of its neighbors.

We remark that plausible deniability is also achieved for on-chain transactions by coin mixing techniques. In wallets supporting coin-mixing one can regularly observe privacy-enhanced transactions with large anonymity sets, where the identity of a sender is hidden by mixing with as many as 100 other transaction senders. Hence for LN to provide privacy guarantees stronger than on-chain transactions, offering plausible deniability in itself can be insufficient.
But, both because senders have imperfect information about the state of the network, and because each hop in the route imposes fees, senders in practice choose short routes via the small number of large, well-connected router nodes such as LNBIG.com. LNBIG.com supplies about half the total liquidity of the network, and owns at least 25 router nodes. As shown in Figure 22 above:
The average shortest path length of LN is around 2.8, meaning that most payment routes involve one or two intermediaries. This phenomenon is further exacerbated by the client software, which prefers choosing shortest paths, resulting in a considerable fraction of single-hop transactions.
Béres et al observe that:
Simulations reveal that on average 17% of the payments are single-hop payments, ... By increasing the fraction of merchants among receivers, this fraction increases to 37%, meaning that strong statistical evidence can be gathered on the payment source and destination through the router node for more than one third of the LN payments. We note that in practice, the ratio of de-anonymizable transactions might be even larger, since payments with longer routes can also be de-anonymized if all the router nodes correspond to the same company.
As for example with LNBIG.com. This all leads Béres et al to conclude:
the topological properties of LN make a considerable fraction of payments easily de-anonymizable. However, with the present fee structure, paths can be obfuscated by injecting extra hops with low cost to enhance payment privacy.
In other words, in order for Lightning Network to provide privacy, it must be massively over-capitalized. If fees are high enough that running a router node is economically rational, privacy cannot be provided because the additional hops needed would both be too expensive and would increase the already high probability of transaction failure.

[Update 1st March 2020]

Congestion Attacks in Payment Channel Networks by Ayelet Mizrahi and Aviv Zohar (summarized here) describes a devastating potential attack on the Lightning Network:
Our attack is based on the inner workings of the main mechanism that makes payment channel networks possible: Hashed Time- Locked Contracts (HTLC). Essentially, as payments are set up to move along some path in the network, all channels along the path reserve some funds for the transfer that is about to take place. The number of simultaneously reserved and unresolved payments per path is limited. Our attack thus simply opens many small payment requests along extremely long paths and keeps them unresolved for as long as possible. In this way, all channels along the path are unable to relay other transfers.
Their anaysis shows that this is a cheap attack:
The costs of running the attack are extremely low. We evaluate these costs in the Lightning Network where we show that using less than half a bitcoin, the attacker can indefinitely lock up channels holding the majority of the funds currently assigned to all channels.


Jon said...

The "fees" assessed for running the network correspond to only a small fraction of the costs of transactions in our financial system. The Bitcoin promoters used to frequently site the 2.5-3% cost of credit card payments; but a good chunk is returned to consumers in rewards points. The actual "network" fee component of these transactions is miniscule.

This point was so obvious back in 2015 when I first wrote about Bitcoin it is hard to believe those making it aren't either very ignorant or liars.

Ben Horowitz is one example---he seems like an intelligent knowledgeable person, how could he make such ridiculous claims?

dave said...

> Because Bitcoin failed to achieve Satoshi Nakamoto's goal of supporting "small, casual payments"

This is not correct.

It is the BTC fork of bitcoin which failed to realise this vision.

Those who didn't follow the BTC branch of bitcoin (ie. those who kept the original bitcoin protocol) are doing this just fine, and "small, casual payments" are just the smallest tip of the iceberg.

The markets and people at large, are confused about this .... as the BTC fork of bitcoin did two things. It took the entire user base, and it took the "bitcoin name". This was done through corruption and misinformation .... but as the blockchain isn't a simple topic, most "people who cared", didn't get it, and fell for the "FUD".

Like the internet.... the masses will not care (or understand) the underlying technology. They'll just care about the products and services built on top of it.

Leondavibe said...

The rewards schemes pay consumers

But merchants pays the fees not consumers

So to a merchant the fee stays the same

David. said...

Ben Munster sums up the year in cryptocurrencies in a 4-part series called Crypto's 101 stupidest moments of 2019.

David. said...

Jonathon Ganor reports on a test of the Lightning Network community's cooperation:

"The Lightning Network torch is in essence a proof-of-concept of the Lightning Network's capabilities. At launch the torch started with 100,000 satoshis and every participant who receives the torch adds an additional 10,000 satoshis. The goal is essentially to pass the torch to as many participants in as many countries as possible until it "breaks", as Hodlonaut said. The first torch was eventually valued at $217 USD and was donated to Bitcoin Venezuela, a non-profit organization.
The first torch reached 56 countries and was passed 293 times over the course of 83 days. The second torch has reached 51 countries, was passed 148 times and is on its 9th day of activity. There is one problem however, the second torch was stolen by participants over 5 times.

David. said...

Lightning Network: a second path towards centralisation of the Bitcoin economy by Jian-Hong Lin et al measures how centralized the Lightning Network is:

"the average Gini coefficient of the node strengths (computed across the entire history of the Bitcoin Lightning Network) is, in fact, 0.88 causing the 10% (50%) of the nodes to hold the 80% (99%) of the bitcoins at stake in the BLN (on average, across the entire period) ... removing hubs leads to the collapse of the network into many components, an evidence suggesting that this network may be a target for the so-called split attacks."

Told you so in 2018 and last month.

David. said...

On the Great Wall of Numbers Tim Swanson asks 40 cointroversies to look into over the summer. Many are interesting but part of #14 caught my eye:

"When will LN hubs need to become compliant with the Travel Rule?"

The link is to FinCen's explanation of the Travel Rule:

"1. Are all transmittals of funds subject to this rule?

No. Only transmittals of funds equal to or greater than $3,000 (or its foreign equivalent) are subject to this rule, regardless of whether or not currency is involved. In addition, transmittals of funds governed by the Electronic Funds Transfer Act (Reg E) or made through ATM or point-of-sale systems are not subject to this rule.

2. What are the "Travel" rule's requirements?

All transmittor's financial institutions must include and send the following in the transmittal order:

The name of the transmittor, The account number of the transmittor, if used,The address of the transmittor,The identity of the transmittor's financial institution,The amount of the transmittal order,The execution date of the transmittal order, and The identity of the recipient's financial institution;

and, if received:

The name of the recipient,The address of the recipient,The account number of the recipient, and Any other specific identifier of the recipient."


"An intermediary financial institution must pass on all of the above listed information, as specified in the travel rule, it receives from a transmittor's financial institution or the preceding intermediary financial institution ..., but has no general duty to retrieve information not provided by the transmittor's financial institution or the preceding intermediary financial institution."

So the rule appears to apply only to the first node in a Lightning route. But the centralized nature of the Lightning Network means this applies to most transactions over $3K.

David. said...

Joost Jager has a Twitter thread pointing out that it is trivially easy to mount a denial-of-service attack on the Lightning network:

"The underlying issue is that a channel cannot hold more than 483 htlcs at a time, regardless of the channel capacity. Sending 483 micro-payments to yourself and holding on to the htlcs is enough to incapacitate a channel for up to two weeks.

By utilizing the max route length to add loops, each payment can consume up to 9 htlc slots on the target channel. If the script kid is lucky, they only need to send 54 payments to get it done. A single tiny channel takes double-digit amounts of #bitcoin out of business."

htlcs are Hashed Time Locked Contracts.

David. said...

David Gerard writes:

"Crypto guy loses a bet, and tries to pay the bet using the Lightning Network. Hilarity ensues."

You really have to read the archived Twitter thread to understand how not-ready-for-prime-time the Lightning network still is (and will remain).

David. said...

Back in 2018 Brazilian computer scientist Jorge Stolfi's Reddit post pretty much summed up the Lightning Network. Things haven't improved since.