René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2019-03-05 📝 Original message: Hey everyone, In this ...
📅 Original date posted:2019-03-05
📝 Original message:
Hey everyone,
In this mail I introduce the Just in Time Routing schema (aka JIT Routing).
Its main idea is to mitigate the disadvantages from our current source
based routing (i.e.: guessing a route that will work in the sense that it
has enough liquidity in each channel) and make the routing process a little
bit more like the best effort routing that we know from IP-forwarding. As
far as I know this will not decrease the privacy of the nodes. As part of
this Routing scheme nodes need to be able to quickly rebalance their
channels. Thus in this mail I also propose a heuristic for doing this
efficiently which I have implemented and seems to provide pretty good
results. Obviously the heuristic should be tested with the help of a
simulation. I did not have the chance to do that yet. Partly also because I
am lacking a proper dataset and I don't want to do this on artificial data.
The advantages of JIT Routing are:
* it is possible to do now without any protocol modification. In particular
no modifications of the onions are necessary.
* routing nodes can already easily implement it. By implementing it they
will increase the routing success even for nodes which are running older
implementations
* it seems to be logically equivalent to AMP Routing. In particular its
properties will also help base AMP once it is part of the protocol.
* local channel balance information along the route can now be part of the
path finding process while not decreasing the privacy by sharing
information about channel balances with others. In fact the privacy of
nodes is even being increased.
The disadvantages seem:
* it might economically not be incentivized for a routing node in every
situation. Theoretically it can even happen that a node pays a fee in order
to use this technique but can't earn the routing fee as the onion fails
later. Nodes can implement risk management strategies to mitigate this
issue.
* The routing process might take a longer time as it starts sub routing
processes.
* While doing JIT routing the capacity for channels should be reserved even
before HTLCs are set up (to prevent hostile recursive chains of rebalancing
operations)
Obviously routing single big payments is a challenge for the lightning
network. During the developer summit in Adelaide we have agreed to put Base
AMP to BOLT 1.1. To review Base AMP the idea is basically after receiving a
payment hash to create several onions on various routes to the recipient.
While Base AMP in theory can find the maxflow / min cut and achieve maximum
liquidity it is not clear yet how well Base AMP will really work.
While it has been shown that smaller payments have a higher chance to be
routed successfully there is the downside that we have more payments which
increases the likelihood that any one of those payment eventually fails. As
far as I know there have not been any studies researching this fact. Also
the fact remains that Base AMP is still a source base routing protocol
putting the sender into a tough spot as it has to guess which routes might
work.
How to JIT Routing?
For the BOLTs we basically need one Recommendation (in fact even today
nodes can do this without this explicit recommendation, but I would suggest
to add the recommendation):
If a node cannot forward an incoming HTLC because the node has not enough
funds on the outgoing channel the node MAY pause the routing process and
try to rebalance the channel that misses liquidity. If it isn't able to
rebalance the channel it should fail the onion sending back an insufficient
wire funds error `temporary_channel_failure`
Let us consider the following Graph and situation for an example:
100 / 110 80 / 200
S ----------> B --------> R
\ /
80/200 \ / 100/200
\ /
T
Meaning we have the following channels:
S ---> B capacity: 110 A funds: 100 B funds: 10
B ---> R capacity: 200 B funds: 80 R funds: 120
B ---> T capacity: 200 B funds: 80 T funds: 120
T ---> R capacity: 200 T funds: 100 R funds: 100
Let us assume S wants to send a payment of 90 to R. With this distribution
of funds this will not work with a single route S ---> B ---> R as the
channel B--->R can only forward 78 (taking the channel reserve of 1% into
consideration)
Now with Base AMP after a protocol update this would be resolved by making
two onions forwarding for example 45 each. Also S would have to pay more
routing fees as the basefee of B will be charged twice.
Onion 1: S ---> B ---> R
Onion 2: S ---> B ---> T ---> R
However it is S again who has to guess how the problems with the liquidity
are it does not know how B has spread its funds between R and T (and
potentially other channels)
With the above recommendation in place B can create a different onion with
lets say moving 50 from the B---> T channel to the B ---> R channel
resulting in the following situation:
100 / 110 130 / 200
S ----------> B --------> R
\ /
30/200 \ / 50/200
\ /
T
Meaning we have the following channels:
S ---> B capacity: 110 A funds: 100 B funds: 10
B ---> R capacity: 200 B funds: 130 R funds: 70
B ---> T capacity: 200 B funds: 30 T funds: 170
T ---> R capacity: 200 T funds: 50 R funds: 150
Now B can easily pass the original onion with a value of 90 which was
designed for the route S ---> B ---> R
Obviously there can also be issues when B tries to rebalance their channels
as the attempted event of rebalancing might trigger another JIT operation
at another node (potentially making a later stage of the original onion
harder to be forwarded). Also B does not have full information about the
T---> R channel. Yet B has more information about B's neighbourhood than S
does as B knows which channels are liquid and how many paths exist between
the endpoints of those channels. This B should be able to make a more
educated decision as the originator node S. Since B would only do a
rebalancing if the routing fees for the rebalancing are cheaper than the
fees they collect (and other nodes would do the same) the risk for and
infinit cascade of rebalancing operations should be mitigated. Also the
total CLTV for the rebalancing operation should be smaller than the
original onion. A sender of the onion could obviously start with larger
cltv_deltas to allow routing nodes to have some buffer. This is also good
in the sense of shadow routing as described in the BOLTs.
Another problem that might arise is the question if the routing node is
able to quickly compute rebalancing paths. I have been working on a
c-lightning plugin for rebalancing over the weekend (it is actually when I
came up with the idea of JIT routing). Currently I use the following
promising heuristic for rebalancing:
I look at the friend of a friend network of the node that wants to
rebalance channels. This network consists of alle channel partners of the
node and their channels. This will in particular have all triangles and
rectangles of the lightning network that the node that wants to rebalance
is part of. Now I remove the node that wants to rebalance from the friend
of the friend network. The resulting graph should always stay pretty small.
In a regular small world network the friend of a friend graph consists of
roughly 10k nodes. In particular after pruning nodes with degree 1 (which
can't be used to rebalance on this subgraph) we have a pretty small
network. After extracting this subnetwork (which for general operation
could always be maintained while gossip messages are coming in) the
computation to suggest several hundred rebalancing cycles and even ordering
them by price takes less than 1 second on my machine.
So far I have been pretty successful finding several (cheap!) rebalancing
suggestions in this network from my lightning node (which has about 40
channels)
I will release the code for the rebalancing schema soon but I wanted to
have the idea already out in order to get more feedback while working on
this.
best Rene
--
https://www.rene-pickhardt.de
Skype: rene.pickhardt
mobile: +49 (0)176 5762 3618
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20190305/8ed84b9d/attachment.html>;
📝 Original message:
Hey everyone,
In this mail I introduce the Just in Time Routing schema (aka JIT Routing).
Its main idea is to mitigate the disadvantages from our current source
based routing (i.e.: guessing a route that will work in the sense that it
has enough liquidity in each channel) and make the routing process a little
bit more like the best effort routing that we know from IP-forwarding. As
far as I know this will not decrease the privacy of the nodes. As part of
this Routing scheme nodes need to be able to quickly rebalance their
channels. Thus in this mail I also propose a heuristic for doing this
efficiently which I have implemented and seems to provide pretty good
results. Obviously the heuristic should be tested with the help of a
simulation. I did not have the chance to do that yet. Partly also because I
am lacking a proper dataset and I don't want to do this on artificial data.
The advantages of JIT Routing are:
* it is possible to do now without any protocol modification. In particular
no modifications of the onions are necessary.
* routing nodes can already easily implement it. By implementing it they
will increase the routing success even for nodes which are running older
implementations
* it seems to be logically equivalent to AMP Routing. In particular its
properties will also help base AMP once it is part of the protocol.
* local channel balance information along the route can now be part of the
path finding process while not decreasing the privacy by sharing
information about channel balances with others. In fact the privacy of
nodes is even being increased.
The disadvantages seem:
* it might economically not be incentivized for a routing node in every
situation. Theoretically it can even happen that a node pays a fee in order
to use this technique but can't earn the routing fee as the onion fails
later. Nodes can implement risk management strategies to mitigate this
issue.
* The routing process might take a longer time as it starts sub routing
processes.
* While doing JIT routing the capacity for channels should be reserved even
before HTLCs are set up (to prevent hostile recursive chains of rebalancing
operations)
Obviously routing single big payments is a challenge for the lightning
network. During the developer summit in Adelaide we have agreed to put Base
AMP to BOLT 1.1. To review Base AMP the idea is basically after receiving a
payment hash to create several onions on various routes to the recipient.
While Base AMP in theory can find the maxflow / min cut and achieve maximum
liquidity it is not clear yet how well Base AMP will really work.
While it has been shown that smaller payments have a higher chance to be
routed successfully there is the downside that we have more payments which
increases the likelihood that any one of those payment eventually fails. As
far as I know there have not been any studies researching this fact. Also
the fact remains that Base AMP is still a source base routing protocol
putting the sender into a tough spot as it has to guess which routes might
work.
How to JIT Routing?
For the BOLTs we basically need one Recommendation (in fact even today
nodes can do this without this explicit recommendation, but I would suggest
to add the recommendation):
If a node cannot forward an incoming HTLC because the node has not enough
funds on the outgoing channel the node MAY pause the routing process and
try to rebalance the channel that misses liquidity. If it isn't able to
rebalance the channel it should fail the onion sending back an insufficient
wire funds error `temporary_channel_failure`
Let us consider the following Graph and situation for an example:
100 / 110 80 / 200
S ----------> B --------> R
\ /
80/200 \ / 100/200
\ /
T
Meaning we have the following channels:
S ---> B capacity: 110 A funds: 100 B funds: 10
B ---> R capacity: 200 B funds: 80 R funds: 120
B ---> T capacity: 200 B funds: 80 T funds: 120
T ---> R capacity: 200 T funds: 100 R funds: 100
Let us assume S wants to send a payment of 90 to R. With this distribution
of funds this will not work with a single route S ---> B ---> R as the
channel B--->R can only forward 78 (taking the channel reserve of 1% into
consideration)
Now with Base AMP after a protocol update this would be resolved by making
two onions forwarding for example 45 each. Also S would have to pay more
routing fees as the basefee of B will be charged twice.
Onion 1: S ---> B ---> R
Onion 2: S ---> B ---> T ---> R
However it is S again who has to guess how the problems with the liquidity
are it does not know how B has spread its funds between R and T (and
potentially other channels)
With the above recommendation in place B can create a different onion with
lets say moving 50 from the B---> T channel to the B ---> R channel
resulting in the following situation:
100 / 110 130 / 200
S ----------> B --------> R
\ /
30/200 \ / 50/200
\ /
T
Meaning we have the following channels:
S ---> B capacity: 110 A funds: 100 B funds: 10
B ---> R capacity: 200 B funds: 130 R funds: 70
B ---> T capacity: 200 B funds: 30 T funds: 170
T ---> R capacity: 200 T funds: 50 R funds: 150
Now B can easily pass the original onion with a value of 90 which was
designed for the route S ---> B ---> R
Obviously there can also be issues when B tries to rebalance their channels
as the attempted event of rebalancing might trigger another JIT operation
at another node (potentially making a later stage of the original onion
harder to be forwarded). Also B does not have full information about the
T---> R channel. Yet B has more information about B's neighbourhood than S
does as B knows which channels are liquid and how many paths exist between
the endpoints of those channels. This B should be able to make a more
educated decision as the originator node S. Since B would only do a
rebalancing if the routing fees for the rebalancing are cheaper than the
fees they collect (and other nodes would do the same) the risk for and
infinit cascade of rebalancing operations should be mitigated. Also the
total CLTV for the rebalancing operation should be smaller than the
original onion. A sender of the onion could obviously start with larger
cltv_deltas to allow routing nodes to have some buffer. This is also good
in the sense of shadow routing as described in the BOLTs.
Another problem that might arise is the question if the routing node is
able to quickly compute rebalancing paths. I have been working on a
c-lightning plugin for rebalancing over the weekend (it is actually when I
came up with the idea of JIT routing). Currently I use the following
promising heuristic for rebalancing:
I look at the friend of a friend network of the node that wants to
rebalance channels. This network consists of alle channel partners of the
node and their channels. This will in particular have all triangles and
rectangles of the lightning network that the node that wants to rebalance
is part of. Now I remove the node that wants to rebalance from the friend
of the friend network. The resulting graph should always stay pretty small.
In a regular small world network the friend of a friend graph consists of
roughly 10k nodes. In particular after pruning nodes with degree 1 (which
can't be used to rebalance on this subgraph) we have a pretty small
network. After extracting this subnetwork (which for general operation
could always be maintained while gossip messages are coming in) the
computation to suggest several hundred rebalancing cycles and even ordering
them by price takes less than 1 second on my machine.
So far I have been pretty successful finding several (cheap!) rebalancing
suggestions in this network from my lightning node (which has about 40
channels)
I will release the code for the rebalancing schema soon but I wanted to
have the idea already out in order to get more feedback while working on
this.
best Rene
--
https://www.rene-pickhardt.de
Skype: rene.pickhardt
mobile: +49 (0)176 5762 3618
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20190305/8ed84b9d/attachment.html>;