# Optimized gossip notes ## Erlay [Erlay](https://arxiv.org/abs/1905.10518) protocol optimizes bitcoin's mempool gossip. Erlay still floods messages, but only to 8 fixed peers. I never figured out how they select those 8 peers for flooding. Anyone else? They employ a set reconciliation scheme called minsketch with any nodes besides those 8. Their set reconciliation relies upon good estimates for set difference sizes. If this fails, they improve the estimate by bisecting the sets. This prevents the sizes being too large, which matters because the min/pinsketch algorithm has quadratic complexity. Their set reconciliation used only a 64 bit rehashed representation of the 32 byte transaction hash. They mitigate the threat of adversarial transaction hashes by hashing with a salt st by the requester node and presumably different for each connection and known only to the two gossiping nodes. Erlay does set reconciliation protocol using Pieter Wuille's [minisketch](https://github.com/sipa/minisketch) library. There are rust bindings at https://github.com/eupn/minisketch-rs but no pure rust implementation yet. Their minsketch algorithm is based on the pinsketch algorithm from section 6.3 of [_Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data_](http://web.cs.ucla.edu/~rafail/PUBLIC/89.pdf) ([short](https://www.iacr.org/cryptodb/archive/2004/EUROCRYPT/2305/2305.pdf)) by Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith, which uses Bose–Chaudhuri–Hocquenghem (BCH) codes. Another implementation by these authors with additional details exists at https://www.cs.bu.edu/~reyzin/code/fuzzy.html Erlay notes exported from https://github.com/w3f/research-internal/issues/141 ## TODO https://hal.inria.fr/hal-01479885/file/RR-9039.pdf