Knowledge Base
Browse the concepts behind Truestamp. Follow the links between concepts, or search across everything.
Tagged: merkle
29
Glossary
Audit path
The path member of a Merkle inclusion proof, RFC 6962's audit path and RFC 9162's inclusion path - the sibling hashes from a leaf up to the root, each 64 lowercase hex and at most 32, with no side markers, since leaf_index and tree_size fix each sibling's side.
Block (Truestamp block)
A unit of Truestamp's internal ledger, made at least once a minute while items or entropy observations wait: a Merkle tree over their hashes, hash-chained to the previous block and Ed25519-signed, created finalized and committed once its commitment into an epoch on a public chain exists.
Entropy observation
A captured record of unpredictable public entropy from the NIST Randomness Beacon, the Stellar ledger, or the Bitcoin blockchain, hashed but not 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: the blocks after a chain's last recorded epoch form one Merkle tree, and the hash of the epoch record {leaf_count, merkle_root} goes on Stellar or Bitcoin; each chain advances its own series of epochs, and epochs are not signed.
Epoch hash
The hash Truestamp writes on a public chain for each epoch - SHA-256 under prefix 0x40 of the epoch record {leaf_count, merkle_root} over the epoch's block hashes - as a Stellar hash memo or a Bitcoin OP_RETURN output; a proof carries it in each commitment entry's epoch.
Inclusion proof
The RFC 9162 proof that one leaf belongs to a Merkle tree, the object {leaf_index, path, tree_size} with at most 32 path hashes; a Truestamp proof walks one from the subject's hash to its block's merkle_root and one per commitment from the block hash to its epoch's merkle_root.
Item Commitment
Item Commitment means an item's commitment exists: a commitment row binds its item_hash into the Merkle tree of a finalized block, holding the inclusion proof to that block's merkle_root, and the item moves from processing to committed in the same write.
Item hash
The hash of an item's record, SHA-256 under prefix 0x11 over the JCS of {claims_hash, id, witness_hashes}; it is the item's Merkle-tree leaf in a Truestamp block, gives the item its item code, is not signed, and leaves out authorship and ownership.
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 record's merkle_root commits to that block's items and entropy observations, and an epoch record's merkle_root and leaf_count hash to the epoch hash recorded on chain.
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 - and its tree shape, which Truestamp builds over leaves it sorts by key.
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
Merkle Inclusion Proofs
How a Truestamp inclusion proof, {leaf_index, path, tree_size} of RFC 9162, proves a record hash is a leaf of a block's or an epoch's tree, the walk and its 32-step cap, the committed leaf count, how a submission window follows, and what is and is not provable.
Merkle Proof Encodings
The two encodings of a Truestamp Merkle inclusion proof - the JSON object {leaf_index, path, tree_size} that proofs and the APIs carry, and the fixed-width binary form Truestamp stores, 16 + 32 x d bytes - with their limits and a worked example.
Truestamp's Merkle Tree
Truestamp's binary Merkle hash tree at the block and epoch levels, the RFC 9162 Merkle Tree Hash over leaves sorted by key with no padding, its 0x00 leaf and 0x01 node prefixes over SHA-256, how the root is computed, and the leaf count committed beside every root.