halo2_axiom/
plonk.rs

Help
1//! This module provides an implementation of a variant of (Turbo)[PLONK][plonk]
2//! that is designed specifically for the polynomial commitment scheme described
3//! in the [Halo][halo] paper.
4//!
5//! [halo]: https://eprint.iacr.org/2019/1021
6//! [plonk]: https://eprint.iacr.org/2019/953
7
8use blake2b_simd::Params as Blake2bParams;
9use group::ff::{Field, FromUniformBytes, PrimeField};
10
11use crate::arithmetic::CurveAffine;
12use crate::helpers::{
13    polynomial_slice_byte_length, read_polynomial_vec, write_polynomial_slice, SerdeCurveAffine,
14    SerdePrimeField,
15};
16use crate::poly::{Coeff, EvaluationDomain, LagrangeCoeff, PinnedEvaluationDomain, Polynomial};
17use crate::transcript::{ChallengeScalar, EncodedChallenge, Transcript};
18use crate::SerdeFormat;
19
20mod assigned;
21mod circuit;
22mod error;
23mod evaluation;
24mod keygen;
25mod lookup;
26pub mod permutation;
27// mod shuffle;
28mod vanishing;
29
30mod prover;
31mod verifier;
32
33pub use assigned::*;
34pub use circuit::*;
35pub use error::*;
36pub use keygen::*;
37pub use prover::*;
38pub use verifier::*;
39
40use evaluation::Evaluator;
41
42use std::io;
43
44/// This is a verifying key which allows for the verification of proofs for a
45/// particular circuit.
46#[derive(Clone, Debug)]
47pub struct VerifyingKey<C: CurveAffine> {
48    domain: EvaluationDomain<C::Scalar>,
49    fixed_commitments: Vec<C>,
50    permutation: permutation::VerifyingKey<C>,
51    cs: ConstraintSystem<C::Scalar>,
52    /// Cached maximum degree of `cs` (which doesn't change after construction).
53    cs_degree: usize,
54    /// The representative of this `VerifyingKey` in transcripts.
55    transcript_repr: C::Scalar,
56    selectors: Vec<Vec<bool>>,
57    /// Whether selector compression is turned on or not.
58    compress_selectors: bool,
59}
60
61impl<C: SerdeCurveAffine> VerifyingKey<C>
62where
63    C::Scalar: SerdePrimeField + FromUniformBytes<64>, // the FromUniformBytes<64> should not be necessary: currently serialization always stores a Blake2b hash of verifying key; this should be removed
64{
65    /// Writes a verifying key to a buffer.
66    ///
67    /// Writes a curve element according to `format`:
68    /// - `Processed`: Writes a compressed curve element with coordinates in standard form.
69    /// Writes a field element in standard form, with endianness specified by the
70    /// `PrimeField` implementation.
71    /// - Otherwise: Writes an uncompressed curve element with coordinates in Montgomery form
72    /// Writes a field element into raw bytes in its internal Montgomery representation,
73    /// WITHOUT performing the expensive Montgomery reduction.
74    pub fn write<W: io::Write>(&self, writer: &mut W, format: SerdeFormat) -> io::Result<()> {
75        // Version byte that will be checked on read.
76        writer.write_all(&[0x02])?;
77        writer.write_all(&self.domain.k().to_le_bytes())?;
78        writer.write_all(&[self.compress_selectors as u8])?;
79        writer.write_all(&(self.fixed_commitments.len() as u32).to_le_bytes())?;
80        for commitment in &self.fixed_commitments {
81            commitment.write(writer, format)?;
82        }
83        self.permutation.write(writer, format)?;
84
85        if !self.compress_selectors {
86            assert!(self.selectors.is_empty());
87        }
88        // write self.selectors
89        for selector in &self.selectors {
90            // since `selector` is filled with `bool`, we pack them 8 at a time into bytes and then write
91            for bits in selector.chunks(8) {
92                writer.write_all(&[crate::helpers::pack(bits)])?;
93            }
94        }
95        Ok(())
96    }
97
98    /// Reads a verification key from a buffer.
99    ///
100    /// Reads a curve element from the buffer and parses it according to the `format`:
101    /// - `Processed`: Reads a compressed curve element and decompresses it.
102    /// Reads a field element in standard form, with endianness specified by the
103    /// `PrimeField` implementation, and checks that the element is less than the modulus.
104    /// - `RawBytes`: Reads an uncompressed curve element with coordinates in Montgomery form.
105    /// Checks that field elements are less than modulus, and then checks that the point is on the curve.
106    /// - `RawBytesUnchecked`: Reads an uncompressed curve element with coordinates in Montgomery form;
107    /// does not perform any checks
108    pub fn read<R: io::Read, ConcreteCircuit: Circuit<C::Scalar>>(
109        reader: &mut R,
110        format: SerdeFormat,
111        #[cfg(feature = "circuit-params")] params: ConcreteCircuit::Params,
112    ) -> io::Result<Self> {
113        let mut version_byte = [0u8; 1];
114        reader.read_exact(&mut version_byte)?;
115        if 0x02 != version_byte[0] {
116            return Err(io::Error::new(
117                io::ErrorKind::InvalidData,
118                "unexpected version byte",
119            ));
120        }
121        let mut k = [0u8; 4];
122        reader.read_exact(&mut k)?;
123        let k = u32::from_le_bytes(k);
124        let mut compress_selectors = [0u8; 1];
125        reader.read_exact(&mut compress_selectors)?;
126        if compress_selectors[0] != 0 && compress_selectors[0] != 1 {
127            return Err(io::Error::new(
128                io::ErrorKind::InvalidData,
129                "unexpected compress_selectors not boolean",
130            ));
131        }
132        let compress_selectors = compress_selectors[0] == 1;
133        let (domain, cs, _) = keygen::create_domain::<C, ConcreteCircuit>(
134            k,
135            #[cfg(feature = "circuit-params")]
136            params,
137        );
138        let mut num_fixed_columns = [0u8; 4];
139        reader.read_exact(&mut num_fixed_columns)?;
140        let num_fixed_columns = u32::from_le_bytes(num_fixed_columns);
141
142        let fixed_commitments: Vec<_> = (0..num_fixed_columns)
143            .map(|_| C::read(reader, format))
144            .collect::<io::Result<_>>()?;
145
146        let permutation = permutation::VerifyingKey::read(reader, &cs.permutation, format)?;
147
148        let (cs, selectors) = if compress_selectors {
149            // read selectors
150            let selectors: Vec<Vec<bool>> = vec![vec![false; 1 << k]; cs.num_selectors]
151                .into_iter()
152                .map(|mut selector| {
153                    let mut selector_bytes = vec![0u8; (selector.len() + 7) / 8];
154                    reader.read_exact(&mut selector_bytes)?;
155                    for (bits, byte) in selector.chunks_mut(8).zip(selector_bytes) {
156                        crate::helpers::unpack(byte, bits);
157                    }
158                    Ok(selector)
159                })
160                .collect::<io::Result<_>>()?;
161            let (cs, _) = cs.compress_selectors(selectors.clone());
162            (cs, selectors)
163        } else {
164            // we still need to replace selectors with fixed Expressions in `cs`
165            let fake_selectors = vec![vec![false]; cs.num_selectors];
166            let (cs, _) = cs.directly_convert_selectors_to_fixed(fake_selectors);
167            (cs, vec![])
168        };
169
170        Ok(Self::from_parts(
171            domain,
172            fixed_commitments,
173            permutation,
174            cs,
175            selectors,
176            compress_selectors,
177        ))
178    }
179
180    /// Writes a verifying key to a vector of bytes using [`Self::write`].
181    pub fn to_bytes(&self, format: SerdeFormat) -> Vec<u8> {
182        let mut bytes = Vec::<u8>::with_capacity(self.bytes_length());
183        Self::write(self, &mut bytes, format).expect("Writing to vector should not fail");
184        bytes
185    }
186
187    /// Reads a verification key from a slice of bytes using [`Self::read`].
188    pub fn from_bytes<ConcreteCircuit: Circuit<C::Scalar>>(
189        mut bytes: &[u8],
190        format: SerdeFormat,
191        #[cfg(feature = "circuit-params")] params: ConcreteCircuit::Params,
192    ) -> io::Result<Self> {
193        Self::read::<_, ConcreteCircuit>(
194            &mut bytes,
195            format,
196            #[cfg(feature = "circuit-params")]
197            params,
198        )
199    }
200}
201
202impl<C: CurveAffine> VerifyingKey<C> {
203    fn bytes_length(&self) -> usize {
204        8 + (self.fixed_commitments.len() * C::default().to_bytes().as_ref().len())
205            + self.permutation.bytes_length()
206            + self.selectors.len()
207                * (self
208                    .selectors
209                    .get(0)
210                    .map(|selector| (selector.len() + 7) / 8)
211                    .unwrap_or(0))
212    }
213
214    fn from_parts(
215        domain: EvaluationDomain<C::Scalar>,
216        fixed_commitments: Vec<C>,
217        permutation: permutation::VerifyingKey<C>,
218        cs: ConstraintSystem<C::Scalar>,
219        selectors: Vec<Vec<bool>>,
220        compress_selectors: bool,
221    ) -> Self
222    where
223        C::Scalar: FromUniformBytes<64>,
224    {
225        // Compute cached values.
226        let cs_degree = cs.degree();
227
228        let mut vk = Self {
229            domain,
230            fixed_commitments,
231            permutation,
232            cs,
233            cs_degree,
234            // Temporary, this is not pinned.
235            transcript_repr: C::Scalar::ZERO,
236            selectors,
237            compress_selectors,
238        };
239
240        let mut hasher = Blake2bParams::new()
241            .hash_length(64)
242            .personal(b"Halo2-Verify-Key")
243            .to_state();
244
245        let s = format!("{:?}", vk.pinned());
246
247        hasher.update(&(s.len() as u64).to_le_bytes());
248        hasher.update(s.as_bytes());
249
250        // Hash in final Blake2bState
251        vk.transcript_repr = C::Scalar::from_uniform_bytes(hasher.finalize().as_array());
252
253        vk
254    }
255
256    /// Hashes a verification key into a transcript.
257    pub fn hash_into<E: EncodedChallenge<C>, T: Transcript<C, E>>(
258        &self,
259        transcript: &mut T,
260    ) -> io::Result<()> {
261        transcript.common_scalar(self.transcript_repr)?;
262
263        Ok(())
264    }
265
266    /// Obtains a pinned representation of this verification key that contains
267    /// the minimal information necessary to reconstruct the verification key.
268    pub fn pinned(&self) -> PinnedVerificationKey<'_, C> {
269        PinnedVerificationKey {
270            base_modulus: C::Base::MODULUS,
271            scalar_modulus: C::Scalar::MODULUS,
272            domain: self.domain.pinned(),
273            fixed_commitments: &self.fixed_commitments,
274            permutation: &self.permutation,
275            cs: self.cs.pinned(),
276        }
277    }
278
279    /// Returns commitments of fixed polynomials
280    pub fn fixed_commitments(&self) -> &Vec<C> {
281        &self.fixed_commitments
282    }
283
284    /// Returns `VerifyingKey` of permutation
285    pub fn permutation(&self) -> &permutation::VerifyingKey<C> {
286        &self.permutation
287    }
288
289    /// Returns `ConstraintSystem`
290    pub fn cs(&self) -> &ConstraintSystem<C::Scalar> {
291        &self.cs
292    }
293
294    /// Returns representative of this `VerifyingKey` in transcripts
295    pub fn transcript_repr(&self) -> C::Scalar {
296        self.transcript_repr
297    }
298}
299
300/// Minimal representation of a verification key that can be used to identify
301/// its active contents.
302#[allow(dead_code)]
303#[derive(Debug)]
304pub struct PinnedVerificationKey<'a, C: CurveAffine> {
305    base_modulus: &'static str,
306    scalar_modulus: &'static str,
307    domain: PinnedEvaluationDomain<'a, C::Scalar>,
308    cs: PinnedConstraintSystem<'a, C::Scalar>,
309    fixed_commitments: &'a Vec<C>,
310    permutation: &'a permutation::VerifyingKey<C>,
311}
312/// This is a proving key which allows for the creation of proofs for a
313/// particular circuit.
314#[derive(Clone, Debug)]
315pub struct ProvingKey<C: CurveAffine> {
316    vk: VerifyingKey<C>,
317    l0: Polynomial<C::Scalar, Coeff>,
318    l_last: Polynomial<C::Scalar, Coeff>,
319    l_active_row: Polynomial<C::Scalar, Coeff>,
320    fixed_values: Vec<Polynomial<C::Scalar, LagrangeCoeff>>,
321    fixed_polys: Vec<Polynomial<C::Scalar, Coeff>>,
322    permutation: permutation::ProvingKey<C>,
323    ev: Evaluator<C>,
324}
325
326impl<C: CurveAffine> ProvingKey<C>
327where
328    C::Scalar: FromUniformBytes<64>,
329{
330    /// Get the underlying [`VerifyingKey`].
331    pub fn get_vk(&self) -> &VerifyingKey<C> {
332        &self.vk
333    }
334
335    /// Gets the total number of bytes in the serialization of `self`
336    fn bytes_length(&self) -> usize {
337        let scalar_len = C::Scalar::default().to_repr().as_ref().len();
338        self.vk.bytes_length()
339            + 12
340            + scalar_len * (self.l0.len() + self.l_last.len() + self.l_active_row.len())
341            + polynomial_slice_byte_length(&self.fixed_values)
342            + polynomial_slice_byte_length(&self.fixed_polys)
343            + self.permutation.bytes_length()
344    }
345}
346
347impl<C: SerdeCurveAffine> ProvingKey<C>
348where
349    C::Scalar: SerdePrimeField + FromUniformBytes<64>,
350{
351    /// Writes a proving key to a buffer.
352    ///
353    /// Writes a curve element according to `format`:
354    /// - `Processed`: Writes a compressed curve element with coordinates in standard form.
355    /// Writes a field element in standard form, with endianness specified by the
356    /// `PrimeField` implementation.
357    /// - Otherwise: Writes an uncompressed curve element with coordinates in Montgomery form
358    /// Writes a field element into raw bytes in its internal Montgomery representation,
359    /// WITHOUT performing the expensive Montgomery reduction.
360    /// Does so by first writing the verifying key and then serializing the rest of the data (in the form of field polynomials)
361    pub fn write<W: io::Write>(&self, writer: &mut W, format: SerdeFormat) -> io::Result<()> {
362        self.vk.write(writer, format)?;
363        self.l0.write(writer, format);
364        self.l_last.write(writer, format);
365        self.l_active_row.write(writer, format);
366        write_polynomial_slice(&self.fixed_values, writer, format);
367        write_polynomial_slice(&self.fixed_polys, writer, format);
368        self.permutation.write(writer, format);
369        Ok(())
370    }
371
372    /// Reads a proving key from a buffer.
373    /// Does so by reading verification key first, and then deserializing the rest of the file into the remaining proving key data.
374    ///
375    /// Reads a curve element from the buffer and parses it according to the `format`:
376    /// - `Processed`: Reads a compressed curve element and decompresses it.
377    /// Reads a field element in standard form, with endianness specified by the
378    /// `PrimeField` implementation, and checks that the element is less than the modulus.
379    /// - `RawBytes`: Reads an uncompressed curve element with coordinates in Montgomery form.
380    /// Checks that field elements are less than modulus, and then checks that the point is on the curve.
381    /// - `RawBytesUnchecked`: Reads an uncompressed curve element with coordinates in Montgomery form;
382    /// does not perform any checks
383    pub fn read<R: io::Read, ConcreteCircuit: Circuit<C::Scalar>>(
384        reader: &mut R,
385        format: SerdeFormat,
386        #[cfg(feature = "circuit-params")] params: ConcreteCircuit::Params,
387    ) -> io::Result<Self> {
388        let vk = VerifyingKey::<C>::read::<R, ConcreteCircuit>(
389            reader,
390            format,
391            #[cfg(feature = "circuit-params")]
392            params,
393        )?;
394        let l0 = Polynomial::read(reader, format);
395        let l_last = Polynomial::read(reader, format);
396        let l_active_row = Polynomial::read(reader, format);
397        let fixed_values = read_polynomial_vec(reader, format);
398        let fixed_polys = read_polynomial_vec(reader, format);
399        let permutation = permutation::ProvingKey::read(reader, format);
400        let ev = Evaluator::new(vk.cs());
401        Ok(Self {
402            vk,
403            l0,
404            l_last,
405            l_active_row,
406            fixed_values,
407            fixed_polys,
408            permutation,
409            ev,
410        })
411    }
412
413    /// Writes a proving key to a vector of bytes using [`Self::write`].
414    pub fn to_bytes(&self, format: SerdeFormat) -> Vec<u8> {
415        let mut bytes = Vec::<u8>::with_capacity(self.bytes_length());
416        Self::write(self, &mut bytes, format).expect("Writing to vector should not fail");
417        bytes
418    }
419
420    /// Reads a proving key from a slice of bytes using [`Self::read`].
421    pub fn from_bytes<ConcreteCircuit: Circuit<C::Scalar>>(
422        mut bytes: &[u8],
423        format: SerdeFormat,
424        #[cfg(feature = "circuit-params")] params: ConcreteCircuit::Params,
425    ) -> io::Result<Self> {
426        Self::read::<_, ConcreteCircuit>(
427            &mut bytes,
428            format,
429            #[cfg(feature = "circuit-params")]
430            params,
431        )
432    }
433}
434
435impl<C: CurveAffine> VerifyingKey<C> {
436    /// Get the underlying [`EvaluationDomain`].
437    pub fn get_domain(&self) -> &EvaluationDomain<C::Scalar> {
438        &self.domain
439    }
440}
441
442#[derive(Clone, Copy, Debug)]
443struct Theta;
444type ChallengeTheta<F> = ChallengeScalar<F, Theta>;
445
446#[derive(Clone, Copy, Debug)]
447struct Beta;
448type ChallengeBeta<F> = ChallengeScalar<F, Beta>;
449
450#[derive(Clone, Copy, Debug)]
451struct Gamma;
452type ChallengeGamma<F> = ChallengeScalar<F, Gamma>;
453
454#[derive(Clone, Copy, Debug)]
455struct Y;
456type ChallengeY<F> = ChallengeScalar<F, Y>;
457
458#[derive(Clone, Copy, Debug)]
459struct X;
460type ChallengeX<F> = ChallengeScalar<F, X>;
halo2_axiom/plonk.rs

halo2_axiom/
plonk.rs
