halo2_axiom/plonk/
permutation.rs

Help
1//! Implementation of permutation argument.
2
3use super::circuit::{Any, Column};
4use crate::{
5    arithmetic::CurveAffine,
6    helpers::{
7        polynomial_slice_byte_length, read_polynomial_vec, write_polynomial_slice,
8        SerdeCurveAffine, SerdePrimeField,
9    },
10    poly::{Coeff, LagrangeCoeff, Polynomial},
11    SerdeFormat,
12};
13
14pub(crate) mod keygen;
15pub(crate) mod prover;
16pub(crate) mod verifier;
17
18pub use keygen::Assembly;
19
20use std::io;
21
22/// A permutation argument.
23#[derive(Debug, Clone)]
24pub struct Argument {
25    /// A sequence of columns involved in the argument.
26    pub(super) columns: Vec<Column<Any>>,
27}
28
29impl Argument {
30    pub(crate) fn new() -> Self {
31        Argument { columns: vec![] }
32    }
33
34    /// Returns the minimum circuit degree required by the permutation argument.
35    /// The argument may use larger degree gates depending on the actual
36    /// circuit's degree and how many columns are involved in the permutation.
37    pub(crate) fn required_degree(&self) -> usize {
38        // degree 2:
39        // l_0(X) * (1 - z(X)) = 0
40        //
41        // We will fit as many polynomials p_i(X) as possible
42        // into the required degree of the circuit, so the
43        // following will not affect the required degree of
44        // this middleware.
45        //
46        // (1 - (l_last(X) + l_blind(X))) * (
47        //   z(\omega X) \prod (p(X) + \beta s_i(X) + \gamma)
48        // - z(X) \prod (p(X) + \delta^i \beta X + \gamma)
49        // )
50        //
51        // On the first sets of columns, except the first
52        // set, we will do
53        //
54        // l_0(X) * (z(X) - z'(\omega^(last) X)) = 0
55        //
56        // where z'(X) is the permutation for the previous set
57        // of columns.
58        //
59        // On the final set of columns, we will do
60        //
61        // degree 3:
62        // l_last(X) * (z'(X)^2 - z'(X)) = 0
63        //
64        // which will allow the last value to be zero to
65        // ensure the argument is perfectly complete.
66
67        // There are constraints of degree 3 regardless of the
68        // number of columns involved.
69        3
70    }
71
72    pub(crate) fn add_column(&mut self, column: Column<Any>) {
73        if !self.columns.contains(&column) {
74            self.columns.push(column);
75        }
76    }
77
78    /// Returns columns that participate on the permutation argument.
79    pub fn get_columns(&self) -> Vec<Column<Any>> {
80        self.columns.clone()
81    }
82}
83
84/// The verifying key for a single permutation argument.
85#[derive(Clone, Debug)]
86pub struct VerifyingKey<C: CurveAffine> {
87    commitments: Vec<C>,
88}
89
90impl<C: CurveAffine> VerifyingKey<C> {
91    /// Returns commitments of sigma polynomials
92    pub fn commitments(&self) -> &Vec<C> {
93        &self.commitments
94    }
95
96    pub(crate) fn write<W: io::Write>(&self, writer: &mut W, format: SerdeFormat) -> io::Result<()>
97    where
98        C: SerdeCurveAffine,
99    {
100        for commitment in &self.commitments {
101            commitment.write(writer, format)?;
102        }
103        Ok(())
104    }
105
106    pub(crate) fn read<R: io::Read>(
107        reader: &mut R,
108        argument: &Argument,
109        format: SerdeFormat,
110    ) -> io::Result<Self>
111    where
112        C: SerdeCurveAffine,
113    {
114        let commitments = (0..argument.columns.len())
115            .map(|_| C::read(reader, format))
116            .collect::<io::Result<Vec<_>>>()?;
117        Ok(VerifyingKey { commitments })
118    }
119
120    pub(crate) fn bytes_length(&self) -> usize {
121        self.commitments.len() * C::default().to_bytes().as_ref().len()
122    }
123}
124
125/// The proving key for a single permutation argument.
126#[derive(Clone, Debug)]
127pub(crate) struct ProvingKey<C: CurveAffine> {
128    permutations: Vec<Polynomial<C::Scalar, LagrangeCoeff>>,
129    pub(super) polys: Vec<Polynomial<C::Scalar, Coeff>>,
130}
131
132impl<C: SerdeCurveAffine> ProvingKey<C>
133where
134    C::Scalar: SerdePrimeField,
135{
136    /// Reads proving key for a single permutation argument from buffer using `Polynomial::read`.
137    pub(super) fn read<R: io::Read>(reader: &mut R, format: SerdeFormat) -> Self {
138        let permutations = read_polynomial_vec(reader, format);
139        let polys = read_polynomial_vec(reader, format);
140        ProvingKey {
141            permutations,
142            polys,
143        }
144    }
145
146    /// Writes proving key for a single permutation argument to buffer using `Polynomial::write`.
147    pub(super) fn write<W: io::Write>(&self, writer: &mut W, format: SerdeFormat) {
148        write_polynomial_slice(&self.permutations, writer, format);
149        write_polynomial_slice(&self.polys, writer, format);
150    }
151}
152
153impl<C: CurveAffine> ProvingKey<C> {
154    /// Gets the total number of bytes in the serialization of `self`
155    pub(super) fn bytes_length(&self) -> usize {
156        polynomial_slice_byte_length(&self.permutations) + polynomial_slice_byte_length(&self.polys)
157    }
158}
halo2_axiom/plonk/permutation.rs

halo2_axiom/plonk/
permutation.rs
