git ssb

This is a simple Binary Radix Tree. The default encodeing used is cbor and the default hashing algorithim used is sha2-256.

Node

Each node is an variable length array containing at the most four elements "left branch", "right branch" "extension", "value"

node : = [LBRANCH, RBRANCH, EXTENSION, VALUE]

If no value exists at a given node the array is truncated to

node : = [LBRANCH, RBRANCH, EXTENSION]

If no value and no extension exists at a given node the array is truncated to

node : = [LBRANCH, RBRANCH]

All empty values in the array are encoded as "undefined"

Branches

Branch are merkle link defined in the IPLD format
Each link points to the next node in the tree.

branch : = {'/': <merkle link>}

Where the link is a CID is encoded as a byte string. Using CIDs allow for the flexablity to update the hashing algorithim and encoding at a later date while being backwards compatiable.

Extensions

Extensions encode shared paths. Extensions are defined as

extension := [length, extension]

Where the length is an interger and the extension is a byte string padded with 0's

For example if the binary keys [0, 0, 1, 1] and [0, 0, 1, 0] have a shared path of [0, 0]. If they where the only two values in the tree the root node would have an extension of [0, 0]

root := [undefined, <link>, [2, 0x00]]