Documentation about the protocol for constructing crumtrails, Merkle trees and proofs, and libraries for creating and verifying related sructures are gathered here. A hashing grammar is in the works that aids in (obviates the need for) specifying normative descriptions for hash proofs.
The service uses a custom Merkle tree implementation that aids in navigating/walking the nodes in the tree.
For crums.io the Merkle tree library is configured for SHA-256 hashing. The leaves of the tree too are 32-byte wide values. (In the general case, the leaves of a tree may be variable-width values.) In this application, a tree advertises the number of leaves it has. This information, in turn, locks down what a Merkle tree structurally looks like: it's maximum depth (height, in our terminology), for example; or given a leaf's index, a structural path (i.e. ignoring the exact hash values on the way) to the tree's root node.
In the same way that knowing the number of leaves (items) in a Merkle tree fixes the structure of the tree, knowing the index of an item (leaf node) in the tree (together with the total number of leaves in the tree), fixes the structural [hashing] path from the item to the root node. Merkle proofs in this implementation advertise both this index of the item at the leaf (bottom-most) layer and the number of leaves there are in the tree. These 2 numbers are presented as the index and count fields in JSON. Note the (structural) path-to-root represented by these two numbers doesn't just determine how many other hashes must be known in order to get to the root of the tree: it also determines whether the hash must join from the left or right to derive a parent hash and whether the hash joined comes from a leaf or an internal node (important since leaf nodes are prepended with a 0 byte, and internal nodes with a 1, before hashing).
The service packages 2 types of entity as Merkle proofs in the API.
The following are open sourced. More tools and updates are in the works.
The data model, parsers, and a REST client are the main features of v0.0.1, this first release. It also introduces an experimental grammar aimed at generalizing hash proofs. The project's doc site is here.
© 2020-2021 crums.io