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 

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.


(PS, sorry for the separate thread, LML will not let me subscribe to the list)
Lightning-dev mailing list

Reply via email to