Re: [Lightning-dev] Proposal for syncing channel updates

2018-10-12 Thread Fabrice Drouin
Hi Zmn,

> It may be reduced to a set reconciliation problem if we consider the 
> timestamp and enable/disable state of channel updates as part of an item, 
> i.e. a channel update of 111:1:1 at 2018-10-04 state=enabled is not the same 
> as a channel update of 111:1:1 at 2018-10-05 state=disabled.
>
> Then both sides can use standard set reconciliation algorithms, and for 
> channel updates of the same short channel ID, we simply drop all items except 
> the one with latest timestamp.
>
> The above idea might be less efficient than your proposed extension.

Yes there may be some way use the structure of channel_update messages
to transpose this into a set reconciliation problem, and use smarter
tools like IBLTs. But we would need to have a good estimate for the
number of differences between the local and remote sets. This would be
the really hard part I think, and probably even harder to get right
with channel_updates than with channel_announcements. I had a quick
look at how this type of sync issue is handled in different contexts
and my impression is that exchanging and and comparing timestamps
would be the most natural solution ?

But mostly my point is that I think we missed something with the
current channel queries, so first I would like to know if other people
agree with that :) and propose something that is close to what we have
today, should be easy to implement if you already support channel
queries, and should fix the issue that I think we have.

Thanks,
Fabrice
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Proposal for syncing channel updates

2018-10-05 Thread ZmnSCPxj via Lightning-dev
Good Morning Fabrice,

Without objecting to the rest of your email (which I have not read and thought 
about extensively):

>And it is not
> really a set reconciliation problem (like syncing channel
> announcements for example): we’re not missing items, we’re missing
> updates for existing items.

It may be reduced to a set reconciliation problem if we consider the timestamp 
and enable/disable state of channel updates as part of an item, i.e. a channel 
update of 111:1:1 at 2018-10-04 state=enabled is not the same as a channel 
update of 111:1:1 at 2018-10-05 state=disabled.

Then both sides can use standard set reconciliation algorithms, and for channel 
updates of the same short channel ID, we simply drop all items except the one 
with latest timestamp.

The above idea might be less efficient than your proposed extension.

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] Proposal for syncing channel updates

2018-10-04 Thread Fabrice Drouin
Hi,

This a a proposal for an extension of our current “channel queries”
that should allow nodes to properly sync their outdated channel
updates. I already opened a issue on the RFC’s github repo
(https://github.com/lightningnetwork/lightning-rfc/issues/480) but
decided to post here too to, to have a less “constrained” discussion.
And it looks like a fairly standard synchronisation problem so maybe
someone will think of others similar schemes that have been used in a
different context.

Thanks,

Fabrice

Background: Routing Table Sync

(If you’re familiar with LN you can just skip this section)

LN is a p2p network of nodes, which can be represented as a graph
where nodes are vertices and channels are edges, and where you can pay
any node you can find a route to:
- each nodes maintains a routing table i.e. a full view of the LN graph
- to send a payment, nodes use their local routing table to compute a
route to the destination, and send a onion-like message to the first
node on that route, which will forward it to the next node and so on
until it reaches its destination

The routing table includes:
- “static” information: channel announcements
- “dynamic” information: channel updates (relay fees)
(It also includes node announcements, which are not needed for route
computation)
Using our graph analogy, channel updates would be edge parameters
(cost, max capacity, min payment amount, …). They can change often,
usually when nodes decide to change their relay fee policy, but also
to signify that a channel is temporarily unusable. A new channel
update will replace the previous one.

Channel ids are identified with an 8 bytes "short transaction id": we
use the blockchain coordinates of the funding tx: block height (4
bytes) + tx index (2 bytes) + output index (2 bytes)

Chanel updates include a channel id, a direction (for a channel
between Alice and Bob there are 2 channel updates: one for Alice->Bob
and one for Bob->Alice), fee parameters, and a 4 bytes timestamp.

To compute routes, nodes need a way to keep their routing table
up-to-date: we call it "routing table sync" or "routing sync".

There is something else to consider: route finding is only needed when
you're * sending * payments, not when you're relaying them or
receiving them. A node that sits in the "middle" of the LN network and
just keeps relaying payments would work even if it has no routing
information at all.

Likewise, a node that just creates payment requests and receives
payments does not need a routing table.

On the other end of the spectrum, a LN "wallet" that is mostly used to
send payments will not work very well it its routing table is missing
info or contains outdated info, so routing sync is a very important
issue for LN wallets, which are also typically offline more often than
other nodes.

If your wallet is missing channel announcements it may not be able to
find a route, and if its channel updates are outdated it may compute a
route that includes channels that are temporarily disabled, or use fee
rates that are too old and will be refused by relaying nodes. In this
case nodes can return errors that include their most recent channel
update, so that the sender can try again, but this will only work well
if just a few channel updates are outdated.

So far, these are the “routing table sync” schemes that have been
specified and implemented:

Step #1: just send everything

The first routing sync scheme was very simple: nodes would request
that peers they connect to send them a complete "dump" of their entire
routing table. It worked well at the beginning but was expensive for
both peers and quickly became impractical.

Step #2: synchronise channel announcements

New query messages where added to the LN protocol to improve routing
table sync: nodes can ask their peers for all their channel ids in a
given block range, compare that list to their own channel ids and
query the ones they're missing (as well as related channel updates).

Nodes can also send a timestamp-based filter to their peers ("only
send me  channel updates that match this timestamp filter").

It's a nice improvement but there are still issues with nodes that are
offline very often: they will be able to sync their channel
announcements, but not their channel updates.

Suppose that at T0 a node has 1000 channel updates that are outdated.
It comes back online, starts syncing its routing table, and goes
offline after a few minutes. It now has 900 channel updates that are
outdated.
At T1 = T0 + 8 hours it comes back online again. If it uses T0 to
filter out channel updates, it will never receive the info it is
missing for its 900 outdated channel updates. Using our "last time I
was online at" timestamp as a gossip filter does not work here.

=> Proposed solution: timestamp-based channel updates sync

We need a better method for syncing channel updates. And it is not
really a set reconciliation problem (like syncing channel
announcements for example): we’re not missing items,