# spacemeshos/merkle-tree architecture

> Architecture diagram of the GitHub repository spacemeshos/merkle-tree, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-09-25). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/spacemeshos/merkle-tree
- Repository: https://github.com/spacemeshos/merkle-tree

## Overview

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`](https://github.com/spacemeshos/merkle-tree/blob/develop/merkle.go) (Incremental tree), [`cache/cache.go`](https://github.com/spacemeshos/merkle-tree/blob/develop/cache/cache.go) (Cache manager), [`proving.go`](https://github.com/spacemeshos/merkle-tree/blob/develop/proving.go) (Cached proof generator), [`cache/layerfactories.go`](https://github.com/spacemeshos/merkle-tree/blob/develop/cache/layerfactories.go) (Layer factories)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_tree["Tree construction"]
  node_builder["Tree builder<br/>[treebuilder.go]"]
  node_tree_api["Incremental tree<br/>[merkle.go]"]
  node_root_proof["Root and proof<br/>[merkle.go]"]
end

subgraph group_proof["Proof workflows"]
  node_proof_gen["Cached proof generator<br/>[proving.go]"]
  node_subtree["Subtree traversal<br/>[proving.go]"]
  node_node_lookup["Cached node lookup<br/>[proving.go]"]
  node_validator["Partial proof validator<br/>[validation.go]"]
end

subgraph group_cache["Layer caching"]
  node_cache_manager["Cache manager<br/>[cache.go]"]
  node_cache_policy["Caching policies<br/>[cachingpolicies.go]"]
  node_layer_factory["Layer factories<br/>[layerfactories.go]"]
  node_slice_store[("Memory layer store<br/>[slice.go]")]
  node_file_store[("File layer store<br/>[file.go]")]
end

subgraph group_core["Shared primitives"]
  node_positions["Positions and iteration<br/>[position.go]"]
  node_iterators["Proof iterators<br/>[iterators.go]"]
  node_interfaces["Cache interfaces<br/>[types.go]"]
  node_hash["Parent hashing<br/>[merkle.go]"]
end

node_caller(("Library caller"))

node_caller -->|"configures"| node_builder
node_builder -->|"builds"| node_tree_api
node_caller -->|"adds leaves"| node_tree_api
node_tree_api -->|"hashes parents"| node_hash
node_tree_api -->|"writes layers"| node_cache_manager
node_tree_api -->|"returns"| node_root_proof
node_caller -->|"requests proof"| node_proof_gen
node_proof_gen -->|"uses positions"| node_positions
node_proof_gen -->|"iterates indices"| node_iterators
node_proof_gen -->|"fetches siblings"| node_node_lookup
node_proof_gen -->|"traverses subtrees"| node_subtree
node_node_lookup -->|"reads layers"| node_cache_manager
node_subtree -->|"builds subtree tree"| node_builder
node_subtree -->|"hashes parents"| node_hash
node_caller -->|"submits proof"| node_validator
node_validator -->|"recomputes root"| node_hash
node_caller -->|"configures cache"| node_cache_manager
node_cache_manager -->|"checks policy"| node_cache_policy
node_cache_manager -->|"creates layers"| node_layer_factory
node_layer_factory -->|"creates memory store"| node_slice_store
node_layer_factory -.->|"creates file store"| node_file_store
node_cache_manager -->|"implements contracts"| node_interfaces
node_tree_api -->|"uses contracts"| node_interfaces

click node_builder "https://github.com/spacemeshos/merkle-tree/blob/develop/treebuilder.go"
click node_tree_api "https://github.com/spacemeshos/merkle-tree/blob/develop/merkle.go"
click node_root_proof "https://github.com/spacemeshos/merkle-tree/blob/develop/merkle.go"
click node_proof_gen "https://github.com/spacemeshos/merkle-tree/blob/develop/proving.go"
click node_subtree "https://github.com/spacemeshos/merkle-tree/blob/develop/proving.go"
click node_node_lookup "https://github.com/spacemeshos/merkle-tree/blob/develop/proving.go"
click node_validator "https://github.com/spacemeshos/merkle-tree/blob/develop/validation.go"
click node_positions "https://github.com/spacemeshos/merkle-tree/blob/develop/position.go"
click node_iterators "https://github.com/spacemeshos/merkle-tree/blob/develop/iterators.go"
click node_cache_manager "https://github.com/spacemeshos/merkle-tree/blob/develop/cache/cache.go"
click node_cache_policy "https://github.com/spacemeshos/merkle-tree/blob/develop/cache/cachingpolicies.go"
click node_layer_factory "https://github.com/spacemeshos/merkle-tree/blob/develop/cache/layerfactories.go"
click node_slice_store "https://github.com/spacemeshos/merkle-tree/blob/develop/cache/readwriters/slice.go"
click node_file_store "https://github.com/spacemeshos/merkle-tree/blob/develop/cache/readwriters/file.go"
click node_interfaces "https://github.com/spacemeshos/merkle-tree/blob/develop/shared/types.go"
click node_hash "https://github.com/spacemeshos/merkle-tree/blob/develop/merkle.go"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_builder,node_tree_api,node_root_proof toneBlue
class node_proof_gen,node_subtree,node_node_lookup,node_validator toneAmber
class node_cache_manager,node_cache_policy,node_layer_factory,node_slice_store,node_file_store toneMint
class node_positions,node_iterators,node_interfaces,node_hash toneRose
class node_caller toneIndigo
```

## Components

### Tree construction

- [Tree builder](https://github.com/spacemeshos/merkle-tree/blob/develop/treebuilder.go): `treebuilder.go`
- [Incremental tree](https://github.com/spacemeshos/merkle-tree/blob/develop/merkle.go): `merkle.go`
- [Root and proof](https://github.com/spacemeshos/merkle-tree/blob/develop/merkle.go): `merkle.go`

### Proof workflows

- [Cached proof generator](https://github.com/spacemeshos/merkle-tree/blob/develop/proving.go): `proving.go`
- [Subtree traversal](https://github.com/spacemeshos/merkle-tree/blob/develop/proving.go): `proving.go`
- [Cached node lookup](https://github.com/spacemeshos/merkle-tree/blob/develop/proving.go): `proving.go`
- [Partial proof validator](https://github.com/spacemeshos/merkle-tree/blob/develop/validation.go): `validation.go`

### Layer caching

- [Cache manager](https://github.com/spacemeshos/merkle-tree/blob/develop/cache/cache.go): `cache/cache.go`
- [Caching policies](https://github.com/spacemeshos/merkle-tree/blob/develop/cache/cachingpolicies.go): `cache/cachingpolicies.go`
- [Layer factories](https://github.com/spacemeshos/merkle-tree/blob/develop/cache/layerfactories.go): `cache/layerfactories.go`
- [Memory layer store](https://github.com/spacemeshos/merkle-tree/blob/develop/cache/readwriters/slice.go): `cache/readwriters/slice.go`
- [File layer store](https://github.com/spacemeshos/merkle-tree/blob/develop/cache/readwriters/file.go): `cache/readwriters/file.go`

### Shared primitives

- [Positions and iteration](https://github.com/spacemeshos/merkle-tree/blob/develop/position.go): `position.go`
- [Proof iterators](https://github.com/spacemeshos/merkle-tree/blob/develop/iterators.go): `iterators.go`
- [Cache interfaces](https://github.com/spacemeshos/merkle-tree/blob/develop/shared/types.go): `shared/types.go`
- [Parent hashing](https://github.com/spacemeshos/merkle-tree/blob/develop/merkle.go): `merkle.go`

### Other components

- **Library caller**

## Connections

- 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