Flash layer: Implement path-finding algorithm

[AndrejMitrovic]

There are several well-known path-finding algorithms with 100% success rate (but may not be the most efficient).

This is a good starting point: https://medium.com/@renepickhardt/evaluating-path-finding-strategies-on-the-lightning-network-238fe2fdf3d6

Some of the algorithms mentioned are:

• HushRelay
• Ant Routing
• Trampoline Routing

Please also consult this book for useful information (and also other chapters):

• https://github.com/lnbook/lnbook/blob/develop/03_how_ln_works.asciidoc

[AndrejMitrovic]

Since currently the flash layer is WIP, there are still some parts missing:

• gossiping of open channels is missing
• emitting channel fees is missing (also part of gossiping)

But we can still proceed with research and even prototyping. You can think of the necessary data structures as being the following:

struct Channel
{
    // fee paid for routing through this specific channel
    Amount fee;
    // total capacity is owner_amount + dest_amount
    Amount owner_amount;
    Amount dest_amount;
    Hash owner;
    Hash dest;
}

struct FlashNode
{
    Channel[Hash] known_channels;
}

Then, consider an example channel layout:

A -> B -> C -> D -> E
  \                /
   -----> F ----> G

If A wants to send a micro-transaction to E, then he is responsible for creating the entire path before actually routing the packet across that path. He needs to take several things into account:

• The amount he's trying to send. If it's too big to fit through a specific channel (because it lacks capacity) then it obviously cannot select that channel path.
• The amount of total channel hops for a path. The less hops the better. The more hops, the greater chance of failing to route a micro-transaction (node could become offline, for example)
• Fees are paid for every channel. That means A -> B, B -> C, C -> D, D -> E, in these cases A needs to prepare the fees for B, C, and D. It's in A's best interest to pay as little fee as possible. But, a route with a smaller fee could in theory be a route with too many hops - although typically the opposite is true.

Hopefully I'll finish #1419 soon and the actual data structures will be there for you to use.

[omerfirmak]

What does owner_amount and dest_amount represent here?
I am assuming they are the initial deposits to the channel not the current balances?

[AndrejMitrovic]

They are the current balances. Initially there is only one output which spends back to the founder.

[omerfirmak]

How does a node know the latest distribution of all the channels though? Would not that need every payment to be public and gossiped?

Quoting the resources you posted here;

If we would start to gossip about balance information we would have to do so with every payment(attempt) and this would — besides the privacy implications — mean that every participant of the network has to be informed about every payment.

However, the balance information of all channels is not and cannot be known to all participants of the network. We need more innovative pathfinding strategies.

Or am I missing something?

[AndrejMitrovic]

How does a node know the latest distribution of all the channels though?

Yeah that's part of the problem. We only know the capacity for sure, but not necessarily the balance. So if we do have any balance information, it may not be up to date. Maybe the only thing we can do is attempt one path, and if there is not enough balance for a node to forward a payment then try a different path..

[omerfirmak]

struct Channel
{
    // fee paid for routing through this specific channel
    Amount fee;
    // total capacity is owner_amount + dest_amount
    Amount owner_amount;
    Amount dest_amount;
    Hash owner;
    Hash dest;
}

Apparently, owner and dest nodes can request different amount of fees for routing a payment through the channel. So this structure would not quite work. See https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md#routing-example

[AndrejMitrovic]

Yeah I haven't gotten around to tackling fees yet.

[AndrejMitrovic]

This is a dupe of #244 but I didn't notice it when writing the issue, so I'll close #244.

[omerfirmak]

This was addressed through a series of PRs. As I don't have any immediate plans for improvement, I am closing this issue.

#1611
#1633
#1670
#1672
#1712
#1719
#1724
#1730
#1731
#1795