splicing – Data Science, Data Analytics and Machine Learning Consulting in Koblenz Germany https://www.rene-pickhardt.de Extract knowledge from your data and be ahead of your competition Tue, 17 Jul 2018 12:12:43 +0000 en-US hourly 1 https://wordpress.org/?v=4.9.6 Thoughts about eltoo: Another protocol for payment channel management in the lightning network https://www.rene-pickhardt.de/thoughts-about-eltoo-another-protocol-for-payment-channel-management-in-the-lightning-network/ https://www.rene-pickhardt.de/thoughts-about-eltoo-another-protocol-for-payment-channel-management-in-the-lightning-network/#comments Sun, 08 Jul 2018 21:56:08 +0000 http://www.rene-pickhardt.de/?p=2116 In this article I will give an overview about the proposed lightning network extension eltoo. There has been quite some buzz about the eltoo paper proposed by Christian Decker, Rusty Russell and Olaoluwa Osuntokun in May 2018. Bitcoin magazines and blogs have been making promising statements, that lightning will become even faster than it currently is. According to them eltoo allows for payment channels to interact less with bitcoins blockchain (which I will state already is just plain wrong.)

Having read Christian Deckers main publication for his dissertation in which the authors suggest the use of invalidation trees to invalidate old states of an payment channel I was confident that eltoo would be a really nice improvement for the lightning network protocol. However following the “Don’t trust. Verify!” philosophy of the Bitcoin community I obviously had to study the eltoo protocol proposal myself. In particular I did not believe those bullish news from the magazines since from a technical perspective I do not see how the speed of the lightning network can significantly be increased. The speed of the lightning network at its current state is basically bound by the speed of TCP/IP sockets at the payment channel level and during routing by the time locks of the HTLCs. Since eltoo is only looking at channel management we can obviously omit the later case. As I am starting to work on the splicing part of the BOLT 1.1 specification which is a protocol extension of payment channel management obviously I need to understand eltoo anyway.

Yesterday after holding an openly licensed German language lecture on the basics of the lightning network technology  (not to be confused with BOLT the Lightning network RFC) I had a 5 hour train ride home from the event and finally found the time to carefully study the eltoo paper. Even though the paper is very well structured and written and I thought it might be helpful if I share my understanding of the proposed protocol back with the community. However my main reason is that I hope by writing down and explaining the paper I get an even clearer understanding myself. In case I misunderstood something about the eltoo paper please let me know so that I can update this article. Also there are some rather technical questions I still have (for example this one which I have already posted on bitcoin stack exchange)

So let us analyze eltoo by understanding the motivation for yet another payment channel protocol by reviewing some of the well known facts about the current payment channel management.

Unpublished commitment Transactions encode the balance (or more technically spoken state) of a payment channel in the lightning network.

For the current version of the lightning network payment channel protocol we need to store information about all the old states of a channel. With state of a channel we mean the current distribution of the channels capacity (aka the balance) among the channel partners. At the core the current payment channel (and also the solution proposed in eltoo) a payment channel is just a 2-2 multi signature wallet. Currently the balance of a payment channel is encoded by two unpublished transactions that would spend the channels capacity according to the balance sheet with the channel partners as receipients. Actually we call those transactions commitment transactions. These transactions are both signed by both channel partners and each of them has one of them stored on his lightning node. This creates some kind of information asymmetry and a risk of funds being stolen should the information leak to the channel partner.

Funds within the channel are being maintained by creating a new commitment transaction (kind of a double spend) that spends the funds of the multi signature wallet (the channels capacity) in a different way. In order for both parties to be able to trust in the newly agreed upon channel balance we obviously have the problem of invalidating the old commitment transactions. In a trustless setting (which we wish to achieve) channel partners cannot rely on their counterparts to delete the old commitment transaction once they agree on a new channel balance. The reason is that those commitment transaction are valid bitcoin transactions signed by both channel partners and both partners own a copy and could have theoretically made more copies in between time.

All currently known protocols for maintaining a full duplex payment channel have in common that old channel states need to be invalidated. 

The current implementation of the lightning network achieves the goal of invalidating old channel states by including the hash of a revocation key within the output script of a commitment transaction. The revocation key itself can only be known by the channel partner that does not control a signed copy of that transaction. (Again this is where the information asymmetry kicks in) The output script of the commitment transaction will eventually spend the funds according to the channel balance that was agreed upon for this particular commitment transaction. However it allows to spend the output of a published commitment transaction directly to send the entire capacity of the channel to ones own bitcoin address once one can present the signature from the secrete revocation key. If channel partners wish to update to a new channel state they will collaboratively compute the revocation resulting in the hash that is stored in the most current commitment transaction. The important requirement of the protocol design is that neither partner can compute the revocation key without the help of the other partner. Owning the revocation key prevents the channel partner to publish an old commitment transaction (aka state) since the publishing side would be punished by the other side releasing the revocation key and spending the outputs of the commitment transaction directly. Note that releasing the revocation key itself is not dangerous since it can only be useful in the output script of the transaction which includes the hash of the revocation key. As you would imagine each new state / commitment transaction includes the hash of a new revocation key. Therefor it is really the old transaction that needs to be kept secrete or even better destroyed. Obviously with such a setup both sides need to store all old revocation keys in order to be able to protect oneself from the other side publishing an old channel state (which for example could be a state in which all the funds belonged to the side that tries to publish this state)

Eltoo suggest a different protocol for channel management such that either side does not need to store all old state but just the current state. This is supposed to simplify implementing lightning nodes and also running them. According to Christian Decker this will also simplify implementing features like splicing. (On a side note I have not thought the splicing operation completely through for eltoo but it seems obvious to me that the chain of update transactions in eltoo can easily be extended by at least splice out operations.)

The initial setup of a payment channel within the Eltoo protocol is in my opinion exactly the same as in the current specification of the lightning network.
A payment channel is created by funding a 2-2 multi signature wallet. The state of the channel is again encoded within a transaction that is just not published yet. Only the process of invalidating old state differs. Both channel parties create two sets of public and private keys. The first set is called the update keys and the second set is called the settlement keys. Actually the settlement keys should be derived from a deterministic hierarchical wallet so that settlement transactions can only be bound to one specific update transaction (but I guess that is a rather subtle though important detail). According to Christian Decker what is new is that

… commitment is no longer a single transaction customized for each side, but an update/commitment that is symmetric and a settlement built on top.

A chain of update and settlement transactions allows for encoding channel state.

The state of the channel is encoded as the most recent element of a sequence of settlement transactions in which the current settlement transaction is encoding the current channel state. All the old settlement transactions are not needed and can safely be thrown away. Though not being the same as commitment transactions in the current lightning network implementations the settlement transactions can probably be considered to be the analogous counterpart. Each settlement transaction spends an – so called – update transaction.  The update transactions are formed as a “linked list” starting from the funding transaction (which could already be interpreted as an update transaction). The update transactions spend the output of the funding transaction (or the previous update transaction(s!) ). The output of the new update transaction is a two path multisignature script where in the first path the output can be directly spent with the pair of update keys. In the second path the output can be spent with the settlement keys as long as a timelock is achieved. This will always give priority to successfully double spend an old settlement transaction with a newer update transaction. In case the newest settlement transaction is being broadcast there exist no newer update transaction which is why the double spend of another update transaction cannot be achieved by a single entity in the channel. Therefor after the timelock is over the channel is closed.

This setup is bad however since the current channel balance encoded in an settlement transaction which is the child of the latest update transaction which is the child of the previous update transaction and so on. Therefor in order to close the channel one would need to broadcast the complete chain of update transactions. This would be bad as it would not take any load from the blockchain in comparison to directly transfer bitcoins every time one wold want to update a payment channel and we would also need to store all old update transactions not really decreasing the overhead. However with the current version of the bitcoin protcol there is nothing we can do about this and eltoo is nothing but a nice thought and completely impractical. However a minor update to bitcoin (which was actually already talked about in the current lightning network paper) is finally proposed as BIP 118 and would also make eltoo useful.

Eltoo achieves the simplification by introducing the idea of floating transactions which are realized by introducing a modifier SIGHASH_NOINPUT for the existing OP_CODES check{,multi}sig{,verify}

With SIGHASH_NOINPUT the transaction that is being created to spend some output will ignore the prevout_point (tx hash, output  index), sequences, and scriptCode for its signature calculation. This allows to change the output that is being spent as long as the output script matches the input script. Since the output scripts of the updating transactions are all the same (at least for the path that spends to output again to the update keys of the 2-2 multisig wallet) one can bind a later update transaction to the parents or grandparents or great grandparents or … of the most recent output transaction. (I don’t see the point of summarizing all the technical details here since they are very well described in the paper and I don’t see how I would formulate them differently or shorter) What this does however is that instead of the need to publish all previous funding transactions the current one can just be bound to the funding transaction and can be broadcasted together with its settlement transaction. Since there is a timelock in the update transaction (it could be an invalid one) the settlementtransaction should obviously only be broadcasted after the timeout since it will be rejected by the bitcoin network beforehand.

That being said the current channel state is defined by the already mined funding transaction as well as the most recent update transaction and its child the settlement transaction. In case channel partner Mallory would want to publish and older state (encoded within some settlement transaction) she would first need to publish the update transaction that is parent of this very settlement transaction. She can do so as she can also bind that corresponding update transaction to the funding transaction. However if she now spends the settlement transaction there is the path in the output script of the update transaction that allows for direct spending of a newer update transaction (which can be the newest update transaction -known by the other side – being bound to that particular update transaction). This will prevent old state from entering the blockchain.

There are some minor details about including a trigger transaction which I will omit here. However it seems important to mention that this mechanism also requires for the other side to be online or having a watchtower mechanism being included. Also with this mechanism in the uncollaborative closing case, the collaborative one and the case where one party tries to steal funds the blockchain will need to have at least three transactions being broadcasted to the blockchain (the trigger transaction, the most recent update transaction and the settlement transaction) In that sense I understand eltoo as a tradeoff between convenience for channel management in comparison to minimal blockchain involvement. As I mentioned during the autopilot discussion at the lightning hackday the blockchain will still need about 10 years to have one payment channel open for every internet user in the world. On the other side it seems to have many advantages over the current protocol for payment channel management.

Advantages of eltoo:

  • Biggest pro seems to be that it is easily compatible with the current lightning network. It does not matter of the network uses various protocols for payment channel management.
  • As fraudulent behavior can also exist by accident (e.g. a bug in the implementation) it is nice that with eltoo the punishment of fraudulent behavior is not achieved by giving all bitcoins to the honest side but rather by forcing a channel close and distributing the funds according to the last agreed upon channel balance
  • Way less protocol overhead on the implementation side (only true if we eventually only support eltoo channels and don’t have to support both payment channels)
  • (Although I did not explain the details here) Fees for settling (closing) the channel do not need to be decided for while creating the payment channel but can be chosen a posteriori.
  • Possibility to easily create multi user payment channels (though all parties have to be online in order to update the channel balance which is said because otherwise we could easily create payment caves in wich thousands of participants would share the balance increasing liquidity in the network) also the transaction size increases (but still stays smaller than having several 2 party channels created among the participants). Christian Decker pointed out that with Schnorr Signatures there won’t be a difference in the size of the transactions for 2 party channels or n party channels. I see that the signature part of the transaction won’t grow but if more parties are on the channel more outputs are being created. (Maybe I miss something. I haven’t had the chance to look at Schnorr Signatures in detail.)
  • Since honest nodes can safely forget old channel state we should never run in memory issues while maintaining one channel.

disadvantages of eltoo:

  • It might incentivize people to try behave in a fraudulent way since there is only the risk of loosing fees involved.
  • SIGHASH_NOINPUT needs to be implemented in future bitcoin versions. Though the authors claim the protocol is backward compatible with bitcoin for the lightning network this seems like a typical IT mess. Probably it will take time for bitcoin and lightning network nodes to update. Obviously a routing network can be created with various channel management protcols as long as they support HTLCs and the internal API for routing. However it seems quite cumbersome to implement future features to support both eltoo and the classical lightning payment channels. One strategy could be to just implement splicing on top of eltoo or to implement it with a higher abstraction of channel management (not sure yet if that is possible)

Open Questions:

  • What happens if we have an Integer overflow in the sequence number?

Which Christian Decker answered by stating that in case this really happens one can set back the counter by splicing or reanchoring (splice without changing the values).

If you are more interested in technical write ups about the technology of the lightning network you can follow me on twitter. If you are also an enthusiast of the lightning network you could connect to my lightning node via: 036f464b54416ea583dcfae3872d28516dbe85414ed838513b1c34fb3a4aee4e7a@144.76.235.20:9735 and help to grow the lightning network. Also I want to shout out a thanks to Christian Decker who has reviewed this article and pointed out some mistakes which have been fixed.

]]>
https://www.rene-pickhardt.de/thoughts-about-eltoo-another-protocol-for-payment-channel-management-in-the-lightning-network/feed/ 1
Improve the autopilot of bitcoin’s lightning network (Summary of the bar camp Session at the 2nd lightninghackday in Berlin) https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin/ https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin/#comments Sun, 24 Jun 2018 22:02:55 +0000 http://www.rene-pickhardt.de/?p=2085

I have been visiting Berlin to attend the second lightninghackday and want to give a brief wrap up about the event. This article will basically cover two topics. 1st as promised within my bar camp session on “Building an automated topology for autopilot features of the lightning network nodes” I will give an extensive protocol / summary of the session itself. 2nd I will talk about an already well known technique called splicing which I realized during the event might be one of the more important yet unimplemented features of lightning nodes.

Let me just make a quick shoutout to Jeff and his team from fulmo lightning: Thanks for organizing this excellent event. Especially bringing together such a group of high profile lightning network enthusiasts was astonishing for me. Out of the many tech events and conferences that I have attended in the past this was one of my top experiences.

In my bar camp session we had roughly 30 people attending. Luckily also Conner Fromknecht and Olaoluwa Osuntokun from the San Francisco based lightning labs joined the session and gave many insights resulting from their hands on experience. I started the session with a short presentation of my thoughts about the problem. I had previously formulated those in my github repo as a rough draft / scetch for a whitepaper on the topic. That happened after I opened Issue 677 in the LND Project criticizing the current design choices for the autopilot. The main points of those thoughts are a list of metrics and criteria I previously thought I would want to monitor and optimize in order to find a good network topology. Before the hackday that list looked like that. (We discussed this list and basically people agreed on it):

  • Diameter: A small diameter produces short paths for onion routing. Short paths are preferable because failiure is less likely to happen if less nodes are involved for routing a payment.
  • Channel balance: Channels should be properly funded but also the funds should be balanced to some degree.
  • Connectivity / Redundancy: Removing nodes (in particular strongly connected nodes) should not be a problem for the remaining nodes / connectivity of the network.
  • Uptime: It seems obvious that nodes with a high uptime are better candidates to open a channel to.
  • Blockchain Transactions: Realizing that the Blockchain only supports around 300k Transactions per day the opening, closing and updating of channels should be minimized.
  • Fees for routing: Maybe opening a channel (which is cost intensive) is cheaper overall.
  • Bandwith, Latency,…: nodes can only process a certain amount of routing requests. I assume that also the HTLCs will lock channels for a certain amount of time during onion routing.
  • Internet topology: obviously routing through the network becomes faster if the P2P network has a similar topology as the underlying physical network. Also it makes sense since even on the internet people might most of the time use products and services within their geographic region. check assumptions

Before I state the new ideas that came from the attendees and the discussion I want to briefly sum up the great keynote by the guys from lightning labs that preceded the bar camp session. In particular I think the insights and techniques (Atomic Multi Path routing and Splicing) they talked about have a huge impact on the autopilot and the topology generation problems of the lightning network. Long story short the magic concept in my opinion is splicing. For those that are unfamiliar with the topic: Splicing is the process of updating the channel balance of a payment channel by adding or removing (partial) funds. In the past I always thought that even though it was not implemented in any of the lightning nodes that this is a problem which technically is rather trivial to solve and thus of minor importance. The guys from lightning labs basically stated the same emphasizing that splicing funds out of a channel is trivial and can even be achieved easily in a non blocking way such that the channel can be used again directly after splicing out even if the spent transaction is not yet mined. However splicing in (aka adding more funds to a channel) seems to be a little bit more cumbersome. Without going into too many technical details the real eyeopener for me was the fact that splicing (together with the autopilot) seem to make lightning wallets in the way they exist these days obsolete. This obviously is a game changer. So to make it crystal clear:

With splicing and the autopilot implemented in a standard bitcoin wallet (and running in the background without the need for users to be aware of this) users can efficiently, quickly and cheaply send funds from one to another. If a path via lightning exists the transaction will be lightning fast. If no path can be found one could just splice out some funds from existing channels to create a new channel for the transaction. This would basically boil down to a common on chain transaction which happened before we had the lightning network anyway. However it doesn’t matter if all funds are currently frozen up in payment channels. Also it doesn’t waste the blockchain transaction but rather uses this opportunity to open create a funding transaction for the next channel increasing the size of the lightning network. I dare to say a bigger lightning network is a better lightning network in general. Basically the goal would be that eventually all bitcoin funds would be locked in some payment channels (which with splicing obviously doesn’t lower the control or flexibility of the user) In case a user really needs to do a transaction wich can’t be achieved via lightning it will just be spliced out and takes as much processing time as a regular on chain transaction. As a disclaimer: Obviously watchtowers are still needed in particular in this scenario in which users might not even realize they are using the lightning network.

Taking the opportunities of splicing into consideration I think that the topology problem of the autopilot becomes issue of only minor importance. One can easily splice out from existing payment channels to new payment channels if needed. The only bad thing is that such a transaction is not routed at lightning speed but rather takes a couple block times to be mined and processed. However it eventually creates a user generated network topology that hopefully pretty much follows actual flows of funds and would thus be rather robust. The only drawback with such a process would be that transactions frequently include channel creations which takes some time and that only a maximum of 300k channels can be altered per day on top of the current bitcoin protocol. This observation explains why topology generation of the autopilot still is a reasonable topic to think about since it should still help to move traffic away from the blockchain.

Finally I will now list some new thoughts that have been collected during the session. I will also update my whitepaper soon. Feel free to fork me on github and do a pull request in order to fix mistakes or add your own thoughts.

Number of nodes reachable within x hops:
It was pointed out that his metric would look quite nice. As a result of the discussion we came to realize that this greedy heuristic would basically lead to the scenario in which every node would open a channel to the most central node in the channel. such a central node would increase the number of nodes that can be reached within x hopes by the maximum amount. Still it looks like an important number to somehow optimize for.

Honesty and well behavior of nodes:
Following a similar philosophy we discussed weather a distributed topology creation algorithm should aim for global health of the network in comparison for greedy strategies in which every node tries to optimize their own view of the network. Though it wasn’t pointed out in the session I think that a strategy where every node tries to optimize their own access to the network will at some point yield a Nash equilibrium which. With my rather little understanding of game theory I think this might not necessarily be the best solution from a global perspective. Also we discussed that in the later mentioned sections where clients share information with neighbors an algorithm must be robust against fraudulent behavior or lying of nodes.

Stakeholder models:
Pretty much everyone agreed right away that different nodes might have different needs for the lightning network. so the topology creation should be configurable (or learnable by the node) taking into respect weather the node is just a casual consumer or a shop or a bank / exchange or …

Privacy vs information sharing:
We discussed quite extensively that for a distributed algorithm to make predictions which channels should be created it would be great if channel balances would be public (or at least there would be some rough information available about the distribution of the balance within one channel). We realized that as a first step following the ideas of lnd Issue 1253 nodes should start collecting historic information about their own operations and routing acticities. Actually I just saw that a pull request that claims to have resolved issue 1253 already exists.
We also realized that channel fees might act as a reasonable well proxy for the channel balance. Assume Alice and Bob have a channel and the balance is very skew in the sense that Alice has almost no funds and Bob has all of them. If Bob was asked to route a payment through that channel he would probably charge a smaller fee than Alice if she was asked to route a payment through her almost dried up channel.

Still the idea circulated around that nodes could share their channel balances with neighbors in a similar fashion how routing information in the IP network are shared with neighbors. In such a way eventually a map of paths would be constructed for each node.

A point mentioned – that in my oppionion is important but only somewhat related to these issues – was the fact that of course nodes should take higher routing fees if the timelock of the routing request is high since in the worst case this makes a channel or many other paths unusable for quite some time maybe even without a payment taking place. As a side node I just realize that this could be a more sophisticated strategy for nodes to estimate their fees if they are aware of the number of routing paths their channel makes possible.

Some technical details:
One could use the number of disjoint paths between nodes as a good criteria since it also enables heavy use of atomic multi path transactions. Also it was mentioned that one could look at the AS-number of the underlying internet hosts.

Why not using machine Learning instead of trying to find some smart algorithm / heuristics?
For me the most surprising idea was the fact that this entire autopilot problem could easily be transferd into a machine learning problem. There are some obvious flaws because single nodes might not have enough training data and if one has enough data sharing the model would probably also not work out of the box. So we discussed a little bit if that would be a use case for transfer learning. Here I will not dig deeper into the topic, since the article is already quite long. But working in the field of machine learning and being a data scientist and having not even put the slightest thought about this idea before the event took place was a little bit shocking and surprising for me.

Anyway I hope my summary of the session will be useful for you and the community! My personal roadmap now consists of four things.

  1. I am thinking to add a splicing protocol specification to the BOLT (lightning-rfc)
  2. I want to get running with go-lang and the codebase of lnd in order to be able to do some hands on experiments.
  3. I plan to update the very rough draft of the white paper.
  4. Finally I will hopefully find the time to hack a litte python script that does a simulation of how my above described splicing strategy would create a lightning network wich is able to route most payment requests. If you want to be update just follow me on twitter where I will inform you once I am done. Also feel free to leave a comment with more ideas or extend the draft of the white paper. I would love join forces working on this topic.

Also kudos to Susette Bader who took this really nice snapshot and cover image of this post while we have been hacking.

]]>
https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin/feed/ 2