Gossip Observer: New project to monitor the Lightning P2P network

Minisketch, a protocol designed for set reconciliation, faces challenges with superlinear decoding costs when dealing with large sketches, which can significantly consume CPU resources. To mitigate this, more frequent reconciliations could be considered; however, each reconciliation introduces communication overheads due to the overshooting of the unknown required amount for reconstruction. Erlay's approach of combining flooding with sketches is highlighted as beneficial because it offloads the majority of the workload to the flooding process, allowing sketches to efficiently address smaller omissions.

The discussion transitions to alternative reconciliation methods, specifically highlighting the potential of using Invertible Bloom Lookup Tables (IBLT) over Minisketch in certain scenarios. This is due to IBLT's higher overheads being potentially less significant when processing all traffic through it, despite their generally worse performance compared to Minisketch. A recent paper proposing an IBLT-based set reconciliation protocol appears promising for these use cases. The CPISync implementation, a benchmark referenced in the Minisketch repository, has been updated and expanded, covering new protocols available at nislab/gensync. Additionally, a study comparing various synchronization strategies, including Cuckoo filters, CPI, and IBLT, provides insights into their trade-offs and applicability to different settings, detailed in a paper found at arxiv.org.

Cuckoo filters, while explored, were deemed not entirely suitable due to their operational characteristics that do not align well with the specific requirements of the discussed use case. The exploration of synchronization methods led to the discovery of the Rateless IBLT (RIBLT) scheme, outlined in a paper available at arxiv.org, which incorporates the Minisketch library in its benchmarks. RIBLT presents an innovative approach by making IBLT rateless, thus enabling efficient encoding for growing set sizes without needing to estimate set differences or regenerate the IBLT upon decoding failure. This method shows promise in terms of bandwidth overhead and scalability for both small and large set differences, according to simulations and benchmarks detailed in the paper.

The potential of RIBLT, especially when considering its performance with smaller sets and elements, suggests that integrating frequent IBLT-based synchronizations with less frequent Minisketch usage could offer a balanced approach to managing bandwidth overhead and CPU utilization. This consideration becomes even more relevant when dealing with small average message sizes, such as those typically found in network gossip protocols. Further investigation into implementations optimized for these conditions could reveal significant benefits, particularly in reducing CPU cost for larger element sizes.