Prolly trees, a data structure combining Merkle trees with content-defined chunking, have been independently invented at least four times since 2009 under different names. Starting with bup in 2009, then Noms in 2015 (coining "prolly tree"), French researchers in 2019 ("Merkle Search Trees"), and DePaul University in 2020 ("Content-Defined Merkle Trees"). These structures provide history independence, efficient diffing, structural sharing, and self-balancing properties, making them valuable for version control systems and distributed applications. The repeated independent discovery suggests strong demand for this technology in modern software development.
Table of contents
2015: Noms Invents Prolly Trees2019: France Invents Merkle Search Trees (a.k.a Prolly Trees)2020: DePaul University Invents Content-Defined Merkle Trees (a.k.a Prolly Trees)The End?2009: Bup Invents Prolly Trees (But Doesn't Name it Anything)A Tree By Any Other NameSort: