A cutting-edge reconciliation algorithm developed at WIDE is being used by Bluesky, the decentralized social network built on the AT protocol. In a recent research paper detailing Bluesky’s tech stack [1], researchers from Cambridge and Bluesky reveal that the AT protocol harnesses Merkle Search Trees (MST) – an innovative data structure crafted by Alex Auvolat at WIDE, under François Taïani’s guidance [2].
MSTs supercharge traditional Merkle trees with balanced search tree capabilities while preserving key ordering. This unique feature makes them ideal for implementing CRDTs (Conflict-free Replicated Data Types), which often grapple with updates to sets of sequential keys – a hallmark of many decentralized apps
[1] Martin Kleppmann, Paul Frazee, Jake Gold, Jay Graber, Daniel Holmgren, Devin Ivy, Jeromy Johnson, Bryan Newbold, and Jaz Volpert. 2024. Bluesky and the AT Protocol: Usable Decentralized Social Media. In Proceedings of the ACM Conext-2024 Workshop on the Decentralization of the Internet (DIN ’24). Association for Computing Machinery, New York, NY, USA, 1–7. https://doi.org/10.1145/3694809.3700740
[2] Alex Auvolat, François Taïani. Merkle Search Trees: Efficient State-Based CRDTs in Open Networks SRDS 2019 – 38th IEEE International Symposium on Reliable Distributed Systems, Oct 2019, Lyon, France. pp.1-10, https://doi.org/10.1109/SRDS.2019.00032 https://inria.hal.science/hal-02303490/file/paper%20%281%29.pdf
