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