prollipop

prollipop 🍭

A modded Prolly-tree implementation in Typescript.

It's in a decent state but have not done performance analysis. API breaks will result in major version change.

I haven't tested with non-local blockstores. Need to add abort signals and timeouts.

This package implements a modded prolly-tree in Typescript. Most relevant code is in src/mutate.ts and src/diff.ts.

mods:

npm install prollipop

pnpm install && pnpm build

API docs

As you can see from the list below, a lot of ideas have been stolen from the Dolt project's blog so be sure to check them out!

Prolly Trees
- author: Tim Sehn
- implementation: dolt
- relevance: great introduction to prolly-trees
Prolly Tree PoC and technical writeup
- author: ABresting
- implementation: Prolly-tree-Waku-Message
- relevance: Custom implementation of prolly-tree with right side backbone
Merklizing the key/value store for fun and profit
- author: Joel Gustafson
- implementation: okra-js
- relevance: content-defined merkle trees: A node is the first child of its parent if u32(node.hash[0..4]) < (2^32 / Q).
Efficient Diff on Prolly-trees
- author: Aaron Son
- implementation: dolt
- relevance: excellent visual examples for prolly-tree diffs
Only Consider Keys
- author: Tim Sehn
- implementation: dolt
- relevance: only consider keys for chunk boundary, not keys + values
Range-Based Set Reconciliation
- author: Doug Hoyte
- relevance: Negantrophy section uses [number, hash] tuples as keys