How spacemeshos/merkle-tree works
This is a Go Merkle-tree library: it incrementally builds roots and optional multi-leaf proofs, can cache tree layers for later proof generation, and validates partial proofs against an expected root. The main flow is builder → incremental tree → root/proof; the cached-proof flow reads stored layers and calculates missing nodes as needed. Cache storage can be in memory or file-backed. The README documents sequential construction and partial proofs; proof validation and cache details are supported by sampled source, while some wiring to iterators and positions is inferred only where explicit calls are visible.
Main entry points: merkle.go Incremental tree · cache.go Cache manager · proving.go Cached proof generator · layerfactories.go Layer factories
Components 17
Tree construction
- Tree builder
treebuilder.go - Incremental tree
merkle.go - Root and proof
merkle.go
Proof workflows
- Cached proof generator
proving.go - Subtree traversal
proving.go - Cached node lookup
proving.go - Partial proof validator
validation.go
Layer caching
- Cache manager
cache/cache.go - Caching policies
cache/cachingpolicies.go - Layer factories
cache/layerfactories.go - Memory layer store
cache/readwriters/slice.go - File layer store
cache/readwriters/file.go
Shared primitives
- Positions and iteration
position.go - Proof iterators
iterators.go - Cache interfaces
shared/types.go - Parent hashing
merkle.go
Other components
- Library caller
Connections 23
- Library caller → Tree builder: configures
- Tree builder → Incremental tree: builds
- Library caller → Incremental tree: adds leaves
- Incremental tree → Parent hashing: hashes parents
- Incremental tree → Cache manager: writes layers
- Incremental tree → Root and proof: returns
- Library caller → Cached proof generator: requests proof
- Cached proof generator → Positions and iteration: uses positions
- Cached proof generator → Proof iterators: iterates indices
- Cached proof generator → Cached node lookup: fetches siblings
- Cached proof generator → Subtree traversal: traverses subtrees
- Cached node lookup → Cache manager: reads layers
- Subtree traversal → Tree builder: builds subtree tree
- Subtree traversal → Parent hashing: hashes parents
- Library caller → Partial proof validator: submits proof
- Partial proof validator → Parent hashing: recomputes root
- Library caller → Cache manager: configures cache
- Cache manager → Caching policies: checks policy
- Cache manager → Layer factories: creates layers
- Layer factories → Memory layer store: creates memory store
- Layer factories → File layer store: creates file store
- Cache manager → Cache interfaces: implements contracts
- Incremental tree → Cache interfaces: uses contracts