kimchi/circuits/lookup/tables/
mod.rs

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

kimchi/circuits/lookup/tables/
mod.rs
