Knowledge Base
Browse the concepts behind Truestamp. Follow the links between concepts, or search across everything.
Tagged: merkle
30
Glossary
Audit path
The ordered list of sibling hashes in a Merkle inclusion proof; each entry is tagged left or right so a verifier can recompute the root from a leaf and match it against the published root.
Block (Truestamp block)
A minute-cadence unit of Truestamp's internal ledger: a Merkle tree over the item hashes and entropy observations collected in that window, hash-chained to the previous block and Ed25519-signed, created finalized and transitioning to committed once an epoch commitment covers it.
Compact proof encoding
The binary wire form of a Merkle inclusion proof used in a proof bundle's inclusion_proof and epoch_proof fields, packing a depth byte, a left/right direction bitfield, and raw 32-byte sibling hashes into unpadded base64url, mapping losslessly to and from the JSON direction:hash form.
Entropy observation
A captured record of unpredictable public entropy from the NIST Randomness Beacon, the Stellar ledger, or the Bitcoin blockchain, hashed, Ed25519-signed, folded directly as a Merkle leaf into a Truestamp block, and named as a witness by the items submitted after it.
Epoch
The batch Truestamp uses for Block Commitment: all block hashes finalized since the last commitment of a given kind form one Merkle tree whose single root is recorded on a public blockchain, with each chain (Stellar, Bitcoin) advancing its own independent series of epochs.
Epoch root
The single Merkle root summarizing every block hash in an epoch, the exact value written on-chain as a Stellar transaction memo hash or a Bitcoin OP_RETURN payload, carried in a proof bundle as each commitment's epoch_merkle_root and the root its epoch_proof walks a block hash up to.
Inclusion proof
A short list of ceil(log2(N)) sibling hashes, also called an audit proof, proving one Merkle leaf belongs to a tree with a given root without revealing other leaves; a Truestamp proof bundle uses one subject-into-block inclusion_proof and one block-into-epoch epoch_proof per commitment.
Item Commitment
The first Truestamp commitment event: an item's item_hash becomes a Merkle-tree leaf in a finalized block, recorded with a compact inclusion proof, moving the item to the committed state and proving it was submitted within that block's submission window.
Item hash
The item's composite fingerprint, a SHA-256 hash (prefix 0x13) binding an item's ULID, claims hash, metadata hash, and signing-key ID into one value; it becomes the item's Merkle-tree leaf in a Truestamp block and is the value Truestamp signs, with authorship and ownership deliberately excluded.
Merkle leaf
The bottom-level entry of a Merkle tree, hashed as SHA-256(0x00 || hash) under the reserved leaf prefix so it can never be confused with an interior node (prefix 0x01); block-tree leaves are item and entropy observation hashes, epoch-tree leaves are block hashes.
Merkle root
The single hash at the top of a Merkle tree that commits to every leaf below it; a block's Merkle root (the merkle_root field of every block map in a proof bundle) commits to that block's items and entropy observations, and an epoch's root is the value recorded on a public blockchain.
Merkle tree
A binary hash tree where each parent is the SHA-256 hash of its two children, reducing a whole set of leaves to one root; Truestamp builds these trees over item and entropy observation hashes per block and over block hashes per epoch.
RFC 6962
The Certificate Transparency standard Truestamp takes its Merkle hash primitives from - SHA-256 with 0x00 leaf and 0x01 node domain-separation prefixes, and the empty-tree root - while shaping the tree above them by its own key-sort and power-of-two padding rules.
Library
An Introduction to Merkle Patricia Trie
LambdaClass blog primer on the Merkle Patricia Trie (MPT), the authenticated key-value structure behind Ethereum state: tries, Patricia path compression, Keccak hashing, node types, StateRoot, and proof construction.
Angela: A Sparse, Distributed, and Highly Concurrent Merkle Tree
UC Berkeley CS262a project report on Angela, a sparse distributed Merkle tree with fine-grained conflict-node locking for concurrent batched updates, built on Ray and Amazon Aurora, achieving 2x over Trillian.
Comprehensive Guide to Merkle Trees, Merkle Proofs, and Merkle Roots
Cyfrin developer primer defining Merkle trees, proofs, and roots, how pair-wise hashing builds a root, how inclusion proofs verify membership, the second preimage attack, and blockchain uses.
Merkle tree - Wikipedia
Wikipedia's reference article on Merkle (hash) trees: leaf and parent hashing, the root hash, logarithmic inclusion verification, Ralph Merkle's 1979 patent, the second-preimage attack, and uses in Bitcoin, Git, ZFS, and Certificate Transparency.
Merkle Trees in Git and Bitcoin
Initial Commit blog article explaining how Git and Bitcoin both use Merkle trees and content-addressable hashing to build tamper-evident, verifiable distributed data structures.
Ralph Merkle - Wikipedia
Wikipedia biography of Ralph Merkle, co-inventor of public-key cryptography, inventor of Merkle trees and cryptographic hashing, and researcher in nanotechnology and cryonics.
RFC 6962: Certificate Transparency
IETF Experimental RFC defining Certificate Transparency: publicly auditable append-only Merkle Hash Tree logs of TLS certificates, with SHA-256 leaf/node domain separation, inclusion and consistency proofs, SCTs, and Signed Tree Heads.
Some Aspects of Merkle Tree - DEV Community
Sergey Shandar's developer article on Merkle tree implementation pitfalls: second preimage and length extension attacks, distinguishing data from branch nodes, and hash alignment limits in content-addressable networks.
Using Merkle Trees to Efficiently Detect Data Changes
JavaScript Development Substack tutorial on Merkle (hash) trees: bottom-up SHA-256 construction, root-hash summaries, logarithmic change detection, and use in blockchain, P2P, and cloud sync.
Why and how Bitcoin uses Merkle trees - Applied Mathematics Consulting
John D. Cook blog post explaining how Bitcoin organizes block transactions into a Merkle tree, storing only the root in the block header to enable logarithmic-size Simple Payment Verification proofs.
Why do cryptocurrencies use Merkle trees instead of hashing all the data in the block in one go?
Reddit r/cryptography discussion explaining why blockchains use Merkle trees rather than a single block-wide hash: inclusion proofs, SPV light-client verification, partial verification without full data, and second preimage concerns.
Merkle
Compact Merkle Proof Encoding
The compact binary and base64url wire encoding of a Merkle inclusion proof - a depth byte, a packed left/right direction bitfield, and raw 32-byte sibling hashes - and how it maps to and from the JSON "direction:hash" proof form.
Merkle Inclusion Proofs
How a Merkle inclusion (audit) proof uses an audit path of sibling hashes to prove a leaf is a member of a root, how a submission window is proven between the records a submission commits to and the block that contains it, and the provable set versus what is not provable.
Truestamp's Merkle Tree
Truestamp's binary Merkle hash tree, which sorts leaves by key, pads to a power of two, and hashes leaves and internal nodes under separate byte prefixes over SHA-256, defining leaf, node, and root and how the root is computed.