Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-04 Thread ZmnSCPxj via Lightning-dev
Good morning Christian,

First:

> Like mentioned above the entire job of trampolines is to provide base
> routing capability, and we should not make special provisions for myopic
> trampoline nodes, since routing is their entire reason for existence :-)

The point of providing this special provision is to increase the anonymity set 
of full-routemap nodes.

Suppose we were to require that myopic routing nodes fail if they are unable to 
see the next trampoline.
Then it becomes possible to profile the network and identify full-routemap vs. 
myopic routing nodes.
Myopic routing nodes are more likely to fail than full-routemap nodes.

In particular, full-routemap nodes are particularly juicy targets for attackers 
who wish to disrupt the Lightning Network once the LN grows in size.

This is even worse if we end up proposing that full-routemap nodes announce 
themselves as such on gossip.
Then attackers do not even need to profile the network; listening to gossip is 
enough to identify full-routemap targets to attack.

In a world where we allow myopic routing nodes to delegate instead of fail, 
then it becomes much harder for a third party to profile the network.
Myopic routing nodes would only have slightly higher failure rate than 
full-routemap nodes, possibly within the noise level, making it hard for third 
parties to definitely differentiate full-routemap nodes from myopic routing 
nodes.
Anonymity loves company, and the protection of the deity Anonymous is a 
tremendous boon in sustaining systems from attack and censure.

Another advantage of allowing myopic routing nodes to delegate is that it 
allows myopia to be a relative condition rather than a binary "either I know 
the whole routemap or not".
That is, I can have 90%, 75%, 50%, 25%, 10$, or 1% of the routemap, and still I 
can participate in supporting the network by at least helping route to those 
nodes that I can route to, or delegating to someone else who might know that 
part of the network better than I do.
This provides more graceful degradation of service than the binary 
"full-routemap or not" you propose.
In particular, as the LN grows, fewer and fewer nodes will be able to have a 
full routemap, and they will have larger and larger targets painted on their 
back as points of attack.

Another point:

> I think we should not try to recover from a node not finding the next
> hop in the trampoline, and rather expect trampolines to have reasonable
> uptime (required anyway) and have an up to date routing table

But with myopic trampoline nodes, the only requirement is high uptime; 
completeness of the routing table becomes unimportant.
This means that selecting good trampoline nodes only requires one desiderata 
(high uptime).
In particular, high uptime can be easily measured (just attempt to connect or 
ping), but completeness of routing table is not.

Then:

> (that's
> what we're paying them for after all).

This contradicts your position in the other sub-thread of this topic:

> This is not an issue. Like we discussed for the multi-part payments the HTLCs 
> still resolve correctly, though node B might chose to short circuit the 
> payment it'll also clear the HTLCs through E And D (by failing them instead 
> of settling them) but the overall payment remains atomic and end-to-end 
> secure. The skipped nodes (which may include the trampoline) may lose a bit 
> of fees, but that is not in any way different than a failed payment attempt 
> that is being retried from the sender :-)

In that case, E is a full-routemap node, while B may or may not be a 
full-routemap node, but B gets paid (more!) while E does not.
E took the effort to find a route while all B did was pass the onion to the 
next.
What gives?

But regardless ---
I would like to point out that it is still incentive-compatible to support 
myopic trampoline nodes, and that full-routemap nodes will be paid much more 
than a myopic trampoline node.

Suppose a trampoline node is a full-routemap node.
In exchange for the service of providing routes, it expects to be allocated a 
higher fee.
Then the routing fee of nodes between it and the next trampoline node are 
deducted from the fee allocated to it.
In particular, it will refuse to continue payment if it does not get a 
higher-than-normal fee for its own hop.
After all, it must be paid for this service, as you insist.

Suppose a trampoline node is a myopic node, that knows the next trampoline is 
not in its routemap, but considers that another node (the delegatee) is more 
likely to know the next trampoline that it does.
In such a case, that myopic node would consider it more optimal to allocate 
only a small amount of fee for its own hop and to devote most of the fee to the 
delegatee.
This increases the chance that the delegatee, if it knows the route to the next 
trampoline, will accept and continue routing.
Its alternative would be to allocate too low a fee to the delegatee, leading 
the delegatee to reject the routing, which 

Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-04 Thread Christian Decker
Hi ZmnSCPzj,

I think we should not try to recover from a node not finding the next
hop in the trampoline, and rather expect trampolines to have reasonable
uptime (required anyway) and have an up to date routing table (that's
what we're paying them for after all).

So I'd rather propose reusing the existing onion construction as is and
expect the trampolines to fail a payment if they can't find the next
hop.

Let's take the following route for example (upper case letters represent
trampolines):

```
a -> b -> c -> D -> e -> f -> G -> h -> i -> j
```

With `a` being the sender, and `j` being the recipient. `D` and `G` are
trampolines. The sender `a` selects trampolines `D` and `G` at random
from their partial (possibly outdated) routing table. It creates the
inner onion using those two trampolines. It then computes a route to `D`
(`a -> b -> c -> D`). The `hop_payload` for `D` is a TLV payload that
has a single key `t` (assuming `t` is assigned in the TLV spec) that
contains the inner onion. It then initiates the payment using this
nested onion (`a -> b -> c -> D` + trampoline payload for `D`).

Upon receiving the onion `D` decrypts the outer onion to find the TLV
payload containing the `t` entry, which indicates that it should act as
a trampoline. It then decodes the inner trampoline onion and finds the
`node_id` of `G`. `D` then computes the outer onion to the next
trampoline `D -> e -> f -> G`, and adds the trampoline payload for `G`
(the inner trampoline onion we just decoded).

Upon receiving the onion `G` processes the onion like normal, finding
again an inner trampoline onion and decrypting it. Since `j` did not
indicate that it understands the trampoline protocol, `G` is instructed
to downgrade the onion into a normal non-trampoline onion (don't include
a trampoline, rather include the raw payload for `j`). It then computes
the route to `j`, and it creates a normal outer base routing onion `G ->
h -> i -> j`, which completes the protocol.

Like mentioned above the entire job of trampolines is to provide base
routing capability, and we should not make special provisions for myopic
trampoline nodes, since routing is their entire reason for existence :-)

Cheers,
Christian

>> Could this be implemented by replacing only the front of the 
>> trampoline-level onion?
>> (presumably with some adjustment of how the HMAC is computed for the new 
>> trampoline layer)
>
> I am trying to design a trampoline-level onion that would allow replacement 
> of the first hop of the onion.
>
> Below is what I came up with.
> As I am neither a cryptographer nor a mathematician, I am unable to consider, 
> whether this may have some problem in security.
>
> Now the "normal" onion, the first hop is encrypted to the recipient.
>
> I propose that for the "inner" trampoline-level onion, the first hop be sent 
> "in the clear".
> I think this is still secure, as the "inner" trampoline-level onion will 
> still be wrapped by the outer link-level onion, which would still encrypt it.
>
> When a node receives a trampoline-level onion, it checks if it is the first 
> hop.
> If it is, then it decrypts the rest of the onion and tries to route to the 
> next trampoline-level node.
> If not, then it is being delegated to, to find the trampoline.
>
> If the node cannot find the front of the trampoline-level onion, then it can 
> route it to another node that it suspects is more likely to know the 
> destination (such as the mechanisms in discussion in the "Routemap Scaling" 
> thread).
>
> Let me provide a concrete example.
>
> Payer Z creates a trampoline-level onion C->D->E:
>
> C | Z | encrypt(Z * C, D | encrypt(Z * D, E))
>
> Then Z routes to link-level onion A->B->C, with the payload to C being the 
> above trampoline-level onion:
>
> encrypt(Z * A, "link level" | B | encrypt(Z * B, "link level" | C | encrypt(Z 
> * C, "trampoline level" | C | Z | encrypt(Z * C, D | encrypt(Z * D, E)
>
> Upon reaching C, it sees it is given a trampoline-level onion, and if C is 
> unable to find D in its local map, it can delegate it to some other node.
>
> For example, if C thinks its neighbor M knows D, it can create:
>
> encrypt(C * M, "link level" | M | encrypt(C * M, "trampoline level" | D | Z | 
> encrypt(Z * D, E)))
>
> M finds that it is not the first hop in the trampoline-level onion.
> So M finds a route to D, for example via M->N->D, and gives:
>
> encrypt(M * N, "link level" | D | encrypt(M * D, "trampoline level" | D | Z | 
> encrypt(Z * D, E)))
>
> Is this workable?
> Note that it seems to encounter the same problem as Rendezvous Routing.
> I assume it is possible to do this somehow (else how would hidden services in 
> Tor work?), but the details, I am uncertain of.
> I only play a cryptographer on Internet.
>
> Regards,
> ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-04 Thread ZmnSCPxj via Lightning-dev
Good morning list,


> Could this be implemented by replacing only the front of the trampoline-level 
> onion?
> (presumably with some adjustment of how the HMAC is computed for the new 
> trampoline layer)

I am trying to design a trampoline-level onion that would allow replacement of 
the first hop of the onion.

Below is what I came up with.
As I am neither a cryptographer nor a mathematician, I am unable to consider, 
whether this may have some problem in security.

Now the "normal" onion, the first hop is encrypted to the recipient.

I propose that for the "inner" trampoline-level onion, the first hop be sent 
"in the clear".
I think this is still secure, as the "inner" trampoline-level onion will still 
be wrapped by the outer link-level onion, which would still encrypt it.

When a node receives a trampoline-level onion, it checks if it is the first hop.
If it is, then it decrypts the rest of the onion and tries to route to the next 
trampoline-level node.
If not, then it is being delegated to, to find the trampoline.

If the node cannot find the front of the trampoline-level onion, then it can 
route it to another node that it suspects is more likely to know the 
destination (such as the mechanisms in discussion in the "Routemap Scaling" 
thread).

Let me provide a concrete example.

Payer Z creates a trampoline-level onion C->D->E:

C | Z | encrypt(Z * C, D | encrypt(Z * D, E))

Then Z routes to link-level onion A->B->C, with the payload to C being the 
above trampoline-level onion:

encrypt(Z * A, "link level" | B | encrypt(Z * B, "link level" | C | encrypt(Z * 
C, "trampoline level" | C | Z | encrypt(Z * C, D | encrypt(Z * D, E)

Upon reaching C, it sees it is given a trampoline-level onion, and if C is 
unable to find D in its local map, it can delegate it to some other node.

For example, if C thinks its neighbor M knows D, it can create:

encrypt(C * M, "link level" | M | encrypt(C * M, "trampoline level" | D | Z | 
encrypt(Z * D, E)))

M finds that it is not the first hop in the trampoline-level onion.
So M finds a route to D, for example via M->N->D, and gives:

encrypt(M * N, "link level" | D | encrypt(M * D, "trampoline level" | D | Z | 
encrypt(Z * D, E)))

Is this workable?
Note that it seems to encounter the same problem as Rendezvous Routing.
I assume it is possible to do this somehow (else how would hidden services in 
Tor work?), but the details, I am uncertain of.
I only play a cryptographer on Internet.

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-03 Thread Pierre
> This is not an issue. Like we discussed for the multi-part payments the HTLCs 
> still resolve correctly

Right! Great, missed that
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-03 Thread Christian Decker
On Wed, 3 Apr 2019, 05:42 ZmnSCPxj via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> wrote:

> Good morning Pierre and list,
>
> > There is another unrelated issue: because trampoline nodes don't know
> > anything about what happened before they received the onion, they may
> > unintentionnaly create overlapping routes. So we can't simply use the
> > payment_hash as we currently do, we would have to use something a bit
> > more elaborate.
>
> Just to be clear, the issue is for example with a network like:
>
>
> A --- B  C
>  / \
> /   \
>/ \
>   /   \
>  D --- E
>
> Then, A creates an inner trampoline onion "E->C", and an outer onion
> "A->B->E".
>
> E, on receiving the inner trampoline onion "E->C", finds that E->B
> direction is low capacity, so routes over the outer onion "E->D->B->C" with
> inner trampoline onion "C".
>
> This creates an overall route A->B->E->D->B->C.
>
> When the B->C HTLC is resolved, B can instead claim the A->B HTLC and just
> fail the D->B HTLC, thereby removing D and E from the route and claiming
> their fees, even though they participated in the route.
>

This is not an issue. Like we discussed for the multi-part payments the
HTLCs still resolve correctly, though node B might chose to short circuit
the payment it'll also clear the HTLCs through E And D (by failing them
instead of settling them) but the overall payment remains atomic and
end-to-end secure. The skipped nodes (which may include the trampoline) may
lose a bit of fees, but that is not in any way different than a failed
payment attempt that is being retried from the sender :-)

>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-03 Thread Pierre
Hello ZmnSCPxj,

> Do you refer to the changing from "H"TLC to "P"TLC point-locked timelocked 
> contracts?
> i.e. instead of payment hash / preimage, we use payment point / scalar.

Yes, that is what I meant. Cryptography isn't my strong suit though,
so I'm not able to go into much more details.

Cheers,

Pierre
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-03 Thread Johan Torås Halseth
Hi Pierre and list folks,

I haven't looked at the technical implications of implementing this in
detail, but I like the high-level direction this proposal is taking :)

I think it nicely ties together several concepts that have been proposed
earlier, and with the correct design could give the sender all the
flexibility needed to craft payments according to its own
reliability/privacy/fee tradeoff.

In an ideal world we would have:
- Multi-hop locks: hop decorrelation will be even more important when the
sender no longer controls the whole payment path.

- Packet switched routing: the sender can choose whether to route purely
packet switched (only knowing the destination, no need to keep any routing
table) or route purely onion-based (as today), or something in between. As
Christian mentions, this is similar to how TOR/TCP works, and I like the
flexibility this layering allows.

- Rendezvous routing: such a proposal would be nice to combine with
rendezvous routing. This way even the sender wouldn't necessarily know if
the "destination node" is just another trampoline. Maybe maybe this concern
shouldn't be on this layer though?

- Fees: (as today) the sender would set the fees it is willing to pay
between trampolines, and it could dynamically learn about fee levels needed
to reach different parts of the network. Today we know the fee needed to
reach the next hop, but here we could start out low (for the
trampoline-to-trampoline fee) and let different trampolines return
competing fee offers to get to the next hop.

As mentioned, I haven't thought about the technical implications of all
this, and it would certainly require a lot of work to get this actually
implemented.

Cheers,
Johan

On Wed, Apr 3, 2019 at 5:42 AM ZmnSCPxj via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> wrote:

> Good morning Pierre and list,
>
> > There is another unrelated issue: because trampoline nodes don't know
> > anything about what happened before they received the onion, they may
> > unintentionnaly create overlapping routes. So we can't simply use the
> > payment_hash as we currently do, we would have to use something a bit
> > more elaborate.
>
> Just to be clear, the issue is for example with a network like:
>
>
> A --- B  C
>  / \
> /   \
>/ \
>   /   \
>  D --- E
>
> Then, A creates an inner trampoline onion "E->C", and an outer onion
> "A->B->E".
>
> E, on receiving the inner trampoline onion "E->C", finds that E->B
> direction is low capacity, so routes over the outer onion "E->D->B->C" with
> inner trampoline onion "C".
>
> This creates an overall route A->B->E->D->B->C.
>
> When the B->C HTLC is resolved, B can instead claim the A->B HTLC and just
> fail the D->B HTLC, thereby removing D and E from the route and claiming
> their fees, even though they participated in the route.
>
> > (maybe private keys?)
>
> Do you refer to the changing from "H"TLC to "P"TLC point-locked timelocked
> contracts?
> i.e. instead of payment hash / preimage, we use payment point / scalar.
>
> I think a few ideas would be improved by this.
>
> 1.  Trampoline payments, as described above.
> 2.  Offline vending machines
> - Instead of storing a fixed number of invoices from the always-online
> payment node, store a HD parent point and derive child points for payments.
> 3.  Enables payment decorrelation.
>
> Perhaps we should consider switching to payment points/scalars sometime
> soon.
>
> Regards,
> ZmnSCPxj
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-02 Thread ZmnSCPxj via Lightning-dev
Good morning Pierre and list,

> There is another unrelated issue: because trampoline nodes don't know
> anything about what happened before they received the onion, they may
> unintentionnaly create overlapping routes. So we can't simply use the
> payment_hash as we currently do, we would have to use something a bit
> more elaborate.

Just to be clear, the issue is for example with a network like:


A --- B  C
 / \
/   \
   / \
  /   \
 D --- E

Then, A creates an inner trampoline onion "E->C", and an outer onion "A->B->E".

E, on receiving the inner trampoline onion "E->C", finds that E->B direction is 
low capacity, so routes over the outer onion "E->D->B->C" with inner trampoline 
onion "C".

This creates an overall route A->B->E->D->B->C.

When the B->C HTLC is resolved, B can instead claim the A->B HTLC and just fail 
the D->B HTLC, thereby removing D and E from the route and claiming their fees, 
even though they participated in the route.

> (maybe private keys?)

Do you refer to the changing from "H"TLC to "P"TLC point-locked timelocked 
contracts?
i.e. instead of payment hash / preimage, we use payment point / scalar.

I think a few ideas would be improved by this.

1.  Trampoline payments, as described above.
2.  Offline vending machines
- Instead of storing a fixed number of invoices from the always-online 
payment node, store a HD parent point and derive child points for payments.
3.  Enables payment decorrelation.

Perhaps we should consider switching to payment points/scalars sometime soon.

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-01 Thread ZmnSCPxj via Lightning-dev
Good morning Christian,


>
> There are two ways we can use this:
>
> -   A simple variant in which we just tell a single trampoline what the
> intended recipient is (just a pubkey, and an amount) and it'll find a
> route.
>
> -   A complex variant in which a trampoline is given a next hop, and a
> smaller onion to pass along to the next hop. The trampoline doesn't
> learn the intended recipient, but can still route it.

The simple variant definitely tells the trampoline who the payee is, so I would 
reject it.


> Multi-trampoline routing
> =
>
> The more complex proposal involves nesting a smaller onion into the
> outer routing onion. For this the sender generates a small onion of, for
> example, 10 hops whose length is only 650 bytes instead of the 20 hops
> for the outer routing onion. The hops in the inner/smaller onion do not
> have to be adjacent to each other, i.e., they can be picked randomly
> from the set of known nodes and there doesn't need to be a channel
> between two consecutive hops, unlike in the outer/routing onion. The
> hops in the smaller onion are called trampolines `t_1` to `t_10`.
>
> The construction of the smaller onion can be identical to the
> construction of the routing onion, just needs its size adjusted. The
> sender then picks a random trampoline node `t_0` in its known
> neighborhood and generates a routing onion containing the smaller onion
> as payload to `t_0` and signaling data (final recipient, amount, inner
> onion). Upon receiving an incoming payment with trampoline instructions
> a trampoline `t_i` unwraps the inner onion, which yields the next
> trampoline `t_{i+1}` node_id. The trampoline then finds a route to
> `t_{i+1}`, serializing the inner onion (which was unwrapped and is now
> destined for `t_{i+1}`) and creating the outer routing onion with that
> as the payload. Notice that, like in the simple variant, `t_i` generates
> a new outer onion, which means we don't have any issues with shared
> secrets and HMACs like in rendezvous routing. Resolution is also
> identical to above.
>
> This construction reuses all the onion primitives we already have, and
> it allows us to bounce a payment through multiple trampolines without
> them learning their position in this nested path. The sender does
> not have to have a total view of the network topology, just have a
> reasonable chance that two consecutive trampolines can find a route to
> each other, i.e., don't use mobile phone as trampolines :-)

Naively, would it not be possible?

Suppose a mobile phone keeps only a small subset of the routemap due to memory 
constraints, but has high uptime because it is the precious mobile device of 
somebody who uses the mobile phone at all hours.

When the mobile phone trampoline is unable to route to the next trampoline, 
could it not "delegate" this by looking for some node in its smaller routemap 
that it believes (by some other mechanism) to be more likely to route to the 
next trampoline?
Could this be implemented by replacing only the front of the trampoline-level 
onion?
(presumably with some adjustment of how the HMAC is computed for the new 
trampoline layer)

If we will change to use trampoline-level onions then maybe we can change 
things somewhat to support this usage better.

Otherwise it would seem that possible trampolines would have to advertise 
themselves as such.
It would be better if a trampoline could be just "taken out of a hat" and 
selected randomly.
And as long as the trampoline is able to *delegate* the routing to some other 
trampoline, and there is sufficient fee, payment can succeed.

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-01 Thread Christian Decker
Thanks Pierre for this awesome proposal, I think we're onto something
here. I'll add a bit more color to the proposal, since I've been
thinking about it all weekend :-)

There are two ways we can use this:

 - A simple variant in which we just tell a single trampoline what the
   intended recipient is (just a pubkey, and an amount) and it'll find a
   route.
 - A complex variant in which a trampoline is given a next hop, and a
   smaller onion to pass along to the next hop. The trampoline doesn't
   learn the intended recipient, but can still route it.

# Simple Variant

As the name implies it is pretty trivial to implement: the sender
computes a route to some trampoline node `t` it knows in its 2- or
3-neightborhood and creates an onion that describes this route. The
payload for the trampoline node `t` then contains two parameters:
`receiver` and `amount`. The trampoline node `t` then computes a route
from itself to the `receiver` and creates a new onion (the old onion
terminates at the trampoline node). Since the trampoline node generates
a new route, it also generates the shared secrets, HMACs and everything
else to match (no problem with matching HMACs like in the case of
rendezvous routing).

The receiver doesn't learn anything about this being a trampoline
payment (it doesn't even have to implement it itself), and resolution of
the HTLC happens like normal (with the extra caveat that the trampoline
needs to associate the upstream incoming HTLC with the resolution of the
downstream HTLC, but we do that anyway now).

# Multi-trampoline routing

The more complex proposal involves nesting a smaller onion into the
outer routing onion. For this the sender generates a small onion of, for
example, 10 hops whose length is only 650 bytes instead of the 20 hops
for the outer routing onion. The hops in the inner/smaller onion do not
have to be adjacent to each other, i.e., they can be picked randomly
from the set of known nodes and there doesn't need to be a channel
between two consecutive hops, unlike in the outer/routing onion. The
hops in the smaller onion are called trampolines `t_1` to `t_10`.

The construction of the smaller onion can be identical to the
construction of the routing onion, just needs its size adjusted. The
sender then picks a random trampoline node `t_0` in its known
neighborhood and generates a routing onion containing the smaller onion
as payload to `t_0` and signaling data (final recipient, amount, inner
onion). Upon receiving an incoming payment with trampoline instructions
a trampoline `t_i` unwraps the inner onion, which yields the next
trampoline `t_{i+1}` node_id. The trampoline then finds a route to
`t_{i+1}`, serializing the inner onion (which was unwrapped and is now
destined for `t_{i+1}`) and creating the outer routing onion with that
as the payload. Notice that, like in the simple variant, `t_i` generates
a new outer onion, which means we don't have any issues with shared
secrets and HMACs like in rendezvous routing. Resolution is also
identical to above.

This construction reuses all the onion primitives we already have, and
it allows us to bounce a payment through multiple trampolines without
them learning their position in this nested path. The sender does
not have to have a total view of the network topology, just have a
reasonable chance that two consecutive trampolines can find a route to
each other, i.e., don't use mobile phone as trampolines :-)

# Tradeoffs everywhere

## Longer Routes

One potential downside is that by introducing this two-level nesting of
an outer routing onion and an inner trampoline onion, we increase the
maximum length of a route to `num_outer_hops * num_inner_hops`, given
that each layer of the inner onion may initiate a new `num_outer_hops`
outer route. For the example above (which is also the worst case) we
have a 10 inner hops, and 9 outer hops (due to the signalling overhead),
which results in a maximum route length of 90 hops. This may result in
more funds being used to route a payment, but it may also increase
chances of the payment succeeding.

## Comparison with TCP/IP + Tor

This proposal also brings us a lot closer to the structure of Tor on the
public network, in which the nodes that are part of a circuit do not
have to be direct neighboors in the network topology since end-to-end
reachability is guaranteed by a base routing layer (TCP/IP) whereas
sender/receiver obfuscation is tackled at a higher layer (Tor).

In our case the outer onion serves as the base routing layer that is
used for point-to-point communication, but unlike TCP/IP is also
encrypted and routed anonymously, while the inner onion takes care of
end-to-end reachability, also in encrypted fashion.

## In-network retrial

>From the comparison with TCP/IP and Tor might have hinted at this, but
since the outer onion is created from scratch at each trampoline, a
trampoline may actually retry a payment multiple times if an attempt
failed, reducing the burden on the sender, 

Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-01 Thread Pierre
Hello ZmnSCPxj,

> Unless we propose to massively change the onion packet construction...?

I'm afraid we would have to make some changes. I imagine we would have
two onions:
- one for the adjacent hops (this is the onion we are currently using)
- one for the trampoline hops

The 'trampoline onion' would be contained in the per-hop payload of
the final node of the 'adjacent onion'. So in your example B would:
1) receive the htlc
2) see that it is the last hop in the route, and extract the trampoline payload
3) peel the trampoline onion and see that it should delegate the payment to C
4) find a route to C and set the trampoline onion as payload for C

I haven't studied PR #593 enough to tell how easy that would be
achievable though.

There is another unrelated issue: because trampoline nodes don't know
anything about what happened before they received the onion, they may
unintentionnaly create overlapping routes. So we can't simply use the
payment_hash as we currently do, we would have to use something a bit
more elaborate. (maybe private keys?)

Cheers,

Pierre
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-04-01 Thread ZmnSCPxj via Lightning-dev
Good morning Pierre, Rene, and list,

I would also like to point out that even if the trampoline point does not know 
the next trampoline point, then it need not fail the routing.
(this may occur if we start pruning the routemap as the LN size grows)

As long as we can fix the issues regarding HMAC, then the trampoline point may 
itself delegate the routing to the next trampoline point to another trampoline 
point it inserts into the onion.

So what we need to somehow support, is to be able to "left shift" and "right 
shift" arbitrarily in the onion packet.
If we can handle this, then trampolining is possible and trampoline routing is 
feasible to delegate routing elsewhere.

This also ties with deterministic methods of pruning routemaps.
For instance, somebody proposed to create a false "geographic location" for 
each node, possibly derived only from the node public key being projected into 
some spatial volume.
(To be clear, this does *not* mean that every node needs to register some 
merely-Earth-based location, which can be easily falsified anyway; instead we 
project the node public key to some notion of "nearness")
Then a node might be expected to keep at least the nearest nodes to its 
"geographic location" in its routemap.

Then if I happen to be a trampoline point, and I am unable to locate the next 
trampoline point in my local routemap, I could instead locate the node on my 
routemap that is "nearest" to the next trampoline point, and forward the 
payment there.

Now, to an extent, privacy is reduced here since it is likelier than before 
that the "next trampoline" is actually the payee.
However, as a source node, I only need to know the actual route to my first 
trampoline point, and let the trampoline point worry about how to get it to the 
next trampoline.
So I can even just prune only the channels and channel relationships (endpoints 
of channels), and retain only the node public keys (a cheap 32 bytes), probably 
pruning the node public keys in some deterministically probabilistic fashion.
In this case, I might still be interested in gossip about faraway channels --- 
I would still want to check that the channel exists (by blockchain lookup), but 
after I know the channel exists I can throw it away, only considering it as a 
proof-of-existence of a faraway node that I might use as a trampoline to 
improve my privacy.

In effect, this lets us give a continuum:

1.  At one end, the full route and every intermediate hop to the destination is 
known only by the source.
2.  At the other end, the source only knows its direct channels, and sends to 
some adjacent trampoline node, and asks the trampoline node to route to the 
destination.

The above gives a nice continuum where the amount of space dedicated to your 
own local routemap improves your privacy, and you can prune your routemap at 
the cost of privacy reduction (and probably hedging your fees by always 
overpaying fees).

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-03-31 Thread ZmnSCPxj via Lightning-dev
Good morning Rene and Pierre,

An issue here (which I think also affects Rendezvous Routing) is with 
compatibility of the HMAC.

HMAC covers the entire 1300-byte `hops_data` field.

If, in order to reach the next trampoline, more than one intermediate node is 
inserted, would the packet that reaches the next trampoline have a valid HMAC 
still?
Consider that the filler data generated by the current trampoline to 
communicate with intermediate nodes may cause different filler data to be XORed 
with the 0x00 data added to left-shift the data at each intermediate node.
(I am unsure if I express myself coherently here)

So for example, suppose I am the source and I trampoline to nodes B and C, and 
pay to destination D.
Suppose B is a direct neighbor of mine, but I have no idea where C and D are.

Suppose for simplicity that the onion packet is just 6 hops long.
So I initialize as:

[ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]

I right shift and insert destination D:

[ D, here's my payment ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]

Then I encrypt with some shared secret known by me A and D:

[ encrypt(A * D, "D, here's my payment") ] [ encrypt(A * D, 0) ] [ encrypt(A * 
D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ]

Then I right shift and insert trampoline C:

[ C, send this to D ] [ encrypt(A * D, "D, here's my payment") ] [ encrypt(A * 
D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ] [ encrypt(A * D, 0) ]

Then I encrypt with some shared secret known by me A and C:

[ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, encrypt(A * D, "D, 
here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, 
encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, 
encrypt(A * D, 0)) ]

Then I right shift and insert trampoline B:

[ B, send this to C ] [ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, 
encrypt(A * D, "D, here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] 
[ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ]

And encrypt with A * B:

[ encrypt(A * B, "B, send this to C") ] [ encrypt(A * B, encrypt(A * C, "C, 
send this to D")) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, "D, here's 
my payment"))) ] [ encrypt(A * B, encrypt(A * C, encrypt(A * D, 0))) ] [ 
encrypt(A * B, encrypt(A * C, encrypt(A * D, 0))) ] [ encrypt(A * B, encrypt(A 
* C, encrypt(A * D, 0))) ]

I send this to B, who removes one layer of encryption:

[ B, send this to C ] [ encrypt(A * C, "C, send this to D") ] [ encrypt(A * C, 
encrypt(A * D, "D, here's my payment")) ] [ encrypt(A * C, encrypt(A * D, 0)) ] 
[ encrypt(A * C, encrypt(A * D, 0)) ] [ encrypt(A * C, encrypt(A * D, 0)) ]

Now B finds the shortest route involves nodes N and O before reaching C.
So B has to insert N and O, pushing out one packet from the end.
But the pushed-out packet will no longer be recoverable and it cannot be 
re-encrypted except by A.

(Unless I misunderstand the onion construction)


Unless we propose to massively change the onion packet construction...?


> 1.) A different fee mechanism. Let us (only as a radical thought experiment) 
> assume we drop the privacy of the final amount in routing.

Please no.

> A sending node could offer a fee for successful routing. Every routing node 
> could decide how much fee it would collect for forwarding. Nodes could try to 
> collect larger fees than the min they announce but that lowers the probably 
> for the payment to be successful. Even more radical: Nodes would not even 
> have to announce min fees anymore. Turning routing and fees to a real 
> interactive market

Would this not also require that intermediate nodes know the ultimate 
destination of the payment?
How would intermediate nodes find out which next hop would be reasonable?

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-03-28 Thread René Pickhardt via Lightning-dev
Dear Pierre-Marie and fellow lightning developers,

I really like that suggestion. In the context of JIT routing I was
tinkering about the same idea (is it possible for sending nodes to only
know a small part of the network - for example the friend of a friend
network - to save Hardware / gossip bandwidth requirements) but I was
thinking about a different solution which I want to drop in here. (I
believe yours is better though)

My thought was to use rendez-vous routing. This would mean the sender would
have to provide a rendez vous point from his local (friend of a friend?)
network and the recipient provides a route to him/herself. Only the
recipient has to know the entire network topology.

One problem with rendez vous routing is of course that the routing fails if
the route from the rendez vous point does not work. This again could be
mitigated with JIT routing.

In the context of JIT routing it also makes sense to "overpay" fees so that
JIT nodes could rebalance without loss. Making my solution also
probabilistic with the fees. The fact that this pattern of probabilistic
fees occurs for the second time now leads me to the following 2 more
general ideas (maybe we should start a new thread if we discuss them to
stay on topic here) that might help with routing.

1.) A different fee mechanism. Let us (only as a radical thought
experiment) assume we drop the privacy of the final amount in routing. A
sending node could offer a fee for successful routing. Every routing node
could decide how much fee it would collect for forwarding. Nodes could try
to collect larger fees than the min they announce but that lowers the
probably for the payment to be successful. Even more radical: Nodes would
not even have to announce min fees anymore. Turning routing and fees to a
real interactive market

2.) A virtual hierarchical address space. Maybe we should start thinking
about the creation of a semantic overlynetwork / address space for nodes
similar to IP. This would allow any node to just have a pruned network view
but still make smart routing decisions. Obviously we would have to find a
way to assign virtual network addresses to nodes which might be hard.

The second suggestion would be of particular interest in your case if N
also did not know the entire network and has to decide to whom to to
forward for the final destination D.

Sorry for "hijacking" your suggestion and throwing so many new ideas but in
my mind this seems all very connected /related.

Best Rene


Pierre  schrieb am Do., 28. März 2019, 23:25:

> Hello List,
>
> I think we can use the upcoming "Multi-frame sphinx onion format" [1]
> to trustlessly outsource the computation of payment routes.
>
> A sends a payment to an intermediate node N, and in the onion payload,
> A provides the actual destination D of the payment and the amount. N
> then has to find a route to D and make a payment himself. Of course D
> may be yet another intermediate node, and so on. The fact that we can
> make several "trampoline hops" preserves the privacy characteristics
> that we already have.
>
> Intermediate nodes have an incentive to cooperate because they are
> part of the route and will earn fees. As a nice side effect, it also
> creates an incentive for "routing nodes" to participate in the gossip,
> which they are lacking currently.
>
> This could significantly lessen the load on (lite) sending nodes both
> on the memory/bandwidth side (they would only need to know a smallish
> neighborhood) and on the cpu side (intermediate nodes would run the
> actual route computation).
>
> As Christian pointed out, one downside is that fee computation would
> have to be pessimistic (he also came up with the name trampoline!).
>
> Cheers,
>
> Pierre-Marie
>
> [1]
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-February/001875.html
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] Outsourcing route computation with trampoline payments

2019-03-28 Thread Pierre
Hello List,

I think we can use the upcoming "Multi-frame sphinx onion format" [1]
to trustlessly outsource the computation of payment routes.

A sends a payment to an intermediate node N, and in the onion payload,
A provides the actual destination D of the payment and the amount. N
then has to find a route to D and make a payment himself. Of course D
may be yet another intermediate node, and so on. The fact that we can
make several "trampoline hops" preserves the privacy characteristics
that we already have.

Intermediate nodes have an incentive to cooperate because they are
part of the route and will earn fees. As a nice side effect, it also
creates an incentive for "routing nodes" to participate in the gossip,
which they are lacking currently.

This could significantly lessen the load on (lite) sending nodes both
on the memory/bandwidth side (they would only need to know a smallish
neighborhood) and on the cpu side (intermediate nodes would run the
actual route computation).

As Christian pointed out, one downside is that fee computation would
have to be pessimistic (he also came up with the name trampoline!).

Cheers,

Pierre-Marie

[1] 
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-February/001875.html
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev