kimchi_msm/serialization/
mod.rs

1pub mod column;
2pub mod interpreter;
3pub mod lookups;
4
5/// The number of intermediate limbs of 4 bits required for the circuit
6pub const N_INTERMEDIATE_LIMBS: usize = 20;
7
8#[cfg(test)]
9mod tests {
10    use ark_ff::UniformRand;
11    use std::collections::BTreeMap;
12
13    use crate::{
14        circuit_design::{constraints::ConstraintBuilderEnv, witness::WitnessBuilderEnv},
15        columns::ColumnIndexer,
16        logup::LookupTableID,
17        serialization::{
18            column::{SerializationColumn, N_COL_SER, N_FSEL_SER},
19            interpreter::{
20                build_selectors, constrain_multiplication, deserialize_field_element,
21                limb_decompose_ff, serialization_circuit,
22            },
23            lookups::LookupTable,
24        },
25        Ff1, Fp,
26    };
27
28    type SerializationWitnessBuilderEnv = WitnessBuilderEnv<
29        Fp,
30        SerializationColumn,
31        { <SerializationColumn as ColumnIndexer<usize>>::N_COL - N_FSEL_SER },
32        { <SerializationColumn as ColumnIndexer<usize>>::N_COL - N_FSEL_SER },
33        0,
34        N_FSEL_SER,
35        LookupTable<Ff1>,
36    >;
37
38    #[test]
39    fn heavy_test_completeness() {
40        let mut rng = o1_utils::tests::make_test_rng(None);
41        // Must be at least 1 << 15 to support rangecheck15
42        let domain_size: usize = 1 << 15;
43
44        let mut witness_env = SerializationWitnessBuilderEnv::create();
45
46        let fixed_selectors = build_selectors(domain_size);
47        witness_env.set_fixed_selectors(fixed_selectors.to_vec());
48
49        let mut field_elements = vec![];
50
51        // FIXME: we do use always the same values here, because we have a
52        // constant check (X - c), different for each row. And there is no
53        // constant support/public input yet in the quotient polynomial.
54        let input_chal: Ff1 = <Ff1 as UniformRand>::rand(&mut rng);
55        let [input1, input2, input3]: [Fp; 3] = limb_decompose_ff::<Fp, Ff1, 88, 3>(&input_chal);
56        for _ in 0..domain_size {
57            field_elements.push([input1, input2, input3])
58        }
59
60        let constraints = {
61            let mut constraints_env = ConstraintBuilderEnv::<Fp, LookupTable<Ff1>>::create();
62            deserialize_field_element(&mut constraints_env, field_elements[0].map(Into::into));
63            constrain_multiplication(&mut constraints_env);
64
65            // Sanity checks.
66            assert!(constraints_env.lookup_reads[&LookupTable::RangeCheck15].len() == (3 * 17 - 1));
67            assert!(constraints_env.lookup_reads[&LookupTable::RangeCheck4].len() == 20);
68            assert!(constraints_env.lookup_reads[&LookupTable::RangeCheck9Abs].len() == 6);
69            assert!(
70                constraints_env.lookup_reads
71                    [&LookupTable::RangeCheckFfHighest(std::marker::PhantomData)]
72                    .len()
73                    == 1
74            );
75
76            constraints_env.get_constraints()
77        };
78
79        serialization_circuit(&mut witness_env, input_chal, field_elements, domain_size);
80
81        let runtime_tables: BTreeMap<_, Vec<Vec<Vec<_>>>> =
82            witness_env.get_runtime_tables(domain_size);
83
84        // TODO remove this clone
85        // Fixed tables can be generated inside lookup_tables_data. Runtime should be generated here.
86        let multiplication_bus: Vec<Vec<Vec<Fp>>> = runtime_tables
87            .get(&LookupTable::MultiplicationBus)
88            .unwrap()
89            .clone();
90
91        //assert!(multiplication_bus.len() == 2);
92
93        let mut lookup_tables_data: BTreeMap<LookupTable<Ff1>, Vec<Vec<Vec<Fp>>>> = BTreeMap::new();
94        for table_id in LookupTable::<Ff1>::all_variants().into_iter() {
95            if table_id.is_fixed() {
96                lookup_tables_data.insert(
97                    table_id,
98                    vec![table_id
99                        .entries(domain_size as u64)
100                        .unwrap()
101                        .into_iter()
102                        .map(|x| vec![x])
103                        .collect()],
104                );
105            }
106        }
107        lookup_tables_data.insert(LookupTable::MultiplicationBus, multiplication_bus);
108        let proof_inputs = witness_env.get_proof_inputs(domain_size, lookup_tables_data);
109
110        crate::test::test_completeness_generic::<
111            { N_COL_SER - N_FSEL_SER },
112            { N_COL_SER - N_FSEL_SER },
113            0,
114            N_FSEL_SER,
115            LookupTable<Ff1>,
116            _,
117        >(
118            constraints,
119            Box::new(fixed_selectors),
120            proof_inputs,
121            domain_size,
122            &mut rng,
123        );
124    }
125}
kimchi_msm/serialization/mod.rs

kimchi_msm/serialization/
mod.rs
