Round 1 / go-ipld-prolly-trees

Prolly Trees Probabilistic Merkle B-Trees

Problem In order to have git-like diff, sync, and merge, you need merkle trees.

In order to have database-like features (joins, sorted scans) and performance, you need b-trees.

B-trees don’t “merklize” well because they are path-dependent - their topology is dependent on history of mutations.

Prolly Trees Probabilistic merkle b-trees

Like merkle trees: Verifiable Proofs of inclusion/exclusion Efficient and correct diff/sync/merge

Like b-trees: Efficient random reads/writes Efficient ordered scans Tightly controlled blocksize

B-trees are what enable databases to maintain large indexes efficiently.

Prolly-trees make indexes syncable and distributable on a p2p network.

Prolly Tree Structure Prolly trees look like b trees - wide, shallow search trees Nodes have probabilistic capacity rather than min/max size Size of node is pure function of content Topology of tree is pure function of content Small changes in input yield small change in topology