Set reconciliation

Bloom filter

Invertible Bloom Lookup Table

Used in Beelay sync server

References

References

[1] Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolić, Sharon Weed Cocco, and Jason Yellick. 2018. Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of the Thirteenth EuroSys Conference (Porto, Portugal) (EuroSys ’18). Association for Computing Machinery, New York, NY, USA, Article 30, 15 pages. https://doi.org/10.1145/3190508.3190538

[2] Jean-Philippe Aumasson and Daniel J. Bernstein. 2012. SipHash: A Fast Short- Input PRF. In 13th International Conference on Cryptology in India (INDOCRYPT 2012) (Kolkata, India) (Lecture Notes in Computer Science, Vol. 7668). Springer, New York, NY, USA, 489–508. https://doi.org/10.1007/978-3-642-34931-7_28

[3] Burton H. Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13, 7 (jul 1970), 422–426. https://doi.org/10.1145/362686.362692

[4] R. C. Bose and Dwijendra K. Ray-Chaudhuri. 1960. On A Class of Error Correcting Binary Group Codes. Inf. Control. 3, 1 (1960), 68–79. https://doi.org/10.1016/ S0019-9958(60)90287-4

[5] John W. Byers, Michael Luby, Michael Mitzenmacher, and Ashutosh Rege. 1998. A digital fountain approach to reliable distribution of bulk data. In Proceedings of the ACM SIGCOMM ’98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (Vancouver, British Columbia, Canada) (SIGCOMM ’98). Association for Computing Machinery, New York, NY, USA, 56–67. https://doi.org/10.1145/285237.285258

[6] Lucien Le Cam. 1960. An approximation theorem for the Poisson binomial distribution. Pacific J. Math. 10, 4 (1960), 1181 – 1197.

[7] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. 2008. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38, 1 (2008), 97–139. https://doi.org/10.1137/060651380

[8] David Eppstein, Michael T. Goodrich, Frank Uyeda, and George Varghese. 2011. What’s the difference? efficient set reconciliation without prior context. In Proceedings of the ACM SIGCOMM 2011 Conference (Toronto, Ontario, Canada) (SIG- COMM ’11). Association for Computing Machinery, New York, NY, USA, 218–229. https://doi.org/10.1145/2018436.2018462

[9] Robert G. Gallager. 1962. Low-density parity-check codes. IRE Trans. Inf. Theory 8, 1 (1962), 21–28. https://doi.org/10.1109/TIT.1962.1057683

[10] The go-ethereum Authors. 2024. go-ethereum: Official Go implementation of the Ethereum protocol. https://geth.ethereum.org.

[11] The go-ethereum Authors. 2024. State heal phase is very slow (not finished after 2 weeks). https://github.com/ethereum/go-ethereum/issues/23191.

[12] The go-ethereum Authors. 2024. trie package - go-ethereum. https://pkg.go.dev/ github.com/ethereum/go-ethereum/trie.

[13] Michael T. Goodrich and Michael Mitzenmacher. 2011. Invertible Bloom Lookup Tables. In 49th Annual Allerton Conference on Communication, Control, and Com- puting (Allerton 2011) (Monticello, IL, USA). IEEE, New York, NY, USA, 792–799. https://doi.org/10.1109/ALLERTON.2011.6120248

[14] Yilin Han, Chenxing Li, Peilun Li, Ming Wu, Dong Zhou, and Fan Long. 2020. Shrec: bandwidth-efficient transaction relay in high-throughput blockchain sys- tems. In Proceedings of the 11th ACM Symposium on Cloud Computing (Virtual Event, USA) (SoCC ’20). Association for Computing Machinery, New York, NY, USA, 238–252. https://doi.org/10.1145/3419111.3421283

[15] Francisco Lázaro and Balázs Matuz. 2021. Irregular Invertible Bloom Look-Up Tables. In 11th International Symposium on Topics in Coding (ISTC 2021) (Montreal, QC, Canada). IEEE, New York, NY, USA, 1–5. https://doi.org/10.1109/ISTC49272. 2021.9594198

[16] Francisco Lázaro and Balázs Matuz. 2023. A Rate-Compatible Solution to the Set Reconciliation Problem. IEEE Trans. Commun. 71, 10 (2023), 5769–5782. https://doi.org/10.1109/TCOMM.2023.3296630

[17] Michael Luby. 2002. LT Codes. In 43rd Symposium on Foundations of Computer Sci- ence (FOCS 2002) (Vancouver, BC, Canada). IEEE Computer Society, Los Alamitos, CA, USA, 271. https://doi.org/10.1109/SFCS.2002.1181950

[18] Michael G. Luby, Michael Mitzenmacher, and M. Amin Shokrollahi. 1998. Analysis of random processes via And-Or tree evaluation. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, USA) (SODA ’98). Society for Industrial and Applied Mathematics, USA, 364–373.

[19] Yaron Minsky, Ari Trachtenberg, and Richard Zippel. 2003. Set reconciliation with nearly optimal communication complexity. IEEE Trans. Inf. Theory 49, 9 (2003), 2213–2218. https://doi.org/10.1109/TIT.2003.815784

[20] Michael Mitzenmacher and Rasmus Pagh. 2018. Simple multi-party set reconciliation. Distributed Comput. 31, 6 (2018), 441–453. https://doi.org/10.1007/S00446- 017-0316-0

[21] Michael Mitzenmacher and George Varghese. 2012. Biff (Bloom filter) codes: Fast error correction for large data sets. In Proceedings of the 2012 IEEE International Symposium on Information Theory (ISIT 2012) (Cambridge, MA, USA). IEEE, New York, NY, USA, 483–487. https://doi.org/10.1109/ISIT.2012.6284236

[22] Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system.

[23] Gleb Naumenko, Gregory Maxwell, Pieter Wuille, Alexandra Fedorova, and Ivan Beschastnikh. 2019. Erlay: Efficient Transaction Relay for Bitcoin. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (London, United Kingdom) (CCS ’19). Association for Computing Machinery, New York, NY, USA, 817–831. https://doi.org/10.1145/3319535.3354237

[24] A. Pinar Ozisik, Gavin Andresen, Brian N. Levine, Darren Tapp, George Bis- sias, and Sunny Katkuri. 2019. Graphene: efficient interactive set reconcil- iation applied to blockchain propagation. In Proceedings of the ACM Special Interest Group on Data Communication (Beijing, China) (SIGCOMM ’19). As- sociation for Computing Machinery, New York, NY, USA, 303–317. https: //doi.org/10.1145/3341302.3342082

[25] Neil Perry, Bruce Spang, Saba Eskandarian, and Dan Boneh. 2022. Strong Anonymity for Mesh Messaging. arXiv:2207.04145

[cs.CR] [26] Aravindh Raman, Sagar Joglekar, Emiliano De Cristofaro, Nishanth Sastry, and Gareth Tyson. 2019. Challenges in the Decentralised Web: The Mastodon Case. In Proceedings of the Internet Measurement Conference (Amsterdam, Netherlands) (IMC ’19). Association for Computing Machinery, New York, NY, USA, 217–229. https://doi.org/10.1145/3355369.3355572

[27] Irving S. Reed and Gustave Solomon. 1960. Polynomial Codes Over Certain Finite Fields. J. Soc. Indust. Appl. Math. 8, 2 (1960), 300–304. https://doi.org/10.1137/ 0108018

[28] Thomas J. Richardson and Rüdiger L. Urbanke. 2001. The capacity of low-density parity-check codes under message-passing decoding. IEEE Trans. Inf. Theory 47, 2 (2001), 599–618. https://doi.org/10.1109/18.910577

[29] Luigi Rizzo. 1997. Dummynet: a simple approach to the evaluation of network protocols. SIGCOMM Comput. Commun. Rev. 27, 1 (jan 1997), 31–41. https: //doi.org/10.1145/251007.251012

[30] Herbert Robbins. 1955. A remark on Stirling’s formula. The American mathemat- ical monthly 62, 1 (1955), 26–29.

[31] Sonic. 2024. Ethereum Execution Client Diversity. https://execution-diversity.info (retrieved January 22, 2024).

[32] J Michael Steele. 1994. Le Cam’s inequality and Poisson approximations. The American Mathematical Monthly 101, 1 (1994), 48–54.

[33] E. Summermatter and C. Grothoff. 2022. Byzantine Fault Tolerant Set Reconcilia- tion. https://lsd.gnunet.org/lsd0003/.

[34] Massimiliano Taverna and Kenneth G. Paterson. 2023. Snapping Snap Sync: Practical Attacks on Go Ethereum Synchronising Nodes. In 32nd USENIX Security Symposium (USENIX Security 23). USENIX Association, Anaheim, CA, 3331–3348. https://www.usenix.org/conference/usenixsecurity23/presentation/taverna

[35] Dennis Trautwein, Aravindh Raman, Gareth Tyson, Ignacio Castro, Will Scott, Moritz Schubotz, Bela Gipp, and Yiannis Psaras. 2022. Design and evalua- tion of IPFS: a storage layer for the decentralized web. In Proceedings of the ACM SIGCOMM 2022 Conference (Amsterdam, Netherlands) (SIGCOMM ’22). Association for Computing Machinery, New York, NY, USA, 739–752. https: //doi.org/10.1145/3544216.3544232

[36] Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. 2017. An Experimental Study of Bitmap Compression vs. Inverted List Compression. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 993–1008. https://doi.org/10.1145/3035918.3064007

[37] Gavin Wood. 2014. Ethereum: A secure decentralised generalised transaction ledger.

[38] Pieter Wuille. 2018. Minisketch: a library for BCH-based set reconciliation. https://github.com/sipa/minisketch.

[39] Cong Yue, Zhongle Xie, Meihui Zhang, Gang Chen, Beng Chin Ooi, Sheng Wang, and Xiaokui Xiao. 2020. Analysis of Indexing Structures for Immutable Data. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD ’20). Association for Computing Machinery, New York, NY, USA, 925–935. https://doi.org/10.1145/3318464.3389773