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

[ZmnSCPxj]

Good morning m.a.holden,


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Saturday, April 6, 2019 10:39 AM, m.a.holden m.a.holden at protonmail.com wrote:

> Good morning ZmnSCPxj,
> I'll try to clarify my proposal further, but also have a few questions about yours.
>
> > Now, it seems to me what you propose, is to have octrees contain octrees, and so on.
>
> There's one global tree, which is the same for all users. Every node in the tree has a bucket and exactly 4 child nodes, except leaves have no children. The tree has a max depth, which each client sets itself. The theoretical maximum being HASHLEN/2 (In practice, we're likely to be concerned about <8). Note that every parent's bucket contains all of the information of all of its children's buckets - meaning the root node of the global quadtree is equivalent to the unfiltered global network. Nodes pick a depth and concern themselves with the bucket at that depth, unless it overflows, in which case they increase the depth by 1.

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

If you mean "Lightning Network Node", then how can lookup proceed if a node that should be looked through at some step is brought down by a targeted DDoS?
What happens if a node near the root of the tree, which is handling lookup for much more of the network, is brought down?
In my mechanism, the answer is: you try another node, and as long as that node has a dist(that node, target node) lower than yours, the algorithm will progress.
This is because in my mechanism, each node does not have some fixed set of 4 other nodes that are the only nodes referred to when doing lookup.

If you mean in-memory node, then I do not see how relevant it is, the structure that some implementation uses.
You can use a bag, set, tree, or whatever base structure.
But the number of Lightning Network nodes and channels any one node can store is finite since the memory available to that node is finite.
The issue is how to get help from some other node(s) when the target node is not in your routemap.

--

Any tree structure is, looking only at the nodes and edges, indistinguishable from a hierarchy.
And takeovers of hierarchies are simple: simply attack the easiest target near the top of the hierarchy / root of the tree.
Hierarchies are excessively centralized and we should avoid them on the public network in order to prevent attacks.
Thus I consider my proposal much more resilient compared to yours.

One might say, that my approach creates a circle where all nodes are equal, and where the removal of some node is survivable.
Or: ZmnSCPxj and the nodes of the round table.

> > I can overload those N nodes by generating node addresses that also lie in that octant.
> > By just iterating over scalars, about 1/8 of the generated node addresses will lie in the target octant.
>
> If you target the first layer of the tree only, then once nodes spill to the second layer, they will filter out any gossip which does not concern them. It isn't sufficient to just brute force the first 2 bits, but you need to do it for 2^depth, where depth is the target's maximum they're willing to spill to (which is not shared).
> However, commodity hardware can attempt millions of ec_mult/hash per second, so getting a node into the bucket you want is trivial anyway for small depth.
>
> > In order to disrupt a particular node, I must place fake nodes near that node, in an attempt to force its neighbors to reduce the arc of the circle that they can map.
> > However, I need to generate fake nodes that are nearer to that node than genuine honest nodes.
> > This means the probability of me generating such node addresses are much lower than 1/8, thus requiring that I devote more energy to generating the falsified attack nodes.
>
> I would argue that the above is also true in your approach. It would still be trivial to brute force the prefixes which minimize the distance between themselves and the target, even with a network of tens of millions of nodes. The amount of energy which would need devoting does not seem like it would a deciding factor for this attack.

The issue is not how difficult to attack a single node is.

The issue is: it should be easier to attack a single node, than to attack several nodes simultaneously.
This is how all things should be.

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.

The rest of your argument only answers the specific problem I brought up.
But the issue is simply this:

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

In my approach, there is no tree, and therefore each node is far less important.

Regards,
ZmnSCPxj