kimchi_msm/test/
generic.rs

1/// Generic test runners for prover/verifier.
2use crate::{
3    expr::E, logup::LookupTableID, lookups::LookupTableIDs, proof::ProofInputs, prover::prove,
4    verifier::verify, witness::Witness, BaseSponge, Fp, OpeningProof, ScalarSponge, BN254,
5};
6use ark_ec::AffineRepr;
7use kimchi::circuits::domains::EvaluationDomains;
8use poly_commitment::kzg::PairingSRS;
9use rand::{CryptoRng, RngCore};
10
11/// No lookups, no selectors, only witness column. `N_WIT == N_REL`.
12pub fn test_completeness_generic_only_relation<const N_REL: usize, RNG>(
13    constraints: Vec<E<Fp>>,
14    evaluations: Witness<N_REL, Vec<Fp>>,
15    domain_size: usize,
16    rng: &mut RNG,
17) where
18    RNG: RngCore + CryptoRng,
19{
20    test_completeness_generic_no_lookups::<N_REL, N_REL, 0, 0, _>(
21        constraints,
22        Box::new([]),
23        evaluations,
24        domain_size,
25        rng,
26    )
27}
28
29pub fn test_completeness_generic_no_lookups<
30    const N_WIT: usize,
31    const N_REL: usize,
32    const N_DSEL: usize,
33    const N_FSEL: usize,
34    RNG,
35>(
36    constraints: Vec<E<Fp>>,
37    fixed_selectors: Box<[Vec<Fp>; N_FSEL]>,
38    evaluations: Witness<N_WIT, Vec<Fp>>,
39    domain_size: usize,
40    rng: &mut RNG,
41) where
42    RNG: RngCore + CryptoRng,
43{
44    let proof_inputs = ProofInputs {
45        evaluations,
46        logups: Default::default(),
47    };
48    test_completeness_generic::<N_WIT, N_REL, N_DSEL, N_FSEL, LookupTableIDs, _>(
49        constraints,
50        fixed_selectors,
51        proof_inputs,
52        domain_size,
53        rng,
54    )
55}
56
57// Generic function to test with different circuits with the generic prover/verifier.
58// It doesn't use the interpreter to build the witness and compute the constraints.
59pub fn test_completeness_generic<
60    const N_WIT: usize,
61    const N_REL: usize,
62    const N_DSEL: usize,
63    const N_FSEL: usize,
64    LT: LookupTableID,
65    RNG,
66>(
67    constraints: Vec<E<Fp>>,
68    fixed_selectors: Box<[Vec<Fp>; N_FSEL]>,
69    proof_inputs: ProofInputs<N_WIT, Fp, LT>,
70    domain_size: usize,
71    rng: &mut RNG,
72) where
73    RNG: RngCore + CryptoRng,
74{
75    let domain = EvaluationDomains::<Fp>::create(domain_size).unwrap();
76
77    let srs: PairingSRS<BN254> = crate::precomputed_srs::get_bn254_srs(domain);
78
79    let proof =
80        prove::<_, OpeningProof, BaseSponge, ScalarSponge, _, N_WIT, N_REL, N_DSEL, N_FSEL, LT>(
81            domain,
82            &srs,
83            &constraints,
84            fixed_selectors.clone(),
85            proof_inputs.clone(),
86            rng,
87        )
88        .unwrap();
89
90    {
91        // Checking the proof size. We should have:
92        // - N commitments for the columns
93        // - N evaluations for the columns
94        // - MAX_DEGREE - 1 commitments for the constraints (quotient polynomial)
95        // TODO: add lookups
96
97        // We check there is always only one commitment chunk
98        (&proof.proof_comms.witness_comms)
99            .into_iter()
100            .for_each(|x| assert_eq!(x.len(), 1));
101        // This equality is therefore trivial, but still doing it.
102        assert!(
103            (&proof.proof_comms.witness_comms)
104                .into_iter()
105                .fold(0, |acc, x| acc + x.len())
106                == N_WIT
107        );
108        // Checking that none of the commitments are zero
109        (&proof.proof_comms.witness_comms)
110            .into_iter()
111            .for_each(|v| v.chunks.iter().for_each(|x| assert!(!x.is_zero())));
112
113        // Checking the number of chunks of the quotient polynomial
114        let max_degree = {
115            if proof_inputs.logups.is_empty() {
116                constraints
117                    .iter()
118                    .map(|expr| expr.degree(1, 0))
119                    .max()
120                    .unwrap_or(0)
121            } else {
122                8
123            }
124        };
125
126        if max_degree == 1 {
127            assert_eq!(proof.proof_comms.t_comm.len(), 1);
128        } else {
129            assert_eq!(proof.proof_comms.t_comm.len(), max_degree as usize - 1);
130        }
131    }
132
133    let verifies =
134        verify::<_, OpeningProof, BaseSponge, ScalarSponge, N_WIT, N_REL, N_DSEL, N_FSEL, 0, LT>(
135            domain,
136            &srs,
137            &constraints,
138            fixed_selectors,
139            &proof,
140            Witness::zero_vec(domain_size),
141        );
142    assert!(verifies)
143}
144
145pub fn test_soundness_generic<
146    const N_WIT: usize,
147    const N_REL: usize,
148    const N_DSEL: usize,
149    const N_FSEL: usize,
150    LT: LookupTableID,
151    RNG,
152>(
153    constraints: Vec<E<Fp>>,
154    fixed_selectors: Box<[Vec<Fp>; N_FSEL]>,
155    proof_inputs: ProofInputs<N_WIT, Fp, LT>,
156    proof_inputs_prime: ProofInputs<N_WIT, Fp, LT>,
157    domain_size: usize,
158    rng: &mut RNG,
159) where
160    RNG: RngCore + CryptoRng,
161{
162    let domain = EvaluationDomains::<Fp>::create(domain_size).unwrap();
163
164    let srs: PairingSRS<BN254> = crate::precomputed_srs::get_bn254_srs(domain);
165
166    // generate the proof
167    let proof =
168        prove::<_, OpeningProof, BaseSponge, ScalarSponge, _, N_WIT, N_REL, N_DSEL, N_FSEL, LT>(
169            domain,
170            &srs,
171            &constraints,
172            fixed_selectors.clone(),
173            proof_inputs,
174            rng,
175        )
176        .unwrap();
177
178    // generate another (prime) proof
179    let proof_prime =
180        prove::<_, OpeningProof, BaseSponge, ScalarSponge, _, N_WIT, N_REL, N_DSEL, N_FSEL, LT>(
181            domain,
182            &srs,
183            &constraints,
184            fixed_selectors.clone(),
185            proof_inputs_prime,
186            rng,
187        )
188        .unwrap();
189
190    // Swap the opening proof. The verification should fail.
191    {
192        let mut proof_clone = proof.clone();
193        proof_clone.opening_proof = proof_prime.opening_proof;
194        let verifies = verify::<
195            _,
196            OpeningProof,
197            BaseSponge,
198            ScalarSponge,
199            N_WIT,
200            N_REL,
201            N_DSEL,
202            N_FSEL,
203            0,
204            LT,
205        >(
206            domain,
207            &srs,
208            &constraints,
209            fixed_selectors.clone(),
210            &proof_clone,
211            Witness::zero_vec(domain_size),
212        );
213        assert!(!verifies, "Proof with a swapped opening must fail");
214    }
215
216    // Changing at least one commitment in the proof should fail the verification.
217    // TODO: improve me by swapping only one commitments. It should be
218    // easier when an index trait is implemented.
219    {
220        let mut proof_clone = proof.clone();
221        proof_clone.proof_comms = proof_prime.proof_comms;
222        let verifies = verify::<
223            _,
224            OpeningProof,
225            BaseSponge,
226            ScalarSponge,
227            N_WIT,
228            N_REL,
229            N_DSEL,
230            N_FSEL,
231            0,
232            LT,
233        >(
234            domain,
235            &srs,
236            &constraints,
237            fixed_selectors.clone(),
238            &proof_clone,
239            Witness::zero_vec(domain_size),
240        );
241        assert!(!verifies, "Proof with a swapped commitment must fail");
242    }
243
244    // Changing at least one evaluation at zeta in the proof should fail
245    // the verification.
246    // TODO: improve me by swapping only one evaluation at \zeta. It should be
247    // easier when an index trait is implemented.
248    {
249        let mut proof_clone = proof.clone();
250        proof_clone.proof_evals.witness_evals = proof_prime.proof_evals.witness_evals;
251        let verifies = verify::<
252            _,
253            OpeningProof,
254            BaseSponge,
255            ScalarSponge,
256            N_WIT,
257            N_REL,
258            N_DSEL,
259            N_FSEL,
260            0,
261            LT,
262        >(
263            domain,
264            &srs,
265            &constraints,
266            fixed_selectors,
267            &proof_clone,
268            Witness::zero_vec(domain_size),
269        );
270        assert!(!verifies, "Proof with a swapped witness eval must fail");
271    }
272}
kimchi_msm/test/generic.rs

kimchi_msm/test/
generic.rs
