barretenberg
Loading...
Searching...
No Matches
sha256.hpp
1#pragma once
2
3#include "barretenberg/crypto/aes128/aes128.hpp"
4#include "barretenberg/numeric/bitop/pow.hpp"
5#include "barretenberg/numeric/bitop/rotate.hpp"
6#include "barretenberg/numeric/bitop/sparse_form.hpp"
7
8#include "sparse.hpp"
9#include "types.hpp"
10
11namespace plookup {
12namespace sha256_tables {
13
14static constexpr uint64_t choose_normalization_table[28]{
15 /* xor result = 0 */
16 0, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
17 0, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
18 0, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
19 1, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
20 0, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
21 1, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
22 1, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
23 /* xor result = 1 */
24 1, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
25 1, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
26 1, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
27 2, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
28 1, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
29 2, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
30 2, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
31 /* xor result = 2 */
32 0, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
33 0, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
34 0, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
35 1, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
36 0, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
37 1, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
38 1, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
39 1, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
40 /* xor result = 3 */
41 1, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
42 1, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
43 2, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
44 1, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
45 2, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
46 2, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
47};
48
49static constexpr uint64_t majority_normalization_table[16]{
50 /* xor result = 0 */
51 0, // a + b + c = 0 => (a & b) ^ (a & c) ^ (b & c) = 0
52 0, // a + b + c = 1 => (a & b) ^ (a & c) ^ (b & c) = 0
53 1, // a + b + c = 2 => (a & b) ^ (a & c) ^ (b & c) = 1
54 1, // a + b + c = 3 => (a & b) ^ (a & c) ^ (b & c) = 1
55 /* xor result = 1 */
56 1,
57 1,
58 2,
59 2,
60 /* xor result = 2 */
61 0,
62 0,
63 1,
64 1,
65 /* xor result = 3 */
66 1,
67 1,
68 2,
69 2,
70};
71
72static constexpr uint64_t witness_extension_normalization_table[16]{
73 /* xor result = 0 */
74 0,
75 1,
76 0,
77 1,
78 /* xor result = 1 */
79 1,
80 2,
81 1,
82 2,
83 /* xor result = 2 */
84 0,
85 1,
86 0,
87 1,
88 /* xor result = 3 */
89 1,
90 2,
91 1,
92 2,
93};
94
95inline BasicTable generate_witness_extension_normalization_table(BasicTableId id, const size_t table_index)
96{
97 return sparse_tables::generate_sparse_normalization_table<16, 3, witness_extension_normalization_table>(
98 id, table_index);
99}
100
101inline BasicTable generate_choose_normalization_table(BasicTableId id, const size_t table_index)
102{
103 return sparse_tables::generate_sparse_normalization_table<28, 2, choose_normalization_table>(id, table_index);
104}
105
106inline BasicTable generate_majority_normalization_table(BasicTableId id, const size_t table_index)
107{
108 return sparse_tables::generate_sparse_normalization_table<16, 3, majority_normalization_table>(id, table_index);
109}
110
111inline MultiTable get_witness_extension_output_table(const MultiTableId id = SHA256_WITNESS_OUTPUT)
112{
113 const size_t num_entries = 11;
114
115 MultiTable table(numeric::pow64(16, 3), 1 << 3, 0, num_entries);
116
117 table.id = id;
118 for (size_t i = 0; i < num_entries; ++i) {
119 table.slice_sizes.emplace_back(numeric::pow64(16, 3));
120 table.lookup_ids.emplace_back(SHA256_WITNESS_NORMALIZE);
121 table.get_table_values.emplace_back(
122 &sparse_tables::get_sparse_normalization_values<16, witness_extension_normalization_table>);
123 }
124 return table;
125}
126
127inline MultiTable get_choose_output_table(const MultiTableId id = SHA256_CH_OUTPUT)
128{
129 const size_t num_entries = 16;
130
131 MultiTable table(numeric::pow64(28, 2), 1 << 2, 0, num_entries);
132
133 table.id = id;
134 for (size_t i = 0; i < num_entries; ++i) {
135 table.slice_sizes.emplace_back(numeric::pow64(28, 2));
136 table.lookup_ids.emplace_back(SHA256_CH_NORMALIZE);
137 table.get_table_values.emplace_back(
138 &sparse_tables::get_sparse_normalization_values<28, choose_normalization_table>);
139 }
140 return table;
141}
142
143inline MultiTable get_majority_output_table(const MultiTableId id = SHA256_MAJ_OUTPUT)
144{
145 const size_t num_entries = 11;
146
147 MultiTable table(numeric::pow64(16, 3), 1 << 3, 0, num_entries);
148
149 table.id = id;
150 for (size_t i = 0; i < num_entries; ++i) {
151 table.slice_sizes.emplace_back(numeric::pow64(16, 3));
152 table.lookup_ids.emplace_back(SHA256_MAJ_NORMALIZE);
153 table.get_table_values.emplace_back(
154 &sparse_tables::get_sparse_normalization_values<16, majority_normalization_table>);
155 }
156 return table;
157}
158
159inline std::array<barretenberg::fr, 3> get_majority_rotation_multipliers()
160{
161 constexpr uint64_t base_temp = 16;
162 auto base = barretenberg::fr(base_temp);
163 // scaling factors applied to a's sparse limbs, excluding the rotated limb
164 const std::array<barretenberg::fr, 3> rot2_coefficients{ 0, base.pow(11 - 2), base.pow(22 - 2) };
165 const std::array<barretenberg::fr, 3> rot13_coefficients{ base.pow(32 - 13), 0, base.pow(22 - 13) };
166 const std::array<barretenberg::fr, 3> rot22_coefficients{ base.pow(32 - 22), base.pow(32 - 22 + 11), 0 };
167
168 // these are the coefficients that we want
169 const std::array<barretenberg::fr, 3> target_rotation_coefficients{
170 rot2_coefficients[0] + rot13_coefficients[0] + rot22_coefficients[0],
171 rot2_coefficients[1] + rot13_coefficients[1] + rot22_coefficients[1],
172 rot2_coefficients[2] + rot13_coefficients[2] + rot22_coefficients[2],
173 };
174
175 barretenberg::fr column_2_row_1_multiplier = target_rotation_coefficients[0];
176 barretenberg::fr column_2_row_2_multiplier =
177 target_rotation_coefficients[0] * (-barretenberg::fr(base).pow(11)) + target_rotation_coefficients[1];
178
179 std::array<barretenberg::fr, 3> rotation_multipliers = { column_2_row_1_multiplier,
180 column_2_row_2_multiplier,
181 barretenberg::fr(0) };
182 return rotation_multipliers;
183}
184
185// template <uint64_t rot_a, uint64_t rot_b, uint64_t rot_c>
186inline std::array<barretenberg::fr, 3> get_choose_rotation_multipliers()
187{
188 const std::array<barretenberg::fr, 3> column_2_row_3_coefficients{
189 barretenberg::fr(1),
190 barretenberg::fr(28).pow(11),
191 barretenberg::fr(28).pow(22),
192 };
193
194 // scaling factors applied to a's sparse limbs, excluding the rotated limb
195 const std::array<barretenberg::fr, 3> rot6_coefficients{ barretenberg::fr(0),
196 barretenberg::fr(28).pow(11 - 6),
197 barretenberg::fr(28).pow(22 - 6) };
198 const std::array<barretenberg::fr, 3> rot11_coefficients{ barretenberg::fr(28).pow(32 - 11),
199 barretenberg::fr(0),
200 barretenberg::fr(28).pow(22 - 11) };
201 const std::array<barretenberg::fr, 3> rot25_coefficients{ barretenberg::fr(28).pow(32 - 25),
202 barretenberg::fr(28).pow(32 - 25 + 11),
203 barretenberg::fr(0) };
204
205 // these are the coefficients that we want
206 const std::array<barretenberg::fr, 3> target_rotation_coefficients{
207 rot6_coefficients[0] + rot11_coefficients[0] + rot25_coefficients[0],
208 rot6_coefficients[1] + rot11_coefficients[1] + rot25_coefficients[1],
209 rot6_coefficients[2] + rot11_coefficients[2] + rot25_coefficients[2],
210 };
211
212 barretenberg::fr column_2_row_1_multiplier =
213 barretenberg::fr(1) * target_rotation_coefficients[0]; // why multiply by one?
214
215 // this gives us the correct scaling factor for a0's 1st limb
216 std::array<barretenberg::fr, 3> current_coefficients{
217 column_2_row_3_coefficients[0] * column_2_row_1_multiplier,
218 column_2_row_3_coefficients[1] * column_2_row_1_multiplier,
219 column_2_row_3_coefficients[2] * column_2_row_1_multiplier,
220 };
221
222 barretenberg::fr column_2_row_3_multiplier = -(current_coefficients[2]) + target_rotation_coefficients[2];
223
224 std::array<barretenberg::fr, 3> rotation_multipliers = { column_2_row_1_multiplier,
225 barretenberg::fr(0),
226 column_2_row_3_multiplier };
227 return rotation_multipliers;
228}
229
230inline MultiTable get_witness_extension_input_table(const MultiTableId id = SHA256_WITNESS_INPUT)
231{
232 std::vector<barretenberg::fr> column_1_coefficients{ 1, 1 << 3, 1 << 10, 1 << 18 };
233 std::vector<barretenberg::fr> column_2_coefficients{ 0, 0, 0, 0 };
234 std::vector<barretenberg::fr> column_3_coefficients{ 0, 0, 0, 0 };
235 MultiTable table(column_1_coefficients, column_2_coefficients, column_3_coefficients);
236 table.id = id;
237 table.slice_sizes = { (1 << 3), (1 << 7), (1 << 8), (1 << 18) };
238 table.lookup_ids = { SHA256_WITNESS_SLICE_3,
239 SHA256_WITNESS_SLICE_7_ROTATE_4,
240 SHA256_WITNESS_SLICE_8_ROTATE_7,
241 SHA256_WITNESS_SLICE_14_ROTATE_1 };
242
243 table.get_table_values = {
244 &sparse_tables::get_sparse_table_with_rotation_values<16, 0>,
245 &sparse_tables::get_sparse_table_with_rotation_values<16, 4>,
246 &sparse_tables::get_sparse_table_with_rotation_values<16, 7>,
247 &sparse_tables::get_sparse_table_with_rotation_values<16, 1>,
248 };
249 return table;
250}
251
252inline MultiTable get_choose_input_table(const MultiTableId id = SHA256_CH_INPUT)
253{
306 // scaling factors applied to a's sparse limbs, excluding the rotated limb
307 const std::array<barretenberg::fr, 3> rot6_coefficients{ barretenberg::fr(0),
308 barretenberg::fr(28).pow(11 - 6),
309 barretenberg::fr(28).pow(22 - 6) };
310 const std::array<barretenberg::fr, 3> rot11_coefficients{ barretenberg::fr(28).pow(32 - 11),
311 barretenberg::fr(0),
312 barretenberg::fr(28).pow(22 - 11) };
313 const std::array<barretenberg::fr, 3> rot25_coefficients{ barretenberg::fr(28).pow(32 - 25),
314 barretenberg::fr(28).pow(32 - 25 + 11),
315 barretenberg::fr(0) };
316
317 // these are the coefficients that we want
318 const std::array<barretenberg::fr, 3> target_rotation_coefficients{
319 rot6_coefficients[0] + rot11_coefficients[0] + rot25_coefficients[0],
320 rot6_coefficients[1] + rot11_coefficients[1] + rot25_coefficients[1],
321 rot6_coefficients[2] + rot11_coefficients[2] + rot25_coefficients[2],
322 };
323
324 barretenberg::fr column_2_row_1_multiplier = target_rotation_coefficients[0];
325
326 // this gives us the correct scaling factor for a0's 1st limb
327 std::array<barretenberg::fr, 3> current_coefficients{
328 column_2_row_1_multiplier,
329 barretenberg::fr(28).pow(11) * column_2_row_1_multiplier,
330 barretenberg::fr(28).pow(22) * column_2_row_1_multiplier,
331 };
332
333 // barretenberg::fr column_2_row_3_multiplier = -(current_coefficients[2]) + target_rotation_coefficients[2];
334 barretenberg::fr column_3_row_2_multiplier = -(current_coefficients[1]) + target_rotation_coefficients[1];
335
336 std::vector<barretenberg::fr> column_1_coefficients{ barretenberg::fr(1),
337 barretenberg::fr(1 << 11),
338 barretenberg::fr(1 << 22) };
339 std::vector<barretenberg::fr> column_2_coefficients{ barretenberg::fr(1),
340 barretenberg::fr(28).pow(11),
341 barretenberg::fr(28).pow(22) };
342 std::vector<barretenberg::fr> column_3_coefficients{ barretenberg::fr(1),
343 column_3_row_2_multiplier + barretenberg::fr(1),
344 barretenberg::fr(1) };
345 MultiTable table(column_1_coefficients, column_2_coefficients, column_3_coefficients);
346 table.id = id;
347 table.slice_sizes = { (1 << 11), (1 << 11), (1 << 10) };
348 table.lookup_ids = { SHA256_BASE28_ROTATE6, SHA256_BASE28, SHA256_BASE28_ROTATE3 };
349
350 table.get_table_values.push_back(&sparse_tables::get_sparse_table_with_rotation_values<28, 6>);
351 table.get_table_values.push_back(&sparse_tables::get_sparse_table_with_rotation_values<28, 0>);
352 table.get_table_values.push_back(&sparse_tables::get_sparse_table_with_rotation_values<28, 3>);
353 // table.get_table_values = std::vector<MultiTable::table_out (*)(MultiTable::table_in)>{
354
355 // &get_sha256_sparse_map_values<28, 0, 0>,
356 // &get_sha256_sparse_map_values<28, 3, 0>,
357 // };
358 return table;
359}
360
361// This table (at third row and column) returns the sum of roations that "non-trivially wrap"
362inline MultiTable get_majority_input_table(const MultiTableId id = SHA256_MAJ_INPUT)
363{
381 constexpr uint64_t base = 16;
382
383 // scaling factors applied to a's sparse limbs, excluding the rotated limb
384 const std::array<barretenberg::fr, 3> rot2_coefficients{ barretenberg::fr(0),
385 barretenberg::fr(base).pow(11 - 2),
386 barretenberg::fr(base).pow(22 - 2) };
387 const std::array<barretenberg::fr, 3> rot13_coefficients{ barretenberg::fr(base).pow(32 - 13),
388 barretenberg::fr(0),
389 barretenberg::fr(base).pow(22 - 13) };
390 const std::array<barretenberg::fr, 3> rot22_coefficients{ barretenberg::fr(base).pow(32 - 22),
391 barretenberg::fr(base).pow(32 - 22 + 11),
392 barretenberg::fr(0) };
393
394 // these are the coefficients that we want
395 const std::array<barretenberg::fr, 3> target_rotation_coefficients{
396 rot2_coefficients[0] + rot13_coefficients[0] + rot22_coefficients[0],
397 rot2_coefficients[1] + rot13_coefficients[1] + rot22_coefficients[1],
398 rot2_coefficients[2] + rot13_coefficients[2] + rot22_coefficients[2],
399 };
400
401 barretenberg::fr column_2_row_3_multiplier =
402 target_rotation_coefficients[1] * (-barretenberg::fr(base).pow(11)) + target_rotation_coefficients[2];
403
404 std::vector<barretenberg::fr> column_1_coefficients{ barretenberg::fr(1),
405 barretenberg::fr(1 << 11),
406 barretenberg::fr(1 << 22) };
407 std::vector<barretenberg::fr> column_2_coefficients{ barretenberg::fr(1),
408 barretenberg::fr(base).pow(11),
409 barretenberg::fr(base).pow(22) };
410 std::vector<barretenberg::fr> column_3_coefficients{ barretenberg::fr(1),
411 barretenberg::fr(1),
412 barretenberg::fr(1) + column_2_row_3_multiplier };
413
414 MultiTable table(column_1_coefficients, column_2_coefficients, column_3_coefficients);
415 table.id = id;
416 table.slice_sizes = { (1 << 11), (1 << 11), (1 << 10) };
417 table.lookup_ids = { SHA256_BASE16_ROTATE2, SHA256_BASE16_ROTATE2, SHA256_BASE16 };
418 table.get_table_values = {
419 &sparse_tables::get_sparse_table_with_rotation_values<16, 2>,
420 &sparse_tables::get_sparse_table_with_rotation_values<16, 2>,
421 &sparse_tables::get_sparse_table_with_rotation_values<16, 0>,
422 };
423 return table;
424}
425
426} // namespace sha256_tables
427} // namespace plookup
Generated by doxygen 1.9.6