kimchi/circuits/lookup/tables/
mod.rs

1use ark_ff::{FftField, One, Zero};
2use poly_commitment::PolyComm;
3use serde::{Deserialize, Serialize};
4
5pub mod range_check;
6pub mod xor;
7
8// If you add new tables, update ../../../../../book/src/kimchi/lookup.md
9// accordingly
10
11//~ spec:startcode
12/// The table ID associated with the XOR lookup table.
13pub const XOR_TABLE_ID: i32 = 0;
14
15/// The range check table ID.
16pub const RANGE_CHECK_TABLE_ID: i32 = 1;
17//~ spec:endcode
18
19/// Enumerates the different 'fixed' lookup tables used by individual gates
20#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
21pub enum GateLookupTable {
22    Xor,
23    RangeCheck,
24}
25
26/// Enumerates the different 'fixed' lookup tables used by individual gates
27#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
28pub struct GateLookupTables {
29    pub xor: bool,
30    pub range_check: bool,
31}
32
33impl core::ops::Index<GateLookupTable> for GateLookupTables {
34    type Output = bool;
35
36    fn index(&self, index: GateLookupTable) -> &Self::Output {
37        match index {
38            GateLookupTable::Xor => &self.xor,
39            GateLookupTable::RangeCheck => &self.range_check,
40        }
41    }
42}
43
44impl core::ops::IndexMut<GateLookupTable> for GateLookupTables {
45    fn index_mut(&mut self, index: GateLookupTable) -> &mut Self::Output {
46        match index {
47            GateLookupTable::Xor => &mut self.xor,
48            GateLookupTable::RangeCheck => &mut self.range_check,
49        }
50    }
51}
52
53impl IntoIterator for GateLookupTables {
54    type Item = GateLookupTable;
55    type IntoIter = std::vec::IntoIter<Self::Item>;
56
57    fn into_iter(self) -> Self::IntoIter {
58        // Destructor pattern to make sure we add new lookup patterns.
59        let GateLookupTables { xor, range_check } = self;
60
61        let mut patterns = Vec::with_capacity(2);
62
63        if xor {
64            patterns.push(GateLookupTable::Xor)
65        }
66        if range_check {
67            patterns.push(GateLookupTable::RangeCheck)
68        }
69        patterns.into_iter()
70    }
71}
72
73/// A table of values that can be used for a lookup, along with the ID for the table.
74#[derive(Debug, Clone)]
75pub struct LookupTable<F> {
76    pub id: i32,
77    pub data: Vec<Vec<F>>,
78}
79
80impl<F> LookupTable<F>
81where
82    F: FftField,
83{
84    /// Return true if the table has an entry (row) containing all zeros.
85    pub fn has_zero_entry(&self) -> bool {
86        // reminder: a table is written as a list of columns,
87        // not as a list of row entries.
88        for row in 0..self.len() {
89            if self.data.iter().all(|col| col[row].is_zero()) {
90                return true;
91            }
92        }
93        false
94    }
95
96    /// Returns the number of columns, i.e. the width of the table.
97    /// It is less error prone to introduce this method than using the public
98    /// field data.
99    pub fn width(&self) -> usize {
100        self.data.len()
101    }
102
103    /// Returns the length of the table.
104    pub fn len(&self) -> usize {
105        self.data[0].len()
106    }
107
108    /// Returns `true` if the lookup table is empty, `false` otherwise.
109    pub fn is_empty(&self) -> bool {
110        self.data.is_empty()
111    }
112}
113
114/// Returns the lookup table associated to a [`GateLookupTable`].
115pub fn get_table<F: FftField>(table_name: GateLookupTable) -> LookupTable<F> {
116    match table_name {
117        GateLookupTable::Xor => xor::xor_table(),
118        GateLookupTable::RangeCheck => range_check::range_check_table(),
119    }
120}
121
122impl GateLookupTable {
123    /// Returns the lookup table associated to a [`GateLookupTable`].
124    pub fn table_size(&self) -> usize {
125        match self {
126            GateLookupTable::Xor => xor::TABLE_SIZE,
127            GateLookupTable::RangeCheck => range_check::TABLE_SIZE,
128        }
129    }
130}
131
132/// Let's say we want to do a lookup in a "vector-valued" table `T: Vec<[F; n]>` (here I
133/// am using `[F; n]` to model a vector of length `n`).
134///
135/// For `i < n`, define `T_i := T.map(|t| t[i]).collect()`. In other words, the table
136/// obtained by taking the `ith` entry of each element of `T`.
137///
138/// In the lookup argument, we perform lookups in `T` by sampling a random challenge
139/// `joint_combiner`, and computing a "combined" lookup table `sum_{i < n} joint_combiner^i T_i`.
140///
141/// To check a vector's membership in this lookup table, we combine the values in that vector
142/// analogously using `joint_combiner`.
143///
144/// This function computes that combined value.
145pub fn combine_table_entry<'a, F, I>(
146    joint_combiner: &F,
147    table_id_combiner: &F,
148    v: I,
149    // TODO: this should be an option?
150    table_id: &F,
151) -> F
152where
153    F: 'a, // Any references in `F` must have a lifetime longer than `'a`.
154    F: Zero + One + Clone,
155    I: DoubleEndedIterator<Item = &'a F>,
156{
157    v.rev()
158        .fold(F::zero(), |acc, x| joint_combiner.clone() * acc + x.clone())
159        + table_id_combiner.clone() * table_id.clone()
160}
161
162/// Same as [`combine_table_entry`], but for an entire table.
163/// The function will panic if given an empty table (0 columns).
164///
165/// # Panics
166///
167/// Will panic if `columns` is empty.
168pub fn combine_table<G>(
169    columns: &[&PolyComm<G>],
170    column_combiner: G::ScalarField,
171    table_id_combiner: G::ScalarField,
172    table_id_vector: Option<&PolyComm<G>>,
173    runtime_vector: Option<&PolyComm<G>>,
174) -> PolyComm<G>
175where
176    G: poly_commitment::commitment::CommitmentCurve,
177{
178    assert!(!columns.is_empty());
179
180    // combine the columns
181    let mut j = G::ScalarField::one();
182    let mut scalars = vec![j];
183    let mut commitments = vec![columns[0]];
184    for comm in columns.iter().skip(1) {
185        j *= column_combiner;
186        scalars.push(j);
187        commitments.push(comm);
188    }
189
190    // combine the table id
191    if let Some(table_id) = table_id_vector {
192        scalars.push(table_id_combiner);
193        commitments.push(table_id);
194    }
195
196    // combine the runtime vector
197    if let Some(runtime) = runtime_vector {
198        scalars.push(column_combiner); // 2nd column idx is j^1
199        commitments.push(runtime);
200    }
201
202    PolyComm::multi_scalar_mul(&commitments, &scalars)
203}
204
205#[cfg(feature = "ocaml_types")]
206pub mod caml {
207    use ark_ff::PrimeField;
208    use ocaml;
209    use ocaml_gen;
210
211    use super::LookupTable;
212
213    //
214    // CamlLookupTable<CamlF>
215    //
216
217    #[derive(ocaml::IntoValue, ocaml::FromValue, ocaml_gen::Struct)]
218    pub struct CamlLookupTable<CamlF> {
219        pub id: i32,
220        pub data: Vec<Vec<CamlF>>,
221    }
222
223    impl<F, CamlF> From<CamlLookupTable<CamlF>> for LookupTable<F>
224    where
225        F: PrimeField,
226        CamlF: Into<F>,
227    {
228        fn from(caml_lt: CamlLookupTable<CamlF>) -> Self {
229            Self {
230                id: caml_lt.id,
231                data: caml_lt
232                    .data
233                    .into_iter()
234                    .map(|t| t.into_iter().map(Into::into).collect())
235                    .collect(),
236            }
237        }
238    }
239
240    impl<F, CamlF> From<LookupTable<F>> for CamlLookupTable<CamlF>
241    where
242        F: PrimeField,
243        CamlF: From<F>,
244    {
245        fn from(lt: LookupTable<F>) -> Self {
246            Self {
247                id: lt.id,
248                data: lt
249                    .data
250                    .into_iter()
251                    .map(|t| t.into_iter().map(Into::into).collect())
252                    .collect(),
253            }
254        }
255    }
256}
kimchi/circuits/lookup/tables/mod.rs

kimchi/circuits/lookup/tables/
mod.rs
