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

kimchi/circuits/lookup/tables/
mod.rs
