[Lightning-dev] Incremental Routing (Was: Making (some) channel limits dynamic)

Antoine Riard antoine.riard at gmail.com
Thu Oct 8 16:17:29 UTC 2020


Hi Zeeman,

> * It requires a lot more communication rounds and (symmetric, at least)
cryptographic operations.

At first sight, it sounds similar to HORNET/rendez-vous, at least in the
goal of achieving bidirectional communications.

* Intermediate nodes can guess the distance from the source by measuring
timing of a previous response to the next message from the payer.

Yes an intermediary node servicing also a message relay one can likely
learn a lot from message RTT timings _and_ CLTV/routed value...

Note, for the point raised about untrusted upfront payment, if your payment
path hops are stealing upfront, just consider this as a normal routing
failure and downgrade them in your routing algorithm. Thus incentivizing
them to behave well to keep their routing fees. Of course, assigning the
blame to the real faultive hop is likely hard without making onion errors
reliable but I think each hop would be incentivized to sign correctly its
failures and police its neighbouring peers for their laziness.

For sure, upfront payments need more grinding. But I think it will also
solve adjacent issues like your counterparty updating a channel for nothing
until you exhaust your watchtower update storage credit.

Best,
Antoine

Le mer. 7 oct. 2020 à 13:33, ZmnSCPxj <ZmnSCPxj at protonmail.com> a écrit :

> Good morning Antoine, Bastien, and list,
>
> > > Instead of relying on reputation, the other alternative is just to
> have an upfront payment system, where a relay node doesn't have to account
> for a HTLC issuer reputation to decide acceptance and can just forward a
> HTLC as long it paid enough. More, I think it's better to mitigate jamming
> with a fees-based system than a web-of-trust one, less burden on network
> newcomers.
> >
> > Let us consider some of the complications here.
> >
> > A newcomer wants to make an outgoing payment.
> > Speculatively, it connects to some existing nodes based on some policy.
> >
> > Now, since forwarding is upfront, the newcomer fears that the node it
> connected to might not even bother forwarding the payment, and instead just
> fail it and claim the upfront fees.
> >
> > In particular: how would the newcomer offer upfront fees to a node it is
> not directly channeled with?
> > In order to do that, we would have to offer the upfront fees for that
> node, to the node we are channeled with, so it can forward this as well.
> >
> > -   We can give the upfront fee outright to the first hop, and trust
> that if it forwards, it will also forward the upfront fee for the next hop.
> >     -   The first hop would then prefer to just fail the HTLC then and
> there and steal all the upfront fees.
> >         -   After all, the offerrer is a newcomer, and might be the
> sybil of a hacker that is trying to tie up its liquidity.
> >             The first hop would (1) avoid this risk and (2) earn more
> upfront fees because it does not forward those fees to later hops.
> >
> >     -   This is arguably custodial and not your keys not your coins
> applies.
> >         Thus, it returns us back to tr\*st anyway.
> >
> > -   We can require that the first hop prove where along the route
> errored.
> >     If it provably failed at a later hop, then the first hop can claim
> more as upfront fees, since it will forward the upfront fees to the later
> hop as well.
> >     -   This has to be enforcable onchain in case the channel gets
> dropped onchain.
> >         Is there a proposal SCRIPT which can enforce this?
> >
> >     -   If not enforcable onchain, then there may be onchain shenanigans
> possible and thus this solution might introduce an attack vector even as it
> fixes another.
> >         -   On the other hand, sub-satoshi amounts are not enforcable
> onchain too, and nobody cares, so...
>
> One thing I have been thinking about, but have not proposed seriously yet,
> would be "incremental routing".
>
> Basically, the route of pending HTLCs also doubles as an encrypted
> bidirectional tunnel.
>
> Let me first describe how I imagine this "incremental routing" would look
> like.
>
> First, you offer an HTLC with a direct peer.
> The data with this HTLC includes a point, which the peer will ECDH with
> its own privkey, to form a shared secret.
> You can then send additional messages to that node, which it will decrypt
> using the shared secret as the symmetric encryption key.
> The node can also reply to those messages, by encrypting it with the same
> symmetric encryption key.
> Typically this will be via a stream cipher which is XORed with the real
> data.
>
> One of the messages you can send to that node (your direct peer) would be
> "please send out an HTLC to this peer of yours".
> Together with that message, you could also bump up the value of the HTLC,
> and possibly the CLTV delta, you have with that node.
> This bumping up is the forwarding fee and resolution time you have to give
> to that node in order to have it safely put an HTLC to the next hop.
>
> If there is a problem on the next hop, the node replies back, saying it
> cannot forward the HTLC further.
> Your node can then respond by giving an alternative next hop, which that
> node can reply back is also not available, etc. until you say "give up" and
> that node will just fail the HTLC.
>
> However, suppose the next hop is online and there is enough space in the
> channel.
> That node then establishes the HTLC with the next hop.
>
> At this point, you can then send a message to the direct peer which is
> nothing more than "send the rest of this message as the message to the next
> hop on the same HTLC, then wait for a reply and wrap it and reply to me".
> This is effectively onion-wrapping the message to the peer of your peer,
> and waiting for an onion-wrapped reply from the peer of your peer.
>
> You can then talk to the peer of your peer (of your peer...) to
> incrementally build the rest of the route, until you reach the destination.
>
> How is this related to upfront payments?
> Well, in upfront payments, on the timelock branch, instead of the entire
> fund value returning to the offerer of the HTLC, part of the fund value is
> given forward to the next peer.
> For onchain enforcement the upfront payment is simply added to the miner
> fees, so at least the one offerring it does not have incentive to drop it
> onchain to play onchain shenanigans.
>
> Now, suppose your direct peer requires an upfront payment before it will
> even bother make an outgoing HTLC on the strength of your incoming one.
> So, you bump up your HTLC, and arrange to have the timelock branch give
> the upfront payment to the direct peer.
>
> Then, you can now ask the peer to open an HTLC to the next peer, on the
> basis of that upfront payment.
>
> Of course, if the peer of the peer is not the destination, you still have
> to increment further.
> You then bump up the upfront payment of the direct peer, with a message to
> offer an equivalent amount of upfront payment to the peer of the peer.
> Your direct peer can then pretend that communication with the peer of the
> peer failed, so it should get the bumped-up upfront payment, equivalent to
> the upfront payments of itself plus the next peer.
>
> However, at any one time, the upfront payment that can be stolen by your
> direct peer can only amount to the upfront fee of a single hop, the one
> that is being built out next in the incremental routing.
> This is because it has already offered the upfront payment to the next hop.
>
> Some numbers may make this easier to understand.
> For example, suppose all nodes require 1msat prepaid to send out to the
> next hop.
> At the start, you are just offering the HTLC amount with 0 msat in upfront
> payment.
> Then you increase the upfront payment by 1msat, then tell the direct peer
> to create an HTLC to the peer of the peer, of equal HTLC value, but with 0
> msats in upfront payment.
> Next, you increase the upfront payment to the direct peer to 2msat, then
> tell the direct peer to bump up the upfront payment of its outgoing HTLC by
> 1 msat as well.
>
> Then next, you increase the upfront payment to the direct peer to 3 msat.
> The direct peer is giving out 1 msat upfront payment to the outgoing HTLC,
> which it is now supposed to increase to 2msat.
> After doing that, it sends a message to the peer of the peer.
> The peer of the peer is giving out 0 msat upfront payment, which it is now
> supposed to increase to 1 msat.
> After doing that, it sends a message to the peer of the peer of the peer.
> The peer of the peer of the peer has no outgoing HTLC yet, but since it is
> now being offered 1msat in upfront fee, it is now wlling to be instructed
> to send out an outgoing HTLC to another channel.
>
> And so on.
>
> At any one time, an intermediate node can pretend communications to the
> next node in the route failed, and claim 2msat in upfront fee instead of
> 1msat.
> But it cannot steal more than the equivalent of the upfront fee of one
> node.
>
> (I elide the fact that in this scheme, you would *also* offer a fee
> conditional on the HTLC actually pushing through; sort of like a "pay half
> now, pay half later on completion" deal; your imagination can fill in the
> rest.)
>
> This is in contrast with upfront payments where you have to offer the
> upfront payment of all the nodes along the route to the direct peer.
> The direct peer can, then and there, claim the entire upfront payment
> earmarked for the entire route.
>
> A nice thing about incremental routing is that the time risk of your money
> being locked up can be managed a little easier.
> You can start with an HTLC with the minimum time, then also bump up the
> time of the first HTLC (with time bumps rippling out along the incremental
> route) as you build up the incremental route until you reach the
> destination.
>
> --
>
> Against incremental routing, however, is that:
>
> * It requires a lot more communication rounds and (symmetric, at least)
> cryptographic operations.
> * Intermediate nodes can guess the distance from the source by measuring
> timing of a previous response to the next message from the payer.
>   * In particular, current LN can allow an intermediate node to guess the
> distance to the destination of a payment (by CLTV delta bounds) but *not*
> the distance to the source of the payment, with incremental routing the
> distance to the source of the payment is guessable as well from message
> timings.
> * The idea is completely imaginary as of now with no peer review, and
> there may be actual cryptographic or practical problems with the idea.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20201008/b43f3096/attachment.html>


More information about the Lightning-dev mailing list