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

2020-10-08 Thread Antoine Riard
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  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 

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

2020-10-08 Thread Bastien TEINTURIER via Lightning-dev
If I remember correctly, it looks very similar to how I2P establishes
tunnels, it may be worth
diving in their documentation to fish for ideas.

However in their case the goal is to establish a long-lived tunnel, which
is why it's ok to have
a slow and costly protocol. It feels to me that for payments, this is a lot
of messages and delays,
I'm not sure this is feasible at a reasonable scale...

Cheers,
Bastien

Le mer. 7 oct. 2020 à 19:34, ZmnSCPxj via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> 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 

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

2020-10-07 Thread ZmnSCPxj via Lightning-dev
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