Probability for geeks


The Lightning network is being touted as the solution to Bitcoin's scaling problems. If lots of transactions can be taken off the main chain, the thinking goes, then Bitcoin can still take over the world despite its considerable performance problems. Lightning enthusiasts say that when fully enacted, the network will be able to process millions of transactions at, er, lightning speed, without compromising decentralisation, security or transparency.

But there are dissenting voices. For example, in this piece, Jonald Fyookball disputes the claims of the Lightning enthusiasts on the grounds that the mathematics doesn't stack up. Predictably, the Lightning geeks have fought back: the pseudonymous "Murch", a software engineer at the Bitgo cryptocurrency exchange, describes Fyookball's analysis as "laughable".

Fyookball describes the Lightning network thus:
To send or receive bitcoins, you need either a payment channel with that specific user, or a linked series of payment channels (a “route”).

It’s pointless to create a payment channel for the sole purpose of sending an off-chain transaction, since it requires an on-chain transaction to open the channel (and another one to close). You might as well just send an on-chain transaction instead; you don’t need the LN. 
The idea is that you’re supposed to be able to route your payment to any destination through a series of connections. From the viewpoint of a user, the potential path to anyone else looks like a tree structure:

Murch jumps on this, saying it isn't really true:
When a LN participant searches for a route, they're obviously only interested in directed payment capacity. This aspect is correctly represented in the tree. However, the nodes along the route are interconnected. While this could even allow cycles to occur, cycles are not possible in the route construction, as it would allow participants involved multiple times to cut out the cycle when learning the secret for the first time. The resulting graph is what we call a DAG or directed acyclic graph:

So, who is correct? Is Lightning a tree structure, or something more complex?

To explain, let's look at how Lightning decision-making works. We need a whole cast of actors, not just the famous Alice and Bob. Lightning is supposed to be used for small transactions, so let's imagine that Alice wants to buy a coffee in Starbucks. She doesn't have an open Lightning channel with Starbucks (we could call it an "account"), so she asks her friend Carol to pay Starbucks for her, and she will reimburse Carol when the payment is made. Carol doesn't have an open channel either, so she asks Bob to pay Starbucks. Bob has an open channel with Starbucks, so he makes the payment and is reimbursed by Carol, who can then claim her payment from Alice. This looks like a tree structure, doesn't it?

No. Each of the actors has more than one relationship. Alice could have asked Tim or Jim to make the payment for her. Why did she choose Carol? Well, there might be all number of reasons. Perhaps she wrongly thought Carol had an open Starbucks channel. Perhaps Tim was away on holiday and she wasn't able to contact him. Perhaps Alice simply issued a broadcast message to all her friends and Carol was the first to answer. Perhaps Carol was simply the first person to come into Alice's mind. There are all manner of reasons why people might choose a particular participant.

Carol, too, has more than one relationship. Why did she choose Bob? We don't know. And importantly, Alice doesn't know. When Alice asks Carol to pay Starbucks, she does not know what payment route Carol will choose. Carol doesn't have to send that payment directly. Indeed, if she doesn't have an open Starbucks channel, she can't. So she sends it via Bob. But she could have chosen Tim or Jim instead. Yes, the same Tim and Jim that Alice also knows. And if Bob knows them too, then he could route the payment via Tim or Jim instead of paying Starbucks directly. The structure is therefore not just a simple tree structure.

But more importantly, none of the participants knows the route in advance. Each participant has a number of choices, and no participant knows what choices the other participants will make. The final route is therefore not determined until Starbucks gets its money and the payment cascade back to Alice starts. And because no-one knows what anyone else will do, the final route is randomly determined.

Murch disputes this, so let me explain. If we assume that all participants are equal (which is necessary for full decentralisation), then the more potential participants there are, the greater the number of potential routes, and the lower the probability that a given route will be the final one. When there are only a very small number of potential participants, then the probabilities can be calculated. But when the network expands to thousands or millions, as Lightning enthusiasts intend, then the number of potential routes rises exponentially, and the probability of any one route being selected approaches zero. Obviously, one route will be selected: but the selection is effectively random.

Murch's argument is that everyone will know their friends, so the choice of route would not be random. I'm afraid this is our old friend the fallacy of composition, otherwise known as "generalising from the particular". I know my friends, and I may know some of their friends: but I don't know their friends' friends, let alone their friends' friends' friends. Once we are more than about one or two steps removed from the originator's circle of friends, the originator simply does not know enough about the network to be able to predict what direction the payment route will take. Nor does any other participant. The more potential participants there are, and the more choices each participant has, the less knowledge anyone will have about what is really going on.

Payment routes could become very long and very complex without anyone knowing. They could even become recursive. It is entirely possible that the same person could be asked to make a payment more than once in the same chain, by two different participants. Murch says this isn't possible, but unless there is some kind of Fat Controller preventing duplicate participation in payment chains, he is wrong. Anyone can choose their participants, and people only see their own backyards, so it is absolutely possible for a payment to be sent twice to the same participant, and no-one would know.

But why might a simple payment to Starbucks become so complex? Well, this brings me to the second area of dispute between Fyookball and Murch. Fyookball describes Lightning payments as "lending". Murch says they are nothing of the kind: they are simply a balance trade. Who is right?

This time, Fyookball is right. Lightning is a "pull" system. Every participant makes a payment, then "pulls" reimbursement from the previous participant. So each participant has to have sufficient "own funds" in their channel to make the payment. If they don't, they can't participate in the route, and their predecessor must find a different participant. Using "own funds" to make a payment on behalf of someone else meets the normal definition of "lending". It may be settled within milliseconds (or not, as we shall see), but that doesn't change what it is.

Note also that no-one gets paid until Starbucks does. Carol cannot claim her payment from Alice until Bob claims his payment from her, and Bob cannot claim his payment from Carol until Starbucks claims its payment from him. The final payment in the route triggers a cascade of claims. When there are a lot of hops in the route, therefore, reimbursement for early participants could be significantly delayed.

Reimbursement delays could seriously degrade network performance. When a participant commits to a payment, the "own funds" in the channel must be available for that payment. But any funds already committed to another payment that hasn't yet settled are not available. We can think of this as like selling your house: if you've already exchanged contracts with someone, but the sale hasn't completed because there is a blockage further up the chain, you can't sell your house to someone else. If there are insufficient unencumbered funds in the channel, the participant can't commit to the payment, and the channel becomes "unresponsive". When network traffic is heavy, then if all participants are small users with limited funds, it is possible that all potential payment routes available to a particular participant could become unresponsive, resulting in payments failing to complete. That is gridlock.

And if you think this couldn't happen, you need to play The London Game. In this, players ride London's Tube system to reach various randomly-determined tourist destinations. You start at a major London train station, and you use the Tube map to work out how to get to your destination. Note that this is already significantly less difficult than the Lightning system, because at least you can see the whole map and work out a viable route. In Lightning, you can't see more than a couple of Tube stops beyond your start point.

But your route choices are immediately compromised by two things; the decisions of other players regarding which Tube stops should be closed (become unresponsive, in Lightning parlance), and the Hazard cards that mean you can be randomly diverted somewhere else (this approximates to losing control of your route, as you do in Lightning). Let's suppose you are trying to get from Victoria to Tower Hill, and someone decides to close Embankment. I've put a London Tube map at the head of this post so you can amuse yourself working out what effect that has on what was quite a short, simple route. Or let's suppose you were trying to get from Liverpool Street to Regent's Park, but you get diverted by a Hazard card and end up at Temple, again with Embankment closed. It's not difficult to see that available routes quickly become long, complex and congested - and this is with only one closed Tube stop. As more Tube stops are closed, it is actually possible for some participants to be completely unable to move: for example, if you are at St. James's Park and someone closes both Victoria and Westminster, you aren't going anywhere.

Gridlock is, of course, the fun of The London Game. But when it occurs in a payments system (or on the Tube in reality, of course) it is anything but fun.

Now, of course the London Tube is not a fully decentralised system. All tube stops are not equal. Taking out Oxford Circus has a far more disruptive effect on network traffic than taking out Swiss Cottage. Lightning at least attempts to level the playing field, but it does so at the price of inevitable gridlock. The combination of low funds levels in payment channels with payment delays due to long chains is deadly.

And Lightning has a second problem, too. Because players of The London Game can see the whole map, they spend much of their time working out alternative routes. But Lightning users can't see the whole map. All they can do is try different payment channels. Their situation is rather similar to a Tube user, knowing that Westminster is blocked, deciding to go via Oxford Circus instead, only to discover at Green Park that Oxford Circus is blocked too. The fact that no-one knows either the past or the future of a payment route creates the real possibility that some payments may never reach their destination at all, but wander the network forever like the Flying Dutchman.

Suppose that Alice's payment fails to settle. It hops from participant to participant, but no-one ever sends it to Starbucks. How does this look to the participants? Well, Carol, Bob, Tim, Jim, Old Uncle Tom Cobbleigh and all lose money, because they make payments for which they are never reimbursed. None of them know why the payment fails to settle, because all they can see is their own back yard. They don't realise that the problem is that no-one has a channel with Starbucks, or if they have one, they either can't or don't want to use it. So they mutter about funds being "stolen". And Alice may face a lawsuit from Starbucks for failing to pay for her coffee.

Because this is a network, there is absolutely nothing any of them can do to stop the payment wandering, except by opening a channel with Starbucks - and why would they do that for a one-off payment? Individually, their decisions not to send the payment to Starbucks are no doubt entirely rational. But collectively, their behaviour results in a payment failure. This is what Fyookball means when he refers to the possibility that there may not be a path at all.

But is Fyookball's solution any better? Well, having dedicated payment channels with much larger reserves that remained online all the time would ease Lightning's liquidity problem, and if liquidity was more abundant there might be less likelihood that payments would seize up or "wander". People would simply send their payment to a liquidity hub, which would maintain a permanently open channel with Starbucks. But this could hardly be called "decentralised". The liquidity hub would inevitably be a target for thieves and hackers. And if it went down, the network could have a heart attack, just as closing Oxford Circus brings the entire London Tube network to a halt (believe me, it does).

Of course, Lightning is a financial system, not a transport network. So perhaps we should call such a centralised payment channel by a different name. "Lehman Brothers", for example. How does that sound?

Related reading:

Thunder and lightning in the Bitcoin world - Forbes
Pilate's Game
Calculus for journalists
Tweet thread on Lightning 

Comments

  1. Please contact me via email: edo.fazlinovic@gmail.com
    About #XRB aka Raiblocks

    For a story you can ping @zackshapiro on twitter.
    He is core dev of #XRB @raiblocks and verified twitter user and have real life profile avatar, not like me tho. :)

    ReplyDelete
  2. Ha! Lehman Brothers, that's a good and funny one! What we need to be very careful about is that we don't leave ourselves open to the final integration and coalescence of the dominating paradigm of Debt Only into the system which is what I believe is the real covert agenda behind bitcoin and crypto-currencies instead of better and more efficient monetary administration and distribution.

    wisdomicsblog.com

    Systems were made for Man, not Man for Systems.

    ReplyDelete

  3. Dear Frances,
    Regarding you challenging post, two points.
    How does your lightening system differ from the original concept of the internet? Back in the eighties, with the "gopher", I was told that the system was explicitly designed (by the US military) as a bomb-proof system. A message message was sent out simultaneously on all available channels. When it found an open 'node' it was received, and a reply sent to stop further sends. If the node was the addressee the package was read. If not the addressee, it was retransmitted, again on all available routes, till a destination was found. If the message was too big for a 'packet', it was sent as multiple packets, which had to be stitched together at the destination, but not before. I suppose I was correctly informed.(?)
    We do not get emails twice, and the do arrive quite fast, so the present system does seem to work. But if that is not fast enough for the bitcoin people, then a refinement may be needed. I can imagine something like a brain (or what I suppose a brain to be like), so that pathways that are used ofter get faster and faster (get 'favoured status').

    My second point is that I thought bitcoin was only for gamblers. Or buying black diamonds, or guns. Wrong?
    --
    Ian West, 9 Thenford road, Middleton Cheney, Banbury, OX17 2NB

    ReplyDelete
    Replies
    1. On the internet a packet are sent once (unless it fails) down a single path selected out of multiple paths by routers and routing tabels. If one route fails it will be sent down another route.

      If all packets were sent everywhere the whole edifice would collapse in a second.

      The transaction costs for Bitcoin render it too expensive for small payments like a coffee, even if you buy at Starbucks. And unless you are prepared to pay a higher rate to have your transaction prioritised it could be sitting in the mempool for hours or even days until the miners decided to process it.

      Without a utility value, and to call Bitcoin a store of value is laughable, yep, Bitcoin is a bet for all the wannabee rich quick.

      Delete
  4. This LN solution seems bonkers unless Starbucks is at Mornington Crescent. :-)

    ReplyDelete
  5. I'm no big fan of Lightning, seems over complicated compared to just having big blocks, but the alleged problems don't seem real.

    What is a channel? It's basically like a correspondent banking relationship, with a security. The details differ but we could reduce it to a 1-of-2 multisig address for simplicity: to open a channel Alice and Bob each send say 1 BTC each to that address (on-chain). 1-of-2 means that either of them can spend the 2 BTC. If one of them thinks the other party has defaulted, they can pay themselves the security, thereby destroying the channel (the other party monitors that the security remains unspent on chain).

    The routing problems (how to find the end point, how to avoid infinite loops, etc) are the same as internet routing, which is a more or less a solved problem (I'm told IP routing is not mathematically sound, but it works okay).

    How does a payment work for an intermediary? When you receive a payment request, if any of your correspondents knows a route to the end recipient you send it there, if not, you reply "not for me". In the former case, you forward the reply from your correspondent, either a "not for me" (or equivalently a time out) or the proof of payment (something signed by starbucks). If you see the proof of payment you credit your internal balance for your correspondent (and you have a credit upstream). If the balance with a correspondent gets close to a channel security (up or down) you settle it: if it's in your favour you pay the correspondent on-chain to take it back to 0, if it's owed to you, you check on-chain your correspondent has settled. It's where a channel can fail: if the channel is "full" (pending balance close to security) and you don't pay, the other side will claim the security and break the channel. It can also fail if the other side steals the security, which is why you need some trust to exist before establishing a channel. There's an incentive not to break the channel because you lose reputation and a perpetual stream of future lightning micro-fees.

    Liquidity is not really an issue because the problem we're trying to solve is payments where the on-chain fee is above a certain pain threshold, and the channels need not be much bigger than the minimum on-chain payment above the pain threshold (which defines how often you settle).

    Where there's a difficulty is when we want decentralisation: trust is probably a natural oligopoly in that you'll probably end up with everyone having channels to bitpay, so that most payments go punter->bitpay->vendor, or through a handful or bitpay-style operators.

    ReplyDelete
    Replies
    1. I do think liquidity is an issue, for the reasons that I gave. Pre-funding does not solve liquidity problems. Indeed it creates them. Fractional reserve banking exists because liquidity is too restricted in a full reserve system.

      But I agree the real problem is decentralisation. There is no way a fully decentralised network can possibly work - or even exist for long. Fyookball's point was essentially that the system would naturally tend to oligopoly, with payments routed via large, liquidity-rich hubs. My point is that this effectively recreates the existing system, with its weaknesses. Pre-funding does not solve this problem.

      I don't think it is possible to have total pre-funding (full reserve), full decentralisation and abundant liquidity.

      Delete
    2. For a full-reserve payment system you just need liquidity = payment volume within 1 settlement cycle, allowing a capacity slack multiple (so that you don't run at 100% on average).

      The faster the settlement cycle, the less liquidity is needed. Legacy banking was 1 day or more, probably getting better now. In crypto currency we're talking minutes, worst case say 1h for Bitcoin, and that's not written in stone. Legacy electronic banking (no blockchain needed) can technically probably go down to a few minutes easily.

      Take worldwide petty transactions volume for your settlement time, times capacity slack, times your market share, that's the liquidity requirement for your payment system. It's all spare change at the scale of the financial system.

      Fractional reserve and abundant liquidity is needed for a long term credit system with maturity transformation (whether that's at all useful is another debate) but certainly not for funding the flow of a few minutes' worth of coffee payments.

      Delete
    3. As legacy electronic banking is double entry, transactions across the central bank settle instantaneously due to simultaneous posting. So do transfers within the same bank.

      I don't really buy the argument that liquidity problems only arise in a long-term credit system. Lightning payment routes depend wholly on people being willing to allow their funds to be used to settle payments about which they know nothing. If the system allowed people to refuse, liquidity would dry up. Lightning devs seem to think they can solve this problem by denying people the right to refuse to settle other people's payments. But even with coercion, it is possible that for some payments there could simply be no route, if people kept payment channel funds at the bare minimum. I'd call that a liquidity problem, personally.

      Delete
    4. Correct. Liquidity problems are only a sign that the true problem, individual income, is much lower than it normally is, and individual income is pitifully and chronically scarce even under "good" economic times. The velocity of money is really just that, an indication of commercial liquidity. People and astonishingly even economists think its additional individual income because the classical story of it that depicts the hotelier taking $20 to the baker who takes the same $20 to the butcher, candlestick maker etc. However the description is fallacious because whatever money circulates back into the economy is BUSINESS REVENUE NOT INDIVIDUAL INCOME and business revenue must be expensed against all business costs until a relatively small percentage of it is finally distributed as individual income....and that not only is woefully inadequate it does not go up significantly even if "good" times are on. What? Does the entrepreneur immediately give everyone a raise just because his/her revenue went up 10%. Think again. The whole crypto thing is another rabbit hole distraction from the real problem which is the chronic and increasing scarcity of INDIVIDUAL INCOME.

      Delete
  6. It seems too much for a system to expect one to waste time having to coerce one's friends into supporting a simple transaction such as buying a cup of coffee. Also what is the legal status if one becomes implicated in money laundering or other such crimes by 'innocently' helping out in the transaction chain?

    ReplyDelete
    Replies
    1. The amount of credit risk in this system is massive. Trust-free, it isn't. I'm amazed people can't see that.

      Oh, and it turns out that they are now planning to introduce a Fat Controller. Identify and test payment paths up front, then automatically route payments via intermediate channels without the consent of the owners of the funds in those channels. This is a legal minefield, but they seem to think they can set up a nice smart contract that will make it impossible for people to object to their funds being used for payments about which they know nothing. Money launderers' paradise.

      Delete
    2. Its amazing how the Bitcoin system consistently creates and generally throws up far more problems than it was ever intended to solve.

      All it originally was created for was as a system of micro-payments that eliminated the role of trusted 3rd parties to mediate disputes in order to supposedly reduce transaction fees.

      But it turned out that all the trusted 3rd parties entities and systems within the ecosystem of e-commerce (Amazon, Ebay, PayPal, customer product review systems etc) are absolutely vital to e-commerce functioning at all as they effectively help produce the trust within the system which allows it to operate in the first place without our having to endlessly research every individual on-line seller before making a purchase and for them to trust their customers in turn.

      I've been a heavy user of e-commerce since the mid 1990s and never had any problems using 3rd parties which I trust. I don't think banks or Visa themselves have ever really acted as mediators within such systems and I would suggest that Visa's costs largely come from running state of the art data centres with built in earthquake and hurricane protection, huge back up electricity supplies and complex anti-fraud and theft systems alert to actively protecting customer's funds from illegal or unusual transactions. For the few cents Visa charges for a transaction this seems a reasonable deal but I wouldn't complain if regulators found that banks were charging a premium on such services and forced them to make them cheaper.

      It makes one wonder if Nakomota ever used e-commerce at all when he dreamed up this insane problem creating 'solution'. Bitcoin was never fit for purpose from the word go and no programmer with any experience of true enterprise scale computing where transactions run into the trillions would ever have committed themselves or their organizations to such an inappropriate open, distributed physical and logical architecture. For disruptive and distributed, just say disorganized and generally irresponsible as no-one with the Bitcoin ecosystem even has the slightest clue as to how much power this monster is consuming. Bitcoin simply cannot scale to the kinds of global disruptive usage that have been claimed for BTC. I'm not even sure that global, finance and disruption are three words that you really want to see in the same sentence.

      Delete
  7. This comment has been removed by the author.

    ReplyDelete

  8. I think your description of the routing mechanism is wrong. The network you describe would be considerably more sophisticated than the actual implementation.

    Currently there are two aspects to it - route discovery, and then the route definition. Route discovery is easy - there isn't any!

    Currently each node is required to hold a "map" of the entire network topology, this is built by every node on the network broadcasting its availability through the network - each node then also broadcasts its available channels and shares it public keys.

    With the network map available then the route itself can be predetermined by the originating node - either automagically, or manually - it'd be up to the software implementation.

    Once the route has been created by the original node it then wraps up the required data in an "onion" packet - with a layer for each node on the route. Each layer is encrypted (hence the sharing of public keys) so it can only be read by the relevant hop on the route. The unencrypyted data contains the information about the transaction and the address of the next hop - as the "onion" is unpeeled it makes its way through the network until it reaches the final node.

    This means that many of the issues you've describe here simply won't, or can't happen - issues like recursion can be ruled out as the route is predetermined. Basically, Murch is correct, but its due to a lack of sophistication, not a clever solution. The issues you describe are real, and haven't been solved.

    The big issue here is that this isn't at all scalable, holding a map and manually building a route from a few hundred nodes might be simple enough, but at the level of use they aspire to its simply not practical. I believe the aspiration is to implement automatic routing using something along the lines of BGP (Border Gateway Protocol), which is the protocol used to build routing information on the internet, but it seems a fair way off.

    If you know your network protocols then LN at the moment is basically NetBUEI, and they need TCP/IP.

    ReplyDelete

Post a Comment

Popular posts from this blog

The sad story of Maplin Electronics

The Bitcoin Standard - a critical review

When governments become banks