freivalds-stwo

A STARK-based prover for proving matrix multiplication efficiently using Freivalds' algorithm, built on Stwo.

What is Freivalds' Algorithm?

Freivalds' algorithm is a probabilistic method to verify that C = A × B without recomputing the full multiplication. Given a random vector r, it checks:

A × (B × r) == C × r

If the equation holds, then C = A × B with high probability. This reduces verification from O(n³) to O(n²).

This library generates a zero-knowledge STARK proof of this verification, allowing a verifier to trust the computation without recomputation.

Usage

use freivalds::{Matrix, MatmulInput, Prover, Verifier};

// Create matrices A and B, compute C = A × B
let a = Matrix::random(26, 42);
let b = Matrix::random(26, 43);
let input = MatmulInput::new_valid(a, b);

// Generate a STARK proof
let proof = Prover::new()
    .prove(&input)
    .expect("proving failed");

// Verify the proof
Verifier::new()
    .verify(proof)
    .expect("verification failed");

Public vs Private Matrices

You can configure which matrices are exposed to the verifier:

• Public: The verifier knows the matrix values (bound via LogUp).
• Private: The verifier only sees a Merkle commitment.

use freivalds::{Prover, PublicInputConfig};

// All matrices private
let proof = Prover::new()
    .with_public_config(PublicInputConfig::all_private())
    .prove(&input)?;

// Custom: A public, B and C private
let config = PublicInputConfig::default()
    .with_a_public(true)
    .with_b_public(false)
    .with_c_public(false);

let proof = Prover::new()
    .with_public_config(config)
    .prove(&input)?;

Running the Example

$ cargo run --package freivalds --release

>>>
Summary:
  Matrix generation: 1.854959ms
  Proof generation:  25.656792ms
  Verification:      323.958µs
  Total time:        27.835709ms

This generates and verifies a proof for 2048×2048 matrix multiplication.

Benchmarks

Run benchmarks comparing Freivalds vs naive matrix multiplication:

$ cargo run --package benchmarks --release --bin benchmark

The benchmarks measure proving time and verification time across multiple matrix sizes. Results show that Freivalds' algorithm provides significant speedups:

Matrix Size	Freivalds Prove Time	Freivalds Verify Time	Naive Prove Time	Naive Verify Time	Proving Speedup	Verification Speedup
128×128	24 ms	290 µs	1.41 s	460 µs	57.03×	1.58×
256×256	83 ms	340 µs	15.08 s	559 µs	181.69×	1.64×
512×512	210 ms	390 µs	-	-	—	—
1024×1024	748 ms	450 µs	-	-	—	—
2048×2048	3.03 s	470 µs	-	-	—	—

Note: Naive matmul benchmarks are limited to smaller sizes (≤512×512) due to domain size constraints, while Freivalds can scale to much larger matrices.

License

MIT