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 std::collections::BTreeMap;
9use thiserror::Error;
10use zinc_uair::LookupTableType;
11
12// ---------------------------------------------------------------------------
13// Per-group proof (BatchedDecompLogup)
14// ---------------------------------------------------------------------------
15
16/// Proof for one lookup group (columns sharing the same table type).
17///
18/// Does **not** contain a sumcheck proof — the sumcheck is shared via
19/// the protocol-level multi-degree sumcheck. This struct
20/// carries only the auxiliary vectors the verifier needs to reconstruct
21/// evaluations at the shared point.
22///
23/// Chunk vectors are **not** included — the verifier reconstructs them
24/// from the inverse witnesses: `c_k[j] = β − 1/u_k[j]`. Soundness
25/// follows from the PCS commitment binding the parent column.
26#[derive(Clone, Debug, PartialEq, Eq)]
27pub struct BatchedDecompLogupProof<F> {
28    /// Per-witness aggregated multiplicity vectors:
29    /// `aggregated_multiplicities[l][j] = Σ_k m_k^(l)[j]`.
30    pub aggregated_multiplicities: Vec<Vec<F>>,
31    /// Per-witness per-chunk inverse witness vectors:
32    /// `chunk_inverse_witnesses[l][k][i] = 1 / (β − chunk[l][k][i])`.
33    pub chunk_inverse_witnesses: Vec<Vec<Vec<F>>>,
34    /// Shared inverse table vector: `inverse_table[j] = 1 / (β − T[j])`.
35    pub inverse_table: Vec<F>,
36}
37
38// ---------------------------------------------------------------------------
39// Per-group metadata (carried in the proof for the verifier)
40// ---------------------------------------------------------------------------
41
42/// Describes how a lookup witness column was derived from the trace.
43///
44/// Carried in [`LookupGroupMeta`] so the verifier can reconstruct the
45/// parent evaluation without re-receiving the lookup specs.
46#[derive(Clone, Debug, PartialEq, Eq)]
47pub enum LookupWitnessSource {
48    /// Standard column lookup: parent eval = `up_evals[column_index]`.
49    Column {
50        /// Original trace column index.
51        column_index: usize,
52    },
53    /// Affine-combination lookup: parent eval = `Σ coeff·up_evals[col] +
54    /// offset`. Currently only needed for BitPoly
55    Affine {
56        /// `(column_index, coefficient)` pairs.
57        terms: Vec<(usize, i64)>,
58        /// Constant bit-polynomial offset encoded as a u32 bit pattern.
59        constant_offset_bits: u32,
60    },
61}
62
63/// Per-group metadata stored in the proof so the verifier can reconstruct
64/// tables and column layout without being passed the original lookup specs.
65#[derive(Clone, Debug, PartialEq, Eq)]
66pub struct LookupGroupMeta {
67    /// Table type for this group (determines subtable generation).
68    pub table_type: LookupTableType,
69    /// Number of witness columns batched into this group (L).
70    pub num_columns: usize,
71    /// Number of rows in each witness vector (trace length).
72    pub witness_len: usize,
73    /// Per-witness source descriptors.
74    pub witness_sources: Vec<LookupWitnessSource>,
75}
76
77// ---------------------------------------------------------------------------
78// Complete lookup proof
79// ---------------------------------------------------------------------------
80
81/// Top-level proof: one [`BatchedDecompLogupProof`] per lookup group
82/// (groups formed by batching columns with the same [`LookupTableType`]).
83/// Carries [`LookupGroupMeta`] per group so the verifier needs no
84/// external specs.
85#[derive(Clone, Default, Debug, PartialEq, Eq)]
86pub struct BatchedLookupProof<F> {
87    /// Per-group proofs, in group order.
88    pub group_proofs: Vec<BatchedDecompLogupProof<F>>,
89    /// Per-group metadata needed by the verifier.
90    pub group_meta: Vec<LookupGroupMeta>,
91}
92
93// ---------------------------------------------------------------------------
94// Grouping utility
95// ---------------------------------------------------------------------------
96
97/// A group of columns that all look up into the same decomposed table.
98///
99/// Produced by [`group_lookup_specs`] and consumed by the pipeline.
100#[derive(Debug)]
101pub struct LookupGroup {
102    /// The shared table type.
103    pub table_type: LookupTableType,
104    /// Indices of all columns in this group.
105    pub column_indices: Vec<usize>,
106}
107
108/// Groups a list of [`LookupColumnSpec`](zinc_uair::LookupColumnSpec)s
109/// by their table type.
110///
111/// Columns with the same `LookupTableType` are batched into a single
112/// `BatchedDecompLogupProtocol` instance.
113pub fn group_lookup_specs(specs: &[zinc_uair::LookupColumnSpec]) -> Vec<LookupGroup> {
114    let mut map: BTreeMap<LookupTableType, Vec<usize>> = BTreeMap::new();
115    for spec in specs {
116        map.entry(spec.table_type.clone())
117            .or_default()
118            .push(spec.column_index);
119    }
120    map.into_iter()
121        .map(|(table_type, column_indices)| LookupGroup {
122            table_type,
123            column_indices,
124        })
125        .collect()
126}
127
128// ---------------------------------------------------------------------------
129// Errors
130// ---------------------------------------------------------------------------
131
132/// Errors from the lookup protocol.
133#[derive(Debug, Error)]
134pub enum LookupError {
135    #[error("lookup not implemented")]
136    NotImplemented,
137
138    #[error("witness entry not found in lookup table")]
139    WitnessNotInTable,
140
141    #[error("table inverse vector is incorrect at index {index}")]
142    TableInverseIncorrect { index: usize },
143
144    #[error("decomposition consistency check failed")]
145    DecompositionInconsistent,
146
147    #[error("multiplicity sum mismatch: expected {expected}, got {got}")]
148    MultiplicitySumMismatch { expected: u64, got: u64 },
149
150    #[error("final evaluation check failed")]
151    FinalEvaluationMismatch,
152}
zinc_piop/lookup/structs.rs

zinc_piop/lookup/
structs.rs
