kimchi_msm/fec/
mod.rs

1pub mod columns;
2pub mod interpreter;
3pub mod lookups;
4
5#[cfg(test)]
6mod tests {
7
8    use crate::{
9        circuit_design::{ConstraintBuilderEnv, WitnessBuilderEnv},
10        columns::ColumnIndexer,
11        fec::{
12            columns::{FECColumn, FEC_N_COLUMNS},
13            interpreter::{constrain_ec_addition, ec_add_circuit},
14            lookups::LookupTable,
15        },
16        logup::LookupTableID,
17        Ff1, Fp,
18    };
19    use ark_ec::AffineRepr;
20    use ark_ff::UniformRand;
21    use rand::{CryptoRng, RngCore};
22    use std::{
23        collections::{BTreeMap, HashMap},
24        ops::Mul,
25    };
26
27    type FECWitnessBuilderEnv = WitnessBuilderEnv<
28        Fp,
29        FECColumn,
30        { <FECColumn as ColumnIndexer<usize>>::N_COL },
31        { <FECColumn as ColumnIndexer<usize>>::N_COL },
32        0,
33        0,
34        LookupTable<Ff1>,
35    >;
36
37    fn build_fec_addition_circuit<RNG: RngCore + CryptoRng>(
38        rng: &mut RNG,
39        domain_size: usize,
40    ) -> FECWitnessBuilderEnv {
41        use mina_curves::pasta::Pallas;
42        // Fq = Ff2
43        type Fq = <Pallas as AffineRepr>::ScalarField;
44
45        let mut witness_env = WitnessBuilderEnv::create();
46
47        // To support less rows than domain_size we need to have selectors.
48        //let row_num = rng.gen_range(0..domain_size);
49
50        let gen = Pallas::generator();
51
52        let kp: Fq = UniformRand::rand(rng);
53        let p: Pallas = gen.mul(kp).into();
54        let px: Ff1 = p.x;
55        let py: Ff1 = p.y;
56
57        for row_i in 0..domain_size {
58            let kq: Fq = UniformRand::rand(rng);
59            let q: Pallas = gen.mul(kq).into();
60
61            let qx: Ff1 = q.x;
62            let qy: Ff1 = q.y;
63
64            let (rx, ry) = ec_add_circuit(&mut witness_env, px, py, qx, qy);
65
66            let r: Pallas = ark_ec::models::short_weierstrass::Affine::new_unchecked(rx, ry);
67
68            assert!(
69                r == p + q,
70                "fec addition circuit does not compute actual p + q, expected {} got {r:?}",
71                p + q
72            );
73
74            if row_i < domain_size - 1 {
75                witness_env.next_row();
76            }
77        }
78
79        witness_env
80    }
81
82    #[test]
83    /// Builds the FF addition circuit with random values. The witness
84    /// environment enforces the constraints internally, so it is
85    /// enough to just build the circuit to ensure it is satisfied.
86    pub fn test_fec_addition_circuit() {
87        let mut rng = o1_utils::tests::make_test_rng(None);
88        build_fec_addition_circuit(&mut rng, 1 << 4);
89    }
90
91    #[test]
92    pub fn test_regression_relation_constraints_fec() {
93        let mut constraint_env = ConstraintBuilderEnv::<Fp, LookupTable<Ff1>>::create();
94        constrain_ec_addition::<Fp, Ff1, _>(&mut constraint_env);
95        let constraints = constraint_env.get_relation_constraints();
96
97        let mut constraints_degrees = HashMap::new();
98
99        assert_eq!(constraints.len(), 36);
100
101        {
102            constraints.iter().for_each(|c| {
103                let degree = c.degree(1, 0);
104                *constraints_degrees.entry(degree).or_insert(0) += 1;
105            });
106
107            assert_eq!(constraints_degrees.get(&1), None);
108            assert_eq!(constraints_degrees.get(&2), Some(&36));
109            assert_eq!(constraints_degrees.get(&3), None);
110
111            assert!(constraints.iter().map(|c| c.degree(1, 0)).max() <= Some(3));
112        }
113    }
114
115    #[test]
116    pub fn test_regression_constraints_fec() {
117        let mut constraint_env = ConstraintBuilderEnv::<Fp, LookupTable<Ff1>>::create();
118        constrain_ec_addition::<Fp, Ff1, _>(&mut constraint_env);
119        let constraints = constraint_env.get_constraints();
120
121        let mut constraints_degrees = HashMap::new();
122
123        assert_eq!(constraints.len(), 75);
124
125        {
126            constraints.iter().for_each(|c| {
127                let degree = c.degree(1, 0);
128                *constraints_degrees.entry(degree).or_insert(0) += 1;
129            });
130
131            assert_eq!(constraints_degrees.get(&1), Some(&1));
132            assert_eq!(constraints_degrees.get(&2), Some(&38));
133            assert_eq!(constraints_degrees.get(&3), None);
134            assert_eq!(constraints_degrees.get(&4), None);
135            assert_eq!(constraints_degrees.get(&5), Some(&2));
136            assert_eq!(constraints_degrees.get(&6), None);
137            assert_eq!(constraints_degrees.get(&7), Some(&34));
138        }
139    }
140
141    #[test]
142    pub fn heavy_test_fec_completeness() {
143        let mut rng = o1_utils::tests::make_test_rng(None);
144        let domain_size = 1 << 15; // Otherwise we can't do 15-bit lookups.
145
146        let mut constraint_env = ConstraintBuilderEnv::<Fp, LookupTable<Ff1>>::create();
147        constrain_ec_addition::<Fp, Ff1, _>(&mut constraint_env);
148        let constraints = constraint_env.get_constraints();
149
150        let witness_env = build_fec_addition_circuit(&mut rng, domain_size);
151
152        // Fixed tables can be generated inside lookup_tables_data. Runtime should be generated here.
153        let mut lookup_tables_data = BTreeMap::new();
154        for table_id in LookupTable::<Ff1>::all_variants().into_iter() {
155            lookup_tables_data.insert(
156                table_id,
157                vec![table_id
158                    .entries(domain_size as u64)
159                    .into_iter()
160                    .map(|x| vec![x])
161                    .collect()],
162            );
163        }
164        let proof_inputs = witness_env.get_proof_inputs(domain_size, lookup_tables_data);
165
166        crate::test::test_completeness_generic::<
167            FEC_N_COLUMNS,
168            FEC_N_COLUMNS,
169            0,
170            0,
171            LookupTable<Ff1>,
172            _,
173        >(
174            constraints,
175            Box::new([]),
176            proof_inputs,
177            domain_size,
178            &mut rng,
179        );
180    }
181}
kimchi_msm/fec/mod.rs

kimchi_msm/fec/
mod.rs
