Hi ZmnSCPxj,

> Let me clarify: When you say "node" here, do you mean Lightning Network node?
> Or do you mean instead an in-memory node?

Neither. I meant a node in a tree. I tried to use the term bucket to make the 
distinction between this and Lightning node.
The tree is not strictly in-memory. There is a purely conceptual global 

Each bucket is essentially a view over the union of its 4 children. The bucket 
00b is (0000b U 0001b U 0010b U 0011b). The bucket 0011b is (001100b U 001101b 
U 001110b 001111b), etc. Each client choses a suitable max_depth <= HASHLEN/2, 
and the leaves of their tree contain a set of all PKH whose prefix matches the 
bucket index. A client will keep, at minimum, a subtree of the global quadtree 
(and both nodes for all channels where at least one of the nodes is in the same 

As you state, you can use any data structure for storing this in memory, but 
there are obvious benefits to using a quadtree-index to mirror the conceptual 
global one in terms of efficient querying, filtering, spilling, aggregating 
branch sizes.

If many clients follow the convention then the optimisation opportunities 
arise, because the majority of routes will be discoverable with a single 
(possibly parallel) query to the network. Gossip size can be reduced and 
unwanted gossip can be eliminated, which alleviates the most constrained 
resource, bandwidth. If the conventions are widely followed, the benefits are 
maximized for everybody. Not following convention does not break things, it 
just limits the potential wins.


> As I understand your proposal, taking over or taking down a node near the 
> root of the tree will make it difficult to look up several nodes at once.
> This is because the tree nature makes nodes near the root of the tree (top of 
> the hierarchy) much more important than leaf nodes, which only worry about 
> themselves.

If a node advertises itself near the top of the tree then it will be a better 
information provider than others, but this is never at the exclusion of others 
below it. All of the information a node in the parent bucket holds is held in 
part by the nodes in the child buckets. The parent does not know anything that 
other people don't know too. No nodes are "more important", but they might 
potentially be "more optimal".

If you know about some nodes in bucket 0011b, but none in 0001b where a payment 
destination is, then you could query any node in 0011b and ask about any nodes 
in bucket 0001b. Since the buckets are nearby, there is a greater probability 
that they'll know about more nodes than somebody further away. This would be 
similar to how your proposal operates. If somebody did advertise being in 
bucket 00b, then they're able to find a potentially better (shorter) path to 
the destination because they know more information and you don't need to find a 
path through multiple buckets. If they are under DDoS, it doesn't bring down 
the network or limit access to the child buckets - it just makes it trivially 
less optimal to route because it *might* (low probability) require more queries 
to reach the destination.

When querying, it is expected that if you know about any nodes in the same 
bucket as the payment destination, then there's a high probability that they 
will know a route to the destination. A parent bucket of that bucket is not any 
more likely to know about the destination, they have the same information. I've 
shown that at small depth, there's a high probability that you will have 
knowledge about a reasonable quantity of paths to every other bucket in the 
global network - so the majority of payments will only need to visit one bucket 
outside your own. The reason to specifically query parent buckets is limited, 
and not ultimately necessary.

The only way I can see the problem you raise being a concern is if 
misconfigured clients have an unreasonably large depth for the amount of 
information in the network, such that there are few, or no channels from their 
own bucket to other buckets. In that case, they might become over-reliant on 
the parent's buckets to receive payments, but there are likely to be numerous 
parents at every depth of the tree (correctly configured clients), meaning 
there isn't a clear-cut target that an attacker could DDoS to try and disrupt a 

Nodes do not need to present the real depth at which they keep gossip, but 
there are potentially greater fee-earning opportunities if publicly advertising 
their maximum information capability. Nodes could counterbalance potential DDoS 
risk with higher routing fees, where people might pay more to have a greater 
chance of finding shorter routes in fewer queries, but a frugal client would 
simply chose the cheapest routes, and the more expensive routes via parent 
buckets would be less desirable to them - meaning DDoS on nodes in parent 
buckets may be wasted effort because it would drive people towards saving money 
on fees. Also, since the opportunity cost for missed routing fees would be 
increased for nodes nearer the top of the tree, they are incentivized to make 
the efforts to maintain uptime and try to mitigate DDoS attacks against 

It's hard to say for certain whether the risks would be real cause for concern 
without testing on real world data, which we don't yet have the scale to test, 
but I just can't see it being realistic that there would be so few targets 
which make DDoS feasible to begin with, and that if attacks against a 
significant number of nodes were successful, the potential degrading of the 
network would be trivial or even unnoticeable. As the network grows, it seems 
the attack vector would get even more unrealistic because the number of targets 
that one would need DDoS would increase.

> What happens if a node near the root of the tree is brought down?

Buckets closer to the root do not hold any exclusive information. If you bring 
down every node in the root bucket, and every node at depth=1, then nodes at 
depth>=2 will continue to communicate and still collectively know the entire 
network map, with still a good probability that any node can find any other 
node in the network by asking just one other node.

Mark H
Lightning-dev mailing list

Reply via email to