halo2_proofs/plonk/
permutation.rs

Help
1use super::circuit::{Any, Column};
2use crate::{
3    arithmetic::CurveAffine,
4    helpers::CurveRead,
5    poly::{Coeff, ExtendedLagrangeCoeff, LagrangeCoeff, Polynomial},
6};
7
8pub(crate) mod keygen;
9pub(crate) mod prover;
10pub(crate) mod verifier;
11
12use std::io;
13
14/// A permutation argument.
15#[derive(Debug, Clone)]
16pub(crate) struct Argument {
17    /// A sequence of columns involved in the argument.
18    columns: Vec<Column<Any>>,
19}
20
21impl Argument {
22    pub(crate) fn new() -> Self {
23        Argument { columns: vec![] }
24    }
25
26    /// Returns the minimum circuit degree required by the permutation argument.
27    /// The argument may use larger degree gates depending on the actual
28    /// circuit's degree and how many columns are involved in the permutation.
29    pub(crate) fn required_degree(&self) -> usize {
30        // degree 2:
31        // l_0(X) * (1 - z(X)) = 0
32        //
33        // We will fit as many polynomials p_i(X) as possible
34        // into the required degree of the circuit, so the
35        // following will not affect the required degree of
36        // this middleware.
37        //
38        // (1 - (l_last(X) + l_blind(X))) * (
39        //   z(\omega X) \prod (p(X) + \beta s_i(X) + \gamma)
40        // - z(X) \prod (p(X) + \delta^i \beta X + \gamma)
41        // )
42        //
43        // On the first sets of columns, except the first
44        // set, we will do
45        //
46        // l_0(X) * (z(X) - z'(\omega^(last) X)) = 0
47        //
48        // where z'(X) is the permutation for the previous set
49        // of columns.
50        //
51        // On the final set of columns, we will do
52        //
53        // degree 3:
54        // l_last(X) * (z'(X)^2 - z'(X)) = 0
55        //
56        // which will allow the last value to be zero to
57        // ensure the argument is perfectly complete.
58
59        // There are constraints of degree 3 regardless of the
60        // number of columns involved.
61        3
62    }
63
64    pub(crate) fn add_column(&mut self, column: Column<Any>) {
65        if !self.columns.contains(&column) {
66            self.columns.push(column);
67        }
68    }
69
70    pub(crate) fn get_columns(&self) -> Vec<Column<Any>> {
71        self.columns.clone()
72    }
73}
74
75/// The verifying key for a single permutation argument.
76#[derive(Clone, Debug)]
77pub(crate) struct VerifyingKey<C: CurveAffine> {
78    commitments: Vec<C>,
79}
80
81/// The proving key for a single permutation argument.
82#[derive(Clone, Debug)]
83pub(crate) struct ProvingKey<C: CurveAffine> {
84    permutations: Vec<Polynomial<C::Scalar, LagrangeCoeff>>,
85    polys: Vec<Polynomial<C::Scalar, Coeff>>,
86    pub(super) cosets: Vec<Polynomial<C::Scalar, ExtendedLagrangeCoeff>>,
87}
halo2_proofs/plonk/permutation.rs

halo2_proofs/plonk/
permutation.rs
