# manojkgorle/brainfuckvm architecture

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

- Interactive diagram: https://gitdiagram.com/manojkgorle/brainfuckvm
- Repository: https://github.com/manojkgorle/brainfuckvm

## Overview

##### Overall Architecture & Main Components
- Modules from the file tree:
- Main Execution Engine: Represented by src/main.rs which drives the execution, proof generation, and verification.
- Virtual Machine (VM) Module: Found in src/vm/mod.rs, it compiles, runs, and simulates BrainFuck programs.
- STARK Prover/Verifier: Located in src/stark/mod.rs – encapsulates the core functions and helpers for generating and checking STARK proofs.
- Computation Tables: In src/tables/ – includes subcomponents like processor, instruction, memory, and IO tables needed to record and simulate the execution state.
- FRI Protocol: In src/fri/mod.rs – a minimal implementation for low degree testing as part of the proof system.
- Field Arithmetic: In src/fields/mod.rs – provides modular arithmetic functions required for cryptographic operations.
- Univariate Polynomials: In src/univariate_polynomial/mod.rs – handles polynomial arithmetic which is essential for building the intermediate representations used in the STARK.
- Merkle Tree: In src/merkle/mod.rs – wraps the Merkle tree logic used to commit to various data structures.
- Fiat-Shamir Oracle (Channel): In src/channel/mod.rs – simulates communications between prover and verifier.

##### Illustrating Relationships & Data Flow
- "VM Module" for compiling and running BrainFuck programs.
- "STARK Module" which is responsible for the proving/verification process.
- The “STARK Module” further interacts with:
- "FRI Module" for performing the FRI protocol on quotient polynomials.
- "Field Arithmetic" and "Polynomial Module" for all underlying arithmetic operations.
- "Merkle Tree" for data commitment.
- "Tables Module" comprising several subcomponents (Processor, Instruction, IO, Memory Tables) that support the STARK mechanism by recording program execution details.
- "Channel Module" to simulate the interactive proofs (Fiat-Shamir heuristic).
- Data (like state tables and polynomials) flows from the execution in VM to the Tables Module.
- These tables flow into the STARK module where field and polynomial operations occur, then to the FRI module.
- The results, along with commitments using the Merkle Tree, interplay with the Channel Module to simulate challenge-response interactions between a prover and a verifier.

##### Architectural Patterns and Key Principles
- Modular Design: Each submodule—tables, field arithmetic, polynomial operations, and so on—is a self-contained component that interacts with others primarily through well-defined interfaces (e.g., data structures representing tables or polynomials).
- Data Flow and Interaction: Clearly map how data is processed through several layers: from program execution, to table generation, to cryptographic proof steps managed by STARK and FRI, then using Merkle trees and the Channel (oracle) for verifying integrity.
- Optimization Strategies: Optionally note that some components (e.g., parallel computing for Lagrange polynomials) are intended to reduce proving time, which may be annotated as performance enhancements.

## Diagram (Mermaid)

```mermaid
flowchart TD
    Main["Main"]:::core
    VM["VM Module"]:::core
    STARK["STARK Module"]:::crypto
    Tables["Tables Module"]:::aux
    FRI["FRI Module"]:::crypto
    Field["Field Arithmetic"]:::crypto
    Poly["Polynomial Module"]:::crypto
    Merkle["Merkle Tree"]:::crypto
    Channel["Channel Module"]:::aux

    subgraph "Tables Subcomponents"
        Processor["Processor Table"]:::aux
        Instruction["Instruction Table"]:::aux
        Memory["Memory Table"]:::aux
        IO["I/O Table"]:::aux
    end

    Main -->|"executes"| VM
    Main -->|"starts_proof"| STARK
    VM -->|"populates"| Tables
    Tables -->|"supplies_data"| STARK
    STARK -->|"low_degree_test"| FRI
    STARK -->|"arithmetic_ops"| Field
    STARK -->|"polynomial_ops"| Poly
    STARK -->|"commit_data"| Merkle
    STARK -->|"fiat_shamir"| Channel

    Tables -.->|"contains"| Processor
    Tables -.->|"contains"| Instruction
    Tables -.->|"contains"| Memory
    Tables -.->|"contains"| IO

    classDef core fill:#C1E1C1,stroke:#333,stroke-width:2px;
    classDef crypto fill:#AEDFF7,stroke:#333,stroke-width:2px;
    classDef aux fill:#FDEBD0,stroke:#333,stroke-width:2px;

    click Main "https://github.com/manojkgorle/brainfuckvm/blob/main/src/main.rs"
    click VM "https://github.com/manojkgorle/brainfuckvm/blob/main/src/vm/mod.rs"
    click STARK "https://github.com/manojkgorle/brainfuckvm/blob/main/src/stark/mod.rs"
    click Tables "https://github.com/manojkgorle/brainfuckvm/blob/main/src/tables/mod.rs"
    click Processor "https://github.com/manojkgorle/brainfuckvm/blob/main/src/tables/processor.rs"
    click Instruction "https://github.com/manojkgorle/brainfuckvm/blob/main/src/tables/instruction.rs"
    click Memory "https://github.com/manojkgorle/brainfuckvm/blob/main/src/tables/memory.rs"
    click IO "https://github.com/manojkgorle/brainfuckvm/blob/main/src/tables/io.rs"
    click FRI "https://github.com/manojkgorle/brainfuckvm/blob/main/src/fri/mod.rs"
    click Field "https://github.com/manojkgorle/brainfuckvm/blob/main/src/fields/mod.rs"
    click Poly "https://github.com/manojkgorle/brainfuckvm/blob/main/src/univariate_polynomial/mod.rs"
    click Merkle "https://github.com/manojkgorle/brainfuckvm/blob/main/src/merkle/mod.rs"
    click Channel "https://github.com/manojkgorle/brainfuckvm/blob/main/src/channel/mod.rs"
```
