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).
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
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
See also discussion regarding Fulgurite.
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
