How to Build Robust Payment Channel Networks with Zeta Avarikioti | a16z crypto research talks

Transcript

very happy to introduce um zeta avaria kyoti who is visiting us from tui and will be telling us about payment channels hi everyone i'm i'm a postdoc at the technical university of vienna uh and i'm going to present you today a multiple works that i did last year on payment channel networks uh so i will start with a brief introduction scalability and what payment channels and payment channel networks are i guess you all know that cryptocurrencies cannot scale and what we mean by cannot scale is that they have a very low transaction throughput specifically bitcoin and ethereum can process tens of transactions per second

while digital payment systems such as visa handle thousands of transactions per second now the the question is can we actually make the cryptocurrencies a scale and amount such as visa and there are multiple solutions proposed towards this direction because the problem is inherent in the consensus layer of the cryptocurrencies of the blockchain and the solutions can be categorized into major categories the first one is on chain solutions which increases the layer 1 throughput so essentially you're trying to make the blockchain itself to handle more transactions per second and the second one is called layer two and this is an off-chain solution and

what we mean by off-chain solution is that the major part of the transaction workload is handled off the blockchain so typical layer 1 solutions are designed in a new consensus mechanism using other structures from a chain you can go to a tag or use sharding which is using parallel blockchains to parallelize the processing of the transactions uh typical layer 2 solutions are payment channels which is which is going to be the focus of the talk today and another example is side chains there are solutions that lie in between layer one and layer two uh notably uh commit chains and roll-ups

now most of you would know roll-ups and they're sometimes considered layer two solutions but given the fact that they have a very high on chain uh footprint um i would say they lie somewhere in between layer one and layer two so you're thinking of like a pure layer two was having like sub-constant on-chain footprint for transaction kind of thing yes because the thing is with roll-ups as they are to have that availability you need to uh publish the transactions on chain so you can have a constant compression which is fine but asymptotically don't really do anything while payment channels or side chains you theoretically you handle everything of changing yourself just use the blockchain as a dispute mechanism

resolution mechanism so i will do a brief introduction on payment channels if something is not clear just stop me so what is a payment channel suppose we have alice and bob and they want to do multiple transactions uh on the blockchain but they don't actually want to use the blockchain because of the load transaction throughput which eventually leads to very high transaction fees what alice and bob can do is they can create a joint account where they lock their funds and they can use them however they want later so to do so they create this transaction which is called a funding transaction uh the notation we're gonna use or the names is from lightning uh because we're gonna focus more on the bitcoin uh lightning network which is

implementation of payment charts on bitcoin uh so the fountain transaction has two inputs which is one from alice and one from bob it represents the coins they put and the output is uh something it's a it's a utxo that can be spent by the signature of both alice and bob so essentially to close the joint account we need both parties to agree now before they open that account um on the blockchain alice and bob give back create the first commitment transaction and give back to themselves the original distribution of coins so if alice put five coins in pop four we create a transaction that spends the fund the output of the funding transaction and says alice owns four by five coins and bob four

the moment they have created and signed this transaction they can open the join account on the blockchain which we call a payment channel now from that point on alice and bob can transact arbitrarily many times as long as there is enough capital to do what they want what i mean by that is the following suppose alice wants to send three coins to bob so what will happen is essentially that alice and bob will update the distribution of the joint funds to represent what the the new state after the transaction so alice had five minus three c will have two and bob had four plus three he will have seven and bob may want to send six coins to

aries again we do the same thing so essentially the coins in the payment channel they move like the balls in a row of an abacus back and forth but that we cannot move more than what is existing at the moment so for instance in the last date if bob wants to give two coins to alice this is not visible because he does not own two coins the other important thing is that the money that is locked in a payment channel cannot be used for any other purpose any other purpose on the blockchain or any other payment channel that alice or bob owns so essentially this money is locked there until the payment channel is closed but how do we close a payment channel i just want to say that's one of the more

helpful in the previous slide right that's one of the more helpful figures it's exactly right yes because you also can't move right from one light to another so um if you want to close a payment channel there are two ways the first way is uh to do it in collaboration with your with your with your counterparty so let's say alice wants to close the channel so she goes to bob and say okay this is the last distribution that we have agreed on let's sign a transaction that spends the output of the funding transaction if boba garris we're fine but there is a case where bob may not be

responsive or doesn't want to sign because for instance he has zero money in the in the channel so he doesn't care anymore ali should always be able to get back the money that is locked in the channel unilaterally so what alice would do in that case is she would publish the latest commitment transaction i will remind you that the commitment transactions that we saw before they're all the same the they are all spending the output of the funding transaction they just have a new distribution which means that in the eyes of a miner they're all equivalently valid and the miners don't know how many updates have happened in the channel because only alice and bob know if they have done five or ten transactions so they cannot tell which is the latest

commitment transaction why is that important uh the reason is because alice may benefit from publishing an older commitment transaction where she held more coins and as we said bob at the moment is not reactive so what could happen is that alice could publish this previous transaction and the channel then would close in an incorrect state in the sense that alice would steal money from bob to avoid that from happening the way commitment transactions are created make sure that the output of bob is always spendable immediately but the output of alice which is the party that publishes the transaction is time locked for a period that is called the dispute period

the reason this period exists is because we want bob to be able to go online during that period and challenge alice in case you can miss fraud if if this happens if alice commits fraud and bob challenges that on chain then all the money of the channel is awarded to bob so his money and alice's money is awarded to bob because we want to punish the cheating party that is a high level description of how lightning works um is it helpful to figure out i mean these days you hear a lot about fraud proofs in the context of optimistic roll-ups so i think this is like a natural conceptual precursor to that is that

fair i think it's much easier because the revocation for the bridge remedy for lightning is pretty much a secret it's like releasing the image of a hush so that is much good improv improving fraud i guess in the in the roller because the roll-up wants like miracle proofs and stuff like this right so i think it was just like a particularly simple property yes yes yes generally i think payment channels are the initial idea and roll-ups were developed slowly from going to like commit change which is the the predecessor of roll-up is pretty much um a structure that's like a payment hub and they said okay i don't want to lock that much capital let's make the commit

change and then the commit change became the roll-up so yeah i think there is much correlation between all of these and there are trade-offs pretty much a trade-off between a roll-up and a payment channel is the on-chain footprint versus how much capital you lock because if you lock the capital needed to do all transactions then you're secure you don't need proofs in that sense you don't you don't need it but then the more you relax the capital the more information you need to publish on the chain this is how i perceive that yeah i mean what they described before is a payment

channel between two parties however the power of payment channels is mainly mainly lies on the on the fact that they can create a network and what i mean by that is that if alice and bob do not share a payment channel but they are connected through a path of j payment channels they can still send a transaction to each other now how is this visible the important part is that there is a connection like a path where the edges are the channels and the nodes that participate in the channel that are the nodes in the graph um and that path has enough capital on every edge so for instance if alice wants to send three coins to bob she has to have enough money on her side

of course it's five here you can see it's uh she can send the money and the intermediary let's say charlie has to have enough coins also in this case this is feasible now there are two things that are important in implementing such an idea the first one is that we need all the transactions in the path to happen atomically and that means that either all the transactions go through or none of them go through the second thing is that the intermediary does not do that altruistically typically they ask for a fee this fee in the lightning network is quite low at the moment but this opens up a whole dimension as we will see later for game theory applications

let's see quickly how we can achieve the atomicity of transactions along campaign path so uh the tool that we use in this case the simplest tool is to use a hash timelock contract which is a contract that says that alice will pay bob a specific amount if bob can provide the pre-image of a hush else if the time passes by and bob doesn't do so the money is returned to aries so essentially you hustle something and you also time lock it you say you can take the money if you give me the secret or not take the money if you don't give me the secret during that period of time the way we use it to achieve atomicity is that

we ask the receiver in this case bob to create a secret that he only knows send the hash of that secret to the sender so alice and then alice creates that with intermediary with charlie and says i'm gonna give you that you can take the money if you know the secret that bob has but within two days and then charlie creates a similar thing with bob and says you can take the money from the channel as long as you do it within one day the reason we want the decreasing time locks is for having um ensuring security like the intermediary is not will never lose money in that way so if bob triggers that if bob triggers the the dominance of hdlcs then everybody will

have enough time to claim the money from the previous person if pop doesn't do anything then every for all the channels the money will be returned to the sender to the point the y is the same in all of these hltc's is that right yes they can just copy paste that same solution unlike the previous one right like the y something yeah so this is a very old image of the lightning network and at the moment i checked yesterday apparently we have 85 000 channels 70

000 nodes a huge increase very hard to see that and there are multiple problems this seems like a very nice solution but there are multiple problems that need to be handled uh from routing from liquidity and we will see some of them in the rest of the talk now there are these things that called state channels for instance sprites next week pat mccord is visiting he's the author of that he can tell you much more in principle yes i don't know if it's used anywhere i mean even payment

channels are not really used in some sense i'm gonna discuss about three uh different directions uh the one is called rebalancing this is the main focus of today's talk the second will be a little bit about routing uh in some specific cases of graphs and a specific business model and the third the last work i want to talk about if there is time is about um game theoretic analysis of the primitive of a payment channel so um the first problem that payment channels have is liquidity and the reason is we look that we lock the money in the channel for a very long period of

time and this money cannot be used anywhere else so uh in payment channels it is very often the channels are depleted and if the channel is depleted depleted means that one edge of the channel has not enough coins we need to top up the channel and this typically is done by going on the blockchain now there for the to avoid this there was a solution proposed that is uh to rebalance uh channels in a cycle and this can be done off-chain let me be more specific imagine we have that graph and uh by you see the notes and you see that the channels are

you can see the capacities of the channels in both sides and with red you can see what ideally the parties would want in a channel so for instance in the channel between a and d uh now a owns six coins and they owns zero coins but they would like to have a more balanced let's say distribution so they would say i would prefer to have three and three now if we have all these preferences then we can find if there are cycles where we can move all together atomically the money along the channels as i said before the money cannot jump from channel to channel but what can happen is that we can find the minimum amount let's say two for which i

a will move the money to d d to b bit way and that will create a more balanced um payment network now it is important that of course no user loses money and in what we mean about losing money is that the amount the sum of the coins each vertex has remains the same so for instance a node a in the beginning had 13 coins six six and one and at the end again has four three and six which is again thirteen uh is this is it clear the idea of rebalancing great okay so there is an easy way to model this

problem and that is that we assume that the users know how much they want to rebalance and from that we can create a directed graph where the edge capacities now represent the amount the maximum amount you want to balance your channel for and in that graph now we just need to find circulations which are flows with a zero net flow for each vertex there are two solutions uh prior solutions to our work that do that the first one is what is implemented in lightning and is it works locally so it's a local peer-to-peer search for a cycle and that means that if somebody wants to

uh do rebalancing they start and they search if there is a cycle to do so that is actually uh very computationally um this is very slow so the advantage is that it is lightweight and asynchronous every person can do it on their own they don't need any coordination whatsoever but the problem is that during the time that you search to find such a rebalancing cycle the balances of the channels because it is very slow um may change because the some of the in between channels they may actually do some transactions or do another balancing so what you thought that the cycle existed at the moment might fail

and of course yes did you specify sort of like the goal should be that for every single channel that they get closer together when you do this operation or there's some measure that says this graph is more balanced than that graph or like is there a clear specification for what the objective is no so uh the thing is um the what we can say is that we want to do as much as possible like the maximum flow right this is the optimal for us but what is balanced it depends on the two users because for someone balance maybe you have 10 and you have 100 because the a node sends more money typically to b uh for another one maybe 50 50 so we

don't know it's yeah this is why we say we ask the users what they want to rebalance for and then we create the graph so the idea is that like every every user would say i like this better than this and if all the users in the cycle will say like it's better than this yes yes yes yes it's not exactly user because it's more like a channel the two people have to agree in the channel but yes the idea is everybody submits their wants and uh if the wants match or the minimum amount for which the match can be can be rebalanced so yes exactly

so that goes to the second work because um i told you what is this the first main thing for the local search is that it's not optimal also so um arthur gerves three years ago proposed revive which is an opt-in protocol and they modeled the problem as a linear program and the the optimization is simple we have the capacities which are the amount that we want to rebalance we want the flows uh that maximize the sum of lows let's say we want to maximize the amount of flows through the network we have to respect the capacities and every edge and we need to preserve uh the flow on every vertex that's it the problem with this work is that i'll

explain first how a high level so the idea was you somehow select a delegate and then this delegate gets all the constraints from every user computes the resolution returns it to the users then the users verify it's a correct solution and they agree to execute it or not and if they all agree then they do an atomic execution across the whole network sorry that's another question about this so the capacities are the actual capacities of the channels their capacities are input by the channel they're input assuming that the utilities for each

edge for each pair of nodes is like linear in how much you could say that yes i mean the assumption is yes it is an underlying assumption yes i would say so because you want to maximize the flow if it was not if it was not linear it would be a different function i guess because it would be for instance more important to have one channel that is more full to the balancing request or a lot of channels that are all of them a little bit so yes it is an underlying assumption uh so the main disadvantages of the problem is first of all you have a lack of privacy completely because you have just one delegate the delegate gets every information and then it returns the

whole solution so everybody sees everything pretty much the second is you have no robustness and that is because as i said when you every user gets back the solution they can choose or not to take part in the execution then if one party one player disagrees and doesn't want to go through with it the whole solution is um unimplementable let's say you can execute it and the third is minor uh but it's it has it requires smart contracts so it's not compatible with bitcoin so in a work that we presented this year on financial crypto called hide and seek we try to solve exactly these problems

so the properties that we wanted was to have an opt-in protocol that is applicable on bitcoin and has four major properties the first one is security by balance conservation we mean that no node loses money the second is privacy so we wanted um the users to know exactly what they would need to know to execute an htc so if you're in a cycle your predecessor your successor and the amount that's it any further information should not be revealed by the protocol the of course we wanted to maintain optimality uh so we wanted to maximize again the the flow that goes through the

rebalancing protocol and we wanted to increase robustness and by that we mean if have some fault tolerance if some person doesn't want to participate to not break down the whole execution now a high level description of our protocol is as follows we have two phases the first one is exploration phase and the second execution the exploration phase we again formulate the problem as a linear program a mean cost flow problem actually and then what we do is we um we select k uh nodes at random using for instance um cryptographic sortation it's not important it's adaptable how you choose a node

and then every user secret shares their constraints to this k node then this k nodes run a multi-part computation protocol and it returned later to the users the result that are only only relevant the flows that are relevant for them only during the execution phase uh the execution phase uh is done with basic htlc and the reason we can use hclcs is that because before we um execute the solution we decompose it to assign consistent cycles what do i mean about for with that um i mean that if we have for instance um

the normal solution that for instance revive would return would be uh the sum of the blue and the and the red cycle so it would 10 10 a horizontal four six six but what we do is we break uh the the flow in same consistent cycles such that we increase the robustness so for instance if the the node c decides to not participate that does not affect what happens in uh in the red cycle right it only affects what happens in the blue cycle so our goal is to create as many uh possible as many cycles as possible now the other advantage is that um we need we need the the cycles to be

sign consistent because if they're not so in this example the the node may have incentive to sign uh the one htlc go in one direction but not the other one because it goes against the rebalancing request that the node asked for so uh but this can be done it's it's an algorithm that already exists so yeah just use this it's called conformal decomposition okay and the last um important thing to note is that um mpc generally is a very heavy tool uh but in our case uh we believe we have not run simulations

that it is it can run in a few minutes and the main reasons are uh first the number of delegates that can be very small like three four um and as long as we have one correct then we have private one honest we have privacy and correctness the second is we don't use genetical p but we use a mean cost flow uh formulation which apparently is faster and the last one is that the structure of our problem guarantees that we have an integer solution which means that we use an integer arithmetic not floating point arithmetic so comparing that to the revive thing uh they don't have npcs [Music]

but maybe they do have the energy solution property i would guess and i would think they would also have the conformal decomposition property they don't or i think you couldn't do it i mean that's sort of engineering yes you could do it because what we did is essentially to revive and try to fix the problems one by one so yes if you uh apply our algorithms to revive you'll end up with a hide and seek yeah so there's some parts that you said it's revived and it's good and you also have it it's still good and there's other parts that they didn't have and now you do that yes that's it yes revive had the optimity now you have

privacy and robustness and i don't remember the third point but yeah now um i would like to talk about an ongoing work that's happening uh is building on top of hide and seek it's with some of the co-authors of hide and seek and that is uh more directed to the people that uh work on auctions here i would be happy to have some input because we're stuck so um naturally uh when you do this balancing you think first to involve the participants that want to rebalance but uh since the fees in lightning for instance are very low it could be that most of the people that want to

rebalance would be willing to pay a very low fee to the people that are intermediaries right so the same way that the transaction can go through and the intermediary asks for a fee the same way the intermediary can enable a rebalancing cycle and that is probably much less uh costly compared to actually going on chain and topping up the channel so now this creates a new a new question we have the service providers that are willing to get some money by enabling the people to rebalance and we have the people that want to rebalance and are willing to give some money for this purpose so essentially what we have is users that submit bids that are positive these are the buyers

so the people that want to rebalance and some that have negative bids which are the sellers that want to get money for this purpose now we have an optimality shift so before we wanted to maximize the flow now we want to maximize the social welfare and we end up with a mechanism design problem so the questions we want to answer is how to make the users submit their bids truthfully and to do so we need to answer how do we price the cycles so what was the semantics the semantics for big yeah uh it's okay it depends on which model but the simplest would be i would hope to do one unit of rebalancing for 0.1 unit of um uh payment

even even simpler just like either or like either either do this specifically balance something or don't do it nothing that's kind of two i would say it's more like a no a double auction i would say like i'm willing to give up to that amount of money you're you want at least that amount of money so from the intermediaries yes [Music] it's like the intermediary yes it can be

imagine it like an edge yes i mean it is a vertex it is a node but um the node is using a specific channel if that node sends the money so he's losing capital on his side he's the only one getting a fee the other one is gaining he doesn't need a fee so that's the idea so yes it is an edge so where the sender is only getting the fee that's the generally the idea of providing a service and asking for a routing fee so so so we should think about like each node is like getting paid interest on whatever capital they have and so you're saying basically the

more stuff comes to you you're also getting paid off just sort of in the form of additional interest yeah yeah you're paying the opportunity cost of being able to send that money for someone else for instance or doing something for their own good so typically what the the fees in lightning is one satoshi plus zero point zero zero zero zero thirty three percent uh times the value so it's a basically plus uh a constant times the value um so in this uh auction pretty much what are the properties that we want ideally

we want optimality of course which is called economic efficiency we want incentive compatibility so we want the users to truthfully tell us their bids we want rationality which means um we should never charge the players more than the bids and we finally want strongly budget balance and that is what creates the most problems problems for us so we want the zero net flow to maintain for every vertex and that is important because at the moment at least i'm not aware of a way to burn money in a channel so due to the construction the primitive construction of payment channels we cannot have a weekly budget balance and we know

that these four properties are impossible so now we go and see what we can do now the first idea of course yes [Music] uh okay let's ignore the face yeah yeah typically yes you have to transmit the whole thing with the face yes but the fees are very small in comparison typically to the to the whole value yeah but yes you have to transfer the fees around the cycle for instance if you yes but in that aspect we are not we

don't require a zero net flow because i mean you have to take into account what is paid yeah formally yes uh and actually it's a we want a property that's stronger even than that because that in a graph strongly budget balance would mean that a vertex that can have like three edges you want them these three edges to sum to zero if we use the scientist decomposition um the the cycle decomposition we want cyclically strongly budget balance we want every single cycle to sum up to zero now the first idea of course was to use first price auction uh in the sense that we price someone their bid minus the social welfare divided by the number of

yeah so uh what are their [Music] what is um i would say what you uh what you rebalance minus what you pay so it's a linear function in half so you have some ideal like in the previous world i would have submitted five and now my utility is again okay let me think so um

[Music] yeah right then it's then my utility was like 10 times five thirds or sorry ten times three-fifths yeah i would say ten times ten times three fifths yes yes and it is linear yes the function is linear uh so here for instance what did we do we we took the bids and we uh priced the people

with the uh the bid minus what they gained the social welfare divided by the number of the participants so we had the same problem as first price auctions pretty much which is if you want to be included you are motivated to over bid but if you have the solution you want to under bid because you pay less there's no incentive compatibility [Music] but after doing this you can charge

people whatever you want for the solution like if for some reason this solution is very valuable to me you would definitely charge me a whole bitcoin or something um so what the way to find the solution we have no problem because then you can use differential privacy we i mean the problem we end up having is always pricing the one cycle like you have done you have a solution you have the decomposition and then you have this situation where people have submitted this for instance these are the bids how do we price it we do not have a way to do that incentive compatible and maintaining the zero net flow around removing the fees yeah

this is the problem i think i'm confused how do you charge prices it depends on which solution in any solute like how what are the mechanics by which you charge prices this is exactly what we're trying to solve so um given the the bits right for instance in the first solution as i said we uh we use the beats minus uh the social worker divided by the number of participants here we run the problem multiple times for instance we removed some participants some cycles broke down we solved the problem again then we saw how much was beneficial to typical vcg how do i pay like if everything has to

be strongly balanced then my payment is always zero in payment channels you can send more i mean it doesn't need to be the rebalancing need to be zero flow the fees that you send are whatever you want as long as there is slack the slack also we assume it exists because that is also something that is a hidden assumption we assume that we have the space the capacity in the real channel to send these fees around but typically they're very low that's

why we assume that so yeah in any in any solution that we tried we ended up always having that problem and we don't know how to solve that problem no just what is this so these are the bids so um let's say unit flow okay and a to d says i'm willing to pay up to 10 to do that unit flow then one then one then minus one how do we divide that such that the people will truthfully tell us the bids and the the flow will be also zero net yeah so can you go back to your list of

properties yes yes i mean really what really drives the impossibility here is one and four um so i mean like truthfulness like and so it's just really at equilibrium you're not going to get welfare optimality budget balance i mean that's kind of a very robust fundamental hospitality result so i mean it's going to relax something and have i mean one of those two has to be relaxed for anything to be possible i think so i think that's the question how which one how much because well so it depends which one it sounds like your application may insist that four cannot be relaxed in which case the

only question in some sense is you know minimize the welfare loss so get to all the rest if you can find easily how to manipulate the price to gain more or less but you really care about the outcome or you don't really care about the manipulation so much like you just care about that equilibrium again it's convenient if it's like very straightforward to figure out how to participate but if you had a i mean like first price options are not truthful they're actually very useful right they still do good things right so even if you have like a non-truthful that had equilibrium had doubted welfare loss for example

i'm really not an expert on this topic trying to understand most of the things while we're writing this now i will move on to routing problems um so the first uh the first paper this is uh wiser i will explain a bit so it's motivated by uh noticing a behavior in uh in payment channel networks where wealthy participants create multiple channels they are charging fees to route transactions so this is a way to gain money um so we assume we have a business model where we have payment hubs and these payment hubs are connected to clients so the clients they're not connected any

other way with each other just through the hubs much like banks so that structure of course is very beneficial because you have a high and reliable transaction throughput but it has some problems again the first one is that you are bound again by the liquidity of the hubs so that is uh the bottleneck for the transaction throughput then you have the feast you have to pay in the hubs uh that ideally at the moment would be uh proportional to the amount you're sending we would like to reduce that and the third is that you have no privacy for the users so in our new work just got accepted at ift we propose a solution that's called wiser

that comes from transferwise and we we try to use transaction aggregation to solve these three problems so the first one is we want to increase the transaction throughput as much as possible the second is we want to reduce the fees that the clients pay to the hubs and the third is to enhance the privacy of transactions i mean all of these properties are done are achieved optimistically in very weird edge cases you may have zero improvement to doing classic transactions and by classic transaction i mean to do transactions sequentially so the main idea for transaction aggregation is that instead of doing every

transaction in the payment hub like here uh one by one when they come you wait for a period of time and then you aggregate all the transactions and you execute them atomically um to see the benefit of transaction aggregation um you i will explain the two examples because it's dual the first part is that transaction aggregation allows uh transactions to happen that in the normal uh payment network sequentially they wouldn't be able to happen now assume that you have uh three transactions uh one from v1 to v3 for 10 coins another one similar v1 to v3 for 10 coins and a transaction from b4 to v6

again for 10 coins in that payment network where you can see um the the balances that are denoted by the number and where there is none is zero this is not possible uh because there is no capacity of ten in each of these uh paths but if you aggregate the transactions what you notice is that the first or the second is the same and the third transaction are possible why because when you see the problem in the transaction aggregation you can consider the following what you really want is v1 to send 10 coins and v3 to receive 10 coins don't really care to route it through the network then you want v6 to

receive 10 coins and before to send 10 coins so what you can do is essentially the same idea as transferwise does you can send from b1 to v6 and from b4 to v3 where you have the availability and just make sure that these two things happen atomically and that is that demonstrates mostly what is the gain from this uh from transaction aggregation the other part that we gain is uh that we can use some canceling out effects and that effectively reduces the fees a lot for instance in the graph uh the other the right left the left graph you can see um in the bottom that has a transaction vector and it says okay that v3 wants to send five coins to v5

and then v5 to points to uh v3 if you do it sequentially you would do two transactions and you would pay seven uh coins in total for transaction fees if you aggregate them because they cancel out each other you just send one transaction for three coins from b3 to v5 and then the fee that goes proportionally to the amount that you send is reduced more than half so uh i think these are the most um important examples what we have open and what is very interesting and why that doesn't do it is that theoretically you could have a transaction vector that says v3 sends 20 to

v5 and then v5 since 12 to v3 and that in principle is feasible because they cancel out to 8. however we have in our protocol this is not visible we have constrained it so that is open at the moment um this problem is also present in finance uh it's called netting in the interbanking settlements and it's a notion of the centralized transfer y system can you go to that right all right i actually follow the example so for the what yeah for this diagram we said v1 wants to play v3 five uh in the beginning though i said um

five coins from three to five and two coins from five to three so they cancel out five minus uh two coins is three by going through d5 yes so you can sit here like this is v3 the third position sends five coins to the last position which is v5 and then again v3 receives from v52 so it's just going from three to five and five to three they cancel out if you aggregate them so what is the bottleneck for the payments what do you mean no so what was the transaction that was impossible before but it's possible now with aggregation like what is this ah that is here yes so what was impossible what was

impossible is to send 10 coins from v1 to v3 and then 10 coins from v4 to v6 this is not visible in this network because you don't have the capacities but if you take that between uh the borrower i guess it's the four four four four yes this is the maximum you can send yes it's the one to show that it is visible to the transactions that you couldn't before the other is you see there can be a canceling out that reduces fees

so we want to really want to exchange 10 coins but the bottleneck is four so how is the aggregation solving okay so the way you can look at it is that v1 must send 10 coins v3 must receive 10 coins equivalently v6 must receive 10 coins and v for send then so what you can do is have v1 sent it to v6 and then before sent it to v3 and do that atomically and you guarantee that everybody has done what they should although the paths do not allow so and this is interesting because you can have even disconnected graphs doing it yeah so the aggregation part is just that you're taking two separate transactions and doing that together yes and not even two it's multiple yes that's the main idea you wait for time

and you take all these transactions and you cancel out all the the effects and then you have transaction throughput that is higher because more flow is feasible in that way okay the bottleneck for the right diagram is that in our solution we use a check at some point uh that the individual amounts are below the capacity of the channel and we use it in the solution in the in the the algorithmic problem solution uh and that forbids something that should be feasible which would be if v if

node 5 wants to send to node 3 20 and the node 3 wants to send to 5 12. the canceling out is 8 it's below the capacity of the channel that should be pretty visible but we need it for other purposes so yeah that's why it's kind of open again the high level idea is that we have accumulation of transactions we solve the transaction aggregation problem we get the resulting flow we check that the flow is correct and then we execute it how do we do that similarly to before we select some nodes from the hubs that have they're online and they have high computational power that we secret share we solve the problem again with npc

and the interesting part here is that the problem generically is uh hard for transaction aggregation in a generic network but due to our structure uh we use a fixed parameter and linear uh algorithm that runs linear to the number of constraints and exponential to the number of hubs that we select um for the execution we need to have atomic execution not like the previous work but like revive so to do so it's not that easy but there is fortunately a work we can use it's called thora very recent paper also that make sure that we can do that the gains that we have is that we have computational visibility for a problem that is generally not visible

no user loses money we have maximal throughput we are cost efficient in the sense that we reduce the fees as much as much as possible and uh we are private and we show that by the defining and indistinguishability gain sorry fixed parameter linear fixed parameter algorithm linear to the yeah for it it's linear to the users for us to the clients let's say who it's the number of hubs that we select

yes for future work we would be interested if of course we can have a more generic graph as i said it's an mp hard problem but this doesn't um say that we cannot have an approximation algorithm that is good enough so this is open at the moment we haven't even started working on it now i will very briefly uh go through the the high level of what we did in this two last work because i'm running out of time um now the main idea for this paper is that we wanted to uh find how to find routes in a payment channel network where we don't know the topology and our motivation was taproot so in bitcoin so far if you

had a channel opened everybody could see the creation of the channel but after tapper that is not true so that means that we can have a private network completely if the users don't want to say that they have a channel so that makes routing much harder which was anyway hard before and we wanted to have something that is private so it doesn't leak a lot of the topology uh that is efficient and of course that's optimal in the sense that we find the cheapest route the very very very high level idea is that we have both the sender and the receiver propagate information encrypted messages in the network and we use bi-linear maps in a way that we can have the intermediaries connect

the messages if they receive the same the message that is from the same resender and receiver and that intermediary can then drop back backwards propagate the path discovery to the sender and receiver and they can stop the propagation of the message that is very high level we want the first phase the the first propagation phase to be quite slow so the rest can effectively stop it from happening later and we assume that the other set is passive and that we we demand that the nodes propagate the messages with a delay that's proportional to the fees so we can find the cheapest path first that's a high

level idea we have open problems such as how to quantify privacy leakage because if the adversary is positioned close to the sender and close to the receiver so gets the message from two sides they can infer a lot of information about the topology in here you can do it in topology hiding manner using mpc but that is out of the question for practicality reasons here and of course there is an efficiency optimality and privacy tradeoff that has to do with how much you load the network with communication so to how many people you send the message so if you send it to every one of your neighbors you find a solution that is optimal but if you send it to one of your neighbors we measure that you on average find the twice the worst solution

and all of this uh space in between is open and for the last part um uh this work was also uh published in financial crypto this year and it has to do with a primitive construction of payment channels as you remember i said in the beginning that if alice commits fraud she can publish a commitment transaction that sold and then bob creates this challenge and goes on chain and says to the miners give me the money because i was cheated that would be true if the miners are willing to include the revocation transaction which is the one that gives the money to bob but alice in that case can actually

bribe the miners to not do so so what she does is she creates a transaction that says if you don't include the revocation after my timeout expires i will give you this amount of money and that creates a game so the miner at every time step at every block generation has to decide between introducing including the transaction from bob that gives him a fee that is small or wait for a specific period of time and include the transaction of files that gives them a higher fee and we studied when this is a nash equilibrium and we set the parameter space we propose a solution where you bob can counter bribe pretty much and for which amount bob the channel is still secure because

bob has the slack to counter bribe and we end it up with um two specific cases but the space in between is again uh um open so for for a very small bribes or very large bribes we have a solution but uh for um very close bro the bribing of one and the other being very close we don't know what happens is if alice is herself a minor is it like with the game change and sensitive alice kind of convinces bob to put a large bride to the miners alice just

gets separate because she resolves the miner yes it changes and also changes another like in a specific for the case that we discussed not really but for the space in between which is the most profitable to happen it actually changes because you can do other type of attacks if you have mining power like feather forking you can like say okay i'm not going to mine on top of that if you include the revocation transaction and there are papers that show that this is actually a good attack but miners will not mine the revocations stuff like this so yes this is not studied at all there is a yeah parameter space where you're saying that the channel actually is secure yeah

so um actually the channel is not secure this is what we find uh we say that if the bribe is as you see ignore the f the f is essentially the unrelated transaction phase so we don't care so if the bribe is greater than the fee of the revocation transaction divided by the computational power of the weakest mining pool is when you should always uh wait for the uh to get alice's bribe pretty much then obviously if you have the fee of the revocation higher than the bribe so the counter bribe higher than the bribe you're fine so like this

well our solution for the lightning for instance was very simple we said okay calculate the uh in the last date how much money you had eight what's the total money you can get if the revocation is included 15. so you can bribe for seven is that greater or less than what alice did that you know the security of your channel pretty much when you sign a transaction if that is incentive compatible if um alice could get a second bike being honest and she's trying to cheat together then alice is losing the seven and so that creates some spread where it's possible for me that i actually have an

advantage over her and sometimes even if she's the minor receiving the bride they'd still be not good for her with this i conclude my presentation so feel free to ask any other questions you want [Applause]