Re: [Lightning-dev] Outsourcing route computation with trampoline payments
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
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] 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)
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
