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

```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

```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).

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 :-)

## 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

```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

```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] Eltoo in a tree

```Good morning Hossein,

This is already known.
Indeed, this is the basis of Burchert-Decker-Wattenhofer "Channel Factories".
https://www.tik.ee.ethz.ch/file/a20a865ce40d40c8f942cf206a7cba96/Scalable_Funding_Of_Blockchain_Micropayment_Networks%20(1).pdf

https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-December/001721.html

It is likely that channel factories of some form will be created after we can
get Decker-Russell-Osuntokun ("eltoo") online.
Decker-Russell-Osuntokun requires some kind of `SIGHASH_NOINPUT`.

In many ways, a channel is simply a type of cryptocurrency system.
If we were to generate some kind of hierarchical system of types:

* Cryptocurrency System (abstract)
* Blockchain (abstract)
* Bitcoin (concrete) - the only blockchain that can ever exist
* Offchain cryptocurrency system (abstract) - requires an existing
Cryptocurrency System to construct
* Poon-Dryja (concrete) - current Lightning Network; 2-party only
* Decker-Wattenhofer (concrete) - multiparty but requires long locktimes on
unilateral
* Decker-Russell-Osuntokun (concrete) - multiparty, requires short
locktimes on unilateral

Burchert-Decker-Wattenhofer factories are just the realization that you can do
something like instantiate a Poon-Dryja channel inside a Decker-Wattenhofer
channel inside a Bitcoin blockchain.

Similarly, your NOctaHub is just another offchain cryptocurrency system, and
the realization that you can nest other offchain cryptocurrency systems inside
it is simply the same realization that Burchert-Decker-Wattenhofer had.

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

```

Re: [Lightning-dev] Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

```Hi ZmnSCPxj & RenĂ©.

One way you could have both determinism and encourage a diverse distribution of
network maps is to treat it as a spatial indexing problem, where the space we
use is the lexicographical space of the node ids (or hashes of), borrowing some
similarities from DHTs.

If for example, we take a quadtree, you can take the 2 most-significant bits of
the public key hash, which would put your node into one of 4 buckets. Nodes
could advertise a feature bit indicating that they are committed to keeping the
entire routemap of the bucket which matches their own public key hash, which
would be all of the nodes in the same bucket - and all of the channels with one
or both of their endpoints in the bucket.

I'd estimate that with a quadtree, information held by each node could be
reduced to about 40% of that of the parent node in the quadtree, although the
real amounts would depend on such things as autopilot defaults (ie, how many
channels you open to nodes within your bucket versus channels to nodes in other
buckets). Nodes could decide their own bucket capacities on which they wish to
spill and reduce the amount of gossip by taking the 2 next most significant
bits of the PKH, and could go several layers deep.

A node which needs to make a payment to another node within its bucket should
be able to do so without querying (unless there are no routes with the required
capacity). If making a payment to another bucket, then there would still exist
a decent number of channels in the local routemap to nodes in those other
buckets, and these nodes could be queried to find the second half of a route to
the destination, or could use JIT routing for the second half, assuming the
first half of the route can be selected from the local routemap.

In terms of relating this to "locality" in the geographical sense, one could
create a convention where each bucket represents an approximate physical
location. The globe can be spatially-indexed as a quadtree by taking a
tetrahedral map projection (eg, Lee conformal projection[1]). The 4 equalateral
triangles of the tetrahedron can be infinitely split again into 4 smaller
equal-sized equalateral triangles for however many layers deep the quadtree
might be. With this, it might be possible to have a convention where there is a
relation between the lexicographical space and the geographical space, and
wallet software would essentially brute force a private key to put you into the
corresponding bucket to your physical location (trivial for the small number of
bits we're talking about). Routing would be improved for local trade because
you would have the entire local topology stored, and would only need to query
when making payment at distance. (This may raise some privacy concerns which
would need discussing.)

One issue is that it would result in a very unbalanced tree given that
population is dense in some areas and sparse in others. To overcome this,
instead of using a conformal or equal-area projection, we might be able to use
an equal-population-per-area projection, which I had never heard of such
projection before but have found some research in regards to producing them[2].
Nodes would need to agree on the projection in order for this to work, but the
work could be done once and the results open sourced and shared between the
implementations.

Autopilot implementations might also need adjusting to consider distance too.
As a starting point I would suggest a geometric distribution, where half of
opened channels should be within the same bucket, a quarter should be to
sibling buckets, and an eight to cousin buckets, etc. This would result in
increased probability of routing and reduced querying for local payments -
paying your local coffee shop should be query-free - and payments to the other
side of the world might require increased querying.

There are also privacy considerations if nodes indicate their approximate
locations which would need discussing. What do you think?

Also, this method does not need the be the exclusive way in which gossip is
communicated between nodes, and one might also combine with something like
ZmnSCPxj has suggested, for gossiping about the highest capacity nodes. It
might be also possible to share information about the highest capacity channels
in a bucket too.

[1]:https://en.wikipedia.org/wiki/Lee_conformal_world_in_a_tetrahedron
[2]:https://www.pnas.org/content/101/20/7499.full

(PS, sorry for the separate thread, LML will not let me subscribe to the list)___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

```