A hash-based multilinear polynomial commitment whose evaluation proofs use no sumcheck: an evaluation is one coefficient of a product, checked by plain FRI.
The coefficient of XN−1−a in Kz is the monomial value za. Multiplying by the coefficient vector of f puts f(z) = Σa αaza at the degree N−1. Try it over 𝔽17 with three variables.
Click a coefficient to change it.
The highlighted coefficient is the one of X7.
The prover splits X Uf Kz = A + v XN + XN+1H with A, H of degree < N. If such polynomials exist, v must be the right value (Lemma 4.12).
Evaluate Uf on a smooth multiplicative domain of order M = 4N (one NTT) and publish a Merkle root, one leaf per fibre {±ξ}.
The prover commits to A only. The verifier never receives H: at each query it computes h(ξ) = (ξw(ξ)Kz(ξ) − wA(ξ) − vξN) / ξN+1, a virtual word.
A random β merges the commitment, wA and h into one word. If the claimed value is wrong, h contains the term c/ξ, which agrees with any low-degree codeword on at most N points.
Plain FRI with the kernel fold, down to a final polynomial, then κ queries. The verifier is an FRI verifier plus O(n) field operations per query. No sumcheck.
Self-contained proofs in the unique-decoding regime. The only external result about codes is the correlated-agreement theorem of Ben-Sasson, Carmon, Ishai, Kopparty and Saraf.
f(z) = [XN−1] UfKz; the split into opening polynomials, and why the factor X makes the degree bound N sufficient.
Fibre distance, good challenges, witness sets and the codeword chain, stated for any prover so they serve as the round-by-round state.
Correlated agreement for curves of degree 2 plus the identity lemma, through the virtual word. Error below 3M/|𝔽| + (1−δ)κ.
Round-by-round knowledge soundness with a decoding extractor, and evaluation binding.
Straightline knowledge soundness of the compiled scheme in the quantum random oracle model (Chiesa–Di–Hu–Zheng), for one opening: εext < 2−31.8 at 264 queries.
m polynomials at one point for the cost of one opening, with error (m−1)M/|𝔽| + εKF, in fibre distance.
One core, ρ = 1/4, κ = 148 (100-bit query term), Goldilocks with a quadratic extension, unsalted trees, recommended configuration: folding arity 8, Merkle caps of 128 nodes, ℓ = n − 8. The soundness error is the same as for binary folding (Prop 5.28).
| n | Commit | Open | Verify | Proof |
|---|---|---|---|---|
| 16 | 41 ms | 92 ms | 2.4 ms | 184 KiB |
| 18 | 160 ms | 388 ms | 3.0 ms | 248 KiB |
| 20 | 0.73 s | 1.69 s | 3.4 ms | 299 KiB |
| 22 | 3.18 s | 9.28 s | 4.5 ms | 372 KiB |
At identical engineering (n = 20, binary folding, no caps, the configuration of the KBFold code), all measured in one session:
| Scheme | Commit | Open | Verify | Proof |
|---|---|---|---|---|
| Kronecker-FRI | 0.73 s | 2.14 s | 6.3 ms | 1117 KiB |
| KBFold (sumcheck + kernel folding) | 0.77 s | 0.71 s | 5.9 ms | 1072 KiB |
| Coefficient-form baseline (BaseFold-style) | 0.74 s | 0.60 s | 5.7 ms | 1072 KiB |
Commit and verify cost the same across n = 12 … 22, with proofs within 5%. The opening commits to A: the product UfKz, one NTT, one Merkle tree and the virtual word, each measured in the paper (Table 6).
sorry, one axiom (correlated agreement).@misc{Mkhida2026KroneckerFRI,
author = {Abdelali Mkhida},
title = {Kronecker-FRI: A Hash-Based Multilinear Polynomial
Commitment from a Coefficient-Extraction Identity},
year = {2026},
note = {Preprint},
url = {https://github.com/qoosmo/kronecker-fri}
}