halo2_proofs/plonk/permutation/
verifier.rs

Help
1use ff::Field;
2use std::iter;
3
4use super::super::{circuit::Any, ChallengeBeta, ChallengeGamma, ChallengeX};
5use super::{Argument, VerifyingKey};
6use crate::{
7    arithmetic::{CurveAffine, FieldExt},
8    plonk::{self, Error},
9    poly::{multiopen::VerifierQuery, Rotation},
10    transcript::{EncodedChallenge, TranscriptRead},
11};
12
13pub struct Committed<C: CurveAffine> {
14    permutation_product_commitments: Vec<C>,
15}
16
17pub struct EvaluatedSet<C: CurveAffine> {
18    permutation_product_commitment: C,
19    permutation_product_eval: C::Scalar,
20    permutation_product_next_eval: C::Scalar,
21    permutation_product_last_eval: Option<C::Scalar>,
22}
23
24pub struct CommonEvaluated<C: CurveAffine> {
25    permutation_evals: Vec<C::Scalar>,
26}
27
28pub struct Evaluated<C: CurveAffine> {
29    sets: Vec<EvaluatedSet<C>>,
30}
31
32impl Argument {
33    pub(crate) fn read_product_commitments<
34        C: CurveAffine,
35        E: EncodedChallenge<C>,
36        T: TranscriptRead<C, E>,
37    >(
38        &self,
39        vk: &plonk::VerifyingKey<C>,
40        transcript: &mut T,
41    ) -> Result<Committed<C>, Error> {
42        let chunk_len = vk.cs.degree() - 2;
43
44        let permutation_product_commitments = self
45            .columns
46            .chunks(chunk_len)
47            .map(|_| transcript.read_point())
48            .collect::<Result<Vec<_>, _>>()?;
49
50        Ok(Committed {
51            permutation_product_commitments,
52        })
53    }
54}
55
56impl<C: CurveAffine> VerifyingKey<C> {
57    pub(in crate::plonk) fn evaluate<E: EncodedChallenge<C>, T: TranscriptRead<C, E>>(
58        &self,
59        transcript: &mut T,
60    ) -> Result<CommonEvaluated<C>, Error> {
61        let permutation_evals = self
62            .commitments
63            .iter()
64            .map(|_| transcript.read_scalar())
65            .collect::<Result<Vec<_>, _>>()?;
66
67        Ok(CommonEvaluated { permutation_evals })
68    }
69}
70
71impl<C: CurveAffine> Committed<C> {
72    pub(crate) fn evaluate<E: EncodedChallenge<C>, T: TranscriptRead<C, E>>(
73        self,
74        transcript: &mut T,
75    ) -> Result<Evaluated<C>, Error> {
76        let mut sets = vec![];
77
78        let mut iter = self.permutation_product_commitments.into_iter();
79
80        while let Some(permutation_product_commitment) = iter.next() {
81            let permutation_product_eval = transcript.read_scalar()?;
82            let permutation_product_next_eval = transcript.read_scalar()?;
83            let permutation_product_last_eval = if iter.len() > 0 {
84                Some(transcript.read_scalar()?)
85            } else {
86                None
87            };
88
89            sets.push(EvaluatedSet {
90                permutation_product_commitment,
91                permutation_product_eval,
92                permutation_product_next_eval,
93                permutation_product_last_eval,
94            });
95        }
96
97        Ok(Evaluated { sets })
98    }
99}
100
101impl<C: CurveAffine> Evaluated<C> {
102    pub(in crate::plonk) fn expressions<'a>(
103        &'a self,
104        vk: &'a plonk::VerifyingKey<C>,
105        p: &'a Argument,
106        common: &'a CommonEvaluated<C>,
107        advice_evals: &'a [C::Scalar],
108        fixed_evals: &'a [C::Scalar],
109        instance_evals: &'a [C::Scalar],
110        l_0: C::Scalar,
111        l_last: C::Scalar,
112        l_blind: C::Scalar,
113        beta: ChallengeBeta<C>,
114        gamma: ChallengeGamma<C>,
115        x: ChallengeX<C>,
116    ) -> impl Iterator<Item = C::Scalar> + 'a {
117        let chunk_len = vk.cs.degree() - 2;
118        iter::empty()
119            // Enforce only for the first set.
120            // l_0(X) * (1 - z_0(X)) = 0
121            .chain(
122                self.sets.first().map(|first_set| {
123                    l_0 * &(C::Scalar::one() - &first_set.permutation_product_eval)
124                }),
125            )
126            // Enforce only for the last set.
127            // l_last(X) * (z_l(X)^2 - z_l(X)) = 0
128            .chain(self.sets.last().map(|last_set| {
129                (last_set.permutation_product_eval.square() - &last_set.permutation_product_eval)
130                    * &l_last
131            }))
132            // Except for the first set, enforce.
133            // l_0(X) * (z_i(X) - z_{i-1}(\omega^(last) X)) = 0
134            .chain(
135                self.sets
136                    .iter()
137                    .skip(1)
138                    .zip(self.sets.iter())
139                    .map(|(set, last_set)| {
140                        (
141                            set.permutation_product_eval,
142                            last_set.permutation_product_last_eval.unwrap(),
143                        )
144                    })
145                    .map(move |(set, prev_last)| (set - &prev_last) * &l_0),
146            )
147            // And for all the sets we enforce:
148            // (1 - (l_last(X) + l_blind(X))) * (
149            //   z_i(\omega X) \prod (p(X) + \beta s_i(X) + \gamma)
150            // - z_i(X) \prod (p(X) + \delta^i \beta X + \gamma)
151            // )
152            .chain(
153                self.sets
154                    .iter()
155                    .zip(p.columns.chunks(chunk_len))
156                    .zip(common.permutation_evals.chunks(chunk_len))
157                    .enumerate()
158                    .map(move |(chunk_index, ((set, columns), permutation_evals))| {
159                        let mut left = set.permutation_product_next_eval;
160                        for (eval, permutation_eval) in columns
161                            .iter()
162                            .map(|&column| match column.column_type() {
163                                Any::Advice => {
164                                    advice_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
165                                }
166                                Any::Fixed => {
167                                    fixed_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
168                                }
169                                Any::Instance => {
170                                    instance_evals
171                                        [vk.cs.get_any_query_index(column, Rotation::cur())]
172                                }
173                            })
174                            .zip(permutation_evals.iter())
175                        {
176                            left *= &(eval + &(*beta * permutation_eval) + &*gamma);
177                        }
178
179                        let mut right = set.permutation_product_eval;
180                        let mut current_delta = (*beta * &*x)
181                            * &(C::Scalar::DELTA.pow_vartime(&[(chunk_index * chunk_len) as u64]));
182                        for eval in columns.iter().map(|&column| match column.column_type() {
183                            Any::Advice => {
184                                advice_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
185                            }
186                            Any::Fixed => {
187                                fixed_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
188                            }
189                            Any::Instance => {
190                                instance_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
191                            }
192                        }) {
193                            right *= &(eval + &current_delta + &*gamma);
194                            current_delta *= &C::Scalar::DELTA;
195                        }
196
197                        (left - &right) * (C::Scalar::one() - &(l_last + &l_blind))
198                    }),
199            )
200    }
201
202    pub(in crate::plonk) fn queries<'r, 'params: 'r>(
203        &'r self,
204        vk: &'r plonk::VerifyingKey<C>,
205        x: ChallengeX<C>,
206    ) -> impl Iterator<Item = VerifierQuery<'r, 'params, C>> + Clone {
207        let blinding_factors = vk.cs.blinding_factors();
208        let x_next = vk.domain.rotate_omega(*x, Rotation::next());
209        let x_last = vk
210            .domain
211            .rotate_omega(*x, Rotation(-((blinding_factors + 1) as i32)));
212
213        iter::empty()
214            .chain(self.sets.iter().flat_map(move |set| {
215                iter::empty()
216                    // Open permutation product commitments at x and \omega^{-1} x
217                    // Open permutation product commitments at x and \omega x
218                    .chain(Some(VerifierQuery::new_commitment(
219                        &set.permutation_product_commitment,
220                        *x,
221                        set.permutation_product_eval,
222                    )))
223                    .chain(Some(VerifierQuery::new_commitment(
224                        &set.permutation_product_commitment,
225                        x_next,
226                        set.permutation_product_next_eval,
227                    )))
228            }))
229            // Open it at \omega^{last} x for all but the last set
230            .chain(self.sets.iter().rev().skip(1).flat_map(move |set| {
231                Some(VerifierQuery::new_commitment(
232                    &set.permutation_product_commitment,
233                    x_last,
234                    set.permutation_product_last_eval.unwrap(),
235                ))
236            }))
237    }
238}
239
240impl<C: CurveAffine> CommonEvaluated<C> {
241    pub(in crate::plonk) fn queries<'r, 'params: 'r>(
242        &'r self,
243        vkey: &'r VerifyingKey<C>,
244        x: ChallengeX<C>,
245    ) -> impl Iterator<Item = VerifierQuery<'r, 'params, C>> + Clone {
246        // Open permutation commitments for each permutation argument at x
247        vkey.commitments
248            .iter()
249            .zip(self.permutation_evals.iter())
250            .map(move |(commitment, &eval)| VerifierQuery::new_commitment(commitment, *x, eval))
251    }
252}
halo2_proofs/plonk/permutation/verifier.rs

halo2_proofs/plonk/permutation/
verifier.rs
