Gossip Observer: New project to monitor the Lightning P2P network

[jonhbit]

@rustyrussell

No, I meant, say you use 24 bits for blknum, 14 for txindex, 12 for output number, 1 for direction and 12 for blocknumber, that uniquely identifies each update in 64 bits. But it someone uses the 4096th output of a tx for a channel, you can’t encode it in the set. For that, you simply encode it raw, outside the minisketch.

Ah ok, makes sense now. I think another option is to use more bits per field, and then ‘overlap’ fields by XORing between the low-entropy bits of one field with the high-entropy bits of another.

As an example, a 24 bit blknum field supports another ~300 years of blockheights (we could probably shrink it?). blknum could be encoded little-endian (LE) / with the LSBs starting from index 0. txindex is expanded to 18 bits, also encoded as LE, but starts from index 20. So the two fields overlap on 4 bits:

Key[0:19] = LE(blknum)[0:19]

Key[20:23] = LE(blknum)[20:23] ⊕ LE(txindex)[0:3]

Key[24:37] = LE(txindex)[4:17]

IMO we can adjust the size of these fields based on current constraints like min. tx size, etc. such that the amount of overlap is minimal, but we wouldn’t need this fallback path.

@rustyrussell

You don’t need to signal. When you get their sketch, it fails for you. So you go larger, if you can.

This is the message flow I was thinking of in my response:

sequenceDiagram
    participant Alice
    participant Bob
    
    Alice->>Bob: RequestSketch()
    Bob-->>Alice: SketchDifferenceOfTwoFourths
    Alice->>Alice: DecodeSketch()
    
    alt DecodeSketch() failed
        Alice->>Bob: RequestSketchExtension()
        Bob-->>Alice: SketchDifferenceOfThirdFourth
        Alice->>Alice: decode
    end

I’m unclear on what you meant by “go larger”, but I think you meant that Alice should build a sketch from a larger set locally and retry reconciliation?. IIUC, if the number of differences exceeds the capacity of the sketch Bob sent Alice, Alice retrying reconciliation in this way would only succeed if the number of differences decreased between her first and second sets. Which may happen if she has reconciled with other peers in the meantime.

I think we’d probably want to do both? So if initial reconciliation fails, wait for timer_interval / 3 seconds, expand our local set, build a larger sketch, and try reconciliation again. If the 2nd reconciliation fails, ask Bob for a sketch extension and retry reconciliation a 3rd time. If it still fails, either:

• Query Bob for all set elements and reconcile locally (lots of bandwidth, minimal CPU)
• Give up on reconciliation with Bob for this interval, retry the normal reconciliation protocol in (timer_interval) * 2/3 seconds. Hope that our reconciliation with other peers reduces our difference with Bob.

Another option is to ask Bob for a fresh sketch of the same capacity, instead of an extension of the 1st sketch we received.

IIUC we mostly agree on the options for handling initial reconciliation failure; I think having evidence to decide will require simulation and tweaking parameters there.

@rustyrussell

Per-peer salt penalizes scaling. Now each peer costs you more than bandwidth. If we can avoid this, we should, and I think we can.

My response earlier may have been missing a /s tag, sorry; I think we may just have a different mental model for which parts of this process consume more or less resources. From the benchmarks in the minisketch repo, and comments upthread, we know that:

• Encoding a sketch is very fast; most of the compute for reconciliation is part of sketch merging & decoding.
• Decode time is quadratic with # of differences.
• Given current optimizations, decode time is 2x as long for 64-bit keys vs. 32-bit keys.

My argument re: salting and 32-bit set keys, is that the additional complexity of per-connection salts, and the extra work of computing more set keys (1 per connection vs. 1 global set key), is worth the expected ~2x savings in compute for sketch decoding.

As a supporting point, non-cryptographic hash functions like xxhash are extremely fast for small inputs. As a detracting point, I suspect that a per-peer salt would require using a bit more memory to keep track of per-peer sketch state.

I’m not married to a requirement that we use 32-bit keys, but I think it’s worth exploring / keeping in mind. Perhaps we can tweak other knobs, keep the # of differences down, and then not lose much by having longer 64-bit keys.

@rustyrussell

The current blockheight you are aware of. This is important, because channel updates must be refreshed every 2048 blocks (IIRC in the new spec proposal), and you will accept new channel announcements on each block. So you expect non-zero differences in this case.

The block hash would allow you to see forks, if that happened.

Makes sense, I agree

@rustyrussell

Note that the long pole in the scaling tent is channel updates. Node announcements only change when you change IP address or something, and there are far fewer nodes than channels x 2. Channel announcements only happen once per channel.

@rustyrussell

I think in practice, implementations will fall back to asking for everything if reconciliation fails. It has the benefit of being simple, both to implement and test.

Fair; though I suspect maintaining a larger set / allowing messages to remain in the set for longer will help a lot with reconciliation reliability. Another question for simulation!

@rustyrussell

Yes, there’s a whole load of fun avoiding griefing here. Some rando connects and sends you 8k elements of junk, you don’t want to spend 1 second of CPU (based roughly on the graphs on the minisketch page). Fortunately you can limit it to some ceiling simply by trimming first. The ideal BOLT spec would give exact numbers here, but thorough benchmarks required (like, how long does it take the build the set for all the gossip in the first place? How long to maintain it on each block? etc).

IIUC, the sketch decode has multiple steps, and most of the compute is in the final step. Before that final step, a decoder would know if decode is expected to yield a successful reconciliation with very high probability, before executing that final step. So an early exit should make the cost for that much smaller; I think this isn’t yet implemented in the minisketch library though.

I imagine you’d only want to accept sketches after explicitly requesting them, and you’d disconnect peers that repeatedly send malformed sketches.

I agree a lot of this will depend on some more benchmarking, especially since I think our set and difference sizes may be larger than what is covered on the minisketch repo right now. More varied benchmarking should be a straightforward first step before network-level simulation, I’ll look into it.