[Lightning-dev] Improving the initial gossip sync: DRAFT

[Rusty Russell]

https://github.com/lightningnetwork/lightning-rfc/pull/392

I'll append to this as suggestions come in.  I'm trying to find some
cycles to implement it too.

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

Re: [Lightning-dev] Improving the initial gossip sync

[Rusty Russell]

Fabrice Drouin  writes:
> On 20 February 2018 at 02:08, Rusty Russell  wrote:
>> Hi all,
>>
>> This consumed much of our lightning dev interop call today!  But
>> I think we have a way forward, which is in three parts, gated by a new
>> feature bitpair:
>
> We've built a prototype with a new feature bit `channel_range_queries`
> and the following logic:
> When you receive their init message and check their local features
> - if they set `initial_routing_sync` and `channel_range_queries` then
> do nothing (they will send you a `query_channel_range`)
> - if they set `initial_routing_sync` and not `channel_range_queries`
> then send your routing table (as before)
> - if you support `channel_range_queries` then send a
> `query_channel_range` message

That seems logical; in this way, channel_range_queries obsoletes
initial_routing_sync.

>> 1. query_short_channel_id
>> =
>>
>> 1. type: 260 (`query_short_channel_id`)
>> 2. data:
>>* [`32`:`chain_hash`]
>>* [`8`:`short_channel_id`]
>
> We could add a `data` field which contains zipped ids like in
> `reply_channel_range` so we can query several items with a single
> message ?

We could, let's use the same compression format as we decide for the
`reply_channel_range` `data` field.

>
>> 1. type: 262 (`reply_channel_range`)
>> 2. data:
>>* [`32`:`chain_hash`]
>>* [`4`:`first_blocknum`]
>>* [`4`:`number_of_blocks`]
>>* [`2`:`len`]
>>* [`len`:`data`]
>
> We could add an additional `encoding_type` field before `data` (or it
> could be the first byte of `data`)

Yes, let's put it in first byte of data.

>> I tried various obvious compression schemes, in increasing complexity
>> order (see source below, which takes stdin and spits out stdout):
>>
>> Raw = raw 8-byte stream of ordered channels.
>> gzip -9: gzip -9 of raw.
>> splitgz: all blocknums first, then all txnums, then all outnums, 
>> then gzip -9
>> delta: CVarInt encoding: 
>> blocknum_delta,num,num*txnum_delta,num*outnum.
>> deltagz: delta, with gzip -9
>>
>> Corpus 1: LN mainnet dump, 1830 channels.[1]
>>
>> Raw: 14640 bytes
>> gzip -9: 6717 bytes
>> splitgz: 6464 bytes
>> delta: 6624 bytes
>> deltagz: 4171 bytes
>>
>> Corpus 2: All P2SH outputs between blocks 508000-508999 incl, 790844 
>> channels.[2]
>>
>> Raw: 6326752 bytes
>> gzip -9: 1861710 bytes
>> splitgz: 964332 bytes
>> delta: 1655255 bytes
>> deltagz: 595469 bytes
>>
>> [1] http://ozlabs.org/~rusty/short_channels-mainnet.xz
>> [2] http://ozlabs.org/~rusty/short_channels-all-p2sh-508000-509000.xz
>
> Impressive!

Which method did you prefer?  splitgz is trivial, deltagz is better but
requires some actual work.  We should pick one and make that `version
0`.

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

Re: [Lightning-dev] Improving the initial gossip sync

[Olaoluwa Osuntokun]

> With that said, this should instead be a distinct `chan_update_horizon`
> message (or w/e name). If a particular bit is set in the `init` message,
> then the next message *both* sides send *must* be `chan_update_horizon`.

Tweaking this a bit, if we make it: don't send *any* channel updates at all
unless the other side sends this message, then this allows both parties to
precisely control their initial load, and also if they even *want*
channel_update messages at all.

Purely routing nodes don't need any updates at all. In the case they wish to
send (assumed to be infrequent in this model), they'll get the latest update
after their first failure.

Similarly, leaf/edge nodes can opt to receive the latest updates if they
wish to minimize payment latency due to routing failures that are the result
of dated information.

IMO, the only case where a node would want the most up to date link policy
state is for optimization/analysis, or to minimize payment latency at the
cost of additional load.

--Laolu

On Fri, Feb 23, 2018 at 4:45 PM Olaoluwa Osuntokun 
wrote:

> Hi Rusty,
>
> > 1. query_short_channel_id
> > IMPLEMENTATION: trivial
>
> *thumbs up*
>
> > 2. query_channel_range/reply_channel_range
> > IMPLEMENTATION: requires channel index by block number, zlib
>
> For the sake of expediency of deployment, if we add a byte (or two) to
> denote the encoding/compression scheme, we can immediately roll out the
> vanilla (just list the ID's), then progressively roll out more
> context-specific optimized schemes.
>
> > 3. A gossip_timestamp field in `init`
> > This is a new field appended to `init`: the negotiation of this feature
> bit
> > overrides `initial_routing_sync`
>
> As I've brought up before, from my PoV, we can't append any additional
> fields to the innit message as it already contains *two* variable sized
> fields (and no fixed size fields). Aside from this, it seems that the
> `innit` message should be simply for exchange versioning information,
> which
> may govern exactly *which* messages are sent after it. Otherwise, by adding
> _additional_ fields to the `innit` message, we paint ourselves in a corner
> and can never remove it. Compared to using the `innit` message to set up
> the
> initial session context, where we can safely add other bits to nullify or
> remove certain expected messages.
>
> With that said, this should instead be a distinct `chan_update_horizon`
> message (or w/e name). If a particular bit is set in the `init` message,
> then the next message *both* sides send *must* be `chan_update_horizon`.
>
> Another advantage of making this a distinct message, is that either party
> can at any time update this horizon/filter to ensure that they only receive
> the *freshest* updates.Otherwise, one can image a very long lived
> connections (say weeks) and the remote party keeps sending me very dated
> updates (wasting bandwidth) when I only really want the *latest*.
>
> This can incorporate decker's idea about having a high+low timestamp. I
> think this is desirable as then for the initial sync case, the receiver can
> *precisely* control their "verification load" to ensure they only process a
> particular chunk at a time.
>
>
> Fabrice wrote:
> > We could add a `data` field which contains zipped ids like in
> > `reply_channel_range` so we can query several items with a single
> message ?
>
> I think this is an excellent idea! It would allow batched requests in
> response to a channel range message. I'm not so sure we need to jump
> *straight* to compressing everything however.
>
> > We could add an additional `encoding_type` field before `data` (or it
> > could be the first byte of `data`)
>
> Great minds think alike :-)
>
>
> If we're in rough agreement generally about this initial "kick can"
> approach, I'll start implementing some of this in a prototype branch for
> lnd. I'm very eager to solve the zombie churn, and initial burst that can
> be
> very hard on light clients.
>
> -- Laolu
>
>
> On Wed, Feb 21, 2018 at 10:03 AM Fabrice Drouin 
> wrote:
>
>> On 20 February 2018 at 02:08, Rusty Russell 
>> wrote:
>> > Hi all,
>> >
>> > This consumed much of our lightning dev interop call today!  But
>> > I think we have a way forward, which is in three parts, gated by a new
>> > feature bitpair:
>>
>> We've built a prototype with a new feature bit `channel_range_queries`
>> and the following logic:
>> When you receive their init message and check their local features
>> - if they set `initial_routing_sync` and `channel_range_queries` then
>> do nothing (they will send you a `query_channel_range`)
>> - if they set `initial_routing_sync` and not `channel_range_queries`
>> then send your routing table (as before)
>> - if you support `channel_range_queries` then send a
>> `query_channel_range` message
>>
>> This way new and old nodes should be able to understand each other
>>
>> > 1. query_short_channel_id
>> > 

Re: [Lightning-dev] Improving the initial gossip sync

[Olaoluwa Osuntokun]

Hi Rusty,

> 1. query_short_channel_id
> IMPLEMENTATION: trivial

*thumbs up*

> 2. query_channel_range/reply_channel_range
> IMPLEMENTATION: requires channel index by block number, zlib

For the sake of expediency of deployment, if we add a byte (or two) to
denote the encoding/compression scheme, we can immediately roll out the
vanilla (just list the ID's), then progressively roll out more
context-specific optimized schemes.

> 3. A gossip_timestamp field in `init`
> This is a new field appended to `init`: the negotiation of this feature
bit
> overrides `initial_routing_sync`

As I've brought up before, from my PoV, we can't append any additional
fields to the innit message as it already contains *two* variable sized
fields (and no fixed size fields). Aside from this, it seems that the
`innit` message should be simply for exchange versioning information, which
may govern exactly *which* messages are sent after it. Otherwise, by adding
_additional_ fields to the `innit` message, we paint ourselves in a corner
and can never remove it. Compared to using the `innit` message to set up the
initial session context, where we can safely add other bits to nullify or
remove certain expected messages.

With that said, this should instead be a distinct `chan_update_horizon`
message (or w/e name). If a particular bit is set in the `init` message,
then the next message *both* sides send *must* be `chan_update_horizon`.

Another advantage of making this a distinct message, is that either party
can at any time update this horizon/filter to ensure that they only receive
the *freshest* updates.Otherwise, one can image a very long lived
connections (say weeks) and the remote party keeps sending me very dated
updates (wasting bandwidth) when I only really want the *latest*.

This can incorporate decker's idea about having a high+low timestamp. I
think this is desirable as then for the initial sync case, the receiver can
*precisely* control their "verification load" to ensure they only process a
particular chunk at a time.


Fabrice wrote:
> We could add a `data` field which contains zipped ids like in
> `reply_channel_range` so we can query several items with a single message
?

I think this is an excellent idea! It would allow batched requests in
response to a channel range message. I'm not so sure we need to jump
*straight* to compressing everything however.

> We could add an additional `encoding_type` field before `data` (or it
> could be the first byte of `data`)

Great minds think alike :-)


If we're in rough agreement generally about this initial "kick can"
approach, I'll start implementing some of this in a prototype branch for
lnd. I'm very eager to solve the zombie churn, and initial burst that can be
very hard on light clients.

-- Laolu


On Wed, Feb 21, 2018 at 10:03 AM Fabrice Drouin 
wrote:

> On 20 February 2018 at 02:08, Rusty Russell  wrote:
> > Hi all,
> >
> > This consumed much of our lightning dev interop call today!  But
> > I think we have a way forward, which is in three parts, gated by a new
> > feature bitpair:
>
> We've built a prototype with a new feature bit `channel_range_queries`
> and the following logic:
> When you receive their init message and check their local features
> - if they set `initial_routing_sync` and `channel_range_queries` then
> do nothing (they will send you a `query_channel_range`)
> - if they set `initial_routing_sync` and not `channel_range_queries`
> then send your routing table (as before)
> - if you support `channel_range_queries` then send a
> `query_channel_range` message
>
> This way new and old nodes should be able to understand each other
>
> > 1. query_short_channel_id
> > =
> >
> > 1. type: 260 (`query_short_channel_id`)
> > 2. data:
> >* [`32`:`chain_hash`]
> >* [`8`:`short_channel_id`]
>
> We could add a `data` field which contains zipped ids like in
> `reply_channel_range` so we can query several items with a single
> message ?
>
> > 1. type: 262 (`reply_channel_range`)
> > 2. data:
> >* [`32`:`chain_hash`]
> >* [`4`:`first_blocknum`]
> >* [`4`:`number_of_blocks`]
> >* [`2`:`len`]
> >* [`len`:`data`]
>
> We could add an additional `encoding_type` field before `data` (or it
> could be the first byte of `data`)
>
> > Appendix A: Encoding Sizes
> > ==
> >
> > I tried various obvious compression schemes, in increasing complexity
> > order (see source below, which takes stdin and spits out stdout):
> >
> > Raw = raw 8-byte stream of ordered channels.
> > gzip -9: gzip -9 of raw.
> > splitgz: all blocknums first, then all txnums, then all outnums,
> then gzip -9
> > delta: CVarInt encoding:
> blocknum_delta,num,num*txnum_delta,num*outnum.
> > deltagz: delta, with gzip -9
> >
> > Corpus 1: LN mainnet dump, 1830 channels.[1]
> >
> > Raw: 14640 bytes
> > gzip -9: 6717 bytes
> >   

Re: [Lightning-dev] Improving the initial gossip sync

[Fabrice Drouin]

On 20 February 2018 at 02:08, Rusty Russell  wrote:
> Hi all,
>
> This consumed much of our lightning dev interop call today!  But
> I think we have a way forward, which is in three parts, gated by a new
> feature bitpair:

We've built a prototype with a new feature bit `channel_range_queries`
and the following logic:
When you receive their init message and check their local features
- if they set `initial_routing_sync` and `channel_range_queries` then
do nothing (they will send you a `query_channel_range`)
- if they set `initial_routing_sync` and not `channel_range_queries`
then send your routing table (as before)
- if you support `channel_range_queries` then send a
`query_channel_range` message

This way new and old nodes should be able to understand each other

> 1. query_short_channel_id
> =
>
> 1. type: 260 (`query_short_channel_id`)
> 2. data:
>* [`32`:`chain_hash`]
>* [`8`:`short_channel_id`]

We could add a `data` field which contains zipped ids like in
`reply_channel_range` so we can query several items with a single
message ?

> 1. type: 262 (`reply_channel_range`)
> 2. data:
>* [`32`:`chain_hash`]
>* [`4`:`first_blocknum`]
>* [`4`:`number_of_blocks`]
>* [`2`:`len`]
>* [`len`:`data`]

We could add an additional `encoding_type` field before `data` (or it
could be the first byte of `data`)

> Appendix A: Encoding Sizes
> ==
>
> I tried various obvious compression schemes, in increasing complexity
> order (see source below, which takes stdin and spits out stdout):
>
> Raw = raw 8-byte stream of ordered channels.
> gzip -9: gzip -9 of raw.
> splitgz: all blocknums first, then all txnums, then all outnums, then 
> gzip -9
> delta: CVarInt encoding: 
> blocknum_delta,num,num*txnum_delta,num*outnum.
> deltagz: delta, with gzip -9
>
> Corpus 1: LN mainnet dump, 1830 channels.[1]
>
> Raw: 14640 bytes
> gzip -9: 6717 bytes
> splitgz: 6464 bytes
> delta: 6624 bytes
> deltagz: 4171 bytes
>
> Corpus 2: All P2SH outputs between blocks 508000-508999 incl, 790844 
> channels.[2]
>
> Raw: 6326752 bytes
> gzip -9: 1861710 bytes
> splitgz: 964332 bytes
> delta: 1655255 bytes
> deltagz: 595469 bytes
>
> [1] http://ozlabs.org/~rusty/short_channels-mainnet.xz
> [2] http://ozlabs.org/~rusty/short_channels-all-p2sh-508000-509000.xz
>

Impressive!
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] Improving the initial gossip sync

[ZmnSCPxj via Lightning-dev]

Good morning Rusty,

​>4. query_short_channel_id
> =
>
>
>5. type: 260 (query_short_channel_id)
>
>6. data: 
> - [32:chain_hash]
>
> - [8:short_channel_id]
>
> This is general mechanism which lets you query for a
> channel_announcement and channel_updates for a specific 8-byte shortid.
> The receiver should respond with a channel_announce and the latest
> channel_update for each end, not batched in the normal 60-second gossip
> cycle.
>
> A node MAY send this if it receives a channel_update for a channel it
> has no channel_announcement, but SHOULD NOT if the channel referred to
> is not an unspent output (ie. check that it's not closed before sending
> this query!).

Is the SHOULD NOT something the sender can assure?  In the case that the sender 
is a lightweight Bitcoin node, and does not keep track of a mempool, and only 
notices closes if they have been confirmed onchain, it may be possible that the 
sender thinks the channel is still possibly open, while the receiver is a full 
Bitcoin node and has seen the closing transaction of the channel on the 
mempool.  There are also race conditions where the sender has not received a 
new block yet, then sends the message, and the receiver receives/processes the 
message after it has received a new block containing the closing transaction.

Perhaps there should also be a possible reply to this message which indicates 
"short_channel_id so-and-so was closed by txid so-and-so".

Or maybe receivers should not rely on this "SHOULD NOT" and will have to 
silently ignore `query_short_channel_id` that it thinks is closed; this also 
implies that the sender cannot rely on getting information on the specified 
channel from anyone, either.

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

Re: [Lightning-dev] Improving the initial gossip sync

[Rusty Russell]

Hi all,

This consumed much of our lightning dev interop call today!  But
I think we have a way forward, which is in three parts, gated by a new
feature bitpair:

1. A query message for a particular shortid.
2. A query message for shortids in a range of blocks.
3. A gossip_timestamp field in `init`

I think these will still be desirable even when we have a more complex
scheme in future.

1. query_short_channel_id
=

1. type: 260 (`query_short_channel_id`)
2. data:
   * [`32`:`chain_hash`]
   * [`8`:`short_channel_id`]

This is general mechanism which lets you query for a
channel_announcement and channel_updates for a specific 8-byte shortid.
The receiver should respond with a channel_announce and the latest
channel_update for each end, not batched in the normal 60-second gossip
cycle.

A node MAY send this if it receives a `channel_update` for a channel it
has no `channel_announcement`, but SHOULD NOT if the channel referred to
is not an unspent output (ie. check that it's not closed before sending
this query!).

IMPLEMENTATION: trivial

2. query_channel_range/reply_channel_range
==
This is a new message pair, something like:

1. type: 261 (`query_channel_range`)
2. data:
   * [`32`:`chain_hash`]
   * [`4`:`first_blocknum`]
   * [`4`:`number_of_blocks`]

1. type: 262 (`reply_channel_range`)
2. data:
   * [`32`:`chain_hash`]
   * [`4`:`first_blocknum`]
   * [`4`:`number_of_blocks`]
   * [`2`:`len`]
   * [`len`:`data`]

Where data is a series of ordered shortids (see Appendix A for various
encodings).  `number_of_blocks` in the reply may be less than in the
request of the required data did not fit; it is assumed that we can fit
a single block per reply, at least.

IMPLEMENTATION: requires channel index by block number, zlib

3. gossip_timestamp.


This is useful for the simple case of a node reconnecting to a single
peer, for example.  This is a new field appended to `init`: the
negotiation of this feature bit overrides `initial_routing_sync` as the
same results can be obtained by setting the `gossip_timestamp` field to
the current time (for no initial sync) or 0 (for an initial sync).

Note that a node should allow for some minutes of propagation time, thus
set the `gossip_timestamp` to sometime before its last seen gossip
message.  It may also receive `channel_update` messages for which it has
not seen the `channel_announcement` and thus use 

IMPLEMENTATION: easy.

Appendix A: Encoding Sizes
==

I tried various obvious compression schemes, in increasing complexity
order (see source below, which takes stdin and spits out stdout):

Raw = raw 8-byte stream of ordered channels.
gzip -9: gzip -9 of raw.
splitgz: all blocknums first, then all txnums, then all outnums, then 
gzip -9
delta: CVarInt encoding: blocknum_delta,num,num*txnum_delta,num*outnum.
deltagz: delta, with gzip -9

Corpus 1: LN mainnet dump, 1830 channels.[1]

Raw: 14640 bytes
gzip -9: 6717 bytes
splitgz: 6464 bytes
delta: 6624 bytes
deltagz: 4171 bytes

Corpus 2: All P2SH outputs between blocks 508000-508999 incl, 790844 
channels.[2]

Raw: 6326752 bytes
gzip -9: 1861710 bytes
splitgz: 964332 bytes
delta: 1655255 bytes
deltagz: 595469 bytes

[1] http://ozlabs.org/~rusty/short_channels-mainnet.xz
[2] http://ozlabs.org/~rusty/short_channels-all-p2sh-508000-509000.xz

Appendix B: Encoding Sourcecode
===
// gcc -g -Wall -o encode-short_channel_ids encode-short_channel_ids.c
#include 
#include 
#include 
#include 

/* BOLT #1:
 * All data fields are big-endian unless otherwise specified. */
static void write_bytes(uint32_t val, int n)
{
/* BE, so write out tail */
uint32_t v = htonl(val);

fwrite((char *) + (4 - n), n,  1, stdout);
}

/* CVarInt from bitcoin/src/serialize.h:
// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2016 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 */
static void write_varint(uint32_t n)
{
unsigned char tmp[(sizeof(n)*8+6)/7];
int len=0;
while (1) {
tmp[len] = (n & 0x7F) | (len ? 0x80 : 0x00);
if (n <= 0x7F)
break;
n = (n >> 7) - 1;
len++;
}
do {
fwrite([len], 1, 1, stdout);
} while(len--);
}

int main(void)
{
size_t n, max = 1024;
uint32_t *block = malloc(max * sizeof(uint32_t));
uint32_t *txnum = malloc(max * sizeof(uint32_t));
uint32_t *outnum = malloc(max * sizeof(uint32_t));

n = 0;
while (scanf("%u:%u:%u", [n], [n], [n]) == 3) {
if (++n == max) {
max *= 2;
   

Re: [Lightning-dev] Improving the initial gossip sync

[Fabrice Drouin]

I'm still pushing for the hash-based solution because it can be
implemented and developed quickly and easily and fixes the main issues
we've seen on testnet:
- routing sync on mobile nodes
- "route not found" errors when you're missing routing info.

It can be deployed as an optional feature and will give us time to
specify and implement proper IBLT-based filters.

It can be combined with the timestamp approach: nodes would send
bucket hashes + low and high watermarks.

I've tried and summarised the issue below:

## The problem

The current scheme (broadcast + optionally ask for a full routing
table when you connect) works well for nodes which are never
completely offline, but is becoming unpractical on mobile
node/end-user nodes which are often offline and connected to a few
peers. We need a way to improve the initial routing sync and retrieve
announcements that we've missed without having to download the entire
routing table.

Additionally, the only way to check that routing information is
consistent between different nodes is to ask each one of them to send
you their entire routing table. Exchanging filters/digests/… would
mitigate the issue of having to “trust” that your peers do provide do
with a good routing table, especially when you’re connected to very
few peers.

## Requirements

- Easy to specify and implement
- Low overhead
- Ability to retrieve missing routing information
- (Nice to have) Ability to query multiple peers for consistency checks

## Background

The current method for retrieving this routing table is to set the
`initial_routing_sync` flag in the `init` message that you send every
time you connect/reconnect to a peer, which will then send back its
entire routing table (currently 6000 channels on testnet).
If a node believes that a channel is available when it has in fact
been closed, and uses it to build a route, it will receive an error
message and try again without this specific channel.
But if a node is missing a channel, and cannot route payments, there
is currently no way to recover it: it has to wait until the channel
parameters are updated, and will then receive a `channel_announcement`
and the matching `channel_update`. This could take a very long time.

Hence, the only option for mobile nodes is to request a routing table
dump every time they connect/reconnect, which simply does not work.

We need a way to improve this initial table sync, which is simple
enough to be implemented and deployed quickly. Otherwise, these nodes
will probably use ugly specific hacks (like use their own mechanisms
for retrieving and syncing routing tables) or even rely on remote
servers to compute routes for them.

## Proposed solutions

### Timestamps/watermarks

When they connect to another peer, nodes send a timestamp (I know the
routing table up to X) or a pair of timestamps (I know the routing
table from time X to time Y).

Pros:
- Very simple to specify (use `channel_update` timestamps) and implement.
- Very little overhead
- Solves the “download the entire routing table every time” issue

Cons:
- Does not solve the "missing announcements" issue: if you're missing
routing info you would have to wait for channel parameters to be
updated etc.., as above

### Bucket hashes

Routing info (i.e. channel announcements) are grouped by buckets, one
bucket being a group of 144 blocks. A hash is computed for each
bucket, peers exchanges these hashes and send back all announcements
for which bucket hashes don't match.
We propose to use a bucket per block for the last 7 days, one bucket
per 144 blocks for older announcements,
If gives a total of `(365 + 7*144) = 1373` hashes, for a year of announcements

Pros:
- Simple to specify and implement
- Little overhead (a few dozen Kb)
- If a node is missing a few elements it will immediately recover
them, even if they're very old
- Works well when routing tables are mostly synchronized, which would
be the case for nodes which connect to a very small number of peers
- Bucket hashes are the same for all peers you connect to, and can be
used for consistency checks between peers

Cons:
- Buckets hashes are not queryable filters
- Since a single mismatch will invalidate an entire buckets, even with
small differences nodes could end up having to send their entire
routing table (which exactly what they are doing today)

### IBLT filters

Upon connection, nodes exchange information to estimate the number of
differences between their routing table.
Using this estimate, they build and exchange IBLT filters, and use
them to compute the announcements that they should send to their peer.

Pros:
- Queryable filters
- Very efficient if the number of differences is small, even with very
large routing tables

Cons:
- More complex to specify and implement: we need a good estimator for
the number of differences (send min height + max height + a sample of
announcements ?)
- Filters become peer-specific (similar to the server-side vs
client-side filtering for SPV clients)



On 

Re: [Lightning-dev] Improving the initial gossip sync

[Rusty Russell]

Christian Decker  writes:
> Rusty Russell  writes:
>> Finally catching up.  I prefer the simplicity of the timestamp
>> mechanism, with a more ambitious mechanism TBA.
>
> Fabrice and I had a short chat a few days ago and decided that we'll
> simulate both approaches and see what consumes less bandwidth. With
> zombie channels and the chances for missing channels during a weak form
> of synchronization, it's not that clear to us which one has the better
> tradeoff. With some numbers behind it it may become easier to decide :-)

Maybe; I think we'd be best off with an IBLT-approach similar to
Fabrice's proposal.  An IBLT is better than a simple hash, since if your
results are similar you can just extract the differences, and they're
easier to maintain.  Even easier if we make the boundaries static rather
than now-relative.  For node_announce and channel_update you'd probably
want separate IBLTs (perhaps, though not necessarily, as a separate
RTT).

Note that this approach fits really well as a complement to the
timestamp approach: you'd use this for older pre-timestamp, where you're
likely to have a similar idea of channels.

>> Deployment suggestions:
>>
>> 1. This should be a feature bit pair.  As usual, even == 'support this or
>>disconnect', and odd == 'ok even if you don't understand'.
>
> If we add the timestamp to the end of the `init` message, instead of
> introducing a new message altogether, we are forced to use the required
> bit, otherwise we just made any future field appended to the `init`
> message unparseable to non-supporting nodes. Let's say we add another
> field to it later, that the peer supports, but it follows the timestamp
> which the peer does not. The peer doesn't know how many bytes to skip
> (if any) for the timestamp bit he doesn't understand, to get to the
> bytes he does know how to parse. I'm slowly getting to like the extra
> message more, since it also allows a number of cute tricks later.

This, of course, is the nature of all appendings.  You can't understand
feature N+1 without understanding feature N, if they both append to the
same message.

You don't have to *support* feature N, of course.

>> 2. This `timestamp_routing_sync`? feature overrides `initial_routing_sync`.
>>That lets you decide what old nodes do, using the older
>>`initial_routing_sync` option.  Similarly, a future `fancy_sync` would
>>override `timestamp_routing_sync`.
>
> So you'd set both bits, and if the peer knows `timestamp_routing_sync`
> that then force-sets the `initial_routing_sync`? Sounds ok, if we allow
> optional implementations, even though I'd like to avoid feature
> interactions as much as possible.

If we don't allow optional implementations we're breaking the spec.  And
we're not going to do that*

[* Yeah, OK, we'll eventually do that.  But we'll do it when we're
   pretty sure that ~0 users would break, because they'd be ancient ]

>> 3. We can append an optional 4 byte `routing_sync_timestamp` field to to
>>`init` without issues, since all lengths in there are explicit.  If you
>>don't offer the `timestamp_sync` feature, this Must Be Zero (for appending
>>more stuff in future).
>
> That'd still require the peer to know that it has to skip 4 bytes to get
> any future fields, which is why I am convinced that either forcing it to
> be mandatory, or adding a new message is the better way to go, even if
> now everybody implements it correctly.

This is simply how we upgrade.  See `open_channel` for how this is
already done, for example; in fact, we originally had two different
upgrades (but we broke spec instead) and they used exactly this
technique.

A separate message here is supremely awkward, too.

>> Now, as to the proposal specifics.
>>
>> I dislike the re-transmission of all old channel_announcement and
>> node_announcement messages, just because there's been a recent
>> channel_update.  Simpler to just say 'send anything >=
>> routing_sync_timestamp`.
>
> I'm afraid we can't really omit the `channel_announcement` since a
> `channel_update` that isn't preceded by a `channel_announcement` is
> invalid and will be dropped by peers (especially because the
> `channel_update` doesn't contain the necessary information for
> validation).

OTOH this is a rare corner case which will eventually be fixed by weekly
channel_announce retransmission.  In particular, the receiver should
have already seen the channel_announce, since it preceeded the timestamp
they asked for.

Presumably IRL you'd ask for a timestamp sometime before you were last
disconnected, say 30 minutes.

"The perfect is the enemy of the good".

>> Background: c-lightning internally keeps an tree of gossip in the order
>> we received them, keeping a 'current' pointer for each peer.  This is
>> very efficient (though we don't remember if a peer sent us a gossip msg
>> already, so uses twice the bandwidth it could).
>
> We can solve that by 

Re: [Lightning-dev] Improving the initial gossip sync

[Jim Posen]

I like Christian's proposal of adding a simple announcement cutoff
timestamp with the intention of designing something more sophisticated
given more time.

I prefer the approach of having an optional feature bit signalling that a
`set_gossip_timestamp` message must be sent immediately after `init`, as
Laolu suggested. This way it doesn't conflict with and other possible
handshake extensions.


On Feb 7, 2018 9:50 AM, "Fabrice Drouin"  wrote:

Hi,

Suppose you partition nodes into 3 generic roles:
- payers: they mostly send payments, are typically small and operated
by end users, and are offline quite a lot
- relayers: they mostly relay payments, and would be online most of
the time (if they're too unreliable other nodes will eventually close
their channels with them)
- payees: they mostly receive payments, how often they can be online
is directly link to their particular mode of operations (since you
need to be online to receive payments)

Of course most nodes would play more or less all roles. However,
mobile nodes would probably be mostly "payers", and they have specific
properties:
- if they don't relay payments they don't have to be announced. There
could be millions of mobile nodes that would have no impact on the
size of the routing table
- it does not impact the network when they're offline
- but they need an accurate routing table. This is very different from
nodes who mostly relay or accept payements
- they would be connected to a very small number of nodes
- they would typically be online for just  a few hours every day, but
could be stopped/paused/restarted many times a day

Laolu wrote:
> So I think the primary distinction between y'alls proposals is that
> cdecker's proposal focuses on eventually synchronizing all the set of
> _updates_, while Fabrice's proposal cares *only* about the newly created
> channels. It only cares about new channels as the rationale is that if
once
> tries to route over a channel with a state channel update for it, then
> you'll get an error with the latest update encapsulated.

If you have one filter per day and they don't match (because your peer
has channels that you missed, or
 have been closed and you were not aware of it) then you will receive
all channel announcements for
this particular day, and the associated updates

Laolu wrote:
> I think he's actually proposing just a general update horizon in which
> vertexes+edges with a lower time stamp just shouldn't be set at all. In
the
> case of an old zombie channel which was resurrected, it would eventually
be
> re-propagated as the node on either end of the channel should broadcast a
> fresh update along with the original chan ann.

Yes but it could take a long time. It may be worse on testnet since it
seems that nodes
don't change their fees very often. "Payer nodes" need a good routing
table (as opposed
to "relayers" which could work without one if they never initiate payments)

Laolu wrote:
> This seems to assume that both nodes have a strongly synchronized view of
> the network. Otherwise, they'll fall back to sending everything that went
on
> during the entire epoch regularly. It also doesn't address the zombie
churn
> issue as they may eventually send you very old channels you'll have to
deal
> with (or discard).

Yes I agree that for nodes which have connections to a lot of peers,
strongly synchronized routing tables is
harder to achieve since a small change may invalidate an entire
bucket. Real queryable filters would be much
better, but worst case scenario is we've sent an additionnal 30 Kb or
o of sync messages.
(A very naive filter would be sort + pack all short ids for example)

But we focus on nodes which are connected to a very small number of
peers, and in this particular
case it is not an unrealistic expectation.
We have built a prototype and on testnet it works fairly well. I also
found nodes which have no direct
channel betweem them but produce the same filters for 75% of the
buckets ("produce" here means
that I opened a simple gossip connection to them, got their routing
table and used it to generate filters).


Laolu wrote:
> How far back would this go? Weeks, months, years?
Since forever :)
One filter per day for all annoucements that are older than now - 1
week (modulo 144)
One filter per block for recent announcements

>
> FWIW this approach optimizes for just learning of new channels instead of
> learning of the freshest state you haven't yet seen.

I'd say it optimizes the case where you are connected to very few
peers, and are online a few times every day (?)

>
> -- Laolu
>
>
> On Mon, Feb 5, 2018 at 7:08 AM Fabrice Drouin 
> wrote:
>>
>> Hi,
>>
>> On 5 February 2018 at 14:02, Christian Decker
>>  wrote:
>> > Hi everyone
>> >
>> > The feature bit is even, meaning that it is required from the peer,
>> > since we extend the `init` message itself, and a peer that does not
>> > support this feature would be 

Re: [Lightning-dev] Improving the initial gossip sync

[Fabrice Drouin]

Hi,

Suppose you partition nodes into 3 generic roles:
- payers: they mostly send payments, are typically small and operated
by end users, and are offline quite a lot
- relayers: they mostly relay payments, and would be online most of
the time (if they're too unreliable other nodes will eventually close
their channels with them)
- payees: they mostly receive payments, how often they can be online
is directly link to their particular mode of operations (since you
need to be online to receive payments)

Of course most nodes would play more or less all roles. However,
mobile nodes would probably be mostly "payers", and they have specific
properties:
- if they don't relay payments they don't have to be announced. There
could be millions of mobile nodes that would have no impact on the
size of the routing table
- it does not impact the network when they're offline
- but they need an accurate routing table. This is very different from
nodes who mostly relay or accept payements
- they would be connected to a very small number of nodes
- they would typically be online for just  a few hours every day, but
could be stopped/paused/restarted many times a day

Laolu wrote:
> So I think the primary distinction between y'alls proposals is that
> cdecker's proposal focuses on eventually synchronizing all the set of
> _updates_, while Fabrice's proposal cares *only* about the newly created
> channels. It only cares about new channels as the rationale is that if once
> tries to route over a channel with a state channel update for it, then
> you'll get an error with the latest update encapsulated.

If you have one filter per day and they don't match (because your peer
has channels that you missed, or
 have been closed and you were not aware of it) then you will receive
all channel announcements for
this particular day, and the associated updates

Laolu wrote:
> I think he's actually proposing just a general update horizon in which
> vertexes+edges with a lower time stamp just shouldn't be set at all. In the
> case of an old zombie channel which was resurrected, it would eventually be
> re-propagated as the node on either end of the channel should broadcast a
> fresh update along with the original chan ann.

Yes but it could take a long time. It may be worse on testnet since it
seems that nodes
don't change their fees very often. "Payer nodes" need a good routing
table (as opposed
to "relayers" which could work without one if they never initiate payments)

Laolu wrote:
> This seems to assume that both nodes have a strongly synchronized view of
> the network. Otherwise, they'll fall back to sending everything that went on
> during the entire epoch regularly. It also doesn't address the zombie churn
> issue as they may eventually send you very old channels you'll have to deal
> with (or discard).

Yes I agree that for nodes which have connections to a lot of peers,
strongly synchronized routing tables is
harder to achieve since a small change may invalidate an entire
bucket. Real queryable filters would be much
better, but worst case scenario is we've sent an additionnal 30 Kb or
o of sync messages.
(A very naive filter would be sort + pack all short ids for example)

But we focus on nodes which are connected to a very small number of
peers, and in this particular
case it is not an unrealistic expectation.
We have built a prototype and on testnet it works fairly well. I also
found nodes which have no direct
channel betweem them but produce the same filters for 75% of the
buckets ("produce" here means
that I opened a simple gossip connection to them, got their routing
table and used it to generate filters).


Laolu wrote:
> How far back would this go? Weeks, months, years?
Since forever :)
One filter per day for all annoucements that are older than now - 1
week (modulo 144)
One filter per block for recent announcements

>
> FWIW this approach optimizes for just learning of new channels instead of
> learning of the freshest state you haven't yet seen.

I'd say it optimizes the case where you are connected to very few
peers, and are online a few times every day (?)

>
> -- Laolu
>
>
> On Mon, Feb 5, 2018 at 7:08 AM Fabrice Drouin 
> wrote:
>>
>> Hi,
>>
>> On 5 February 2018 at 14:02, Christian Decker
>>  wrote:
>> > Hi everyone
>> >
>> > The feature bit is even, meaning that it is required from the peer,
>> > since we extend the `init` message itself, and a peer that does not
>> > support this feature would be unable to parse any future extensions to
>> > the `init` message. Alternatively we could create a new
>> > `set_gossip_timestamp` message that is only sent if both endpoints
>> > support this proposal, but that could result in duplicate messages being
>> > delivered between the `init` and the `set_gossip_timestamp` message and
>> > it'd require additional messages.
>>
>> We chose the other aproach and propose to use an optional feature
>>
>> > The reason I'm using 

Re: [Lightning-dev] Improving the initial gossip sync

[Fabrice Drouin]

Hi,

On 5 February 2018 at 14:02, Christian Decker
 wrote:
> Hi everyone
>
> The feature bit is even, meaning that it is required from the peer,
> since we extend the `init` message itself, and a peer that does not
> support this feature would be unable to parse any future extensions to
> the `init` message. Alternatively we could create a new
> `set_gossip_timestamp` message that is only sent if both endpoints
> support this proposal, but that could result in duplicate messages being
> delivered between the `init` and the `set_gossip_timestamp` message and
> it'd require additional messages.

We chose the other aproach and propose to use an optional feature

> The reason I'm using timestamp and not the blockheight in the short
> channel ID is that we already use the timestamp for pruning. In the
> blockheight based timestamp we might ignore channels that were created,
> then not announced or forgotten, and then later came back and are now
> stable.

Just to be clear, you propose to use the timestamp of the most recent
channel updates to filter
the associated channel announcements ?

> I hope this rather simple proposal is sufficient to fix the short-term
> issues we are facing with the initial sync, while we wait for a real
> sync protocol. It is definitely not meant to allow perfect
> synchronization of the topology between peers, but then again I don't
> believe that is strictly necessary to make the routing successful.
>
> Please let me know what you think, and I'd love to discuss Pierre's
> proposal as well.
>
> Cheers,
> Christian

Our idea is to group channel announcements by "buckets", create a
filter for each bucket, exchange and use them to filter out channel
announcements.

We would add a new `use_channel_announcement_filters` optional feature
bit (7 for example), and a new `channel_announcement_filters` message.

When a node that supports channel announcement filters receives an
`init` message with the `use_channel_announcement_filters` bit set, it
sends back its channel filters.

When a node that supports channel announcement filters receives
a`channel_announcement_filters` message, it uses it to filter channel
announcements (and, implicitly ,channel updates) before sending them.

The filters we have in mind are simple:
- Sort announcements by short channel id
- Compute a marker height, which is `144 * ((now - 7 * 144) / 144)`
(we round to multiples of 144 to make sync easier)
- Group channel announcements that were created before this marker by
groups of 144 blocks
- Group channel announcements that were created after this marker by
groups of 1 block
- For each group, sort and concatenate all channel announcements short
channel ids and hash the result (we could use sha256, or the first 16
bytes of the sha256 hash)

The new `channel_announcement_filters` would then be a list of
(height, hash) pairs ordered by increasing heights.

This implies that implementation can easily sort announcements by
short channel id, which should not be very difficult.
An additional step could be to send all short channel ids for all
groups for which the group hash did not match. Alternatively we could
use smarter filters

The use case we have in mind is mobile nodes, or more generally nodes
which are often offline and need to resync very often.

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

[Lightning-dev] Improving the initial gossip sync

[Christian Decker]

Hi everyone

When we started drafting the specification we decided to postpone the
topology syncronization mechanism until we have a better picture of the
kind of loads that are to be expected in the network, e.g., churn and
update rate, and instead implement a trivial gossip protocol to
distribute the topology updates. This includes the dreaded initial
synchonization dump that has caused some issues lately to all
implementations, given that we dump several thousands of updates, that
may require block metadata (short channel ID to txid conversion) lookup
and a UTXO lookup (is this channel still active?).

During the last call we decided to go for an incremental improvement,
rather than a full synchronization mechanism (IBLT, rsync, ...). So
let's discuss how that improvement could look like.

In the following I'll describe a very simple extension based on a
highwater mark for updates, and I think Pierre has a good proposal of
his own, that I'll let him explain.

We already have the `initial_routing_sync` feature bit, which (if
implemented) allows disabling the initial gossip synchronization, and
onyl forwarding newly received gossip messages. I propose adding a new
feature bit (6, i.e., bitmask 0x40) indicating that the `init` message
is extended with a u32 `gossip_timestamp`, interpreted as a UNIX
timestamp. The `gossip_timestamp` is the lowest `channel_update` and
`node_announcement` timestamp the recipient is supposed to send, any
older update or announcement is to be skipped. This allows the `init`
sender to specify how far back the initial synchronization should go.

The logic to forward announcements thus follows this outline:

 - Set `gossip_timestamp` for this peer
 - Iterate through all `channel_update`s that have a timestamp that is
   newer than the `gossip_timestamp` (skipping replaced ones as per BOLT
   07)
 - For each `channel_update` fetch the corresponding
   `channel_announcement` and the endpoints `node_announcement`.
 - Forward the messages in the correct order, i.e.,
 - `channel_announcement`, then `channel_update`, and then `node_announcement`

The feature bit is even, meaning that it is required from the peer,
since we extend the `init` message itself, and a peer that does not
support this feature would be unable to parse any future extensions to
the `init` message. Alternatively we could create a new
`set_gossip_timestamp` message that is only sent if both endpoints
support this proposal, but that could result in duplicate messages being
delivered between the `init` and the `set_gossip_timestamp` message and
it'd require additional messages.

`gossip_timestamp` is rather flexible, since it allows the sender to
specify its most recent update if it believes it is completely caught
up, or send a slightly older timestamp to have some overlap for
currently broadcasting updates, or send the timestamp the node was last
connected with the network, in the case of prolonged downtime.

The reason I'm using timestamp and not the blockheight in the short
channel ID is that we already use the timestamp for pruning. In the
blockheight based timestamp we might ignore channels that were created,
then not announced or forgotten, and then later came back and are now
stable.

I hope this rather simple proposal is sufficient to fix the short-term
issues we are facing with the initial sync, while we wait for a real
sync protocol. It is definitely not meant to allow perfect
synchronization of the topology between peers, but then again I don't
believe that is strictly necessary to make the routing successful.

Please let me know what you think, and I'd love to discuss Pierre's
proposal as well.

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