What's the most number of nodes you'll have to check to find a path?
The max you'll have to search is the total that exist. You're not going to check the same one multiple times.
So: If you have a partial mesh where each
/1
node is connected to 10 other nodes, and your shortest path is 20 hops.
The average number of nodes would be (10^20)/2 [On average, you'd only check half the last hop)
So, that means you'd check 100,000,000,000,000,000,000 nodes, right?
*WRONG*
If there are 4 billion nodes
That means, at MOST, you'd check only 4B. You don't check the same ones multiple times.
So, how long would it take a modern computer to process this?
1 Ghz = 1 Billion cycles per second.
So, a Six core 4 GHz processor has 24 BILLION cycles per SECOND.
The next question, which is unknown, and can be optimized...
How many cycles does it take to process a single path of a single node, when optimized?
No idea, and doubt there is a known answer yet.
So, lets just say it takes 600 cycles, and there are 8 Billion nodes and
you literally search every single one of them. How much time would that take?
200 seconds. That's about 3 minutes to check every single path on the planet with 8,000,000,000 nodes.
When you take into account natural hubs (vendors) that number drops dramatically.
Since each hop adds exponentially, you can search from both ends until you find a node in common, and it cuts the EXPONENT in half.
If each node has 8 connections, it's extremely likely you'll find a path within 10 hops.
So, the formula for nodes searches is (8^10)/2 for
average.
However, if you search from both ends, you cut the exponent in half, and x2 the entire thing.
2[8^(10/2)]/2 which simplifies to 8^5. Instead of having to check 4B, you'll only have to check 32,768 before finding a path. [Assuming one exists within 10 hops]
Using the above math, I have demonstrated that even with billions of nodes running #LightningNetwork, a modern day computer will be able to successfully find multiple 10 hop paths in a fraction of a second.
#BTC #BCH #Bcash