barretenberg
Loading...
Searching...
No Matches
bigfield.fuzzer.hpp
1#pragma once
2#include "barretenberg/ecc/curves/bn254/fq.hpp"
3#include "barretenberg/numeric/random/engine.hpp"
4#include "barretenberg/numeric/uint256/uint256.hpp"
5#include "barretenberg/stdlib/primitives/bigfield/bigfield.hpp"
6#include "barretenberg/stdlib/primitives/circuit_builders/circuit_builders_fwd.hpp"
7#pragma clang diagnostic push
8// TODO(luke/kesha): Add a comment explaining why we need this ignore and what the solution is.
9#pragma clang diagnostic ignored "-Wc99-designator"
10// This is a global variable, so that the execution handling class could alter it and signal to the input tester
11// that the input should fail
12bool circuit_should_fail = false;
13
14#define HAVOC_TESTING
15// #define DISABLE_DIVISION 1
16#include "barretenberg/common/fuzzer.hpp"
17
18FastRandom VarianceRNG(0);
19// #define DISABLE_DIVISION
20// Enable this definition, when you want to find out the instructions that caused a failure
21// #define SHOW_INFORMATION 1
22
23#ifdef SHOW_INFORMATION
24#define PRINT_SINGLE_ARG_INSTRUCTION(first_index, vector, operation_name, preposition) \
25 { \
26 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
27 << vector[first_index].bigfield.get_value() << ") at " << first_index << " " << preposition \
28 << std::flush; \
29 }
30
31#define PRINT_TWO_ARG_INSTRUCTION(first_index, second_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 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
36 << vector[second_index].bigfield.get_value() << ") at " << second_index << std::flush; \
37 }
38
39#define PRINT_THREE_ARG_INSTRUCTION( \
40 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2) \
41 { \
42 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
43 << vector[first_index].bigfield.get_value() << ") at " << first_index << " " << preposition1 << " " \
44 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
45 << vector[second_index].bigfield.get_value() << ") at " << second_index << " " << preposition2 \
46 << " " << (vector[third_index].bigfield.is_constant() ? "constant(" : "witness(") \
47 << vector[third_index].bigfield.get_value() << ") at " << third_index << std::flush; \
48 }
49#define PRINT_TWO_ARG_ONE_VALUE_INSTRUCTION( \
50 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2) \
51 { \
52 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
53 << vector[first_index].bigfield.get_value() << ":" << vector[first_index].suint.current_max \
54 << ") at " << first_index << " " << preposition1 << " " \
55 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
56 << vector[second_index].bigfield.get_value() << ":" << vector[second_index].suint.current_max \
57 << ") at " << second_index << " " << preposition2 << " " << third_index << std::flush; \
58 }
59
60#define PRINT_TWO_ARG_TWO_VALUES_INSTRUCTION( \
61 first_index, second_index, value1, value2, vector, operation_name, preposition1, preposition2, preposition3) \
62 { \
63 std::cout << operation_name << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
64 << vector[first_index].bigfield.get_value() << ") at " << first_index << " " << preposition1 << " " \
65 << (vector[second_index].bigfield.is_constant() ? "constant(" : "witness(") \
66 << vector[second_index].bigfield.get_value() << ") at " << second_index << " " << preposition2 \
67 << " " << value1 << preposition3 << value2 << std::flush; \
68 }
69
70#define PRINT_SLICE(first_index, lsb, msb, vector) \
71 { \
72 std::cout << "Slice:" \
73 << " " << (vector[first_index].bigfield.is_constant() ? "constant(" : "witness(") \
74 << vector[first_index].bigfield.get_value() << ":" << vector[first_index].suint.current_max \
75 << ") at " << first_index << " " \
76 << "(" << (size_t)lsb << ":" << (size_t)msb << ")" << std::flush; \
77 }
78
79#define PRINT_RESULT(prefix, action, index, value) \
80 { \
81 std::cout << " result(" << value.bigfield.get_value() << ")" << action << index << std::endl << std::flush; \
82 }
83
84#else
85
86#define PRINT_SINGLE_ARG_INSTRUCTION(first_index, vector, operation_name, preposition)
87#define PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, vector, operation_name, preposition)
88
89#define PRINT_TWO_ARG_ONE_VALUE_INSTRUCTION( \
90 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2)
91#define PRINT_TWO_ARG_TWO_VALUES_INSTRUCTION( \
92 first_index, second_index, value1, value2, vector, operation_name, preposition1, preposition2, preposition3)
93
94#define PRINT_THREE_ARG_INSTRUCTION( \
95 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2)
96#define PRINT_RESULT(prefix, action, index, value)
97
98#define PRINT_SLICE(first_index, lsb, msb, vector)
99#endif
100
101#define OPERATION_TYPE_SIZE 1
102
103#define ELEMENT_SIZE (sizeof(fq) + 1)
104#define TWO_IN_ONE_OUT 3
105#define THREE_IN_ONE_OUT 4
106#define SLICE_ARGS_SIZE 6
107
108#define MSUB_DIV_MINIMUM_MUL_PAIRS 1
109#define MSUB_DIV_MAXIMUM_MUL_PAIRS 8
110#define MSUB_DIV_MINIMUM_SUBTRACTED_ELEMENTS 0
111#define MSUB_DIV_MAXIMUM_SUBTRACTED_ELEMENTS 8
112#define MULT_MADD_MINIMUM_MUL_PAIRS 1
113#define MULT_MADD_MAXIMUM_MUL_PAIRS 8
114#define MULT_MADD_MINIMUM_ADDED_ELEMENTS 0
115#define MULT_MADD_MAXIMUM_ADDED_ELEMENTS 8
116#define SQR_ADD_MINIMUM_ADDED_ELEMENTS 0
117#define SQR_ADD_MAXIMUM_ADDED_ELEMENTS 8
122template <typename Builder> class BigFieldBase {
123 private:
124 typedef proof_system::plonk::stdlib::bool_t<Builder> bool_t;
125 typedef proof_system::plonk::stdlib::field_t<Builder> field_t;
126 typedef proof_system::plonk::stdlib::witness_t<Builder> witness_t;
127 typedef proof_system::plonk::stdlib::public_witness_t<Builder> public_witness_t;
128 typedef proof_system::plonk::stdlib::bigfield<Builder, barretenberg::Bn254FqParams> bigfield_t;
129
130 public:
135 class Instruction {
136 public:
137 enum OPCODE {
138 CONSTANT,
139 WITNESS,
140 CONSTANT_WITNESS,
141 ADD,
142 SUBTRACT,
143 MULTIPLY,
144#ifndef DISABLE_DIVISION
145 DIVIDE,
146#endif
147 ADD_TWO,
148 MADD,
149 MULT_MADD,
150 SQR,
151 SQR_ADD,
152 ASSERT_EQUAL,
153 ASSERT_NOT_EQUAL,
154 MSUB_DIV,
155 COND_NEGATE,
156 COND_SELECT,
157 SET,
158 RANDOMSEED,
159 _LAST
160 };
161
162 struct Element {
163 Element(uint64_t v)
164 : value(v)
165 {}
166 fq value;
167 };
168 struct TwoArgs {
169 uint8_t in;
170 uint8_t out;
171 };
172 struct ThreeArgs {
173 uint8_t in1;
174 uint8_t in2;
175 uint8_t out;
176 };
177 struct FourArgs {
178 uint8_t in1;
179 uint8_t in2;
180 uint8_t in3;
181 uint8_t out;
182 };
183 struct FiveArgs {
184 uint8_t in1;
185 uint8_t in2;
186 uint8_t qbs;
187 uint8_t rbs;
188 uint8_t out;
189 };
190 struct MultAddArgs {
191 uint8_t add_elements[MULT_MADD_MAXIMUM_ADDED_ELEMENTS];
192 uint8_t add_elements_count = 0;
193 uint8_t input_index;
194 uint8_t output_index;
195 };
196 struct MultOpArgs {
197 uint8_t mult_pairs[MULT_MADD_MAXIMUM_MUL_PAIRS * 2];
198 uint8_t add_elements[MULT_MADD_MAXIMUM_ADDED_ELEMENTS];
199 uint8_t mult_pairs_count = 1;
200 uint8_t add_elements_count = 0;
201 uint8_t divisor_index;
202 uint8_t output_index;
203 };
204
205 struct SliceArgs {
206 uint8_t in1;
207 uint8_t lsb;
208 uint8_t msb;
209 uint8_t out1;
210 uint8_t out2;
211 uint8_t out3;
212 };
213 union ArgumentContents {
214 ArgumentContents()
215 : randomseed(0)
216 {}
217 uint32_t randomseed;
218 Element element;
219 TwoArgs twoArgs;
220 ThreeArgs threeArgs;
221 FourArgs fourArgs;
222 FiveArgs fiveArgs;
223 SliceArgs sliceArgs;
224 MultOpArgs multOpArgs;
225 MultAddArgs multAddArgs;
226 };
227 // The type of instruction
228 OPCODE id;
229 // Instruction arguments
230 ArgumentContents arguments;
231
239 template <typename T>
240 inline static Instruction generateRandom(T& rng)
241 requires SimpleRng<T>
242 {
243 // Choose which instruction we are going to generate
244 OPCODE instruction_opcode = static_cast<OPCODE>(rng.next() % (OPCODE::_LAST));
245 uint8_t in1, in2, in3, out, mask_size, mult_size, add_size;
246 uint256_t mask, temp;
247 Instruction instr;
248 uint8_t mult_pairs[MULT_MADD_MAXIMUM_MUL_PAIRS * 2] = { 0 };
249 uint8_t add_elements[MULT_MADD_MAXIMUM_ADDED_ELEMENTS > SQR_ADD_MAXIMUM_ADDED_ELEMENTS
250 ? MULT_MADD_MAXIMUM_ADDED_ELEMENTS
251 : SQR_ADD_MAXIMUM_ADDED_ELEMENTS] = { 0 };
252
253 // Depending on instruction
254 switch (instruction_opcode) {
255 case OPCODE::CONSTANT:
256 case OPCODE::WITNESS:
257 case OPCODE::CONSTANT_WITNESS:
258 // If it's a constant or witness, it just pushes data onto the stack to be acted upon
259 // Generate a random field element
260 for (size_t i = 0; i < (sizeof(uint256_t) >> 1); i++) {
261 *(((uint16_t*)&temp) + i) = static_cast<uint16_t>(rng.next() & 0xffff);
262 }
263 // We want small values, too. If we generate randomly, we aren't going to have them, so we also apply a
264 // random mask, which randomizes the logarithm of maximum value
265 mask_size = static_cast<uint8_t>(rng.next() & 0xff);
266 mask = (uint256_t(1) << mask_size) - 1;
267 // Choose the bit range
268 // Return instruction
269 return { .id = instruction_opcode, .arguments.element = Element(static_cast<uint64_t>(temp & mask)) };
270
271 break;
272 case OPCODE::RANDOMSEED:
273 return { .id = instruction_opcode, .arguments.randomseed = rng.next() };
274 break;
275 case OPCODE::SQR:
276 case OPCODE::ASSERT_EQUAL:
277 case OPCODE::ASSERT_NOT_EQUAL:
278 case OPCODE::SET:
279 in1 = static_cast<uint8_t>(rng.next() & 0xff);
280 out = static_cast<uint8_t>(rng.next() & 0xff);
281 return { .id = instruction_opcode, .arguments.twoArgs = { .in = in1, .out = out } };
282 break;
283 case OPCODE::ADD:
284 case OPCODE::SUBTRACT:
285 case OPCODE::MULTIPLY:
286#ifndef DISABLE_DIVISION
287 case OPCODE::DIVIDE:
288#endif
289 case OPCODE::COND_NEGATE:
290 // For two-input-one-output instructions we just randomly pick each argument and generate an instruction
291 // accordingly
292 in1 = static_cast<uint8_t>(rng.next() & 0xff);
293 in2 = static_cast<uint8_t>(rng.next() & 0xff);
294 out = static_cast<uint8_t>(rng.next() & 0xff);
295 return { .id = instruction_opcode, .arguments.threeArgs = { .in1 = in1, .in2 = in2, .out = out } };
296 break;
297 case OPCODE::ADD_TWO:
298 case OPCODE::MADD:
299 case OPCODE::COND_SELECT:
300 // For three-input-one-output instructions we just randomly pick each argument and generate an
301 // instruction accordingly
302 in1 = static_cast<uint8_t>(rng.next() & 0xff);
303 in2 = static_cast<uint8_t>(rng.next() & 0xff);
304 in3 = static_cast<uint8_t>(rng.next() & 0xff);
305 out = static_cast<uint8_t>(rng.next() & 0xff);
306 return { .id = instruction_opcode,
307 .arguments.fourArgs{ .in1 = in1, .in2 = in2, .in3 = in3, .out = out } };
308 break;
309 case OPCODE::MSUB_DIV:
310 instr.arguments.multOpArgs.divisor_index = static_cast<uint8_t>(rng.next() & 0xff);
311 case OPCODE::MULT_MADD:
312 mult_size =
313 MULT_MADD_MINIMUM_MUL_PAIRS +
314 static_cast<uint8_t>(rng.next() % (MULT_MADD_MAXIMUM_MUL_PAIRS - MULT_MADD_MINIMUM_MUL_PAIRS));
315 add_size = MULT_MADD_MINIMUM_ADDED_ELEMENTS +
316 static_cast<uint8_t>(rng.next() %
317 (MULT_MADD_MAXIMUM_ADDED_ELEMENTS - MULT_MADD_MINIMUM_ADDED_ELEMENTS));
318
319 for (size_t i = 0; i < mult_size; i++) {
320 mult_pairs[i * 2] = static_cast<uint8_t>(rng.next() & 0xff);
321 mult_pairs[i * 2 + 1] = static_cast<uint8_t>(rng.next() & 0xff);
322 }
323 for (size_t i = 0; i < add_size; i++) {
324 add_elements[i] = static_cast<uint8_t>(rng.next() & 0xff);
325 }
326 instr.id = instruction_opcode;
327 memcpy(instr.arguments.multOpArgs.mult_pairs, mult_pairs, 2 * MULT_MADD_MAXIMUM_MUL_PAIRS);
328 memcpy(instr.arguments.multOpArgs.add_elements, add_elements, MULT_MADD_MAXIMUM_ADDED_ELEMENTS);
329 instr.arguments.multOpArgs.add_elements_count = add_size;
330 instr.arguments.multOpArgs.mult_pairs_count = mult_size;
331
332 instr.arguments.multOpArgs.output_index = static_cast<uint8_t>(rng.next() & 0xff);
333 return instr;
334 break;
335 case OPCODE::SQR_ADD:
336 add_size = SQR_ADD_MINIMUM_ADDED_ELEMENTS +
337 static_cast<uint8_t>(rng.next() %
338 (SQR_ADD_MAXIMUM_ADDED_ELEMENTS - SQR_ADD_MINIMUM_ADDED_ELEMENTS));
339
340 for (size_t i = 0; i < add_size; i++) {
341 add_elements[i] = static_cast<uint8_t>(rng.next() & 0xff);
342 }
343 instr.id = instruction_opcode;
344 memcpy(instr.arguments.multAddArgs.add_elements, add_elements, SQR_ADD_MAXIMUM_ADDED_ELEMENTS);
345 instr.arguments.multAddArgs.add_elements_count = add_size;
346
347 instr.arguments.multAddArgs.input_index = static_cast<uint8_t>(rng.next() & 0xff);
348 instr.arguments.multAddArgs.output_index = static_cast<uint8_t>(rng.next() & 0xff);
349 return instr;
350 break;
351 default:
352 abort(); // We have missed some instructions, it seems
353 break;
354 }
355 }
356
366 template <typename T>
367 inline static fq mutateFieldElement(fq e, T& rng, HavocSettings& havoc_config)
368 requires SimpleRng<T>
369 {
370 // With a certain probability, we apply changes to the Montgomery form, rather than the plain form. This
371 // has merit, since the computation is performed in montgomery form and comparisons are often performed
372 // in it, too. Libfuzzer comparison tracing logic can then be enabled in Montgomery form
373 bool convert_to_montgomery = (rng.next() % (havoc_config.VAL_MUT_MONTGOMERY_PROBABILITY +
374 havoc_config.VAL_MUT_NON_MONTGOMERY_PROBABILITY)) <
375 havoc_config.VAL_MUT_MONTGOMERY_PROBABILITY;
376 uint256_t value_data;
377 // Conversion at the start
378#define MONT_CONVERSION \
379 if (convert_to_montgomery) { \
380 value_data = uint256_t(e.to_montgomery_form()); \
381 } else { \
382 value_data = uint256_t(e); \
383 }
384 // Inverse conversion at the end
385#define INV_MONT_CONVERSION \
386 if (convert_to_montgomery) { \
387 e = fq(value_data).from_montgomery_form(); \
388 } else { \
389 e = fq(value_data); \
390 }
391
392 // Pick the last value from the mutation distrivution vector
393 const size_t mutation_type_count = havoc_config.value_mutation_distribution.size();
394 // Choose mutation
395 const size_t choice = rng.next() % havoc_config.value_mutation_distribution[mutation_type_count - 1];
396 if (choice < havoc_config.value_mutation_distribution[0]) {
397 // Delegate mutation to libfuzzer (bit/byte mutations, autodictionary, etc)
398 MONT_CONVERSION
399 LLVMFuzzerMutate((uint8_t*)&value_data, sizeof(uint256_t), sizeof(uint256_t));
400 INV_MONT_CONVERSION
401 } else if (choice < havoc_config.value_mutation_distribution[1]) {
402 // Small addition/subtraction
403 if (convert_to_montgomery) {
404 e = e.to_montgomery_form();
405 }
406 if (rng.next() & 1) {
407 value_data = e + fq(rng.next() & 0xff);
408 } else {
409 value_data = e - fq(rng.next() & 0xff);
410 }
411 if (convert_to_montgomery) {
412 e = e.from_montgomery_form();
413 }
414 } else {
415 // Substitute field element with a special value
416 MONT_CONVERSION
417 switch (rng.next() % 9) {
418 case 0:
419 e = fq::zero();
420 break;
421 case 1:
422 e = fq::one();
423 break;
424 case 2:
425 e = -fq::one();
426 break;
427 case 3:
428 e = fq::one().sqrt().second;
429 break;
430 case 4:
431 e = fq::one().sqrt().second.invert();
432 break;
433 case 5:
434 e = fq::get_root_of_unity(8);
435 break;
436 case 6:
437 e = fq(2);
438 break;
439 case 7:
440 e = fq((fq::modulus - 1) / 2);
441 break;
442 case 8:
443 e = fq((fr::modulus));
444 break;
445 default:
446 abort();
447 break;
448 }
449 INV_MONT_CONVERSION
450 }
451 // Return instruction
452 return e;
453 }
463 template <typename T>
464 inline static Instruction mutateInstruction(Instruction instruction, T& rng, HavocSettings& havoc_config)
465 requires SimpleRng<T>
466 {
467#define PUT_RANDOM_BYTE_IF_LUCKY(variable) \
468 if (rng.next() & 1) { \
469 variable = rng.next() & 0xff; \
470 }
471 // Depending on instruction type...
472 switch (instruction.id) {
473 case OPCODE::CONSTANT:
474 case OPCODE::WITNESS:
475 case OPCODE::CONSTANT_WITNESS:
476 // If it represents pushing a value on the stack with a 50% probability randomly sample a bit_range
477 // Maybe mutate the value
478 if (rng.next() & 1) {
479 instruction.arguments.element.value =
480 mutateFieldElement(instruction.arguments.element.value, rng, havoc_config);
481 }
482 break;
483 case OPCODE::SQR:
484 case OPCODE::ASSERT_EQUAL:
485 case OPCODE::ASSERT_NOT_EQUAL:
486 case OPCODE::SET:
487 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.twoArgs.in)
488 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.twoArgs.out)
489 break;
490 case OPCODE::ADD:
491#ifndef DISABLE_DIVISION
492 case OPCODE::DIVIDE:
493#endif
494 case OPCODE::MULTIPLY:
495 case OPCODE::SUBTRACT:
496 case OPCODE::COND_NEGATE:
497 // Randomly sample each of the arguments with 50% probability
498 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.in1)
499 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.in2)
500 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.out)
501 break;
502 case OPCODE::ADD_TWO:
503 case OPCODE::MADD:
504 case OPCODE::COND_SELECT:
505 // Randomly sample each of the arguments with 50% probability
506 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in1)
507 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in2)
508 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in3)
509 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.out)
510 break;
511 case OPCODE::MSUB_DIV:
512 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multOpArgs.divisor_index)
513 case OPCODE::MULT_MADD:
514 if (rng.next() & 1) {
515 // Mutate pair count
516 instruction.arguments.multOpArgs.mult_pairs_count =
517 MULT_MADD_MINIMUM_MUL_PAIRS +
518 static_cast<uint8_t>(rng.next() % (MULT_MADD_MAXIMUM_MUL_PAIRS - MULT_MADD_MINIMUM_MUL_PAIRS));
519 }
520 if (rng.next() & 1) {
521 // Mutate added element count
522 instruction.arguments.multOpArgs.add_elements_count =
523 MULT_MADD_MINIMUM_ADDED_ELEMENTS +
524 static_cast<uint8_t>(rng.next() %
525 (MULT_MADD_MAXIMUM_ADDED_ELEMENTS - MULT_MADD_MINIMUM_ADDED_ELEMENTS));
526 }
527 if (instruction.arguments.multOpArgs.mult_pairs_count && rng.next() & 1) {
528 // Mutate multiplication pairs
529 size_t mut_count = static_cast<uint8_t>(
530 rng.next() % (2 * (size_t)instruction.arguments.multOpArgs.mult_pairs_count));
531
532 for (size_t i = 0; i < mut_count; i++) {
533 auto ind = rng.next() % (2 * (size_t)instruction.arguments.multOpArgs.mult_pairs_count);
534 instruction.arguments.multOpArgs.mult_pairs[ind] = static_cast<uint8_t>(rng.next() & 0xff);
535 }
536 }
537 if (instruction.arguments.multOpArgs.add_elements_count && rng.next() & 1) {
538 // Mutate additions
539 size_t add_mut_count = static_cast<uint8_t>(
540 rng.next() % ((size_t)instruction.arguments.multOpArgs.add_elements_count));
541
542 for (size_t i = 0; i < add_mut_count; i++) {
543 instruction.arguments.multOpArgs
544 .add_elements[rng.next() % ((size_t)instruction.arguments.multOpArgs.add_elements_count)] =
545 static_cast<uint8_t>(rng.next() & 0xff);
546 }
547 }
548 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multOpArgs.output_index)
549 break;
550 case OPCODE::SQR_ADD:
551 if (rng.next() & 1) {
552 // Mutate added element count
553 instruction.arguments.multAddArgs.add_elements_count =
554 SQR_ADD_MINIMUM_ADDED_ELEMENTS +
555 static_cast<uint8_t>(rng.next() %
556 (SQR_ADD_MAXIMUM_ADDED_ELEMENTS - SQR_ADD_MINIMUM_ADDED_ELEMENTS));
557 }
558
559 if (instruction.arguments.multAddArgs.add_elements_count && rng.next() & 1) {
560 // Mutate additions
561 size_t add_mut_count = static_cast<uint8_t>(
562 rng.next() % ((size_t)instruction.arguments.multAddArgs.add_elements_count));
563
564 for (size_t i = 0; i < add_mut_count; i++) {
565 instruction.arguments.multAddArgs
566 .add_elements[rng.next() % ((size_t)instruction.arguments.multAddArgs.add_elements_count)] =
567 static_cast<uint8_t>(rng.next() & 0xff);
568 }
569 }
570 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multAddArgs.input_index)
571 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.multAddArgs.output_index)
572 break;
573 case OPCODE::RANDOMSEED:
574 instruction.arguments.randomseed = rng.next();
575 break;
576 default:
577 abort(); // New instruction encountered
578 break;
579 }
580 // Return mutated instruction
581 return instruction;
582 }
583 };
584 // We use argsizes to both specify the size of data needed to parse the instruction and to signal that the
585 // instruction is enabled (if it is -1,it's disabled )
586 class ArgSizes {
587 public:
588 static constexpr size_t CONSTANT = sizeof(fq);
589 static constexpr size_t WITNESS = sizeof(fq);
590 static constexpr size_t CONSTANT_WITNESS = sizeof(fq);
591 static constexpr size_t SQR = 2;
592 static constexpr size_t ASSERT_EQUAL = 2;
593 static constexpr size_t ASSERT_NOT_EQUAL = 2;
594 static constexpr size_t ADD = 3;
595 static constexpr size_t SUBTRACT = 3;
596 static constexpr size_t MULTIPLY = 3;
597 static constexpr size_t ADD_TWO = static_cast<size_t>(-1);
598#ifndef DISABLE_DIVISION
599 static constexpr size_t DIVIDE = 3;
600#else
601 static constexpr size_t DIVIDE = static_cast<size_t>(-1);
602#endif
603 static constexpr size_t MADD = 4;
604 static constexpr size_t MULT_MADD = sizeof(typename Instruction::MultOpArgs);
605 static constexpr size_t MSUB_DIV = sizeof(typename Instruction::MultOpArgs);
606 static constexpr size_t SQR_ADD = sizeof(typename Instruction::MultAddArgs);
607 static constexpr size_t SUBTRACT_WITH_CONSTRAINT = static_cast<size_t>(-1);
608 static constexpr size_t DIVIDE_WITH_CONSTRAINTS = static_cast<size_t>(-1);
609 static constexpr size_t SLICE = static_cast<size_t>(-1);
610 static constexpr size_t COND_NEGATE = 3;
611 static constexpr size_t COND_SELECT = 4;
612 static constexpr size_t SET = 2;
613 static constexpr size_t RANDOMSEED = sizeof(uint32_t);
614 };
615
621 class InstructionWeights {
622 public:
623 static constexpr size_t CONSTANT = 1;
624 static constexpr size_t WITNESS = 1;
625 static constexpr size_t CONSTANT_WITNESS = 1;
626 static constexpr size_t ADD = 1;
627 static constexpr size_t SUBTRACT = 1;
628 static constexpr size_t MULTIPLY = 2;
629 static constexpr size_t SQR = 2;
630 static constexpr size_t ASSERT_EQUAL = 2;
631 static constexpr size_t ASSERT_NOT_EQUAL = 2;
632 static constexpr size_t ADD_TWO = 0;
633#ifndef DISABLE_DIVISION
634 static constexpr size_t DIVIDE = 16;
635#endif
636 static constexpr size_t MADD = 2;
637 static constexpr size_t MULT_MADD = 3;
638 static constexpr size_t MSUB_DIV = 3;
639 static constexpr size_t SQR_ADD = 2;
640 static constexpr size_t SUBTRACT_WITH_CONSTRAINT = 0;
641 static constexpr size_t DIVIDE_WITH_CONSTRAINTS = 0;
642 static constexpr size_t SLICE = 0;
643 static constexpr size_t COND_NEGATE = 0;
644 static constexpr size_t COND_SELECT = 0;
645 static constexpr size_t SET = 0;
646 static constexpr size_t RANDOMSEED = 0;
647 static constexpr size_t _LIMIT = 64;
648 };
653 class Parser {
654 public:
662 template <typename Instruction::OPCODE opcode> inline static Instruction parseInstructionArgs(uint8_t* Data)
663 {
664 if constexpr (opcode == Instruction::OPCODE::CONSTANT || opcode == Instruction::OPCODE::WITNESS ||
665 opcode == Instruction::OPCODE::CONSTANT_WITNESS) {
666 Instruction instr;
667 instr.id = static_cast<typename Instruction::OPCODE>(opcode);
668 instr.arguments.element.value = fq::serialize_from_buffer(Data);
669 return instr;
670 };
671 if constexpr (opcode == Instruction::OPCODE::RANDOMSEED) {
672 Instruction instr;
673 instr.id = static_cast<typename Instruction::OPCODE>(opcode);
674 memcpy(&instr.arguments.randomseed, Data, sizeof(uint32_t));
675 return instr;
676 };
677 if constexpr (opcode == Instruction::OPCODE::SQR || opcode == Instruction::OPCODE::ASSERT_EQUAL ||
678 opcode == Instruction::OPCODE::ASSERT_NOT_EQUAL || opcode == Instruction::OPCODE::SET) {
679 return { .id = static_cast<typename Instruction::OPCODE>(opcode),
680 .arguments.twoArgs = { .in = *Data, .out = *(Data + 1) } };
681 }
682 if constexpr (opcode == Instruction::OPCODE::ADD || opcode == Instruction::OPCODE::MULTIPLY ||
683#ifndef DISABLE_DIVISION
684 opcode == Instruction::OPCODE::DIVIDE ||
685#endif
686 opcode == Instruction::OPCODE::SUBTRACT || opcode == Instruction::OPCODE::COND_NEGATE) {
687 return { .id = static_cast<typename Instruction::OPCODE>(opcode),
688 .arguments.threeArgs = { .in1 = *Data, .in2 = *(Data + 1), .out = *(Data + 2) } };
689 }
690 if constexpr (opcode == Instruction::OPCODE::MADD || opcode == Instruction::OPCODE::ADD_TWO ||
691 opcode == Instruction::OPCODE::COND_SELECT) {
692
693 return { .id = static_cast<typename Instruction::OPCODE>(opcode),
694 .arguments.fourArgs = {
695 .in1 = *Data, .in2 = *(Data + 1), .in3 = *(Data + 2), .out = *(Data + 3) } };
696 }
697 if constexpr (opcode == Instruction::OPCODE::MULT_MADD || opcode == Instruction::OPCODE::MSUB_DIV) {
698 Instruction mult_madd_or_div;
699 mult_madd_or_div.id = static_cast<typename Instruction::OPCODE>(opcode);
700 memcpy(&mult_madd_or_div.arguments.multOpArgs, Data, sizeof(typename Instruction::MultOpArgs));
701 mult_madd_or_div.arguments.multOpArgs.add_elements_count =
702 mult_madd_or_div.arguments.multOpArgs.add_elements_count % MULT_MADD_MAXIMUM_ADDED_ELEMENTS;
703
704 if (mult_madd_or_div.arguments.multOpArgs.add_elements_count < MULT_MADD_MINIMUM_ADDED_ELEMENTS) {
705
706 mult_madd_or_div.arguments.multOpArgs.add_elements_count = MULT_MADD_MINIMUM_ADDED_ELEMENTS;
707 }
708 mult_madd_or_div.arguments.multOpArgs.mult_pairs_count =
709 mult_madd_or_div.arguments.multOpArgs.mult_pairs_count % MULT_MADD_MAXIMUM_MUL_PAIRS;
710
711 if (mult_madd_or_div.arguments.multOpArgs.mult_pairs_count < MULT_MADD_MINIMUM_MUL_PAIRS) {
712 mult_madd_or_div.arguments.multOpArgs.mult_pairs_count = MULT_MADD_MINIMUM_MUL_PAIRS;
713 }
714 return mult_madd_or_div;
715 }
716 if constexpr (opcode == Instruction::OPCODE::SQR_ADD) {
717 Instruction sqr_add;
718 sqr_add.id = static_cast<typename Instruction::OPCODE>(opcode);
719 memcpy(&sqr_add.arguments.multAddArgs, Data, sizeof(typename Instruction::MultAddArgs));
720 sqr_add.arguments.multAddArgs.add_elements_count =
721 sqr_add.arguments.multAddArgs.add_elements_count % SQR_ADD_MAXIMUM_ADDED_ELEMENTS;
722
723 if (sqr_add.arguments.multOpArgs.add_elements_count < SQR_ADD_MINIMUM_ADDED_ELEMENTS) {
724
725 sqr_add.arguments.multOpArgs.add_elements_count = SQR_ADD_MINIMUM_ADDED_ELEMENTS;
726 }
727 return sqr_add;
728 }
729 }
737 template <typename Instruction::OPCODE instruction_opcode>
738 inline static void writeInstruction(Instruction& instruction, uint8_t* Data)
739 {
740 if constexpr (instruction_opcode == Instruction::OPCODE::CONSTANT ||
741 instruction_opcode == Instruction::OPCODE::WITNESS ||
742 instruction_opcode == Instruction::OPCODE::CONSTANT_WITNESS) {
743 *Data = instruction.id;
744 memcpy(Data + 1,
745 &instruction.arguments.element.value.data[0],
746 sizeof(instruction.arguments.element.value.data));
747 }
748
749 if constexpr (instruction_opcode == Instruction::OPCODE::SQR ||
750 instruction_opcode == Instruction::OPCODE::ASSERT_EQUAL ||
751 instruction_opcode == Instruction::OPCODE::ASSERT_NOT_EQUAL ||
752 instruction_opcode == Instruction::OPCODE::SET) {
753 *Data = instruction.id;
754 *(Data + 1) = instruction.arguments.twoArgs.in;
755 *(Data + 2) = instruction.arguments.twoArgs.out;
756 }
757 if constexpr (instruction_opcode == Instruction::OPCODE::ADD ||
758#ifndef DISABLE_DIVISION
759 instruction_opcode == Instruction::OPCODE::DIVIDE ||
760#endif
761 instruction_opcode == Instruction::OPCODE::MULTIPLY ||
762 instruction_opcode == Instruction::OPCODE::SUBTRACT ||
763 instruction_opcode == Instruction::OPCODE::COND_NEGATE) {
764 *Data = instruction.id;
765 *(Data + 1) = instruction.arguments.threeArgs.in1;
766 *(Data + 2) = instruction.arguments.threeArgs.in2;
767 *(Data + 3) = instruction.arguments.threeArgs.out;
768 }
769 if constexpr (instruction_opcode == Instruction::OPCODE::ADD_TWO ||
770 instruction_opcode == Instruction::OPCODE::MADD ||
771 instruction_opcode == Instruction::OPCODE::COND_SELECT) {
772 *Data = instruction.id;
773 *(Data + 1) = instruction.arguments.fourArgs.in1;
774 *(Data + 2) = instruction.arguments.fourArgs.in2;
775 *(Data + 3) = instruction.arguments.fourArgs.in3;
776 *(Data + 4) = instruction.arguments.fourArgs.out;
777 }
778 if constexpr (instruction_opcode == Instruction::OPCODE::MULT_MADD ||
779 instruction_opcode == Instruction::OPCODE::MSUB_DIV) {
780
781 *Data = instruction.id;
782 memcpy(Data + 1, &instruction.arguments.multOpArgs, sizeof(typename Instruction::MultOpArgs));
783 }
784 if constexpr (instruction_opcode == Instruction::OPCODE::SQR_ADD) {
785
786 *Data = instruction.id;
787 memcpy(Data + 1, &instruction.arguments.multAddArgs, sizeof(typename Instruction::MultAddArgs));
788 }
789 if constexpr (instruction_opcode == Instruction::OPCODE::RANDOMSEED) {
790
791 *Data = instruction.id;
792 memcpy(Data + 1, &instruction.arguments.randomseed, sizeof(uint32_t));
793 }
794 }
795 };
800 class ExecutionHandler {
801 private:
802 static bool_t construct_predicate(Builder* builder, const bool predicate)
803 {
804 /* The context field of a predicate can be nullptr;
805 * in that case, the function that handles the predicate
806 * will use the context of another input parameter
807 */
808 const bool predicate_has_ctx = static_cast<bool>(VarianceRNG.next() % 2);
809
810 return bool_t(predicate_has_ctx ? builder : nullptr, predicate);
811 }
812 bigfield_t bf() const
813 {
814 const bool reconstruct = static_cast<bool>(VarianceRNG.next() % 2);
815
816 if (!reconstruct) {
817 return this->bigfield;
818 }
819
820 return bigfield_t(this->bigfield);
821 }
822 uint256_t bf_u256(void) const
823 {
824 return static_cast<uint256_t>((this->bigfield.get_value() % uint512_t(fq::modulus)).lo);
825 }
826
827 public:
828 fq base;
829 bigfield_t bigfield;
830 ExecutionHandler() = default;
831 ExecutionHandler(fq a, bigfield_t b)
832 : base(a)
833 , bigfield(b)
834 {
835 if (b.get_context() == nullptr) {
836 abort();
837 }
838 if (b.get_value() > b.get_maximum_value()) {
839 abort();
840 }
841 for (auto& limb : b.binary_basis_limbs) {
842 if (limb.maximum_value < limb.element.get_value()) {
843 abort();
844 }
845 }
846 }
847 ExecutionHandler(fq a, bigfield_t& b)
848 : base(a)
849 , bigfield(b)
850 {
851 if (b.get_context() == nullptr) {
852 abort();
853 }
854 if (b.get_value() > b.get_maximum_value()) {
855 abort();
856 }
857 for (auto& limb : b.binary_basis_limbs) {
858 if (limb.maximum_value < limb.element.get_value()) {
859 abort();
860 }
861 }
862 }
863 ExecutionHandler(fq& a, bigfield_t& b)
864 : base(a)
865 , bigfield(b)
866 {
867 if (b.get_context() == nullptr) {
868 abort();
869 }
870 if (b.get_value() > b.get_maximum_value()) {
871 abort();
872 }
873 for (auto& limb : b.binary_basis_limbs) {
874 if (limb.maximum_value < limb.element.get_value()) {
875 abort();
876 }
877 }
878 }
879 ExecutionHandler operator+(const ExecutionHandler& other)
880 {
881 return ExecutionHandler(this->base + other.base, this->bf() + other.bf());
882 }
883 ExecutionHandler operator-(const ExecutionHandler& other)
884 {
885 return ExecutionHandler(this->base - other.base, this->bf() - other.bf());
886 }
887 ExecutionHandler operator*(const ExecutionHandler& other)
888 {
889 return ExecutionHandler(this->base * other.base, this->bf() * other.bf());
890 }
891 ExecutionHandler sqr() { return ExecutionHandler(this->base.sqr(), this->bf().sqr()); }
892 ExecutionHandler operator/(const ExecutionHandler& other)
893 {
894 if (other.bf().get_value() == 0) {
895 circuit_should_fail = true;
896 }
897 /* Avoid division by zero of the reference variable */
898 const auto divisor = other.base != 0 ? other.base : 1;
899 switch (VarianceRNG.next() % 3) {
900 case 0:
901 return ExecutionHandler(this->base / divisor, this->bf() / other.bf());
902 case 1:
903 return ExecutionHandler(this->base / divisor,
904 bigfield_t::div_check_denominator_nonzero({ this->bf() }, other.bf()));
905 case 2: {
906 /* Construct 'numerators' such that its sum equals this->base */
907
908 fq v = 0;
909 std::vector<bigfield_t> numerators;
910 while (v != this->base) {
911 const auto add =
912 static_cast<uint256_t>(fq::random_element()) % (static_cast<uint256_t>(this->base - v) + 1);
913 numerators.push_back(bigfield_t(this->bigfield.context, fq(add)));
914 v += add;
915 }
916
917 return ExecutionHandler(this->base / divisor,
918 /* Multi-numerator division */
919 bigfield_t::div_check_denominator_nonzero(numerators, other.bf()));
920 }
921 default:
922 abort();
923 }
924 }
925
926 ExecutionHandler madd(const ExecutionHandler& other1, const ExecutionHandler& other2)
927 {
928
929 return ExecutionHandler(this->base * other1.base + other2.base,
930 this->bf().madd(other1.bigfield, { other2.bigfield }));
931 }
932 ExecutionHandler sqr_add(const std::vector<ExecutionHandler>& to_add)
933 {
934 std::vector<bigfield_t> to_add_bf;
935 fq accumulator = this->base.sqr();
936 for (size_t i = 0; i < to_add.size(); i++) {
937 to_add_bf.push_back(to_add[i].bigfield);
938 accumulator += to_add[i].base;
939 }
940 return ExecutionHandler(accumulator, this->bf().sqradd(to_add_bf));
941 }
942
943 static ExecutionHandler mult_madd(const std::vector<ExecutionHandler>& input_left,
944 const std::vector<ExecutionHandler>& input_right,
945 const std::vector<ExecutionHandler>& to_add)
946 {
947 std::vector<bigfield_t> input_left_bf;
948 std::vector<bigfield_t> input_right_bf;
949 std::vector<bigfield_t> to_add_bf;
950 fq accumulator = fq::zero();
951 for (size_t i = 0; i < input_left.size(); i++) {
952 input_left_bf.push_back(input_left[i].bigfield);
953 input_right_bf.push_back(input_right[i].bigfield);
954 accumulator += input_left[i].base * input_right[i].base;
955 }
956 for (size_t i = 0; i < to_add.size(); i++) {
957 to_add_bf.push_back(to_add[i].bigfield);
958 accumulator += to_add[i].base;
959 }
960 return ExecutionHandler(accumulator, bigfield_t::mult_madd(input_left_bf, input_right_bf, to_add_bf));
961 }
962 static ExecutionHandler msub_div(const std::vector<ExecutionHandler>& input_left,
963 const std::vector<ExecutionHandler>& input_right,
964 const ExecutionHandler& divisor,
965 const std::vector<ExecutionHandler>& to_sub)
966 {
967 std::vector<bigfield_t> input_left_bf;
968 std::vector<bigfield_t> input_right_bf;
969 std::vector<bigfield_t> to_sub_bf;
970 fq accumulator = fq::zero();
971 for (size_t i = 0; i < input_left.size(); i++) {
972 input_left_bf.push_back(input_left[i].bigfield);
973 input_right_bf.push_back(input_right[i].bigfield);
974 accumulator -= input_left[i].base * input_right[i].base;
975 }
976 for (size_t i = 0; i < to_sub.size(); i++) {
977 to_sub_bf.push_back(to_sub[i].bigfield);
978 accumulator -= to_sub[i].base;
979 }
980 /* Avoid division by zero of the reference variable */
981 if (divisor.base != 0) {
982 accumulator /= divisor.base;
983 }
984 const bool enable_divisor_nz_check = static_cast<bool>(VarianceRNG.next() % 2);
985 return ExecutionHandler(
986 accumulator,
987 bigfield_t::msub_div(
988 input_left_bf, input_right_bf, divisor.bigfield, to_sub_bf, enable_divisor_nz_check));
989 }
990 // assert_equal uses assert_is_in_field in some cases, so we don't need to check that separately
991 void assert_equal(ExecutionHandler& other)
992 {
993 if (other.bf().is_constant()) {
994 if (this->bf().is_constant()) {
995 // Assert equal does nothing in this case
996 return;
997 } else {
998 /* Operate on this->bigfield rather than this->bf() to prevent
999 * that assert_is_in_field is called on a different object than
1000 * assert_equal.
1001 *
1002 * See also: https://github.com/AztecProtocol/aztec2-internal/issues/1242
1003 */
1004 this->bigfield.assert_is_in_field();
1005 auto to_add = bigfield_t(this->bigfield.context, uint256_t(this->base - other.base));
1006 this->bigfield.assert_equal(other.bf() + to_add);
1007 }
1008 } else {
1009 if (this->bf().is_constant()) {
1010 auto to_add = bigfield_t(this->bf().context, uint256_t(this->base - other.base));
1011 auto new_el = other.bf() + to_add;
1012 new_el.assert_is_in_field();
1013 this->bf().assert_equal(new_el);
1014 } else {
1015 auto to_add = bigfield_t(this->bf().context, uint256_t(this->base - other.base));
1016 this->bf().assert_equal(other.bf() + to_add);
1017 }
1018 }
1019 }
1020
1021 void assert_not_equal(ExecutionHandler& other)
1022 {
1023 if (this->base == other.base) {
1024 return;
1025 } else {
1026 this->bf().assert_is_not_equal(other.bf());
1027 }
1028 }
1029
1030 ExecutionHandler conditional_negate(Builder* builder, const bool predicate)
1031 {
1032 return ExecutionHandler(predicate ? -(this->base) : this->base,
1033 this->bf().conditional_negate(construct_predicate(builder, predicate)));
1034 }
1035
1036 ExecutionHandler conditional_select(Builder* builder, ExecutionHandler& other, const bool predicate)
1037 {
1038 return ExecutionHandler(predicate ? other.base : this->base,
1039 this->bf().conditional_select(other.bf(), construct_predicate(builder, predicate)));
1040 }
1041 /* Explicit re-instantiation using the various bigfield_t constructors */
1042 ExecutionHandler set(Builder* builder)
1043 {
1044 /* Invariant check */
1045 if (this->bigfield.get_value() > this->bigfield.get_maximum_value()) {
1046 std::cerr << "bigfield value is larger than its maximum" << std::endl;
1047 abort();
1048 }
1049
1050 switch (VarianceRNG.next() % 6) {
1051 case 0:
1052 /* Construct via bigfield_t */
1053 return ExecutionHandler(this->base, bigfield_t(this->bigfield));
1054 case 1:
1055 /* Construct via uint256_t */
1056 return ExecutionHandler(this->base, bigfield_t(builder, bf_u256()));
1057 case 2:
1058 /* Construct via byte_array */
1059 /*
1060 * Bug: https://github.com/AztecProtocol/aztec2-internal/issues/1496
1061 *
1062 * Remove of change this invocation if that issue is a false positive */
1063 return ExecutionHandler(this->base, bigfield_t(this->bigfield.to_byte_array()));
1064 case 3: {
1065 const uint256_t u256 = bf_u256();
1066 const uint256_t u256_lo = u256.slice(0, bigfield_t::NUM_LIMB_BITS * 2);
1067 const uint256_t u256_hi = u256.slice(bigfield_t::NUM_LIMB_BITS * 2, bigfield_t::NUM_LIMB_BITS * 4);
1068 const field_t field_lo(builder, u256_lo);
1069 const field_t field_hi(builder, u256_hi);
1070
1071 /* Construct via two field_t's */
1072 return ExecutionHandler(this->base, bigfield_t(field_lo, field_hi));
1073 }
1074 case 4: {
1075 /* Invoke assignment operator */
1076
1077 bigfield_t bf_new(builder);
1078 bf_new = bf();
1079
1080 return ExecutionHandler(this->base, bigfield_t(bf_new));
1081 }
1082 case 5: {
1083 /* Invoke move constructor */
1084 auto bf_copy = bf();
1085
1086 return ExecutionHandler(this->base, bigfield_t(std::move(bf_copy)));
1087 }
1088 default:
1089 abort();
1090 }
1091 }
1092
1101 static inline size_t execute_CONSTANT(Builder* builder,
1102 std::vector<ExecutionHandler>& stack,
1103 Instruction& instruction)
1104 {
1105 (void)builder;
1106 stack.push_back(ExecutionHandler(instruction.arguments.element.value,
1107 bigfield_t(builder, instruction.arguments.element.value)));
1108#ifdef SHOW_INFORMATION
1109 std::cout << "Pushed constant value " << instruction.arguments.element.value << " to position "
1110 << stack.size() - 1 << std::endl;
1111#endif
1112 return 0;
1113 }
1114
1123 static inline size_t execute_WITNESS(Builder* builder,
1124 std::vector<ExecutionHandler>& stack,
1125 Instruction& instruction)
1126 {
1127
1128 // THis is strange
1129 stack.push_back(
1130 ExecutionHandler(instruction.arguments.element.value,
1131 bigfield_t::from_witness(builder, fq(instruction.arguments.element.value))));
1132 // stack.push_back(
1133 // bigfield_t::create_from_u512_as_witness(builder,
1134 // uint256_t(instruction.arguments.element.value)));
1135
1136#ifdef SHOW_INFORMATION
1137 std::cout << "Pushed witness value " << instruction.arguments.element.value << " to position "
1138 << stack.size() - 1 << std::endl;
1139#endif
1140 return 0;
1141 }
1142
1152 static inline size_t execute_CONSTANT_WITNESS(Builder* builder,
1153 std::vector<ExecutionHandler>& stack,
1154 Instruction& instruction)
1155 {
1156 stack.push_back(ExecutionHandler(
1157 instruction.arguments.element.value,
1158 bigfield_t::create_from_u512_as_witness(builder, uint256_t(instruction.arguments.element.value))));
1159#ifdef SHOW_INFORMATION
1160 std::cout << "Pushed constant witness value " << instruction.arguments.element.value << " to position "
1161 << stack.size() - 1 << std::endl;
1162#endif
1163 return 0;
1164 }
1173 static inline size_t execute_MULTIPLY(Builder* builder,
1174 std::vector<ExecutionHandler>& stack,
1175 Instruction& instruction)
1176 {
1177
1178 (void)builder;
1179 if (stack.size() == 0) {
1180 return 1;
1181 }
1182 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1183 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1184 size_t output_index = instruction.arguments.threeArgs.out;
1185
1186 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Multiplying", "*")
1187
1188 ExecutionHandler result;
1189 result = stack[first_index] * stack[second_index];
1190 // If the output index is larger than the number of elements in stack, append
1191 if (output_index >= stack.size()) {
1192 PRINT_RESULT("", "pushed to ", stack.size(), result)
1193 stack.push_back(result);
1194 } else {
1195
1196 PRINT_RESULT("", "saved to ", output_index, result)
1197 stack[output_index] = result;
1198 }
1199 return 0;
1200 };
1209 static inline size_t execute_ADD(Builder* builder,
1210 std::vector<ExecutionHandler>& stack,
1211 Instruction& instruction)
1212 {
1213 (void)builder;
1214 if (stack.size() == 0) {
1215 return 1;
1216 }
1217 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1218 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1219 size_t output_index = instruction.arguments.threeArgs.out;
1220
1221 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Adding", "+")
1222
1223 ExecutionHandler result;
1224 result = stack[first_index] + stack[second_index];
1225 // If the output index is larger than the number of elements in stack, append
1226 if (output_index >= stack.size()) {
1227 PRINT_RESULT("", "pushed to ", stack.size(), result)
1228 stack.push_back(result);
1229 } else {
1230
1231 PRINT_RESULT("", "saved to ", output_index, result)
1232 stack[output_index] = result;
1233 }
1234 return 0;
1235 };
1236
1245 static inline size_t execute_SQR(Builder* builder,
1246 std::vector<ExecutionHandler>& stack,
1247 Instruction& instruction)
1248 {
1249 (void)builder;
1250 if (stack.size() == 0) {
1251 return 1;
1252 }
1253 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1254 size_t output_index = instruction.arguments.twoArgs.out;
1255
1256 PRINT_SINGLE_ARG_INSTRUCTION(first_index, stack, "Squaring", "squared")
1257
1258 ExecutionHandler result;
1259 result = stack[first_index].sqr();
1260 // If the output index is larger than the number of elements in stack, append
1261 if (output_index >= stack.size()) {
1262 PRINT_RESULT("", "pushed to ", stack.size(), result)
1263 stack.push_back(result);
1264 } else {
1265
1266 PRINT_RESULT("", "saved to ", output_index, result)
1267 stack[output_index] = result;
1268 }
1269 return 0;
1270 };
1271
1280 static inline size_t execute_ASSERT_EQUAL(Builder* builder,
1281 std::vector<ExecutionHandler>& stack,
1282 Instruction& instruction)
1283 {
1284 (void)builder;
1285 if (stack.size() == 0) {
1286 return 1;
1287 }
1288 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1289 size_t second_index = instruction.arguments.twoArgs.out % stack.size();
1290
1291 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "ASSERT_EQUAL", "== something + ")
1292#ifdef SHOW_INFORMATION
1293 std::cout << std::endl;
1294#endif
1295
1296 stack[first_index].assert_equal(stack[second_index]);
1297 return 0;
1298 };
1299
1308 static inline size_t execute_ASSERT_NOT_EQUAL(Builder* builder,
1309 std::vector<ExecutionHandler>& stack,
1310 Instruction& instruction)
1311 {
1312 (void)builder;
1313 if (stack.size() == 0) {
1314 return 1;
1315 }
1316 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1317 size_t second_index = instruction.arguments.twoArgs.out % stack.size();
1318
1319 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "ASSERT_NOT_EQUAL", "!=")
1320#ifdef SHOW_INFORMATION
1321 std::cout << std::endl;
1322#endif
1323
1324 // We have an assert that is triggered for this case
1325 if (stack[first_index].bigfield.is_constant() && stack[second_index].bigfield.is_constant()) {
1326 return 0;
1327 }
1328 stack[first_index].assert_not_equal(stack[second_index]);
1329 return 0;
1330 };
1331
1340 static inline size_t execute_SUBTRACT(Builder* builder,
1341 std::vector<ExecutionHandler>& stack,
1342 Instruction& instruction)
1343 {
1344 (void)builder;
1345 if (stack.size() == 0) {
1346 return 1;
1347 }
1348 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1349 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1350 size_t output_index = instruction.arguments.threeArgs.out;
1351
1352 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Subtracting", "-")
1353
1354 ExecutionHandler result;
1355 result = stack[first_index] - stack[second_index];
1356 // If the output index is larger than the number of elements in stack, append
1357 if (output_index >= stack.size()) {
1358 PRINT_RESULT("", "pushed to ", stack.size(), result)
1359 stack.push_back(result);
1360 } else {
1361
1362 PRINT_RESULT("", "saved to ", output_index, result)
1363 stack[output_index] = result;
1364 }
1365 return 0;
1366 };
1375 static inline size_t execute_DIVIDE(Builder* builder,
1376 std::vector<ExecutionHandler>& stack,
1377 Instruction& instruction)
1378 {
1379 (void)builder;
1380 if (stack.size() == 0) {
1381 return 1;
1382 }
1383 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1384 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
1385 size_t output_index = instruction.arguments.threeArgs.out;
1386
1387 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Dividing", "/")
1388
1389 ExecutionHandler result;
1390 if (fq((stack[second_index].bigfield.get_value() % fq::modulus).lo) == 0) {
1391 return 0; // This is not handled by bigfield
1392 }
1393 // TODO: FIX THIS. I can't think of an elegant fix for this bigfield issue right now
1394 // if (fq((stack[first_index].bigfield.get_value() % fq::modulus).lo) == 0) {
1395 // return 0;
1396 // }
1397 result = stack[first_index] / stack[second_index];
1398 // If the output index is larger than the number of elements .in stack, append
1399 if (output_index >= stack.size()) {
1400 PRINT_RESULT("", "pushed to ", stack.size(), result)
1401 stack.push_back(result);
1402 } else {
1403
1404 PRINT_RESULT("", "saved to ", output_index, result)
1405 stack[output_index] = result;
1406 }
1407 return 0;
1408 };
1418 static inline size_t execute_MADD(Builder* builder,
1419 std::vector<ExecutionHandler>& stack,
1420 Instruction& instruction)
1421 {
1422 (void)builder;
1423 if (stack.size() == 0) {
1424 return 1;
1425 }
1426 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1427 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1428 size_t third_index = instruction.arguments.fourArgs.in3 % stack.size();
1429 size_t output_index = instruction.arguments.fourArgs.out;
1430 PRINT_THREE_ARG_INSTRUCTION(first_index, second_index, third_index, stack, "MADD:", "*", "+")
1431
1432 ExecutionHandler result;
1433 result = stack[first_index].madd(stack[second_index], stack[third_index]);
1434 // If the output index is larger than the number of elements in stack, append
1435 if (output_index >= stack.size()) {
1436 PRINT_RESULT("", "pushed to ", stack.size(), result)
1437 stack.push_back(result);
1438 } else {
1439
1440 PRINT_RESULT("", "saved to ", output_index, result)
1441 stack[output_index] = result;
1442 }
1443 return 0;
1444 };
1454 static inline size_t execute_MULT_MADD(Builder* builder,
1455 std::vector<ExecutionHandler>& stack,
1456 Instruction& instruction)
1457 {
1458 (void)builder;
1459 if (stack.size() == 0) {
1460 return 1;
1461 }
1462 std::vector<ExecutionHandler> input_left;
1463 std::vector<ExecutionHandler> input_right;
1464 std::vector<ExecutionHandler> to_add;
1465#ifdef SHOW_INFORMATION
1466 std::cout << "MULT_MADD:" << std::endl;
1467 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1468 size_t index_left = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size();
1469 size_t index_right = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size();
1470 std::cout << (stack[index_left].bigfield.is_constant() ? "Constant( " : "Witness( ")
1471 << stack[index_left].bigfield.get_value() << ") at " << index_left << " * ";
1472 std::cout << (stack[index_right].bigfield.is_constant() ? "Constant( " : "Witness( ")
1473 << stack[index_right].bigfield.get_value() << ") at " << index_right;
1474 if (i == (instruction.arguments.multOpArgs.mult_pairs_count - 1) &&
1475 instruction.arguments.multOpArgs.add_elements_count == 0) {
1476 std::cout << std::endl;
1477 } else {
1478 std::cout << " + " << std::endl;
1479 }
1480 }
1481 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1482 size_t add_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1483 std::cout << (stack[add_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1484 << stack[add_index].bigfield.get_value() << ") at " << add_index;
1485 if (i == (instruction.arguments.multOpArgs.add_elements_count - 1)) {
1486 std::cout << std::endl;
1487 } else {
1488 std::cout << " + " << std::endl;
1489 }
1490 }
1491#endif
1492 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1493 input_left.push_back(stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size()]);
1494 input_right.push_back(
1495 stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size()]);
1496 }
1497
1498 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1499 auto element_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1500 to_add.push_back(stack[element_index]);
1501 }
1502 size_t output_index = (size_t)instruction.arguments.multOpArgs.output_index;
1503
1504 ExecutionHandler result;
1505 result = ExecutionHandler::mult_madd(input_left, input_right, to_add);
1506 // If the output index is larger than the number of elements in stack, append
1507 if (output_index >= stack.size()) {
1508 PRINT_RESULT("", "pushed to ", stack.size(), result)
1509 stack.push_back(result);
1510 } else {
1511
1512 PRINT_RESULT("", "saved to ", output_index, result)
1513 stack[output_index] = result;
1514 }
1515 return 0;
1516 };
1517
1527 static inline size_t execute_MSUB_DIV(Builder* builder,
1528 std::vector<ExecutionHandler>& stack,
1529 Instruction& instruction)
1530 {
1531 (void)builder;
1532 if (stack.size() == 0) {
1533 return 1;
1534 }
1535 std::vector<ExecutionHandler> input_left;
1536 std::vector<ExecutionHandler> input_right;
1537 std::vector<ExecutionHandler> to_sub;
1538 size_t divisor_index = instruction.arguments.multOpArgs.divisor_index % stack.size();
1539#ifdef SHOW_INFORMATION
1540
1541 std::cout << "MSUB_DIV:" << std::endl;
1542 std::cout << "- (";
1543 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1544 size_t index_left = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size();
1545 size_t index_right = (size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size();
1546 std::cout << (stack[index_left].bigfield.is_constant() ? "Constant( " : "Witness( ")
1547 << stack[index_left].bigfield.get_value() << ") at " << index_left << " * ";
1548 std::cout << (stack[index_right].bigfield.is_constant() ? "Constant( " : "Witness( ")
1549 << stack[index_right].bigfield.get_value() << ") at " << index_right;
1550 if (i == (instruction.arguments.multOpArgs.mult_pairs_count - 1) &&
1551 instruction.arguments.multOpArgs.add_elements_count == 0) {
1552 std::cout << std::endl;
1553 } else {
1554 std::cout << " + " << std::endl;
1555 }
1556 }
1557 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1558 size_t add_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1559 std::cout << (stack[add_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1560 << stack[add_index].bigfield.get_value() << ") at " << add_index;
1561 if (i == (instruction.arguments.multOpArgs.add_elements_count - 1)) {
1562 std::cout << std::endl;
1563 } else {
1564 std::cout << " + " << std::endl;
1565 }
1566 }
1567 std::cout << ") / " << std::endl;
1568 std::cout << (stack[divisor_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1569 << stack[divisor_index].bigfield.get_value() << ") at " << divisor_index << std::endl;
1570
1571#endif
1572 if (fq((stack[divisor_index].bigfield.get_value() % fq::modulus).lo) == 0) {
1573 return 0; // This is not handled by bigfield by default, need to enable check
1574 }
1575 for (size_t i = 0; i < instruction.arguments.multOpArgs.mult_pairs_count; i++) {
1576 input_left.push_back(stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i] % stack.size()]);
1577 input_right.push_back(
1578 stack[(size_t)instruction.arguments.multOpArgs.mult_pairs[2 * i + 1] % stack.size()]);
1579 }
1580
1581 for (size_t i = 0; i < instruction.arguments.multOpArgs.add_elements_count; i++) {
1582 auto element_index = (size_t)instruction.arguments.multOpArgs.add_elements[i] % stack.size();
1583 to_sub.push_back(stack[element_index]);
1584 }
1585 size_t output_index = (size_t)instruction.arguments.multOpArgs.output_index;
1586
1587 ExecutionHandler result;
1588 result = ExecutionHandler::msub_div(input_left, input_right, stack[divisor_index], to_sub);
1589 // If the output index is larger than the number of elements in stack, append
1590 if (output_index >= stack.size()) {
1591 PRINT_RESULT("", "pushed to ", stack.size(), result)
1592 stack.push_back(result);
1593 } else {
1594
1595 PRINT_RESULT("", "saved to ", output_index, result)
1596 stack[output_index] = result;
1597 }
1598 return 0;
1599 };
1600
1610 static inline size_t execute_SQR_ADD(Builder* builder,
1611 std::vector<ExecutionHandler>& stack,
1612 Instruction& instruction)
1613 {
1614 (void)builder;
1615 if (stack.size() == 0) {
1616 return 1;
1617 }
1618 std::vector<ExecutionHandler> to_add;
1619
1620 size_t input_index = (size_t)instruction.arguments.multAddArgs.input_index % stack.size();
1621#ifdef SHOW_INFORMATION
1622 std::cout << "SQR_ADD:" << std::endl;
1623 std::cout << (stack[input_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1624 << stack[input_index].bigfield.get_value() << ") at " << input_index << " squared ";
1625 if (instruction.arguments.multAddArgs.add_elements_count == 0) {
1626 std::cout << std::endl;
1627 } else {
1628 std::cout << "+" << std::endl;
1629 }
1630
1631 for (size_t i = 0; i < instruction.arguments.multAddArgs.add_elements_count; i++) {
1632 size_t add_index = (size_t)instruction.arguments.multAddArgs.add_elements[i] % stack.size();
1633 std::cout << (stack[add_index].bigfield.is_constant() ? "Constant( " : "Witness( ")
1634 << stack[add_index].bigfield.get_value() << ") at " << add_index;
1635 if (i == (instruction.arguments.multOpArgs.add_elements_count - 1)) {
1636 std::cout << std::endl;
1637 } else {
1638 std::cout << " + " << std::endl;
1639 }
1640 }
1641#endif
1642
1643 for (size_t i = 0; i < instruction.arguments.multAddArgs.add_elements_count; i++) {
1644 auto element_index = (size_t)instruction.arguments.multAddArgs.add_elements[i] % stack.size();
1645 to_add.push_back(stack[element_index]);
1646 }
1647 size_t output_index = (size_t)instruction.arguments.multAddArgs.output_index;
1648
1649 ExecutionHandler result;
1650 result = stack[input_index].sqr_add(to_add);
1651 // If the output index is larger than the number of elements in stack, append
1652 if (output_index >= stack.size()) {
1653 PRINT_RESULT("", "pushed to ", stack.size(), result)
1654 stack.push_back(result);
1655 } else {
1656
1657 PRINT_RESULT("", "saved to ", output_index, result)
1658 stack[output_index] = result;
1659 }
1660 return 0;
1661 };
1670 static inline size_t execute_COND_NEGATE(Builder* builder,
1671 std::vector<ExecutionHandler>& stack,
1672 Instruction& instruction)
1673 {
1674 (void)builder;
1675 if (stack.size() == 0) {
1676 return 1;
1677 }
1678 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
1679 size_t output_index = instruction.arguments.threeArgs.out % stack.size();
1680 bool predicate = instruction.arguments.threeArgs.in2 % 2;
1681 ExecutionHandler result;
1682 result = stack[first_index].conditional_negate(builder, predicate);
1683 // If the output index is larger than the number of elements in stack, append
1684 if (output_index >= stack.size()) {
1685 PRINT_RESULT("", "pushed to ", stack.size(), result)
1686 stack.push_back(result);
1687 } else {
1688
1689 PRINT_RESULT("", "saved to ", output_index, result)
1690 stack[output_index] = result;
1691 }
1692 return 0;
1693 };
1694
1703 static inline size_t execute_COND_SELECT(Builder* builder,
1704 std::vector<ExecutionHandler>& stack,
1705 Instruction& instruction)
1706 {
1707 (void)builder;
1708 if (stack.size() == 0) {
1709 return 1;
1710 }
1711 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1712 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1713 size_t output_index = instruction.arguments.fourArgs.out % stack.size();
1714 bool predicate = instruction.arguments.fourArgs.in3 % 2;
1715
1716 ExecutionHandler result;
1717 result = stack[first_index].conditional_select(builder, stack[second_index], predicate);
1718 // If the output index is larger than the number of elements in stack, append
1719 if (output_index >= stack.size()) {
1720 PRINT_RESULT("", "pushed to ", stack.size(), result)
1721 stack.push_back(result);
1722 } else {
1723
1724 PRINT_RESULT("", "saved to ", output_index, result)
1725 stack[output_index] = result;
1726 }
1727 return 0;
1728 };
1737 static inline size_t execute_SET(Builder* builder,
1738 std::vector<ExecutionHandler>& stack,
1739 Instruction& instruction)
1740 {
1741 (void)builder;
1742 if (stack.size() == 0) {
1743 return 1;
1744 }
1745 size_t first_index = instruction.arguments.twoArgs.in % stack.size();
1746 size_t output_index = instruction.arguments.twoArgs.out;
1747 ExecutionHandler result;
1748 result = stack[first_index].set(builder);
1749 // If the output index is larger than the number of elements in stack, append
1750 if (output_index >= stack.size()) {
1751 stack.push_back(result);
1752 } else {
1753 stack[output_index] = result;
1754 }
1755 return 0;
1756 };
1765 static inline size_t execute_RANDOMSEED(Builder* builder,
1766 std::vector<ExecutionHandler>& stack,
1767 Instruction& instruction)
1768 {
1769 (void)builder;
1770 (void)stack;
1771
1772 VarianceRNG.reseed(instruction.arguments.randomseed);
1773 return 0;
1774 };
1775 };
1776
1780 typedef std::vector<ExecutionHandler> ExecutionState;
1790 inline static bool postProcess(Builder* builder, std::vector<BigFieldBase::ExecutionHandler>& stack)
1791 {
1792 (void)builder;
1793 for (size_t i = 0; i < stack.size(); i++) {
1794 auto element = stack[i];
1795 if (fq((element.bigfield.get_value() % uint512_t(fq::modulus)).lo) != element.base) {
1796 std::cerr << "Failed at " << i << " with actual value " << element.base << " and value in bigfield "
1797 << element.bigfield.get_value() << std::endl;
1798 return false;
1799 }
1800 }
1801 return true;
1802 }
1803};
1804
1805#ifdef HAVOC_TESTING
1806
1807extern "C" int LLVMFuzzerInitialize(int* argc, char*** argv)
1808{
1809 (void)argc;
1810 (void)argv;
1811 // These are the settings, optimized for the safeuint class (under them, fuzzer reaches maximum expected
1812 // coverage in 40 seconds)
1813 fuzzer_havoc_settings = HavocSettings{
1814 .GEN_LLVM_POST_MUTATION_PROB = 30, // Out of 200
1815 .GEN_MUTATION_COUNT_LOG = 5, // -Fully checked
1816 .GEN_STRUCTURAL_MUTATION_PROBABILITY = 300, // Fully checked
1817 .GEN_VALUE_MUTATION_PROBABILITY = 700, // Fully checked
1818 .ST_MUT_DELETION_PROBABILITY = 100, // Fully checked
1819 .ST_MUT_DUPLICATION_PROBABILITY = 80, // Fully checked
1820 .ST_MUT_INSERTION_PROBABILITY = 120, // Fully checked
1821 .ST_MUT_MAXIMUM_DELETION_LOG = 6, // 2 because of limit
1822 .ST_MUT_MAXIMUM_DUPLICATION_LOG = 2, // -Fully checked
1823 .ST_MUT_SWAP_PROBABILITY = 50, // Fully checked
1824 .VAL_MUT_LLVM_MUTATE_PROBABILITY = 250, // Fully checked
1825 .VAL_MUT_MONTGOMERY_PROBABILITY = 130, // Fully checked
1826 .VAL_MUT_NON_MONTGOMERY_PROBABILITY = 50, // Fully checked
1827 .VAL_MUT_SMALL_ADDITION_PROBABILITY = 110, // Fully checked
1828 .VAL_MUT_SPECIAL_VALUE_PROBABILITY = 130 // Fully checked
1829
1830 };
1836 /*
1837 std::random_device rd;
1838 std::uniform_int_distribution<uint64_t> dist(0, ~(uint64_t)(0));
1839 srandom(static_cast<unsigned int>(dist(rd)));
1840
1841 fuzzer_havoc_settings =
1842 HavocSettings{ .GEN_MUTATION_COUNT_LOG = static_cast<size_t>((random() % 8) + 1),
1843 .GEN_STRUCTURAL_MUTATION_PROBABILITY = static_cast<size_t>(random() % 100),
1844 .GEN_VALUE_MUTATION_PROBABILITY = static_cast<size_t>(random() % 100),
1845 .ST_MUT_DELETION_PROBABILITY = static_cast<size_t>(random() % 100),
1846 .ST_MUT_DUPLICATION_PROBABILITY = static_cast<size_t>(random() % 100),
1847 .ST_MUT_INSERTION_PROBABILITY = static_cast<size_t>((random() % 99) + 1),
1848 .ST_MUT_MAXIMUM_DELETION_LOG = static_cast<size_t>((random() % 8) + 1),
1849 .ST_MUT_MAXIMUM_DUPLICATION_LOG = static_cast<size_t>((random() % 8) + 1),
1850 .ST_MUT_SWAP_PROBABILITY = static_cast<size_t>(random() % 100),
1851 .VAL_MUT_LLVM_MUTATE_PROBABILITY = static_cast<size_t>(random() % 100),
1852 .VAL_MUT_MONTGOMERY_PROBABILITY = static_cast<size_t>(random() % 100),
1853 .VAL_MUT_NON_MONTGOMERY_PROBABILITY = static_cast<size_t>(random() % 100),
1854 .VAL_MUT_SMALL_ADDITION_PROBABILITY = static_cast<size_t>(random() % 100),
1855 .VAL_MUT_SPECIAL_VALUE_PROBABILITY = static_cast<size_t>(random() % 100)
1856
1857 };
1858 while (fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY == 0 &&
1859 fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY == 0) {
1860 fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY = static_cast<size_t>(random() % 8);
1861 fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY = static_cast<size_t>(random() % 8);
1862 }
1863 */
1864
1865 // fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB = static_cast<size_t>(((random() % (20 - 1)) + 1) * 10);
1870 /*
1871 std::cerr << "CUSTOM MUTATOR SETTINGS:" << std::endl
1872 << "################################################################" << std::endl
1873 << "GEN_LLVM_POST_MUTATION_PROB: " << fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB << std::endl
1874 << "GEN_MUTATION_COUNT_LOG: " << fuzzer_havoc_settings.GEN_MUTATION_COUNT_LOG << std::endl
1875 << "GEN_STRUCTURAL_MUTATION_PROBABILITY: " <<
1876 fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY
1877 << std::endl
1878 << "GEN_VALUE_MUTATION_PROBABILITY: " << fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY <<
1879 std::endl
1880 << "ST_MUT_DELETION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_DELETION_PROBABILITY << std::endl
1881 << "ST_MUT_DUPLICATION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_DUPLICATION_PROBABILITY <<
1882 std::endl
1883 << "ST_MUT_INSERTION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_INSERTION_PROBABILITY << std::endl
1884 << "ST_MUT_MAXIMUM_DELETION_LOG: " << fuzzer_havoc_settings.ST_MUT_MAXIMUM_DELETION_LOG << std::endl
1885 << "ST_MUT_MAXIMUM_DUPLICATION_LOG: " << fuzzer_havoc_settings.ST_MUT_MAXIMUM_DUPLICATION_LOG <<
1886 std::endl
1887 << "ST_MUT_SWAP_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_SWAP_PROBABILITY << std::endl
1888 << "VAL_MUT_LLVM_MUTATE_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_LLVM_MUTATE_PROBABILITY
1889 << std::endl
1890 << "VAL_MUT_MONTGOMERY_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_MONTGOMERY_PROBABILITY <<
1891 std::endl
1892 << "VAL_MUT_NON_MONTGOMERY_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_NON_MONTGOMERY_PROBABILITY
1893 << std::endl
1894 << "VAL_MUT_SMALL_ADDITION_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_SMALL_ADDITION_PROBABILITY
1895 << std::endl
1896 << "VAL_MUT_SMALL_MULTIPLICATION_PROBABILITY: "
1897 << fuzzer_havoc_settings.VAL_MUT_SMALL_MULTIPLICATION_PROBABILITY << std::endl
1898 << "VAL_MUT_SPECIAL_VALUE_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_SPECIAL_VALUE_PROBABILITY
1899 << std::endl;
1900 */
1901 std::vector<size_t> structural_mutation_distribution;
1902 std::vector<size_t> value_mutation_distribution;
1903 size_t temp = 0;
1904 temp += fuzzer_havoc_settings.ST_MUT_DELETION_PROBABILITY;
1905 structural_mutation_distribution.push_back(temp);
1906 temp += fuzzer_havoc_settings.ST_MUT_DUPLICATION_PROBABILITY;
1907 structural_mutation_distribution.push_back(temp);
1908 temp += fuzzer_havoc_settings.ST_MUT_INSERTION_PROBABILITY;
1909 structural_mutation_distribution.push_back(temp);
1910 temp += fuzzer_havoc_settings.ST_MUT_SWAP_PROBABILITY;
1911 structural_mutation_distribution.push_back(temp);
1912 fuzzer_havoc_settings.structural_mutation_distribution = structural_mutation_distribution;
1913
1914 temp = 0;
1915 temp += fuzzer_havoc_settings.VAL_MUT_LLVM_MUTATE_PROBABILITY;
1916 value_mutation_distribution.push_back(temp);
1917 temp += fuzzer_havoc_settings.VAL_MUT_SMALL_ADDITION_PROBABILITY;
1918 value_mutation_distribution.push_back(temp);
1919
1920 temp += fuzzer_havoc_settings.VAL_MUT_SPECIAL_VALUE_PROBABILITY;
1921 value_mutation_distribution.push_back(temp);
1922 fuzzer_havoc_settings.value_mutation_distribution = value_mutation_distribution;
1923 return 0;
1924}
1925#endif
1926#ifndef DISABLE_CUSTOM_MUTATORS
1931extern "C" size_t LLVMFuzzerCustomMutator(uint8_t* Data, size_t Size, size_t MaxSize, unsigned int Seed)
1932{
1933 using FuzzerClass = BigFieldBase<proof_system::StandardCircuitBuilder>;
1934 auto fast_random = FastRandom(Seed);
1935 auto size_occupied = ArithmeticFuzzHelper<FuzzerClass>::MutateInstructionBuffer(Data, Size, MaxSize, fast_random);
1936 if ((fast_random.next() % 200) < fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB) {
1937 size_occupied = LLVMFuzzerMutate(Data, size_occupied, MaxSize);
1938 }
1939 return size_occupied;
1940}
1941
1946extern "C" size_t LLVMFuzzerCustomCrossOver(const uint8_t* Data1,
1947 size_t Size1,
1948 const uint8_t* Data2,
1949 size_t Size2,
1950 uint8_t* Out,
1951 size_t MaxOutSize,
1952 unsigned int Seed)
1953{
1954 using FuzzerClass = BigFieldBase<proof_system::StandardCircuitBuilder>;
1955 auto fast_random = FastRandom(Seed);
1956 auto vecA = ArithmeticFuzzHelper<FuzzerClass>::parseDataIntoInstructions(Data1, Size1);
1957 auto vecB = ArithmeticFuzzHelper<FuzzerClass>::parseDataIntoInstructions(Data2, Size2);
1958 auto vecC = ArithmeticFuzzHelper<FuzzerClass>::crossoverInstructionVector(vecA, vecB, fast_random);
1959 return ArithmeticFuzzHelper<FuzzerClass>::writeInstructionsToBuffer(vecC, Out, MaxOutSize);
1960}
1961
1962#endif
1963
1968extern "C" size_t LLVMFuzzerTestOneInput(const uint8_t* Data, size_t Size)
1969{
1970 RunWithBuilders<BigFieldBase, FuzzerCircuitTypes>(Data, Size, VarianceRNG);
1971 return 0;
1972}
1973
1974#pragma clang diagnostic pop
ArithmeticFuzzHelper::writeInstructionsToBuffer
static size_t writeInstructionsToBuffer(std::vector< typename T::Instruction > &instructions, uint8_t *Data, size_t MaxSize)
Write instructions into the buffer until there are no instructions left or there is no more space.
Definition: fuzzer.hpp:561
ArithmeticFuzzHelper::parseDataIntoInstructions
static std::vector< typename T::Instruction > parseDataIntoInstructions(const uint8_t *Data, size_t Size)
Parses a given data buffer into a vector of instructions for testing the arithmetic.
Definition: fuzzer.hpp:520
ArithmeticFuzzHelper::MutateInstructionBuffer
static size_t MutateInstructionBuffer(uint8_t *Data, size_t Size, size_t MaxSize, FastRandom &rng)
Interpret the data buffer as a series of arithmetic instructions and mutate it accordingly.
Definition: fuzzer.hpp:670
ArithmeticFuzzHelper::crossoverInstructionVector
static std::vector< typename T::Instruction > crossoverInstructionVector(const std::vector< typename T::Instruction > &vecA, const std::vector< typename T::Instruction > &vecB, FastRandom &rng)
Splice two instruction vectors into one randomly.
Definition: fuzzer.hpp:458
BigFieldBase::ArgSizes
Definition: bigfield.fuzzer.hpp:586
BigFieldBase::ExecutionHandler
This class implements the execution of safeuint with an oracle to detect discrepancies.
Definition: bigfield.fuzzer.hpp:800
BigFieldBase::ExecutionHandler::execute_CONSTANT_WITNESS
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)
Definition: bigfield.fuzzer.hpp:1152
BigFieldBase::ExecutionHandler::execute_SET
static size_t execute_SET(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the SET instruction.
Definition: bigfield.fuzzer.hpp:1737
BigFieldBase::ExecutionHandler::execute_RANDOMSEED
static size_t execute_RANDOMSEED(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the RANDOMSEED instruction.
Definition: bigfield.fuzzer.hpp:1765
BigFieldBase::ExecutionHandler::execute_WITNESS
static size_t execute_WITNESS(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the witness instruction (push witness safeuit to the stack)
Definition: bigfield.fuzzer.hpp:1123
BigFieldBase::ExecutionHandler::execute_SUBTRACT
static size_t execute_SUBTRACT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the subtraction operator instruction.
Definition: bigfield.fuzzer.hpp:1340
BigFieldBase::ExecutionHandler::execute_MADD
static size_t execute_MADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the MADD instruction.
Definition: bigfield.fuzzer.hpp:1418
BigFieldBase::ExecutionHandler::execute_MSUB_DIV
static size_t execute_MSUB_DIV(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the MSUB_DIV instruction.
Definition: bigfield.fuzzer.hpp:1527
BigFieldBase::ExecutionHandler::execute_CONSTANT
static size_t execute_CONSTANT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the constant instruction (push constant safeuint to the stack)
Definition: bigfield.fuzzer.hpp:1101
BigFieldBase::ExecutionHandler::execute_DIVIDE
static size_t execute_DIVIDE(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the division operator instruction.
Definition: bigfield.fuzzer.hpp:1375
BigFieldBase::ExecutionHandler::execute_ADD
static size_t execute_ADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the addition operator instruction.
Definition: bigfield.fuzzer.hpp:1209
BigFieldBase::ExecutionHandler::execute_ASSERT_NOT_EQUAL
static size_t execute_ASSERT_NOT_EQUAL(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the ASSERT_NOT_EQUAL instruction.
Definition: bigfield.fuzzer.hpp:1308
BigFieldBase::ExecutionHandler::execute_COND_NEGATE
static size_t execute_COND_NEGATE(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the COND_NEGATE instruction.
Definition: bigfield.fuzzer.hpp:1670
BigFieldBase::ExecutionHandler::execute_ASSERT_EQUAL
static size_t execute_ASSERT_EQUAL(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the ASSERT_EQUAL instruction.
Definition: bigfield.fuzzer.hpp:1280
BigFieldBase::ExecutionHandler::execute_SQR
static size_t execute_SQR(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the SQR instruction.
Definition: bigfield.fuzzer.hpp:1245
BigFieldBase::ExecutionHandler::execute_SQR_ADD
static size_t execute_SQR_ADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the SQR_ADD instruction.
Definition: bigfield.fuzzer.hpp:1610
BigFieldBase::ExecutionHandler::execute_COND_SELECT
static size_t execute_COND_SELECT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the COND_SELECT instruction.
Definition: bigfield.fuzzer.hpp:1703
BigFieldBase::ExecutionHandler::execute_MULT_MADD
static size_t execute_MULT_MADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the MULT_MADD instruction.
Definition: bigfield.fuzzer.hpp:1454
BigFieldBase::ExecutionHandler::execute_MULTIPLY
static size_t execute_MULTIPLY(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the multiply instruction.
Definition: bigfield.fuzzer.hpp:1173
BigFieldBase::InstructionWeights
Optional subclass that governs limits on the use of certain instructions, since some of them can be t...
Definition: bigfield.fuzzer.hpp:621
BigFieldBase::Instruction
A class representing a single fuzzing instruction.
Definition: bigfield.fuzzer.hpp:135
BigFieldBase::Instruction::mutateFieldElement
static fq mutateFieldElement(fq e, T &rng, HavocSettings &havoc_config)
Mutate the value of a field element.
Definition: bigfield.fuzzer.hpp:367
BigFieldBase::Instruction::generateRandom
static Instruction generateRandom(T &rng)
Generate a random instruction.
Definition: bigfield.fuzzer.hpp:240
BigFieldBase::Instruction::mutateInstruction
static Instruction mutateInstruction(Instruction instruction, T &rng, HavocSettings &havoc_config)
Mutate a single instruction.
Definition: bigfield.fuzzer.hpp:464
BigFieldBase::Parser
Parser class handles the parsing and writing the instructions back to data buffer.
Definition: bigfield.fuzzer.hpp:653
BigFieldBase::Parser::parseInstructionArgs
static Instruction parseInstructionArgs(uint8_t *Data)
Parse a single instruction from data.
Definition: bigfield.fuzzer.hpp:662
BigFieldBase::Parser::writeInstruction
static void writeInstruction(Instruction &instruction, uint8_t *Data)
Write a single instruction to buffer.
Definition: bigfield.fuzzer.hpp:738
BigFieldBase
The class parametrizing Bigfield fuzzing instructions, execution, etc.
Definition: bigfield.fuzzer.hpp:122
BigFieldBase::ExecutionState
std::vector< ExecutionHandler > ExecutionState
Definition: bigfield.fuzzer.hpp:1780
BigFieldBase::postProcess
static bool postProcess(Builder *builder, std::vector< BigFieldBase::ExecutionHandler > &stack)
Check that the resulting values are equal to expected.
Definition: bigfield.fuzzer.hpp:1790
FastRandom
Class for quickly deterministically creating new random values. We don't care about distribution much...
Definition: fuzzer.hpp:64
numeric::uint256_t
Definition: uint256.hpp:25
numeric::uint256_t::slice
constexpr uint256_t slice(uint64_t start, uint64_t end) const
Definition: uint256_impl.hpp:157
proof_system::StandardCircuitBuilder_
Definition: standard_circuit_builder.hpp:12
proof_system::plonk::stdlib::bigfield
Definition: bigfield.hpp:17
proof_system::plonk::stdlib::bool_t
Definition: bool.hpp:7
proof_system::plonk::stdlib::field_t
Definition: field.hpp:10
proof_system::plonk::stdlib::public_witness_t
Definition: witness.hpp:51
proof_system::plonk::stdlib::witness_t
Definition: witness.hpp:10
SimpleRng
Concept for a simple PRNG which returns a uint32_t when next is called.
Definition: fuzzer.hpp:91
BigFieldBase::Instruction::Element
Definition: bigfield.fuzzer.hpp:162
BigFieldBase::Instruction::FiveArgs
Definition: bigfield.fuzzer.hpp:183
BigFieldBase::Instruction::FourArgs
Definition: bigfield.fuzzer.hpp:177
BigFieldBase::Instruction::MultAddArgs
Definition: bigfield.fuzzer.hpp:190
BigFieldBase::Instruction::MultOpArgs
Definition: bigfield.fuzzer.hpp:196
BigFieldBase::Instruction::SliceArgs
Definition: bigfield.fuzzer.hpp:205
BigFieldBase::Instruction::ThreeArgs
Definition: bigfield.fuzzer.hpp:172
BigFieldBase::Instruction::TwoArgs
Definition: bigfield.fuzzer.hpp:168
HavocSettings
Definition: fuzzer.hpp:27
barretenberg::field::sqr
BBERG_INLINE constexpr field sqr() const noexcept
Definition: field_impl.hpp:61
BigFieldBase::Instruction::ArgumentContents
Definition: bigfield.fuzzer.hpp:213
Generated by doxygen 1.9.6