kimchi_msm/
lookups.rs

1//! Instantiate the Logup protocol for the MSM project.
2
3use crate::logup::{Logup, LogupWitness, LookupTableID};
4use ark_ff::{FftField, PrimeField};
5use kimchi::circuits::domains::EvaluationDomains;
6use rand::{seq::SliceRandom, thread_rng, Rng};
7use std::cmp::Ord;
8
9/// Dummy lookup table. For the cases when you don't need one -- a single dummy element 0.
10#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq, Ord, PartialOrd)]
11pub enum DummyLookupTable {
12    DummyLookupTable,
13}
14
15impl LookupTableID for DummyLookupTable {
16    fn to_u32(&self) -> u32 {
17        1
18    }
19
20    fn from_u32(id: u32) -> Self {
21        match id {
22            1 => DummyLookupTable::DummyLookupTable,
23            _ => panic!("Dummy lookup table has only index 1"),
24        }
25    }
26
27    fn length(&self) -> usize {
28        1
29    }
30
31    /// All tables are fixed tables.
32    fn is_fixed(&self) -> bool {
33        true
34    }
35
36    fn runtime_create_column(&self) -> bool {
37        panic!("No runtime tables specified");
38    }
39
40    fn ix_by_value<F: PrimeField>(&self, value: &[F]) -> Option<usize> {
41        if value[0] == F::zero() {
42            Some(0)
43        } else {
44            panic!("Invalid value for DummyLookupTable")
45        }
46    }
47
48    fn all_variants() -> Vec<Self> {
49        vec![DummyLookupTable::DummyLookupTable]
50    }
51}
52
53impl DummyLookupTable {
54    /// Provides a full list of entries for the given table.
55    pub fn entries<F: PrimeField>(&self, domain_d1_size: u64) -> Vec<F> {
56        // All zeroes
57        (0..domain_d1_size).map(|_| F::zero()).collect()
58    }
59}
60
61/// Lookup tables used in the MSM project
62// TODO: Add more built-in lookup tables
63#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq, Ord, PartialOrd)]
64pub enum LookupTableIDs {
65    RangeCheck16,
66    /// Custom lookup table
67    /// The index of the table is used as the ID, padded with the number of
68    /// built-in tables.
69    Custom(u32),
70}
71
72impl LookupTableID for LookupTableIDs {
73    fn to_u32(&self) -> u32 {
74        match self {
75            LookupTableIDs::RangeCheck16 => 1_u32,
76            LookupTableIDs::Custom(id) => id + 1,
77        }
78    }
79
80    fn from_u32(id: u32) -> Self {
81        match id {
82            1 => LookupTableIDs::RangeCheck16,
83            _ => LookupTableIDs::Custom(id - 1),
84        }
85    }
86
87    fn length(&self) -> usize {
88        match self {
89            LookupTableIDs::RangeCheck16 => 1 << 16,
90            LookupTableIDs::Custom(_) => todo!(),
91        }
92    }
93
94    /// All tables are fixed tables.
95    fn is_fixed(&self) -> bool {
96        true
97    }
98
99    fn runtime_create_column(&self) -> bool {
100        panic!("No runtime tables specified");
101    }
102
103    fn ix_by_value<F: PrimeField>(&self, _value: &[F]) -> Option<usize> {
104        todo!()
105    }
106
107    fn all_variants() -> Vec<Self> {
108        // TODO in the future this must depend on some associated type
109        // that parameterises the lookup table.
110        vec![Self::RangeCheck16, Self::Custom(0)]
111    }
112}
113
114/// Additive lookups used in the MSM project based on Logup
115pub type Lookup<F> = Logup<F, LookupTableIDs>;
116
117/// Represents a witness of one instance of the lookup argument of the MSM project
118pub type LookupWitness<F> = LogupWitness<F, LookupTableIDs>;
119
120// This should be used only for testing purposes.
121// It is not only in the test API because it is used at the moment in the
122// main.rs. It should be moved to the test API when main.rs is replaced with
123// real production code.
124impl<F: FftField> LookupWitness<F> {
125    /// Generate a random number of correct lookups in the table RangeCheck16
126    pub fn random(domain: EvaluationDomains<F>) -> (LookupTableIDs, Self) {
127        let mut rng = thread_rng();
128        // TODO: generate more random f
129        let table_size: u64 = rng.gen_range(1..domain.d1.size);
130        let table_id = rng.gen_range(1..1000);
131        // Build a table of value we can look up
132        let t: Vec<u64> = {
133            // Generate distinct values to avoid to have to handle the
134            // normalized multiplicity polynomial
135            let mut n: Vec<u64> = (1..(table_size * 100)).collect();
136            n.shuffle(&mut rng);
137            n[0..table_size as usize].to_vec()
138        };
139        // permutation argument
140        let f = {
141            let mut f = t.clone();
142            f.shuffle(&mut rng);
143            f
144        };
145        let dummy_value = F::rand(&mut rng);
146        let repeated_dummy_value: Vec<F> =
147            o1_utils::repeat_n(dummy_value, (domain.d1.size - table_size) as usize).collect();
148        let t_evals = {
149            let mut table = Vec::with_capacity(domain.d1.size as usize);
150            table.extend(t.iter().map(|v| Lookup {
151                table_id: LookupTableIDs::Custom(table_id),
152                numerator: -F::one(),
153                value: vec![F::from(*v)],
154            }));
155            table.extend(
156                repeated_dummy_value
157                    .iter()
158                    .map(|v| Lookup {
159                        table_id: LookupTableIDs::Custom(table_id),
160                        numerator: -F::one(),
161                        value: vec![*v],
162                    })
163                    .collect::<Vec<Lookup<F>>>(),
164            );
165            table
166        };
167        let f_evals: Vec<Lookup<F>> = {
168            let mut table = Vec::with_capacity(domain.d1.size as usize);
169            table.extend(f.iter().map(|v| Lookup {
170                table_id: LookupTableIDs::Custom(table_id),
171                numerator: F::one(),
172                value: vec![F::from(*v)],
173            }));
174            table.extend(
175                repeated_dummy_value
176                    .iter()
177                    .map(|v| Lookup {
178                        table_id: LookupTableIDs::Custom(table_id),
179                        numerator: F::one(),
180                        value: vec![*v],
181                    })
182                    .collect::<Vec<Lookup<F>>>(),
183            );
184            table
185        };
186        let m = (0..domain.d1.size).map(|_| F::one()).collect();
187        (
188            LookupTableIDs::Custom(table_id),
189            LookupWitness {
190                f: vec![f_evals, t_evals],
191                m: vec![m],
192            },
193        )
194    }
195}
kimchi_msm/lookups.rs

kimchi_msm/
lookups.rs
