Tiny STARK Java

An educational tiny STARK protocol engine in Java 21.

This repository contains reusable protocol pieces plus a small example statement. The example proves a public square relation, f = x * x, while the generic protocol code stays independent of that specific computation.

The implementation is small on purpose, with commented source code that follows the main STARK layers: field arithmetic, polynomial interpolation, trace commitments, AIR composition, Fiat-Shamir, Merkle openings, toy FRI, proof serialization, and a generic protocol API.

This is not production cryptography. It is a learning implementation designed to make the protocol shape visible.

Current Status

The reusable educational protocol is implemented end to end:

• Goldilocks prime field arithmetic
• polynomial operations and Lagrange interpolation
• power-of-two evaluation domains
• expression-based AIR definitions
• generic composition construction for expression-based AIR
• generic proof object, prover, verifier, and codec
• example package proving f = x * x
• trace low-degree-extension commitment
• SHA-256 Merkle commitments and openings
• Fiat-Shamir transcript
• sampled trace and composition query checks
• toy FRI folding checks for the composition codeword
• deterministic proof binary codec

Quick Start

Run tests:

./mvnw -q test

Compile:

./mvnw -q compile

Create and verify a square proof:

java -cp target/classes io.tinystark.cli.TinyStarkCli prove-square 7 square.proof
java -cp target/classes io.tinystark.cli.TinyStarkCli verify-square square.proof

Project Map

src/main/java/io/tinystark/
- air/          generic AIR interface and expression-based AIR constraints
- cli/          minimal command-line entry point
- commitment/   SHA-256 Merkle tree and Merkle proofs
- composition/  generic composition quotient polynomials
- domain/       power-of-two evaluation domains
- example/      concrete example statements built on the generic protocol
- field/        Goldilocks field implementation
- fri/          toy FRI prover, verifier, proof objects
- polynomial/   polynomial arithmetic and interpolation
- protocol/     generic STARK protocol, proof objects, prover, verifier, and codec
- trace/        trace table
- transcript/   Fiat-Shamir transcript

Detailed theory and protocol notes:

• STARK protocol flow diagram
• STARK layers theory
• Tiny STARK protocol notes

Adding A Statement

Small statements can be written as AIR formulas instead of custom composition code. A statement should provide:

1. a trace generator
2. a ProgramAir built from expression constraints
3. public input labels and values
4. optional CLI glue if it should be runnable from the command line

The reusable protocol entry points are:

• StarkProver.prove(StarkStatement)
• StarkVerifier.verify(StarkProof, ProgramAir)
• StarkProofCodec.encode(...)
• StarkProofCodec.decode(...)

See io.tinystark.example.SquareStatement for the smallest concrete example. It builds a two-column trace where column 0 is x, column 1 is f, and the AIR constraint enforces f - x*x = 0.

Prover Flow

At a high level, the generic prover:

1. Receives a StarkStatement.
2. Checks that the witness trace satisfies the AIR.
3. Interpolates trace columns over the execution domain.
4. Evaluates the trace low-degree extension over the larger composition domain.
5. Commits to trace LDE rows with a Merkle tree.
6. Samples random composition challenges from the transcript.
7. Builds the composition polynomial by dividing AIR numerators by their zerofiers.
8. Commits to the composition codeword.
9. Commits to FRI folded codewords.
10. Samples query indices after all commitments are transcript-bound.
11. Opens trace rows, shifted trace rows, composition values, and FRI paths.
12. Returns a deterministic proof object.

Verifier Flow

The generic verifier:

1. Replays public inputs into the Fiat-Shamir transcript.
2. Recomputes composition challenges from the trace root.
3. Replays composition and FRI roots into the transcript.
4. Recomputes query indices.
5. Verifies Merkle openings for trace LDE rows and composition values.
6. Recomputes composition values from opened trace values and AIR constraints.
7. Verifies toy FRI folding paths and the final constant layer.

Educational Scope

This project is useful for learning the shape of a STARK, but it intentionally leaves out many production requirements:

• no security parameter calibration
• no optimized FFT/NTT implementation
• no grinding or proof-of-work against transcript bias
• no domain separation audit beyond simple labels
• no constant-time side-channel review
• no production-grade FRI batching or DEEP-FRI
• only a small expression-based AIR builder, not a complete AIR language
• no formal soundness analysis for chosen parameters

Treat it as a readable tiny STARK, not as a secure proving system.

Spring Boot Note

The repository still contains a minimal Spring Boot application generated at the start of the project. The STARK protocol does not depend on the web endpoint; the library packages are the main implementation.