[Lightning-dev] Improving the initial gossip sync: DRAFT
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
Olaoluwa Osuntokun writes: > 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. While I do agree that a new message with high and low watermarks for a sync controlled by the recipient is the way to go, I just don't see the issue with extending the `init` message (and I think it may be useful in future, which is why I bring it up). The two variable size fields are length prefixed so we know exactly what their size is, and where they end, so a new field added to the end can be trivially identified as such. As pointed out in my first mail, we'd have to make it mandatory for the recipient to understand the new field, since it cannot be skipped if the recipient does not, but this still doesn't preclude adding such a field. As for the overflow issue you mention, a single features bitfield is already sufficient to completely overflow the `init` message length, since it's prefix is 2 bytes, allowing for 65535 bytes for that single field alone, in a message that only has 65533 bytes of payload left. But the sender would have to be bonkers to overflow the message and then try something with the appended field. It'd overflow in the next packet since we can't even tell the recipient that we have >65535 bytes of payload, and it'd fail the HMAC check. IMHO the connection would simply be stopped right there, and the sender just found a very contorted way of closing the connection :-) In the good case however the `init` message can look something like this: - [2:gflen] - [gflen:globalfeatures] - [2:lflen] - [lflen:localfeatures] - [4:lowwatermark] - [4:highwatermark] Maybe I'm just not seeing it, and if that's the case I apologize :-) Cheers, Christian ___ 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 writes: > Hi Rusty, > >> 1. query_short_channel_id >> IMPLEMENTATION: trivial > > *thumbs up* OK, I'm implementing this now, with data packing so we can have more than one. (Current 0 and the straight array, will then be able to assess how impactful adding a simple encoder is). >> 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. Meh, zlib is pretty trivial for all implementations though. Will implement and see how long it takes me though. >> 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. I don't see this argument at all; we can add fields, we can remove them, but we still have to transmit them which wastes a little space. Adding a new field and insist it be next packet is a weird ordering contraint, which AFAICT is unique in the protocol. > 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. This is a more convincing argument. I guess we'll have to index by timestamp (we currently index by receive order only); I was hoping we could get away with a single brute-force traverse when the peer initially connected. So, let's say `channel_range_queries` means don't send *any* gossip messages until asked (presumably from `gossip_set_timestamp_range`); we'd implement this by setting the peer's timestamp range to 0,0. Receiving a new `gossip_set_timestamp_range` would override any previous. OK, I'm hacking together now to see if I've missed anything before proposing a proper spec... 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
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
> 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 >> > = >> > >> > 1. type: 260 (`query_short_channel_id`) >>
Re: [Lightning-dev] Improving the initial gossip sync
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 > > splitgz: 6464 bytes > > delta: 6624 by
Re: [Lightning-dev] Improving the initial gossip sync
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
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
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 *)&v + (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(&tmp[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", &block[n], &txnum[n], &outnum[n]) == 3) {
if (++n == max) {
Re: [Lightning-dev] Improving the initial gossip sync
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 16
Re: [Lightning-dev] Improving the initial gossip sync
On 12 February 2018 at 02:45, Rusty Russell wrote: > 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). Yes, real filters would be better, but the 'bucket hash' idea works (from what I've seen on testnet) for our specific target (nodes which are connected to very small number of peers and go offline very often) . > 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. Both approaches maybe needed because they may be solutions to different problems (nodes which get d isconnected from a small set of peers vs nodes connected to many peers, which remain online but not some of their peers) >>> 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". This is precisely what I think would not work very well with the timestamp approach: when you're missing an 'old' channel announcement, and only have a few sources for them. It can have a huge impact on terminal nodes which won't be able to find routes and waiting for a new channel update would take too long. Yes, using just a few peers mean that you will be limited to the routing table they will give you, but having some kind of filter would let nodes connect to other peers just to retrieve them and check how far off they are from the rest of the nework. This would not possible with a timestamp (you would need to download the entire routing table again, which is what we're trying to avoid) >>> 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). Ok so a peer would receive an announcement it has sent, but woud immediately dismiss it ? >> >> We can solve that by keeping a filter of the messages we received from >> the peer, it's more of an optimization than anything, other than the >> bandwidth cost, it doesn't hurt. > > Yes, it's on the TODO somewhere... we should do this! > >>> But this isn't *quite* the same as timestamp order, so we can't just set >>> the 'current' pointer based on the first entry >= >>> `routing_sync_timestamp`; we need to actively filter. This is still a >>> simple traverse, however, skipping over any entry less than >>> routing_sync_timestamp. >>> >>> OTOH, if we need to retransmit announcements, when do we stop >>> retransmitting them? If a new channel_update comes in during this time, >>> are we still to dump the announcements? Do we have to remember which >>> ones we've sent to each peer? >> >> That's more of an implementation detail. In c-lightning we can just >> remember the index at which the initial sync started, and send >> announcements along until the index is larger than the initial sync >> index. > > True. It is an implementation detail which is critical to saving > bandwidth though. > >> A more general approach would be to have 2 timestamps, one highwater and >> one lowwater mark. Anything inbetween these marks will be forwarded >> togeth
Re: [Lightning-dev] Improving the initial gossip sync
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 keeping a filter of the messages we received from > th
Re: [Lightning-dev] Improving the initial gossip sync
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 :-) > 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. > 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. > 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. > 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). > 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 keeping a filter of the messages we received from the peer, it's more of an optimization than anything, other than the bandwidth cost, it doesn't hurt. > But this isn't *quite* the same as timestamp order, so we can't just set > the 'current' pointer based on the first entry >= > `routing_sync_timestamp`; we need to actively filter. This is still a > simple traverse, however, skipping over any entry less than > routing_sync_timestamp. > > OTOH, if we need to retransmit announcements, when do we stop > retransmitting them? If a new channel_update comes in during this time, > are we still to dump the announcements? Do we have to remember which > ones we've sent to each peer? That's more of an implementation detail. In c-lightning we can just remember the index at which the initial sync started, and send announcements along until the index is larger than the initial sync index. A more general approach would be to have 2 timestamps, one highwater and one lowwater mark. Anything inbetween these marks will be forwarded together with all associated announcements (node / channel), anything newer than that will only forward the update. The two timestamps approach, combined with a new message, would also allow us to send multiple `timestamp_routing_sync` messages, e.g., first sync the last hour, then the last day, then the last week, etc. It gives the syncing node control over what timewindow to send, inverting the current initial sync. Cheers, Christian ___ 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
Hi all! Finally catching up. I prefer the simplicity of the timestamp mechanism, with a more ambitious mechanism TBA. 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'. 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`. 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). 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`. 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). But this isn't *quite* the same as timestamp order, so we can't just set the 'current' pointer based on the first entry >= `routing_sync_timestamp`; we need to actively filter. This is still a simple traverse, however, skipping over any entry less than routing_sync_timestamp. OTOH, if we need to retransmit announcements, when do we stop retransmitting them? If a new channel_update comes in during this time, are we still to dump the announcements? Do we have to remember which ones we've sent to each peer? If missing announcements becomes a problem, we could add a simple query message: I think this is going to be needed for any fancy scheme anyway. 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
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 unable to parse any future extensions to
>> > the `init` message. Alternatively we
Re: [Lightning-dev] Improving the initial gossip sync
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 timestamp and not the blockheight in the short
>> > channel I
Re: [Lightning-dev] Improving the initial gossip sync
Hi Y'all, Definitely agree that we need a stop-gap solution to fix the naive table dump on initial connect. I've been sketching out some fancier stuff, but we would need time to properly tune the fanciness, and I'm inclined to get out a stop-gap solution asap. On testnet, the zombie churn is pretty bad atm. It results in uneasily wasted bandwidth as the churn is now almost constant. There still exist some very old testnet nodes our there it seems. Beyond the zombie churn, with the size of the testnet graph, we're forced to send tens of thousands of messages (even if we're already fully synced) upon initial connect, so very wasteful over all. 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. Christian wrote: > 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. As the `init` message solely contains two variably sized byte slices, I don't think we can actually safely extend it in this manner. Instead, a new message is required, where the semantics of the feature bit _require_ the other side to send it directly after receiving the `init` message from the other side. Aside from that, overall I like the simplicity of the protocol: it eliminates both the zombie churn, and the intensive initial connection graph dump without any extra messaging overhead (for reconciliation, etc). Fabrice wrote: > Just to be clear, you propose to use the timestamp of the most recent > channel updates to filter the associated channel announcements ? 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. > 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 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). > The use case we have in mind is mobile nodes, or more generally nodes > which are often offline and need to resync very often. How far back would this go? Weeks, months, years? FWIW this approach optimizes for just learning of new channels instead of learning of the freshest state you haven't yet seen. -- 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 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
Re: [Lightning-dev] Improving the initial gossip sync
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
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
