barretenberg
Loading...
Searching...
No Matches
safe_uint.fuzzer.hpp
1#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
2#include "barretenberg/numeric/random/engine.hpp"
3#include "barretenberg/numeric/uint256/uint256.hpp"
4#include "barretenberg/stdlib/primitives/safe_uint/safe_uint.hpp"
5#pragma clang diagnostic push
6#pragma clang diagnostic ignored "-Wc99-designator"
7
8// This is a global variable, so that the execution handling class could alter it and signal to the input tester that
9// the input should fail
10bool circuit_should_fail = false;
11
12using fr = barretenberg::fr;
13#define HAVOC_TESTING
14
15#include "barretenberg/common/fuzzer.hpp"
16FastRandom VarianceRNG(0);
17
18// Enable this definition, when you want to find out the instructions that caused a failure
19// #define SHOW_INFORMATION 1
20
21#ifdef SHOW_INFORMATION
22#define PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, vector, operation_name, preposition) \
23 { \
24 std::cout << operation_name << " " << (vector[first_index].suint.is_constant() ? "constant(" : "witness(") \
25 << vector[first_index].suint.get_value() << ":" << vector[first_index].suint.current_max << ") at " \
26 << first_index << " " << preposition << " " \
27 << (vector[second_index].suint.is_constant() ? "constant(" : "witness(") \
28 << vector[second_index].suint.get_value() << ":" << vector[second_index].suint.current_max \
29 << ") at " << second_index << std::flush; \
30 }
31
32#define PRINT_THREE_ARG_INSTRUCTION( \
33 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2) \
34 { \
35 std::cout << operation_name << " " << (vector[first_index].suint.is_constant() ? "constant(" : "witness(") \
36 << vector[first_index].suint.get_value() << ":" << vector[first_index].suint.current_max << ") at " \
37 << first_index << " " << preposition1 << " " \
38 << (vector[second_index].suint.is_constant() ? "constant(" : "witness(") \
39 << vector[second_index].suint.get_value() << ":" << vector[second_index].suint.current_max \
40 << ") at " << second_index << " " << preposition2 << " " \
41 << (vector[third_index].suint.is_constant() ? "constant(" : "witness(") \
42 << vector[third_index].suint.get_value() << ":" << vector[third_index].suint.current_max << ") at " \
43 << third_index << std::flush; \
44 }
45#define PRINT_TWO_ARG_ONE_VALUE_INSTRUCTION( \
46 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2) \
47 { \
48 std::cout << operation_name << " " << (vector[first_index].suint.is_constant() ? "constant(" : "witness(") \
49 << vector[first_index].suint.get_value() << ":" << vector[first_index].suint.current_max << ") at " \
50 << first_index << " " << preposition1 << " " \
51 << (vector[second_index].suint.is_constant() ? "constant(" : "witness(") \
52 << vector[second_index].suint.get_value() << ":" << vector[second_index].suint.current_max \
53 << ") at " << second_index << " " << preposition2 << " " << third_index << std::flush; \
54 }
55
56#define PRINT_TWO_ARG_TWO_VALUES_INSTRUCTION( \
57 first_index, second_index, value1, value2, vector, operation_name, preposition1, preposition2, preposition3) \
58 { \
59 std::cout << operation_name << " " << (vector[first_index].suint.is_constant() ? "constant(" : "witness(") \
60 << vector[first_index].suint.get_value() << ":" << vector[first_index].suint.current_max << ") at " \
61 << first_index << " " << preposition1 << " " \
62 << (vector[second_index].suint.is_constant() ? "constant(" : "witness(") \
63 << vector[second_index].suint.get_value() << ":" << vector[second_index].suint.current_max \
64 << ") at " << second_index << " " << preposition2 << " " << value1 << preposition3 << value2 \
65 << std::flush; \
66 }
67
68#define PRINT_SLICE(first_index, lsb, msb, vector) \
69 { \
70 std::cout << "Slice:" \
71 << " " << (vector[first_index].suint.is_constant() ? "constant(" : "witness(") \
72 << vector[first_index].suint.get_value() << ":" << vector[first_index].suint.current_max << ") at " \
73 << first_index << " " \
74 << "(" << (size_t)lsb << ":" << (size_t)msb << ")" << std::flush; \
75 }
76
77#define PRINT_RESULT(prefix, action, index, value) \
78 { \
79 std::cout << " result(" << value.suint.get_value() << " : " << value.suint.current_max << ") " << action \
80 << index << std::endl \
81 << std::flush; \
82 }
83
84#else
85
86#define PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, vector, operation_name, preposition)
87
88#define PRINT_TWO_ARG_ONE_VALUE_INSTRUCTION( \
89 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2)
90#define PRINT_TWO_ARG_TWO_VALUES_INSTRUCTION( \
91 first_index, second_index, value1, value2, vector, operation_name, preposition1, preposition2, preposition3)
92
93#define PRINT_THREE_ARG_INSTRUCTION( \
94 first_index, second_index, third_index, vector, operation_name, preposition1, preposition2)
95#define PRINT_RESULT(prefix, action, index, value)
96
97#define PRINT_SLICE(first_index, lsb, msb, vector)
98#endif
99
100#define OPERATION_TYPE_SIZE 1
101
102#define ELEMENT_SIZE (sizeof(fr) + 1)
103#define TWO_IN_ONE_OUT 3
104#define THREE_IN_ONE_OUT 4
105#define SLICE_ARGS_SIZE 6
106
111template <typename Builder> class SafeUintFuzzBase {
112 private:
113 typedef proof_system::plonk::stdlib::bool_t<Builder> bool_t;
114 typedef proof_system::plonk::stdlib::field_t<Builder> field_t;
115 typedef proof_system::plonk::stdlib::safe_uint_t<Builder> suint_t;
116 typedef proof_system::plonk::stdlib::witness_t<Builder> witness_t;
117 typedef proof_system::plonk::stdlib::public_witness_t<Builder> public_witness_t;
118
119 public:
124 class Instruction {
125 public:
126 enum OPCODE {
127 CONSTANT,
128 WITNESS,
129 CONSTANT_WITNESS,
130 ADD,
131 SUBTRACT,
132 MULTIPLY,
133 DIVIDE,
134 ADD_TWO,
135 MADD,
136 SUBTRACT_WITH_CONSTRAINT,
137 DIVIDE_WITH_CONSTRAINTS,
138 SLICE,
139 RANDOMSEED,
140 _LAST
141 };
142 struct Element {
143 fr value;
144 uint8_t bit_range;
145 };
146 struct ThreeArgs {
147 uint8_t in1;
148 uint8_t in2;
149 uint8_t out;
150 };
151 struct FourArgs {
152 uint8_t in1;
153 uint8_t in2;
154 uint8_t in3;
155 uint8_t out;
156 };
157 struct FiveArgs {
158 uint8_t in1;
159 uint8_t in2;
160 uint8_t qbs;
161 uint8_t rbs;
162 uint8_t out;
163 };
164
165 struct SliceArgs {
166 uint8_t in1;
167 uint8_t lsb;
168 uint8_t msb;
169 uint8_t out1;
170 uint8_t out2;
171 uint8_t out3;
172 };
173 union ArgumentContents {
174 uint32_t randomseed;
175 Element element;
176 ThreeArgs threeArgs;
177 FourArgs fourArgs;
178 FiveArgs fiveArgs;
179 SliceArgs sliceArgs;
180 };
181 // The type of instruction
182 OPCODE id;
183 // Instruction arguments
184 ArgumentContents arguments;
192 template <typename T>
193 inline static Instruction generateRandom(T& rng)
194 requires SimpleRng<T>
195 {
196 // Choose which instruction we are going to generate
197 OPCODE instruction_opcode = static_cast<OPCODE>(rng.next() % (OPCODE::_LAST));
198 uint8_t in1, in2, in3, lsb, msb, out, out1, out2, out3, mask_size, bit_range;
199 uint256_t mask, temp;
200 // Depending on instruction
201 switch (instruction_opcode) {
202 case OPCODE::CONSTANT:
203 case OPCODE::WITNESS:
204 case OPCODE::CONSTANT_WITNESS:
205 // If it's a constant or witness, it just pushes data onto the stack to be acted upon
206 // Generate a random field element
207 for (size_t i = 0; i < (sizeof(uint256_t) >> 1); i++) {
208 *(((uint16_t*)&temp) + i) = static_cast<uint16_t>(rng.next() & 0xffff);
209 }
210 // We want small values, too. If we generate randomly, we aren't going to have them, so we also apply a
211 // random mask, which randomizes the logarithm of maximum value
212 mask_size = static_cast<uint8_t>(rng.next() & 0xff);
213 mask = (uint256_t(1) << mask_size) - 1;
214 // Choose the bit range
215 bit_range = static_cast<uint8_t>(rng.next() & 0xff);
216 // Return instruction
217 return { .id = instruction_opcode,
218 .arguments.element = { .value = fr(temp & mask), .bit_range = bit_range } };
219
220 break;
221 case OPCODE::ADD:
222 case OPCODE::SUBTRACT:
223 case OPCODE::MULTIPLY:
224 case OPCODE::DIVIDE:
225 // For two-input-one-output instructions we just randomly pick each argument and generate an instruction
226 // accordingly
227 in1 = static_cast<uint8_t>(rng.next() & 0xff);
228 in2 = static_cast<uint8_t>(rng.next() & 0xff);
229 out = static_cast<uint8_t>(rng.next() & 0xff);
230 return { .id = instruction_opcode, .arguments.threeArgs = { .in1 = in1, .in2 = in2, .out = out } };
231 break;
232 case OPCODE::ADD_TWO:
233 case OPCODE::MADD:
234 case OPCODE::SUBTRACT_WITH_CONSTRAINT:
235 // For three-input-one-output instructions we just randomly pick each argument and generate an
236 // instruction accordingly
237 in1 = static_cast<uint8_t>(rng.next() & 0xff);
238 in2 = static_cast<uint8_t>(rng.next() & 0xff);
239 in3 = static_cast<uint8_t>(rng.next() & 0xff);
240 out = static_cast<uint8_t>(rng.next() & 0xff);
241 return { .id = instruction_opcode,
242 .arguments.fourArgs = { .in1 = in1, .in2 = in2, .in3 = in3, .out = out } };
243 break;
244
245 case OPCODE::DIVIDE_WITH_CONSTRAINTS:
246 // For four-input-one-output instructions we just randomly pick each argument and generate an
247 // instruction accordingly
248 in1 = static_cast<uint8_t>(rng.next() & 0xff);
249 in2 = static_cast<uint8_t>(rng.next() & 0xff);
250 in3 = static_cast<uint8_t>(rng.next() & 0xff);
251 lsb = static_cast<uint8_t>(rng.next() & 0xff);
252 out = static_cast<uint8_t>(rng.next() & 0xff);
253 return { .id = instruction_opcode,
254 .arguments.fiveArgs = { .in1 = in1, .in2 = in2, .qbs = in3, .rbs = lsb, .out = out } };
255
256 break;
257 case OPCODE::SLICE:
258 // For the slice instruction we just randomly pick each argument and generate an instruction
259 // accordingly
260 in1 = static_cast<uint8_t>(rng.next() & 0xff);
261 lsb = static_cast<uint8_t>(rng.next() & 0xff);
262 msb = static_cast<uint8_t>(rng.next() & 0xff);
263 out1 = static_cast<uint8_t>(rng.next() & 0xff);
264 out2 = static_cast<uint8_t>(rng.next() & 0xff);
265 out3 = static_cast<uint8_t>(rng.next() & 0xff);
266 return { .id = instruction_opcode,
267 .arguments.sliceArgs = {
268 .in1 = in1, .lsb = lsb, .msb = msb, .out1 = out1, .out2 = out2, .out3 = out3 } };
269 break;
270 case OPCODE::RANDOMSEED:
271 return { .id = instruction_opcode, .arguments.randomseed = rng.next() };
272 break;
273 default:
274 abort(); // We have missed some instructions, it seems
275 break;
276 }
277 }
278
288 template <typename T>
289 inline static fr mutateFieldElement(fr e, T& rng, HavocSettings& havoc_config)
290 requires SimpleRng<T>
291 {
292 // With a certain probability, we apply changes to the Montgomery form, rather than the plain form. This has
293 // merit, since the computation is performed in montgomery form and comparisons are often performed in it,
294 // too. Libfuzzer comparison tracing logic can then be enabled in Montgomery form
295 bool convert_to_montgomery = (rng.next() % (havoc_config.VAL_MUT_MONTGOMERY_PROBABILITY +
296 havoc_config.VAL_MUT_NON_MONTGOMERY_PROBABILITY)) <
297 havoc_config.VAL_MUT_MONTGOMERY_PROBABILITY;
298 uint256_t value_data;
299 // Conversion at the start
300#define MONT_CONVERSION \
301 if (convert_to_montgomery) { \
302 value_data = uint256_t(e.to_montgomery_form()); \
303 } else { \
304 value_data = uint256_t(e); \
305 }
306 // Inverse conversion at the end
307#define INV_MONT_CONVERSION \
308 if (convert_to_montgomery) { \
309 e = fr(value_data).from_montgomery_form(); \
310 } else { \
311 e = fr(value_data); \
312 }
313
314 // Pick the last value from the mutation distrivution vector
315 const size_t mutation_type_count = havoc_config.value_mutation_distribution.size();
316 // Choose mutation
317 const size_t choice = rng.next() % havoc_config.value_mutation_distribution[mutation_type_count - 1];
318 if (choice < havoc_config.value_mutation_distribution[0]) {
319 // Delegate mutation to libfuzzer (bit/byte mutations, autodictionary, etc)
320 MONT_CONVERSION
321 LLVMFuzzerMutate((uint8_t*)&value_data, sizeof(uint256_t), sizeof(uint256_t));
322 INV_MONT_CONVERSION
323 } else if (choice < havoc_config.value_mutation_distribution[1]) {
324 // Small addition/subtraction
325 if (convert_to_montgomery) {
326 e = e.to_montgomery_form();
327 }
328 if (rng.next() & 1) {
329 value_data = e + fr(rng.next() & 0xff);
330 } else {
331 value_data = e - fr(rng.next() & 0xff);
332 }
333 if (convert_to_montgomery) {
334 e = e.from_montgomery_form();
335 }
336 } else {
337 // Substitute field element with a special value
338 MONT_CONVERSION
339 switch (rng.next() % 8) {
340 case 0:
341 e = fr::zero();
342 break;
343 case 1:
344 e = fr::one();
345 break;
346 case 2:
347 e = -fr::one();
348 break;
349 case 3:
350 e = fr::one().sqrt().second;
351 break;
352 case 4:
353 e = fr::one().sqrt().second.invert();
354 break;
355 case 5:
356 e = fr::get_root_of_unity(8);
357 break;
358 case 6:
359 e = fr(2);
360 break;
361 case 7:
362 e = fr((fr::modulus - 1) / 2);
363 break;
364 default:
365 abort();
366 break;
367 }
368 INV_MONT_CONVERSION
369 }
370 // Return instruction
371 return e;
372 }
382 template <typename T>
383 inline static Instruction mutateInstruction(Instruction instruction, T& rng, HavocSettings& havoc_config)
384 requires SimpleRng<T>
385 {
386#define PUT_RANDOM_BYTE_IF_LUCKY(variable) \
387 if (rng.next() & 1) { \
388 variable = rng.next() & 0xff; \
389 }
390 // Depending on instruction type...
391 switch (instruction.id) {
392 case OPCODE::CONSTANT:
393 case OPCODE::WITNESS:
394 case OPCODE::CONSTANT_WITNESS:
395 // If it represents pushing a value on the stack with a 50% probability randomly sample a bit_range
396 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.element.bit_range);
397 // Maybe mutate the value
398 if (rng.next() & 1) {
399 instruction.arguments.element.value =
400 mutateFieldElement(instruction.arguments.element.value, rng, havoc_config);
401 }
402 break;
403 case OPCODE::ADD:
404 case OPCODE::DIVIDE:
405 case OPCODE::MULTIPLY:
406 case OPCODE::SUBTRACT:
407 // Randomly sample each of the arguments with 50% probability
408 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.in1)
409 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.in2)
410 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.threeArgs.out)
411 break;
412 case OPCODE::ADD_TWO:
413 case OPCODE::MADD:
414 case OPCODE::SUBTRACT_WITH_CONSTRAINT:
415 // Randomly sample each of the arguments with 50% probability
416 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in1)
417 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in2)
418 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.in3)
419 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fourArgs.out)
420 break;
421 case OPCODE::DIVIDE_WITH_CONSTRAINTS:
422 // Randomly sample each of the arguments with 50% probability
423 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fiveArgs.in1)
424 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fiveArgs.in2)
425 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fiveArgs.qbs)
426 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fiveArgs.rbs)
427 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.fiveArgs.out)
428 break;
429 case OPCODE::SLICE:
430 // Randomly sample each of the arguments with 50% probability
431 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.sliceArgs.in1)
432 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.sliceArgs.lsb)
433 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.sliceArgs.msb)
434 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.sliceArgs.out1)
435 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.sliceArgs.out2)
436 PUT_RANDOM_BYTE_IF_LUCKY(instruction.arguments.sliceArgs.out3)
437 break;
438 case OPCODE::RANDOMSEED:
439 instruction.arguments.randomseed = rng.next();
440 break;
441 default:
442 abort(); // New instruction encountered
443 break;
444 }
445 // Return mutated instruction
446 return instruction;
447 }
448 };
449 // We use argsizes to both specify the size of data needed to parse the instruction and to signal that the
450 // instruction is enabled (if it is -1,it's disabled )
451 class ArgSizes {
452 public:
453 static constexpr size_t CONSTANT = sizeof(uint256_t) + 1;
454 static constexpr size_t WITNESS = sizeof(uint256_t) + 1;
455 static constexpr size_t CONSTANT_WITNESS = sizeof(uint256_t) + 1;
456 static constexpr size_t ADD = 3;
457 static constexpr size_t SUBTRACT = 3;
458 static constexpr size_t MULTIPLY = 3;
459 static constexpr size_t ADD_TWO = 4;
460 static constexpr size_t DIVIDE = 3;
461 static constexpr size_t MADD = 4;
462 static constexpr size_t SUBTRACT_WITH_CONSTRAINT = 4;
463 static constexpr size_t DIVIDE_WITH_CONSTRAINTS = 5;
464 static constexpr size_t SLICE = 6;
465 static constexpr size_t RANDOMSEED = sizeof(uint32_t);
466 };
471 class Parser {
472 public:
480 template <typename Instruction::OPCODE opcode> inline static Instruction parseInstructionArgs(uint8_t* Data)
481 {
482 if constexpr (opcode == Instruction::OPCODE::CONSTANT || opcode == Instruction::OPCODE::WITNESS ||
483 opcode == Instruction::OPCODE::CONSTANT_WITNESS) {
484 return Instruction{ .id = static_cast<typename Instruction::OPCODE>(opcode),
485 .arguments.element = { .value = fr::serialize_from_buffer(Data + 1),
486 .bit_range = *Data } };
487 }
488 if constexpr (opcode == Instruction::OPCODE::ADD || opcode == Instruction::OPCODE::MULTIPLY ||
489 opcode == Instruction::OPCODE::DIVIDE || opcode == Instruction::OPCODE::SUBTRACT) {
490 return Instruction{ .id = static_cast<typename Instruction::OPCODE>(opcode),
491 .arguments.threeArgs = { .in1 = *Data, .in2 = *(Data + 1), .out = *(Data + 2) } };
492 }
493 if constexpr (opcode == Instruction::OPCODE::MADD || opcode == Instruction::OPCODE::ADD_TWO ||
494 opcode == Instruction::OPCODE::SUBTRACT_WITH_CONSTRAINT) {
495 return Instruction{ .id = static_cast<typename Instruction::OPCODE>(opcode),
496 .arguments.fourArgs = {
497 .in1 = *Data, .in2 = *(Data + 1), .in3 = *(Data + 2), .out = *(Data + 3) } };
498 }
499 if constexpr (opcode == Instruction::OPCODE::DIVIDE_WITH_CONSTRAINTS) {
500 return Instruction{ .id = static_cast<typename Instruction::OPCODE>(opcode),
501 .arguments.fiveArgs = { .in1 = *Data,
502 .in2 = *(Data + 1),
503 .qbs = *(Data + 2),
504 .rbs = *(Data + 3),
505 .out = *(Data + 4) } };
506 }
507 if constexpr (opcode == Instruction::OPCODE::SLICE) {
508 return Instruction{ .id = static_cast<typename Instruction::OPCODE>(opcode),
509 .arguments.sliceArgs = { .in1 = *Data,
510 .lsb = *(Data + 1),
511 .msb = *(Data + 2),
512 .out1 = *(Data + 3),
513 .out2 = *(Data + 4),
514 .out3 = *(Data + 5) } };
515 }
516 if constexpr (opcode == Instruction::OPCODE::RANDOMSEED) {
517 uint32_t randomseed;
518 memcpy(&randomseed, Data, sizeof(uint32_t));
519 return Instruction{ .id = static_cast<typename Instruction::OPCODE>(opcode),
520 .arguments.randomseed = randomseed };
521 };
522 }
530 template <typename Instruction::OPCODE instruction_opcode>
531 inline static void writeInstruction(Instruction& instruction, uint8_t* Data)
532 {
533 if constexpr (instruction_opcode == Instruction::OPCODE::CONSTANT ||
534 instruction_opcode == Instruction::OPCODE::WITNESS ||
535 instruction_opcode == Instruction::OPCODE::CONSTANT_WITNESS) {
536 *Data = instruction.id;
537 *(Data + 1) = instruction.arguments.element.bit_range;
538 fr::serialize_to_buffer(instruction.arguments.element.value, Data + 2);
539 }
540
541 if constexpr (instruction_opcode == Instruction::OPCODE::ADD ||
542 instruction_opcode == Instruction::OPCODE::DIVIDE ||
543 instruction_opcode == Instruction::OPCODE::MULTIPLY ||
544 instruction_opcode == Instruction::OPCODE::SUBTRACT) {
545 *Data = instruction.id;
546 *(Data + 1) = instruction.arguments.threeArgs.in1;
547 *(Data + 2) = instruction.arguments.threeArgs.in2;
548 *(Data + 3) = instruction.arguments.threeArgs.out;
549 }
550 if constexpr (instruction_opcode == Instruction::OPCODE::ADD_TWO ||
551 instruction_opcode == Instruction::OPCODE::MADD ||
552 instruction_opcode == Instruction::OPCODE::SUBTRACT_WITH_CONSTRAINT) {
553 *Data = instruction.id;
554 *(Data + 1) = instruction.arguments.fourArgs.in1;
555 *(Data + 2) = instruction.arguments.fourArgs.in2;
556 *(Data + 3) = instruction.arguments.fourArgs.in3;
557 *(Data + 4) = instruction.arguments.fourArgs.out;
558 }
559 if constexpr (instruction_opcode == Instruction::OPCODE::DIVIDE_WITH_CONSTRAINTS) {
560 *Data = instruction.id;
561 *(Data + 1) = instruction.arguments.fiveArgs.in1;
562 *(Data + 2) = instruction.arguments.fiveArgs.in2;
563 *(Data + 3) = instruction.arguments.fiveArgs.qbs;
564 *(Data + 4) = instruction.arguments.fiveArgs.rbs;
565 *(Data + 5) = instruction.arguments.fiveArgs.out;
566 }
567 if constexpr (instruction_opcode == Instruction::OPCODE::SLICE) {
568 *Data = instruction.id;
569 *(Data + 1) = instruction.arguments.sliceArgs.in1;
570 *(Data + 2) = instruction.arguments.sliceArgs.lsb;
571 *(Data + 3) = instruction.arguments.sliceArgs.msb;
572 *(Data + 4) = instruction.arguments.sliceArgs.out1;
573 *(Data + 5) = instruction.arguments.sliceArgs.out2;
574 *(Data + 6) = instruction.arguments.sliceArgs.out3;
575 }
576 if constexpr (instruction_opcode == Instruction::OPCODE::RANDOMSEED) {
577
578 *Data = instruction.id;
579 memcpy(Data + 1, &instruction.arguments.randomseed, sizeof(uint32_t));
580 }
581 }
582 };
587 class ExecutionHandler {
588 suint_t s() const
589 {
590 const bool reconstruct = static_cast<bool>(VarianceRNG.next() % 2);
591
592 if (!reconstruct) {
593 return this->suint;
594 }
595
596 return suint_t(this->suint);
597 }
598
599 public:
600 // The value that tracks the actual uint value and shouldn't be able to overflow, so it helps detect when suint
601 // overflows the modulus
602 uint512_t reference_value;
603
604 suint_t suint;
605 ExecutionHandler() = default;
606 ExecutionHandler(uint512_t& r, suint_t& s)
607 : reference_value(r)
608 , suint(s)
609 {
610 // If the reference value overflows the modulus, the circuit is expected to fail
611 if (r >= static_cast<uint512_t>(fr::modulus)) {
612 circuit_should_fail = true;
613 }
614 }
615 ExecutionHandler(uint512_t r, suint_t s)
616 : reference_value(r)
617 , suint(s)
618 {
619
620 // If the reference value overflows the modulus, the circuit is expected to fail
621 if (r >= static_cast<uint512_t>(fr::modulus)) {
622
623 circuit_should_fail = true;
624 }
625 }
626 ExecutionHandler(suint_t s)
627 : reference_value(s.get_value())
628 , suint(s)
629 {}
630 ExecutionHandler operator+(const ExecutionHandler& other)
631 {
632 return ExecutionHandler(this->reference_value + other.reference_value, this->s() + other.s());
633 }
634 ExecutionHandler subtract(const ExecutionHandler& other, size_t difference_bit_size)
635 {
636 if ((this->reference_value - other.reference_value) >= (uint512_t(1) << difference_bit_size)) {
637 circuit_should_fail = true;
638 }
639 return ExecutionHandler(this->reference_value - other.reference_value,
640 this->s().subtract(other.s(), difference_bit_size));
641 }
642 ExecutionHandler operator-(const ExecutionHandler& other)
643 {
644 return ExecutionHandler(this->reference_value - other.reference_value, this->s() - other.s());
645 }
646 ExecutionHandler operator*(const ExecutionHandler& other)
647 {
648 return ExecutionHandler(this->reference_value * other.reference_value, this->s() * other.s());
649 }
650 ExecutionHandler divide(const ExecutionHandler& other, size_t quotient_bit_size, size_t remainder_bit_size)
651 {
652 if (other.s().get_value() == 0) {
653 circuit_should_fail = true;
654 }
655 auto quotient = static_cast<uint512_t>(this->reference_value.lo / other.reference_value.lo);
656 auto remainder = this->reference_value.lo - quotient.lo * other.reference_value.lo;
657 if ((quotient.lo >= (uint256_t(1) << quotient_bit_size)) ||
658 (remainder >= (uint256_t(1) << remainder_bit_size))) {
659 circuit_should_fail = true;
660 }
661 return ExecutionHandler(quotient, this->s().divide(other.s(), quotient_bit_size, remainder_bit_size));
662 }
663 ExecutionHandler operator/(const ExecutionHandler& other)
664 {
665 if (other.s().get_value() == 0) {
666 circuit_should_fail = true;
667 }
668 return ExecutionHandler(static_cast<uint512_t>(this->reference_value.lo / other.reference_value.lo),
669 this->s() / other.s());
670 }
671
672 ExecutionHandler add_two(const ExecutionHandler& other1, const ExecutionHandler& other2)
673 {
674
675 return ExecutionHandler(this->reference_value + other1.reference_value + other2.reference_value,
676 this->s().add_two(other1.s(), other2.s()));
677 }
678
679 ExecutionHandler madd(const ExecutionHandler& other1, const ExecutionHandler& other2)
680 {
681
682 return ExecutionHandler(this->reference_value * other1.reference_value + other2.reference_value,
683 this->s().madd(other1.s(), other2.s()));
684 }
685
686 std::array<ExecutionHandler, 3> slice(uint8_t lsb, uint8_t msb)
687 {
688 const auto msb_plus_one = uint32_t(msb) + 1;
689 const auto hi_mask = ((uint256_t(1) << (256 - uint32_t(msb))) - 1);
690 const auto hi_reference = (this->reference_value.lo >> msb_plus_one) & hi_mask;
691
692 const auto lo_mask = (uint256_t(1) << lsb) - 1;
693 const auto lo_reference = this->reference_value.lo & lo_mask;
694
695 const auto slice_mask = ((uint256_t(1) << (uint32_t(msb - lsb) + 1)) - 1);
696 const auto slice_reference = (this->reference_value.lo >> lsb) & slice_mask;
697
698 auto lo_slice_hi_suint_array = this->s().slice(msb, lsb);
699 return std::array<ExecutionHandler, 3>{ ExecutionHandler(lo_reference, lo_slice_hi_suint_array[0]),
700 ExecutionHandler(slice_reference, lo_slice_hi_suint_array[1]),
701 ExecutionHandler(hi_reference, lo_slice_hi_suint_array[2]) };
702 }
703
712 static inline size_t execute_CONSTANT(Builder* builder,
713 std::vector<ExecutionHandler>& stack,
714 Instruction& instruction)
715 {
716 (void)builder;
717 stack.push_back(suint_t(instruction.arguments.element.value));
718#ifdef SHOW_INFORMATION
719 std::cout << "Pushed constant value " << instruction.arguments.element.value << " to position "
720 << stack.size() - 1 << std::endl;
721#endif
722 return 0;
723 }
724
733 static inline size_t execute_WITNESS(Builder* builder,
734 std::vector<ExecutionHandler>& stack,
735 Instruction& instruction)
736 {
737 size_t bit_range = static_cast<size_t>(instruction.arguments.element.bit_range);
738 // This is handled by an assert
739 if ((bit_range > suint_t::MAX_BIT_NUM) ||
740 (bit_range > 0 && (uint256_t(instruction.arguments.element.value) >= (uint256_t(1) << bit_range)))) {
741 return 1;
742 }
743 // Bit range ==0 should only work for the 0 value
744 if (bit_range == 0 && instruction.arguments.element.value != 0) {
745 circuit_should_fail = true;
746 }
747
748 stack.push_back(suint_t(witness_t(builder, instruction.arguments.element.value),
749 instruction.arguments.element.bit_range));
750#ifdef SHOW_INFORMATION
751 std::cout << "Pushed witness value " << instruction.arguments.element.value << " < 2^" << (size_t)bit_range
752 << " to position " << stack.size() - 1 << std::endl;
753#endif
754 return 0;
755 }
756
765 static inline size_t execute_CONSTANT_WITNESS(Builder* builder,
766 std::vector<ExecutionHandler>& stack,
767 Instruction& instruction)
768 {
769 stack.push_back(suint_t::create_constant_witness(builder, instruction.arguments.element.value));
770#ifdef SHOW_INFORMATION
771 std::cout << "Pushed constant witness value " << instruction.arguments.element.value << " to position "
772 << stack.size() - 1 << std::endl;
773#endif
774 return 0;
775 }
784 static inline size_t execute_MULTIPLY(Builder* builder,
785 std::vector<ExecutionHandler>& stack,
786 Instruction& instruction)
787 {
788
789 (void)builder;
790 if (stack.size() == 0) {
791 return 1;
792 }
793 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
794 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
795 size_t output_index = instruction.arguments.threeArgs.out;
796
797 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Multiplying", "*")
798
799 // If the maximum values overflow 256 bits, this is detected by ASSERTS
800 if ((static_cast<uint512_t>(stack[first_index].suint.current_max) *
801 static_cast<uint512_t>(stack[second_index].suint.current_max))
802 .hi != 0) {
803 // Handled by asserts
804 return 1;
805 }
806 ExecutionHandler result;
807 try {
808 result = stack[first_index] * stack[second_index];
809 } catch (std::runtime_error& err) {
810 if (!strncmp(err.what(),
811 "exceeded modulus in safe_uint class",
812 sizeof("exceeded modulus in safe_uint class"))) {
813 return 1;
814 }
815 throw err;
816 }
817 // If the output index is larger than the number of elements in stack, append
818 if (output_index >= stack.size()) {
819 PRINT_RESULT("", "pushed to ", stack.size(), result)
820 stack.push_back(result);
821 } else {
822
823 PRINT_RESULT("", "saved to ", output_index, result)
824 stack[output_index] = result;
825 }
826 return 0;
827 };
836 static inline size_t execute_ADD(Builder* builder,
837 std::vector<ExecutionHandler>& stack,
838 Instruction& instruction)
839 {
840 (void)builder;
841 if (stack.size() == 0) {
842 return 1;
843 }
844 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
845 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
846 size_t output_index = instruction.arguments.threeArgs.out;
847
848 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Adding", "+")
849
850 ExecutionHandler result;
851 try {
852 result = stack[first_index] + stack[second_index];
853 } catch (std::runtime_error& err) {
854 if (!strncmp(err.what(),
855 "exceeded modulus in safe_uint class",
856 sizeof("exceeded modulus in safe_uint class"))) {
857 return 1;
858 }
859 throw err;
860 }
861 // If the output index is larger than the number of elements in stack, append
862 if (output_index >= stack.size()) {
863 PRINT_RESULT("", "pushed to ", stack.size(), result)
864 stack.push_back(result);
865 } else {
866
867 PRINT_RESULT("", "saved to ", output_index, result)
868 stack[output_index] = result;
869 }
870 return 0;
871 };
880 static inline size_t execute_SUBTRACT(Builder* builder,
881 std::vector<ExecutionHandler>& stack,
882 Instruction& instruction)
883 {
884 (void)builder;
885 if (stack.size() == 0) {
886 return 1;
887 }
888 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
889 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
890 size_t output_index = instruction.arguments.threeArgs.out;
891
892 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Subtracting", "-")
893
894 // Perform ASSERT checks that we've disabled
895 if ((static_cast<uint512_t>(1 << (stack[first_index].suint.current_max.get_msb() + 1)) +
896 static_cast<uint512_t>(stack[second_index].suint.current_max)) > suint_t::MAX_VALUE) {
897 // We don't want to trigger the throw
898 return 0;
899 }
900
901 if (stack[first_index].suint.is_constant() && stack[second_index].suint.is_constant() &&
902 (static_cast<uint256_t>(stack[first_index].suint.get_value()) <
903 static_cast<uint256_t>(stack[second_index].suint.get_value()))) {
904 // This case is handled by assert
905 return 0;
906 }
907 // When we subtract values, there is an ASSERT that checks that the maximum possible result can be
908 // constrained. So let's check it beforehand
909 if ((stack[first_index].suint.current_max.get_msb() + 1) > suint_t::MAX_BIT_NUM) {
910 return 0;
911 }
912 ExecutionHandler result;
913 try {
914 result = stack[first_index] - stack[second_index];
915 } catch (std::runtime_error& err) {
916 if (!strncmp(err.what(),
917 "exceeded modulus in safe_uint class",
918 sizeof("exceeded modulus in safe_uint class"))) {
919 return 1;
920 }
921 if (!strncmp(err.what(),
922 "maximum value exceeded in safe_uint minus operator",
923 sizeof("maximum value exceeded in safe_uint minus operator"))) {
924 return 1;
925 }
926 throw err;
927 }
928 // If the output index is larger than the number of elements in stack, append
929 if (output_index >= stack.size()) {
930 PRINT_RESULT("", "pushed to ", stack.size(), result)
931 stack.push_back(result);
932 } else {
933
934 PRINT_RESULT("", "saved to ", output_index, result)
935 stack[output_index] = result;
936 }
937 return 0;
938 };
947 static inline size_t execute_DIVIDE(Builder* builder,
948 std::vector<ExecutionHandler>& stack,
949 Instruction& instruction)
950 {
951 (void)builder;
952 if (stack.size() == 0) {
953 return 1;
954 }
955 size_t first_index = instruction.arguments.threeArgs.in1 % stack.size();
956 size_t second_index = instruction.arguments.threeArgs.in2 % stack.size();
957 size_t output_index = instruction.arguments.threeArgs.out;
958
959 PRINT_TWO_ARG_INSTRUCTION(first_index, second_index, stack, "Dividing", "/")
960
961 if (stack[first_index].suint.value.is_constant()) {
962 return 1;
963 }
964 // Assert checks
965 // The maximum value of the quotient * divisor shouldn't overflow uint256_t
966 if ((((uint512_t(1) << (stack[first_index].suint.current_max.get_msb() + 1)) - 1) *
967 stack[second_index].suint.current_max)
968 .hi != 0) {
969 return 0;
970 }
971 ExecutionHandler result;
972 try {
973 result = stack[first_index] / stack[second_index];
974 } catch (std::runtime_error& err) {
975 if (!strncmp(err.what(),
976 "exceeded modulus in safe_uint class",
977 sizeof("exceeded modulus in safe_uint class"))) {
978 return 1;
979 }
980 if (!strncmp(err.what(),
981 "maximum value exceeded in safe_uint minus operator",
982 sizeof("maximum value exceeded in safe_uint minus operator"))) {
983 return 1;
984 }
985 throw err;
986 }
987 // If division of zero by zero passes that is not ok.
988 if (stack[first_index].suint.get_value().is_zero() && stack[second_index].suint.get_value().is_zero()) {
989 circuit_should_fail = true;
990 }
991 // If the output index is larger than the number of elements in stack, append
992 if (output_index >= stack.size()) {
993 PRINT_RESULT("", "pushed to ", stack.size(), result)
994 stack.push_back(result);
995 } else {
996
997 PRINT_RESULT("", "saved to ", output_index, result)
998 stack[output_index] = result;
999 }
1000 return 0;
1001 };
1011 static inline size_t execute_ADD_TWO(Builder* builder,
1012 std::vector<ExecutionHandler>& stack,
1013 Instruction& instruction)
1014 {
1015 (void)builder;
1016 if (stack.size() == 0) {
1017 return 1;
1018 }
1019 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1020 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1021 size_t third_index = instruction.arguments.fourArgs.in3 % stack.size();
1022 size_t output_index = instruction.arguments.fourArgs.out;
1023 PRINT_THREE_ARG_INSTRUCTION(first_index, second_index, third_index, stack, "ADD_TWO:", "+", "+")
1024
1025 if ((static_cast<uint512_t>(stack[first_index].suint.current_max) +
1026 static_cast<uint512_t>(stack[second_index].suint.current_max) +
1027 static_cast<uint512_t>(stack[third_index].suint.current_max)) >
1028 static_cast<uint512_t>(suint_t::MAX_VALUE)) {
1029 return 1;
1030 }
1031 ExecutionHandler result;
1032 try {
1033 result = stack[first_index].add_two(stack[second_index], stack[third_index]);
1034 } catch (std::runtime_error& err) {
1035 if (!strncmp(err.what(),
1036 "exceeded modulus in safe_uint class",
1037 sizeof("exceeded modulus in safe_uint class"))) {
1038 return 1;
1039 }
1040 throw err;
1041 }
1042 // If the output index is larger than the number of elements in stack, append
1043 if (output_index >= stack.size()) {
1044 PRINT_RESULT("", "pushed to ", stack.size(), result)
1045 stack.push_back(result);
1046 } else {
1047
1048 PRINT_RESULT("", "saved to ", output_index, result)
1049 stack[output_index] = result;
1050 }
1051 return 0;
1052 };
1062 static inline size_t execute_MADD(Builder* builder,
1063 std::vector<ExecutionHandler>& stack,
1064 Instruction& instruction)
1065 {
1066 (void)builder;
1067 if (stack.size() == 0) {
1068 return 1;
1069 }
1070 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1071 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1072 size_t third_index = instruction.arguments.fourArgs.in3 % stack.size();
1073 size_t output_index = instruction.arguments.fourArgs.out;
1074 PRINT_THREE_ARG_INSTRUCTION(first_index, second_index, third_index, stack, "MADD:", "*", "+")
1075
1076 // If maximums overflow the modulus, then skip this instruction (an assert should handle this)
1077 if ((static_cast<uint512_t>(stack[first_index].suint.current_max) *
1078 static_cast<uint512_t>(stack[second_index].suint.current_max) +
1079 static_cast<uint512_t>(stack[third_index].suint.current_max)) >
1080 static_cast<uint512_t>(suint_t::MAX_VALUE)) {
1081 return 0;
1082 }
1083 ExecutionHandler result;
1084 try {
1085 result = stack[first_index].madd(stack[second_index], stack[third_index]);
1086 } catch (std::runtime_error& err) {
1087 if (!strncmp(err.what(),
1088 "exceeded modulus in safe_uint class",
1089 sizeof("exceeded modulus in safe_uint class"))) {
1090 return 1;
1091 }
1092 throw err;
1093 }
1094 // If the output index is larger than the number of elements in stack, append
1095 if (output_index >= stack.size()) {
1096 PRINT_RESULT("", "pushed to ", stack.size(), result)
1097 stack.push_back(result);
1098 } else {
1099
1100 PRINT_RESULT("", "saved to ", output_index, result)
1101 stack[output_index] = result;
1102 }
1103 return 0;
1104 };
1105
1115 static inline size_t execute_SUBTRACT_WITH_CONSTRAINT(Builder* builder,
1116 std::vector<ExecutionHandler>& stack,
1117 Instruction& instruction)
1118 {
1119 (void)builder;
1120 if (stack.size() == 0) {
1121 return 1;
1122 }
1123 size_t first_index = instruction.arguments.fourArgs.in1 % stack.size();
1124 size_t second_index = instruction.arguments.fourArgs.in2 % stack.size();
1125 size_t difference_bit_size = instruction.arguments.fourArgs.in3;
1126 size_t output_index = instruction.arguments.fourArgs.out;
1127 PRINT_TWO_ARG_ONE_VALUE_INSTRUCTION(
1128 first_index, second_index, difference_bit_size, stack, "SUBTRACT_WITH_CONSTRAINT:", "-", "<= 2**")
1129
1130 // If difference bit size is too big, it should be caught by assertion.
1131 if (difference_bit_size > suint_t::MAX_BIT_NUM) {
1132 return 0;
1133 }
1134 // If both constants, should be handled by assert
1135 if (stack[first_index].suint.is_constant() && stack[second_index].suint.is_constant()) {
1136 return 0;
1137 }
1138 ExecutionHandler result;
1139 try {
1140 result = stack[first_index].subtract(stack[second_index], difference_bit_size);
1141 } catch (std::runtime_error& err) {
1142 if (!strncmp(err.what(),
1143 "maximum value exceeded in safe_uint subtract",
1144 sizeof("maximum value exceeded in safe_uint subtract"))) {
1145 return 1;
1146 }
1147 throw err;
1148 }
1149 // If the output index is larger than the number of elements in stack, append
1150 if (output_index >= stack.size()) {
1151 PRINT_RESULT("", "pushed to ", stack.size(), result)
1152 stack.push_back(result);
1153 } else {
1154
1155 PRINT_RESULT("", "saved to ", output_index, result)
1156 stack[output_index] = result;
1157 }
1158 return 0;
1159 };
1160
1170 static inline size_t execute_DIVIDE_WITH_CONSTRAINTS(Builder* builder,
1171 std::vector<ExecutionHandler>& stack,
1172 Instruction& instruction)
1173 {
1174 (void)builder;
1175 if (stack.size() == 0) {
1176 return 1;
1177 }
1178 size_t first_index = instruction.arguments.fiveArgs.in1 % stack.size();
1179 size_t second_index = instruction.arguments.fiveArgs.in2 % stack.size();
1180 size_t quotient_bit_size = instruction.arguments.fiveArgs.qbs;
1181 size_t remainder_bit_size = instruction.arguments.fiveArgs.rbs;
1182 size_t output_index = instruction.arguments.fiveArgs.out;
1183 PRINT_TWO_ARG_TWO_VALUES_INSTRUCTION(first_index,
1184 second_index,
1185 quotient_bit_size,
1186 remainder_bit_size,
1187 stack,
1188 "DIVIDE_WITH_CONSTRAINTS:",
1189 "/",
1190 "quotient < 2**",
1191 "remainder < 2**")
1192
1193 // If difference bit size is too big, it should be caught by assertion.
1194 if ((quotient_bit_size > suint_t::MAX_BIT_NUM) || (remainder_bit_size > suint_t::MAX_BIT_NUM)) {
1195 return 0;
1196 }
1197 // If both constants, should be handled by assert
1198 if (stack[first_index].suint.is_constant()) {
1199 return 0;
1200 }
1201 ExecutionHandler result;
1202 try {
1203 result = stack[first_index].divide(stack[second_index], quotient_bit_size, remainder_bit_size);
1204 } catch (std::runtime_error& err) {
1205 if (!strncmp(err.what(),
1206 "exceeded modulus in safe_uint class",
1207 sizeof("exceeded modulus in safe_uint class"))) {
1208 return 1;
1209 }
1210 if (!strncmp(err.what(),
1211 "maximum value exceeded in safe_uint minus operator",
1212 sizeof("maximum value exceeded in safe_uint minus operator"))) {
1213 return 1;
1214 }
1215 throw err;
1216 }
1217 // If the output index is larger than the number of elements in stack, append
1218 if (output_index >= stack.size()) {
1219 PRINT_RESULT("", "pushed to ", stack.size(), result)
1220 stack.push_back(result);
1221 } else {
1222
1223 PRINT_RESULT("", "saved to ", output_index, result)
1224 stack[output_index] = result;
1225 }
1226 return 0;
1227 };
1237 static inline size_t execute_SLICE(Builder* builder,
1238 std::vector<ExecutionHandler>& stack,
1239 Instruction& instruction)
1240 {
1241 (void)builder;
1242 if (stack.size() == 0) {
1243 return 1;
1244 }
1245 size_t first_index = instruction.arguments.sliceArgs.in1 % stack.size();
1246 uint8_t lsb = instruction.arguments.sliceArgs.lsb;
1247 uint8_t msb = instruction.arguments.sliceArgs.msb;
1248 size_t second_index = instruction.arguments.sliceArgs.out1;
1249 size_t third_index = instruction.arguments.sliceArgs.out2;
1250 size_t output_index = instruction.arguments.sliceArgs.out3;
1251 PRINT_SLICE(first_index, lsb, msb, stack)
1252 // Check assert conditions
1253 if ((lsb > msb) || (msb > 252) ||
1254 (static_cast<uint256_t>(stack[first_index].suint.get_value()) >=
1255 (static_cast<uint256_t>(1) << grumpkin::MAX_NO_WRAP_INTEGER_BIT_LENGTH))) {
1256 return 0;
1257 }
1258 PRINT_SLICE(first_index, lsb, msb, stack)
1259 auto slices = stack[first_index].slice(lsb, msb);
1260 std::array<std::pair<ExecutionHandler, size_t>, 3> what_where = { std::make_pair(slices[0], second_index),
1261 std::make_pair(slices[1], third_index),
1262 std::make_pair(slices[2], output_index) };
1263 for (auto& x : what_where) {
1264 auto suints_count = stack.size();
1265 if (x.second >= suints_count) {
1266
1267 PRINT_RESULT("\t", "pushed to ", stack.size(), x.first)
1268 stack.push_back(x.first);
1269 } else {
1270
1271 PRINT_RESULT("\t", "saved to ", x.second, x.first)
1272 stack[x.second] = x.first;
1273 }
1274 }
1275
1276 return 0;
1277 }
1286 static inline size_t execute_RANDOMSEED(Builder* builder,
1287 std::vector<ExecutionHandler>& stack,
1288 Instruction& instruction)
1289 {
1290 (void)builder;
1291 (void)stack;
1292
1293 VarianceRNG.reseed(instruction.arguments.randomseed);
1294 return 0;
1295 };
1296 };
1297
1298 typedef std::vector<ExecutionHandler> ExecutionState;
1299};
1300
1301#ifdef HAVOC_TESTING
1302
1303extern "C" int LLVMFuzzerInitialize(int* argc, char*** argv)
1304{
1305 (void)argc;
1306 (void)argv;
1307 // These are the settings, optimized for the safeuint class (under them, fuzzer reaches maximum expected coverage in
1308 // 40 seconds)
1309 fuzzer_havoc_settings = HavocSettings{
1310 .GEN_LLVM_POST_MUTATION_PROB = 30, // Out of 200
1311 .GEN_MUTATION_COUNT_LOG = 5, // Fully checked
1312 .GEN_STRUCTURAL_MUTATION_PROBABILITY = 300, // Fully checked
1313 .GEN_VALUE_MUTATION_PROBABILITY = 700, // Fully checked
1314 .ST_MUT_DELETION_PROBABILITY = 100, // Fully checked
1315 .ST_MUT_DUPLICATION_PROBABILITY = 80, // Fully checked
1316 .ST_MUT_INSERTION_PROBABILITY = 120, // Fully checked
1317 .ST_MUT_MAXIMUM_DELETION_LOG = 6, // Fully checked
1318 .ST_MUT_MAXIMUM_DUPLICATION_LOG = 2, // Fully checked
1319 .ST_MUT_SWAP_PROBABILITY = 50, // Fully checked
1320 .VAL_MUT_LLVM_MUTATE_PROBABILITY = 250, // Fully checked
1321 .VAL_MUT_MONTGOMERY_PROBABILITY = 130, // Fully checked
1322 .VAL_MUT_NON_MONTGOMERY_PROBABILITY = 50, // Fully checked
1323 .VAL_MUT_SMALL_ADDITION_PROBABILITY = 110, // Fully checked
1324 .VAL_MUT_SPECIAL_VALUE_PROBABILITY = 130 // Fully checked
1325
1326 };
1331 /*
1332 std::random_device rd;
1333 std::uniform_int_distribution<uint64_t> dist(0, ~(uint64_t)(0));
1334 srandom(static_cast<unsigned int>(dist(rd)));
1335
1336 fuzzer_havoc_settings =
1337 HavocSettings{ .GEN_MUTATION_COUNT_LOG = static_cast<size_t>((random() % 8) + 1),
1338 .GEN_STRUCTURAL_MUTATION_PROBABILITY = static_cast<size_t>(random() % 100),
1339 .GEN_VALUE_MUTATION_PROBABILITY = static_cast<size_t>(random() % 100),
1340 .ST_MUT_DELETION_PROBABILITY = static_cast<size_t>(random() % 100),
1341 .ST_MUT_DUPLICATION_PROBABILITY = static_cast<size_t>(random() % 100),
1342 .ST_MUT_INSERTION_PROBABILITY = static_cast<size_t>((random() % 99) + 1),
1343 .ST_MUT_MAXIMUM_DELETION_LOG = static_cast<size_t>((random() % 8) + 1),
1344 .ST_MUT_MAXIMUM_DUPLICATION_LOG = static_cast<size_t>((random() % 8) + 1),
1345 .ST_MUT_SWAP_PROBABILITY = static_cast<size_t>(random() % 100),
1346 .VAL_MUT_LLVM_MUTATE_PROBABILITY = static_cast<size_t>(random() % 100),
1347 .VAL_MUT_MONTGOMERY_PROBABILITY = static_cast<size_t>(random() % 100),
1348 .VAL_MUT_NON_MONTGOMERY_PROBABILITY = static_cast<size_t>(random() % 100),
1349 .VAL_MUT_SMALL_ADDITION_PROBABILITY = static_cast<size_t>(random() % 100),
1350 .VAL_MUT_SPECIAL_VALUE_PROBABILITY = static_cast<size_t>(random() % 100)
1351
1352 };
1353 while (fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY == 0 &&
1354 fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY == 0) {
1355 fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY = static_cast<size_t>(random() % 8);
1356 fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY = static_cast<size_t>(random() % 8);
1357 }
1358 */
1359
1360 // fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB = static_cast<size_t>(((random() % (20 - 1)) + 1) * 10);
1365 /*
1366 std::cerr << "CUSTOM MUTATOR SETTINGS:" << std::endl
1367 << "################################################################" << std::endl
1368 << "GEN_LLVM_POST_MUTATION_PROB: " << fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB << std::endl
1369 << "GEN_MUTATION_COUNT_LOG: " << fuzzer_havoc_settings.GEN_MUTATION_COUNT_LOG << std::endl
1370 << "GEN_STRUCTURAL_MUTATION_PROBABILITY: " << fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY
1371 << std::endl
1372 << "GEN_VALUE_MUTATION_PROBABILITY: " << fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY << std::endl
1373 << "ST_MUT_DELETION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_DELETION_PROBABILITY << std::endl
1374 << "ST_MUT_DUPLICATION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_DUPLICATION_PROBABILITY << std::endl
1375 << "ST_MUT_INSERTION_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_INSERTION_PROBABILITY << std::endl
1376 << "ST_MUT_MAXIMUM_DELETION_LOG: " << fuzzer_havoc_settings.ST_MUT_MAXIMUM_DELETION_LOG << std::endl
1377 << "ST_MUT_MAXIMUM_DUPLICATION_LOG: " << fuzzer_havoc_settings.ST_MUT_MAXIMUM_DUPLICATION_LOG << std::endl
1378 << "ST_MUT_SWAP_PROBABILITY: " << fuzzer_havoc_settings.ST_MUT_SWAP_PROBABILITY << std::endl
1379 << "VAL_MUT_LLVM_MUTATE_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_LLVM_MUTATE_PROBABILITY
1380 << std::endl
1381 << "VAL_MUT_MONTGOMERY_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_MONTGOMERY_PROBABILITY << std::endl
1382 << "VAL_MUT_NON_MONTGOMERY_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_NON_MONTGOMERY_PROBABILITY
1383 << std::endl
1384 << "VAL_MUT_SMALL_ADDITION_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_SMALL_ADDITION_PROBABILITY
1385 << std::endl
1386 << "VAL_MUT_SMALL_MULTIPLICATION_PROBABILITY: "
1387 << fuzzer_havoc_settings.VAL_MUT_SMALL_MULTIPLICATION_PROBABILITY << std::endl
1388 << "VAL_MUT_SPECIAL_VALUE_PROBABILITY: " << fuzzer_havoc_settings.VAL_MUT_SPECIAL_VALUE_PROBABILITY
1389 << std::endl;
1390 */
1391 std::vector<size_t> structural_mutation_distribution;
1392 std::vector<size_t> value_mutation_distribution;
1393 size_t temp = 0;
1394 temp += fuzzer_havoc_settings.ST_MUT_DELETION_PROBABILITY;
1395 structural_mutation_distribution.push_back(temp);
1396 temp += fuzzer_havoc_settings.ST_MUT_DUPLICATION_PROBABILITY;
1397 structural_mutation_distribution.push_back(temp);
1398 temp += fuzzer_havoc_settings.ST_MUT_INSERTION_PROBABILITY;
1399 structural_mutation_distribution.push_back(temp);
1400 temp += fuzzer_havoc_settings.ST_MUT_SWAP_PROBABILITY;
1401 structural_mutation_distribution.push_back(temp);
1402 fuzzer_havoc_settings.structural_mutation_distribution = structural_mutation_distribution;
1403
1404 temp = 0;
1405 temp += fuzzer_havoc_settings.VAL_MUT_LLVM_MUTATE_PROBABILITY;
1406 value_mutation_distribution.push_back(temp);
1407 temp += fuzzer_havoc_settings.VAL_MUT_SMALL_ADDITION_PROBABILITY;
1408 value_mutation_distribution.push_back(temp);
1409
1410 temp += fuzzer_havoc_settings.VAL_MUT_SPECIAL_VALUE_PROBABILITY;
1411 value_mutation_distribution.push_back(temp);
1412 fuzzer_havoc_settings.value_mutation_distribution = value_mutation_distribution;
1413 return 0;
1414}
1415#endif
1416#ifndef DISABLE_CUSTOM_MUTATORS
1421extern "C" size_t LLVMFuzzerCustomMutator(uint8_t* Data, size_t Size, size_t MaxSize, unsigned int Seed)
1422{
1423 using FuzzerClass = SafeUintFuzzBase<proof_system::StandardCircuitBuilder>;
1424 auto fast_random = FastRandom(Seed);
1425 auto size_occupied = ArithmeticFuzzHelper<FuzzerClass>::MutateInstructionBuffer(Data, Size, MaxSize, fast_random);
1426 if ((fast_random.next() % 200) < fuzzer_havoc_settings.GEN_LLVM_POST_MUTATION_PROB) {
1427 size_occupied = LLVMFuzzerMutate(Data, size_occupied, MaxSize);
1428 }
1429 return size_occupied;
1430}
1431
1436extern "C" size_t LLVMFuzzerCustomCrossOver(const uint8_t* Data1,
1437 size_t Size1,
1438 const uint8_t* Data2,
1439 size_t Size2,
1440 uint8_t* Out,
1441 size_t MaxOutSize,
1442 unsigned int Seed)
1443{
1444 using FuzzerClass = SafeUintFuzzBase<proof_system::StandardCircuitBuilder>;
1445 auto fast_random = FastRandom(Seed);
1446 auto vecA = ArithmeticFuzzHelper<FuzzerClass>::parseDataIntoInstructions(Data1, Size1);
1447 auto vecB = ArithmeticFuzzHelper<FuzzerClass>::parseDataIntoInstructions(Data2, Size2);
1448 auto vecC = ArithmeticFuzzHelper<FuzzerClass>::crossoverInstructionVector(vecA, vecB, fast_random);
1449 return ArithmeticFuzzHelper<FuzzerClass>::writeInstructionsToBuffer(vecC, Out, MaxOutSize);
1450}
1451
1452#endif
1453
1458extern "C" size_t LLVMFuzzerTestOneInput(const uint8_t* Data, size_t Size)
1459{
1460 RunWithBuilders<SafeUintFuzzBase, FuzzerCircuitTypes>(Data, Size, VarianceRNG);
1461 return 0;
1462}
1463
1464#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
FastRandom
Class for quickly deterministically creating new random values. We don't care about distribution much...
Definition: fuzzer.hpp:64
SafeUintFuzzBase::ArgSizes
Definition: safe_uint.fuzzer.hpp:451
SafeUintFuzzBase::ExecutionHandler
This class implements the execution of safeuint with an oracle to detect discrepancies.
Definition: safe_uint.fuzzer.hpp:587
SafeUintFuzzBase::ExecutionHandler::execute_SUBTRACT
static size_t execute_SUBTRACT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the subtraction operator instruction.
Definition: safe_uint.fuzzer.hpp:880
SafeUintFuzzBase::ExecutionHandler::execute_MULTIPLY
static size_t execute_MULTIPLY(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the multiply instruction.
Definition: safe_uint.fuzzer.hpp:784
SafeUintFuzzBase::ExecutionHandler::execute_SLICE
static size_t execute_SLICE(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the slice instruction.
Definition: safe_uint.fuzzer.hpp:1237
SafeUintFuzzBase::ExecutionHandler::execute_SUBTRACT_WITH_CONSTRAINT
static size_t execute_SUBTRACT_WITH_CONSTRAINT(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the SUBTRACT_WITH_CONSTRAINT instruction.
Definition: safe_uint.fuzzer.hpp:1115
SafeUintFuzzBase::ExecutionHandler::execute_MADD
static size_t execute_MADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the MADD instruction.
Definition: safe_uint.fuzzer.hpp:1062
SafeUintFuzzBase::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: safe_uint.fuzzer.hpp:712
SafeUintFuzzBase::ExecutionHandler::execute_DIVIDE_WITH_CONSTRAINTS
static size_t execute_DIVIDE_WITH_CONSTRAINTS(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Definition: safe_uint.fuzzer.hpp:1170
SafeUintFuzzBase::ExecutionHandler::execute_DIVIDE
static size_t execute_DIVIDE(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the division operator instruction.
Definition: safe_uint.fuzzer.hpp:947
SafeUintFuzzBase::ExecutionHandler::execute_ADD_TWO
static size_t execute_ADD_TWO(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the ADD_TWO instruction.
Definition: safe_uint.fuzzer.hpp:1011
SafeUintFuzzBase::ExecutionHandler::execute_RANDOMSEED
static size_t execute_RANDOMSEED(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the RANDOMSEED instruction.
Definition: safe_uint.fuzzer.hpp:1286
SafeUintFuzzBase::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: safe_uint.fuzzer.hpp:765
SafeUintFuzzBase::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: safe_uint.fuzzer.hpp:733
SafeUintFuzzBase::ExecutionHandler::execute_ADD
static size_t execute_ADD(Builder *builder, std::vector< ExecutionHandler > &stack, Instruction &instruction)
Execute the addition operator instruction.
Definition: safe_uint.fuzzer.hpp:836
SafeUintFuzzBase::Instruction
A class representing a single fuzzing instruction.
Definition: safe_uint.fuzzer.hpp:124
SafeUintFuzzBase::Instruction::generateRandom
static Instruction generateRandom(T &rng)
Generate a random instruction.
Definition: safe_uint.fuzzer.hpp:193
SafeUintFuzzBase::Instruction::mutateInstruction
static Instruction mutateInstruction(Instruction instruction, T &rng, HavocSettings &havoc_config)
Mutate a single instruction.
Definition: safe_uint.fuzzer.hpp:383
SafeUintFuzzBase::Instruction::mutateFieldElement
static fr mutateFieldElement(fr e, T &rng, HavocSettings &havoc_config)
Mutate the value of a field element.
Definition: safe_uint.fuzzer.hpp:289
SafeUintFuzzBase::Parser
Parser class handles the parsing and writing the instructions back to data buffer.
Definition: safe_uint.fuzzer.hpp:471
SafeUintFuzzBase::Parser::writeInstruction
static void writeInstruction(Instruction &instruction, uint8_t *Data)
Write a single instruction to buffer.
Definition: safe_uint.fuzzer.hpp:531
SafeUintFuzzBase::Parser::parseInstructionArgs
static Instruction parseInstructionArgs(uint8_t *Data)
Parse a single instruction from data.
Definition: safe_uint.fuzzer.hpp:480
SafeUintFuzzBase
The class parametrizing SafeUint fuzzing instructions, execution, etc.
Definition: safe_uint.fuzzer.hpp:111
numeric::uint256_t
Definition: uint256.hpp:25
proof_system::StandardCircuitBuilder_
Definition: standard_circuit_builder.hpp:12
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::safe_uint_t
Definition: safe_uint.hpp:17
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
HavocSettings
Definition: fuzzer.hpp:27
SafeUintFuzzBase::Instruction::Element
Definition: safe_uint.fuzzer.hpp:142
SafeUintFuzzBase::Instruction::FiveArgs
Definition: safe_uint.fuzzer.hpp:157
SafeUintFuzzBase::Instruction::FourArgs
Definition: safe_uint.fuzzer.hpp:151
SafeUintFuzzBase::Instruction::SliceArgs
Definition: safe_uint.fuzzer.hpp:165
SafeUintFuzzBase::Instruction::ThreeArgs
Definition: safe_uint.fuzzer.hpp:146
SafeUintFuzzBase::Instruction::ArgumentContents
Definition: safe_uint.fuzzer.hpp:173
Generated by doxygen 1.9.6