Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
bigfield.fuzzer.hpp
Go to the documentation of this file.
1// === AUDIT STATUS ===
2// internal: { status: not started, auditors: [], date: YYYY-MM-DD }
3// external_1: { status: not started, auditors: [], date: YYYY-MM-DD }
4// external_2: { status: not started, auditors: [], date: YYYY-MM-DD }
5// =====================
6
7#pragma once
14#pragma clang diagnostic push
15// TODO(luke/kesha): Add a comment explaining why we need this ignore and what the solution is.
16#pragma clang diagnostic ignored "-Wc99-designator"
17// This is a global variable, so that the execution handling class could alter it and signal to the input tester
18// that the input should fail
20
21#define HAVOC_TESTING
22// #define DISABLE_DIVISION 1
24
26// #define DISABLE_DIVISION
27// Enable this definition, when you want to find out the instructions that caused a failure
28// #define FUZZING_SHOW_INFORMATION 1
29
30#ifdef FUZZING_SHOW_INFORMATION
31#define PRINT_SINGLE_ARG_INSTRUCTION(first_index, vector, operation_name, preposition) \
32 { \
33 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
34 << vector[first_index].bigfield.get_value() << ") at " << first_index << " " << preposition \
35 << std::flush; \
36 }
37
38#define PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, vector, operation_name, preposition) \
39 { \
40 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
41 << vector[first_index].bigfield.get_value() << ") at " << first_index << " " << preposition << " " \
42 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
43 << vector[second_index].bigfield.get_value() << ") at " << second_index << std::flush; \
44 }
45
46#define PRINT_THREE_ARG_INSTRUCTION( \
47 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2) \
48 { \
49 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
50 << vector[first_index].bigfield.get_value() << ") at " << first_index << " " << preposition1 << " " \
51 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
52 << vector[second_index].bigfield.get_value() << ") at " << second_index << " " << preposition2 \
53 << " " << (vector[third_index].bigfield.is_constant() ? "constant(" : "witness(") \
54 << vector[third_index].bigfield.get_value() << ") at " << third_index << std::flush; \
55 }
56#define PRINT_TWO_ARG_ONE_VALUE_INSTRUCTION( \
57 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2) \
58 { \
59 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
60 << vector[first_index].bigfield.get_value() << ":" << vector[first_index].suint.current_max \
61 << ") at " << first_index << " " << preposition1 << " " \
62 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
63 << vector[second_index].bigfield.get_value() << ":" << vector[second_index].suint.current_max \
64 << ") at " << second_index << " " << preposition2 << " " << third_index << std::flush; \
65 }
66
67#define PRINT_TWO_ARG_TWO_VALUES_INSTRUCTION( \
68 first_index, second_index, value1, value2, vector, operation_name, preposition1, preposition2, preposition3) \
69 { \
70 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
71 << vector[first_index].bigfield.get_value() << ") at " << first_index << " " << preposition1 << " " \
72 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
73 << vector[second_index].bigfield.get_value() << ") at " << second_index << " " << preposition2 \
74 << " " << value1 << preposition3 << value2 << std::flush; \
75 }
76
77#define PRINT_SLICE(first_index, lsb, msb, vector) \
78 { \
79 std::cout << "Slice:" \
80 << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
81 << vector[first_index].bigfield.get_value() << ":" << vector[first_index].suint.current_max \
82 << ") at " << first_index << " " \
83 << "(" << (size_t)lsb << ":" << (size_t)msb << ")" << std::flush; \
84 }
85
86#define PRINT_RESULT(prefix, action, index, value) \
87 { \
88 std::cout << " result(" << value.bigfield.get_value() << ")" << action << index << std::endl << std::flush; \
89 }
90
91#else
92
93#define PRINT_SINGLE_ARG_INSTRUCTION(first_index, vector, operation_name, preposition)
94#define PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, vector, operation_name, preposition)
95
96#define PRINT_TWO_ARG_ONE_VALUE_INSTRUCTION( \
97 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2)
98#define PRINT_TWO_ARG_TWO_VALUES_INSTRUCTION( \
99 first_index, second_index, value1, value2, vector, operation_name, preposition1, preposition2, preposition3)
100
101#define PRINT_THREE_ARG_INSTRUCTION( \
102 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2)
103#define PRINT_RESULT(prefix, action, index, value)
104
105#define PRINT_SLICE(first_index, lsb, msb, vector)
106#endif
107
108#define OPERATION_TYPE_SIZE 1
109
110#define ELEMENT_SIZE (sizeof(fq) + 1)
111#define TWO_IN_ONE_OUT 3
112#define THREE_IN_ONE_OUT 4
113#define SLICE_ARGS_SIZE 6
114
115#define MSUB_DIV_MINIMUM_MUL_PAIRS 1
116#define MSUB_DIV_MAXIMUM_MUL_PAIRS 8
117#define MSUB_DIV_MINIMUM_SUBTRACTED_ELEMENTS 0
118#define MSUB_DIV_MAXIMUM_SUBTRACTED_ELEMENTS 8
119#define MULT_MADD_MINIMUM_MUL_PAIRS 1
120#define MULT_MADD_MAXIMUM_MUL_PAIRS 8
121#define MULT_MADD_MINIMUM_ADDED_ELEMENTS 0
122#define MULT_MADD_MAXIMUM_ADDED_ELEMENTS 8
123#define SQR_ADD_MINIMUM_ADDED_ELEMENTS 0
124#define SQR_ADD_MAXIMUM_ADDED_ELEMENTS 8
129template <typename Builder> class BigFieldBase {
130 private:
136
137 public:
143 public:
168
169 struct Element {
170 Element(uint64_t v)
171 : value(v)
172 {}
174 };
175 struct TwoArgs {
176 uint8_t in;
177 uint8_t out;
178 };
179 struct ThreeArgs {
180 uint8_t in1;
181 uint8_t in2;
182 uint8_t out;
183 };
184 struct FourArgs {
185 uint8_t in1;
186 uint8_t in2;
187 uint8_t in3;
188 uint8_t out;
189 };
190 struct FiveArgs {
191 uint8_t in1;
192 uint8_t in2;
193 uint8_t qbs;
194 uint8_t rbs;
195 uint8_t out;
196 };
211
212 struct SliceArgs {
213 uint8_t in1;
214 uint8_t lsb;
215 uint8_t msb;
216 uint8_t out1;
217 uint8_t out2;
218 uint8_t out3;
219 };
234 // The type of instruction
236 // Instruction arguments
238
246 template <typename T>
247 inline static Instruction generateRandom(T& rng)
248 requires SimpleRng<T>
249 {
250 // Choose which instruction we are going to generate
251 OPCODE instruction_opcode = static_cast<OPCODE>(rng.next() % (OPCODE::_LAST));
252 uint8_t in1, in2, in3, out, mult_size, add_size;
253 Instruction instr;
254 uint8_t mult_pairs[MULT_MADD_MAXIMUM_MUL_PAIRS * 2] = { 0 };
258
259 // Depending on instruction
260 switch (instruction_opcode) {
261 case OPCODE::CONSTANT:
262 case OPCODE::WITNESS:
264 auto value = static_cast<uint64_t>(fast_log_distributed_uint256(rng));
265 return { .id = instruction_opcode, .arguments.element = Element(value) };
266 break;
267 }
269 return { .id = instruction_opcode, .arguments.randomseed = rng.next() };
270 break;
271 case OPCODE::SQR:
274 case OPCODE::SET:
275 in1 = static_cast<uint8_t>(rng.next() & 0xff);
276 out = static_cast<uint8_t>(rng.next() & 0xff);
277 return { .id = instruction_opcode, .arguments.twoArgs = { .in = in1, .out = out } };
278 break;
279 case OPCODE::ADD:
280 case OPCODE::SUBTRACT:
281 case OPCODE::MULTIPLY:
282#ifndef DISABLE_DIVISION
283 case OPCODE::DIVIDE:
284#endif
286 // For two-input-one-output instructions we just randomly pick each argument and generate an instruction
287 // accordingly
288 in1 = static_cast<uint8_t>(rng.next() & 0xff);
289 in2 = static_cast<uint8_t>(rng.next() & 0xff);
290 out = static_cast<uint8_t>(rng.next() & 0xff);
291 return { .id = instruction_opcode, .arguments.threeArgs = { .in1 = in1, .in2 = in2, .out = out } };
292 break;
293 case OPCODE::ADD_TWO:
294 case OPCODE::MADD:
296 // For three-input-one-output instructions we just randomly pick each argument and generate an
297 // instruction accordingly
298 in1 = static_cast<uint8_t>(rng.next() & 0xff);
299 in2 = static_cast<uint8_t>(rng.next() & 0xff);
300 in3 = static_cast<uint8_t>(rng.next() & 0xff);
301 out = static_cast<uint8_t>(rng.next() & 0xff);
302 return { .id = instruction_opcode,
303 .arguments.fourArgs{ .in1 = in1, .in2 = in2, .in3 = in3, .out = out } };
304 break;
305 case OPCODE::MSUB_DIV:
306 instr.arguments.multOpArgs.divisor_index = static_cast<uint8_t>(rng.next() & 0xff);
308 mult_size =
310 static_cast<uint8_t>(rng.next() % (MULT_MADD_MAXIMUM_MUL_PAIRS - MULT_MADD_MINIMUM_MUL_PAIRS));
312 static_cast<uint8_t>(rng.next() %
314
315 for (size_t i = 0; i < mult_size; i++) {
316 mult_pairs[i * 2] = static_cast<uint8_t>(rng.next() & 0xff);
317 mult_pairs[i * 2 + 1] = static_cast<uint8_t>(rng.next() & 0xff);
318 }
319 for (size_t i = 0; i < add_size; i++) {
320 add_elements[i] = static_cast<uint8_t>(rng.next() & 0xff);
321 }
322 instr.id = instruction_opcode;
323 memcpy(instr.arguments.multOpArgs.mult_pairs, mult_pairs, 2 * MULT_MADD_MAXIMUM_MUL_PAIRS);
325 instr.arguments.multOpArgs.add_elements_count = add_size;
326 instr.arguments.multOpArgs.mult_pairs_count = mult_size;
327
328 instr.arguments.multOpArgs.output_index = static_cast<uint8_t>(rng.next() & 0xff);
329 return instr;
330 break;
331 case OPCODE::SQR_ADD:
333 static_cast<uint8_t>(rng.next() %
335
336 for (size_t i = 0; i < add_size; i++) {
337 add_elements[i] = static_cast<uint8_t>(rng.next() & 0xff);
338 }
339 instr.id = instruction_opcode;
342
343 instr.arguments.multAddArgs.input_index = static_cast<uint8_t>(rng.next() & 0xff);
344 instr.arguments.multAddArgs.output_index = static_cast<uint8_t>(rng.next() & 0xff);
345 return instr;
346 break;
347 default:
348 abort(); // We have missed some instructions, it seems
349 break;
350 }
351 }
352
362 template <typename T>
363 inline static bb::fq mutateFieldElement(bb::fq e, T& rng, HavocSettings& havoc_config)
364 requires SimpleRng<T>
365 {
366 // With a certain probability, we apply changes to the Montgomery form, rather than the plain form. This
367 // has merit, since the computation is performed in montgomery form and comparisons are often performed
368 // in it, too. Libfuzzer comparison tracing logic can then be enabled in Montgomery form
369 bool convert_to_montgomery = (rng.next() % (havoc_config.VAL_MUT_MONTGOMERY_PROBABILITY +
370 havoc_config.VAL_MUT_NON_MONTGOMERY_PROBABILITY)) <
371 havoc_config.VAL_MUT_MONTGOMERY_PROBABILITY;
372 uint256_t value_data;
373 // Conversion at the start
374#define MONT_CONVERSION \
375 if (convert_to_montgomery) { \
376 value_data = uint256_t(e.to_montgomery_form()); \
377 } else { \
378 value_data = uint256_t(e); \
379 }
380 // Inverse conversion at the end
381#define INV_MONT_CONVERSION \
382 if (convert_to_montgomery) { \
383 e = bb::fq(value_data).from_montgomery_form(); \
384 } else { \
385 e = bb::fq(value_data); \
386 }
387
388 // Pick the last value from the mutation distribution vector
389 const size_t mutation_type_count = havoc_config.value_mutation_distribution.size();
390 // Choose mutation
391 const size_t choice = rng.next() % havoc_config.value_mutation_distribution[mutation_type_count - 1];
392 if (choice < havoc_config.value_mutation_distribution[0]) {
393 // Delegate mutation to libfuzzer (bit/byte mutations, autodictionary, etc)
395 LLVMFuzzerMutate((uint8_t*)&value_data, sizeof(uint256_t), sizeof(uint256_t));
397 } else if (choice < havoc_config.value_mutation_distribution[1]) {
398 // Small addition/subtraction
399 if (convert_to_montgomery) {
400 e = e.to_montgomery_form();
401 }
402 if (rng.next() & 1) {
403 e += bb::fq(rng.next() & 0xff);
404 } else {
405 e -= bb::fq(rng.next() & 0xff);
406 }
407 if (convert_to_montgomery) {
408 e = e.from_montgomery_form();
409 }
410 } else {
411 // Substitute field element with a special value
412 switch (rng.next() % 9) {
413 case 0:
414 e = bb::fq::zero();
415 break;
416 case 1:
417 e = bb::fq::one();
418 break;
419 case 2:
420 e = -bb::fq::one();
421 break;
422 case 3:
423 e = bb::fq::one().sqrt().second;
424 break;
425 case 4:
426 e = bb::fq::one().sqrt().second.invert();
427 break;
428 case 5:
430 break;
431 case 6:
432 e = bb::fq(2);
433 break;
434 case 7:
435 e = bb::fq((bb::fq::modulus - 1) / 2);
436 break;
437 case 8:
438 e = bb::fq((bb::fr::modulus));
439 break;
440 default:
441 abort();
442 break;
443 }
444 if (convert_to_montgomery) {
445 e = e.from_montgomery_form();
446 }
447 }
448 // Return instruction
449 return e;
450 }
460 template <typename T>
462 requires SimpleRng<T>
463 {
464#define PUT_RANDOM_BYTE_IF_LUCKY(variable) \
465 if (rng.next() & 1) { \
466 variable = rng.next() & 0xff; \
467 }
468 // Depending on instruction type...
469 switch (instruction.id) {
470 case OPCODE::CONSTANT:
471 case OPCODE::WITNESS:
473 // If it represents pushing a value on the stack with a 50% probability randomly sample a bit_range
474 // Maybe mutate the value
475 if (rng.next() & 1) {
476 instruction.arguments.element.value =
477 mutateFieldElement(instruction.arguments.element.value, rng, havoc_config);
478 }
479 break;
480 case OPCODE::SQR:
483 case OPCODE::SET:
484 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.twoArgs.in)
485 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.twoArgs.out)
486 break;
487 case OPCODE::ADD:
488#ifndef DISABLE_DIVISION
489 case OPCODE::DIVIDE:
490#endif
491 case OPCODE::MULTIPLY:
492 case OPCODE::SUBTRACT:
494 // Randomly sample each of the arguments with 50% probability
495 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.in1)
496 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.in2)
497 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.out)
498 break;
499 case OPCODE::ADD_TWO:
500 case OPCODE::MADD:
502 // Randomly sample each of the arguments with 50% probability
503 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in1)
504 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in2)
505 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in3)
506 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.out)
507 break;
508 case OPCODE::MSUB_DIV:
509 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multOpArgs.divisor_index)
511 if (rng.next() & 1) {
512 // Mutate pair count
513 instruction.arguments.multOpArgs.mult_pairs_count =
515 static_cast<uint8_t>(rng.next() % (MULT_MADD_MAXIMUM_MUL_PAIRS - MULT_MADD_MINIMUM_MUL_PAIRS));
516 }
517 if (rng.next() & 1) {
518 // Mutate added element count
519 instruction.arguments.multOpArgs.add_elements_count =
521 static_cast<uint8_t>(rng.next() %
523 }
524 if (instruction.arguments.multOpArgs.mult_pairs_count && rng.next() & 1) {
525 // Mutate multiplication pairs
526 size_t mut_count = static_cast<uint8_t>(
527 rng.next() % (2 * (size_t)instruction.arguments.multOpArgs.mult_pairs_count));
528
529 for (size_t i = 0; i < mut_count; i++) {
530 auto ind = rng.next() % (2 * (size_t)instruction.arguments.multOpArgs.mult_pairs_count);
531 instruction.arguments.multOpArgs.mult_pairs[ind] = static_cast<uint8_t>(rng.next() & 0xff);
532 }
533 }
534 if (instruction.arguments.multOpArgs.add_elements_count && rng.next() & 1) {
535 // Mutate additions
536 size_t add_mut_count = static_cast<uint8_t>(
537 rng.next() % ((size_t)instruction.arguments.multOpArgs.add_elements_count));
538
539 for (size_t i = 0; i < add_mut_count; i++) {
540 instruction.arguments.multOpArgs
541 .add_elements[rng.next() % ((size_t)instruction.arguments.multOpArgs.add_elements_count)] =
542 static_cast<uint8_t>(rng.next() & 0xff);
543 }
544 }
545 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multOpArgs.output_index)
546 break;
547 case OPCODE::SQR_ADD:
548 if (rng.next() & 1) {
549 // Mutate added element count
550 instruction.arguments.multAddArgs.add_elements_count =
552 static_cast<uint8_t>(rng.next() %
554 }
555
556 if (instruction.arguments.multAddArgs.add_elements_count && rng.next() & 1) {
557 // Mutate additions
558 size_t add_mut_count = static_cast<uint8_t>(
559 rng.next() % ((size_t)instruction.arguments.multAddArgs.add_elements_count));
560
561 for (size_t i = 0; i < add_mut_count; i++) {
562 instruction.arguments.multAddArgs
563 .add_elements[rng.next() % ((size_t)instruction.arguments.multAddArgs.add_elements_count)] =
564 static_cast<uint8_t>(rng.next() & 0xff);
565 }
566 }
567 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multAddArgs.input_index)
568 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multAddArgs.output_index)
569 break;
571 instruction.arguments.randomseed = rng.next();
572 break;
573 default:
574 abort(); // New instruction encountered
575 break;
576 }
577 // Return mutated instruction
578 return instruction;
579 }
580 };
581 // We use argsizes to both specify the size of data needed to parse the instruction and to signal that the
582 // instruction is enabled (if it is -1,it's disabled )
583 class ArgSizes {
584 public:
585 static constexpr size_t CONSTANT = sizeof(bb::fq);
586 static constexpr size_t WITNESS = sizeof(bb::fq);
587 static constexpr size_t CONSTANT_WITNESS = sizeof(bb::fq);
588 static constexpr size_t SQR = 2;
589 static constexpr size_t ASSERT_EQUAL = 2;
590 static constexpr size_t ASSERT_NOT_EQUAL = 2;
591 static constexpr size_t ADD = 3;
592 static constexpr size_t SUBTRACT = 3;
593 static constexpr size_t MULTIPLY = 3;
594 static constexpr size_t ADD_TWO = 4;
595#ifndef DISABLE_DIVISION
596 static constexpr size_t DIVIDE = 3;
597#else
598 static constexpr size_t DIVIDE = static_cast<size_t>(-1);
599#endif
600 static constexpr size_t MADD = 4;
601 static constexpr size_t MULT_MADD = sizeof(typename Instruction::MultOpArgs);
602 static constexpr size_t MSUB_DIV = sizeof(typename Instruction::MultOpArgs);
603 static constexpr size_t SQR_ADD = sizeof(typename Instruction::MultAddArgs);
604 static constexpr size_t SUBTRACT_WITH_CONSTRAINT = static_cast<size_t>(-1);
605 static constexpr size_t DIVIDE_WITH_CONSTRAINTS = static_cast<size_t>(-1);
606 static constexpr size_t SLICE = static_cast<size_t>(-1);
607 static constexpr size_t COND_NEGATE = 3;
608 static constexpr size_t COND_SELECT = 4;
609 static constexpr size_t SET = 2;
610 static constexpr size_t RANDOMSEED = sizeof(uint32_t);
611 };
612
619 public:
620 static constexpr size_t CONSTANT = 1;
621 static constexpr size_t WITNESS = 1;
622 static constexpr size_t CONSTANT_WITNESS = 1;
623 static constexpr size_t ADD = 1;
624 static constexpr size_t SUBTRACT = 1;
625 static constexpr size_t MULTIPLY = 2;
626 static constexpr size_t SQR = 2;
627 static constexpr size_t ASSERT_EQUAL = 2;
628 static constexpr size_t ASSERT_NOT_EQUAL = 2;
629 static constexpr size_t ADD_TWO = 1;
630#ifndef DISABLE_DIVISION
631 static constexpr size_t DIVIDE = 16;
632#endif
633 static constexpr size_t MADD = 2;
634 static constexpr size_t MULT_MADD = 3;
635 static constexpr size_t MSUB_DIV = 3;
636 static constexpr size_t SQR_ADD = 2;
637 static constexpr size_t SUBTRACT_WITH_CONSTRAINT = 0;
638 static constexpr size_t DIVIDE_WITH_CONSTRAINTS = 0;
639 static constexpr size_t SLICE = 0;
640 static constexpr size_t COND_NEGATE = 0;
641 static constexpr size_t COND_SELECT = 0;
642 static constexpr size_t SET = 0;
643 static constexpr size_t RANDOMSEED = 0;
644 static constexpr size_t _LIMIT = 64;
645 };
650 class Parser {
651 public:
659 template <typename Instruction::OPCODE opcode> inline static Instruction parseInstructionArgs(uint8_t* Data)
660 {
661 if constexpr (opcode == Instruction::OPCODE::CONSTANT || opcode == Instruction::OPCODE::WITNESS ||
663 Instruction instr;
664 instr.id = static_cast<typename Instruction::OPCODE>(opcode);
666 return instr;
667 };
668 if constexpr (opcode == Instruction::OPCODE::RANDOMSEED) {
669 Instruction instr;
670 instr.id = static_cast<typename Instruction::OPCODE>(opcode);
671 memcpy(&instr.arguments.randomseed, Data, sizeof(uint32_t));
672 return instr;
673 };
674 if constexpr (opcode == Instruction::OPCODE::SQR || opcode == Instruction::OPCODE::ASSERT_EQUAL ||
676 return { .id = static_cast<typename Instruction::OPCODE>(opcode),
677 .arguments.twoArgs = { .in = *Data, .out = *(Data + 1) } };
678 }
679 if constexpr (opcode == Instruction::OPCODE::ADD || opcode == Instruction::OPCODE::MULTIPLY ||
680#ifndef DISABLE_DIVISION
681 opcode == Instruction::OPCODE::DIVIDE ||
682#endif
684 return { .id = static_cast<typename Instruction::OPCODE>(opcode),
685 .arguments.threeArgs = { .in1 = *Data, .in2 = *(Data + 1), .out = *(Data + 2) } };
686 }
687 if constexpr (opcode == Instruction::OPCODE::MADD || opcode == Instruction::OPCODE::ADD_TWO ||
689
690 return { .id = static_cast<typename Instruction::OPCODE>(opcode),
691 .arguments.fourArgs = {
692 .in1 = *Data, .in2 = *(Data + 1), .in3 = *(Data + 2), .out = *(Data + 3) } };
693 }
694 if constexpr (opcode == Instruction::OPCODE::MULT_MADD || opcode == Instruction::OPCODE::MSUB_DIV) {
695 Instruction mult_madd_or_div;
696 mult_madd_or_div.id = static_cast<typename Instruction::OPCODE>(opcode);
697 memcpy(&mult_madd_or_div.arguments.multOpArgs, Data, sizeof(typename Instruction::MultOpArgs));
698 mult_madd_or_div.arguments.multOpArgs.add_elements_count =
699 mult_madd_or_div.arguments.multOpArgs.add_elements_count % MULT_MADD_MAXIMUM_ADDED_ELEMENTS;
700
701 if (mult_madd_or_div.arguments.multOpArgs.add_elements_count < MULT_MADD_MINIMUM_ADDED_ELEMENTS) {
702 mult_madd_or_div.arguments.multOpArgs.add_elements_count = MULT_MADD_MINIMUM_ADDED_ELEMENTS;
703 }
704 mult_madd_or_div.arguments.multOpArgs.mult_pairs_count =
705 mult_madd_or_div.arguments.multOpArgs.mult_pairs_count % MULT_MADD_MAXIMUM_MUL_PAIRS;
706
707 if (mult_madd_or_div.arguments.multOpArgs.mult_pairs_count < MULT_MADD_MINIMUM_MUL_PAIRS) {
708 mult_madd_or_div.arguments.multOpArgs.mult_pairs_count = MULT_MADD_MINIMUM_MUL_PAIRS;
709 }
710 return mult_madd_or_div;
711 }
712 if constexpr (opcode == Instruction::OPCODE::SQR_ADD) {
713 Instruction sqr_add;
714 sqr_add.id = static_cast<typename Instruction::OPCODE>(opcode);
715 memcpy(&sqr_add.arguments.multAddArgs, Data, sizeof(typename Instruction::MultAddArgs));
716 sqr_add.arguments.multAddArgs.add_elements_count =
717 sqr_add.arguments.multAddArgs.add_elements_count % SQR_ADD_MAXIMUM_ADDED_ELEMENTS;
718
719 if (sqr_add.arguments.multOpArgs.add_elements_count < SQR_ADD_MINIMUM_ADDED_ELEMENTS) {
720
721 sqr_add.arguments.multOpArgs.add_elements_count = SQR_ADD_MINIMUM_ADDED_ELEMENTS;
722 }
723 return sqr_add;
724 }
725 }
733 template <typename Instruction::OPCODE instruction_opcode>
734 inline static void writeInstruction(Instruction& instruction, uint8_t* Data)
735 {
736 if constexpr (instruction_opcode == Instruction::OPCODE::CONSTANT ||
737 instruction_opcode == Instruction::OPCODE::WITNESS ||
738 instruction_opcode == Instruction::OPCODE::CONSTANT_WITNESS) {
739 *Data = instruction.id;
740 bb::fq::serialize_to_buffer(instruction.arguments.element.value, Data + 1);
741 }
742
743 if constexpr (instruction_opcode == Instruction::OPCODE::SQR ||
744 instruction_opcode == Instruction::OPCODE::ASSERT_EQUAL ||
745 instruction_opcode == Instruction::OPCODE::ASSERT_NOT_EQUAL ||
746 instruction_opcode == Instruction::OPCODE::SET) {
747 *Data = instruction.id;
748 *(Data + 1) = instruction.arguments.twoArgs.in;
749 *(Data + 2) = instruction.arguments.twoArgs.out;
750 }
751 if constexpr (instruction_opcode == Instruction::OPCODE::ADD ||
752#ifndef DISABLE_DIVISION
753 instruction_opcode == Instruction::OPCODE::DIVIDE ||
754#endif
755 instruction_opcode == Instruction::OPCODE::MULTIPLY ||
756 instruction_opcode == Instruction::OPCODE::SUBTRACT ||
757 instruction_opcode == Instruction::OPCODE::COND_NEGATE) {
758 *Data = instruction.id;
759 *(Data + 1) = instruction.arguments.threeArgs.in1;
760 *(Data + 2) = instruction.arguments.threeArgs.in2;
761 *(Data + 3) = instruction.arguments.threeArgs.out;
762 }
763 if constexpr (instruction_opcode == Instruction::OPCODE::ADD_TWO ||
764 instruction_opcode == Instruction::OPCODE::MADD ||
765 instruction_opcode == Instruction::OPCODE::COND_SELECT) {
766 *Data = instruction.id;
767 *(Data + 1) = instruction.arguments.fourArgs.in1;
768 *(Data + 2) = instruction.arguments.fourArgs.in2;
769 *(Data + 3) = instruction.arguments.fourArgs.in3;
770 *(Data + 4) = instruction.arguments.fourArgs.out;
771 }
772 if constexpr (instruction_opcode == Instruction::OPCODE::MULT_MADD ||
773 instruction_opcode == Instruction::OPCODE::MSUB_DIV) {
774
775 *Data = instruction.id;
776 memcpy(Data + 1, &instruction.arguments.multOpArgs, sizeof(typename Instruction::MultOpArgs));
777 }
778 if constexpr (instruction_opcode == Instruction::OPCODE::SQR_ADD) {
779
780 *Data = instruction.id;
781 memcpy(Data + 1, &instruction.arguments.multAddArgs, sizeof(typename Instruction::MultAddArgs));
782 }
783 if constexpr (instruction_opcode == Instruction::OPCODE::RANDOMSEED) {
784
785 *Data = instruction.id;
786 memcpy(Data + 1, &instruction.arguments.randomseed, sizeof(uint32_t));
787 }
788 }
789 };
795 private:
796 static bool_t construct_predicate(Builder* builder, const bool predicate)
797 {
798 /* The context field of a predicate can be nullptr;
799 * in that case, the function that handles the predicate
800 * will use the context of another input parameter
801 */
802 const bool predicate_has_ctx = static_cast<bool>(VarianceRNG.next() % 2);
803
804 return bool_t(predicate_has_ctx ? builder : nullptr, predicate);
805 }
807 {
808 const bool reconstruct = static_cast<bool>(VarianceRNG.next() % 2);
809
810#ifdef FUZZING_SHOW_INFORMATION
811 std::cout << " reconstruction? " << reconstruct << std::endl;
812#endif
813
814 if (!reconstruct) {
815 return this->bigfield;
816 }
817
818 return bigfield_t(this->bigfield);
819 }
820 uint256_t bf_u256(void) const
821 {
822 return static_cast<uint256_t>((this->bigfield.get_value() % uint512_t(bb::fq::modulus)).lo);
823 }
824
825 public:
828 ExecutionHandler() = default;
830 : base(a)
831 , bigfield(b)
832 {
833 if (b.get_context() == nullptr) {
834 abort();
835 }
836 if (b.get_value() > b.get_maximum_value()) {
837 abort();
838 }
839 for (size_t i = 0; i < 4; i++) {
840 auto limb = b.binary_basis_limbs[i];
841 if (limb.maximum_value < limb.element.get_value()) {
842 info("LIMB ", i, " VALUE IS NOT PROPERLY RESTRICTED");
843 info(limb);
844 abort();
845 }
846 }
847 }
849 : base(a)
850 , bigfield(b)
851 {
852 if (b.get_context() == nullptr) {
853 abort();
854 }
855 if (b.get_value() > b.get_maximum_value()) {
856 abort();
857 }
858 for (auto& limb : b.binary_basis_limbs) {
859 if (limb.maximum_value < limb.element.get_value()) {
860 abort();
861 }
862 }
863 }
865 : base(a)
866 , bigfield(b)
867 {
868 if (b.get_context() == nullptr) {
869 abort();
870 }
871 if (b.get_value() > b.get_maximum_value()) {
872 abort();
873 }
874 for (auto& limb : b.binary_basis_limbs) {
875 if (limb.maximum_value < limb.element.get_value()) {
876 abort();
877 }
878 }
879 }
881 {
882 return ExecutionHandler(this->base + other.base, this->bf() + other.bf());
883 }
885 {
886 return ExecutionHandler(this->base - other.base, this->bf() - other.bf());
887 }
889 {
890 return ExecutionHandler(this->base * other.base, this->bf() * other.bf());
891 }
892 ExecutionHandler sqr() { return ExecutionHandler(this->base.sqr(), this->bf().sqr()); }
894 {
895 if (other.bf().get_value() == 0) {
896 circuit_should_fail = true;
897 }
898 /* Avoid division by zero of the reference variable */
899 const auto divisor = other.base != 0 ? other.base : 1;
900 switch (VarianceRNG.next() % 3) {
901 case 0:
902 return ExecutionHandler(this->base / divisor, this->bf() / other.bf());
903 case 1:
904 return ExecutionHandler(this->base / divisor,
905 bigfield_t::div_check_denominator_nonzero({ this->bf() }, other.bf()));
906 case 2: {
907 /* Construct 'numerators' such that its sum equals this->base */
908
909 bb::fq v = 0;
910 std::vector<bigfield_t> numerators;
911
912 size_t numerators_size = std::max(bigfield_t::MAXIMUM_SUMMAND_COUNT / 2,
914 for (size_t i = 0; i < numerators_size && v != this->base; i++) {
915 uint256_t add;
916 if (i == numerators_size - 1) {
917 add = this->base - v;
918 } else {
919 add = fast_log_distributed_uint256(VarianceRNG) % (static_cast<uint256_t>(this->base - v) + 1);
920 }
921 numerators.push_back(bigfield_t(this->bigfield.context, bb::fq(add)));
922 v += add;
923 }
924 BB_ASSERT_EQ(v, this->base);
925
926 return ExecutionHandler(this->base / divisor,
927 /* Multi-numerator division */
928 bigfield_t::div_check_denominator_nonzero(numerators, other.bf()));
929 }
930 default:
931 abort();
932 }
933 }
935 {
936 return ExecutionHandler(this->base + other1.base + other2.base,
937 this->bf().add_two(other1.bigfield, other2.bigfield));
938 }
940 {
941
942 return ExecutionHandler(this->base * other1.base + other2.base,
943 this->bf().madd(other1.bigfield, { other2.bigfield }));
944 }
946 {
947 std::vector<bigfield_t> to_add_bf;
948 bb::fq accumulator = this->base.sqr();
949 for (size_t i = 0; i < to_add.size(); i++) {
950 to_add_bf.push_back(to_add[i].bigfield);
951 accumulator += to_add[i].base;
952 }
953 return ExecutionHandler(accumulator, this->bf().sqradd(to_add_bf));
954 }
955
957 const std::vector<ExecutionHandler>& input_right,
958 const std::vector<ExecutionHandler>& to_add)
959 {
960 std::vector<bigfield_t> input_left_bf;
961 std::vector<bigfield_t> input_right_bf;
962 std::vector<bigfield_t> to_add_bf;
963 bb::fq accumulator = bb::fq::zero();
964 for (size_t i = 0; i < input_left.size(); i++) {
965 input_left_bf.push_back(input_left[i].bigfield);
966 input_right_bf.push_back(input_right[i].bigfield);
967 accumulator += input_left[i].base * input_right[i].base;
968 }
969 for (size_t i = 0; i < to_add.size(); i++) {
970 to_add_bf.push_back(to_add[i].bigfield);
971 accumulator += to_add[i].base;
972 }
973 return ExecutionHandler(accumulator, bigfield_t::mult_madd(input_left_bf, input_right_bf, to_add_bf));
974 }
976 const std::vector<ExecutionHandler>& input_right,
977 const ExecutionHandler& divisor,
978 const std::vector<ExecutionHandler>& to_sub)
979 {
980 std::vector<bigfield_t> input_left_bf;
981 std::vector<bigfield_t> input_right_bf;
982 std::vector<bigfield_t> to_sub_bf;
983 bb::fq accumulator = bb::fq::zero();
984 for (size_t i = 0; i < input_left.size(); i++) {
985 input_left_bf.push_back(input_left[i].bigfield);
986 input_right_bf.push_back(input_right[i].bigfield);
987 accumulator -= input_left[i].base * input_right[i].base;
988 }
989 for (size_t i = 0; i < to_sub.size(); i++) {
990 to_sub_bf.push_back(to_sub[i].bigfield);
991 accumulator -= to_sub[i].base;
992 }
993 /* Avoid division by zero of the reference variable */
994 if (divisor.base != 0) {
995 accumulator /= divisor.base;
996 }
997 const bool enable_divisor_nz_check = static_cast<bool>(VarianceRNG.next() % 2);
998 return ExecutionHandler(
999 accumulator,
1001 input_left_bf, input_right_bf, divisor.bigfield, to_sub_bf, enable_divisor_nz_check));
1002 }
1003
1004 // assert_equal uses assert_is_in_field in some cases, so we don't need
1005 // to check that separately
1007 {
1008 if (other.bf().is_constant() && this->bf().is_constant()) {
1009 // Assert equal does nothing in this case
1010 return;
1011 }
1012
1013 if (!other.bf().is_constant() && !this->bf().is_constant()) {
1014 auto to_add = bigfield_t(this->bf().context, uint256_t(this->base - other.base));
1015 auto new_el = other.bf() + to_add;
1016
1017 this->bf().assert_equal(new_el);
1018 return;
1019 }
1020
1021 bigfield_t lhs, rhs;
1022 if (other.bf().is_constant() && !this->bf().is_constant()) {
1023 auto to_add = bigfield_t(this->bigfield.context, uint256_t(this->base - other.base));
1024 auto new_el = other.bf() + to_add;
1025 ASSERT(new_el.is_constant());
1026
1027 lhs = this->bigfield;
1028 rhs = new_el;
1029 }
1030
1031 if (!other.bf().is_constant() && this->bf().is_constant()) {
1032 auto to_add = bigfield_t(this->bf().context, uint256_t(this->base - other.base));
1033 auto new_el = other.bf() + to_add;
1034
1035 lhs = new_el;
1036 rhs = this->bf();
1037 }
1038
1039 ASSERT(!lhs.is_constant());
1040 ASSERT(rhs.is_constant());
1041
1042 bool overflow = lhs.get_value() >= bb::fq::modulus;
1043 bool reduce = VarianceRNG.next() & 1;
1044
1045#ifdef FUZZING_SHOW_INFORMATION
1046 std::cout << "reduce? " << reduce << std::endl;
1047 std::cout << "overflow? " << overflow << std::endl;
1048#endif
1049
1050 if (!reduce) {
1051 if (overflow) {
1052 // In case we overflow the modulus, the assert will fail
1053 // see NOTE(https://github.com/AztecProtocol/barretenberg/issues/998)
1054 circuit_should_fail = true;
1055 } else {
1056 // In case we do not overflow, we can be sure that this will pass
1057 lhs.assert_is_in_field();
1058 }
1059 } else {
1060 // otherwise force reduce so we pass it anyway
1062 }
1063
1064 // swap the sides
1065 if (VarianceRNG.next() & 1)
1066 std::swap(lhs, rhs);
1067 lhs.assert_equal(rhs);
1068 }
1069
1071 {
1072 if (this->base == other.base) {
1073 return;
1074 } else {
1075 this->bf().assert_is_not_equal(other.bf());
1076 }
1077 }
1078
1080 {
1081 return ExecutionHandler(predicate ? -(this->base) : this->base,
1082 this->bf().conditional_negate(construct_predicate(builder, predicate)));
1083 }
1084
1086 {
1087 return ExecutionHandler(predicate ? other.base : this->base,
1088 this->bf().conditional_select(other.bf(), construct_predicate(builder, predicate)));
1089 }
1090 /* Explicit re-instantiation using the various bigfield_t constructors */
1092 {
1093 /* Invariant check */
1094 if (this->bigfield.get_value() > this->bigfield.get_maximum_value()) {
1095 std::cerr << "bigfield value is larger than its maximum" << std::endl;
1096 abort();
1097 }
1098
1099 uint32_t switch_case = VarianceRNG.next() % 5;
1100
1101#ifdef FUZZING_SHOW_INFORMATION
1102 std::cout << " using " << switch_case << " constructor" << std::endl;
1103#endif
1104 switch (switch_case) {
1105 case 0:
1106 /* Construct via bigfield_t */
1107 return ExecutionHandler(this->base, bigfield_t(this->bigfield));
1108 case 1:
1109 /* Construct via uint256_t */
1110 return ExecutionHandler(this->base, bigfield_t(builder, bf_u256()));
1111 // case 2: // TODO(alex): Uncomment once fixed
1112 // /* Construct via byte_array */
1113 // /*
1114 // * Bug: https://github.com/AztecProtocol/aztec2-internal/issues/1496
1115 // *
1116 // * Remove of change this invocation if that issue is a false positive */
1117 // return ExecutionHandler(this->base, bigfield_t(this->bigfield.to_byte_array()));
1118 case 2: {
1119 const uint256_t u256 = bf_u256();
1120 const uint256_t u256_lo = u256.slice(0, bigfield_t::NUM_LIMB_BITS * 2);
1122 const field_t field_lo(builder, u256_lo);
1123 const field_t field_hi(builder, u256_hi);
1124
1125 /* Construct via two field_t's */
1126 return ExecutionHandler(this->base, bigfield_t(field_lo, field_hi));
1127 }
1128 case 3: {
1129 /* Invoke assignment operator */
1130
1131 bigfield_t bf_new(builder);
1132 bf_new = bf();
1133
1134 return ExecutionHandler(this->base, bigfield_t(bf_new));
1135 }
1136 case 4: {
1137 /* Invoke move constructor */
1138 auto bf_copy = bf();
1139
1140 return ExecutionHandler(this->base, bigfield_t(std::move(bf_copy)));
1141 }
1142 default:
1143 abort();
1144 }
1145 }
1146
1155 static inline size_t execute_CONSTANT(Builder* builder,
1158 {
1159 (void)builder;
1160 stack.push_back(ExecutionHandler(instruction.arguments.element.value,
1161 bigfield_t(builder, instruction.arguments.element.value)));
1162#ifdef FUZZING_SHOW_INFORMATION
1163 std::cout << "Pushed constant value " << instruction.arguments.element.value << " to position "
1164 << stack.size() - 1 << std::endl;
1165#endif
1166 return 0;
1167 }
1168
1177 static inline size_t execute_WITNESS(Builder* builder,
1180 {
1181
1182 // THis is strange
1183 stack.push_back(
1184 ExecutionHandler(instruction.arguments.element.value,
1185 bigfield_t::from_witness(builder, bb::fq(instruction.arguments.element.value))));
1186 // stack.push_back(
1187 // bigfield_t::create_from_u512_as_witness(builder,
1188 // uint256_t(instruction.arguments.element.value)));
1189
1190#ifdef FUZZING_SHOW_INFORMATION
1191 std::cout << "Pushed witness value " << instruction.arguments.element.value << " to position "
1192 << stack.size() - 1 << std::endl;
1193#endif
1194 return 0;
1195 }
1196
1209 {
1210 stack.push_back(ExecutionHandler(
1211 instruction.arguments.element.value,
1213#ifdef FUZZING_SHOW_INFORMATION
1214 std::cout << "Pushed constant witness value " << instruction.arguments.element.value << " to position "
1215 << stack.size() - 1 << std::endl;
1216#endif
1217 return 0;
1218 }
1227 static inline size_t execute_MULTIPLY(Builder* builder,
1230 {
1231
1232 (void)builder;
1233 if (stack.size() == 0) {
1234 return 1;
1235 }
1236 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1237 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1238 size_t output_index = instruction.arguments.threeArgs.out;
1239
1240 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Multiplying", "*")
1241
1242 ExecutionHandler result;
1243 result = stack[first_index] * stack[second_index];
1244 // If the output index is larger than the number of elements in stack, append
1245 if (output_index >= stack.size()) {
1246 PRINT_RESULT("", "pushed to ", stack.size(), result)
1247 stack.push_back(result);
1248 } else {
1249
1250 PRINT_RESULT("", "saved to ", output_index, result)
1251 stack[output_index] = result;
1252 }
1253 return 0;
1254 };
1263 static inline size_t execute_ADD(Builder* builder,
1266 {
1267 (void)builder;
1268 if (stack.size() == 0) {
1269 return 1;
1270 }
1271 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1272 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1273 size_t output_index = instruction.arguments.threeArgs.out;
1274
1275 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Adding", "+")
1276
1277 ExecutionHandler result;
1278 result = stack[first_index] + stack[second_index];
1279 // If the output index is larger than the number of elements in stack, append
1280 if (output_index >= stack.size()) {
1281 PRINT_RESULT("", "pushed to ", stack.size(), result)
1282 stack.push_back(result);
1283 } else {
1284
1285 PRINT_RESULT("", "saved to ", output_index, result)
1286 stack[output_index] = result;
1287 }
1288 return 0;
1289 };
1290
1299 static inline size_t execute_SQR(Builder* builder,
1302 {
1303 (void)builder;
1304 if (stack.size() == 0) {
1305 return 1;
1306 }
1307 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1308 size_t output_index = instruction.arguments.twoArgs.out;
1309
1310 PRINT_SINGLE_ARG_INSTRUCTION(first_index, stack, "Squaring", "squared")
1311
1312 ExecutionHandler result;
1313 result = stack[first_index].sqr();
1314 // If the output index is larger than the number of elements in stack, append
1315 if (output_index >= stack.size()) {
1316 PRINT_RESULT("", "pushed to ", stack.size(), result)
1317 stack.push_back(result);
1318 } else {
1319
1320 PRINT_RESULT("", "saved to ", output_index, result)
1321 stack[output_index] = result;
1322 }
1323 return 0;
1324 };
1325
1334 static inline size_t execute_ASSERT_EQUAL(Builder* builder,
1337 {
1338 (void)builder;
1339 if (stack.size() == 0) {
1340 return 1;
1341 }
1342 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1343 size_t second_index = instruction.arguments.twoArgs.out % stack.size();
1344
1345 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "ASSERT_EQUAL", "== something + ")
1346#ifdef FUZZING_SHOW_INFORMATION
1348#endif
1349
1350 stack[first_index].assert_equal(stack[second_index]);
1351 return 0;
1352 };
1353
1365 {
1366 (void)builder;
1367 if (stack.size() == 0) {
1368 return 1;
1369 }
1370 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1371 size_t second_index = instruction.arguments.twoArgs.out % stack.size();
1372
1373 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "ASSERT_NOT_EQUAL", "!=")
1374#ifdef FUZZING_SHOW_INFORMATION
1376#endif
1377
1378 // We have an assert that is triggered for this case
1379 if (stack[first_index].bigfield.is_constant() && stack[second_index].bigfield.is_constant()) {
1380 return 0;
1381 }
1382 stack[first_index].assert_not_equal(stack[second_index]);
1383 return 0;
1384 };
1385
1394 static inline size_t execute_SUBTRACT(Builder* builder,
1397 {
1398 (void)builder;
1399 if (stack.size() == 0) {
1400 return 1;
1401 }
1402 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1403 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1404 size_t output_index = instruction.arguments.threeArgs.out;
1405
1406 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Subtracting", "-")
1407
1408 ExecutionHandler result;
1409 result = stack[first_index] - stack[second_index];
1410 // If the output index is larger than the number of elements in stack, append
1411 if (output_index >= stack.size()) {
1412 PRINT_RESULT("", "pushed to ", stack.size(), result)
1413 stack.push_back(result);
1414 } else {
1415
1416 PRINT_RESULT("", "saved to ", output_index, result)
1417 stack[output_index] = result;
1418 }
1419 return 0;
1420 };
1429 static inline size_t execute_DIVIDE(Builder* builder,
1432 {
1433 (void)builder;
1434 if (stack.size() == 0) {
1435 return 1;
1436 }
1437 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1438 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1439 size_t output_index = instruction.arguments.threeArgs.out;
1440
1441 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Dividing", "/")
1442
1443 ExecutionHandler result;
1444 if (bb::fq((stack[second_index].bigfield.get_value() % bb::fq::modulus).lo) == 0) {
1445 return 0; // This is not handled by bigfield
1446 }
1447 // TODO: FIX THIS. I can't think of an elegant fix for this bigfield issue right now
1448 // if (bb::fq((stack[first_index].bigfield.get_value() % bb::fq::modulus).lo) == 0) {
1449 // return 0;
1450 // }
1451 result = stack[first_index] / stack[second_index];
1452 // If the output index is larger than the number of elements .in stack, append
1453 if (output_index >= stack.size()) {
1454 PRINT_RESULT("", "pushed to ", stack.size(), result)
1455 stack.push_back(result);
1456 } else {
1457
1458 PRINT_RESULT("", "saved to ", output_index, result)
1459 stack[output_index] = result;
1460 }
1461 return 0;
1462 };
1472 static inline size_t execute_ADD_TWO(Builder* builder,
1475 {
1476 (void)builder;
1477 if (stack.size() == 0) {
1478 return 1;
1479 }
1480 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1481 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1482 size_t third_index = instruction.arguments.fourArgs.in3 % stack.size();
1483 size_t output_index = instruction.arguments.fourArgs.out;
1484 PRINT_THREE_ARG_INSTRUCTION(first_index, second_index, third_index, stack, "ADD_TWO:", "+", "+")
1485
1486 ExecutionHandler result;
1487 result = stack[first_index].add_two(stack[second_index], stack[third_index]);
1488 // If the output index is larger than the number of elements in stack, append
1489 if (output_index >= stack.size()) {
1490 PRINT_RESULT("", "pushed to ", stack.size(), result)
1491 stack.push_back(result);
1492 } else {
1493 PRINT_RESULT("", "saved to ", output_index, result)
1494 stack[output_index] = result;
1495 }
1496 return 0;
1497 };
1498
1508 static inline size_t execute_MADD(Builder* builder,
1511 {
1512 (void)builder;
1513 if (stack.size() == 0) {
1514 return 1;
1515 }
1516 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1517 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1518 size_t third_index = instruction.arguments.fourArgs.in3 % stack.size();
1519 size_t output_index = instruction.arguments.fourArgs.out;
1520 PRINT_THREE_ARG_INSTRUCTION(first_index, second_index, third_index, stack, "MADD:", "*", "+")
1521
1522 ExecutionHandler result;
1523 result = stack[first_index].madd(stack[second_index], stack[third_index]);
1524 // If the output index is larger than the number of elements in stack, append
1525 if (output_index >= stack.size()) {
1526 PRINT_RESULT("", "pushed to ", stack.size(), result)
1527 stack.push_back(result);
1528 } else {
1529
1530 PRINT_RESULT("", "saved to ", output_index, result)
1531 stack[output_index] = result;
1532 }
1533 return 0;
1534 };
1544 static inline size_t execute_MULT_MADD(Builder* builder,
1547 {
1548 (void)builder;
1549 if (stack.size() == 0) {
1550 return 1;
1551 }
1555#ifdef FUZZING_SHOW_INFORMATION
1556 std::cout << "MULT_MADD:" << std::endl;
1557 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1558 size_t index_left = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size();
1559 size_t index_right = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size();
1560 std::cout << (stack[index_left].bigfield.is_constant() ? "Constant( " : "Witness( ")
1561 << stack[index_left].bigfield.get_value() << ") at " << index_left << " * ";
1562 std::cout << (stack[index_right].bigfield.is_constant() ? "Constant( " : "Witness( ")
1563 << stack[index_right].bigfield.get_value() << ") at " << index_right;
1564 if (i == (instruction.arguments.multOpArgs.mult_pairs_count - 1) &&
1565 instruction.arguments.multOpArgs.add_elements_count == 0) {
1567 } else {
1568 std::cout << " + " << std::endl;
1569 }
1570 }
1571 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1572 size_t add_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1573 std::cout << (stack[add_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1574 << stack[add_index].bigfield.get_value() << ") at " << add_index;
1575 if (i == (instruction.arguments.multOpArgs.add_elements_count - 1)) {
1577 } else {
1578 std::cout << " + " << std::endl;
1579 }
1580 }
1581#endif
1582 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1583 input_left.push_back(stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size()]);
1584 input_right.push_back(
1585 stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size()]);
1586 }
1587
1588 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1589 auto element_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1590 to_add.push_back(stack[element_index]);
1591 }
1592 size_t output_index = (size_t)instruction.arguments.multOpArgs.output_index;
1593
1594 ExecutionHandler result;
1595 result = ExecutionHandler::mult_madd(input_left, input_right, to_add);
1596 // If the output index is larger than the number of elements in stack, append
1597 if (output_index >= stack.size()) {
1598 PRINT_RESULT("", "pushed to ", stack.size(), result)
1599 stack.push_back(result);
1600 } else {
1601
1602 PRINT_RESULT("", "saved to ", output_index, result)
1603 stack[output_index] = result;
1604 }
1605 return 0;
1606 };
1607
1617 static inline size_t execute_MSUB_DIV(Builder* builder,
1620 {
1621 (void)builder;
1622 if (stack.size() == 0) {
1623 return 1;
1624 }
1628 size_t divisor_index = instruction.arguments.multOpArgs.divisor_index % stack.size();
1629#ifdef FUZZING_SHOW_INFORMATION
1630
1631 std::cout << "MSUB_DIV:" << std::endl;
1632 std::cout << "- (";
1633 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1634 size_t index_left = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size();
1635 size_t index_right = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size();
1636 std::cout << (stack[index_left].bigfield.is_constant() ? "Constant( " : "Witness( ")
1637 << stack[index_left].bigfield.get_value() << ") at " << index_left << " * ";
1638 std::cout << (stack[index_right].bigfield.is_constant() ? "Constant( " : "Witness( ")
1639 << stack[index_right].bigfield.get_value() << ") at " << index_right;
1640 if (i == (instruction.arguments.multOpArgs.mult_pairs_count - 1) &&
1641 instruction.arguments.multOpArgs.add_elements_count == 0) {
1643 } else {
1644 std::cout << " + " << std::endl;
1645 }
1646 }
1647 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1648 size_t add_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1649 std::cout << (stack[add_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1650 << stack[add_index].bigfield.get_value() << ") at " << add_index;
1651 if (i == (instruction.arguments.multOpArgs.add_elements_count - 1)) {
1653 } else {
1654 std::cout << " + " << std::endl;
1655 }
1656 }
1657 std::cout << ") / " << std::endl;
1658 std::cout << (stack[divisor_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1659 << stack[divisor_index].bigfield.get_value() << ") at " << divisor_index << std::endl;
1660
1661#endif
1662 if (bb::fq((stack[divisor_index].bigfield.get_value() % bb::fq::modulus).lo) == 0) {
1663 return 0; // This is not handled by bigfield by default, need to enable check
1664 }
1665 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1666 input_left.push_back(stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size()]);
1667 input_right.push_back(
1668 stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size()]);
1669 }
1670
1671 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1672 auto element_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1673 to_sub.push_back(stack[element_index]);
1674 }
1675 size_t output_index = (size_t)instruction.arguments.multOpArgs.output_index;
1676
1677 ExecutionHandler result;
1678 result = ExecutionHandler::msub_div(input_left, input_right, stack[divisor_index], to_sub);
1679 // If the output index is larger than the number of elements in stack, append
1680 if (output_index >= stack.size()) {
1681 PRINT_RESULT("", "pushed to ", stack.size(), result)
1682 stack.push_back(result);
1683 } else {
1684
1685 PRINT_RESULT("", "saved to ", output_index, result)
1686 stack[output_index] = result;
1687 }
1688 return 0;
1689 };
1690
1700 static inline size_t execute_SQR_ADD(Builder* builder,
1703 {
1704 (void)builder;
1705 if (stack.size() == 0) {
1706 return 1;
1707 }
1709
1710 size_t input_index = (size_t)instruction.arguments.multAddArgs.input_index % stack.size();
1711#ifdef FUZZING_SHOW_INFORMATION
1712 std::cout << "SQR_ADD:" << std::endl;
1713 std::cout << (stack[input_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1714 << stack[input_index].bigfield.get_value() << ") at " << input_index << " squared ";
1715 if (instruction.arguments.multAddArgs.add_elements_count == 0) {
1717 } else {
1718 std::cout << "+" << std::endl;
1719 }
1720
1721 for (size_t i = 0; i < instruction.arguments.multAddArgs.add_elements_count; i++) {
1722 size_t add_index = (size_t)instruction.arguments.multAddArgs.add_elements[i] % stack.size();
1723 std::cout << (stack[add_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1724 << stack[add_index].bigfield.get_value() << ") at " << add_index;
1725 if (i == (instruction.arguments.multOpArgs.add_elements_count - 1)) {
1727 } else {
1728 std::cout << " + " << std::endl;
1729 }
1730 }
1731#endif
1732
1733 for (size_t i = 0; i < instruction.arguments.multAddArgs.add_elements_count; i++) {
1734 auto element_index = (size_t)instruction.arguments.multAddArgs.add_elements[i] % stack.size();
1735 to_add.push_back(stack[element_index]);
1736 }
1737 size_t output_index = (size_t)instruction.arguments.multAddArgs.output_index;
1738
1739 ExecutionHandler result;
1740 result = stack[input_index].sqr_add(to_add);
1741 // If the output index is larger than the number of elements in stack, append
1742 if (output_index >= stack.size()) {
1743 PRINT_RESULT("", "pushed to ", stack.size(), result)
1744 stack.push_back(result);
1745 } else {
1746
1747 PRINT_RESULT("", "saved to ", output_index, result)
1748 stack[output_index] = result;
1749 }
1750 return 0;
1751 };
1760 static inline size_t execute_COND_NEGATE(Builder* builder,
1763 {
1764 (void)builder;
1765 if (stack.size() == 0) {
1766 return 1;
1767 }
1768 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1769 size_t output_index = instruction.arguments.threeArgs.out % stack.size();
1770 bool predicate = instruction.arguments.threeArgs.in2 % 2;
1771
1772 PRINT_SINGLE_ARG_INSTRUCTION(first_index, stack, "Negating", "is negated " + std::to_string(predicate))
1773
1774 ExecutionHandler result;
1775 result = stack[first_index].conditional_negate(builder, predicate);
1776 // If the output index is larger than the number of elements in stack, append
1777 if (output_index >= stack.size()) {
1778 PRINT_RESULT("", "pushed to ", stack.size(), result)
1779 stack.push_back(result);
1780 } else {
1781
1782 PRINT_RESULT("", "saved to ", output_index, result)
1783 stack[output_index] = result;
1784 }
1785 return 0;
1786 };
1787
1796 static inline size_t execute_COND_SELECT(Builder* builder,
1799 {
1800 (void)builder;
1801 if (stack.size() == 0) {
1802 return 1;
1803 }
1804 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1805 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1806 size_t output_index = instruction.arguments.fourArgs.out % stack.size();
1807 bool predicate = instruction.arguments.fourArgs.in3 % 2;
1808
1809 ExecutionHandler result;
1810
1812 first_index, second_index, stack, "Selecting #" + std::to_string(predicate) + " from", ", ")
1813
1814 result = stack[first_index].conditional_select(builder, stack[second_index], predicate);
1815 // If the output index is larger than the number of elements in stack, append
1816 if (output_index >= stack.size()) {
1817 PRINT_RESULT("", "pushed to ", stack.size(), result)
1818 stack.push_back(result);
1819 } else {
1820
1821 PRINT_RESULT("", "saved to ", output_index, result)
1822 stack[output_index] = result;
1823 }
1824 return 0;
1825 };
1834 static inline size_t execute_SET(Builder* builder,
1837 {
1838 (void)builder;
1839 if (stack.size() == 0) {
1840 return 1;
1841 }
1842 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1843 size_t output_index = instruction.arguments.twoArgs.out;
1844 ExecutionHandler result;
1845
1846 PRINT_SINGLE_ARG_INSTRUCTION(first_index, stack, "Setting value", "")
1847
1848 result = stack[first_index].set(builder);
1849 // If the output index is larger than the number of elements in stack, append
1850 if (output_index >= stack.size()) {
1851 PRINT_RESULT("", "pushed to ", stack.size(), result)
1852 stack.push_back(result);
1853 } else {
1854 PRINT_RESULT("", "saved to ", stack.size(), result)
1855 stack[output_index] = result;
1856 }
1857 return 0;
1858 };
1867 static inline size_t execute_RANDOMSEED(Builder* builder,
1870 {
1871 (void)builder;
1872 (void)stack;
1873
1874 VarianceRNG.reseed(instruction.arguments.randomseed);
1875 return 0;
1876 };
1877 };
1878
1893 {
1894 (void)builder;
1895 for (size_t i = 0; i < stack.size(); i++) {
1896 auto element = stack[i];
1897 if (bb::fq((element.bigfield.get_value() % uint512_t(bb::fq::modulus)).lo) != element.base) {
1898 std::cerr << "Failed at " << i << " with actual value " << element.base << " and value in bigfield "
1899 << element.bigfield.get_value() << std::endl;
1900 return false;
1901 }
1902 }
1903 return true;
1904 }
1905};
1906
1907#ifdef HAVOC_TESTING
1908
1909extern "C" int LLVMFuzzerInitialize(int* argc, char*** argv)
1910{
1911 (void)argc;
1912 (void)argv;
1913 // These are the settings, optimized for the safeuint class (under them, fuzzer reaches maximum expected
1914 // coverage in 40 seconds)
1915 fuzzer_havoc_settings = HavocSettings{ .GEN_LLVM_POST_MUTATION_PROB = 30, // Out of 200
1916 .GEN_MUTATION_COUNT_LOG = 5, // -Fully checked
1917 .GEN_STRUCTURAL_MUTATION_PROBABILITY = 300, // Fully checked
1918 .GEN_VALUE_MUTATION_PROBABILITY = 700, // Fully checked
1919 .ST_MUT_DELETION_PROBABILITY = 100, // Fully checked
1920 .ST_MUT_DUPLICATION_PROBABILITY = 80, // Fully checked
1921 .ST_MUT_INSERTION_PROBABILITY = 120, // Fully checked
1922 .ST_MUT_MAXIMUM_DELETION_LOG = 6, // 2 because of limit
1923 .ST_MUT_MAXIMUM_DUPLICATION_LOG = 2, // -Fully checked
1924 .ST_MUT_SWAP_PROBABILITY = 50, // Fully checked
1925 .VAL_MUT_LLVM_MUTATE_PROBABILITY = 250, // Fully checked
1926 .VAL_MUT_MONTGOMERY_PROBABILITY = 130, // Fully checked
1927 .VAL_MUT_NON_MONTGOMERY_PROBABILITY = 50, // Fully checked
1928 .VAL_MUT_SMALL_ADDITION_PROBABILITY = 110, // Fully checked
1929 .VAL_MUT_SPECIAL_VALUE_PROBABILITY = 130, // Fully checked
1930 .structural_mutation_distribution = {},
1931 .value_mutation_distribution = {} };
1937 /*
1938 std::random_device rd;
1939 std::uniform_int_distribution<uint64_t> dist(0, ~(uint64_t)(0));
1940 srandom(static_cast<unsigned int>(dist(rd)));
1941
1942 fuzzer_havoc_settings =
1943 HavocSettings{ .GEN_MUTATION_COUNT_LOG = static_cast<size_t>((random() % 8) + 1),
1944 .GEN_STRUCTURAL_MUTATION_PROBABILITY = static_cast<size_t>(random() % 100),
1945 .GEN_VALUE_MUTATION_PROBABILITY = static_cast<size_t>(random() % 100),
1946 .ST_MUT_DELETION_PROBABILITY = static_cast<size_t>(random() % 100),
1947 .ST_MUT_DUPLICATION_PROBABILITY = static_cast<size_t>(random() % 100),
1948 .ST_MUT_INSERTION_PROBABILITY = static_cast<size_t>((random() % 99) + 1),
1949 .ST_MUT_MAXIMUM_DELETION_LOG = static_cast<size_t>((random() % 8) + 1),
1950 .ST_MUT_MAXIMUM_DUPLICATION_LOG = static_cast<size_t>((random() % 8) + 1),
1951 .ST_MUT_SWAP_PROBABILITY = static_cast<size_t>(random() % 100),
1952 .VAL_MUT_LLVM_MUTATE_PROBABILITY = static_cast<size_t>(random() % 100),
1953 .VAL_MUT_MONTGOMERY_PROBABILITY = static_cast<size_t>(random() % 100),
1954 .VAL_MUT_NON_MONTGOMERY_PROBABILITY = static_cast<size_t>(random() % 100),
1955 .VAL_MUT_SMALL_ADDITION_PROBABILITY = static_cast<size_t>(random() % 100),
1956 .VAL_MUT_SPECIAL_VALUE_PROBABILITY = static_cast<size_t>(random() % 100)
1957
1958 };
1959 while (fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY == 0 &&
1960 fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY == 0) {
1961 fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY = static_cast<size_t>(random() % 8);
1962 fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY = static_cast<size_t>(random() % 8);
1963 }
1964 */
1965
1966 // fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB = static_cast<size_t>(((random() % (20 - 1)) + 1) * 10);
1971 /*
1972 std::cerr << "CUSTOM MUTATOR SETTINGS:" << std::endl
1973 << "################################################################" << std::endl
1974 << "GEN_LLVM_POST_MUTATION_PROB: " << fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB << std::endl
1975 << "GEN_MUTATION_COUNT_LOG: " << fuzzer_havoc_settings.GEN_MUTATION_COUNT_LOG << std::endl
1976 << "GEN_STRUCTURAL_MUTATION_PROBABILITY: " <<
1977 fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY
1978 << std::endl
1979 << "GEN_VALUE_MUTATION_PROBABILITY: " << fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY <<
1980 std::endl
1981 << "ST_MUT_DELETION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_DELETION_PROBABILITY << std::endl
1982 << "ST_MUT_DUPLICATION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_DUPLICATION_PROBABILITY <<
1983 std::endl
1984 << "ST_MUT_INSERTION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_INSERTION_PROBABILITY << std::endl
1985 << "ST_MUT_MAXIMUM_DELETION_LOG: " << fuzzer_havoc_settings.ST_MUT_MAXIMUM_DELETION_LOG << std::endl
1986 << "ST_MUT_MAXIMUM_DUPLICATION_LOG: " << fuzzer_havoc_settings.ST_MUT_MAXIMUM_DUPLICATION_LOG <<
1987 std::endl
1988 << "ST_MUT_SWAP_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_SWAP_PROBABILITY << std::endl
1989 << "VAL_MUT_LLVM_MUTATE_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_LLVM_MUTATE_PROBABILITY
1990 << std::endl
1991 << "VAL_MUT_MONTGOMERY_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_MONTGOMERY_PROBABILITY <<
1992 std::endl
1993 << "VAL_MUT_NON_MONTGOMERY_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_NON_MONTGOMERY_PROBABILITY
1994 << std::endl
1995 << "VAL_MUT_SMALL_ADDITION_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_SMALL_ADDITION_PROBABILITY
1996 << std::endl
1997 << "VAL_MUT_SMALL_MULTIPLICATION_PROBABILITY: "
1998 << fuzzer_havoc_settings.VAL_MUT_SMALL_MULTIPLICATION_PROBABILITY << std::endl
1999 << "VAL_MUT_SPECIAL_VALUE_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_SPECIAL_VALUE_PROBABILITY
2000 << std::endl;
2001 */
2002 std::vector<size_t> structural_mutation_distribution;
2003 std::vector<size_t> value_mutation_distribution;
2004 size_t temp = 0;
2005 temp += fuzzer_havoc_settings.ST_MUT_DELETION_PROBABILITY;
2006 structural_mutation_distribution.push_back(temp);
2007 temp += fuzzer_havoc_settings.ST_MUT_DUPLICATION_PROBABILITY;
2008 structural_mutation_distribution.push_back(temp);
2009 temp += fuzzer_havoc_settings.ST_MUT_INSERTION_PROBABILITY;
2010 structural_mutation_distribution.push_back(temp);
2011 temp += fuzzer_havoc_settings.ST_MUT_SWAP_PROBABILITY;
2012 structural_mutation_distribution.push_back(temp);
2013 fuzzer_havoc_settings.structural_mutation_distribution = structural_mutation_distribution;
2014
2015 temp = 0;
2016 temp += fuzzer_havoc_settings.VAL_MUT_LLVM_MUTATE_PROBABILITY;
2017 value_mutation_distribution.push_back(temp);
2018 temp += fuzzer_havoc_settings.VAL_MUT_SMALL_ADDITION_PROBABILITY;
2019 value_mutation_distribution.push_back(temp);
2020
2021 temp += fuzzer_havoc_settings.VAL_MUT_SPECIAL_VALUE_PROBABILITY;
2022 value_mutation_distribution.push_back(temp);
2023 fuzzer_havoc_settings.value_mutation_distribution = value_mutation_distribution;
2024 return 0;
2025}
2026#endif
2027
2032extern "C" size_t LLVMFuzzerTestOneInput(const uint8_t* Data, size_t Size)
2033{
2034 RunWithBuilders<BigFieldBase, FuzzerCircuitTypes>(Data, Size, VarianceRNG);
2035 return 0;
2036}
2037
2038#pragma clang diagnostic pop
#define BB_ASSERT_EQ(actual, expected,...)
Definition assert.hpp:88
#define ASSERT(expression,...)
Definition assert.hpp:77
#define PRINT_SINGLE_ARG_INSTRUCTION(first_index, vector, operation_name, preposition)
#define PRINT_THREE_ARG_INSTRUCTION( first_index, second_index, third_index, vector, operation_name, preposition1, preposition2)
#define PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, vector, operation_name, preposition)
#define INV_MONT_CONVERSION
#define SQR_ADD_MINIMUM_ADDED_ELEMENTS
#define MULT_MADD_MINIMUM_MUL_PAIRS
#define MULT_MADD_MAXIMUM_MUL_PAIRS
FastRandom VarianceRNG(0)
#define MULT_MADD_MINIMUM_ADDED_ELEMENTS
bool circuit_should_fail
int LLVMFuzzerInitialize(int *argc, char ***argv)
#define MULT_MADD_MAXIMUM_ADDED_ELEMENTS
#define MONT_CONVERSION
#define PRINT_RESULT(prefix, action, index, value)
size_t LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size)
Fuzzer entry function.
#define SQR_ADD_MAXIMUM_ADDED_ELEMENTS
#define PUT_RANDOM_BYTE_IF_LUCKY(variable)
static constexpr size_t MADD
static constexpr size_t SUBTRACT
static constexpr size_t RANDOMSEED
static constexpr size_t SLICE
static constexpr size_t MULT_MADD
static constexpr size_t ASSERT_NOT_EQUAL
static constexpr size_t WITNESS
static constexpr size_t MULTIPLY
static constexpr size_t CONSTANT
static constexpr size_t ADD_TWO
static constexpr size_t COND_SELECT
static constexpr size_t ADD
static constexpr size_t SQR_ADD
static constexpr size_t CONSTANT_WITNESS
static constexpr size_t ASSERT_EQUAL
static constexpr size_t SQR
static constexpr size_t COND_NEGATE
static constexpr size_t MSUB_DIV
static constexpr size_t SUBTRACT_WITH_CONSTRAINT
static constexpr size_t DIVIDE
static constexpr size_t SET
static constexpr size_t DIVIDE_WITH_CONSTRAINTS
This class implements the execution of safeuint with an oracle to detect discrepancies.
static size_t execute_CONSTANT_WITNESS(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the constant_witness instruction (push a safeuint witness equal to the constant to the stack)
void assert_not_equal(ExecutionHandler &other)
static size_t execute_SET(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the SET instruction.
static bool_t construct_predicate(Builder *builder, const bool predicate)
static size_t execute_RANDOMSEED(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the RANDOMSEED instruction.
static size_t execute_WITNESS(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the witness instruction (push witness safeuit to the stack)
static size_t execute_SUBTRACT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the subtraction operator instruction.
static size_t execute_ADD_TWO(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the ADD_TWO instruction.
static size_t execute_MADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the MADD instruction.
static ExecutionHandler msub_div(const std::vector< ExecutionHandler > &input_left, const std::vector< ExecutionHandler > &input_right, const ExecutionHandler &divisor, const std::vector< ExecutionHandler > &to_sub)
static size_t execute_MSUB_DIV(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the MSUB_DIV instruction.
static size_t execute_CONSTANT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the constant instruction (push constant safeuint to the stack)
ExecutionHandler conditional_negate(Builder *builder, const bool predicate)
static size_t execute_DIVIDE(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the division operator instruction.
ExecutionHandler madd(const ExecutionHandler &other1, const ExecutionHandler &other2)
ExecutionHandler(bb::fq a, bigfield_t b)
ExecutionHandler(bb::fq &a, bigfield_t &b)
ExecutionHandler operator+(const ExecutionHandler &other)
static size_t execute_ADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the addition operator instruction.
static size_t execute_ASSERT_NOT_EQUAL(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the ASSERT_NOT_EQUAL instruction.
ExecutionHandler conditional_select(Builder *builder, ExecutionHandler &other, const bool predicate)
static size_t execute_COND_NEGATE(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the COND_NEGATE instruction.
ExecutionHandler operator*(const ExecutionHandler &other)
ExecutionHandler(bb::fq a, bigfield_t &b)
static size_t execute_ASSERT_EQUAL(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the ASSERT_EQUAL instruction.
static size_t execute_SQR(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the SQR instruction.
ExecutionHandler operator/(const ExecutionHandler &other)
ExecutionHandler sqr_add(const std::vector< ExecutionHandler > &to_add)
static size_t execute_SQR_ADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the SQR_ADD instruction.
static size_t execute_COND_SELECT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the COND_SELECT instruction.
static ExecutionHandler mult_madd(const std::vector< ExecutionHandler > &input_left, const std::vector< ExecutionHandler > &input_right, const std::vector< ExecutionHandler > &to_add)
ExecutionHandler add_two(const ExecutionHandler &other1, const ExecutionHandler &other2)
ExecutionHandler set(Builder *builder)
ExecutionHandler operator-(const ExecutionHandler &other)
void assert_equal(ExecutionHandler &other)
static size_t execute_MULT_MADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the MULT_MADD instruction.
static size_t execute_MULTIPLY(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the multiply instruction.
A class representing a single fuzzing instruction.
static Instruction generateRandom(T &rng)
Generate a random instruction.
static Instruction mutateInstruction(Instruction instruction, T &rng, HavocSettings &havoc_config)
Mutate a single instruction.
static bb::fq mutateFieldElement(bb::fq e, T &rng, HavocSettings &havoc_config)
Mutate the value of a field element.
Optional subclass that governs limits on the use of certain instructions, since some of them can be t...
static constexpr size_t CONSTANT_WITNESS
static constexpr size_t DIVIDE_WITH_CONSTRAINTS
static constexpr size_t COND_NEGATE
static constexpr size_t SUBTRACT_WITH_CONSTRAINT
static constexpr size_t ASSERT_NOT_EQUAL
static constexpr size_t MULT_MADD
static constexpr size_t RANDOMSEED
static constexpr size_t ASSERT_EQUAL
static constexpr size_t COND_SELECT
Parser class handles the parsing and writing the instructions back to data buffer.
static Instruction parseInstructionArgs(uint8_t *Data)
Parse a single instruction from data.
static void writeInstruction(Instruction &instruction, uint8_t *Data)
Write a single instruction to buffer.
The class parametrizing Bigfield fuzzing instructions, execution, etc.
bb::stdlib::bigfield< Builder, bb::Bn254FqParams > bigfield_t
bb::stdlib::public_witness_t< Builder > public_witness_t
bb::stdlib::field_t< Builder > field_t
std::vector< ExecutionHandler > ExecutionState
bb::stdlib::witness_t< Builder > witness_t
bb::stdlib::bool_t< Builder > bool_t
static bool postProcess(Builder *builder, std::vector< BigFieldBase::ExecutionHandler > &stack)
Check that the resulting values are equal to expected.
Class for quickly deterministically creating new random values. We don't care about distribution much...
Definition fuzzer.hpp:63
void reseed(uint32_t seed)
Definition fuzzer.hpp:75
uint32_t next()
Definition fuzzer.hpp:68
constexpr uint256_t slice(uint64_t start, uint64_t end) const
static bigfield msub_div(const std::vector< bigfield > &mul_left, const std::vector< bigfield > &mul_right, const bigfield &divisor, const std::vector< bigfield > &to_sub, bool enable_divisor_nz_check=true)
static bigfield div_check_denominator_nonzero(const std::vector< bigfield > &numerators, const bigfield &denominator)
static bigfield mult_madd(const std::vector< bigfield > &mul_left, const std::vector< bigfield > &mul_right, const std::vector< bigfield > &to_add, bool fix_remainder_to_zero=false)
uint512_t get_value() const
void assert_is_in_field(std::string const &msg="bigfield::assert_is_in_field") const
static bigfield from_witness(Builder *ctx, const bb::field< bb::Bn254FqParams > &input)
Definition bigfield.hpp:296
bool is_constant() const
Check if the bigfield is constant, i.e. its prime limb is constant.
Definition bigfield.hpp:615
void reduce_mod_target_modulus() const
void assert_equal(const bigfield &other, std::string const &msg="bigfield::assert_equal") const
static bigfield create_from_u512_as_witness(Builder *ctx, const uint512_t &value, const bool can_overflow=false, const size_t maximum_bitlength=0)
Creates a bigfield element from a uint512_t. Bigfield element is constructed as a witness and not a c...
Implements boolean logic in-circuit.
Definition bool.hpp:59
void info(Args... args)
Definition log.hpp:74
Concept for a simple PRNG which returns a uint32_t when next is called.
Definition fuzzer.hpp:125
AluTraceBuilder builder
Definition alu.test.cpp:123
StrictMock< MockContext > context
FF a
FF b
size_t LLVMFuzzerMutate(uint8_t *Data, size_t Size, size_t MaxSize)
Instruction instruction
field< Bn254FqParams > fq
Definition fq.hpp:169
Instruction
Enumeration of VM instructions that can be executed.
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
std::string to_string(bb::avm2::ValueTag tag)
uint8_t add_elements[MULT_MADD_MAXIMUM_ADDED_ELEMENTS]
uint8_t mult_pairs[MULT_MADD_MAXIMUM_MUL_PAIRS *2]
uint8_t add_elements[MULT_MADD_MAXIMUM_ADDED_ELEMENTS]
size_t GEN_LLVM_POST_MUTATION_PROB
Definition fuzzer.hpp:28
static constexpr field get_root_of_unity(size_t subgroup_size) noexcept
static constexpr field one()
static constexpr uint256_t modulus
BB_INLINE constexpr field sqr() const noexcept
static field serialize_from_buffer(const uint8_t *buffer)
static void serialize_to_buffer(const field &value, uint8_t *buffer)
constexpr std::pair< bool, field > sqrt() const noexcept
Compute square root of the field element.
static constexpr field zero()
bb::stdlib::bigfield< Builder, bb::Bn254FqParams > bigfield_t