# alloy-rs/trie architecture

> Architecture diagram of the GitHub repository alloy-rs/trie, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-05-12). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/alloy-rs/trie
- Repository: https://github.com/alloy-rs/trie

## Overview

##### Project type and purpose
- From the README and Cargo.toml, we see this is a Rust library (`alloy‐trie`) that implements a fast Merkle-Patricia Trie (MPT) state root calculator and proof generator.
- It is an open-source, backend-only computational tool (no UI). Its core responsibility is to take key/value pairs (nibbles), build or traverse a trie, compute a state root, and generate/verify proofs.

##### File structure
- Top‐level Rust configuration files and CI/CD workflows:
- `.github/workflows/*` – CI, benchmarking, no_std tests
- `Cargo.toml`, `rustfmt.toml`, `clippy.toml`, etc. – build, lint, formatting
- `benches/bench.rs` – performance benchmarks
- `scripts/` – release & changelog automation
- Core code lives under `src/`:
- `lib.rs` – crate entry point, re-exports core modules
- `account.rs` – account‐type abstractions for MPT leaves
- `root.rs` – logic to compute the trie’s root hash
- `mask.rs` – runtime mask layer for sparse updates or in-memory overlays
- `hash_builder/` – hashing primitives and combiners (keccak/RLP-based)
- `nodes/` – implementations of trie node types (branch, extension, leaf, rlp helpers)
- `proof/` – proof construction and verification, error handling, decoded/retainer structures

##### README for additional insights
- Confirms project scope: state root calculation, proof generation for prefix-sorted nibbles.

##### Detail
- Dependencies (e.g., `proof` depends on `nodes`, `proof::verify` calls `hash_builder`).
- Don’t overcomplicate: include every top‐level module, show clear separation of concerns, and illustrate the linear stages from input to output.

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% API Layer
    subgraph "API Layer"
        API["External Interface (Public API)"]:::api
    end

    %% Input
    Input["Input Interface\n(Key/Value pairs)"]:::api

    %% Core Data Structures
    subgraph "Core Data Structures"
        Account["Account Abstractions\n(account.rs)"]:::coreData
        subgraph "NodeFactory Module\n(src/nodes)"
            Nodes["NodeFactory Module"]:::coreData
            Branch["branch.rs"]:::coreData
            Extension["extension.rs)"]:::coreData
            Leaf["leaf.rs"]:::coreData
            RLP["rlp.rs"]:::coreData
        end
        Mask["Mask Layer\n(mask.rs)"]:::coreData
    end

    %% Cryptographic Primitives
    subgraph "Cryptographic Primitives"
        subgraph "HashBuilder Module\n(src/hash_builder)"
            Hash["HashBuilder Module"]:::crypto
            HashMod["mod.rs"]:::crypto
            HashVal["value.rs"]:::crypto
        end
    end

    %% Trie Root & Proof
    subgraph "Trie Root & Proof"
        Root["Root Calculator\n(root.rs)"]:::coreData
        subgraph "Proof Generator & Verifier\n(src/proof)"
            Proof["Proof Module"]:::coreData
            DecodedNodes["decoded_proof_nodes.rs"]:::coreData
            Retainer["decoded_retainer.rs"]:::coreData
            Error["error.rs"]:::coreData
            ProofNodes["proof_nodes.rs"]:::coreData
            Retain["retainer.rs"]:::coreData
            Verify["verify.rs"]:::coreData
        end
    end

    %% Auxiliary Systems
    subgraph "Auxiliary"
        Bench["Benchmarks\n(benches/bench.rs)"]:::aux
        Scripts["Release & Changelog Scripts\n(scripts/)"]:::aux
        CI["CI/CD Workflows\n(.github/workflows/)"]:::aux
    end

    %% Data Flow
    Input -->|nibbles| Nodes
    Input -->|nibbles| Hash
    Account --> Nodes
    Nodes -->|RLP nodes| Root
    Hash -->|Keccak hash| Root
    Mask -->|overlay| Root
    Root -->|state root| API
    Root -->|trie| Proof
    Proof -->|proof object| API
    Proof -->|verify calls| Hash

    %% Auxiliary interactions
    Bench -->|calls API| API
    Scripts -->|uses API| API
    CI -->|tests API| API

    %% Click Events
    click API "https://github.com/alloy-rs/trie/blob/main/src/lib.rs"
    click Account "https://github.com/alloy-rs/trie/blob/main/src/account.rs"
    click HashMod "https://github.com/alloy-rs/trie/blob/main/src/hash_builder/mod.rs"
    click HashVal "https://github.com/alloy-rs/trie/blob/main/src/hash_builder/value.rs"
    click Nodes "https://github.com/alloy-rs/trie/blob/main/src/nodes/mod.rs"
    click Branch "https://github.com/alloy-rs/trie/blob/main/src/nodes/branch.rs"
    click Extension "https://github.com/alloy-rs/trie/blob/main/src/nodes/extension.rs"
    click Leaf "https://github.com/alloy-rs/trie/blob/main/src/nodes/leaf.rs"
    click RLP "https://github.com/alloy-rs/trie/blob/main/src/nodes/rlp.rs"
    click Mask "https://github.com/alloy-rs/trie/blob/main/src/mask.rs"
    click Root "https://github.com/alloy-rs/trie/blob/main/src/root.rs"
    click Proof "https://github.com/alloy-rs/trie/blob/main/src/proof/mod.rs"
    click DecodedNodes "https://github.com/alloy-rs/trie/blob/main/src/proof/decoded_proof_nodes.rs"
    click Retainer "https://github.com/alloy-rs/trie/blob/main/src/proof/decoded_retainer.rs"
    click Error "https://github.com/alloy-rs/trie/blob/main/src/proof/error.rs"
    click ProofNodes "https://github.com/alloy-rs/trie/blob/main/src/proof/proof_nodes.rs"
    click Retain "https://github.com/alloy-rs/trie/blob/main/src/proof/retainer.rs"
    click Verify "https://github.com/alloy-rs/trie/blob/main/src/proof/verify.rs"
    click Bench "https://github.com/alloy-rs/trie/blob/main/benches/bench.rs"
    click Scripts "https://github.com/alloy-rs/trie/blob/main/scripts/changelog.sh"
    click CI "https://github.com/alloy-rs/trie/blob/main/.github/workflows/ci.yml"

    %% Styles
    classDef api fill:#E3F2FD,stroke:#0D47A1,color:#0D47A1;
    classDef coreData fill:#E8F5E9,stroke:#1B5E20,color:#1B5E20;
    classDef crypto fill:#FFF3E0,stroke:#E65100,color:#E65100;
    classDef aux fill:#F3E5F5,stroke:#4A148C,color:#4A148C;
```
