Lightning Network: how to trace the path between the sending and receivin nodes?

[Avz]

As far as I understood the lightning network is a web of connected nodes that keep balances between them and when Alice wants to send btc to Dave she can update her balance with Bob (-1btc, for example) which will update his balance with Carol (-1btc as well, getting even), who will finally update her balance with Dave. If Dave closed all his channels now he would receive 1 btc more than he would had received before the transactions, while Alice would receive 1 btc less and Bob and Carol would not have their totals changed.
My question is: how do we find this route Alice-Bob-Carol-Dave? When Alice meets Dave they dont know what is the best path between their nodes, or even if there is one.

[achow101]

The Lightning Network has an entire Peer-to-Peer network protocol. Using that protocol, a node can ask its peers for channels that they have open and peers that they know about. Then the node can connect to those other peers (note that connecting does not mean that a channel was opened) and learn of their channels and peers. It can do this to build a graph of the entire network and then thus determine the best route.

Of course there are better ways to do to this with various shortest path algorithms that don't actually need to know the full graph.

[hv_]

The Lightning Network has an entire Peer-to-Peer network protocol. Using that protocol, a node can ask its peers for channels that they have open and peers that they know about. Then the node can connect to those other peers (note that connecting does not mean that a channel was opened) and learn of their channels and peers. It can do this to build a graph of the entire network and then thus determine the best route.

Of course there are better ways to do to this with various shortest path algorithms that don't actually need to know the full graph.

Cmon, and for a central graph the routing is trivial, but for a random distributed?

Its not solvable and so LN is limited to central ones, not even thinking of 'funding',  economical and regulative issues that are also strong fix point attractors for centralization.

[sjefdeklerk]

The Lightning Network has an entire Peer-to-Peer network protocol. Using that protocol, a node can ask its peers for channels that they have open and peers that they know about. Then the node can connect to those other peers (note that connecting does not mean that a channel was opened) and learn of their channels and peers. It can do this to build a graph of the entire network and then thus determine the best route.

Of course there are better ways to do to this with various shortest path algorithms that don't actually need to know the full graph.

So when I want to route money to someone, my software has to ping all of my channels, then have their channels ping theirs etc, every single time?

[pebwindkraft]

Cmon, and for a central graph the routing is trivial, but for a random distributed?
Its not solvable and so LN is limited to central ones, not even thinking of 'funding',  economical and regulative issues that are also strong fix point attractors for centralization.

strong statement - how do you know it's not solvable? Like the Fermat's theorem was not solvable? Or mankind can never fly? Or maybe just "currently it seems extremely difficult to find a solution for this topic"?
I am looking at BGP daemons, and the DNS system. They are exactly dealing with this same problem. And at the very low level RIPv1 was centralized, per design. Up until the time were networks decentralized, and BGP was developped. There are hubs everywhere in the world, there is no single, centralized hub. I imagine a similiar approach in Lightning. Would this still be called centralized? I don't think so...?

[hv_]

Cmon, and for a central graph the routing is trivial, but for a random distributed?
Its not solvable and so LN is limited to central ones, not even thinking of 'funding',  economical and regulative issues that are also strong fix point attractors for centralization.

strong statement - how do you know it's not solvable? Like the Fermat's theorem was not solvable? Or mankind can never fly? Or maybe just "currently it seems extremely difficult to find a solution for this topic"?
I am looking at BGP daemons, and the DNS system. They are exactly dealing with this same problem. And at the very low level RIPv1 was centralized, per design. Up until the time were networks decentralized, and BGP was developped. There are hubs everywhere in the world, there is no single, centralized hub. I imagine a similiar approach in Lightning. Would this still be called centralized? I don't think so...?

The sum of attractors (you've not addressed)  will kill it - its always about cooperative effects potentiating forces (some glues / polymer structures work that way).

Yes - if some genius might solve that math (only), it will be patented in a milli second - because SOOOO MANY need it.

[Anti-Cen]

Of course there are better ways to do to this with various shortest path algorithms that don't actually need to know the full graph.

Node discovery relays and some people argue that it cannot be done and it must be well complicated to calculate the
hops by the time you have to deal with fees and the reliability of intermittent nodes plus ensuring the nodes each have
sufficient balance in the ledgers to carry out the transaction.

I can only imagine the amount of code needed to make this happen so once again as was the case with mining coins
that lead on to CPU-Wars it seems to me like the solution is worse then the initial problem and from a performance
perspective this would be slow if hub/banks were all Alice, Bob, Peter and Paul

Every node for himself just to keep some academic dip sticks happy without more specialized nodes looks like a big mess
to me but if they want to proceed down this lightning route then maybe the need a cluster of routing servers (DNS Type thing)
with plenty of redundancy built in to the system.

Time here is critical because a route could be found but milliseconds later the balance sheets has changed and the funds are
no longer available to carry out the transaction and lets also remember we now have some centralization and transaction won't be in
this wonderful magic things called the public block-chain.

No wonder it taking them years to program this thing and its so hard to understand

[Kprawn]

Does it settle the tx once it found a complete route to the end point or does it settle the tx with every channel that it finds

towards the end point? When do you pay the tx fees for these transactions on these channels? I have seen some demos,

but it was end to end over a single channel. It can become quite complex over multiple hops over several channels. 

[Anti-Cen]

but it was end to end over a single channel. It can become quite complex over multiple hops over several channels. 

Yes it is complicated and Dave on the far end of the route might not be on-line for days at a time

Alice-------->Bob-------->Carol--------->Dave

"When Alice sends payment to Dave through Bob and Carol, she requests
from Dave hash(R) to use for this payment. Alice then counts the
amount of hops until the recipient and uses that as the HTLC expiry. In this
case, she sets the HTLC expiry at 3 days. Bob then creates an HTLC with
Carol with an expiry of 2 days, and Carol does the same with Dave with an
expiry of 1 day. Dave is now free to disclose R to Carol, and both parties will
likely agree to immediate settlement via novation with a replacement Commitment
Transaction. This then occurs step-by-step back to Alice. Note
that this occurs off-chain, and nothing is broadcast to the blockchain when
all parties are cooperative."

it uses a number of HTLC (Time locks) that locks up funds for both Bob and Dave
and they themselves need to set up multisigs private ledger settlement and disputes
can result in settlement going to arbitration and one side having to pay Miner fees
so here we have potential counter party risk.

if Bob and Carol are not major banking hubs with many inter connecting channels
to other major banks then a dispersed network like this even if we assume each person
always has two channels open would require at a guess something like 2,000 hops
so again we are being presented with a case that is not really relevant unless it only
covers a few streets if all the channels are bidirectional which is another pain in the bum
by itself.

See image http://forum.cryptolivecap.com/posts/m38-Lightning-Network#post38

IMHO even if we forget my love of bankers/miners this is not an elegant solution to
the problem of scaling and if I know it then they know it also so why are they doing this
because from what I can see the lightning network is a good system for international
banking but in this case the central bank become the Bitcoin block chain instead of the
FED, ECB or IMF

[achow101]

Cmon, and for a central graph the routing is trivial, but for a random distributed?

Its not solvable and so LN is limited to central ones,

... You know that path finding algorithms have existed for decades right? You know what decades of research has gone into path finding algorithms and quickly finding fast solutions, right? Have you considered that maybe some other thing has run into a similar problem with a large, distributed graph and having to find a good route from point A to B? Maybe something like Google Maps. Or maybe how the internet routes your packets. This is not a new problem, and there are known solutions to it. At this point in time, it's really not that hard to figure out how to quickly find an optimal route in a large, distributed graph. Literally decades of computer science research has been dedicated to this topic and applied to many large distributed graphs that you probably don't even think about.

not even thinking of 'funding',  economical and regulative issues that are also strong fix point attractors for centralization.

In what way do you think that those will attract centralization? The very design of LN makes it so that anyone, at any time, can create their own LN node that serves as a "hub". Even if LN does become centralized around a few large hubs (which I think is unlikely given how easy it is to create your own LN node that is a "hub"), those hubs cannot be a central authority that can take away people's money or force channels open or to never close like an actual central authority can. The user is still in charge of his own money and he can always close a channel unilaterally to access his money.

So when I want to route money to someone, my software has to ping all of my channels, then have their channels ping theirs etc, every single time?

No, that would be horribly inefficient. Your LN node stores locally all of the channel information that it knows about. When a channel is updated, that node will announce to the rest of the network that that channel was updated, so all nodes will update their local knowledge of the network graph.

[RGBKey]

Cmon, and for a central graph the routing is trivial, but for a random distributed?

Its not solvable and so LN is limited to central ones,

... You know that path finding algorithms have existed for decades right? You know what decades of research has gone into path finding algorithms and quickly finding fast solutions, right? Have you considered that maybe some other thing has run into a similar problem with a large, distributed graph and having to find a good route from point A to B? Maybe something like Google Maps. Or maybe how the internet routes your packets. This is not a new problem, and there are known solutions to it. At this point in time, it's really not that hard to figure out how to quickly find an optimal route in a large, distributed graph. Literally decades of computer science research has been dedicated to this topic and applied to many large distributed graphs that you probably don't even think about.

Hail Dijkstra! Seriously, a lot of people here are throwing around "LN is centralized" and "it's the same thing as using banks". That's not how this works. That's not how any of this works.

[Anti-Cen]

In what way do you think that those will attract centralization? The very design of LN makes it so that anyone, at any time, can create their own LN node that serves as a "hub". Even if LN does become centralized around a few large hubs (which I think is unlikely given how easy it is to create your own LN node that is a "hub"), those hubs cannot be a central authority that can take away people's money or force channels open or to never close like an actual central authority can. The user is still in charge of his own money and he can always close a channel unilaterally to access his money.

That's like saying you are free to close your back account at a cost of $30 therefore it not centralized when it is all based around
central banking.

Routeing without big central hubs in a disbursed network looks almost impossible to me if
most people only open one channel and even if I wanted to do the banks out of a job by
becoming one myself then without 60,000BTC to deposit in various channels I cannot do it
no more than you can open a regular high street bank.

if I could move money between various ledgers that I hold open without paying crazy
miner fees then it becomes half possible  if the muiltsig time outs are low and not much
money is held up in transit.

You say "The user is still in charge of his own money" yes so long as we keep paying miners
$30 a pop when we use it and the argument that fees will drop is speculation because Lightning
not designed to move what they term larger amount for the reasons I listed plus you now have
inter bank settlement to on the main BC

if I earn $200 a week as a cam-girl and I live hand to mouth then I need cash to spend in
the shops and the only way I can get BTC to USD is to close the channel to put coins on block
and then cash them in.

[Anti-Cen]

Hail Dijkstra! Seriously, a lot of people here are throwing around "LN is centralized" and "it's the same thing as using banks". That's not how this works. That's not how any of this works.

That is exactly how it works or we would not have deposits of BTC in channels  and the killer
is that money does not cross between private ledgers and you can pick it out from the white-paper
here https://lightning.network/lightning-network-paper.pdf
or see the image that i uploaded here http://forum.cryptolivecap.com/posts/t31-Lightning-Network

and without large central banking hubs your routes end to end would need hundreds of hops and
and involve hundreds of muilisig internal transactions that would be a nightmare to roll back if
just one of the nodes went off-line during the process

You seem to forget that channels cost money to close so I am only going to open one at a time
and that's going to be to someone that has lots of money on deposit and is always connected so
is that not centralized and even now we are hearing about money lost in transit on the BTC
network so whats going to happen if a banking hub goes down and everyone broadcasts a
signal to force settlement on the main BTC BC

When real banks screw up I can pick the phone up so was the above to happen then who are you
going to call

[Kprawn]

Hail Dijkstra! Seriously, a lot of people here are throwing around "LN is centralized" and "it's the same thing as using banks". That's not how this works. That's not how any of this works.

That is exactly how it works or we would not have deposits of BTC in channels  and the killer
is that money does not cross between private ledgers and you can pick it out from the white-paper
here https://lightning.network/lightning-network-paper.pdf
or see the image that i uploaded here http://forum.cryptolivecap.com/posts/t31-Lightning-Network

and without large central banking hubs your routes end to end would need hundreds of hops and
and involve hundreds of muilisig internal transactions that would be a nightmare to roll back if
just one of the nodes went off-line during the process

You seem to forget that channels cost money to close so I am only going to open one at a time
and that's going to be to someone that has lots of money on deposit and is always connected so
is that not centralized and even now we are hearing about money lost in transit on the BTC
network so whats going to happen if a banking hub goes down and everyone broadcasts a
signal to force settlement on the main BTC BC

When real banks screw up I can pick the phone up so was the above to happen then who are you
going to call

You should not be invested in Crypto currencies if you cannot go without centralized third parties managing your money on

your behalf. Bitcoin was not meant to emulate Banks. The opening and closing of channels should be straight forward, but

I agree with you that there should be a "fail safe" built into the solution to resolve possible problems. I was under the

impression that "time-out" thresholds was built into Lightning Network to protect against "Loop" problems. 

[Anti-Cen]

impression that "time-out" thresholds was built into Lightning Network to protect against "Loop" problems.  

Broadcast for settlement is in on the Lightning Network and fees on the LN network would prevent
loop back attacks but the trade of is expensive fees for legitimate micro-transactions but I don't have
a clue why you brought this up

Time outs in LN muiltsig accounts are called Hash Time Locks (HTLC)  but I can talk a bit slower
for you if that helps or maybe you could read the document at your own pace