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, iter};
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            let r: Vec<F> = iter::repeat(dummy_value)
148                .take((domain.d1.size - table_size) as usize)
149                .collect();
150            r
151        };
152        let t_evals = {
153            let mut table = Vec::with_capacity(domain.d1.size as usize);
154            table.extend(t.iter().map(|v| Lookup {
155                table_id: LookupTableIDs::Custom(table_id),
156                numerator: -F::one(),
157                value: vec![F::from(*v)],
158            }));
159            table.extend(
160                repeated_dummy_value
161                    .iter()
162                    .map(|v| Lookup {
163                        table_id: LookupTableIDs::Custom(table_id),
164                        numerator: -F::one(),
165                        value: vec![*v],
166                    })
167                    .collect::<Vec<Lookup<F>>>(),
168            );
169            table
170        };
171        let f_evals: Vec<Lookup<F>> = {
172            let mut table = Vec::with_capacity(domain.d1.size as usize);
173            table.extend(f.iter().map(|v| Lookup {
174                table_id: LookupTableIDs::Custom(table_id),
175                numerator: F::one(),
176                value: vec![F::from(*v)],
177            }));
178            table.extend(
179                repeated_dummy_value
180                    .iter()
181                    .map(|v| Lookup {
182                        table_id: LookupTableIDs::Custom(table_id),
183                        numerator: F::one(),
184                        value: vec![*v],
185                    })
186                    .collect::<Vec<Lookup<F>>>(),
187            );
188            table
189        };
190        let m = (0..domain.d1.size).map(|_| F::one()).collect();
191        (
192            LookupTableIDs::Custom(table_id),
193            LookupWitness {
194                f: vec![f_evals, t_evals],
195                m: vec![m],
196            },
197        )
198    }
199}
kimchi_msm/lookups.rs

kimchi_msm/
lookups.rs
