node-okra v0.0.1

╔══════════════════════════════════════════════════════════════════════════════╗ ║ oooo ║ ║ 888 ║ ║ .ooooo. 888 oooo oooo d8b .oooo. ║ ║ d88'88b 888 .8P' 888""8PP )88b ║ ║ 888 888 888888. 888 .oP"888 ║ ║ 888 888 888 88b. 888 d8( 888 ║ ║Y8bod8P' o888o o888o d888b `Y888""8o ║ ╚══════════════════════════════════════════════════════════════════════════════╝

okra is a pseudo-random deterministic merkle tree built on LMDB.

Leaves of an okra tree are key/value pairs where the key is a constant-width byte array (configured at compile-time) and the value is a 32-byte sha2-256 hash. As you insert leaves into the tree, okra builds and re-balances parent nodes, re-hashing up the tree to the root as necessary.

okra guarantees three significant properties:

1. the expected fanout is a constant (configued at compile-time).
2. the structure of the tree is deterministic: two trees have the same root hash if and only if they have the same set of key/value leaves, independent of insertion order.
3. similar leaf sets produce similar trees: adding or removing any single leaf only changes (on expectation) its log(N) direct ancestors.

These three properties mean that okra trees can be used to efficiently diff large sets of leaves in logarithmic time.

orka is based on the concpet of "Merkle Search Trees" presented in 1 and refined in 2.

okra is written in Zig, and can be linked directly, used with the built-in CLI, or through NodeJS bindings.