kimchi_msm/test/
proof_system.rs

1/// Tests for the proof system itself, targeting prover and verifier.
2
3#[cfg(test)]
4mod tests {
5
6    use crate::{
7        columns::Column,
8        expr::{
9            E, {self},
10        },
11        test::test_completeness_generic_only_relation,
12        witness::Witness,
13        Fp,
14    };
15    use ark_ff::{Field, One, UniformRand};
16    use kimchi::circuits::expr::{ConstantExpr, ConstantTerm};
17
18    // Test a constraint of degree one: X_{0} - X_{1}
19    #[test]
20    fn test_completeness_degree_one() {
21        let mut rng = o1_utils::tests::make_test_rng(None);
22        const N: usize = 2;
23        let domain_size = 1 << 8;
24
25        let constraints = {
26            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
27            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
28            vec![x0.clone() - x1]
29        };
30
31        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
32        let exp_x1 = random_x0s.clone();
33        let witness: Witness<N, Vec<Fp>> = Witness {
34            cols: Box::new([random_x0s, exp_x1]),
35        };
36
37        test_completeness_generic_only_relation::<N, _>(
38            constraints.clone(),
39            witness.clone(),
40            domain_size,
41            &mut rng,
42        );
43        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
44        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
45        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
46    }
47
48    // Test a constraint of degree two: X_{0} * X_{0} - X_{1} - X_{2}
49    #[test]
50    fn test_completeness_degree_two() {
51        let mut rng = o1_utils::tests::make_test_rng(None);
52        const N: usize = 3;
53        let domain_size = 1 << 8;
54
55        let constraints = {
56            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
57            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
58            let x2 = expr::curr_cell::<Fp>(Column::Relation(2));
59            vec![x0.clone() * x0.clone() - x1.clone() - x2.clone()]
60        };
61
62        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
63        let random_x1s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
64        let exp_x2 = random_x0s
65            .iter()
66            .zip(random_x1s.iter())
67            .map(|(x0, x1)| (*x0) * (*x0) - x1)
68            .collect::<Vec<Fp>>();
69        let witness: Witness<N, Vec<Fp>> = Witness {
70            cols: Box::new([random_x0s, random_x1s, exp_x2]),
71        };
72
73        test_completeness_generic_only_relation::<N, _>(
74            constraints.clone(),
75            witness.clone(),
76            domain_size,
77            &mut rng,
78        );
79        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
80        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
81        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
82    }
83
84    // Test a constraint of degree three:
85    //   X_{0} * X_{0} * X_{0} \
86    // - 42 * X_{1} * X_{2} \
87    // + X_{3}
88    #[test]
89    fn test_completeness_degree_three() {
90        let mut rng = o1_utils::tests::make_test_rng(None);
91        const N: usize = 4;
92        let domain_size = 1 << 8;
93
94        let constraints = {
95            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
96            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
97            let x2 = expr::curr_cell::<Fp>(Column::Relation(2));
98            let x3 = expr::curr_cell::<Fp>(Column::Relation(3));
99            vec![
100                x0.clone() * x0.clone() * x0.clone() - E::from(42) * x1.clone() * x2.clone()
101                    + x3.clone(),
102            ]
103        };
104
105        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
106        let random_x1s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
107        let random_x2s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
108        let exp_x3 = random_x0s
109            .iter()
110            .zip(random_x1s.iter())
111            .zip(random_x2s.iter())
112            .map(|((x0, x1), x2)| -((*x0) * (*x0) * (*x0) - Fp::from(42) * (*x1) * (*x2)))
113            .collect::<Vec<Fp>>();
114        let witness: Witness<N, Vec<Fp>> = Witness {
115            cols: Box::new([random_x0s, random_x1s, random_x2s, exp_x3]),
116        };
117
118        test_completeness_generic_only_relation::<N, _>(
119            constraints.clone(),
120            witness.clone(),
121            domain_size,
122            &mut rng,
123        );
124        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
125        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
126        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
127    }
128
129    #[test]
130    // X_{0} * (X_{1} * X_{2} * X_{3} + 1)
131    fn test_completeness_degree_four() {
132        let mut rng = o1_utils::tests::make_test_rng(None);
133        const N: usize = 4;
134        let domain_size = 1 << 8;
135
136        let constraints = {
137            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
138            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
139            let x2 = expr::curr_cell::<Fp>(Column::Relation(2));
140            let x3 = expr::curr_cell::<Fp>(Column::Relation(3));
141            let one = ConstantExpr::from(ConstantTerm::Literal(Fp::one()));
142            vec![x0.clone() * (x1.clone() * x2.clone() * x3.clone() + E::constant(one))]
143        };
144
145        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
146        let random_x1s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
147        let random_x2s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
148        let exp_x3 = random_x1s
149            .iter()
150            .zip(random_x2s.iter())
151            .map(|(x1, x2)| -Fp::one() / (*x1 * *x2))
152            .collect::<Vec<Fp>>();
153        let witness: Witness<N, Vec<Fp>> = Witness {
154            cols: Box::new([random_x0s, random_x1s, random_x2s, exp_x3]),
155        };
156
157        test_completeness_generic_only_relation::<N, _>(
158            constraints.clone(),
159            witness.clone(),
160            domain_size,
161            &mut rng,
162        );
163        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
164        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
165        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
166    }
167
168    #[test]
169    // X_{0}^5 + X_{1}
170    fn test_completeness_degree_five() {
171        let mut rng = o1_utils::tests::make_test_rng(None);
172        const N: usize = 2;
173        let domain_size = 1 << 8;
174
175        let constraints = {
176            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
177            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
178            vec![x0.clone() * x0.clone() * x0.clone() * x0.clone() * x0.clone() + x1.clone()]
179        };
180
181        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
182        let exp_x1 = random_x0s
183            .iter()
184            .map(|x0| -*x0 * *x0 * *x0 * *x0 * *x0)
185            .collect::<Vec<Fp>>();
186        let witness: Witness<N, Vec<Fp>> = Witness {
187            cols: Box::new([random_x0s, exp_x1]),
188        };
189
190        test_completeness_generic_only_relation::<N, _>(
191            constraints.clone(),
192            witness.clone(),
193            domain_size,
194            &mut rng,
195        );
196        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
197        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
198        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
199    }
200
201    #[test]
202    // X_{0}^3 + X_{1} AND X_{2}^2 - 3 X_{3}
203    fn test_completeness_different_constraints_different_degrees() {
204        let mut rng = o1_utils::tests::make_test_rng(None);
205        const N: usize = 4;
206        let domain_size = 1 << 8;
207
208        let constraints = {
209            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
210            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
211            let cst1 = x0.clone() * x0.clone() * x0.clone() + x1.clone();
212            let x2 = expr::curr_cell::<Fp>(Column::Relation(2));
213            let x3 = expr::curr_cell::<Fp>(Column::Relation(3));
214            let three = ConstantExpr::from(ConstantTerm::Literal(Fp::from(3)));
215            let cst2 = x2.clone() * x2.clone() - E::constant(three) * x3.clone();
216            vec![cst1, cst2]
217        };
218
219        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
220        let exp_x1 = random_x0s
221            .iter()
222            .map(|x0| -*x0 * *x0 * *x0)
223            .collect::<Vec<Fp>>();
224        let random_x2s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
225        let exp_x3: Vec<Fp> = random_x2s
226            .iter()
227            .map(|x2| (Fp::one() / Fp::from(3)) * x2 * x2)
228            .collect::<Vec<Fp>>();
229        let witness: Witness<N, Vec<Fp>> = Witness {
230            cols: Box::new([random_x0s, exp_x1, random_x2s, exp_x3]),
231        };
232
233        test_completeness_generic_only_relation::<N, _>(
234            constraints.clone(),
235            witness.clone(),
236            domain_size,
237            &mut rng,
238        );
239        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
240        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
241        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
242    }
243
244    #[test]
245    // X_{0}^6 + X_{1}^4 - X_{2}^3 - 2 X_{3}
246    fn test_completeness_degree_six() {
247        let mut rng = o1_utils::tests::make_test_rng(None);
248        const N: usize = 4;
249        let domain_size = 1 << 8;
250
251        let constraints = {
252            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
253            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
254            let x2 = expr::curr_cell::<Fp>(Column::Relation(2));
255            let x3 = expr::curr_cell::<Fp>(Column::Relation(3));
256            let x0_square = x0.clone() * x0.clone();
257            let x1_square = x1.clone() * x1.clone();
258            let x2_square = x2.clone() * x2.clone();
259            let two = ConstantExpr::from(ConstantTerm::Literal(Fp::from(2)));
260            vec![
261                x0_square.clone() * x0_square.clone() * x0_square.clone()
262                    + x1_square.clone() * x1_square.clone()
263                    - x2_square.clone() * x2.clone()
264                    - E::constant(two) * x3.clone(),
265            ]
266        };
267
268        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
269        let random_x1s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
270        let random_x2s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
271        let exp_x3 = random_x0s
272            .iter()
273            .zip(random_x1s.iter())
274            .zip(random_x2s.iter())
275            .map(|((x0, x1), x2)| {
276                let x0_square = x0.clone().square();
277                let x1_square = x1.clone().square();
278                let x2_square = x2.clone().square();
279                let x0_six = x0_square * x0_square * x0_square;
280                let x1_four = x1_square * x1_square;
281                (Fp::one() / Fp::from(2)) * (x0_six + x1_four - x2_square * x2)
282            })
283            .collect::<Vec<Fp>>();
284        let witness: Witness<N, Vec<Fp>> = Witness {
285            cols: Box::new([random_x0s, random_x1s, random_x2s, exp_x3]),
286        };
287
288        test_completeness_generic_only_relation::<N, _>(
289            constraints.clone(),
290            witness.clone(),
291            domain_size,
292            &mut rng,
293        );
294        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
295        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
296        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
297    }
298
299    #[test]
300    // X_{0}^7 + X_{1}^4 - X_{2}^3 - 2 X_{3}
301    fn test_completeness_degree_seven() {
302        let mut rng = o1_utils::tests::make_test_rng(None);
303        const N: usize = 4;
304        let domain_size = 1 << 8;
305
306        let constraints = {
307            let x0 = expr::curr_cell::<Fp>(Column::Relation(0));
308            let x1 = expr::curr_cell::<Fp>(Column::Relation(1));
309            let x2 = expr::curr_cell::<Fp>(Column::Relation(2));
310            let x3 = expr::curr_cell::<Fp>(Column::Relation(3));
311            let x0_square = x0.clone() * x0.clone();
312            let x1_square = x1.clone() * x1.clone();
313            let x2_square = x2.clone() * x2.clone();
314            let two = ConstantExpr::from(ConstantTerm::Literal(Fp::from(2)));
315            vec![
316                x0_square.clone() * x0_square.clone() * x0_square.clone() * x0.clone()
317                    + x1_square.clone() * x1_square.clone()
318                    - x2_square.clone() * x2.clone()
319                    - E::constant(two) * x3.clone(),
320            ]
321        };
322
323        let random_x0s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
324        let random_x1s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
325        let random_x2s: Vec<Fp> = (0..domain_size).map(|_| Fp::rand(&mut rng)).collect();
326        let exp_x3 = random_x0s
327            .iter()
328            .zip(random_x1s.iter())
329            .zip(random_x2s.iter())
330            .map(|((x0, x1), x2)| {
331                let x0_square = x0.clone().square();
332                let x1_square = x1.clone().square();
333                let x2_square = x2.clone().square();
334                let x0_six = x0_square * x0_square * x0_square * x0;
335                let x1_four = x1_square * x1_square;
336                (Fp::one() / Fp::from(2)) * (x0_six + x1_four - x2_square * x2)
337            })
338            .collect::<Vec<Fp>>();
339        let witness: Witness<N, Vec<Fp>> = Witness {
340            cols: Box::new([random_x0s, random_x1s, random_x2s, exp_x3]),
341        };
342
343        test_completeness_generic_only_relation::<N, _>(
344            constraints.clone(),
345            witness.clone(),
346            domain_size,
347            &mut rng,
348        );
349        // FIXME: we would want to allow the prover to make a proof, but the verification must fail.
350        // TODO: Refactorize code in prover to handle a degug or add an adversarial prover.
351        // test_soundness_generic(constraints, witness, domain_size, &mut rng);
352    }
353}
kimchi_msm/test/proof_system.rs

kimchi_msm/test/
proof_system.rs
