Multihop of the Lightning Network
Speakers: Rene Pickhardt
Date: June 24, 2019
Transcript By: Elle Mouton, Corey Phillips, Brian Mancini, Abubakar Nur Khalil
Media: https://www.youtube.com/watch?v=P7I-C0_sijg
Slides: https://residency.chaincode.com/presentations/lightning/Multihop_Layer.pdf
Introduction
I’m going to talk about Lightning Network payment channels and the update layer which is basically multihop payments and the outline of this talk is one slide myths about routing that are floating around and I just want to discuss them in the beginning very briefly. Then I will talk about the payment process on the Lightning Network and compare it a little bit with the payment process on Bitcoin. It’s not very technical but it motivates some stuff of why we’re doing stuff on Lightning and how we’re doing this. Then I explain how trustless payment can be achieved via HTLCs. As I mentioned before, we do a short break and ask if you really want to see this because I explain it more technically than when I talk about the Sphynx mix format and Onion Routing. For those who are already familiar with a Sphynx mix from it and Onion Routing I don’t talk about filler generation and padding. I omitted this because I think it’s too technical for a talk and if somebody wants to dive in really deeply, they can. So yeah let’s talk about some myths about routing.
Myths
So the first myth is that it is unsolvable. That is certainly not true because currently payments are being routed on the Lightning Network so it’s not unsolvable. The second myth is that it’s NP hard or NP complete. This is plain wrong I mean you have to admit most path finding algorithms have a worst case of cubic run time but it’s far away from being NP complete or NP hard, however it’s still computationally heavy and maybe if the Lightning Network really grows it becomes infeasible for cheap or small hardware or low bandwidth devices, so that’s something I think we as a community should be honest about to acknowledge that routing still is a difficult problem.
(Myth 3) Some people would argue it relies on trust. I would argue that HTLCs operate in a trustless manner so that should not be true however nodes can misbehave to interrupt the routing process. I mean if your node is just not forwarding the HTLC and then sending an error back or saying it timed out or something you still need to like to trust the people to behave properly in order for everything to work but they can’t steal your money or something. (Myth 4) It needs central nodes or routing hubs. Currently we don’t really have research for this on the Lightning Network but if you look into the research of social network analysis it suggests quite the opposite that we don’t need those central nodes.
And then of course there’s the other myth, coming from the Bitcoin community, it has no problems at all. I would say there’s for example spamming and delaying of HTLCs is a principal problem that we have in the current construction of the Lightning Network so I would say there are some problems. And another one is pathfinding that is a little bit difficult which I will talk about tomorrow a little bit more.
So, after this talk you should hopefully understand this picture. So right now you don’t have to understand it. Who does understand this picture already? This is good and for most people hopefully there’s something to learn you don’t have to understand it now. We’re working towards this.
So the payment process: so I want to compare the payment process of on chain Bitcoin and off chain Lightning Network payments. Something that you probably experienced and know. Bitcoin addresses I would say are a little bit like bank numbers or bank account numbers, right? Bitcoins can be sent to that address. If I know the bank account number of another person I can send money to that bank account. I can do wire transfer.
And in Bitcoin we have this concept of payment requests if you have a Bitcoin wallet but they mainly only exist for a smoother user experience because you can already say hey I request this amount of Bitcoin and you can scan the QR code and then your interface already shows this. But Bitcoin itself does not really have this. In Lightning, however, you at least currently cannot really send money to another Lightning node without an invoice which comes with a payment request unless you do some dirty low level routing tricks where you drop the amount and routing fee on a circular route that we just discussed and I did a video in the past demonstrating this. Or you have the spontaneous payment extension by LND.
I think it’s merged by now so you can do it. But still only by using mechanisms like this. But the standard way is to have an invoice. So in Lightning the recipient, or payee, first has to issue this invoice as I just mentioned and the payer in Lightning pays the invoice in return for a secret pre-image. I mean that’s all stuff that we already know. You could call this secret preimage also a receipt, right the proof of payment that we mentioned before. And my question is: what does this have to do with routing and the fact that lightning is a network? Anybody has some ideas on this I mean I’m supposed to talk about multi hop payments right and I started off by looking at the payment process of Bitcoin and Lightning Network and comparing those so why am I doing this and what does this have to do with the fact that in Lightning we have a network?
Audience Members speak
Yeah right right we have the hashed time locks right and then we have the payment hash that is always in there to fulfill these contracts and that is pretty much the reason. How we do a trustless multi-hop payment. But let’s look at this in the next couple of slides.
Trustless multi-hop payment
So I’m actually happy that we’re discussing them even though they’re very high level and non-technical. So let’s start out with a cash setting. It’s not even Bitcoin. Start with cash: let’s assume I do a cash payment, right. So what I do is ask for the price: how much is it? and then the person says worth 10 bucks and then I give the money 10 bucks and I get the receipt or I get the good or I get whatever I wanted to get for the 10 bucks. And from a computer science perspective this process should be somewhat atomic in the best case: if I want to buy your water you can hold the water in one hand I can host the dollar bill in the other hand, it’s ten bucks, and we can both like attach to it and then we can keep loose at the same moment and we can really make this atomic in the sense: either the payment occurred and the good was delivered or it didn’t happen and we’re happy with it. So that’s the concept of atomicity which we get in a cash setting. Let’s look at a direct on chain payment with Bitcoin. So if I want to send one Bitcoin I do not really get a receipt or something. What I do is I look at the blockchain if the transaction was being mined this is my receipt in Bitcoin.
Audience Member speaks
You’re right I could do that. In the standard use case, that people in bitcoin have.
So yes, you could do it on Bitcoin, in the standard use case, what you do is you look on the blockchain, on the blockchain you see that the payment actually occurred. To some degree you could still say it’s atomic because either the payment was mined or it was not mined right so but there’s not no such thing in Bitcoin as a half payment. I mean there’s an unconfirmed transaction yeah right okay.
Indirect physical payment with cash
So let’s look at an indirect physical payment with cash right so let’s assume there’s a third party like a bank or another person that is supposed to help me with my payment by helping to forward the payment. I want this to be atomic right. I don’t want this person in the middle to be able to run with the money. And the question is can it though? because otherwise we have this situation where I give the ten bucks to the person in the middle and the person says ‘yay it’s ten bucks for me, great’. It says ‘yeah it’s great I don’t have a receipt yet but yeah no problem I just didn’t get an answer yet I will do it eventually’.
So the question is can we make this atomic in the real world? And how we could do this is we could create a contract where I’m saying “you know what I give you ten bucks if you prove that you have given ten bucks to a payee and if you do that and we create this contract I feel pretty confident”. So we make this contract and now the person in the middle says “you know what we also make a contract saying: “I pay you, I give you the ten bucks if you provide me with a receipt”. And these people could set up these contracts in the offline world or in the cash world negotiate these contracts.
Audience Member speaks
Okay certainly right I mean that’s the reason why I’m trying to explain the concepts are very basic and natural or human. So you could do something like this. And of course you could add a service fee where you say:“you know what I give you 11 if you prove this and if you forward 10” and then this person gets like $1 or fee of actually having all this hassle of setting up another contract and helping me out with a payment.
So then what would happen is this person would actually know it has this contract that we agreed on this. It would give the 10 bucks, get a receipt. This is an atomic operation. And then it can fulfill this contract. And in this way we have been able, in the offline world, to make an atomic process like this. However I would argue that in the offline world they are huge risks attached to this process. You said that in France this has existed for many years.
You could have a badly written contract. Natural language is just vague in general. And then you could have forgery on the receipt and going to court might be more expensive than the 10 bucks here. Time consuming. So you might not go and settle this in court, you’re just gonna drop your 10 bucks and say “you know what I lost”. So as I’m saying in the real world this kind of indirect payment process comes with huge risk. I would argue that with programmable smart contracts on lightning, with hash time lock contracts, this is going to be much better.
Hashed time locked contracts
So what are hashed time locked contracts? Well it’s just a regular Bitcoin transaction with a special script inside.
This script I refer to as a “condition payment” usually. And I mean there’s a time lock too but it’s conditional payment and the transaction is locked for a certain amount of time. So this amount of time is which it takes to forward the payment and get the receipt. And then the receipt is a secret random, and in the best case unique, value called the preimage. I will use these terms interchangeably. And the hash of the preimage is called the payment hash. This can be seen as an identifier for this particular payment unless we have payment decorrelation where they payment hash will change in every hop but currently we have the same payment hash for every hope in the network and the thing to notice is it’s really like a legal contract from the cash setting but without the disadvantages because it’s pretty cheaply enforceable by publishing the contract, which is the Bitcoin transaction, to the Bitcoin network. It’s much cheaper than our court system even when we have a fee spike. And it’s not really possible to have a misunderstanding because it’s a program contract. It follows a protocol. Everybody knows how to read these contracts and how to follow this protocol. So there is not really a lot of room for misinterpretation here. So hash time lock contracts and payment channels: they enable direct atomic payment between two neighbors that share a channel. Nodes build a network and payments in the networks resemble the situation of indirect payments with cash. And hashed time lock contracts are just there to solve this problem. So in the offline world we had this but in Bitcoin we can do it in this way. On a technical level HTLCs are just another output in the commitment transactions.
We had this before but instead of the two outputs we now have several hased time lock contracts. Coming to the question that you asked before, let’s assume that one of these HTLCs is timing out, I can still set up more HTLCs for other payments. The channel is still operational even though one HTLC might have a local problem at a certain point in time. The good thing is they can be enforced on chain if the channel fails and they can be settled off chain if the pre-image is provided which was the situation that we discussed before when later in the route the channel breaks and the pre-image is seen on chain and then the other one can still settle off chain which is nice.
Before explaining the details of routing, I want to ask: how is the payment hash sent over? We do an invoice. Most of the stuff in Lightning is encoded as lightning messages that are encrypted over Noise_XK framework, ChaChaPoly or whatever. Here we just have an invoice and we depend on communication between people. I could literally on the telephone dictate the invoice to you or I could do a QR code or whatever. But Lightning doesn’t explain which medium we should use for this part of the protocol. But I was wondering in the beginning, when Christian was giving an overview of all the BOLTs, why he didn’t include BOLT 11 as part of the multi-hop layer. He said BOLT 4 and the Onion Routing is the multi-hop but I would argue that BOLT 11 also belongs to multi-hop because this is really the first step that is needed to do this because this is how we transport the payment hash and without the payment hash we can’t set up HTLCs. So that was the first part.
I could skip the next one and go to the Sphinx routing right away so I would do this by hand. Who wants me to skip the next part? perfect only James. All right so let’s talk about trustless routing of payments through a network of payment channels. And again this is very high level and then the technical stuff comes in the third part where I’m talking about sphinx routing. So this is how my lightning network looks like. So here is Alice. Alice has a multi signature wallet together with Bob right and the commitment transaction currently looks like 0.35 bitcoins are going to Alice and 0.15 Bitcoin go to Bob. So together they have this channel and if you add these numbers together (I neglect the onchain fees) they have half a Bitcoin in this channel. and you have a similar situation for Bob and Charlie. Only that this channel has a higher capacity. And if you add these two outputs together you see that Bob has a total balance of 0.65 bitcoins that Bob owns. So this is my setup. And now Alice thinks: “hey, I want to send one Bitcoin to Charlie”.
And as you see I mean I want to talk about a trustless network initially but let’s talk about a trusting Lightning Network initially. Right so Alice thinks: “hey, I want to send this money over to Bob”. How does she do this? the commitment transaction gets updated, right so here the balance changed and now if you add this together Bob now has 0.75 bitcoins and Bob says: “hey, I’m very honest and of course I forward the payment”, so now this balance is updated and Charlie now has 0.4 Bitcoin and Alice has 0.25 bitcoins and the payment went through and everybody is happy.
Obviously we could have the situation, or we do have the situation, how I created this here that Alice needed to trust Bob to forward the payment. Alright, both payment channels needed to negotiate a new commitment transaction for both sides and we could change the output of the commitment transaction so that routing works trustless, right, that’s our goal now. And the idea is - how we do this is - we use the bib–[inaudible] of the hashed time locked contracts and we include this in the outputs of the commitment transactions, so we have another conditional output in the commitment transaction that says “hey, if you can provide me the receipt of the transaction you can settle this”, and this output technically can only be spent by the recipient because that’s the person who knows the preimage sent from the very end of the path back all the way to the sender and within a certain time frame because otherwise if the recipient can’t provide the preimage to the payment hash after this timeframe the sender can claim the funds back.
Alright, so basically on lightning what we do off-chain is remove the HTLC from the channel. Okay, so this is the trustless lightning Network, it starts that Charlie has a hash of some random value “R”, and as you mentioned before, it needs to get this over to Alice somehow and this is being done by Alice saying ‘hey, I want to send you some money please’ to an invoice so this is being sent over via an invoice, and what Alice now does is it changes the outputs here and this commitment transaction that spends from this multi signature wallet, so you see she already removed some of her balance before she had 0.35 Bitcoin here and now there is this 0.1 Bitcoin that is pointing to this payment hash or to a script that when you like reveal the preimage to this hash any person can claim right and Bob still has the old output. Right and Alice thinks well if what doesn’t provide “R” after the time lock I can just claim the money back so no big risk for Alice at this point. What Bob thinks is well I can’t claim this 0.1 Bitcoin without knowing “R” some time, alright. So Bob now is really incentivized to say you know what this payment is supposed to be for Charlie. I set up an HTLC with Charlie using the same payment hash because if Charlie wants to have this payment it can only do so by providing the preimage to me and then I can claim this money.
That’s the entire idea, and as you can see Bob now has less money than before right because this money technically does not belong to him, this money technically is not claimed by him yet right it’s like somewhere in Havana right and the real money that that’s really here at this point is there right but I mean obviously since the CLTV deltas are all fitting together Bob knows that you won’t lose money but Alice on the other hand didn’t need to trust Bob that this is really working that Bob is working properly because if Bob just doesn’t forward the payment then Alice gets her HTLC output back. Well so now um this cloud should be here sorry for that, charlie is like hey I need to really get this payment back to Alice so sorry for this so yeah Charlie thinks well I can only claim this HTLC output by providing “R” so Charlie provides “R” to Bob and now it’s safe to make a new commitment state where Charlie really has the money so Charlie already is reimbursed like in the indirect payment setting with cash that I painted in the beginning and this HTLC is still active Alice has not really paid yet but Alice already like lost the funds by creating this output and then since Bob has the “R” value Bob says yeah “great this “R” really produces the payment hash, so now I claim the funds back from Alice”, yep.
Audience Member asks a question
It shows up, so the thing is, if we two have a channel and we don’t even do a complex routing process but I just want to set money to you the way how we do this and Fabrice already showed it in his pictures is we set up an HTLC, uhm I have some slides later where your question already in my first tour I explained and how exactly the messages are there on the protocol level so remember like last talk it started very high-level and then it became very technical so I come to this but I differ to the future at this point but yes the HTLC really shows up. [someone asks another unknown question] Well this yeah so if you are here, right, technically at this point when when Bob says “I want to forward this”, Charlie could answer right away “hey I already know the preimage, just give me the money” right but the thing is I mean we want to have it in a way where when Bob forwards the payment, Bob doesn’t know that Charlie is the final destination right for privacy reasons right so we implemented it in a way that it’s the general case anyway because then you can do it with the same lightening messages that you don’t have to like do a case distinction so it’s just better to do it in this way. Yep.
Audience Member asks a question
That’s the point, so when we’re here, Charlie doesn’t have to reveal the preimage that’s correct, right, but if Charlie wants to have the money, off-chain or on-chain, in both cases Charlie will need the preimage to either spend this output or to get rid of this output and get the amount of money in there in his output of his commitment transaction also the other party’s commitment transaction but we look later in detail how we really update the commitment transactions and how the HTLC output is there I just ask for some patience.
Source based onion routing and the SPHINX mix format
So let’s go to source based onion routing and the Sphinx mix format and I’ve heard you have already read some parts of the paper and I don’t envy you because I think it’s a very technical paper and incredibly difficult to read.
So why are we using the Sphinx mix format? Well, the payer wants to be able to send money without being exposed, right, so it’s about privacy. It was for me one of the most amazing moments when I set up my first lightning node and I created a small paywall app and the first person paid me and you know, it’s like setting up your first blog or your first youtube video or whatever, right? You’re like “oh who was it”? You look in your log files and I look at my lightning log files already knowing I won’t find anything and I was like yeah I didn’t find anything right because it was completely anonymous as I should have known before. But it was to some degree frustrating to realize that it was really anonymous and then I was really happy to see oh yeah it is really working. Yeah, sorry I had to share this story.
So the payee doesn’t want to be exposed either to the rest of the network. So if I want to receive some money and other people are helping on the routing process they don’t have to know that they’re actually routing money to me. Then the routing nodes have to be able to send back an error message. If something is not working for example there’s not enough balance or the onion was not formatted correctly because there’s not enough fees there. There has to be some way of giving a response back to the initiator. And the routing nodes should know it’s little information about the payment as possible right.
So this is the payment hash, which as I mentioned before and I think Fabrice already mentioned will stop with payment de-correlation and the routing nodes only know an upper bound for the amount that is being paid. If forward a certain amount I know that the extra payment is lower because they’re still future routing fees included in this amount, but this would also stop when we have atomic multipath routing because then I only know that this is a certain payment but there might be other payments on other routes going to this, so I don’t even know the upper bound of the payment.
What they know is the incoming channel where the payment is coming from, so not the original sender necessarily but just my channel on which the payment is coming in and the outgoing channel on which channel I should forward the payment. Everything else they don’t know. And routing nodes want to be able to verify the authenticity of the onion. So they don’t want the onion that is being processed to have some like weird information so there’s still some HMACs in the onions at every hop so that routing nodes can actually check that everything is in the way it is supposed to be.
What the research community will tell you and I think it’s already in the abstract of the paper is it’s very compact format. It uses only very little data and for the coming part I think you already saw the video and I think the video actually is a better medium than slides to explain this, but you will see the exact same example.
There’s Alice and she wants to send 300 satoshis without a direct payment channel to David. But Alice of course knowing the gossip protocol has a pretty good idea of what the network looks like and Alice decides “oh, I have a channel with Bob and Bob has a channel with Charlie and Charlie luckily has a channel with David” so Alice decides that she wants to use this path to send a payment and there’s short channel IDs because we later need them in the onions and I didn’t use the full length short channel IDs but just some short ones to make it easier to talk about them in [inaudible].
So, we start creating the onion, starting from David. So if Alice wants to create a payment Alice begins at David’s point. We create an onion starting from David’s and the interesting thing is in the onion itself there’s no payment hash inside. I was pretty surprised to see this the payment hashes were transported in a different manner. But what does the format of the only look like? Well we have a header and there’s a version byte in it because we might have different versions of the onions. There’s a 33 byte compressed public-key inside of the onion, and we will, in a few slides, see why we actually need this key. It’s used for diffie-hellman key exchange.
The interesting thing is it’s not the sender’s pubkey or node ID. Because if it were the sender’s pubkey the sender would be revealed. So it’s a different one but it’s an ephemeral pubkey from the sender for David. So the sender generates a new key pair specifically to use for this payment with David. From this key-pair the sender sends the pubkey over to David. Then there is a payload in the onion. The payload consists of 1,300 bytes of hops-data and this boils down to 20 times 65 bytes so you can have a maximum of 20 hops on the onion. There’s no longer paths permitted in the Lightning Network currently, even if the network would grow as a larger diameter. And each hop needs 65 bytes of data; the first one is the realm which is currently set to 0. it’s kind of like another version there. Then there is 32 bytes per hop payload 32 byte of an HMAC to verify that this particular per hop data is the one that’s supposed to be there and then there is some filler in the payload and as I said I won’t discuss the filler completely. Once you have the header of the payload and you have another HMAC for the entire onion to go to verify the integrity.
So the question is: what kind of data do we store in the per hop data? We store the short channel ID, the amount to forward, the outgoing CLTV value, and then some padding which we might use later for other information so we already put this here for future backwards compatibility. As you can see there’s in this data that we use in the onion, there’s no where the payment hash is included which again I think it’s a little bit remarkable that it works without it.
[someone asks an inaudible question and prompts an inaudible discussion]
So the shared secret could already be the preimage basically and then you know if you hash it it’s the payment hash, that- stuff like this.
[Someone briefly remarks] But you could even have an inner onion where you don’t have to hash it twice and signal in the realm that this onion is the last one. Hey, there’s a lot of possibilities, I’m just saying this. So yeah, it’s not specked out as Christian says.
So, the per hop payload for David simplified looks like this, that the short channel ID is set to zero which signals to David “hey you are the last hop. There’s no other channel you like to put it to”. The amount to forward is 300 which means you receive 300 satoshis and then there is some CLTV value and I think for the last hop for David you could also set it to basically whatever because there’s nothing happening here anymore.Then what is happening, as I mentioned before, there is this ephemeral key for David and this part here is encrypted by doing a Diffie-Hellman key exchange between the private key that belongs to this ephemeral key and the private key is known to Alice and David’s public node key. Then this is nice because David now with this private node key and this public ephemeral key can also create a shared secret and that was too quick for you.
I will actually talk a little bit about sharing a secret between Alice and David. So this is now very mathematical and I desperately wore my pie shirt today because I’m a mathematician instead of a lightning network shirt because I knew I have this and the next slide which you see me smiling already. So let “G” be a generator point of our elliptic curve of prime order, so we have an elliptic curve of prime order “p” which is always a cyclic subgroup of prime order, and we have “a” and “d”, um, are basically integers smaller than “p” which we call private keys for Alice and David and now we can derive the public keys right, how do we do this?
We multiply our curve point by “a” which basically means we add the “a” to the generator point “a” times to derive our big “A” which is the public key. And we can do the same for David and these are the static node IDs for Alice and David. Now the elliptic curve diffie-hellman key exchange says that “a” times “D”, so small “a” times big “D” is the same as small “d” times big “A” and this is our shared secret which we can use for symmetric encryption. So I want to do a mathematical proof with you to see that this equation actually holds and the funny thing is it’s a very easy simple mathematical proof.
So it starts with a “D” which is the left-hand side of our proof and by definition we know that a “D” is the same as “a” times small “d” times “G.” This is just the definition here and then we can use the law of associativity and we can basically move these parenthesis over here. Then since we have integers which we multiply with each other, we can use the fact that these integers are actually living in this group, which is an abelian group. We can flip them around so now we have “d” times “a” times “G”. We use the law of associativity again.
So now we have “D” times “a"“G” and we can plug in the definition. And here we go. We have proven that “aD” is the same as “dA” which is extremely cool.
No it is. I mean honestly think about this you can just by knowing the public keys of other people and multiplying your own private key you have something that it’s a shared secret or shared value that only you two can know right? I mean this is part of the properties only Alice and David can know their shared secret right? A third party cannot just multiply some value with their private key because it will be a different equation here it will result in a different curve point and the shared secret.
As I said before can be used for symmetric encryption then and once the public keys are known and David can independently compute the shared secret they don’t even have to communicate anymore which is also extremely cool.
Discrete logarithm
Yeah and it’s the second mathematical slide short Intermezzo for math notes about the discrete logarithm because I think everybody who is interested in you just saw this last week already right discrete logarithm right.
I mean I’m strong to say that everybody should really be aware of this because this is where the entire worth of Bitcoin comes from. Alright as soon as we solve the discrete logarithm problem Bitcoin basically instantly becomes worthless so EC is an elliptic curve it’s a group and it’s homeomorphic to Z modulo pZ and the diffie-hellman key exchange heavily uses the following homomorphism so homomorphism is a map that goes from this group to this group and how does this map look like well we take an element from this group which before we call it an integer or usually people call it a private key and we map it with the map age to a times G which is our generator or point on the elliptic curve.
Audience Member asks a question
That is true, but yeah I mean it I’m pretty sure if I would solve the discrete log problem or anybody else they would destroy Bitcoin right away. It’s I mean first of all I could see a lot of funds they could go to an exchange and then exploit it and it would work very quickly and afterwards I’d yeah but you can steal a lot of coins yeah yeah no I mean there’s other ingredients right but I mean the discrete Locke is the core assumption upon which currently builds a security model right? I agree with you that former transactions cannot be reversed but I mean if you can steal them then what good are they?
Anyway the elements in this cyclic group are called private keys and the elements in the elliptic curve are called public keys. By construction and math theory we know that age is not only a homomorphism but an isomorphism, which means that age is ejective and an inverse map age race to the minus 1 power does exist. We already know from a mathematical theory that it does exist, which is a little bit scary, if you think about it. Because as I mentioned before, if we would know how this map looks like, we basically could compromise Bitcoin. So the fun thing is this inverse map is unknown unless we compute H for all elements of this group and we start with this group to be so large that we say it’s infeasible to do this with a computer. Because we could not even store all the elements because we have way too many elements there.
The funny thing is I was just recently at a university talking to some professors who are actually working in algebraic geometry and I asked each of them why is the discrete log problem actually difficult and all of them told me “we don’t even have an argument for this in math. We just know it’s difficult.” There’s no deeper mathematical theory that they were aware of as to why this is a complex problem.
Audience Member asks a question
No. Well the thing is, we already know there is a solution. We already know it exists. We just don’t know a construction to analytically create this. I mean computationally we can already do it even in linear time. We have two for one for each element in the billion and in this group. I mean knowing this map in this direction, this is ridiculously easy. Giving a little closed formula for “H” the inverse map is called the discrete logarithm problem.
So going back to that we use the diffie-hellman key exchange and this stuff to create a shared secret between the private key that belongs to this ephemeral key and the public key that belongs to David. David obviously with this public key and his private note key can decrypt this onion right and nobody else on the route can decrypt this onion so this is what the inner part of the onion looks like now we look at the payload for Charlie.
Charlie now has an increased CATV Delta. Charlie still forwards 300 satoshis because Charlie is paying David and David is supposed to get 300 satoshis. The short channel ID tells Charlie “please forward this on this channel” and again we or Ellis generates a new key pair if it will keep here for Charlie with the same trick encrypts this entire blob. So we are there and now we look at the payload for Bob gets a little bit repetitive but for both something changes a little bit. Bob now has an amount to forward of 301. Why is that? Yeah, but these are not Bob’s fees. Charlie wants fees, right? So Bob is forwarding 301 so that Charlie can forward 300.
So Charlie gets one satoshi in fee, but this is where the fees are actually really encoded into the onion. They’re not explicitly like “here’s your fee” but it’s just the difference of the amount to forward values on there. This gets encrypted again and then of course Ellis has to set up an HTLC to Bob. But this is not part of the onion. So as we mentioned they have to be decreasing along the path so interestingly enough to know that the onion is constructed from Dave - Charlie - Bob - Ellis but now the eightieth he’s have to be set up this goes the other way around. The HTLC’s are set up first from Alice to Bob then from Bob to Charlie and then from Charlie to David and then the preimage again is released in this direction.
Audience Member asks a question
Yeah. Alice is creating this entire onion and Alice is defining all these values here. So what Alice does is look at the gossip protocol, what the CLTV delta has out for each channel, and she’s just basically adding to them. So for this channel, there’s a CLTV Delta of nine. Since we start with nine she’s adding another nine so now we have 18. Then comes, I don’t know what this was, 23, yes exactly. So what could happen is that the onion later on is transported at some point. Charlie looks at what she’s doing there and says, no no no CLTV delta the fee is too small and then an arrow is being reported back right?
So yeah this can happen, in particular when Charlie changes the channel parameters and an update message is sent over the gossip protocol as we will see tomorrow. Meanwhile an onion could already be on its way. So then it arrives at Charlie and Charlie says “No, this does not fit my parameters anymore.”
Audience Member asks a question
Yep, maybe I made a mistake. I mean it happens all the time, but as far as I understood, the time lock needs to be decreasing along the road right? So in case that this thing settled on chain Charlie still has enough time to turn around, it was the wording to go to Bob right? So the CLTV delta has other time locks that are being used and the fees start at the end. We will see this tomorrow. Well I mean you start with this Low CLTV. I mean you could start in the beginning and say this CLTV is a thousand and you always decrease by the deltas. But what could happen is then you go to the negative right? Then since you construct the onion from the end anyway. But for the fees there’s actually a different reason why you will look for.
Some notes on the presented simplifications. The onions themselves are the payload of the update add HTLC message and that is answering your both questions from before. We will look at this afterwards, but this is really where the payload, where the onion is transported the message. The update add HTLC message also contains the payment hash and the message offers an HTLC with an actual amount. So usually the nodes offer the amount that they are supposed to forward. I mean they could mess around with this but probably then the routing process will fail, right? Because either they forward not like less than they’re supposed to forward and then the other person doesn’t have enough fees right?
So why would they do this? Alice constructs the onion and chooses if I’m arrow keys for every hop and the onions are encrypted with the diffie-hellman shared secret between them. And as I explained before, in detail, the hops and the key generated by Alice and the hops node static key and the onions are always 1366 bytes in length so even at the last hop.
Normal operation of a channel (BOLT 02)
So if you look at the picture, the onion was always getting longer, but as I said before, I’m missing out on this village and of making the onions always certain lengths. So the onions are packed with junk data and we do this for privacy reasons. We really don’t want to note at the end of the road that they are basically the last or the second last hope. So let’s go back to bolt 2 and the update layer but I didn’t want to do it before we are in multi hub. So we talked about the normal operation of the channel right so in my last presentation we already talked about how to establish a channel and how to close a channel and all the questions how do I actually send money forward to somebody?
So the picture that you always see looks like this. There are update add HTLC messages that contain onions and we saw how the onions look like before. They have some amount to forward them, some CLTV deltas, and they have some channels on which to do this and some keys. They could go back and forth in both directions, arbitrarily hop and then at some point in time we have commitment side message and to revoke and ack message and we’re going to see how these messages are actually being sent back and forth, and why they are being sent back and forth and how this actually really looks these HTLC’s.
The 5 stages for a htlc to become valid
There are basically five stages for an HTLC to become valid and this is just basically let me just skip the slide. I do it visually afterwards so this is just for your reference to see it written down.
So let’s start here. We have Alice who has her commitment transaction 2a and we have Bob who has his commitment transaction 2b. And you can see in Bob’s commitment transaction the output to Alice’s regular output, where the output to Bob is the RSMC and vice-versa the regular output goes to Bob and the output to Alice herself as the RSMC. And Alice wants to offer a payment to Bob of 15 millibitcoin.
I’m sorry to Fabrice for repeating something that you already explained, but I think it’s worthwhile seeing this again. So Alice wants to offer a payment to Bob of 15 millibitcoin. And when you remember my first talk I basically said there is a new stage where it’s already, like, at the other side and they somehow, like, end up there but there’s actually more state in between. And how does this look like? Well there is an unsigned commitment transaction that Bob creates now. Alice sends the update_add_htlc message, which contains an onion and a payment hash. So Bob can create a new commitment transaction and add this output, right? You see Alice already has less money than here, and this money is sent to this commitment transaction, to this HTLC output. It’s still unsigned. Then Alice at the next step sends a commitment_signed message to Bob. Which means that Alice already knows what’s the next per_commitment_point that was in the opening channel message and other general messages here they will also exchange next per_commitment_point. So she can produce a signature for this transaction. Remember it’s a 2 of 2 multi-sig wallet that is being spent.
So she’s producing her signature and obviously Bob can produce his own signature, right? So now in this situation Bob has actually two valid states there’s nothing revoked yet, right? Bob could technically still publish this state without having any penalty. Only thing is Bob has no incentive to do that, right? Here Bob is getting money. Here Bob doesn’t. So, why would Bob? But he could. So now there comes the revoke_and_ack message that Bob is sending. So what Bob does is he revoked his transaction over here, because he says well this one is better to me anyway. And the entire channel operation protocol doesn’t forward if I don’t do it, right? So Bob now shares the revocation key for his revocable sequence maturity contract, right? So he can still publish this. Miners would mine it but then he would lose all his funds right? So now it’s revoked.
Alice meanwhile creates her own commitment transaction. Remember both parties have their own commitment transaction. But this one is still unsigned. So Alice needs to wait. Oh, question. If we are in this scenario, and Alice has the idea of publishing this commitment transaction, why is Bob not losing money? Yeah, so I mean if you think about it this is one state, and this is the next state, right? And this state is happening by Alice wanting to send 50 millibitcoin to Bob which here Bob seems to kind of already have, right. At least the output is here and Bob knows if he can provide a pre-image he can get this money right? So, yeah. I mean she has not revoked her transaction yet, she could publish this. This is a problem for Bob? Yeah that anyway but Fabian you raised your hand before.
Yeah but let’s assume we’re doing this for routing. That’s the point. That’s an important point, right? Bob does not forward his HTLC yet, that is really important. If Bob would have forwarded his HTLC, and somebody would already release preimages and would ask from Bob, hey I want to get reimbursed on my HTLC, and then Alice goes and publishes this one, Bob effectively loses this HTLC output, right? So the routing process at this point cannot proceed, right? So technically at this point Bob already does not really have this, right? I mean if Alice becomes unresponsive no big deal, Bob can publish this commitment transaction that’s no, no risk for Bob. Because if the timeout is really happening he can claim, well that’s the HTLC for Alice, so yeah.
I mean Bob has 20 millibitcoin here right? Nothing bad happens. This one? This transaction Alice never sees. So, Alice can construct this transaction right? And in the same way as Alice can construct this transaction. She never sees it signed. Right? Because she doesn’t have Bob’s key to sign this. Bob never sends over his key; he only sends over the-Yeah, that’s the point. That’s the point. Only if Bob publishes it, does Bob have a really fully signed transaction. Then she says yeah okay the Bitcoin network obviously accepts it but then she says, hey I can claim this output. This is really how it’s working. Okay I thought you were, sorry. Okay, um, so how does the protocol continue? Well Bob sends his commitment_signed message right? So, this goes pretty much in your direction, which means Bob now sends the signature for this commitment transaction. And again Bob does never see this entire commitment transaction signed unless there’s. His part of the signature. Alice, yep.
So now this is how the protocol looks like. This one is revoked. Alice still is able to publish this one but Alice really wants the payment to go forward right? Maybe she has already set up an HTLC incoming to her right? So what Alice now does is she sends the revoke_and_ack message, which basically reveals the revocation key of this output to Bob. And now after Bob has received this message we know these two states are really invalidated. These two are the real new states. And only now the routing process can actually continue. Only now Bob talks to Charlie and sends forward the onion or if Bob is in the store and can release the preimage can, can do whatever. And can be sure that Bob can actually claim and this output even hits the chain. I’m not sure I get your question.
Yes so the thing is also for the revocation keys, so remember when the channel was opened, the channel open message had five base points right? So there was a revocation base point, a commitment base point, to local base point, to remote base point, and HTLC base points. So the revocation keys are also derived from each other, right? So technically you only need to remember your last revocation key and you can derive all the previous ones. So, but for this to work properly you need to pre-generate like some of the keys and I think they pre-generate like 2 million or something, or you can do this at least 2 million times. And then of course you could renegotiate or whatever right? So, so technically forever or at least theoretically forever. Yes sorry. It’s like, I’m still a little bit jetting. Oh really good ideas actually true to delete the old states because then you don’t accidentally publish them. But, what you do is, when you see um when you see that the funding transaction of your channel, which you, which you save, hits the chain if it’s spent right? I mean the funding transaction was onchain anyway, but if you see that it’s been spent on chain and it’s not spent with your current state.
What you do is you take your current revocation key from the other side and you calculate backwards until you find one of those keys that actually enables you to spend the output. Yeah, yeah but this is something that you can verify as soon as you receive the revocation key. You can directly see if its child was the previous revocation key. And you should check this. I mean even though these slides are very technical, I still omitted some stuff in there. Yeah. The hash? In the penalty transaction, I mean it’s just the penalty path. So. You know. I mean in all stages of the commitment transaction, for all outputs, they all have a penalty path. And the penalty path always is the first line in the contract, where if you have the revocation key you can claim it.
So you don’t need to remember the payment hash. I think so, yeah. I think the revocation key is it’s, it’s on the level of the commitment transaction and then all the outputs like, have the same revocation key. Maybe. Honestly maybe. I mean. You need the script. Okay. But then this would mean that every node would have to store all previous HTLC payment hash values. You know I understand what you’re saying but I mean, then, then when we have to restore that amount of information anyway then it doesn’t make sense, I mean it still makes sense to save some part of the key. But I mean why, why go through all this burden. But at least we are here for another four days right? We can look this up. When I can put a sledge hammer out here as far as I understand with mast, we should not have the problem because we can have separate script parts, but we don’t have mast yet. Yeah but in that case you would only want to use the revocation password. And that you could construct. In this one you could construct. At least one sledgehammer we have here.
All right now we should look this up. I would still suggest we’ll continue with the talk and continue the other discussion either offline or tomorrow because I think currently it’s a little bit difficult to figure this out. Interesting enough.
So yeah, I promised you in the beginning that you would understand this like, workflow complex graphic, by the end of the talk. So if Alice wants to pay David, the first thing that happens by a BOLT 11 invoice, the payment hash being transported back to Alice. And then Alice finds, somehow magically, a path to David. And then creates the entire onion and starts sending the onion forward. And as I mentioned before the onion is part of the update_add_htlc message. So this blob basically is sent from Alice to Bob. And then Bob decrypts this and sees basically this part. And creates a new onion sending over this part. And we have the final onion arriving for David. And then the preimage with the update_fulfill_htlc messages is being propagated backwards.
In this way the HTLC outputs can technically be removed from the commitment transactions. I think in the implementations they will just stay there and the next time they make a new stage they just omit the HTLC output because they know it’s settled. So they don’t make an intermediate output where they don’t have it because they know if it hits the chain they can still enforce it because the preimage is known. So yeah, this is the workflow in multi-hop on the Lightning Network and I think I’d hope this was my last slide so again there are some pointers. Yeah. So let’s look here. The receiver gives up the revocation key first because this one they say, you know what? I don’t care. I can still enforce this. I still have my twenty, which I had before. I don’t know if I get this one, but even if I don’t, I didn’t forward anything. Easy. Then it’s the other way around, right.
Yeah, yeah. Other questions? We discussed a lot already. Yeah. Yeah. In c-lightning I think you can look in your database. There’s an SQLite3 database and I think there is. But still also in the database I would say. The database is the best API. Just make a copy. Database is the best API. Yeah, you should document it on the readme.
[Applause]