I missed that benefit of the flooding in Erlay on my previous reads of the paper; that makes sense.
This opened a rabbit hole that actually led me to a very recent paper proposing an IBLT-based set reconciliation protocol, that may be well-suited for this use case.
Firstly, the CPISync implementation used for benchmarks in the Minisketch repo has moved and expanded to include some new protocols:
There is a related paper that explores some of the tradeoffs of sync with Cuckoo filters vs. CPI vs. IBLT:
Cuckoo filters looked interesting, but IIUC don’t fit our use case well since a participant learns which elements their counterparty is missing, not the opposite (which elements they should request). The bandwidth used also seems to have a high floor. Outside of that, the benchmarks focus on much larger sets than what’s relevant in the LN Gossip (or Erlay) setting.
I never looked at the MET-IBLT paper; it seems like a better IBLT sync scheme, but with no benefits compared to RIBLT.
Looking into cuckoo filters eventually led me to this paper, Rateless IBLT (RIBLT):
Which seems very promising. They even used the Minisketch library in their benchmarks! And there is a public implementation in Golang (+ impls in C++ and Rust linked in the README):
The main math & explanation is in Section 4, with comparison to alternatives in Section 7.
As a tl;dr:
-
To make an IBLT rateless / an infinite stream of coded symbols, we can extend a mostly-normal IBLT s.t. later coded symbols map to fewer and fewer inputs. If we have an efficient function to compute the indices of coded symbols an input must contribute to, we can encode our table efficiently even as the set size grows.
-
- We can also extend the table incrementally, and send extensions until decoding succeeds, so we don’t need to estimate the set difference nor regenerate the IBLT if decode fails (similar to extending a Minisketch) (the paper doesn’t comment much on partial recovery, but Figure 6 has some simulation results related to this).
-
The bandwidth overhead seems to have a ceiling of ~1.75, even for sets with very few differences; it converges to ~1.35 as differences increase past 100, which seems significantly better than standard IBLT? (Figure 5).
-
For both large and small set differences (1-1000), encoding cost grows linearly (Figure 8) This also holds for total set size (FIgure 10). Worth noting that the ratio (set_differences)/(set_size) is quite small in most of their benchmarks.
-
Most of their benchmarks use an element size of 64 bits. IIUC the bandwidth overhead could be significantly reduced if an implementation was optimized for small sets and smaller elements; there are some relevant notes in Sections 7.1 and 7.2.
If these performance properties hold up, I agree that mixing frequent IBLT-based syncs + infrequent Minisketch usage is appealing. It may also be worth skipping Minisketch entirely and trade bandwidth overhead for the CPU savings; I’m not sure how LN implementations feel about that tradeoff tbh.
Another consideration is that the elements we want to exchange are very small (average message size <275 bytes), so there isn’t much room to add bandwidth overhead. These messages will still be small with gossip v2.
Being able to have larger (64+ bit) elements with only a small increased CPU cost (FIgure 11) may be a very significant benefit; I’ll take a look at these implementations soon and report back.