1use ark_std::cmp::max;
  2
  3/// Customized gate is a list of tuples of
  4///     (coefficient, selector_index, wire_indices)
  5///
  6/// Example:
  7///     q_L(X) * W_1(X)^5 - W_2(X) = 0
  8/// is represented as
  9/// vec![
 10///     ( 1,    Some(id_qL),    vec![id_W1, id_W1, id_W1, id_W1, id_W1]),
 11///     (-1,    None,           vec![id_W2])
 12/// ]
 13///
 14/// CustomizedGates {
 15///     gates: vec![
 16///         (1, Some(0), vec![0, 0, 0, 0, 0]),
 17///         (-1, None, vec![1])
 18///     ],
 19/// };
 20/// where id_qL = 0 // first selector
 21/// id_W1 = 0 // first witness
 22/// id_w2 = 1 // second witness
 23///
 24/// NOTE: here coeff is a signed integer, instead of a field element
 25#[derive(Clone, Debug, Default, PartialEq, Eq)]
 26pub struct CustomizedGates {
 27    pub(crate) gates: Vec<(i64, Option<usize>, Vec<usize>)>,
 28}
 29
 30impl CustomizedGates {
 31    /// The degree of the algebraic customized gate
 32    pub fn degree(&self) -> usize {
 33        let mut res = 0;
 34        for x in self.gates.iter() {
 35            res = max(res, x.2.len() + (x.1.is_some() as usize))
 36        }
 37        res
 38    }
 39
 40    /// The number of selectors in a customized gate
 41    pub fn num_selector_columns(&self) -> usize {
 42        let mut res = 0;
 43        for (_coeff, q, _ws) in self.gates.iter() {
 44            // a same selector must not be used for multiple monomials.
 45            if q.is_some() {
 46                res += 1;
 47            }
 48        }
 49        res
 50    }
 51
 52    /// The number of witnesses in a customized gate
 53    pub fn num_witness_columns(&self) -> usize {
 54        let mut res = 0;
 55        for (_coeff, _q, ws) in self.gates.iter() {
 56            // witness list must be ordered
 57            // so we just need to compare with the last one
 58            if let Some(&p) = ws.last() {
 59                if res < p {
 60                    res = p
 61                }
 62            }
 63        }
 64        // add one here because index starts from 0
 65        res + 1
 66    }
 67
 68    /// Return a vanilla plonk gate:
 69    /// ``` ignore
 70    ///   q_L w_1 + q_R w_2 + q_O w_3 + q_M w1w2 + q_C = 0
 71    /// ```
 72    /// which is
 73    /// ``` ignore
 74    ///     (1,    Some(id_qL),     vec![id_W1]),
 75    ///     (1,    Some(id_qR),     vec![id_W2]),
 76    ///     (1,    Some(id_qO),     vec![id_W3]),
 77    ///     (1,    Some(id_qM),     vec![id_W1, id_w2]),
 78    ///     (1,    Some(id_qC),     vec![]),
 79    /// ```
 80    pub fn vanilla_plonk_gate() -> Self {
 81        Self {
 82            gates: vec![
 83                (1, Some(0), vec![0]),
 84                (1, Some(1), vec![1]),
 85                (1, Some(2), vec![2]),
 86                (1, Some(3), vec![0, 1]),
 87                (1, Some(4), vec![]),
 88            ],
 89        }
 90    }
 91
 92    /// Return a jellyfish turbo plonk gate:
 93    /// ```ignore
 94    ///     q_1 w_1   + q_2 w_2   + q_3 w_3   + q_4 w4
 95    ///   + q_M1 w1w2 + q_M2 w3w4
 96    ///   + q_H1 w1^5 + q_H2 w2^5 + q_H3 w1^5 + q_H4 w2^5
 97    ///   + q_E w1w2w3w4
 98    ///   + q_O w5
 99    ///   + q_C
100    ///   = 0
101    /// ```
102    /// with
103    /// - w = [w1, w2, w3, w4, w5]
104    /// - q = [ q_1, q_2, q_3, q_4, q_M1, q_M2, q_H1, q_H2, q_H3, q_H4, q_E,
105    ///   q_O, q_c ]
106    ///
107    /// which is
108    /// ```ignore
109    ///     (1,    Some(q[0]),     vec![w[0]]),
110    ///     (1,    Some(q[1]),     vec![w[1]]),
111    ///     (1,    Some(q[2]),     vec![w[2]]),
112    ///     (1,    Some(q[3]),     vec![w[3]]),
113    ///     (1,    Some(q[4]),     vec![w[0], w[1]]),
114    ///     (1,    Some(q[5]),     vec![w[2], w[3]]),
115    ///     (1,    Some(q[6]),     vec![w[0], w[0], w[0], w[0], w[0]]),
116    ///     (1,    Some(q[7]),     vec![w[1], w[1], w[1], w[1], w[1]]),
117    ///     (1,    Some(q[8]),     vec![w[2], w[2], w[2], w[2], w[2]]),
118    ///     (1,    Some(q[9]),     vec![w[3], w[3], w[3], w[3], w[3]]),
119    ///     (1,    Some(q[10]),    vec![w[0], w[1], w[2], w[3]]),
120    ///     (1,    Some(q[11]),    vec![w[4]]),
121    ///     (1,    Some(q[12]),    vec![]),
122    /// ```
123    pub fn jellyfish_turbo_plonk_gate() -> Self {
124        CustomizedGates {
125            gates: vec![
126                (1, Some(0), vec![0]),
127                (1, Some(1), vec![1]),
128                (1, Some(2), vec![2]),
129                (1, Some(3), vec![3]),
130                (1, Some(4), vec![0, 1]),
131                (1, Some(5), vec![2, 3]),
132                (1, Some(6), vec![0, 0, 0, 0, 0]),
133                (1, Some(7), vec![1, 1, 1, 1, 1]),
134                (1, Some(8), vec![2, 2, 2, 2, 2]),
135                (1, Some(9), vec![3, 3, 3, 3, 3]),
136                (1, Some(10), vec![0, 1, 2, 3]),
137                (1, Some(11), vec![4]),
138                (1, Some(12), vec![]),
139            ],
140        }
141    }
142
143    /// Generate a random gate for `num_witness` with a highest degree =
144    /// `degree`
145    pub fn mock_gate(num_witness: usize, degree: usize) -> Self {
146        let mut gates = vec![];
147
148        let high_degree_term = vec![0; degree];
149
150        gates.push((1, Some(0), high_degree_term));
151        for i in 1..num_witness {
152            gates.push((1, Some(i), vec![i]))
153        }
154        gates.push((1, Some(num_witness), vec![]));
155
156        CustomizedGates { gates }
157    }
158}