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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

//! Implementation of permutation argument.

use crate::plonk::{Column, Error};
use halo2_middleware::circuit::{Any, Cell};

/// A permutation argument.
#[derive(Default, Debug, Clone)]
pub struct Argument {
    /// A sequence of columns involved in the argument.
    pub(crate) columns: Vec<Column<Any>>,
}

impl Argument {
    /// 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);
        }
    }

    /// Returns columns that participate on the permutation argument.
    pub fn get_columns(&self) -> Vec<Column<Any>> {
        self.columns.clone()
    }
}

#[derive(Clone, Debug)]
pub(crate) struct Assembly {
    pub(crate) n: usize,
    pub(crate) columns: Vec<Column<Any>>,
    pub(crate) copies: Vec<(Cell, Cell)>,
}

impl Assembly {
    pub(crate) fn new(n: usize, p: &Argument) -> Self {
        Self {
            n,
            columns: p.columns.clone(),
            copies: Vec::new(),
        }
    }

    pub(crate) fn copy(
        &mut self,
        left_column: Column<Any>,
        left_row: usize,
        right_column: Column<Any>,
        right_row: usize,
    ) -> Result<(), Error> {
        if !self.columns.contains(&left_column) {
            return Err(Error::ColumnNotInPermutation(left_column));
        }
        if !self.columns.contains(&right_column) {
            return Err(Error::ColumnNotInPermutation(right_column));
        }
        // Check bounds
        if left_row >= self.n || right_row >= self.n {
            return Err(Error::BoundsFailure);
        }
        self.copies.push((
            Cell {
                column: left_column.into(),
                row: left_row,
            },
            Cell {
                column: right_column.into(),
                row: right_row,
            },
        ));
        Ok(())
    }
}