kimchi_msm/
proof.rs

1use crate::{
2    logup::{LookupProof, LookupTableID},
3    lookups::{LookupTableIDs, LookupWitness},
4    witness::Witness,
5    LogupWitness, DOMAIN_SIZE,
6};
7use ark_ff::PrimeField;
8use kimchi::{
9    circuits::{
10        domains::EvaluationDomains,
11        expr::{ColumnEvaluations, ExprError},
12    },
13    curve::KimchiCurve,
14    proof::PointEvaluations,
15};
16use poly_commitment::{commitment::PolyComm, OpenProof};
17use rand::thread_rng;
18use std::collections::BTreeMap;
19
20#[derive(Debug, Clone, PartialEq, Eq)]
21pub struct ProofInputs<const N_WIT: usize, F: PrimeField, ID: LookupTableID> {
22    /// Actual values w_i of the witness columns. "Evaluations" as in
23    /// evaluations of polynomial P_w that interpolates w_i.
24    pub evaluations: Witness<N_WIT, Vec<F>>,
25    pub logups: BTreeMap<ID, LogupWitness<F, ID>>,
26}
27
28impl<const N_WIT: usize, F: PrimeField> ProofInputs<N_WIT, F, LookupTableIDs> {
29    // This should be used only for testing purposes.
30    // It is not only in the test API because it is used at the moment in the
31    // main.rs. It should be moved to the test API when main.rs is replaced with
32    // real production code.
33    pub fn random(domain: EvaluationDomains<F>) -> Self {
34        let mut rng = thread_rng();
35        let cols: Box<[Vec<F>; N_WIT]> = Box::new(std::array::from_fn(|_| {
36            (0..domain.d1.size as usize)
37                .map(|_| F::rand(&mut rng))
38                .collect::<Vec<_>>()
39        }));
40        let logups = {
41            let (table_id, item) = LookupWitness::<F>::random(domain);
42            BTreeMap::from([(table_id, item)])
43        };
44        ProofInputs {
45            evaluations: Witness { cols },
46            logups,
47        }
48    }
49}
50
51impl<const N_WIT: usize, F: PrimeField, ID: LookupTableID> Default for ProofInputs<N_WIT, F, ID> {
52    /// Creates a default proof instance. Note that such an empty "zero" instance will not satisfy any constraint.
53    /// E.g. some constraints that have constants inside of them (A - const = 0) cannot be satisfied by it.
54    fn default() -> Self {
55        ProofInputs {
56            evaluations: Witness {
57                cols: Box::new(std::array::from_fn(|_| {
58                    (0..DOMAIN_SIZE).map(|_| F::zero()).collect()
59                })),
60            },
61            logups: Default::default(),
62        }
63    }
64}
65
66#[derive(Debug, Clone)]
67// TODO Should public input and fixed selectors evaluations be here?
68pub struct ProofEvaluations<
69    const N_WIT: usize,
70    const N_REL: usize,
71    const N_DSEL: usize,
72    const N_FSEL: usize,
73    F,
74    ID: LookupTableID,
75> {
76    /// Witness evaluations, including public inputs
77    pub(crate) witness_evals: Witness<N_WIT, PointEvaluations<F>>,
78    /// Evaluations of fixed selectors.
79    pub(crate) fixed_selectors_evals: Box<[PointEvaluations<F>; N_FSEL]>,
80    /// Logup argument evaluations
81    pub(crate) logup_evals: Option<LookupProof<PointEvaluations<F>, ID>>,
82    /// Evaluation of Z_H(ζ) (t_0(X) + ζ^n t_1(X) + ...) at ζω.
83    pub(crate) ft_eval1: F,
84}
85
86/// The trait ColumnEvaluations is used by the verifier.
87/// It will return the evaluation of the corresponding column at the
88/// evaluation points coined by the verifier during the protocol.
89impl<
90        const N_WIT: usize,
91        const N_REL: usize,
92        const N_DSEL: usize,
93        const N_FSEL: usize,
94        F: Clone,
95        ID: LookupTableID,
96    > ColumnEvaluations<F> for ProofEvaluations<N_WIT, N_REL, N_DSEL, N_FSEL, F, ID>
97{
98    type Column = crate::columns::Column<usize>;
99
100    fn evaluate(&self, col: Self::Column) -> Result<PointEvaluations<F>, ExprError<Self::Column>> {
101        // TODO: substitute when non-literal generic constants are available
102        assert!(N_WIT == N_REL + N_DSEL);
103        let res = match col {
104            Self::Column::Relation(i) => {
105                assert!(i < N_REL, "Index out of bounds");
106                self.witness_evals[i].clone()
107            }
108            Self::Column::DynamicSelector(i) => {
109                assert!(i < N_DSEL, "Index out of bounds");
110                self.witness_evals[N_REL + i].clone()
111            }
112            Self::Column::FixedSelector(i) => {
113                assert!(i < N_FSEL, "Index out of bounds");
114                self.fixed_selectors_evals[i].clone()
115            }
116            Self::Column::LookupPartialSum((table_id, idx)) => {
117                if let Some(ref lookup) = self.logup_evals {
118                    lookup.h[&ID::from_u32(table_id)][idx].clone()
119                } else {
120                    panic!("No lookup provided")
121                }
122            }
123            Self::Column::LookupAggregation => {
124                if let Some(ref lookup) = self.logup_evals {
125                    lookup.sum.clone()
126                } else {
127                    panic!("No lookup provided")
128                }
129            }
130            Self::Column::LookupMultiplicity((table_id, idx)) => {
131                if let Some(ref lookup) = self.logup_evals {
132                    lookup.m[&ID::from_u32(table_id)][idx].clone()
133                } else {
134                    panic!("No lookup provided")
135                }
136            }
137            Self::Column::LookupFixedTable(table_id) => {
138                if let Some(ref lookup) = self.logup_evals {
139                    lookup.fixed_tables[&ID::from_u32(table_id)].clone()
140                } else {
141                    panic!("No lookup provided")
142                }
143            }
144        };
145        Ok(res)
146    }
147}
148
149#[derive(Debug, Clone)]
150pub struct ProofCommitments<const N_WIT: usize, G: KimchiCurve, ID: LookupTableID> {
151    /// Commitments to the N columns of the circuits, also called the 'witnesses'.
152    /// If some columns are considered as public inputs, it is counted in the witness.
153    pub(crate) witness_comms: Witness<N_WIT, PolyComm<G>>,
154    /// Commitments to the polynomials used by the lookup argument, coined "logup".
155    /// The values contains the chunked polynomials.
156    pub(crate) logup_comms: Option<LookupProof<PolyComm<G>, ID>>,
157    /// Commitments to the quotient polynomial.
158    /// The value contains the chunked polynomials.
159    pub(crate) t_comm: PolyComm<G>,
160}
161
162#[derive(Debug, Clone)]
163pub struct Proof<
164    const N_WIT: usize,
165    const N_REL: usize,
166    const N_DSEL: usize,
167    const N_FSEL: usize,
168    G: KimchiCurve,
169    OpeningProof: OpenProof<G>,
170    ID: LookupTableID,
171> {
172    pub(crate) proof_comms: ProofCommitments<N_WIT, G, ID>,
173    pub(crate) proof_evals: ProofEvaluations<N_WIT, N_REL, N_DSEL, N_FSEL, G::ScalarField, ID>,
174    pub(crate) opening_proof: OpeningProof,
175}
kimchi_msm/proof.rs

kimchi_msm/
proof.rs
