René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2019-12-23 📝 Original message: Dear fellow Lightning ...
📅 Original date posted:2019-12-23
📝 Original message:
Dear fellow Lightning Developers,
today my research paper (together with Mariusz Nowostawski) "*Imbalance
measure and proactive channel rebalancing algorithm for the Lightning
Network*" was published on arxiv: https://arxiv.org/abs/1912.09555 The
LaTeX project as well as the code for the experiments (simulation and
evaluation) are open source (however not too well documented yet) at:
https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network
I am open for questions, feedback, discussions and in particular critical
remarks. Let me just state that I was quite surprised about the positive
impact of implementing such a rebalancing protocol in particular since in
its current form it seems to protect the privacy of nodes (more research
would be needed to be sure that the privacy is really protected).
# From the abstract:
*We further show that the success rate of a single unit payment increases
from 11.2% on the imbalanced network to 98.3% in the balanced network.
Similarly, the median possible payment size across all pairs of
participants increases from 0 to 0.5 mBTC for initial routing attempts on
the cheapest possible path. We provide an empirical evidence that routing
fees should be dropped for proactive rebalancing operations. Executing 4
different strategies for selecting rebalancing cycles lead to similar
results indicating that a collaborative approach within the friend of a
friend network might be preferable from a practical point of view*
# Some thoughts and context:
Already in my proposal of JIT Routing
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-March/001891.html
I suggested to allow for fee free rebalancing and do the rebalancing
operations in the friend of a friend network. With this research I tested
both assumptions and - unless someone points out methodological errors in
my evaluation - we now have strong evidence that this in deed makes a lot
of sense. I think it is in particular interesting that 0.5 mBTC can be
routed successfully on first attempt in 50% of the cases. I guess using
this together with Multi part / path payments as discussed in the future
work section of the paper might be the way to go for the lightning network.
I envision that while payments along several paths are routed and settled
nodes could already rebalance their channels in particular if we introduce
the redundancy to multi part / path payments as suggested in the Boomerang
Paper https://arxiv.org/abs/1910.01834 by Vivek Bagaria, Joachim Neu and
David Tse.
# Roadmap for BOLT 14 (Fee free Rebalancing Transport):
If no strong objections exist I would try to extend the BOLTs with the
following to be able to implement the rebalancing algorithm across the
network (as with JIT routing nodes can already opt to implement the
algorithm for themselves but this is probably not to useful from an
economic point of view).
* BOLT 07: a new gossip query and reply `query_want_rebalance_channel_ids`
/ `reply_want_rebalance_channel_ids` to ask channel partners on which of
their channels they want inbound / outbound liquidity. The query could
already include an optional offer how much the node initiating the
rebalancing operation is willing to offer while the reply could have an
optional offer field stating how much they nodes are willing to rebalance
(as the paper shows nodes might not have consensus about the amount and the
algorithm currently works by agreeing on the lowest value). Of course this
extension needs some protection against probing attacks to protect the
privacy of nodes.
* BOLT 14: (Fee Free Rebalancing Transport) While it seems tempting to
Reuse BOLT04 with a different realm that omits fees for the rebalancing
cycles (which nodes would have to accept then) this seems impossible as the
onions are not public and nodes could not verify that this is really a
rebalancing operation and not a payment which tries to "steel" fees. While
we might be able to extend BOLT 02 with a new message that transports a
"rebalancing" onion together with the keys for every envelop so that
everyone can verify that in fact this fee free onion is a rebalancing cycle
it seems plausible to have an open tansport for fee free rebalancing to
start with. We could also make it a feature flag and allow nodes to signal
if they support fee free rebalancing. I guess for backwards compatebility
this should be done in any case.
* One problem / attack vector with circular fee free payments that I see is
that if Alice wants to pay David she could initiate a rebalancing onion: A
--> B --> C --> D --> A with the paymenthash that David has created in an
invoice. David would just not set up the final HTLC from him to Alice as he
wanted to receive money from Alice. As far as I see this attack would only
be possible if Alice and David have a channel which they could have used
for the payment right away. Not using that channel is effectively a
rebalancing operation which is exactly why we allow such a protocol. This
means that the channel between Alice and David has to be public to allow
for a fee free operation. Otherwhise I could always claim to have a private
channel if I wanted to pay someone without fees.
Still this allows two people who have a public channel to spam out HTLCs
which settle at no cost. However - according to my research - nodes along
the cycle only participate if that was beneficial for them. Also since
these rebalancing cycles are open and transparent they could be blocked if
nodes feel they are being abused.
While the extension of BOLT 07 seems rather simple and straight forward.
BOLT 14 (I like the fact, that it is actually 4 + 10 ) might be more
controversial. Especially for that I would love to have some feedback
before I start to spec this out.
Have good Christmas time everyone!
--
https://www.rene-pickhardt.de
Skype: rene.pickhardt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20191223/595b5f67/attachment.html>;
📝 Original message:
Dear fellow Lightning Developers,
today my research paper (together with Mariusz Nowostawski) "*Imbalance
measure and proactive channel rebalancing algorithm for the Lightning
Network*" was published on arxiv: https://arxiv.org/abs/1912.09555 The
LaTeX project as well as the code for the experiments (simulation and
evaluation) are open source (however not too well documented yet) at:
https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network
I am open for questions, feedback, discussions and in particular critical
remarks. Let me just state that I was quite surprised about the positive
impact of implementing such a rebalancing protocol in particular since in
its current form it seems to protect the privacy of nodes (more research
would be needed to be sure that the privacy is really protected).
# From the abstract:
*We further show that the success rate of a single unit payment increases
from 11.2% on the imbalanced network to 98.3% in the balanced network.
Similarly, the median possible payment size across all pairs of
participants increases from 0 to 0.5 mBTC for initial routing attempts on
the cheapest possible path. We provide an empirical evidence that routing
fees should be dropped for proactive rebalancing operations. Executing 4
different strategies for selecting rebalancing cycles lead to similar
results indicating that a collaborative approach within the friend of a
friend network might be preferable from a practical point of view*
# Some thoughts and context:
Already in my proposal of JIT Routing
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-March/001891.html
I suggested to allow for fee free rebalancing and do the rebalancing
operations in the friend of a friend network. With this research I tested
both assumptions and - unless someone points out methodological errors in
my evaluation - we now have strong evidence that this in deed makes a lot
of sense. I think it is in particular interesting that 0.5 mBTC can be
routed successfully on first attempt in 50% of the cases. I guess using
this together with Multi part / path payments as discussed in the future
work section of the paper might be the way to go for the lightning network.
I envision that while payments along several paths are routed and settled
nodes could already rebalance their channels in particular if we introduce
the redundancy to multi part / path payments as suggested in the Boomerang
Paper https://arxiv.org/abs/1910.01834 by Vivek Bagaria, Joachim Neu and
David Tse.
# Roadmap for BOLT 14 (Fee free Rebalancing Transport):
If no strong objections exist I would try to extend the BOLTs with the
following to be able to implement the rebalancing algorithm across the
network (as with JIT routing nodes can already opt to implement the
algorithm for themselves but this is probably not to useful from an
economic point of view).
* BOLT 07: a new gossip query and reply `query_want_rebalance_channel_ids`
/ `reply_want_rebalance_channel_ids` to ask channel partners on which of
their channels they want inbound / outbound liquidity. The query could
already include an optional offer how much the node initiating the
rebalancing operation is willing to offer while the reply could have an
optional offer field stating how much they nodes are willing to rebalance
(as the paper shows nodes might not have consensus about the amount and the
algorithm currently works by agreeing on the lowest value). Of course this
extension needs some protection against probing attacks to protect the
privacy of nodes.
* BOLT 14: (Fee Free Rebalancing Transport) While it seems tempting to
Reuse BOLT04 with a different realm that omits fees for the rebalancing
cycles (which nodes would have to accept then) this seems impossible as the
onions are not public and nodes could not verify that this is really a
rebalancing operation and not a payment which tries to "steel" fees. While
we might be able to extend BOLT 02 with a new message that transports a
"rebalancing" onion together with the keys for every envelop so that
everyone can verify that in fact this fee free onion is a rebalancing cycle
it seems plausible to have an open tansport for fee free rebalancing to
start with. We could also make it a feature flag and allow nodes to signal
if they support fee free rebalancing. I guess for backwards compatebility
this should be done in any case.
* One problem / attack vector with circular fee free payments that I see is
that if Alice wants to pay David she could initiate a rebalancing onion: A
--> B --> C --> D --> A with the paymenthash that David has created in an
invoice. David would just not set up the final HTLC from him to Alice as he
wanted to receive money from Alice. As far as I see this attack would only
be possible if Alice and David have a channel which they could have used
for the payment right away. Not using that channel is effectively a
rebalancing operation which is exactly why we allow such a protocol. This
means that the channel between Alice and David has to be public to allow
for a fee free operation. Otherwhise I could always claim to have a private
channel if I wanted to pay someone without fees.
Still this allows two people who have a public channel to spam out HTLCs
which settle at no cost. However - according to my research - nodes along
the cycle only participate if that was beneficial for them. Also since
these rebalancing cycles are open and transparent they could be blocked if
nodes feel they are being abused.
While the extension of BOLT 07 seems rather simple and straight forward.
BOLT 14 (I like the fact, that it is actually 4 + 10 ) might be more
controversial. Especially for that I would love to have some feedback
before I start to spec this out.
Have good Christmas time everyone!
--
https://www.rene-pickhardt.de
Skype: rene.pickhardt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20191223/595b5f67/attachment.html>;