Gossip Observer: New project to monitor the Lightning P2P network

[jonhbit]

@rustyrussell

Sorry to join the conversation late, and I haven’t worked on this for years so my memory could be stale, but here’s a brain dump of our conclusions.

Thanks for reposting it here! Useful to have more context on this, and any snippets of earlier discussions.

@rustyrussell

1. Short channel ids have a lot of bits to squeeze. Ultimate would be to refer to outputs by their index in the blockchain (i.e. the 123456th output), but you can easily use fewer than 64 bits for blocknum/txnum/outnum.

Agreed; I think we could cut at least 6 bits off of txindex? And then use creative XORing to mix in missing bits that don’t have their own spot.

@rustyrussell

3. You maintain three minisketches. We tried a single, but it costs encoding bits, complexity and hits the O(N^2) harder.
4. Channel minisketch is just the scids. Importantly, you send your blockheight with the sketch, because that informs the failure case.
5. Channel update minisketch is compacted scid + direction bit + height. Note that height takes 10 or 11 bits, IIRC, since you don’t send expired ones. You can only reliably decode this once you have reconciled the channels sketch.
6. Node announce sketch is uses the same encoding, using the oldest channel attached to the node as its key. Again this assumes you reconciled the channels sketch first.

If you cannot encode an scid compactly, just send it as a series of “raw" entries. IIRC creating such an scid requires an exceptional number of txs in a block or exceptional output count.

Not sure what you mean with the “raw entries” part? Do you mean, send the underlying gossip message outside of the set reconciliation messaging flow?

@rustyrussell

With this scheme, you simply send the sketches every 60 seconds (like now), and your peer sends you what you’re missing.

Note that you can truncate the set you send if you want to save bandwidth, but really the cost is in the set maintenance, so maybe this is silly. My memory is that minisketch is fast in practice though, even if you keep a 64k (8k element) set which is our max message size anyway.

IIUC the cost is mostly in the final parts of decode; I think if you wanted to save bandwidth, you could create a sketch with an overestimate of the true set difference, and then send some portion of that. If your peer signals that decode would fail, you can send the rest / another chunk of the oversized set.

I didn’t consider the max message size at all; that sounds like an argument for using shorter (32-bit) set elements and using a per-peer salt

@rustyrussell

If reconstruction fails, there are several things you can do:

1. If block height differs, ignore. Time will sort it. Maybe include block hash here?

Not sure I understand this bit; I figure you mean the block height you suggested sending alongside the channel announcement sketch. Is this the blockheight of the newest channel announcement you’ve received, or something else?

@rustyrussell

3. Enlarge your own set (or, send more of your set). If this allows your peer to reconstruct, it will learn that you cannot reconstruct, and it knows to send its largest set if it wasn’t already.
4. Wait for other peers. You might close the gap.
5. Existing gossip queries for recent changes (assuming a pile of old changes haven’t suddenly appeared). You know if you need announcements, updates or node anns.
6. Query for everything.

Oh, we added a “total entries" counter to each message, which gives a clue as well: if your peer has far fewer entries, it’s a cry for help

Mm, I wonder if there are other values that would be useful to add in here.

Re: your follow-up post - I agree on the napkin math working out, and it’s even better if we’re doing one set per message type. And having more peers should also help.

Will think over the message ordering dependencies you mentioned in having three sketches vs. one. Fallback behavior #4 could be promising, where you rebuild a sketch from the messages you received over the last n minutes vs. just 1 minute, reattempt a reconciliation, and hopefully catch up to that peer. I think I’d like to avoid leaning too much on gossip queries if possible