hyperplonk/hyperplonk/src/custom_gate.rs
hyperplonk/src/custom_gate.rsRaw
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 mut high_degree_term = vec![0; degree - 1];
149 high_degree_term.push(1);
150
151 gates.push((1, Some(0), high_degree_term));
152 for i in 0..num_witness {
153 gates.push((1, Some(i + 1), vec![i]))
154 }
155 gates.push((1, Some(num_witness + 1), vec![]));
156
157 CustomizedGates { gates }
158 }
159
160 /// Return a plonk gate where #selector > #witness * 2
161 /// ``` ignore
162 /// q_1 w_1 + q_2 w_2 + q_3 w_3 +
163 /// q_4 w1w2 + q_5 w1w3 + q_6 w2w3 +
164 /// q_7 = 0
165 /// ```
166 /// which is
167 /// ``` ignore
168 /// (1, Some(id_qL), vec![id_W1]),
169 /// (1, Some(id_qR), vec![id_W2]),
170 /// (1, Some(id_qO), vec![id_W3]),
171 /// (1, Some(id_qM), vec![id_W1, id_w2]),
172 /// (1, Some(id_qC), vec![]),
173 /// ```
174 pub fn super_long_selector_gate() -> Self {
175 Self {
176 gates: vec![
177 (1, Some(0), vec![0]),
178 (1, Some(1), vec![1]),
179 (1, Some(2), vec![2]),
180 (1, Some(3), vec![0, 1]),
181 (1, Some(4), vec![0, 2]),
182 (1, Some(5), vec![1, 2]),
183 (1, Some(6), vec![]),
184 ],
185 }
186 }
187}