Skip to main content

Crate kronecker_fri

Crate kronecker_fri 

Source
Expand description

Kronecker-FRI: a hash-based multilinear polynomial commitment from the coefficient-extraction identity f(z) = [X^{N-1}] U_f(X) K_z(X).

Reference implementation of the paper https://github.com/qoosmo/kronecker-fri/blob/main/paper/kronecker-fri.pdf.

use kronecker_fri::field::{Fp, Fp2};
use kronecker_fri::pcs::{Params, commit_table, open, verify};

// n = 10 variables; rate 1/4, arity 8, Merkle caps, 148 queries, 32-byte salts
let p = Params::recommended(10, 148, 32);
let table: Vec<Fp> = (0..1u64 << 10).map(Fp::new).collect(); // f on {0,1}^10
let z: Vec<Fp2> = (0..10u64).map(|i| Fp2(Fp::new(3 + i), Fp::new(7 * i))).collect();
// The salts of the Merkle trees are drawn from the operating system.
let (root, pd) = commit_table(&p, &table)?;
let (v, proof) = open(&p, &pd, &z)?; // v = f(z)
assert!(verify(&p, &root, &z, v, &proof).is_ok());

The modules field, poly, merkle and pcs implement the paper and form the stable API. The other public modules are research prototypes of the note https://github.com/qoosmo/kronecker-fri/blob/main/notes/inner-product/note.pdf; their API may change between versions. Feature parallel: multithreaded prover, identical proofs.

Module map:

  • field: Goldilocks F_p and the extensions F_{p^2}, F_{p^4} (Sections 6.1, 8.4);
  • poly: Moebius transform, NTT, kernel polynomial and product, opening polynomials, folds (Sections 2, 4, 5);
  • merkle: salted Merkle trees and the Fiat-Shamir transcript (Sections 3.4, 8.1);
  • pcs: commitment, prover and verifier of Pi_KF (Section 6);
  • ip: prototype of the sumcheck-free inner-product protocol Pi_IP (research note notes/inner-product, Section 2);
  • had: prototype of the sumcheck-free Hadamard check Pi_Had (same note, Section 3);
  • affine: Pi_Batch on affine forms of committed and public tables (same note, Prop. 5.1);
  • batch: prototype of Pi_Batch, any list of evaluations, inner products and Hadamard checks in one folding test (same note, Section 4);
  • lincheck: clear-text check of the sumcheck-free lincheck reduction (same note, Section 5);
  • r1cs: prototype of the sumcheck-free R1CS argument (same note, Section 5.3);
  • spartan: baseline, the core of a Spartan-style R1CS argument (two sumchecks and one Pi_KF opening) on the same commitment, for the comparison of the same note, Section 5.3;
  • sumcheck: baselines, one inner product and one Hadamard check by sumcheck, closed by a batched opening (same note, Section 6);
  • par (internal): the optional multithreaded prover (feature parallel, rayon); proofs are identical with and without it;
  • ft: the folding test on a batched word and level-0 coset openings, shared by had and batch.

Modules§

affine
Pi_Batch on affine forms (research note notes/inner-product, Proposition 5.1): evaluation, inner-product and Hadamard statements whose arguments are affine forms sum_i c_i w_i + sum_j d_j P_j of committed words w_i and public tables P_j, proved with one folding test.
batch
Prototype of the batched protocol Pi_Batch (research note notes/inner-product, Section 4): any list of evaluation claims, inner-product claims and Hadamard checks on table-form commitments, proved with one folding test.
error
Errors returned by the verifiers and by parameter validation.
field
Goldilocks field F_p, p = 2^64 - 2^32 + 1, its quadratic extension F_p[u]/(u^2 - 7), and its quartic extension F_p[i]/(i^4 - 7) = F_{p^2}[v]/(v^2 - u) with v = i, u = i^2.
ft
Shared pieces of the protocols built on one folding test (had): the folding test Pi_FT on a batched word w_0 (rounds 2 .. l+2 of pcs::open_with) and coset openings of level-0 oracles. The code is that of pcs, factored so that a protocol only supplies w_0, its polynomial U_0, and the level-0 oracles it reads.
had
Prototype of the sumcheck-free Hadamard check Pi_Had (research note notes/inner-product, Section 3): for committed tables a, b, c (table form, as in ip), prove a(w) b(w) = c(w) for all w in {0,1}^n.
ip
Prototype of the sumcheck-free inner-product protocol Pi_IP (research note notes/inner-product, Section 2; Lean: KroneckerFRI/InnerProduct.lean).
lincheck
Clear-text check of the sumcheck-free lincheck of the research note (notes/inner-product, Section 5): the reduction of a' = M z (M a public sparse matrix, z and a’ committed tables) to evaluation, inner-product and Hadamard statements on affine forms of committed and public tables. This module computes the prover’s tables and checks the statements directly (no commitments, no folding test): it validates the algebra of the reduction before it is compiled with batch.
merkle
Salted BLAKE3 Merkle trees (Section 3.4, “Salted Merkle commitments”) and the Fiat-Shamir transcript with the challenge maps phi and pos of Section 8.1.
pcs
The evaluation protocol Pi_KF of Section 6.3, compiled with salted Merkle trees and a Fiat-Shamir transcript (Sections 3.4 and 8.1), with folding of arity 2^k (Section 5.7) and Merkle caps.
poly
Univariate and multilinear helpers: Moebius transform (Lemma 2.6), NTT (Fact 6.4), kernel polynomial and kernel product (Section 4), and the kernel fold (Section 5).
r1cs
Prototype of the sumcheck-free R1CS argument of the research note (notes/inner-product, Section 5.3, Theorem 5.8): (Az) o (Bz) = Cz with z = x_hat + w, for public sparse A, B, C (committed once by an honest indexer), a public input x at fixed positions, and a committed witness w (zero on the input positions).
spartan
Baseline for the research note (notes/inner-product, Section 5.3): the core of a Spartan-style R1CS argument on the same commitment, field, hash and instances as r1cs.
sumcheck
Baselines for the research note (notes/inner-product, Section 6): one inner product and one Hadamard check on committed tables, by two routes that share the same commitments (one group per table, affine::commit_group) and the same proof engine (affine::prove_affine):