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

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


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


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

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

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


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

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)

2019-04-04 Thread m.a.holden via Lightning-dev
Good morning ZmnSCPxj, thanks for the response.

> I would be hesitant to divide the world in such manner.
> I understand that in typical computer science, splitting your objects up into 
> smaller parts is a long-accepted method of doing things.

> However, when it comes to finances and political power (the power to censor 
> or disrupt), such splitting is highly undesirable.

> Thus I am strongly allergic to things that would "hierarchical"ize or 
> "bucket"ize or even just have a separation between "endpoint" and "core" 
> network.

> I would rather propose for acceptance into BOLT, such proposals that would 
> keep the network homogeneous.

Firstly, I completely agree with you that we should not be splitting up the 
network in any way which nodes or channels can be politically targeted, or in 
which any node is designated special privelege or status. I have the same 
allergy as you and took this into considerations when proposing this, and some 
of your suggestions are along a simlar  line of thinking as mine.

I think you might have misunderstood what I was proposing, but it's probably my 
fault for not expressing it well. With my suggestion, all nodes continue to be 
equal participants and there are no special nodes. I used the term "endpoint" 
previously to mean one of the two nodes which a regular channel belongs to, and 
not to mean some kind of special node. Any node can open channels to any other 
node - the "buckets" are merely a strategy for locally organizing gossip so 
that it can be made more efficient. The term "buckets" is used in the 
descriptions of other DHTs such as Kademlia too, and they don't refer to 
splitting up the global network, they merely provide a perspective for looking 
at subsections of it.

I'm certainly interested in any solutions which keep the network permissionless 
because we really don't want to end up with DNS 2.0 or similar.

> Various nodes may have different resources (BTC, CPU, memory, bandwidth, 
> latency).
> Such inequalities are inevitable in this universe.
> But these nodes should still, as much as we can, remain peers on the network.

My suggestion accounts for the difference in computational requirements, as 
each node can determine its own depth in  the tree based on the approximate 
quantity of information it wishes to gossip. A node could filter information to 
whichever depth of the tree they wished, by setting the bucket size at which 
they spill. This also allows for the size of gossip to dynamically shrink as 
the network grows, and is similar to garbage collection, in which anything 
which isn't part of the destination bucket on spilling is purged.

Nodes could also pick (multiple) specific quadtree buckets to communicate all 
gossip about through filters they negotiate (the filter being the hash prefix 
of the desired bucket). It might be desirable to broadcast their filter as part 
of the gossip itself, so that other nodes can learn who are the better 
information providers, but again this would be completely optional.


> This rule can be probabilistically fulfilled by having each node N know *at 
> least* routes to some nodes Ls..., where for all L <- Ls, dist(N, L) < some 
> constant.
> The constant here can be selected by each node independently, depending on 
> its memory and CPU capacity.
(the node knowing more routes than that is perfectly fine)

The quadtree proposes a similar idea, but instead of using some constant, N 
knows about routes to Ls, where each L is within the same bucket. Essentially, 
i < dist(N, L) <= j, where i=BUCKET_MIN and j=BUCKET_MAX. For example, if using 
8-bit ids and the first two bits identify the bucket, then i=, 
j=0011. I guess the equivalent distance using your constant would be 
k=0010, to cover the same range but without discriminating the results 
based on any boundaries like my suggestion does.

> Then, we can have the following global rule:
> * Given three nodes X, Y, and Z, and dist(X, Z) < dist(Y, Z), then X SHOULD 
> be more likely to know a route from itself to Z, than Y to know a route from 
> itself to Z, is also met for nodes which are in different buckets.

This rule is essentially the same as what I was thinking for the distance 
between buckets. With the autopilot suggestion of decreasing the number of 
channels opened as distance increases, the probability of knowing about a 
neighbouring bucket is increased compared with a distant one.


> It looks for any node L <- Ls such that dist(L, D) < dist(N, D).
> In fact, it can just sort those nodes according to dist(L, D) and start with 
> the lowest distance, and fail once it reaches a dist(L, D) that exceeds its 
> own dist(N, D).
> The above algorithm converges since dist(N, D) for each N that is delegated 
> to will progressively get smaller until we reach some N that knows the 
> destination D.

This proposal also seems very similar to how existing DHTs work, unless I'm 
mistaken. My problem with the approach of