How tsunrise/sumcheck_multilinear works
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;