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 notenotes/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 (featureparallel, rayon); proofs are identical with and without it;ft: the folding test on a batched word and level-0 coset openings, shared byhadandbatch.
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 formssum_i c_i w_i + sum_j d_j P_jof committed wordsw_iand public tablesP_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 ofpcs::open_with) and coset openings of level-0 oracles. The code is that ofpcs, 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 inip), 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 ofa' = 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 withbatch. - 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 asr1cs. - 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):