halo2_axiom/plonk/permutation/
verifier.rs

Help
1use ff::{Field, PrimeField};
2use std::iter;
3
4use super::super::{circuit::Any, ChallengeBeta, ChallengeGamma, ChallengeX};
5use super::{Argument, VerifyingKey};
6use crate::{
7    arithmetic::CurveAffine,
8    plonk::{self, Error},
9    poly::{commitment::MSM, Rotation, VerifierQuery},
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    #[allow(clippy::too_many_arguments)]
103    pub(in crate::plonk) fn expressions<'a>(
104        &'a self,
105        vk: &'a plonk::VerifyingKey<C>,
106        p: &'a Argument,
107        common: &'a CommonEvaluated<C>,
108        advice_evals: &'a [C::Scalar],
109        fixed_evals: &'a [C::Scalar],
110        instance_evals: &'a [C::Scalar],
111        l_0: C::Scalar,
112        l_last: C::Scalar,
113        l_blind: C::Scalar,
114        beta: ChallengeBeta<C>,
115        gamma: ChallengeGamma<C>,
116        x: ChallengeX<C>,
117    ) -> impl Iterator<Item = C::Scalar> + 'a {
118        let chunk_len = vk.cs_degree - 2;
119        iter::empty()
120            // Enforce only for the first set.
121            // l_0(X) * (1 - z_0(X)) = 0
122            .chain(
123                self.sets
124                    .first()
125                    .map(|first_set| l_0 * &(C::Scalar::ONE - &first_set.permutation_product_eval)),
126            )
127            // Enforce only for the last set.
128            // l_last(X) * (z_l(X)^2 - z_l(X)) = 0
129            .chain(self.sets.last().map(|last_set| {
130                (last_set.permutation_product_eval.square() - &last_set.permutation_product_eval)
131                    * &l_last
132            }))
133            // Except for the first set, enforce.
134            // l_0(X) * (z_i(X) - z_{i-1}(\omega^(last) X)) = 0
135            .chain(
136                self.sets
137                    .iter()
138                    .skip(1)
139                    .zip(self.sets.iter())
140                    .map(|(set, last_set)| {
141                        (
142                            set.permutation_product_eval,
143                            last_set.permutation_product_last_eval.unwrap(),
144                        )
145                    })
146                    .map(move |(set, prev_last)| (set - &prev_last) * &l_0),
147            )
148            // And for all the sets we enforce:
149            // (1 - (l_last(X) + l_blind(X))) * (
150            //   z_i(\omega X) \prod (p(X) + \beta s_i(X) + \gamma)
151            // - z_i(X) \prod (p(X) + \delta^i \beta X + \gamma)
152            // )
153            .chain(
154                self.sets
155                    .iter()
156                    .zip(p.columns.chunks(chunk_len))
157                    .zip(common.permutation_evals.chunks(chunk_len))
158                    .enumerate()
159                    .map(move |(chunk_index, ((set, columns), permutation_evals))| {
160                        let mut left = set.permutation_product_next_eval;
161                        for (eval, permutation_eval) in columns
162                            .iter()
163                            .map(|&column| match column.column_type() {
164                                Any::Advice(_) => {
165                                    advice_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
166                                }
167                                Any::Fixed => {
168                                    fixed_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
169                                }
170                                Any::Instance => {
171                                    instance_evals
172                                        [vk.cs.get_any_query_index(column, Rotation::cur())]
173                                }
174                            })
175                            .zip(permutation_evals.iter())
176                        {
177                            left *= &(eval + &(*beta * permutation_eval) + &*gamma);
178                        }
179
180                        let mut right = set.permutation_product_eval;
181                        let mut current_delta = (*beta * &*x)
182                            * &(<C::Scalar as PrimeField>::DELTA
183                                .pow_vartime([(chunk_index * chunk_len) as u64]));
184                        for eval in columns.iter().map(|&column| match column.column_type() {
185                            Any::Advice(_) => {
186                                advice_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
187                            }
188                            Any::Fixed => {
189                                fixed_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
190                            }
191                            Any::Instance => {
192                                instance_evals[vk.cs.get_any_query_index(column, Rotation::cur())]
193                            }
194                        }) {
195                            right *= &(eval + &current_delta + &*gamma);
196                            current_delta *= &C::Scalar::DELTA;
197                        }
198
199                        (left - &right) * (C::Scalar::ONE - &(l_last + &l_blind))
200                    }),
201            )
202    }
203
204    pub(in crate::plonk) fn queries<'r, M: MSM<C> + 'r>(
205        &'r self,
206        vk: &'r plonk::VerifyingKey<C>,
207        x: ChallengeX<C>,
208    ) -> impl Iterator<Item = VerifierQuery<'r, C, M>> + Clone {
209        let blinding_factors = vk.cs.blinding_factors();
210        let x_next = vk.domain.rotate_omega(*x, Rotation::next());
211        let x_last = vk
212            .domain
213            .rotate_omega(*x, Rotation(-((blinding_factors + 1) as i32)));
214
215        iter::empty()
216            .chain(self.sets.iter().flat_map(move |set| {
217                iter::empty()
218                    // Open permutation product commitments at x and \omega^{-1} x
219                    // Open permutation product commitments at x and \omega x
220                    .chain(Some(VerifierQuery::new_commitment(
221                        &set.permutation_product_commitment,
222                        *x,
223                        set.permutation_product_eval,
224                    )))
225                    .chain(Some(VerifierQuery::new_commitment(
226                        &set.permutation_product_commitment,
227                        x_next,
228                        set.permutation_product_next_eval,
229                    )))
230            }))
231            // Open it at \omega^{last} x for all but the last set
232            .chain(self.sets.iter().rev().skip(1).flat_map(move |set| {
233                Some(VerifierQuery::new_commitment(
234                    &set.permutation_product_commitment,
235                    x_last,
236                    set.permutation_product_last_eval.unwrap(),
237                ))
238            }))
239    }
240}
241
242impl<C: CurveAffine> CommonEvaluated<C> {
243    pub(in crate::plonk) fn queries<'r, M: MSM<C> + 'r>(
244        &'r self,
245        vkey: &'r VerifyingKey<C>,
246        x: ChallengeX<C>,
247    ) -> impl Iterator<Item = VerifierQuery<'r, C, M>> + Clone {
248        // Open permutation commitments for each permutation argument at x
249        vkey.commitments
250            .iter()
251            .zip(self.permutation_evals.iter())
252            .map(move |(commitment, &eval)| VerifierQuery::new_commitment(commitment, *x, eval))
253    }
254}
halo2_axiom/plonk/permutation/verifier.rs

halo2_axiom/plonk/permutation/
verifier.rs
