Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
plookup.test.cpp
Go to the documentation of this file.
1#include "plookup.hpp"
2#include "barretenberg/circuit_checker/circuit_checker.hpp"
3#include "barretenberg/numeric/bitop/rotate.hpp"
4#include "barretenberg/numeric/bitop/sparse_form.hpp"
5#include "barretenberg/numeric/random/engine.hpp"
6#include "barretenberg/stdlib/primitives/bigfield/bigfield.hpp"
7#include "barretenberg/stdlib/primitives/biggroup/biggroup.hpp"
8#include "barretenberg/stdlib/primitives/circuit_builders/circuit_builders.hpp"
9#include "barretenberg/stdlib/primitives/curves/secp256k1.hpp"
10#include <gtest/gtest.h>
11
12using namespace bb;
13using namespace bb::plookup;
14
15// Defining ultra-specific types for local testing.
16using Builder = UltraCircuitBuilder;
17using field_ct = stdlib::field_t<Builder>;
18using witness_ct = stdlib::witness_t<Builder>;
19using plookup_read = stdlib::plookup_read<Builder>;
20namespace {
21auto& engine = numeric::get_debug_randomness();
22}
23
24// TODO(https://github.com/AztecProtocol/barretenberg/issues/953): Re-enable these tests
25// TEST(stdlib_plookup, pedersen_lookup_left)
26// {
27// Builder builder = Builder();
28
29// fr input_value = fr::random_element();
30// field_ct input_hi = witness_ct(&builder, uint256_t(input_value).slice(126, 256));
31// field_ct input_lo = witness_ct(&builder, uint256_t(input_value).slice(0, 126));
32
33// const auto lookup_hi = plookup_read::get_lookup_accumulators(MultiTableId::PEDERSEN_LEFT_HI, input_hi);
34// const auto lookup_lo = plookup_read::get_lookup_accumulators(MultiTableId::PEDERSEN_LEFT_LO, input_lo);
35
36// std::vector<fr> expected_x;
37// std::vector<fr> expected_y;
38
39// const size_t num_lookups_hi =
40// (128 + crypto::pedersen_hash::lookup::BITS_PER_TABLE) / crypto::pedersen_hash::lookup::BITS_PER_TABLE;
41// const size_t num_lookups_lo = 126 / crypto::pedersen_hash::lookup::BITS_PER_TABLE;
42
43// EXPECT_EQ(num_lookups_hi, lookup_hi[ColumnIdx::C1].size());
44// EXPECT_EQ(num_lookups_lo, lookup_lo[ColumnIdx::C1].size());
45
46// const size_t num_lookups = num_lookups_hi + num_lookups_lo;
47// std::vector<fr> expected_scalars;
48// expected_x.resize(num_lookups);
49// expected_y.resize(num_lookups);
50// expected_scalars.resize(num_lookups);
51
52// {
53// const size_t num_rounds = (num_lookups + 1) / 2;
54// uint256_t bits(input_value);
55
56// const auto mask = crypto::pedersen_hash::lookup::PEDERSEN_TABLE_SIZE - 1;
57
58// for (size_t i = 0; i < num_rounds; ++i) {
59// const auto& table = crypto::pedersen_hash::lookup::get_table(i);
60// const size_t index = i * 2;
61
62// size_t slice_a =
63// static_cast<size_t>(((bits >> (index * crypto::pedersen_hash::lookup::BITS_PER_TABLE)) &
64// mask).data[0]);
65// expected_x[index] = (table[slice_a].x);
66// expected_y[index] = (table[slice_a].y);
67// expected_scalars[index] = slice_a;
68
69// if (i < 14) {
70// size_t slice_b = static_cast<size_t>(
71// ((bits >> ((index + 1) * crypto::pedersen_hash::lookup::BITS_PER_TABLE)) & mask).data[0]);
72// expected_x[index + 1] = (table[slice_b].x);
73// expected_y[index + 1] = (table[slice_b].y);
74// expected_scalars[index + 1] = slice_b;
75// }
76// }
77// }
78
79// for (size_t i = num_lookups - 2; i < num_lookups; --i) {
80// expected_scalars[i] += (expected_scalars[i + 1] * crypto::pedersen_hash::lookup::PEDERSEN_TABLE_SIZE);
81// }
82// size_t hi_shift = 126;
83// const fr hi_cumulative = lookup_hi[ColumnIdx::C1][0].get_value();
84// for (size_t i = 0; i < num_lookups_lo; ++i) {
85// const fr hi_mult = fr(uint256_t(1) << hi_shift);
86// EXPECT_EQ(lookup_lo[ColumnIdx::C1][i].get_value() + (hi_cumulative * hi_mult), expected_scalars[i]);
87// EXPECT_EQ(lookup_lo[ColumnIdx::C2][i].get_value(), expected_x[i]);
88// EXPECT_EQ(lookup_lo[ColumnIdx::C3][i].get_value(), expected_y[i]);
89// hi_shift -= crypto::pedersen_hash::lookup::BITS_PER_TABLE;
90// }
91// for (size_t i = 0; i < num_lookups_hi; ++i) {
92// EXPECT_EQ(lookup_hi[ColumnIdx::C1][i].get_value(), expected_scalars[i + num_lookups_lo]);
93// EXPECT_EQ(lookup_hi[ColumnIdx::C2][i].get_value(), expected_x[i + num_lookups_lo]);
94// EXPECT_EQ(lookup_hi[ColumnIdx::C3][i].get_value(), expected_y[i + num_lookups_lo]);
95// }
96
97// bool result = CircuitChecker::check(builder);
98
99// EXPECT_EQ(result, true);
100// }
101
102// TEST(stdlib_plookup, pedersen_lookup_right)
103// {
104// Builder builder = Builder();
105
106// fr input_value = fr::random_element();
107// field_ct input_hi = witness_ct(&builder, uint256_t(input_value).slice(126, 256));
108// field_ct input_lo = witness_ct(&builder, uint256_t(input_value).slice(0, 126));
109
110// const auto lookup_hi = plookup_read::get_lookup_accumulators(MultiTableId::PEDERSEN_RIGHT_HI, input_hi);
111// const auto lookup_lo = plookup_read::get_lookup_accumulators(MultiTableId::PEDERSEN_RIGHT_LO, input_lo);
112
113// std::vector<fr> expected_x;
114// std::vector<fr> expected_y;
115
116// const size_t num_lookups_hi =
117// (128 + crypto::pedersen_hash::lookup::BITS_PER_TABLE) / crypto::pedersen_hash::lookup::BITS_PER_TABLE;
118// const size_t num_lookups_lo = 126 / crypto::pedersen_hash::lookup::BITS_PER_TABLE;
119
120// EXPECT_EQ(num_lookups_hi, lookup_hi[ColumnIdx::C1].size());
121// EXPECT_EQ(num_lookups_lo, lookup_lo[ColumnIdx::C1].size());
122
123// const size_t num_lookups = num_lookups_hi + num_lookups_lo;
124// std::vector<fr> expected_scalars;
125// expected_x.resize(num_lookups);
126// expected_y.resize(num_lookups);
127// expected_scalars.resize(num_lookups);
128
129// {
130// const size_t num_rounds = (num_lookups + 1) / 2;
131// uint256_t bits(input_value);
132
133// const auto mask = crypto::pedersen_hash::lookup::PEDERSEN_TABLE_SIZE - 1;
134
135// for (size_t i = 0; i < num_rounds; ++i) {
136// const auto& table = crypto::pedersen_hash::lookup::get_table(i + num_rounds);
137// const size_t index = i * 2;
138
139// size_t slice_a =
140// static_cast<size_t>(((bits >> (index * crypto::pedersen_hash::lookup::BITS_PER_TABLE)) &
141// mask).data[0]);
142// expected_x[index] = (table[slice_a].x);
143// expected_y[index] = (table[slice_a].y);
144// expected_scalars[index] = slice_a;
145
146// if (i < 14) {
147// size_t slice_b = static_cast<size_t>(
148// ((bits >> ((index + 1) * crypto::pedersen_hash::lookup::BITS_PER_TABLE)) & mask).data[0]);
149// expected_x[index + 1] = (table[slice_b].x);
150// expected_y[index + 1] = (table[slice_b].y);
151// expected_scalars[index + 1] = slice_b;
152// }
153// }
154// }
155
156// for (size_t i = num_lookups - 2; i < num_lookups; --i) {
157// expected_scalars[i] += (expected_scalars[i + 1] * crypto::pedersen_hash::lookup::PEDERSEN_TABLE_SIZE);
158// }
159// size_t hi_shift = 126;
160// const fr hi_cumulative = lookup_hi[ColumnIdx::C1][0].get_value();
161// for (size_t i = 0; i < num_lookups_lo; ++i) {
162// const fr hi_mult = fr(uint256_t(1) << hi_shift);
163// EXPECT_EQ(lookup_lo[ColumnIdx::C1][i].get_value() + (hi_cumulative * hi_mult), expected_scalars[i]);
164// EXPECT_EQ(lookup_lo[ColumnIdx::C2][i].get_value(), expected_x[i]);
165// EXPECT_EQ(lookup_lo[ColumnIdx::C3][i].get_value(), expected_y[i]);
166// hi_shift -= crypto::pedersen_hash::lookup::BITS_PER_TABLE;
167// }
168// for (size_t i = 0; i < num_lookups_hi; ++i) {
169// EXPECT_EQ(lookup_hi[ColumnIdx::C1][i].get_value(), expected_scalars[i + num_lookups_lo]);
170// EXPECT_EQ(lookup_hi[ColumnIdx::C2][i].get_value(), expected_x[i + num_lookups_lo]);
171// EXPECT_EQ(lookup_hi[ColumnIdx::C3][i].get_value(), expected_y[i + num_lookups_lo]);
172// }
173
174// bool result = CircuitChecker::check(builder);
175
176// EXPECT_EQ(result, true);
177// }
178
179TEST(stdlib_plookup, uint32_xor)
180{
181 Builder builder = Builder();
182
183 const size_t num_lookups = (32 + 5) / 6;
184
185 uint256_t left_value = (engine.get_random_uint256() & 0xffffffffULL);
186 uint256_t right_value = (engine.get_random_uint256() & 0xffffffffULL);
187
188 field_ct left = witness_ct(&builder, bb::fr(left_value));
189 field_ct right = witness_ct(&builder, bb::fr(right_value));
190
191 const auto lookup = plookup_read::get_lookup_accumulators(MultiTableId::UINT32_XOR, left, right, true);
192
193 const auto left_slices = numeric::slice_input(left_value, 1 << 6, num_lookups);
194 const auto right_slices = numeric::slice_input(right_value, 1 << 6, num_lookups);
195
196 std::vector<uint256_t> out_expected(num_lookups);
197 std::vector<uint256_t> left_expected(num_lookups);
198 std::vector<uint256_t> right_expected(num_lookups);
199
200 for (size_t i = 0; i < left_slices.size(); ++i) {
201 out_expected[i] = left_slices[i] ^ right_slices[i];
202 left_expected[i] = left_slices[i];
203 right_expected[i] = right_slices[i];
204 }
205
206 for (size_t i = num_lookups - 2; i < num_lookups; --i) {
207 out_expected[i] += out_expected[i + 1] * (1 << 6);
208 left_expected[i] += left_expected[i + 1] * (1 << 6);
209 right_expected[i] += right_expected[i + 1] * (1 << 6);
210 }
211
212 for (size_t i = 0; i < num_lookups; ++i) {
213 EXPECT_EQ(lookup[ColumnIdx::C1][i].get_value(), bb::fr(left_expected[i]));
214 EXPECT_EQ(lookup[ColumnIdx::C2][i].get_value(), bb::fr(right_expected[i]));
215 EXPECT_EQ(lookup[ColumnIdx::C3][i].get_value(), bb::fr(out_expected[i]));
216 }
217
218 bool result = CircuitChecker::check(builder);
219
220 EXPECT_EQ(result, true);
221}
222
223TEST(stdlib_plookup, blake2s_xor_rotate_16)
224{
225 Builder builder = Builder();
226
227 const size_t num_lookups = 6;
228
229 uint256_t left_value = (engine.get_random_uint256() & 0xffffffffULL);
230 uint256_t right_value = (engine.get_random_uint256() & 0xffffffffULL);
231
232 field_ct left = witness_ct(&builder, bb::fr(left_value));
233 field_ct right = witness_ct(&builder, bb::fr(right_value));
234
235 const auto lookup = plookup_read::get_lookup_accumulators(MultiTableId::BLAKE_XOR_ROTATE_16, left, right, true);
236
237 const auto left_slices = numeric::slice_input(left_value, 1 << 6, num_lookups);
238 const auto right_slices = numeric::slice_input(right_value, 1 << 6, num_lookups);
239
240 std::vector<fr> out_expected(num_lookups);
241 std::vector<fr> left_expected(num_lookups);
242 std::vector<fr> right_expected(num_lookups);
243
244 for (size_t i = 0; i < left_slices.size(); ++i) {
245 if (i == 2) {
246 uint32_t a = static_cast<uint32_t>(left_slices[i]);
247 uint32_t b = static_cast<uint32_t>(right_slices[i]);
248 uint32_t c = numeric::rotate32(a ^ b, 4);
249 out_expected[i] = uint256_t(c);
250 } else {
251 out_expected[i] = uint256_t(left_slices[i]) ^ uint256_t(right_slices[i]);
252 }
253 left_expected[i] = left_slices[i];
254 right_expected[i] = right_slices[i];
255 }
256
257 /*
258 * The following out coefficients are the ones multiplied for computing the cumulative intermediate terms
259 * in the expected output. If the column_3_coefficients for this table are (a0, a1, ..., a5), then the
260 * out_coefficients must be (a5/a4, a4/a3, a3/a2, a2/a1, a1/a0). Note that these are stored in reverse orde
261 * for simplicity.
262 */
263 std::vector<fr> out_coefficients{ (1 << 6), (bb::fr(1) / bb::fr(1 << 22)), (1 << 2), (1 << 6), (1 << 6) };
264
265 for (size_t i = num_lookups - 2; i < num_lookups; --i) {
266 out_expected[i] += out_expected[i + 1] * out_coefficients[i];
267 left_expected[i] += left_expected[i + 1] * (1 << 6);
268 right_expected[i] += right_expected[i + 1] * (1 << 6);
269 }
270
271 for (size_t i = 0; i < num_lookups; ++i) {
272 EXPECT_EQ(lookup[ColumnIdx::C1][i].get_value(), left_expected[i]);
273 EXPECT_EQ(lookup[ColumnIdx::C2][i].get_value(), right_expected[i]);
274 EXPECT_EQ(lookup[ColumnIdx::C3][i].get_value(), out_expected[i]);
275 }
276
277 /*
278 * Note that we multiply the output of the lookup table (lookup[Column::Idx}0]) by 2^{16} because
279 * while defining the table we had set the coefficient of s0 to 1, so to correct that, we need to multiply by a
280 * constant.
281 */
282 auto mul_constant = fr(1 << 16);
283 fr lookup_output = lookup[ColumnIdx::C3][0].get_value() * mul_constant;
284 uint32_t xor_rotate_output = numeric::rotate32(uint32_t(left_value) ^ uint32_t(right_value), 16);
285 EXPECT_EQ(fr(uint256_t(xor_rotate_output)), lookup_output);
286
287 bool result = CircuitChecker::check(builder);
288
289 EXPECT_EQ(result, true);
290}
291
292TEST(stdlib_plookup, blake2s_xor_rotate_8)
293{
294 Builder builder = Builder();
295
296 const size_t num_lookups = 6;
297
298 uint256_t left_value = (engine.get_random_uint256() & 0xffffffffULL);
299 uint256_t right_value = (engine.get_random_uint256() & 0xffffffffULL);
300
301 field_ct left = witness_ct(&builder, bb::fr(left_value));
302 field_ct right = witness_ct(&builder, bb::fr(right_value));
303
304 const auto lookup = plookup_read::get_lookup_accumulators(MultiTableId::BLAKE_XOR_ROTATE_8, left, right, true);
305
306 const auto left_slices = numeric::slice_input(left_value, 1 << 6, num_lookups);
307 const auto right_slices = numeric::slice_input(right_value, 1 << 6, num_lookups);
308
309 std::vector<fr> out_expected(num_lookups);
310 std::vector<fr> left_expected(num_lookups);
311 std::vector<fr> right_expected(num_lookups);
312
313 for (size_t i = 0; i < left_slices.size(); ++i) {
314 if (i == 1) {
315 uint32_t a = static_cast<uint32_t>(left_slices[i]);
316 uint32_t b = static_cast<uint32_t>(right_slices[i]);
317 uint32_t c = numeric::rotate32(a ^ b, 2);
318 out_expected[i] = uint256_t(c);
319 } else {
320 out_expected[i] = uint256_t(left_slices[i]) ^ uint256_t(right_slices[i]);
321 }
322 left_expected[i] = left_slices[i];
323 right_expected[i] = right_slices[i];
324 }
325
326 auto mul_constant = fr(1 << 24);
327 std::vector<fr> out_coefficients{ (bb::fr(1) / mul_constant), (1 << 4), (1 << 6), (1 << 6), (1 << 6) };
328
329 for (size_t i = num_lookups - 2; i < num_lookups; --i) {
330 out_expected[i] += out_expected[i + 1] * out_coefficients[i];
331 left_expected[i] += left_expected[i + 1] * (1 << 6);
332 right_expected[i] += right_expected[i + 1] * (1 << 6);
333 }
334
335 for (size_t i = 0; i < num_lookups; ++i) {
336 EXPECT_EQ(lookup[ColumnIdx::C1][i].get_value(), left_expected[i]);
337 EXPECT_EQ(lookup[ColumnIdx::C2][i].get_value(), right_expected[i]);
338 EXPECT_EQ(lookup[ColumnIdx::C3][i].get_value(), out_expected[i]);
339 }
340
341 fr lookup_output = lookup[ColumnIdx::C3][0].get_value() * mul_constant;
342 uint32_t xor_rotate_output = numeric::rotate32(uint32_t(left_value) ^ uint32_t(right_value), 8);
343 EXPECT_EQ(fr(uint256_t(xor_rotate_output)), lookup_output);
344
345 bool result = CircuitChecker::check(builder);
346
347 EXPECT_EQ(result, true);
348}
349
350TEST(stdlib_plookup, blake2s_xor_rotate_7)
351{
352 Builder builder = Builder();
353
354 const size_t num_lookups = 6;
355
356 uint256_t left_value = (engine.get_random_uint256() & 0xffffffffULL);
357 uint256_t right_value = (engine.get_random_uint256() & 0xffffffffULL);
358
359 field_ct left = witness_ct(&builder, bb::fr(left_value));
360 field_ct right = witness_ct(&builder, bb::fr(right_value));
361
362 const auto lookup = plookup_read::get_lookup_accumulators(MultiTableId::BLAKE_XOR_ROTATE_7, left, right, true);
363
364 const auto left_slices = numeric::slice_input(left_value, 1 << 6, num_lookups);
365 const auto right_slices = numeric::slice_input(right_value, 1 << 6, num_lookups);
366
367 std::vector<fr> out_expected(num_lookups);
368 std::vector<fr> left_expected(num_lookups);
369 std::vector<fr> right_expected(num_lookups);
370
371 for (size_t i = 0; i < left_slices.size(); ++i) {
372 if (i == 1) {
373 uint32_t a = static_cast<uint32_t>(left_slices[i]);
374 uint32_t b = static_cast<uint32_t>(right_slices[i]);
375 uint32_t c = numeric::rotate32(a ^ b, 1);
376 out_expected[i] = uint256_t(c);
377 } else {
378 out_expected[i] = uint256_t(left_slices[i]) ^ uint256_t(right_slices[i]);
379 }
380 left_expected[i] = left_slices[i];
381 right_expected[i] = right_slices[i];
382 }
383
384 auto mul_constant = fr(1 << 25);
385 std::vector<fr> out_coefficients{ (bb::fr(1) / mul_constant), (1 << 5), (1 << 6), (1 << 6), (1 << 6) };
386
387 for (size_t i = num_lookups - 2; i < num_lookups; --i) {
388 out_expected[i] += out_expected[i + 1] * out_coefficients[i];
389 left_expected[i] += left_expected[i + 1] * (1 << 6);
390 right_expected[i] += right_expected[i + 1] * (1 << 6);
391 }
392
393 for (size_t i = 0; i < num_lookups; ++i) {
394 EXPECT_EQ(lookup[ColumnIdx::C1][i].get_value(), left_expected[i]);
395 EXPECT_EQ(lookup[ColumnIdx::C2][i].get_value(), right_expected[i]);
396 EXPECT_EQ(lookup[ColumnIdx::C3][i].get_value(), out_expected[i]);
397 }
398
399 fr lookup_output = lookup[ColumnIdx::C3][0].get_value() * mul_constant;
400 uint32_t xor_rotate_output = numeric::rotate32(uint32_t(left_value) ^ uint32_t(right_value), 7);
401 EXPECT_EQ(fr(uint256_t(xor_rotate_output)), lookup_output);
402
403 bool result = CircuitChecker::check(builder);
404
405 EXPECT_EQ(result, true);
406}
407
408TEST(stdlib_plookup, blake2s_xor)
409{
410 Builder builder = Builder();
411
412 const size_t num_lookups = 6;
413
414 uint256_t left_value = (engine.get_random_uint256() & 0xffffffffULL);
415 uint256_t right_value = (engine.get_random_uint256() & 0xffffffffULL);
416
417 field_ct left = witness_ct(&builder, bb::fr(left_value));
418 field_ct right = witness_ct(&builder, bb::fr(right_value));
419
420 const auto lookup = plookup_read::get_lookup_accumulators(MultiTableId::BLAKE_XOR, left, right, true);
421
422 const auto left_slices = numeric::slice_input(left_value, 1 << 6, num_lookups);
423 const auto right_slices = numeric::slice_input(right_value, 1 << 6, num_lookups);
424
425 std::vector<uint256_t> out_expected(num_lookups);
426 std::vector<uint256_t> left_expected(num_lookups);
427 std::vector<uint256_t> right_expected(num_lookups);
428
429 for (size_t i = 0; i < left_slices.size(); ++i) {
430 out_expected[i] = left_slices[i] ^ right_slices[i];
431 left_expected[i] = left_slices[i];
432 right_expected[i] = right_slices[i];
433 }
434
435 // Compute ror(a ^ b, 12) from lookup table.
436 // t0 = 2^30 a5 + 2^24 a4 + 2^18 a3 + 2^12 a2 + 2^6 a1 + a0
437 // t1 = 2^24 a5 + 2^18 a4 + 2^12 a3 + 2^6 a2 + a1
438 // t2 = 2^18 a5 + 2^12 a4 + 2^6 a3 + a2
439 // t3 = 2^12 a5 + 2^6 a4 + a3
440 // t4 = 2^6 a5 + a4
441 // t5 = a5
442 //
443 // output = (t0 - 2^12 t2) * 2^{32 - 12} + t2
444 fr lookup_output = lookup[ColumnIdx::C3][2].get_value();
445 fr t2_term = fr(1 << 12) * lookup[ColumnIdx::C3][2].get_value();
446 lookup_output += fr(1 << 20) * (lookup[ColumnIdx::C3][0].get_value() - t2_term);
447
448 for (size_t i = num_lookups - 2; i < num_lookups; --i) {
449 out_expected[i] += out_expected[i + 1] * (1 << 6);
450 left_expected[i] += left_expected[i + 1] * (1 << 6);
451 right_expected[i] += right_expected[i + 1] * (1 << 6);
452 }
453
454 //
455 // The following checks if the xor output rotated by 12 can be computed correctly from basic blake2s_xor.
456 //
457 auto xor_rotate_output = numeric::rotate32(uint32_t(left_value) ^ uint32_t(right_value), 12);
458 EXPECT_EQ(fr(uint256_t(xor_rotate_output)), lookup_output);
459
460 for (size_t i = 0; i < num_lookups; ++i) {
461 EXPECT_EQ(lookup[ColumnIdx::C1][i].get_value(), bb::fr(left_expected[i]));
462 EXPECT_EQ(lookup[ColumnIdx::C2][i].get_value(), bb::fr(right_expected[i]));
463 EXPECT_EQ(lookup[ColumnIdx::C3][i].get_value(), bb::fr(out_expected[i]));
464 }
465
466 bool result = CircuitChecker::check(builder);
467
468 EXPECT_EQ(result, true);
469}
470
471TEST(stdlib_plookup, uint32_and)
472{
473 Builder builder = Builder();
474
475 const size_t num_lookups = (32 + 5) / 6;
476
477 uint256_t left_value = (engine.get_random_uint256() & 0xffffffffULL);
478 uint256_t right_value = (engine.get_random_uint256() & 0xffffffffULL);
479
480 field_ct left = witness_ct(&builder, bb::fr(left_value));
481 field_ct right = witness_ct(&builder, bb::fr(right_value));
482
483 const auto lookup = plookup_read::get_lookup_accumulators(MultiTableId::UINT32_AND, left, right, true);
484 const auto left_slices = numeric::slice_input(left_value, 1 << 6, num_lookups);
485 const auto right_slices = numeric::slice_input(right_value, 1 << 6, num_lookups);
486 std::vector<uint256_t> out_expected(num_lookups);
487 std::vector<uint256_t> left_expected(num_lookups);
488 std::vector<uint256_t> right_expected(num_lookups);
489
490 for (size_t i = 0; i < left_slices.size(); ++i) {
491 out_expected[i] = left_slices[i] & right_slices[i];
492 left_expected[i] = left_slices[i];
493 right_expected[i] = right_slices[i];
494 }
495
496 for (size_t i = num_lookups - 2; i < num_lookups; --i) {
497 out_expected[i] += out_expected[i + 1] * (1 << 6);
498 left_expected[i] += left_expected[i + 1] * (1 << 6);
499 right_expected[i] += right_expected[i + 1] * (1 << 6);
500 }
501
502 for (size_t i = 0; i < num_lookups; ++i) {
503 EXPECT_EQ(lookup[ColumnIdx::C1][i].get_value(), bb::fr(left_expected[i]));
504 EXPECT_EQ(lookup[ColumnIdx::C2][i].get_value(), bb::fr(right_expected[i]));
505 EXPECT_EQ(lookup[ColumnIdx::C3][i].get_value(), bb::fr(out_expected[i]));
506 }
507
508 bool result = CircuitChecker::check(builder);
509
510 EXPECT_EQ(result, true);
511}
512
513TEST(stdlib_plookup, secp256k1_generator)
514{
515 using curve = stdlib::secp256k1<Builder>;
516 Builder builder = Builder();
517
518 uint256_t input_value = (engine.get_random_uint256() >> 128);
519
520 uint64_t wnaf_entries[18] = { 0 };
521 bool skew = false;
522 wnaf::fixed_wnaf<129, 1, 8>(&input_value.data[0], &wnaf_entries[0], skew, 0);
523
524 std::vector<uint64_t> naf_values;
525 for (size_t i = 0; i < 17; ++i) {
526 bool predicate = bool((wnaf_entries[i] >> 31U) & 1U);
527 uint64_t offset_entry;
528 if (predicate) {
529 offset_entry = (127 - (wnaf_entries[i] & 0xffffff));
530 } else {
531 offset_entry = (128 + (wnaf_entries[i] & 0xffffff));
532 }
533 naf_values.emplace_back(offset_entry);
534 }
535
536 std::vector<field_ct> circuit_naf_values;
537 for (size_t i = 0; i < naf_values.size(); ++i) {
538 circuit_naf_values.emplace_back(witness_ct(&builder, naf_values[i]));
539 }
540
541 std::vector<field_ct> accumulators;
542 for (size_t i = 0; i < naf_values.size(); ++i) {
543 field_ct t1 = (circuit_naf_values[naf_values.size() - 1 - i]) * field_ct(uint256_t(1) << (i * 8 + 1));
544 field_ct t2 = field_ct(255) * field_ct(uint256_t(1) << (i * 8));
545 accumulators.emplace_back(t1 - t2);
546 }
547 field_ct accumulator_field = field_ct::accumulate(accumulators);
548 EXPECT_EQ(accumulator_field.get_value(), bb::fr(input_value) + bb::fr(skew));
549
550 for (size_t i = 0; i < 256; ++i) {
551 field_ct index(witness_ct(&builder, bb::fr(i)));
552 const auto xlo = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_XLO, index);
553 const auto xhi = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_XHI, index);
554 const auto ylo = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_YLO, index);
555 const auto yhi = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_YHI, index);
556 curve::fq_ct x = curve::fq_ct::unsafe_construct_from_limbs(xlo.first, xlo.second, xhi.first, xhi.second);
557 curve::fq_ct y = curve::fq_ct::unsafe_construct_from_limbs(ylo.first, ylo.second, yhi.first, yhi.second);
558
559 const auto res = curve::g1_ct(x, y).get_value();
560 curve::fr scalar(i);
561 scalar = scalar + scalar;
562 scalar = scalar - 255;
563 curve::g1::affine_element expec(curve::g1::one * scalar);
564
565 EXPECT_EQ(res, expec);
566 }
567 curve::g1_ct accumulator;
568 {
569 const auto xlo = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_XLO, circuit_naf_values[0]);
570 const auto xhi = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_XHI, circuit_naf_values[0]);
571 const auto ylo = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_YLO, circuit_naf_values[0]);
572 const auto yhi = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_YHI, circuit_naf_values[0]);
573
574 curve::fq_ct x = curve::fq_ct::unsafe_construct_from_limbs(xlo.first, xlo.second, xhi.first, xhi.second);
575 curve::fq_ct y = curve::fq_ct::unsafe_construct_from_limbs(ylo.first, ylo.second, yhi.first, yhi.second);
576 accumulator = curve::g1_ct(x, y);
577 }
578 for (size_t i = 1; i < circuit_naf_values.size(); ++i) {
579 accumulator = accumulator.dbl();
580 accumulator = accumulator.dbl();
581 accumulator = accumulator.dbl();
582 accumulator = accumulator.dbl();
583 accumulator = accumulator.dbl();
584 accumulator = accumulator.dbl();
585 accumulator = accumulator.dbl();
586
587 const auto xlo = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_XLO, circuit_naf_values[i]);
588 const auto xhi = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_XHI, circuit_naf_values[i]);
589 const auto ylo = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_YLO, circuit_naf_values[i]);
590 const auto yhi = plookup_read::read_pair_from_table(MultiTableId::SECP256K1_YHI, circuit_naf_values[i]);
591 curve::fq_ct x = curve::fq_ct::unsafe_construct_from_limbs(xlo.first, xlo.second, xhi.first, xhi.second);
592 curve::fq_ct y = curve::fq_ct::unsafe_construct_from_limbs(ylo.first, ylo.second, yhi.first, yhi.second);
593 accumulator = accumulator.montgomery_ladder(curve::g1_ct(x, y));
594 }
595
596 if (skew) {
597 accumulator = accumulator - curve::g1_ct::one(&builder);
598 }
599
600 curve::g1::affine_element result = accumulator.get_value();
601 curve::g1::affine_element expected(curve::g1::one * input_value);
602 EXPECT_EQ(result, expected);
603
604 bool proof_result = CircuitChecker::check(builder);
605 EXPECT_EQ(proof_result, true);
606}
circuit_builders.hpp
circuit_checker.hpp
bb::TranslatorCircuitChecker::check
static bool check(const Builder &circuit)
Check the witness satisifies the circuit.
Definition translator_circuit_checker.cpp:20
bb::group_elements::affine_element
Definition affine_element.hpp:21
bb::group::one
static constexpr element one
Definition group.hpp:46
bb::numeric::RNG::get_random_uint256
virtual uint256_t get_random_uint256()=0
bb::numeric::uint256_t
Definition uint256.hpp:32
bb::numeric::uint256_t::data
uint64_t data[4]
Definition uint256.hpp:208
bb::stdlib::field_t< Builder >
bb::stdlib::field_t< Builder >::accumulate
static field_t accumulate(const std::vector< field_t > &input)
Efficiently compute the sum of vector entries. Using big_add_gate we reduce the number of gates neede...
Definition field.cpp:1147
bb::stdlib::field_t::get_value
bb::fr get_value() const
Given a := *this, compute its value given by a.v * a.mul + a.add.
Definition field.cpp:827
bb::stdlib::plookup_read
Definition plookup.hpp:17
bb::stdlib::plookup_read::get_lookup_accumulators
static plookup::ReadData< field_pt > get_lookup_accumulators(const plookup::MultiTableId id, const field_pt &key_a, const field_pt &key_b=0, const bool is_2_to_1_lookup=false)
Definition plookup.cpp:19
bb::stdlib::plookup_read::read_pair_from_table
static std::pair< field_pt, field_pt > read_pair_from_table(const plookup::MultiTableId id, const field_pt &key)
Definition plookup.cpp:70
bb::stdlib::witness_t
Definition witness.hpp:16
builder
AluTraceBuilder builder
Definition alu.test.cpp:123
a
FF a
Definition field_gt.test.cpp:51
b
FF b
Definition field_gt.test.cpp:52
engine
numeric::RNG & engine
Definition eccvm_transcript.test.cpp:282
bb::numeric::slice_input
std::vector< uint64_t > slice_input(const uint256_t &input, const uint64_t base, const size_t num_slices)
Definition sparse_form.hpp:18
bb::numeric::get_debug_randomness
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:190
bb::numeric::rotate32
constexpr uint32_t rotate32(const uint32_t value, const uint32_t rotation)
Definition rotate.hpp:18
bb
Entry point for Barretenberg command-line interface.
Definition acir_format_getters.cpp:6
bb::TEST
TEST(MegaCircuitBuilder, CopyConstructor)
Definition mega_circuit_builder.test.cpp:14
bb::fr
field< Bn254FrParams > fr
Definition fr.hpp:174
bb::UltraCircuitBuilder
UltraCircuitBuilder_< UltraExecutionTraceBlocks > UltraCircuitBuilder
Definition circuit_builders_fwd.hpp:24
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
field_ct
stdlib::field_t< Builder > field_ct
Definition plookup.test.cpp:17
witness_ct
stdlib::witness_t< Builder > witness_ct
Definition plookup.test.cpp:18
Builder
UltraCircuitBuilder Builder
Definition plookup.test.cpp:16
sparse_form.hpp