Skip to main content

kronecker_fri/
lib.rs

1//! Kronecker-FRI: a hash-based multilinear polynomial commitment from the coefficient-extraction
2//! identity f(z) = [X^{N-1}] U_f(X) K_z(X).
3//!
4//! Reference implementation of the paper
5//! <https://github.com/qoosmo/kronecker-fri/blob/main/paper/kronecker-fri.pdf>.
6//!
7//! ```
8//! use kronecker_fri::field::{Fp, Fp2};
9//! use kronecker_fri::pcs::{Params, commit_table, open, verify};
10//!
11//! // n = 10 variables; rate 1/4, arity 8, Merkle caps, 148 queries, 32-byte salts
12//! let p = Params::recommended(10, 148, 32);
13//! let table: Vec<Fp> = (0..1u64 << 10).map(Fp::new).collect(); // f on {0,1}^10
14//! let z: Vec<Fp2> = (0..10u64).map(|i| Fp2(Fp::new(3 + i), Fp::new(7 * i))).collect();
15//! // The salts of the Merkle trees are drawn from the operating system.
16//! let (root, pd) = commit_table(&p, &table)?;
17//! let (v, proof) = open(&p, &pd, &z)?; // v = f(z)
18//! assert!(verify(&p, &root, &z, v, &proof).is_ok());
19//! # Ok::<(), kronecker_fri::error::Error>(())
20//! ```
21//!
22//! The modules `field`, `poly`, `merkle` and `pcs` implement the paper and form the stable API.
23//! The other public modules are research prototypes of the note
24//! <https://github.com/qoosmo/kronecker-fri/blob/main/notes/inner-product/note.pdf>; their API may
25//! change between versions. Feature `parallel`: multithreaded prover, identical proofs.
26//!
27//! Module map:
28//! - `field`: Goldilocks F_p and the extensions F_{p^2}, F_{p^4} (Sections 6.1, 8.4);
29//! - `poly`: Moebius transform, NTT, kernel polynomial and product, opening polynomials, folds
30//!   (Sections 2, 4, 5);
31//! - `merkle`: salted Merkle trees and the Fiat-Shamir transcript (Sections 3.4, 8.1);
32//! - `pcs`: commitment, prover and verifier of Pi_KF (Section 6);
33//! - `ip`: prototype of the sumcheck-free inner-product protocol Pi_IP (research note
34//!   `notes/inner-product`, Section 2);
35//! - `had`: prototype of the sumcheck-free Hadamard check Pi_Had (same note, Section 3);
36//! - `affine`: Pi_Batch on affine forms of committed and public tables (same note, Prop. 5.1);
37//! - `batch`: prototype of Pi_Batch, any list of evaluations, inner products and Hadamard checks
38//!   in one folding test (same note, Section 4);
39//! - `lincheck`: clear-text check of the sumcheck-free lincheck reduction (same note, Section 5);
40//! - `r1cs`: prototype of the sumcheck-free R1CS argument (same note, Section 5.3);
41//! - `spartan`: baseline, the core of a Spartan-style R1CS argument (two sumchecks and one
42//!   Pi_KF opening) on the same commitment, for the comparison of the same note, Section 5.3;
43//! - `sumcheck`: baselines, one inner product and one Hadamard check by sumcheck, closed by a
44//!   batched opening (same note, Section 6);
45//! - `par` (internal): the optional multithreaded prover (feature `parallel`, rayon); proofs
46//!   are identical with and without it;
47//! - `ft`: the folding test on a batched word and level-0 coset openings, shared by `had` and
48//!   `batch`.
49
50#![forbid(unsafe_code)]
51#![allow(clippy::needless_range_loop)] // index loops mirror the formulas of the paper
52
53pub mod affine;
54pub mod batch;
55pub mod error;
56pub mod field;
57pub mod ft;
58pub mod had;
59pub mod ip;
60pub mod lincheck;
61pub mod merkle;
62mod par;
63pub mod pcs;
64pub mod poly;
65pub mod r1cs;
66mod rand;
67pub mod spartan;
68pub mod sumcheck;
69
70/// Seeded provers for test vectors and reproducible digests (feature `insecure-test-vectors`).
71///
72/// **Insecure:** the seed determines every salt of the proof, so a reused or public seed breaks
73/// hiding and zero knowledge. Never enable this feature in production code.
74#[cfg(feature = "insecure-test-vectors")]
75#[doc(hidden)]
76pub mod insecure {
77    use crate::field::{ExtField, Fp};
78    use crate::merkle::Digest;
79    use crate::pcs::{Params, Proof, ProverData};
80
81    pub fn commit_coeffs(p: &Params, alpha: &[Fp], seed: &Digest) -> (Digest, ProverData) {
82        crate::pcs::commit_coeffs_seeded(p, alpha, seed)
83    }
84    pub fn commit_table(p: &Params, table: &[Fp], seed: &Digest) -> (Digest, ProverData) {
85        crate::pcs::commit_table_seeded(p, table, seed)
86    }
87    pub fn open<E: ExtField>(p: &Params, pd: &ProverData, z: &[E], seed: &Digest) -> (E, Proof<E>) {
88        crate::pcs::open_seeded(p, pd, z, seed)
89    }
90    pub fn open_in<E: ExtField>(
91        p: &Params,
92        tr: &mut crate::merkle::Transcript,
93        pd: &ProverData,
94        z: &[E],
95        seed: &Digest,
96    ) -> (E, Proof<E>) {
97        crate::pcs::open_in_seeded(p, tr, pd, z, seed)
98    }
99    pub fn commit_table_form(p: &Params, table: &[Fp], seed: &Digest) -> (Digest, ProverData) {
100        crate::ip::commit_table_form_seeded(p, table, seed)
101    }
102    pub fn prove_ip<E: ExtField>(
103        p: &Params,
104        pda: &ProverData,
105        pdb: &ProverData,
106        seed: &Digest,
107    ) -> (Fp, crate::ip::IpProof<E>) {
108        crate::ip::prove_ip_seeded(p, pda, pdb, seed)
109    }
110    pub fn prove_had<E: ExtField>(
111        p: &Params,
112        pda: &ProverData,
113        pdb: &ProverData,
114        pdc: &ProverData,
115        seed: &Digest,
116    ) -> crate::had::HadProof<E> {
117        crate::had::prove_had_seeded(p, pda, pdb, pdc, seed)
118    }
119    pub fn prove_batch<E: ExtField>(
120        p: &Params,
121        pds: &[&ProverData],
122        stmts: &[crate::batch::Stmt<E>],
123        seed: &Digest,
124    ) -> crate::batch::BatchProof<E> {
125        crate::batch::prove_batch_seeded(p, pds, stmts, seed)
126    }
127    pub fn index(p: &Params, r: &crate::r1cs::R1cs, seed: &Digest) -> crate::r1cs::Index {
128        crate::r1cs::index_seeded(p, r, seed)
129    }
130    pub fn prove_r1cs<E: ExtField>(
131        p: &Params,
132        r: &crate::r1cs::R1cs,
133        idx: &crate::r1cs::Index,
134        x: &[Fp],
135        wit: &[Fp],
136        seed: &Digest,
137    ) -> crate::r1cs::R1csProof<E> {
138        crate::r1cs::prove_r1cs_seeded(p, r, idx, x, wit, seed)
139    }
140}