zmnscpxj / zmnscpxj.github.io Goto Github PK

In Cyclic Superhubs as Solution Towards Reasonable Lightning Network Topology you write:

Encouraging cyclic superhubs encourages the formation of a grid-like network, which has the major advantage of having many alternate routes between different points.

Do you think the inverse is also true - that grid-like networks naturally form these "cyclic superhubs"? Perhaps it would it require the additional property that the topology is stable across connects and disconnects so that e.g. two nodes which previously connected will re-connect again if one of them goes offline and then comes back on again?

You also write:

Unfortunately some amount of coordination is needed to form superhubs in the first place. The nodes who want to form a superhub need to agree on which node creates channels to which other node.

If it was possible for the coordination to be algorithmic I guess it would be more socially scalable. If it's possible for nodes to form grid-like topologies which are relatively stable and persist across connects and disconnects I think it would bring the same advantages as manually created cyclic superhubs. I think I've got a solution to this which is below.

Context: a similar problem of building grid-like topologies of well-connected peers is discussed by Arvid Norberg in the context of Bittorrent swarms in swarm connectivity. The solution he proposes is:

One way to ensure evenly distributed connections is to come up with a globally-agreed upon connection ranking function. The function would take two endpoints and return the priority of those two peers having a connection.

So whether two peers decide to connect or not depends on the "distance" between them according to the globally agreed upon connection ranking function (distance metric). Later he suggests using IP addresses which are relatively hard to choose, in the ranking function, and also some attacks against this model.

I don't know how widely adopted this suggestion has been in Bittorrent clients but the Bittorrent DHT (peer and torrent discovery overlay network) uses such a connection ranking function in the Kademlia implementation in that queries are routed according to "closeness" of nodes by XOR of peer ID with target. So it's the same idea as Arvid discusses above and it works very well in that existing system of 10s of millions of nodes.

Despite working well in the DHT the main issue with a global ranking function with randomly selected (or IP address selected) node IDs used to measure "closeness" is that it's vulnerable to a class of attack I guess you'd call "sybil gangs" where an attacker can create many nodes with peer IDs (or IP addresses) clustered around their victim and completely isolate them from the grid. Once they've done this they can block/delay messages etc. I think the Bittorrent DHT is vulnerable to this attack as nodes can simply specify whatever "random" node ID they like. Even worse, they can easily see the peer ID of the victim so they don't even have to brute-force it. Manually created cyclic superhubs avoid this of course, but with the down-side of requiring out-of-band coordination by people.

However I think it's possible to make the global ranking function or closeness metric difficult to game by securing it with cryptography. I am not sure if it's original or not but my idea to avoid "sybil gangs" is to use simple public key cryptography to make it very difficult for an attacker to pick IDs in such a way that they can form such gangs around, or even next to, any other node.

It works as follows:

• Imagine node X is joining the network and knows of existing bootstrap node Y.
• Each node has a keypair (which they often do anyway as in the case of lightning network).
• They then sign each-other's public key (plus maybe some salt) to generate a unique ID for me-to-you connection. The signature itself replaces the peer ID or IP address in the Bittorrent scheme.
• As with Arvid's suggestion they then use the ranking function on those two signatures to determine their "closeness" in the distance metric / global ranking function. This closeness tells them whether or not to connect, depending on their existing connections.
• If node X is further away from node Y than its existing connections according to this distance metric then node Y should send a list of its own nodes to node X so that it can continue on and try to connect with each of them in turn.
• By repeating this process node X will eventually find nodes for which it is mutually the "closest" and be connected into its place in the network.
• Any node which goes offline and comes back on again later should be inserted back into a relatively similar spot (connected to the same nodes as before) preserving any cycles which were there previously.

An attacker can try to game this scheme by generating very many keypairs until they get "close" to their victim, but they obviously do not know what the result of the signature will be as they don't have the other node's private key. This is much harder to game than simple randomly generated node IDs and requires interaction with the victim which is quite easily detectable. Additionally it produces a stable topography given stable key pairs because the signatures of public keys will always produce the same resulting IDs for the distance metric.

A legitimate node can also use the signature to verify that the node they are connecting to is being honest about its own ID (by checking the signature with the other node's public key). Finally, if a node finds itself in a bad spot in the network, only connected to dodgy peers for whatever reason, it can simply choose a new key pair and move away to a different location in the grid.

So in short, I think with a scheme like this it's possible to have nodes form grid-like and stable topologies across connects and disconnects bringing many of the same advantages as cyclic superhubs, but with greater socially scalability as it does not require the humans running nodes to cooperate out-of-band.

Keen to hear what you think!

Of unchained https://zmnscpxj.github.io/bitcoin/unchained.html