What is the Big-O for LN bandwidth? Can anyone answer this or provide a link to a spec that is sufficient enough for us to calculate it?

Question

When I worked at Google, if someone wanted to deploy a network application they would need to provide a document to the SREs detailing the behaviour of the application at scale in terms of Big-O. Does something like this exist for LN?

I understand that we would have to make some assumptions about the network topology, that's fine. What I really need to know is simply what are all the network functions and when do they fire.

Answer 1

This is an excellent question but still probably a little bit under specified. Let me try to give an answer and elaborate.

When looking at network bandwidth there are several componants playing into it.

The most obvious (and probably most dominant) one is specified in BOLT 07 routing-gossip. There are 4 messages which are used to provide the information about the gossip protocol to every node.

• The announcement_signatures Message
• The channel_announcement Message
• The node_announcement Message
• The channel_update Message

While the first one is only sent between two peers to decide if a channel stays private or not the second and third needs to be delivered to every node. The way how gossip achieves this is by forwarding the message to each peer if it was received and novel to the node. The amortized / expected network bandwidth for those messages should thus be O(E/V*(E+V)) where E/V ist the average node degree. And E the number of edges and V the number of nodes. In the worst case (unrealistic) of a fully connected graph we have E=V*V and thus O(V^3 + V^2) = O(V^3)

The situation is even worse for the 4th message. Everytime the routing fees are adjusted by a node this message needs to be delivered to every other node and creates O(E/V*(E)) messages. While the 3rd and 4th message will only be propagated when received first. The update message can be send every second and will be propagated Everytime. This the network bandwidth req can be arbitrary (? Still bound by the second) large even for small networks. This is obviously also a ddos attack vector. There is the million channel challenge by rusty to stimulate this behavior.

Other less dominant components are messages that are only exchanged between peers to maintain the channel state. While connecting, handshakes etc seem neglictable there is the case of routing. Let us in a first step assume that every routing process is successful the bandwidth will then grow as O(b*t) with t being the number of transactions or payments being done by the network and b being the betweeness centrality of the node on the fee graph which according to this video is likelihood of that node being on a cheapest path. This would have to be corrected by the likelihoid of routing failures. For the overall network it could be the product of number of transactions times average Pathlenght times average number of routing attempts.

There is also the network bandwidth coming from the Bitcoin node but that should not change with the growth of lightning.

I hope I didn't miss anything. Stuff changes drastically with AMP routing since every payment is split into several small payments.