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