zinc_piop/lookup/
structs.rs

1//! Data structures for the lookup protocol.
2//!
3//! Proof types, prover/verifier intermediates, instance types, and error
4//! definitions live here. Specification types (`LookupTableType`,
5//! `LookupColumnSpec`) live in `zinc-uair` and are re-exported from the
6//! parent module.
7
8use itertools::Itertools;
9use std::collections::BTreeMap;
10use thiserror::Error;
11use zinc_uair::LookupTableType;
12
13// ---------------------------------------------------------------------------
14// Per-group proof (BatchedDecompLogup)
15// ---------------------------------------------------------------------------
16
17/// Proof for one lookup group (columns sharing the same table type).
18///
19/// Does **not** contain a sumcheck proof — the sumcheck is shared via
20/// the protocol-level multi-degree sumcheck. This struct
21/// carries only the auxiliary vectors the verifier needs to reconstruct
22/// evaluations at the shared point.
23///
24/// Chunk vectors are **not** included — the verifier reconstructs them
25/// from the inverse witnesses: `c_k[j] = β − 1/u_k[j]`. Soundness
26/// follows from the PCS commitment binding the parent column.
27#[derive(Clone, Debug, PartialEq, Eq)]
28pub struct BatchedDecompLogupProof<F> {
29    /// Per-witness aggregated multiplicity vectors:
30    /// `aggregated_multiplicities[l][j] = Σ_k m_k^(l)[j]`.
31    pub aggregated_multiplicities: Vec<Vec<F>>,
32    /// Per-witness per-chunk inverse witness vectors:
33    /// `chunk_inverse_witnesses[l][k][i] = 1 / (β − chunk[l][k][i])`.
34    pub chunk_inverse_witnesses: Vec<Vec<Vec<F>>>,
35    /// Shared inverse table vector: `inverse_table[j] = 1 / (β − T[j])`.
36    pub inverse_table: Vec<F>,
37}
38
39impl<F> BatchedDecompLogupProof<F> {
40    /// Maps every field element through `f`, preserving structure — used to
41    /// lift elements into wire integers and to project wire integers back
42    /// into elements at the (de)serialization boundary.
43    pub fn try_map<T, E>(
44        &self,
45        f: impl FnMut(&F) -> Result<T, E> + Copy,
46    ) -> Result<BatchedDecompLogupProof<T>, E> {
47        Ok(BatchedDecompLogupProof {
48            aggregated_multiplicities: self
49                .aggregated_multiplicities
50                .iter()
51                .map(|v| v.iter().map(f).try_collect())
52                .try_collect()?,
53            chunk_inverse_witnesses: self
54                .chunk_inverse_witnesses
55                .iter()
56                .map(|vv| {
57                    vv.iter()
58                        .map(|v| v.iter().map(f).try_collect())
59                        .try_collect()
60                })
61                .try_collect()?,
62            inverse_table: self.inverse_table.iter().map(f).try_collect()?,
63        })
64    }
65}
66
67// ---------------------------------------------------------------------------
68// Per-group metadata (carried in the proof for the verifier)
69// ---------------------------------------------------------------------------
70
71/// Describes how a lookup witness column was derived from the trace.
72///
73/// Carried in [`LookupGroupMeta`] so the verifier can reconstruct the
74/// parent evaluation without re-receiving the lookup specs.
75#[derive(Clone, Debug, PartialEq, Eq)]
76pub enum LookupWitnessSource {
77    /// Standard column lookup: parent eval = `up_evals[column_index]`.
78    Column {
79        /// Original trace column index.
80        column_index: usize,
81    },
82    /// Affine-combination lookup: parent eval = `Σ coeff·up_evals[col] +
83    /// offset`. Currently only needed for BitPoly
84    Affine {
85        /// `(column_index, coefficient)` pairs.
86        terms: Vec<(usize, i64)>,
87        /// Constant bit-polynomial offset encoded as a u32 bit pattern.
88        constant_offset_bits: u32,
89    },
90}
91
92/// Per-group metadata stored in the proof so the verifier can reconstruct
93/// tables and column layout without being passed the original lookup specs.
94#[derive(Clone, Debug, PartialEq, Eq)]
95pub struct LookupGroupMeta {
96    /// Table type for this group (determines subtable generation).
97    pub table_type: LookupTableType,
98    /// Number of witness columns batched into this group (L).
99    pub num_columns: usize,
100    /// Number of rows in each witness vector (trace length).
101    pub witness_len: usize,
102    /// Per-witness source descriptors.
103    pub witness_sources: Vec<LookupWitnessSource>,
104}
105
106// ---------------------------------------------------------------------------
107// Complete lookup proof
108// ---------------------------------------------------------------------------
109
110/// Top-level proof: one [`BatchedDecompLogupProof`] per lookup group
111/// (groups formed by batching columns with the same [`LookupTableType`]).
112/// Carries [`LookupGroupMeta`] per group so the verifier needs no
113/// external specs.
114#[derive(Clone, Default, Debug, PartialEq, Eq)]
115pub struct BatchedLookupProof<F> {
116    /// Per-group proofs, in group order.
117    pub group_proofs: Vec<BatchedDecompLogupProof<F>>,
118    /// Per-group metadata needed by the verifier.
119    pub group_meta: Vec<LookupGroupMeta>,
120}
121
122impl<F> BatchedLookupProof<F> {
123    /// Maps every field element through `f`, preserving structure — used to
124    /// lift elements into wire integers and to project wire integers back
125    /// into elements at the (de)serialization boundary.
126    pub fn try_map<T, E>(
127        &self,
128        f: impl FnMut(&F) -> Result<T, E> + Copy,
129    ) -> Result<BatchedLookupProof<T>, E> {
130        Ok(BatchedLookupProof {
131            group_proofs: self
132                .group_proofs
133                .iter()
134                .map(|p| p.try_map(f))
135                .try_collect()?,
136            group_meta: self.group_meta.clone(),
137        })
138    }
139}
140
141// ---------------------------------------------------------------------------
142// Grouping utility
143// ---------------------------------------------------------------------------
144
145/// A group of columns that all look up into the same decomposed table.
146///
147/// Produced by [`group_lookup_specs`] and consumed by the pipeline.
148#[derive(Debug)]
149pub struct LookupGroup {
150    /// The shared table type.
151    pub table_type: LookupTableType,
152    /// Indices of all columns in this group.
153    pub column_indices: Vec<usize>,
154}
155
156/// Groups a list of [`LookupColumnSpec`](zinc_uair::LookupColumnSpec)s
157/// by their table type.
158///
159/// Columns with the same `LookupTableType` are batched into a single
160/// `BatchedDecompLogupProtocol` instance.
161pub fn group_lookup_specs(specs: &[zinc_uair::LookupColumnSpec]) -> Vec<LookupGroup> {
162    let mut map: BTreeMap<LookupTableType, Vec<usize>> = BTreeMap::new();
163    for spec in specs {
164        map.entry(spec.table_type.clone())
165            .or_default()
166            .push(spec.column_index);
167    }
168    map.into_iter()
169        .map(|(table_type, column_indices)| LookupGroup {
170            table_type,
171            column_indices,
172        })
173        .collect()
174}
175
176// ---------------------------------------------------------------------------
177// Errors
178// ---------------------------------------------------------------------------
179
180/// Errors from the lookup protocol.
181#[derive(Debug, Error)]
182pub enum LookupError {
183    #[error("lookup not implemented")]
184    NotImplemented,
185
186    #[error("witness entry not found in lookup table")]
187    WitnessNotInTable,
188
189    #[error("table inverse vector is incorrect at index {index}")]
190    TableInverseIncorrect { index: usize },
191
192    #[error("decomposition consistency check failed")]
193    DecompositionInconsistent,
194
195    #[error("multiplicity sum mismatch: expected {expected}, got {got}")]
196    MultiplicitySumMismatch { expected: u64, got: u64 },
197
198    #[error("final evaluation check failed")]
199    FinalEvaluationMismatch,
200}
zinc_piop/lookup/structs.rs

zinc_piop/lookup/
structs.rs
