# tsunrise/sumcheck_multilinear architecture

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

- Interactive diagram: https://gitdiagram.com/tsunrise/sumcheck_multilinear
- Repository: https://github.com/tsunrise/sumcheck_multilinear

## Overview

##### Project type and purpose
- This is an open-source Python library/tool that implements sum-check protocols on multilinear polynomials, products of multilinear polynomials (PMF), and the GKR function.
- It provides both interactive (prover/verifier) and non-interactive (Fiat–Shamir offline) versions of the protocols.

##### File structure
Top-level directories and files:
- .github/workflows/test.yml – CI pipeline that runs the test suite on push/PR.
- assets/ – images used in documentation.
- Core modules:
– polynomial.py, multilinear_extension.py – define MVLinear, constructors, arithmetic, random generation.
– PMF.py – defines the product-of-multilinear-polynomial type.
- Interactive protocol modules:
– IPProverLinear.py, IPPMFProver.py, InteractiveVerifier.py, IPPMFVerifier.py – classes to run the sum-check interaction.
- Fiat–Shamir (offline) protocol modules:
– FSProver.py, FSVerifier.py, FSPMFProver.py, FSPMFVerifier.py, FSGKR.py – generate and verify non-interactive proofs.
- GKR modules:
– GKR.py, GKRProver.py, GKRVerifier.py – sum-check specialized for the GKR function.
- Tests: prefixed with test_*.py, skip_test_*.py – unit tests for each component.

##### README for additional insights
- The README describes how to create multilinear polynomials, initialize provers/verifiers, perform interactive sums, and run offline proofs.
- It calls out the mathematical core, the interactive flow (talk rounds), and the offline Fiat–Shamir transform.

a. Components
- Math Core Layer
– MVLinear class (polynomial.py)
– multilinear_extension utilities
– PMF class (PMF.py)
- Interactive Protocol Layer
– InteractiveLinearProver (IPProverLinear.py)
– InteractivePMFProver (IPPMFProver.py)
– InteractiveVerifier (IPVerifier.py)
– InteractivePMFVerifier (IPPMFVerifier.py)
- Offline (Fiat–Shamir) Protocol Layer
– FSProver, FSVerifier (single polynomial)
– FSPMFProver, FSPMFVerifier (PMF)
– FSGKR (GKR offline)
- GKR Specialized Layer
– GKR, GKRProver, GKRVerifier
- Test Suite & CI
– Unit tests (test_*.py)
– CI workflow (.github/workflows/test.yml)

b. Relationships and data flows
- Prover modules depend on and call into the Math Core Layer to compute sums and evaluations.
- Verifier modules also depend on Math Core to check polynomials and partial sums.
- Test Suite imports and exercises all above components; CI runs tests automatically.

c. Architectural patterns and principles
- Layered separation:
– Core math abstractions are independent from protocol logic.
– Interactive vs offline protocols form separate layers.
– Specialized extensions (PMF, GKR) plug into the core+protocol layers.
- Dependency injection: verifiers receive a random seed, polynomial object, and asserted sum at initialization.
- Reuse: the same MVLinear class is reused across all protocols.

d. Key technologies/libraries
- Python 3.x, built-in random and math libraries.
- No external dependencies beyond the standard library.
- GitHub Actions for CI.

##### Elements
- Clear labels for each layer and module group (Math Core, Interactive, Offline, GKR, Tests/CI).
- Rectangles for components;

## Diagram (Mermaid)

```mermaid
flowchart TD
    subgraph "Math Core Layer"
        MC1["polynomial.py\n(MVLinear)"]:::core
        MC2["multilinear_extension.py"]:::core
        MC3["PMF.py"]:::core
    end

    subgraph "Interactive Protocol Layer"
        IP1["IPProverLinear.py"]:::interactive
        IP2["IPPMFProver.py"]:::interactive
        IV1["IPVerifier.py"]:::interactive
        IV2["IPPMFVerifier.py"]:::interactive
    end

    subgraph "Offline (Fiat–Shamir) Protocol Layer"
        FS1["FSProver.py"]:::offline
        FS2["FSVerifier.py"]:::offline
        FSP1["FSPMFProver.py"]:::offline
        FSP2["FSPMFVerifier.py"]:::offline
        FS3["FSGKR.py"]:::offline
    end

    subgraph "GKR Specialized Layer"
        G1["GKR.py"]:::gkr
        G2["GKRProver.py"]:::gkr
        G3["GKRVerifier.py"]:::gkr
    end

    subgraph "Tests & CI"
        T["Unit Tests"]:::tests
        CI["CI Pipeline"]:::tests
    end

    %% Dependencies on Math Core
    IP1 -->|depends on| MC1
    IP1 -->|depends on| MC2
    IP1 -->|depends on| MC3

    IP2 -->|depends on| MC1
    IP2 -->|depends on| MC2
    IP2 -->|depends on| MC3

    IV1 -->|depends on| MC1
    IV1 -->|depends on| MC2
    IV1 -->|depends on| MC3

    IV2 -->|depends on| MC1
    IV2 -->|depends on| MC2
    IV2 -->|depends on| MC3

    FS1 -->|uses core| MC1
    FS1 -->|uses core| MC2
    FS1 -->|uses core| MC3

    FSP1 -->|uses core| MC1
    FSP1 -->|uses core| MC2
    FSP1 -->|uses core| MC3

    FS2 -->|uses core| MC1
    FS2 -->|uses core| MC2
    FS2 -->|uses core| MC3

    FSP2 -->|uses core| MC1
    FSP2 -->|uses core| MC2
    FSP2 -->|uses core| MC3

    G2 -->|builds on core| MC1
    G2 -->|builds on core| MC2
    G2 -->|builds on core| MC3

    G3 -->|builds on core| MC1
    G3 -->|builds on core| MC2
    G3 -->|builds on core| MC3

    %% Interactive protocol flow
    IP1 <-->|"rounds of univariate evaluations & random challenges"| IV1
    IP2 <-->|"rounds of univariate evaluations & random challenges"| IV2

    %% Offline protocol flow
    FS1 -->|"theorem & proof"| FS2
    FSP1 -->|"theorem & proof"| FSP2
    FS3 -->|"GKR proof"| FS2

    %% Tests & CI flows
    T -.-> IP1
    T -.-> IP2
    T -.-> IV1
    T -.-> IV2
    T -.-> FS1
    T -.-> FS2
    T -.-> FSP1
    T -.-> FSP2
    T -.-> FS3
    T -.-> G1
    T -.-> G2
    T -.-> G3
    CI -.-> T

    %% Click Events
    click MC1 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/polynomial.py"
    click MC2 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/multilinear_extension.py"
    click MC3 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/PMF.py"
    click IP1 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/IPProverLinear.py"
    click IP2 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/IPPMFProver.py"
    click IV1 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/IPVerifier.py"
    click IV2 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/IPPMFVerifier.py"
    click FS1 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/FSProver.py"
    click FS2 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/FSVerifier.py"
    click FSP1 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/FSPMFProver.py"
    click FSP2 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/FSPMFVerifier.py"
    click FS3 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/FSGKR.py"
    click G1 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/GKR.py"
    click G2 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/GKRProver.py"
    click G3 "https://github.com/tsunrise/sumcheck_multilinear/blob/master/GKRVerifier.py"
    click CI "https://github.com/tsunrise/sumcheck_multilinear/blob/master/.github/workflows/test.yml"

    %% Styles
    classDef core fill:#cfe2f3,stroke:#084b8a,color:#084b8a;
    classDef interactive fill:#d9ead3,stroke:#38761d,color:#38761d;
    classDef offline fill:#fce5cd,stroke:#dc7633,color:#dc7633;
    classDef gkr fill:#ead1dc,stroke:#7e3878,color:#7e3878;
    classDef tests fill:#eeeeee,stroke:#666666,color:#666666;
```
