# l0ste/no-std-svm-merkle-tree architecture

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

- Interactive diagram: https://gitdiagram.com/l0ste/no-std-svm-merkle-tree
- Repository: https://github.com/l0ste/no-std-svm-merkle-tree

## Overview

This is a **Rust `no_std` cryptographic utility library** (a crate) that implements a **Merkle tree** with:
- a **stateful API** for **off-chain/client-side** tree building + proof generation (`MerkleTree`)
- a **stateless/lightweight API** for **on-chain Solana program** proof verification (compute root from leaf + proof; exposed as `MerkleProof::merklize` / `compute_merkle_root`-style functions)

So the “system” is not a deployed service—it’s a **library used in two runtime environments**:
##### On-chain Solana program (no_std, compute-unit constrained)

From the tree:

- `Cargo.toml`, `Cargo.lock`
- Signals: Rust crate, feature flags for hash implementations (`sha2`, `keccak`).
- `src/lib.rs`
- The public API surface: re-exports types (likely `MerkleTree`, `MerkleProof`, `Sha256`, `Keccak`, errors).
- `src/merkle/` (core implementation module)
- `mod.rs` — module wiring / exports
- `core.rs` — core algorithms / shared utilities (pairing strategy, indexing, merklization walk)
- `tree.rs` — **stateful** tree structure, storage layout (breadth-first array), insertion, merklize, proof generation
- `proof.rs` — **stateless** proof verification / recomputation of root from leaf+siblings+index
- `hash.rs` — hashing abstraction + implementations (Sha256, Keccak, double-hash variants)
- `error.rs` — error types for insertion/merklize/proof bounds, etc.

- Public API (lib.rs)
- Merkle domain module (merkle/*)
- Tree (stateful)
- Proof (stateless)
- Hash (pluggable algorithms)
- Core (shared logic)
- Error (shared types)

##### README-driven architecture insights to reflect explicitly
- **`no_std` + stack-only allocation**: no heap; designed for Solana BPF constraints.
- **Two APIs for two environments**:
- `MerkleTree`: stores full structure for **fast proof generation** (O(log n)), trades memory for speed (duplicates leaf data in arrays).
- `MerkleProof::merklize` / stateless root computation: **minimal compute** for on-chain verification.
- **Bitcoin-style pairing**: odd nodes duplicate (hash node with itself). Important for correctness expectations.
- **Compile-time sizing via const generics**: e.g. `MerkleTree::<32, 1024, 2048>`—this affects how you label interfaces and constraints.

##### On-chain: compare computed root vs stored root → allow claim

**Annotations to add:**
- “Client uses stateful `MerkleTree` (stores nodes, fast proof generation)”
- “Program uses stateless `MerkleProof::merklize` (compute-unit optimized)”
- “Hash algorithm selectable: SHA-256 / Keccak-256 (+ double variants)”

**Crate boundary: `no-std-svm-merkle-tree`**
- `lib.rs` (Public API façade)
- exports: `MerkleTree`, `MerkleProof`, hash types, error types
- `merkle::tree` (Stateful)
- responsibilities: `new`, `insert`, `merklize`, `root`, `get_proof`
- notes: breadth-first arrays, const generic capacities, leaf duplication optimization
- `merkle::proof` (Stateless)
- responsibilities: compute root from leaf+siblings+index
- notes: on-chain optimized
- `merkle::hash`
- responsibilities: hashing trait/abstraction + implementations (SHA2/Keccak feature-gated)
- `merkle::core`
- responsibilities: shared merklization logic, pairing rules, index math
- `merkle::error`
- responsibilities: error enums/results

- `lib.rs` → (exports) → `merkle::*`
- `tree` → `core`, `hash`, `error`
- `proof` → `core`, `hash`
- `core` → `hash`
- (optional) `hash` → feature flags (`sha2`, `keccak`) in Cargo.toml

This is the “architecture” of the codebase.

Actors:
- Client Tooling
- Solana Program Instruction (`claim`)
- `MerkleProof::merklize`
- Hash function (Sha256/Keccak)
- Program state (`AirdropState.merkle_root`)

Sequence:
##### Program compares computed root to stored root → accept/reject

A note: “Odd node duplication (Bitcoin-style)” and “Proof length ≈ ceil(log2(n))”.

##### Relationships/interactions to be explicit about (don’t leave implied)

- **Root crosses client → chain**: `[u8; 32] merkle_root` stored in account state.
- **Proof crosses client → chain**: fixed-size buffer + `proof_len` + `leaf_index`.
- **Hash selection**: determined by type parameter (`::<Sha256>()`, `::<Keccak>()`) and Cargo features; show it as a “pluggable algorithm” dependency.

- **`no_std` compatibility**: “No heap; stack-only buffers; safe for Solana BPF.”
- **Const generics sizing**: “`MerkleTree<HASH, MAX_LEAVES, NODE_CAP>` compile-time capacity.”
- **Performance tradeoff** (stateful tree): “duplicates leaves in arrays for O(log n) proof gen.”
- **On-chain optimization** (stateless): “walk proof only; minimal allocations; minimal compute.”

These are the “why” behind the module split.

##### Technologies/frameworks/libraries to label
Even though it’s “zero-dependency” in spirit, the README indicates feature-driven hashing support:
- Rust `no_std`
- Cargo features: `sha2`, `keccak`
- Solana program usage (Anchor example shown, but crate is Anchor-agnostic)
- Hash algorithms: SHA-256, Keccak-256, double-hash variants

##### Off-chain Client
- Uses `MerkleTree` → produces `root` + `proof`
##### Crate internals
- `MerkleTree` depends on `core/hash/error`
- `MerkleProof` depends on `core/hash`
##### On-chain Solana Program
- Stores `root` in account state
- Verifies `proof` via `MerkleProof::merklize`

## Diagram (Mermaid)

```mermaid
flowchart TD
  %% =========================
  %% Context / Usage (Vertical)
  %% =========================
  subgraph "Off-chain Environment (Client-side, std OK)"
    direction TB
    User["Claimant / User"]:::external
    ClientApp["Off-chain Client App\n(Airdrop/NFT tooling)"]:::offchain
  end

  subgraph "no-std-svm-merkle-tree Crate (compiled for off-chain + on-chain)"
    direction TB

    Readme["Crate Docs / Usage Guidance\n(off-chain vs on-chain)"]:::docs

    subgraph "Public API Surface"
      direction TB
      LibRS["src/lib.rs\nPublic API façade + re-exports"]:::lib
    end

    subgraph "Merkle Module (src/merkle/*)"
      direction TB
      MerkleMod["merkle::mod\nmodule wiring/exports"]:::module

      MerkleTree["MerkleTree (Stateful API)\ninsert(), merklize(), root(), get_proof()\nNotes: breadth-first array layout\nConst generics capacity; fast proof gen"]:::stateful

      MerkleProof["MerkleProof (Stateless API)\nmerklize()/compute root from leaf+proof+index\nNotes: on-chain optimized; minimal allocation"]:::stateless

      Core["merkle::core\nShared merklization + indexing\nBitcoin-style odd duplication\n(left/right by index bit)"]:::core

      Hash["merkle::hash\nHash trait + implementations\nSHA-256 / Keccak-256 (feature-gated)\n+ double-hash variants"]:::hash

      Error["merkle::error\nError types (bounds, capacity, invalid proof)"]:::error
    end

    Cargo["Cargo.toml\nCrate manifest + features:\nsha2 | keccak"]:::config
  end

  subgraph "On-chain Environment (Solana Program, no_std, CU-constrained)"
    direction TB
    Program["On-chain Solana Program\n(claim verifier instruction)"]:::onchain
    StateAcct[("On-chain State Account\nstores merkle_root: [u8; 32]")]:::storage
  end

  %% =========================
  %% Context Data Flows
  %% =========================
  User -->|"submits recipient_data,proof,proof_len,leaf_index"| ClientApp

  ClientApp -->|"insert(leaf: &[u8])"| MerkleTree
  ClientApp -->|"merklize() -> root: [u8; 32]"| MerkleTree
  ClientApp -->|"get_proof(index: u32) -> proof[] + proof_len"| MerkleTree

  ClientApp -->|"one-time admin: store root: [u8; 32]"| StateAcct
  ClientApp -->|"tx: recipient_data + proof[] + proof_len + leaf_index"| Program

  Program -->|"read merkle_root"| StateAcct
  Program -->|"MerkleProof::merklize(leaf,proof,index)"| MerkleProof
  MerkleProof -->|"computed_root: [u8; 32]"| Program
  Program -->|"compare computed_root == stored_root\naccept/reject claim"| StateAcct

  %% =========================
  %% Internal Crate Dependencies
  %% =========================
  Readme -->|"documents"| LibRS
  Cargo -->|"enables features"| Hash

  LibRS -->|"re-exports"| MerkleMod
  MerkleMod -->|"exports"| MerkleTree
  MerkleMod -->|"exports"| MerkleProof
  MerkleMod -->|"exports"| Core
  MerkleMod -->|"exports"| Hash
  MerkleMod -->|"exports"| Error

  MerkleTree -->|"uses"| Core
  MerkleTree -->|"uses"| Hash
  MerkleTree -->|"returns/uses"| Error

  MerkleProof -->|"uses"| Core
  MerkleProof -->|"uses"| Hash

  Core -->|"calls hash()"| Hash

  %% =========================
  %% Notes / Callouts
  %% =========================
  NoStdNote["Constraints\n- no_std compatible\n- no heap; stack-only buffers\n- safe for Solana BPF"]:::note
  ProofNote["Proof properties\n- proof_len ≈ ceil(log2(leaves))\n- odd node duplication (Bitcoin-style)"]:::note
  PerfNote["Tradeoffs\n- Stateful: stores nodes for O(log n) proof gen\n- Stateless: walks proof only (CU-optimized)"]:::note

  LibRS -.->|"applies to"| NoStdNote
  MerkleTree -.->|"explains"| PerfNote
  MerkleProof -.->|"explains"| PerfNote
  Core -.->|"defines"| ProofNote

  %% =========================
  %% Click Events (from mapping)
  %% =========================
  click Cargo "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/Cargo.toml"
  click Readme "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/README.md"
  click LibRS "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/src/lib.rs"
  click MerkleMod "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/src/merkle/mod.rs"
  click Core "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/src/merkle/core.rs"
  click MerkleTree "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/src/merkle/tree.rs"
  click MerkleProof "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/src/merkle/proof.rs"
  click Hash "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/src/merkle/hash.rs"
  click Error "https://github.com/l0ste/no-std-svm-merkle-tree/blob/main/src/merkle/error.rs"

  %% =========================
  %% Styles
  %% =========================
  classDef external fill:#FFFFFF,stroke:#6B7280,stroke-width:1px,color:#111827
  classDef offchain fill:#E0F2FE,stroke:#0284C7,stroke-width:2px,color:#0C4A6E
  classDef onchain fill:#DCFCE7,stroke:#16A34A,stroke-width:2px,color:#14532D
  classDef storage fill:#F0FDF4,stroke:#16A34A,stroke-width:2px,color:#14532D
  classDef lib fill:#EEF2FF,stroke:#4F46E5,stroke-width:2px,color:#1E1B4B
  classDef module fill:#EDE9FE,stroke:#6D28D9,stroke-width:2px,color:#2E1065
  classDef stateful fill:#FFE4E6,stroke:#E11D48,stroke-width:2px,color:#881337
  classDef stateless fill:#FFEDD5,stroke:#F97316,stroke-width:2px,color:#7C2D12
  classDef core fill:#F5F3FF,stroke:#7C3AED,stroke-width:2px,color:#2E1065
  classDef hash fill:#FEF3C7,stroke:#D97706,stroke-width:2px,color:#78350F
  classDef error fill:#FEE2E2,stroke:#B91C1C,stroke-width:2px,color:#7F1D1D
  classDef config fill:#F3F4F6,stroke:#374151,stroke-width:2px,color:#111827
  classDef docs fill:#ECFCCB,stroke:#65A30D,stroke-width:2px,color:#1A2E05
  classDef note fill:#FFF7ED,stroke:#9A3412,stroke-width:1px,color:#7C2D12,stroke-dasharray: 4 3
```
