Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
ultra_circuit_builder.cpp
Go to the documentation of this file.
1// === AUDIT STATUS ===
2// internal: { status: not started, auditors: [], date: YYYY-MM-DD }
3// external_1: { status: not started, auditors: [], date: YYYY-MM-DD }
4// external_2: { status: not started, auditors: [], date: YYYY-MM-DD }
5// =====================
6
14#include "ultra_circuit_builder.hpp"
15#include "barretenberg/common/assert.hpp"
16#include "barretenberg/common/ref_vector.hpp"
17#include "barretenberg/crypto/poseidon2/poseidon2_params.hpp"
18#include "rom_ram_logic.hpp"
19
20#include "barretenberg/crypto/sha256/sha256.hpp"
21#include "barretenberg/serialize/msgpack_impl.hpp"
22#include <execution>
23#include <unordered_map>
24#include <unordered_set>
25
26namespace bb {
27
28template <typename ExecutionTrace>
29void UltraCircuitBuilder_<ExecutionTrace>::finalize_circuit(const bool ensure_nonzero)
30{
56 if (!circuit_finalized) {
57 if (ensure_nonzero) {
58 add_gates_to_ensure_all_polys_are_non_zero();
59 }
60 process_non_native_field_multiplications();
61#ifndef ULTRA_FUZZ
62 this->rom_ram_logic.process_ROM_arrays(this);
63 this->rom_ram_logic.process_RAM_arrays(this);
64 process_range_lists();
65#endif
66 populate_public_inputs_block();
67 circuit_finalized = true;
68 } else {
69 // Gates added after first call to finalize will not be processed since finalization is only performed once
70 info("WARNING: Redundant call to finalize_circuit(). Is this intentional?");
71 }
72}
73
79// TODO(#423): This function adds valid (but arbitrary) gates to ensure that the circuit which includes
80// them will not result in any zero-polynomials. It also ensures that the first coefficient of the wire
81// polynomials is zero, which is required for them to be shiftable.
82template <typename ExecutionTrace>
83void UltraCircuitBuilder_<ExecutionTrace>::add_gates_to_ensure_all_polys_are_non_zero()
84{
85 // q_m, q_1, q_2, q_3, q_4
86 blocks.arithmetic.populate_wires(this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
87 blocks.arithmetic.q_m().emplace_back(1);
88 blocks.arithmetic.q_1().emplace_back(1);
89 blocks.arithmetic.q_2().emplace_back(1);
90 blocks.arithmetic.q_3().emplace_back(1);
91 blocks.arithmetic.q_4().emplace_back(1);
92 blocks.arithmetic.q_c().emplace_back(0);
93 blocks.arithmetic.q_delta_range().emplace_back(0);
94 blocks.arithmetic.q_arith().emplace_back(0);
95 blocks.arithmetic.q_lookup_type().emplace_back(0);
96 blocks.arithmetic.q_elliptic().emplace_back(0);
97 blocks.arithmetic.q_memory().emplace_back(0);
98 blocks.arithmetic.q_nnf().emplace_back(0);
99 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
100 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
101 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
102 blocks.arithmetic.pad_additional();
103 }
104 check_selector_length_consistency();
105 ++this->num_gates;
106
107 // q_delta_range
108 blocks.delta_range.populate_wires(this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
109 blocks.delta_range.q_m().emplace_back(0);
110 blocks.delta_range.q_1().emplace_back(0);
111 blocks.delta_range.q_2().emplace_back(0);
112 blocks.delta_range.q_3().emplace_back(0);
113 blocks.delta_range.q_4().emplace_back(0);
114 blocks.delta_range.q_c().emplace_back(0);
115 blocks.delta_range.q_delta_range().emplace_back(1);
116 blocks.delta_range.q_arith().emplace_back(0);
117 blocks.delta_range.q_lookup_type().emplace_back(0);
118 blocks.delta_range.q_elliptic().emplace_back(0);
119 blocks.delta_range.q_memory().emplace_back(0);
120 blocks.delta_range.q_nnf().emplace_back(0);
121 blocks.delta_range.q_poseidon2_external().emplace_back(0);
122 blocks.delta_range.q_poseidon2_internal().emplace_back(0);
123
124 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
125 blocks.delta_range.pad_additional();
126 }
127 check_selector_length_consistency();
128 ++this->num_gates;
129 create_dummy_gate(blocks.delta_range, this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
130
131 // q_elliptic
132 blocks.elliptic.populate_wires(this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
133 blocks.elliptic.q_m().emplace_back(0);
134 blocks.elliptic.q_1().emplace_back(0);
135 blocks.elliptic.q_2().emplace_back(0);
136 blocks.elliptic.q_3().emplace_back(0);
137 blocks.elliptic.q_4().emplace_back(0);
138 blocks.elliptic.q_c().emplace_back(0);
139 blocks.elliptic.q_delta_range().emplace_back(0);
140 blocks.elliptic.q_arith().emplace_back(0);
141 blocks.elliptic.q_lookup_type().emplace_back(0);
142 blocks.elliptic.q_elliptic().emplace_back(1);
143 blocks.elliptic.q_memory().emplace_back(0);
144 blocks.elliptic.q_nnf().emplace_back(0);
145 blocks.elliptic.q_poseidon2_external().emplace_back(0);
146 blocks.elliptic.q_poseidon2_internal().emplace_back(0);
147 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
148 blocks.elliptic.pad_additional();
149 }
150 check_selector_length_consistency();
151 ++this->num_gates;
152 create_dummy_gate(blocks.elliptic, this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
153
154 // q_memory
155 blocks.memory.populate_wires(this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
156 blocks.memory.q_m().emplace_back(0);
157 blocks.memory.q_1().emplace_back(0);
158 blocks.memory.q_2().emplace_back(0);
159 blocks.memory.q_3().emplace_back(0);
160 blocks.memory.q_4().emplace_back(0);
161 blocks.memory.q_c().emplace_back(0);
162 blocks.memory.q_delta_range().emplace_back(0);
163 blocks.memory.q_arith().emplace_back(0);
164 blocks.memory.q_lookup_type().emplace_back(0);
165 blocks.memory.q_elliptic().emplace_back(0);
166 blocks.memory.q_memory().emplace_back(1);
167 blocks.memory.q_nnf().emplace_back(0);
168 blocks.memory.q_poseidon2_external().emplace_back(0);
169 blocks.memory.q_poseidon2_internal().emplace_back(0);
170 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
171 blocks.memory.pad_additional();
172 }
173 check_selector_length_consistency();
174 ++this->num_gates;
175 create_dummy_gate(blocks.memory, this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
176
177 // q_nnf
178 blocks.nnf.populate_wires(this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
179 blocks.nnf.q_m().emplace_back(0);
180 blocks.nnf.q_1().emplace_back(0);
181 blocks.nnf.q_2().emplace_back(0);
182 blocks.nnf.q_3().emplace_back(0);
183 blocks.nnf.q_4().emplace_back(0);
184 blocks.nnf.q_c().emplace_back(0);
185 blocks.nnf.q_delta_range().emplace_back(0);
186 blocks.nnf.q_arith().emplace_back(0);
187 blocks.nnf.q_lookup_type().emplace_back(0);
188 blocks.nnf.q_elliptic().emplace_back(0);
189 blocks.nnf.q_memory().emplace_back(0);
190 blocks.nnf.q_nnf().emplace_back(1);
191 blocks.nnf.q_poseidon2_external().emplace_back(0);
192 blocks.nnf.q_poseidon2_internal().emplace_back(0);
193 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
194 blocks.nnf.pad_additional();
195 }
196 check_selector_length_consistency();
197 ++this->num_gates;
198 create_dummy_gate(blocks.nnf, this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
199
200 // Add nonzero values in w_4 and q_c (q_4*w_4 + q_c --> 1*1 - 1 = 0)
201 this->one_idx = put_constant_variable(FF::one());
202 create_big_add_gate({ this->zero_idx, this->zero_idx, this->zero_idx, this->one_idx, 0, 0, 0, 1, -1 });
203
204 // Take care of all polys related to lookups (q_lookup, tables, sorted, etc)
205 // by doing a dummy lookup with a special table.
206 // Note: the 4th table poly is the table index: this is not the value of the table
207 // type enum but rather the index of the table in the list of all tables utilized
208 // in the circuit. Therefore we naively need two different basic tables (indices 0, 1)
209 // to get a non-zero value in table_4.
210 // The multitable operates on 2-bit values, so the maximum is 3
211 uint32_t left_value = 3;
212 uint32_t right_value = 3;
213
214 FF left_witness_value = fr{ left_value, 0, 0, 0 }.to_montgomery_form();
215 FF right_witness_value = fr{ right_value, 0, 0, 0 }.to_montgomery_form();
216
217 uint32_t left_witness_index = this->add_variable(left_witness_value);
218 uint32_t right_witness_index = this->add_variable(right_witness_value);
219 const auto dummy_accumulators = plookup::get_lookup_accumulators(
220 plookup::MultiTableId::HONK_DUMMY_MULTI, left_witness_value, right_witness_value, true);
221 auto read_data = create_gates_from_plookup_accumulators(
222 plookup::MultiTableId::HONK_DUMMY_MULTI, dummy_accumulators, left_witness_index, right_witness_index);
223
224 update_used_witnesses(left_witness_index);
225 update_used_witnesses(right_witness_index);
226 std::array<std::vector<uint32_t>, 3> parse_read_data{ read_data[plookup::ColumnIdx::C1],
227 read_data[plookup::ColumnIdx::C2],
228 read_data[plookup::ColumnIdx::C3] };
229 for (const auto& column : parse_read_data) {
230 for (const auto& index : column) {
231 update_used_witnesses(index);
232 }
233 }
234
235 // mock a poseidon external gate, with all zeros as input
236 blocks.poseidon2_external.populate_wires(this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
237 blocks.poseidon2_external.q_m().emplace_back(0);
238 blocks.poseidon2_external.q_1().emplace_back(0);
239 blocks.poseidon2_external.q_2().emplace_back(0);
240 blocks.poseidon2_external.q_3().emplace_back(0);
241 blocks.poseidon2_external.q_c().emplace_back(0);
242 blocks.poseidon2_external.q_arith().emplace_back(0);
243 blocks.poseidon2_external.q_4().emplace_back(0);
244 blocks.poseidon2_external.q_delta_range().emplace_back(0);
245 blocks.poseidon2_external.q_lookup_type().emplace_back(0);
246 blocks.poseidon2_external.q_elliptic().emplace_back(0);
247 blocks.poseidon2_external.q_memory().emplace_back(0);
248 blocks.poseidon2_external.q_nnf().emplace_back(0);
249 blocks.poseidon2_external.q_poseidon2_external().emplace_back(1);
250 blocks.poseidon2_external.q_poseidon2_internal().emplace_back(0);
251 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
252 blocks.poseidon2_external.pad_additional();
253 }
254 check_selector_length_consistency();
255 ++this->num_gates;
256
257 // dummy gate to be read into by previous poseidon external gate via shifts
258 this->create_dummy_gate(blocks.poseidon2_external, this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
259
260 // mock a poseidon internal gate, with all zeros as input
261 blocks.poseidon2_internal.populate_wires(this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
262 blocks.poseidon2_internal.q_m().emplace_back(0);
263 blocks.poseidon2_internal.q_1().emplace_back(0);
264 blocks.poseidon2_internal.q_2().emplace_back(0);
265 blocks.poseidon2_internal.q_3().emplace_back(0);
266 blocks.poseidon2_internal.q_c().emplace_back(0);
267 blocks.poseidon2_internal.q_arith().emplace_back(0);
268 blocks.poseidon2_internal.q_4().emplace_back(0);
269 blocks.poseidon2_internal.q_delta_range().emplace_back(0);
270 blocks.poseidon2_internal.q_lookup_type().emplace_back(0);
271 blocks.poseidon2_internal.q_elliptic().emplace_back(0);
272 blocks.poseidon2_internal.q_memory().emplace_back(0);
273 blocks.poseidon2_internal.q_nnf().emplace_back(0);
274 blocks.poseidon2_internal.q_poseidon2_external().emplace_back(0);
275 blocks.poseidon2_internal.q_poseidon2_internal().emplace_back(1);
276 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
277 blocks.poseidon2_internal.pad_additional();
278 }
279 check_selector_length_consistency();
280 ++this->num_gates;
281
282 // dummy gate to be read into by previous poseidon internal gate via shifts
283 create_dummy_gate(blocks.poseidon2_internal, this->zero_idx, this->zero_idx, this->zero_idx, this->zero_idx);
284}
285
294template <typename ExecutionTrace> void UltraCircuitBuilder_<ExecutionTrace>::create_add_gate(const add_triple_<FF>& in)
295{
296 this->assert_valid_variables({ in.a, in.b, in.c });
297
298 blocks.arithmetic.populate_wires(in.a, in.b, in.c, this->zero_idx);
299 blocks.arithmetic.q_m().emplace_back(0);
300 blocks.arithmetic.q_1().emplace_back(in.a_scaling);
301 blocks.arithmetic.q_2().emplace_back(in.b_scaling);
302 blocks.arithmetic.q_3().emplace_back(in.c_scaling);
303 blocks.arithmetic.q_c().emplace_back(in.const_scaling);
304 blocks.arithmetic.q_arith().emplace_back(1);
305 blocks.arithmetic.q_4().emplace_back(0);
306 blocks.arithmetic.q_delta_range().emplace_back(0);
307 blocks.arithmetic.q_lookup_type().emplace_back(0);
308 blocks.arithmetic.q_elliptic().emplace_back(0);
309 blocks.arithmetic.q_memory().emplace_back(0);
310 blocks.arithmetic.q_nnf().emplace_back(0);
311 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
312 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
313 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
314 blocks.arithmetic.pad_additional();
315 }
316 check_selector_length_consistency();
317 ++this->num_gates;
318}
319
328template <typename ExecutionTrace>
329void UltraCircuitBuilder_<ExecutionTrace>::create_big_mul_add_gate(const mul_quad_<FF>& in,
330 const bool include_next_gate_w_4)
331{
332 this->assert_valid_variables({ in.a, in.b, in.c, in.d });
333 blocks.arithmetic.populate_wires(in.a, in.b, in.c, in.d);
334 blocks.arithmetic.q_m().emplace_back(include_next_gate_w_4 ? in.mul_scaling * FF(2) : in.mul_scaling);
335 blocks.arithmetic.q_1().emplace_back(in.a_scaling);
336 blocks.arithmetic.q_2().emplace_back(in.b_scaling);
337 blocks.arithmetic.q_3().emplace_back(in.c_scaling);
338 blocks.arithmetic.q_c().emplace_back(in.const_scaling);
339 blocks.arithmetic.q_arith().emplace_back(include_next_gate_w_4 ? 2 : 1);
340 blocks.arithmetic.q_4().emplace_back(in.d_scaling);
341 blocks.arithmetic.q_delta_range().emplace_back(0);
342 blocks.arithmetic.q_lookup_type().emplace_back(0);
343 blocks.arithmetic.q_elliptic().emplace_back(0);
344 blocks.arithmetic.q_memory().emplace_back(0);
345 blocks.arithmetic.q_nnf().emplace_back(0);
346 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
347 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
348 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
349 blocks.arithmetic.pad_additional();
350 }
351 check_selector_length_consistency();
352 ++this->num_gates;
353}
354
363template <typename ExecutionTrace>
364void UltraCircuitBuilder_<ExecutionTrace>::create_big_add_gate(const add_quad_<FF>& in,
365 const bool include_next_gate_w_4)
366{
367 this->assert_valid_variables({ in.a, in.b, in.c, in.d });
368 blocks.arithmetic.populate_wires(in.a, in.b, in.c, in.d);
369 blocks.arithmetic.q_m().emplace_back(0);
370 blocks.arithmetic.q_1().emplace_back(in.a_scaling);
371 blocks.arithmetic.q_2().emplace_back(in.b_scaling);
372 blocks.arithmetic.q_3().emplace_back(in.c_scaling);
373 blocks.arithmetic.q_c().emplace_back(in.const_scaling);
374 blocks.arithmetic.q_arith().emplace_back(include_next_gate_w_4 ? 2 : 1);
375 blocks.arithmetic.q_4().emplace_back(in.d_scaling);
376 blocks.arithmetic.q_delta_range().emplace_back(0);
377 blocks.arithmetic.q_lookup_type().emplace_back(0);
378 blocks.arithmetic.q_elliptic().emplace_back(0);
379 blocks.arithmetic.q_memory().emplace_back(0);
380 blocks.arithmetic.q_nnf().emplace_back(0);
381 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
382 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
383 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
384 blocks.arithmetic.pad_additional();
385 }
386 check_selector_length_consistency();
387 ++this->num_gates;
388}
389
396template <typename ExecutionTrace>
397void UltraCircuitBuilder_<ExecutionTrace>::create_big_add_gate_with_bit_extraction(const add_quad_<FF>& in)
398{
399 // This method is an artifact of a turbo plonk feature that implicitly extracts
400 // a high or low bit from a base-4 quad and adds it into the arithmetic gate relationship.
401 // This has been removed in the plookup composer due to it's infrequent use not being worth the extra
402 // cost incurred by the prover for the extra field muls required.
403
404 // We have wires a, b, c, d, where
405 // a + b + c + d + 6 * (extracted bit) = 0
406 // (extracted bit) is the high bit pulled from c - 4d
407
408 this->assert_valid_variables({ in.a, in.b, in.c, in.d });
409
410 const uint256_t quad = this->get_variable(in.c) - this->get_variable(in.d) * 4;
411 const auto lo_bit = quad & uint256_t(1);
412 const auto hi_bit = (quad & uint256_t(2)) >> 1;
413 const auto lo_idx = this->add_variable(lo_bit);
414 const auto hi_idx = this->add_variable(hi_bit);
415 // lo + hi * 2 - c + 4 * d = 0
416 create_big_add_gate({
417 lo_idx,
418 hi_idx,
419 in.c,
420 in.d,
421 1,
422 2,
423 -1,
424 4,
425 0,
426 });
427
428 // create temporary variable t = in.a * in.a_scaling + 6 * hi_bit
429 const auto t = this->get_variable(in.a) * in.a_scaling + FF(hi_bit) * 6;
430 const auto t_idx = this->add_variable(t);
431 create_big_add_gate({
432 in.a,
433 hi_idx,
434 t_idx,
435 this->zero_idx,
436 in.a_scaling,
437 6,
438 -1,
439 0,
440 0,
441 });
442 // (t = a + 6 * hi_bit) + b + c + d = 0
443 create_big_add_gate({
444 t_idx,
445 in.b,
446 in.c,
447 in.d,
448 1,
449 in.b_scaling,
450 in.c_scaling,
451 in.d_scaling,
452 in.const_scaling,
453 });
454}
460template <typename ExecutionTrace>
461void UltraCircuitBuilder_<ExecutionTrace>::create_big_mul_gate(const mul_quad_<FF>& in)
462{
463 this->assert_valid_variables({ in.a, in.b, in.c, in.d });
464
465 blocks.arithmetic.populate_wires(in.a, in.b, in.c, in.d);
466 blocks.arithmetic.q_m().emplace_back(in.mul_scaling);
467 blocks.arithmetic.q_1().emplace_back(in.a_scaling);
468 blocks.arithmetic.q_2().emplace_back(in.b_scaling);
469 blocks.arithmetic.q_3().emplace_back(in.c_scaling);
470 blocks.arithmetic.q_c().emplace_back(in.const_scaling);
471 blocks.arithmetic.q_arith().emplace_back(1);
472 blocks.arithmetic.q_4().emplace_back(in.d_scaling);
473 blocks.arithmetic.q_delta_range().emplace_back(0);
474 blocks.arithmetic.q_lookup_type().emplace_back(0);
475 blocks.arithmetic.q_elliptic().emplace_back(0);
476 blocks.arithmetic.q_memory().emplace_back(0);
477 blocks.arithmetic.q_nnf().emplace_back(0);
478 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
479 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
480 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
481 blocks.arithmetic.pad_additional();
482 }
483 check_selector_length_consistency();
484 ++this->num_gates;
485}
486
487// Creates a width-4 addition gate, where the fourth witness must be a boolean.
488// Can be used to normalize a 32-bit addition
489template <typename ExecutionTrace>
490void UltraCircuitBuilder_<ExecutionTrace>::create_balanced_add_gate(const add_quad_<FF>& in)
491{
492 this->assert_valid_variables({ in.a, in.b, in.c, in.d });
493
494 blocks.arithmetic.populate_wires(in.a, in.b, in.c, in.d);
495 blocks.arithmetic.q_m().emplace_back(0);
496 blocks.arithmetic.q_1().emplace_back(in.a_scaling);
497 blocks.arithmetic.q_2().emplace_back(in.b_scaling);
498 blocks.arithmetic.q_3().emplace_back(in.c_scaling);
499 blocks.arithmetic.q_c().emplace_back(in.const_scaling);
500 blocks.arithmetic.q_arith().emplace_back(1);
501 blocks.arithmetic.q_4().emplace_back(in.d_scaling);
502 blocks.arithmetic.q_delta_range().emplace_back(0);
503 blocks.arithmetic.q_lookup_type().emplace_back(0);
504 blocks.arithmetic.q_elliptic().emplace_back(0);
505 blocks.arithmetic.q_memory().emplace_back(0);
506 blocks.arithmetic.q_nnf().emplace_back(0);
507 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
508 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
509 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
510 blocks.arithmetic.pad_additional();
511 }
512 check_selector_length_consistency();
513 ++this->num_gates;
514
515 // Range constrain the 4-th wire to {0, 1}. Since the inputs being added never exceed (2^x - 1)
516 // during uintx arithmetic, we can safely use a 1-bit range check here. In other words, we do not
517 // allow lazy uintx addition.
518 create_new_range_constraint(in.d, 1);
519}
527template <typename ExecutionTrace> void UltraCircuitBuilder_<ExecutionTrace>::create_mul_gate(const mul_triple_<FF>& in)
528{
529 this->assert_valid_variables({ in.a, in.b, in.c });
530
531 blocks.arithmetic.populate_wires(in.a, in.b, in.c, this->zero_idx);
532 blocks.arithmetic.q_m().emplace_back(in.mul_scaling);
533 blocks.arithmetic.q_1().emplace_back(0);
534 blocks.arithmetic.q_2().emplace_back(0);
535 blocks.arithmetic.q_3().emplace_back(in.c_scaling);
536 blocks.arithmetic.q_c().emplace_back(in.const_scaling);
537 blocks.arithmetic.q_arith().emplace_back(1);
538 blocks.arithmetic.q_4().emplace_back(0);
539 blocks.arithmetic.q_delta_range().emplace_back(0);
540 blocks.arithmetic.q_lookup_type().emplace_back(0);
541 blocks.arithmetic.q_elliptic().emplace_back(0);
542 blocks.arithmetic.q_memory().emplace_back(0);
543 blocks.arithmetic.q_nnf().emplace_back(0);
544 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
545 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
546 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
547 blocks.arithmetic.pad_additional();
548 }
549 check_selector_length_consistency();
550 ++this->num_gates;
551}
557template <typename ExecutionTrace>
558void UltraCircuitBuilder_<ExecutionTrace>::create_bool_gate(const uint32_t variable_index)
559{
560 this->assert_valid_variables({ variable_index });
561
562 blocks.arithmetic.populate_wires(variable_index, variable_index, this->zero_idx, this->zero_idx);
563 blocks.arithmetic.q_m().emplace_back(1);
564 blocks.arithmetic.q_1().emplace_back(-1);
565 blocks.arithmetic.q_2().emplace_back(0);
566 blocks.arithmetic.q_3().emplace_back(0);
567 blocks.arithmetic.q_c().emplace_back(0);
568 blocks.arithmetic.q_delta_range().emplace_back(0);
569
570 blocks.arithmetic.q_arith().emplace_back(1);
571 blocks.arithmetic.q_4().emplace_back(0);
572 blocks.arithmetic.q_lookup_type().emplace_back(0);
573 blocks.arithmetic.q_elliptic().emplace_back(0);
574 blocks.arithmetic.q_memory().emplace_back(0);
575 blocks.arithmetic.q_nnf().emplace_back(0);
576 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
577 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
578 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
579 blocks.arithmetic.pad_additional();
580 }
581 check_selector_length_consistency();
582 ++this->num_gates;
583}
584
591template <typename ExecutionTrace>
592void UltraCircuitBuilder_<ExecutionTrace>::create_poly_gate(const poly_triple_<FF>& in)
593{
594 this->assert_valid_variables({ in.a, in.b, in.c });
595
596 blocks.arithmetic.populate_wires(in.a, in.b, in.c, this->zero_idx);
597 blocks.arithmetic.q_m().emplace_back(in.q_m);
598 blocks.arithmetic.q_1().emplace_back(in.q_l);
599 blocks.arithmetic.q_2().emplace_back(in.q_r);
600 blocks.arithmetic.q_3().emplace_back(in.q_o);
601 blocks.arithmetic.q_c().emplace_back(in.q_c);
602 blocks.arithmetic.q_delta_range().emplace_back(0);
603
604 blocks.arithmetic.q_arith().emplace_back(1);
605 blocks.arithmetic.q_4().emplace_back(0);
606 blocks.arithmetic.q_lookup_type().emplace_back(0);
607 blocks.arithmetic.q_elliptic().emplace_back(0);
608 blocks.arithmetic.q_memory().emplace_back(0);
609 blocks.arithmetic.q_nnf().emplace_back(0);
610 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
611 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
612 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
613 blocks.arithmetic.pad_additional();
614 }
615 check_selector_length_consistency();
616 ++this->num_gates;
617}
618
627template <typename ExecutionTrace>
628void UltraCircuitBuilder_<ExecutionTrace>::create_ecc_add_gate(const ecc_add_gate_<FF>& in)
629{
638 this->assert_valid_variables({ in.x1, in.x2, in.x3, in.y1, in.y2, in.y3 });
639
640 auto& block = blocks.elliptic;
641
642 bool previous_elliptic_gate_exists = block.size() > 0;
643 bool can_fuse_into_previous_gate = previous_elliptic_gate_exists;
644 // TODO(https://github.com/AztecProtocol/barretenberg/issues/1482): scrutinize and clean up this logic
645 if (can_fuse_into_previous_gate) {
646 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.w_r()[block.size() - 1] == in.x1);
647 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.w_o()[block.size() - 1] == in.y1);
648 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_3()[block.size() - 1] == 0);
649 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_4()[block.size() - 1] == 0);
650 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_1()[block.size() - 1] == 0);
651 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_arith()[block.size() - 1] == 0);
652 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_m()[block.size() - 1] == 0);
653 }
654
655 if (can_fuse_into_previous_gate) {
656 block.q_1().set(block.size() - 1, in.sign_coefficient);
657 block.q_elliptic().set(block.size() - 1, 1);
658 } else {
659 block.populate_wires(this->zero_idx, in.x1, in.y1, this->zero_idx);
660 block.q_3().emplace_back(0);
661 block.q_4().emplace_back(0);
662 block.q_1().emplace_back(in.sign_coefficient);
663
664 block.q_arith().emplace_back(0);
665 block.q_2().emplace_back(0);
666 block.q_m().emplace_back(0);
667 block.q_c().emplace_back(0);
668 block.q_delta_range().emplace_back(0);
669 block.q_lookup_type().emplace_back(0);
670 block.q_elliptic().emplace_back(1);
671 block.q_memory().emplace_back(0);
672 block.q_nnf().emplace_back(0);
673 block.q_poseidon2_external().emplace_back(0);
674 block.q_poseidon2_internal().emplace_back(0);
675 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
676 block.pad_additional();
677 }
678 check_selector_length_consistency();
679 ++this->num_gates;
680 }
681 create_dummy_gate(block, in.x2, in.x3, in.y3, in.y2);
682}
683
689template <typename ExecutionTrace>
690void UltraCircuitBuilder_<ExecutionTrace>::create_ecc_dbl_gate(const ecc_dbl_gate_<FF>& in)
691{
692 auto& block = blocks.elliptic;
693
702 this->assert_valid_variables({ in.x1, in.x3, in.y1, in.y3 });
703
704 bool previous_elliptic_gate_exists = block.size() > 0;
705 bool can_fuse_into_previous_gate = previous_elliptic_gate_exists;
706 // TODO(https://github.com/AztecProtocol/barretenberg/issues/1482): scrutinize and clean up this logic
707 if (can_fuse_into_previous_gate) {
708 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.w_r()[block.size() - 1] == in.x1);
709 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.w_o()[block.size() - 1] == in.y1);
710 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_arith()[block.size() - 1] == 0);
711 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_lookup_type()[block.size() - 1] == 0);
712 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_memory()[block.size() - 1] == 0);
713 can_fuse_into_previous_gate = can_fuse_into_previous_gate && (block.q_nnf()[block.size() - 1] == 0);
714 }
715
716 if (can_fuse_into_previous_gate) {
717 block.q_elliptic().set(block.size() - 1, 1);
718 block.q_m().set(block.size() - 1, 1);
719 } else {
720 block.populate_wires(this->zero_idx, in.x1, in.y1, this->zero_idx);
721 block.q_elliptic().emplace_back(1);
722 block.q_m().emplace_back(1);
723 block.q_1().emplace_back(0);
724 block.q_2().emplace_back(0);
725 block.q_3().emplace_back(0);
726 block.q_c().emplace_back(0);
727 block.q_arith().emplace_back(0);
728 block.q_4().emplace_back(0);
729 block.q_delta_range().emplace_back(0);
730 block.q_lookup_type().emplace_back(0);
731 block.q_memory().emplace_back(0);
732 block.q_nnf().emplace_back(0);
733 block.q_poseidon2_external().emplace_back(0);
734 block.q_poseidon2_internal().emplace_back(0);
735 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
736 block.pad_additional();
737 }
738 check_selector_length_consistency();
739 ++this->num_gates;
740 }
741 create_dummy_gate(block, this->zero_idx, in.x3, in.y3, this->zero_idx);
742}
743
750template <typename ExecutionTrace>
751void UltraCircuitBuilder_<ExecutionTrace>::fix_witness(const uint32_t witness_index, const FF& witness_value)
752{
753 this->assert_valid_variables({ witness_index });
754
755 blocks.arithmetic.populate_wires(witness_index, this->zero_idx, this->zero_idx, this->zero_idx);
756 blocks.arithmetic.q_m().emplace_back(0);
757 blocks.arithmetic.q_1().emplace_back(1);
758 blocks.arithmetic.q_2().emplace_back(0);
759 blocks.arithmetic.q_3().emplace_back(0);
760 blocks.arithmetic.q_c().emplace_back(-witness_value);
761 blocks.arithmetic.q_arith().emplace_back(1);
762 blocks.arithmetic.q_4().emplace_back(0);
763 blocks.arithmetic.q_delta_range().emplace_back(0);
764 blocks.arithmetic.q_lookup_type().emplace_back(0);
765 blocks.arithmetic.q_elliptic().emplace_back(0);
766 blocks.arithmetic.q_memory().emplace_back(0);
767 blocks.arithmetic.q_nnf().emplace_back(0);
768 blocks.arithmetic.q_poseidon2_external().emplace_back(0);
769 blocks.arithmetic.q_poseidon2_internal().emplace_back(0);
770 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
771 blocks.arithmetic.pad_additional();
772 }
773 check_selector_length_consistency();
774 ++this->num_gates;
775}
776
777template <typename ExecutionTrace>
778uint32_t UltraCircuitBuilder_<ExecutionTrace>::put_constant_variable(const FF& variable)
779{
780 if (constant_variable_indices.contains(variable)) {
781 return constant_variable_indices.at(variable);
782 } else {
783 uint32_t variable_index = this->add_variable(variable);
784 fix_witness(variable_index, variable);
785 constant_variable_indices.insert({ variable, variable_index });
786 return variable_index;
787 }
788}
789
798template <typename ExecutionTrace>
799plookup::BasicTable& UltraCircuitBuilder_<ExecutionTrace>::get_table(const plookup::BasicTableId id)
800{
801 for (plookup::BasicTable& table : lookup_tables) {
802 if (table.id == id) {
803 return table;
804 }
805 }
806 // Table doesn't exist! So try to create it.
807 lookup_tables.emplace_back(plookup::create_basic_table(id, lookup_tables.size()));
808 return lookup_tables.back();
809}
810
815template <typename ExecutionTrace>
816plookup::ReadData<uint32_t> UltraCircuitBuilder_<ExecutionTrace>::create_gates_from_plookup_accumulators(
817 const plookup::MultiTableId& id,
818 const plookup::ReadData<FF>& read_values,
819 const uint32_t key_a_index,
820 std::optional<uint32_t> key_b_index)
821{
822 const auto& multi_table = plookup::get_multitable(id);
823 const size_t num_lookups = read_values[plookup::ColumnIdx::C1].size();
824 plookup::ReadData<uint32_t> read_data;
825 for (size_t i = 0; i < num_lookups; ++i) {
826 // get basic lookup table; construct and add to builder.lookup_tables if not already present
827 auto& table = get_table(multi_table.basic_table_ids[i]);
828
829 table.lookup_gates.emplace_back(read_values.lookup_entries[i]); // used for constructing sorted polynomials
830
831 const auto first_idx = (i == 0) ? key_a_index : this->add_variable(read_values[plookup::ColumnIdx::C1][i]);
832 const auto second_idx = (i == 0 && (key_b_index.has_value()))
833 ? key_b_index.value()
834 : this->add_variable(read_values[plookup::ColumnIdx::C2][i]);
835 const auto third_idx = this->add_variable(read_values[plookup::ColumnIdx::C3][i]);
836
837 read_data[plookup::ColumnIdx::C1].push_back(first_idx);
838 read_data[plookup::ColumnIdx::C2].push_back(second_idx);
839 read_data[plookup::ColumnIdx::C3].push_back(third_idx);
840 this->assert_valid_variables({ first_idx, second_idx, third_idx });
841
842 blocks.lookup.q_lookup_type().emplace_back(FF(1));
843 blocks.lookup.q_3().emplace_back(FF(table.table_index));
844 blocks.lookup.populate_wires(first_idx, second_idx, third_idx, this->zero_idx);
845 blocks.lookup.q_1().emplace_back(0);
846 blocks.lookup.q_2().emplace_back((i == (num_lookups - 1) ? 0 : -multi_table.column_1_step_sizes[i + 1]));
847 blocks.lookup.q_m().emplace_back((i == (num_lookups - 1) ? 0 : -multi_table.column_2_step_sizes[i + 1]));
848 blocks.lookup.q_c().emplace_back((i == (num_lookups - 1) ? 0 : -multi_table.column_3_step_sizes[i + 1]));
849 blocks.lookup.q_arith().emplace_back(0);
850 blocks.lookup.q_4().emplace_back(0);
851 blocks.lookup.q_delta_range().emplace_back(0);
852 blocks.lookup.q_elliptic().emplace_back(0);
853 blocks.lookup.q_memory().emplace_back(0);
854 blocks.lookup.q_nnf().emplace_back(0);
855 blocks.lookup.q_poseidon2_external().emplace_back(0);
856 blocks.lookup.q_poseidon2_internal().emplace_back(0);
857 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
858 blocks.lookup.pad_additional();
859 }
860 check_selector_length_consistency();
861 ++this->num_gates;
862 }
863 return read_data;
864}
865
869template <typename ExecutionTrace>
870typename UltraCircuitBuilder_<ExecutionTrace>::RangeList UltraCircuitBuilder_<ExecutionTrace>::create_range_list(
871 const uint64_t target_range)
872{
873 RangeList result;
874 const auto range_tag = get_new_tag(); // current_tag + 1;
875 const auto tau_tag = get_new_tag(); // current_tag + 2;
876 create_tag(range_tag, tau_tag);
877 create_tag(tau_tag, range_tag);
878 result.target_range = target_range;
879 result.range_tag = range_tag;
880 result.tau_tag = tau_tag;
881
882 uint64_t num_multiples_of_three = (target_range / DEFAULT_PLOOKUP_RANGE_STEP_SIZE);
883
884 result.variable_indices.reserve((uint32_t)num_multiples_of_three);
885 for (uint64_t i = 0; i <= num_multiples_of_three; ++i) {
886 const uint32_t index = this->add_variable(i * DEFAULT_PLOOKUP_RANGE_STEP_SIZE);
887 result.variable_indices.emplace_back(index);
888 assign_tag(index, result.range_tag);
889 }
890 {
891 const uint32_t index = this->add_variable(target_range);
892 result.variable_indices.emplace_back(index);
893 assign_tag(index, result.range_tag);
894 }
895 // Need this because these variables will not appear in the witness otherwise
896 create_dummy_constraints(result.variable_indices);
897
898 return result;
899}
900
901// range constraint a value by decomposing it into limbs whose size should be the default range constraint size
902
903template <typename ExecutionTrace>
904std::vector<uint32_t> UltraCircuitBuilder_<ExecutionTrace>::decompose_into_default_range(
905 const uint32_t variable_index, const uint64_t num_bits, const uint64_t target_range_bitnum, std::string const& msg)
906{
907 this->assert_valid_variables({ variable_index });
908
909 BB_ASSERT_GT(num_bits, 0U);
910
911 uint256_t val = (uint256_t)(this->get_variable(variable_index));
912
913 // If the value is out of range, set the CircuitBuilder error to the given msg.
914 if (val.get_msb() >= num_bits && !this->failed()) {
915 this->failure(msg);
916 }
917
918 const uint64_t sublimb_mask = (1ULL << target_range_bitnum) - 1;
919
933 std::vector<uint64_t> sublimbs;
934 std::vector<uint32_t> sublimb_indices;
935
936 const bool has_remainder_bits = (num_bits % target_range_bitnum != 0);
937 const uint64_t num_limbs = (num_bits / target_range_bitnum) + has_remainder_bits;
938 const uint64_t last_limb_size = num_bits - ((num_bits / target_range_bitnum) * target_range_bitnum);
939 const uint64_t last_limb_range = ((uint64_t)1 << last_limb_size) - 1;
940
941 uint256_t accumulator = val;
942 for (size_t i = 0; i < num_limbs; ++i) {
943 sublimbs.push_back(accumulator.data[0] & sublimb_mask);
944 accumulator = accumulator >> target_range_bitnum;
945 }
946 for (size_t i = 0; i < sublimbs.size(); ++i) {
947 const auto limb_idx = this->add_variable(sublimbs[i]);
948 sublimb_indices.emplace_back(limb_idx);
949 if ((i == sublimbs.size() - 1) && has_remainder_bits) {
950 create_new_range_constraint(limb_idx, last_limb_range);
951 } else {
952 create_new_range_constraint(limb_idx, sublimb_mask);
953 }
954 }
955
956 const uint64_t num_limb_triples = (num_limbs / 3) + ((num_limbs % 3) != 0);
957 const uint64_t leftovers = (num_limbs % 3) == 0 ? 3 : (num_limbs % 3);
958
959 accumulator = val;
960 uint32_t accumulator_idx = variable_index;
961
962 for (size_t i = 0; i < num_limb_triples; ++i) {
963 const bool real_limbs[3]{
964 (i == (num_limb_triples - 1) && (leftovers < 1)) ? false : true,
965 (i == (num_limb_triples - 1) && (leftovers < 2)) ? false : true,
966 (i == (num_limb_triples - 1) && (leftovers < 3)) ? false : true,
967 };
968
969 const uint64_t round_sublimbs[3]{
970 real_limbs[0] ? sublimbs[3 * i] : 0,
971 real_limbs[1] ? sublimbs[3 * i + 1] : 0,
972 real_limbs[2] ? sublimbs[3 * i + 2] : 0,
973 };
974 const uint32_t new_limbs[3]{
975 real_limbs[0] ? sublimb_indices[3 * i] : this->zero_idx,
976 real_limbs[1] ? sublimb_indices[3 * i + 1] : this->zero_idx,
977 real_limbs[2] ? sublimb_indices[3 * i + 2] : this->zero_idx,
978 };
979 const uint64_t shifts[3]{
980 target_range_bitnum * (3 * i),
981 target_range_bitnum * (3 * i + 1),
982 target_range_bitnum * (3 * i + 2),
983 };
984 uint256_t new_accumulator = accumulator - (uint256_t(round_sublimbs[0]) << shifts[0]) -
985 (uint256_t(round_sublimbs[1]) << shifts[1]) -
986 (uint256_t(round_sublimbs[2]) << shifts[2]);
987
988 create_big_add_gate(
989 {
990 new_limbs[0],
991 new_limbs[1],
992 new_limbs[2],
993 accumulator_idx,
994 uint256_t(1) << shifts[0],
995 uint256_t(1) << shifts[1],
996 uint256_t(1) << shifts[2],
997 -1,
998 0,
999 },
1000 ((i == num_limb_triples - 1) ? false : true));
1001 // TODO(https://github.com/AztecProtocol/barretenberg/issues/1450): this is probably creating an unused
1002 // wire/variable in the circuit, in the last iteration of the loop.
1003 accumulator_idx = this->add_variable(new_accumulator);
1004 accumulator = new_accumulator;
1005 }
1006 return sublimb_indices;
1007}
1008
1018template <typename ExecutionTrace>
1019void UltraCircuitBuilder_<ExecutionTrace>::create_new_range_constraint(const uint32_t variable_index,
1020 const uint64_t target_range,
1021 std::string const msg)
1022{
1023 if (uint256_t(this->get_variable(variable_index)).data[0] > target_range) {
1024 if (!this->failed()) {
1025 this->failure(msg);
1026 }
1027 }
1028 if (range_lists.count(target_range) == 0) {
1029 range_lists.insert({ target_range, create_range_list(target_range) });
1030 }
1031
1032 const auto existing_tag = this->real_variable_tags[this->real_variable_index[variable_index]];
1033 auto& list = range_lists[target_range];
1034
1035 // If the variable's tag matches the target range list's tag, do nothing.
1036 if (existing_tag != list.range_tag) {
1037 // If the variable is 'untagged' (i.e., it has the dummy tag), assign it the appropriate tag.
1038 // Otherwise, find the range for which the variable has already been tagged.
1039 if (existing_tag != DUMMY_TAG) {
1040 bool found_tag = false;
1041 for (const auto& r : range_lists) {
1042 if (r.second.range_tag == existing_tag) {
1043 found_tag = true;
1044 if (r.first < target_range) {
1045 // The variable already has a more restrictive range check, so do nothing.
1046 return;
1047 } else {
1048 // The range constraint we are trying to impose is more restrictive than the existing range
1049 // constraint. It would be difficult to remove an existing range check. Instead deep-copy the
1050 // variable and apply a range check to new variable
1051 const uint32_t copied_witness = this->add_variable(this->get_variable(variable_index));
1052 create_add_gate({ .a = variable_index,
1053 .b = copied_witness,
1054 .c = this->zero_idx,
1055 .a_scaling = 1,
1056 .b_scaling = -1,
1057 .c_scaling = 0,
1058 .const_scaling = 0 });
1059 // Recurse with new witness that has no tag attached.
1060 create_new_range_constraint(copied_witness, target_range, msg);
1061 return;
1062 }
1063 }
1064 }
1065 ASSERT(found_tag);
1066 }
1067 assign_tag(variable_index, list.range_tag);
1068 list.variable_indices.emplace_back(variable_index);
1069 }
1070}
1071
1072template <typename ExecutionTrace> void UltraCircuitBuilder_<ExecutionTrace>::process_range_list(RangeList& list)
1073{
1074 this->assert_valid_variables(list.variable_indices);
1075
1076 BB_ASSERT_GT(list.variable_indices.size(), 0U);
1077
1078 // replace witness index in variable_indices with the real variable index i.e. if a copy constraint has been
1079 // applied on a variable after it was range constrained, this makes sure the indices in list point to the updated
1080 // index in the range list so the set equivalence does not fail
1081 for (uint32_t& x : list.variable_indices) {
1082 x = this->real_variable_index[x];
1083 }
1084 // remove duplicate witness indices to prevent the sorted list set size being wrong!
1085 std::sort(list.variable_indices.begin(), list.variable_indices.end());
1086 auto back_iterator = std::unique(list.variable_indices.begin(), list.variable_indices.end());
1087 list.variable_indices.erase(back_iterator, list.variable_indices.end());
1088
1089 // go over variables
1090 // iterate over each variable and create mirror variable with same value - with tau tag
1091 // need to make sure that, in original list, increments of at most 3
1092 std::vector<uint32_t> sorted_list;
1093 sorted_list.reserve(list.variable_indices.size());
1094 for (const auto variable_index : list.variable_indices) {
1095 const auto& field_element = this->get_variable(variable_index);
1096 const uint32_t shrinked_value = (uint32_t)field_element.from_montgomery_form().data[0];
1097 sorted_list.emplace_back(shrinked_value);
1098 }
1099
1100#ifdef NO_PAR_ALGOS
1101 std::sort(sorted_list.begin(), sorted_list.end());
1102#else
1103 std::sort(std::execution::par_unseq, sorted_list.begin(), sorted_list.end());
1104#endif
1105 // list must be padded to a multipe of 4 and larger than 4 (gate_width)
1106 constexpr size_t gate_width = NUM_WIRES;
1107 size_t padding = (gate_width - (list.variable_indices.size() % gate_width)) % gate_width;
1108
1109 std::vector<uint32_t> indices;
1110 indices.reserve(padding + sorted_list.size());
1111
1112 if (list.variable_indices.size() <= gate_width) {
1113 padding += gate_width;
1114 }
1115 for (size_t i = 0; i < padding; ++i) {
1116 indices.emplace_back(this->zero_idx);
1117 }
1118 for (const auto sorted_value : sorted_list) {
1119 const uint32_t index = this->add_variable(sorted_value);
1120 assign_tag(index, list.tau_tag);
1121 indices.emplace_back(index);
1122 }
1123 create_sort_constraint_with_edges(indices, 0, list.target_range);
1124}
1125
1126template <typename ExecutionTrace> void UltraCircuitBuilder_<ExecutionTrace>::process_range_lists()
1127{
1128 for (auto& i : range_lists) {
1129 process_range_list(i.second);
1130 }
1131}
1132
1133/*
1134 Create range constraint:
1135 * add variable index to a list of range constrained variables
1136 * data structures: vector of lists, each list contains:
1137 * - the range size
1138 * - the list of variables in the range
1139 * - a generalized permutation tag
1140 *
1141 * create range constraint parameters: variable index && range size
1142 *
1143 * std::map<uint64_t, RangeList> range_lists;
1144*/
1145// Check for a sequence of variables that neighboring differences are at most 3 (used for batched range checkj)
1146template <typename ExecutionTrace>
1147void UltraCircuitBuilder_<ExecutionTrace>::create_sort_constraint(const std::vector<uint32_t>& variable_index)
1148{
1149 constexpr size_t gate_width = NUM_WIRES;
1150 BB_ASSERT_EQ(variable_index.size() % gate_width, 0U);
1151 this->assert_valid_variables(variable_index);
1152
1153 for (size_t i = 0; i < variable_index.size(); i += gate_width) {
1154 blocks.delta_range.populate_wires(
1155 variable_index[i], variable_index[i + 1], variable_index[i + 2], variable_index[i + 3]);
1156
1157 ++this->num_gates;
1158 blocks.delta_range.q_m().emplace_back(0);
1159 blocks.delta_range.q_1().emplace_back(0);
1160 blocks.delta_range.q_2().emplace_back(0);
1161 blocks.delta_range.q_3().emplace_back(0);
1162 blocks.delta_range.q_c().emplace_back(0);
1163 blocks.delta_range.q_arith().emplace_back(0);
1164 blocks.delta_range.q_4().emplace_back(0);
1165 blocks.delta_range.q_delta_range().emplace_back(1);
1166 blocks.delta_range.q_elliptic().emplace_back(0);
1167 blocks.delta_range.q_lookup_type().emplace_back(0);
1168 blocks.delta_range.q_memory().emplace_back(0);
1169 blocks.delta_range.q_nnf().emplace_back(0);
1170 blocks.delta_range.q_poseidon2_external().emplace_back(0);
1171 blocks.delta_range.q_poseidon2_internal().emplace_back(0);
1172 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1173 blocks.delta_range.pad_additional();
1174 }
1175 check_selector_length_consistency();
1176 }
1177 // dummy gate needed because of sort widget's check of next row
1178 create_dummy_gate(
1179 blocks.delta_range, variable_index[variable_index.size() - 1], this->zero_idx, this->zero_idx, this->zero_idx);
1180}
1181
1182// useful to put variables in the witness that aren't already used - e.g. the dummy variables of the range constraint in
1183// multiples of three
1184template <typename ExecutionTrace>
1185void UltraCircuitBuilder_<ExecutionTrace>::create_dummy_constraints(const std::vector<uint32_t>& variable_index)
1186{
1187 std::vector<uint32_t> padded_list = variable_index;
1188 constexpr size_t gate_width = NUM_WIRES;
1189 const uint64_t padding = (gate_width - (padded_list.size() % gate_width)) % gate_width;
1190 for (uint64_t i = 0; i < padding; ++i) {
1191 padded_list.emplace_back(this->zero_idx);
1192 }
1193 this->assert_valid_variables(variable_index);
1194 this->assert_valid_variables(padded_list);
1195
1196 for (size_t i = 0; i < padded_list.size(); i += gate_width) {
1197 create_dummy_gate(
1198 blocks.arithmetic, padded_list[i], padded_list[i + 1], padded_list[i + 2], padded_list[i + 3]);
1199 }
1200}
1201
1202// Check for a sequence of variables that neighboring differences are at most 3 (used for batched range checks)
1203template <typename ExecutionTrace>
1204void UltraCircuitBuilder_<ExecutionTrace>::create_sort_constraint_with_edges(
1205 const std::vector<uint32_t>& variable_index, const FF& start, const FF& end)
1206{
1207 // Convenient to assume size is at least 8 (gate_width = 4) for separate gates for start and end conditions
1208 constexpr size_t gate_width = NUM_WIRES;
1209 BB_ASSERT_EQ(variable_index.size() % gate_width, 0U);
1210 BB_ASSERT_GT(variable_index.size(), gate_width);
1211 this->assert_valid_variables(variable_index);
1212
1213 auto& block = blocks.delta_range;
1214
1215 // Add an arithmetic gate to ensure the first input is equal to the start value of the range being checked
1216 create_add_gate({ variable_index[0], this->zero_idx, this->zero_idx, 1, 0, 0, -start });
1217
1218 // enforce range check for all but the final row
1219 for (size_t i = 0; i < variable_index.size() - gate_width; i += gate_width) {
1220
1221 block.populate_wires(variable_index[i], variable_index[i + 1], variable_index[i + 2], variable_index[i + 3]);
1222 ++this->num_gates;
1223 block.q_m().emplace_back(0);
1224 block.q_1().emplace_back(0);
1225 block.q_2().emplace_back(0);
1226 block.q_3().emplace_back(0);
1227 block.q_c().emplace_back(0);
1228 block.q_arith().emplace_back(0);
1229 block.q_4().emplace_back(0);
1230 block.q_delta_range().emplace_back(1);
1231 block.q_elliptic().emplace_back(0);
1232 block.q_lookup_type().emplace_back(0);
1233 block.q_memory().emplace_back(0);
1234 block.q_nnf().emplace_back(0);
1235 block.q_poseidon2_external().emplace_back(0);
1236 block.q_poseidon2_internal().emplace_back(0);
1237 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1238 block.pad_additional();
1239 }
1240 check_selector_length_consistency();
1241 }
1242 // enforce range checks of last row and ending at end
1243 if (variable_index.size() > gate_width) {
1244 block.populate_wires(variable_index[variable_index.size() - 4],
1245 variable_index[variable_index.size() - 3],
1246 variable_index[variable_index.size() - 2],
1247 variable_index[variable_index.size() - 1]);
1248 ++this->num_gates;
1249 block.q_m().emplace_back(0);
1250 block.q_1().emplace_back(0);
1251 block.q_2().emplace_back(0);
1252 block.q_3().emplace_back(0);
1253 block.q_c().emplace_back(0);
1254 block.q_arith().emplace_back(0);
1255 block.q_4().emplace_back(0);
1256 block.q_delta_range().emplace_back(1);
1257 block.q_elliptic().emplace_back(0);
1258 block.q_lookup_type().emplace_back(0);
1259 block.q_memory().emplace_back(0);
1260 block.q_nnf().emplace_back(0);
1261 block.q_poseidon2_external().emplace_back(0);
1262 block.q_poseidon2_internal().emplace_back(0);
1263 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1264 block.pad_additional();
1265 }
1266 check_selector_length_consistency();
1267 }
1268
1269 // NOTE(https://github.com/AztecProtocol/barretenberg/issues/879): Optimisation opportunity to use a single gate
1270 // (and remove dummy gate). This used to be a single gate before trace sorting based on gate types. The dummy gate
1271 // has been added to allow the previous gate to access the required wire data via shifts, allowing the arithmetic
1272 // gate to occur out of sequence. More details on the linked Github issue.
1273 create_dummy_gate(block, variable_index[variable_index.size() - 1], this->zero_idx, this->zero_idx, this->zero_idx);
1274 create_add_gate({ variable_index[variable_index.size() - 1], this->zero_idx, this->zero_idx, 1, 0, 0, -end });
1275}
1276
1277// range constraint a value by decomposing it into limbs whose size should be the default range constraint size
1278
1279template <typename ExecutionTrace>
1280std::vector<uint32_t> UltraCircuitBuilder_<ExecutionTrace>::decompose_into_default_range_better_for_oddlimbnum(
1281 const uint32_t variable_index, const size_t num_bits, std::string const& msg)
1282{
1283 std::vector<uint32_t> sums;
1284 const size_t limb_num = (size_t)num_bits / DEFAULT_PLOOKUP_RANGE_BITNUM;
1285 const size_t last_limb_size = num_bits - (limb_num * DEFAULT_PLOOKUP_RANGE_BITNUM);
1286 if (limb_num < 3) {
1287 std::cerr
1288 << "number of bits in range must be an integer multipe of DEFAULT_PLOOKUP_RANGE_BITNUM of size at least 3"
1289 << std::endl;
1290 return sums;
1291 }
1292
1293 const uint256_t val = (uint256_t)(this->get_variable(variable_index));
1294 // check witness value is indeed in range (commented out cause interferes with negative tests)
1295 // ASSERT(val < ((uint256_t)1 << num_bits) - 1); // Q:ask Zac what happens with wrapping when converting scalar
1296 // field to uint256 ASSERT(limb_num % 3 == 0); // TODO: write version of method that doesn't need this
1297 std::vector<uint32_t> val_limbs;
1298 std::vector<fr> val_slices;
1299 for (size_t i = 0; i < limb_num; i++) {
1300 val_slices.emplace_back(
1301 FF(val.slice(DEFAULT_PLOOKUP_RANGE_BITNUM * i, DEFAULT_PLOOKUP_RANGE_BITNUM * (i + 1) - 1)));
1302 val_limbs.emplace_back(this->add_variable(val_slices[i]));
1303 create_new_range_constraint(val_limbs[i], DEFAULT_PLOOKUP_RANGE_SIZE);
1304 }
1305
1306 uint64_t last_limb_range = ((uint64_t)1 << last_limb_size) - 1;
1307 FF last_slice(0);
1308 uint32_t last_limb(this->zero_idx);
1309 size_t total_limb_num = limb_num;
1310 if (last_limb_size > 0) {
1311 val_slices.emplace_back(FF(val.slice(num_bits - last_limb_size, num_bits)));
1312 val_limbs.emplace_back(this->add_variable(last_slice));
1313 create_new_range_constraint(last_limb, last_limb_range);
1314 total_limb_num++;
1315 }
1316 // pad slices and limbs in case they are not 2 mod 3
1317 if (total_limb_num % 3 == 1) {
1318 val_limbs.emplace_back(this->zero_idx); // TODO: check this is zero
1319 val_slices.emplace_back(0);
1320 total_limb_num++;
1321 }
1322 FF shift = FF(1 << DEFAULT_PLOOKUP_RANGE_BITNUM);
1323 FF second_shift = shift * shift;
1324 sums.emplace_back(this->add_variable(val_slices[0] + shift * val_slices[1] + second_shift * val_slices[2]));
1325 create_big_add_gate({ val_limbs[0], val_limbs[1], val_limbs[2], sums[0], 1, shift, second_shift, -1, 0 });
1326 FF cur_shift = (shift * second_shift);
1327 FF cur_second_shift = cur_shift * shift;
1328 for (size_t i = 3; i < total_limb_num; i = i + 2) {
1329 sums.emplace_back(this->add_variable(this->get_variable(sums[sums.size() - 1]) + cur_shift * val_slices[i] +
1330 cur_second_shift * val_slices[i + 1]));
1331 create_big_add_gate({ sums[sums.size() - 2],
1332 val_limbs[i],
1333 val_limbs[i + 1],
1334 sums[sums.size() - 1],
1335 1,
1336 cur_shift,
1337 cur_second_shift,
1338 -1,
1339 0 });
1340 cur_shift *= second_shift;
1341 cur_second_shift *= second_shift;
1342 }
1343 this->assert_equal(sums[sums.size() - 1], variable_index, msg);
1344 return sums;
1345}
1346
1369template <typename ExecutionTrace>
1370void UltraCircuitBuilder_<ExecutionTrace>::apply_memory_selectors(const MEMORY_SELECTORS type)
1371{
1372 auto& block = blocks.memory;
1373 block.q_memory().emplace_back(type == MEMORY_SELECTORS::MEM_NONE ? 0 : 1);
1374 // Set to zero the selectors that are not enabled for this gate
1375 block.q_arith().emplace_back(0);
1376 block.q_delta_range().emplace_back(0);
1377 block.q_lookup_type().emplace_back(0);
1378 block.q_elliptic().emplace_back(0);
1379 block.q_nnf().emplace_back(0);
1380 block.q_poseidon2_external().emplace_back(0);
1381 block.q_poseidon2_internal().emplace_back(0);
1382 switch (type) {
1383 case MEMORY_SELECTORS::ROM_CONSISTENCY_CHECK: {
1384 // Memory read gate used with the sorted list of memory reads.
1385 // Apply sorted memory read checks with the following additional check:
1386 // 1. Assert that if index field across two gates does not change, the value field does not change.
1387 // Used for ROM reads and RAM reads across write/read boundaries
1388 block.q_1().emplace_back(1);
1389 block.q_2().emplace_back(1);
1390 block.q_3().emplace_back(0);
1391 block.q_4().emplace_back(0);
1392 block.q_m().emplace_back(0);
1393 block.q_c().emplace_back(0);
1394 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1395 block.pad_additional();
1396 }
1397 check_selector_length_consistency();
1398 break;
1399 }
1400 case MEMORY_SELECTORS::RAM_CONSISTENCY_CHECK: {
1401 // Memory read gate used with the sorted list of memory reads.
1402 // 1. Validate adjacent index values across 2 gates increases by 0 or 1
1403 // 2. Validate record computation (r = read_write_flag + index * \eta + \timestamp * \eta^2 + value * \eta^3)
1404 // 3. If adjacent index values across 2 gates does not change, and the next gate's read_write_flag is set to
1405 // 'read', validate adjacent values do not change Used for ROM reads and RAM reads across read/write boundaries
1406 block.q_1().emplace_back(0);
1407 block.q_2().emplace_back(0);
1408 block.q_3().emplace_back(1);
1409 block.q_4().emplace_back(0);
1410 block.q_m().emplace_back(0);
1411 block.q_c().emplace_back(0);
1412 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1413 block.pad_additional();
1414 }
1415 check_selector_length_consistency();
1416 break;
1417 }
1418 case MEMORY_SELECTORS::RAM_TIMESTAMP_CHECK: {
1419 // For two adjacent RAM entries that share the same index, validate the timestamp value is monotonically
1420 // increasing
1421 block.q_1().emplace_back(1);
1422 block.q_2().emplace_back(0);
1423 block.q_3().emplace_back(0);
1424 block.q_4().emplace_back(1);
1425 block.q_m().emplace_back(0);
1426 block.q_c().emplace_back(0);
1427 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1428 block.pad_additional();
1429 }
1430 check_selector_length_consistency();
1431 break;
1432 }
1433 case MEMORY_SELECTORS::ROM_READ: {
1434 // Memory read gate for reading memory cells.
1435 // Validates record witness computation (r = read_write_flag + index * \eta + timestamp * \eta^2 + value *
1436 // \eta^3)
1437 block.q_1().emplace_back(1);
1438 block.q_2().emplace_back(0);
1439 block.q_3().emplace_back(0);
1440 block.q_4().emplace_back(0);
1441 block.q_m().emplace_back(1); // validate record witness is correctly computed
1442 block.q_c().emplace_back(0); // read/write flag stored in q_c
1443 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1444 block.pad_additional();
1445 }
1446 check_selector_length_consistency();
1447 break;
1448 }
1449 case MEMORY_SELECTORS::RAM_READ: {
1450 // Memory read gate for reading memory cells.
1451 // Validates record witness computation (r = read_write_flag + index * \eta + timestamp * \eta^2 + value *
1452 // \eta^3)
1453 block.q_1().emplace_back(1);
1454 block.q_2().emplace_back(0);
1455 block.q_3().emplace_back(0);
1456 block.q_4().emplace_back(0);
1457 block.q_m().emplace_back(1); // validate record witness is correctly computed
1458 block.q_c().emplace_back(0); // read/write flag stored in q_c
1459 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1460 block.pad_additional();
1461 }
1462 check_selector_length_consistency();
1463 break;
1464 }
1465 case MEMORY_SELECTORS::RAM_WRITE: {
1466 // Memory read gate for writing memory cells.
1467 // Validates record witness computation (r = read_write_flag + index * \eta + timestamp * \eta^2 + value *
1468 // \eta^3)
1469 block.q_1().emplace_back(1);
1470 block.q_2().emplace_back(0);
1471 block.q_3().emplace_back(0);
1472 block.q_4().emplace_back(0);
1473 block.q_m().emplace_back(1); // validate record witness is correctly computed
1474 block.q_c().emplace_back(1); // read/write flag stored in q_c
1475 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1476 block.pad_additional();
1477 }
1478 check_selector_length_consistency();
1479 break;
1480 }
1481 default: {
1482 block.q_1().emplace_back(0);
1483 block.q_2().emplace_back(0);
1484 block.q_3().emplace_back(0);
1485 block.q_4().emplace_back(0);
1486 block.q_m().emplace_back(0);
1487 block.q_c().emplace_back(0);
1488 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1489 block.pad_additional();
1490 }
1491 check_selector_length_consistency();
1492 break;
1493 }
1494 }
1495}
1496
1520template <typename ExecutionTrace>
1521void UltraCircuitBuilder_<ExecutionTrace>::apply_nnf_selectors(const NNF_SELECTORS type)
1522{
1523 auto& block = blocks.nnf;
1524 block.q_nnf().emplace_back(type == NNF_SELECTORS::NNF_NONE ? 0 : 1);
1525 // Set to zero the selectors that are not enabled for this gate
1526 block.q_arith().emplace_back(0);
1527 block.q_delta_range().emplace_back(0);
1528 block.q_lookup_type().emplace_back(0);
1529 block.q_elliptic().emplace_back(0);
1530 block.q_memory().emplace_back(0);
1531 block.q_poseidon2_external().emplace_back(0);
1532 block.q_poseidon2_internal().emplace_back(0);
1533 switch (type) {
1534 case NNF_SELECTORS::LIMB_ACCUMULATE_1: {
1535 block.q_1().emplace_back(0);
1536 block.q_2().emplace_back(0);
1537 block.q_3().emplace_back(1);
1538 block.q_4().emplace_back(1);
1539 block.q_m().emplace_back(0);
1540 block.q_c().emplace_back(0);
1541 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1542 block.pad_additional();
1543 }
1544 check_selector_length_consistency();
1545 break;
1546 }
1547 case NNF_SELECTORS::LIMB_ACCUMULATE_2: {
1548 block.q_1().emplace_back(0);
1549 block.q_2().emplace_back(0);
1550 block.q_3().emplace_back(1);
1551 block.q_4().emplace_back(0);
1552 block.q_m().emplace_back(1);
1553 block.q_c().emplace_back(0);
1554 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1555 block.pad_additional();
1556 }
1557 check_selector_length_consistency();
1558 break;
1559 }
1560 case NNF_SELECTORS::NON_NATIVE_FIELD_1: {
1561 block.q_1().emplace_back(0);
1562 block.q_2().emplace_back(1);
1563 block.q_3().emplace_back(1);
1564 block.q_4().emplace_back(0);
1565 block.q_m().emplace_back(0);
1566 block.q_c().emplace_back(0);
1567 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1568 block.pad_additional();
1569 }
1570 check_selector_length_consistency();
1571 break;
1572 }
1573 case NNF_SELECTORS::NON_NATIVE_FIELD_2: {
1574 block.q_1().emplace_back(0);
1575 block.q_2().emplace_back(1);
1576 block.q_3().emplace_back(0);
1577 block.q_4().emplace_back(1);
1578 block.q_m().emplace_back(0);
1579 block.q_c().emplace_back(0);
1580 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1581 block.pad_additional();
1582 }
1583 check_selector_length_consistency();
1584 break;
1585 }
1586 case NNF_SELECTORS::NON_NATIVE_FIELD_3: {
1587 block.q_1().emplace_back(0);
1588 block.q_2().emplace_back(1);
1589 block.q_3().emplace_back(0);
1590 block.q_4().emplace_back(0);
1591 block.q_m().emplace_back(1);
1592 block.q_c().emplace_back(0);
1593 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1594 block.pad_additional();
1595 }
1596 check_selector_length_consistency();
1597 break;
1598 }
1599 default: {
1600 block.q_1().emplace_back(0);
1601 block.q_2().emplace_back(0);
1602 block.q_3().emplace_back(0);
1603 block.q_4().emplace_back(0);
1604 block.q_m().emplace_back(0);
1605 block.q_c().emplace_back(0);
1606 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
1607 block.pad_additional();
1608 }
1609 check_selector_length_consistency();
1610 break;
1611 }
1612 }
1613}
1614
1625template <typename ExecutionTrace>
1626void UltraCircuitBuilder_<ExecutionTrace>::range_constrain_two_limbs(const uint32_t lo_idx,
1627 const uint32_t hi_idx,
1628 const size_t lo_limb_bits,
1629 const size_t hi_limb_bits)
1630{
1631 // Validate limbs are <= 70 bits. If limbs are larger we require more witnesses and cannot use our limb accumulation
1632 // custom gate
1633 BB_ASSERT_LTE(lo_limb_bits, 14U * 5U);
1634 BB_ASSERT_LTE(hi_limb_bits, 14U * 5U);
1635
1636 // Sometimes we try to use limbs that are too large. It's easier to catch this issue here
1637 const auto get_sublimbs = [&](const uint32_t& limb_idx, const std::array<uint64_t, 5>& sublimb_masks) {
1638 const uint256_t limb = this->get_variable(limb_idx);
1639 // we can use constant 2^14 - 1 mask here. If the sublimb value exceeds the expected value then witness will
1640 // fail the range check below
1641 // We also use zero_idx to substitute variables that should be zero
1642 constexpr uint256_t MAX_SUBLIMB_MASK = (uint256_t(1) << 14) - 1;
1643 std::array<uint32_t, 5> sublimb_indices;
1644 sublimb_indices[0] = sublimb_masks[0] != 0 ? this->add_variable(limb & MAX_SUBLIMB_MASK) : this->zero_idx;
1645 sublimb_indices[1] =
1646 sublimb_masks[1] != 0 ? this->add_variable((limb >> 14) & MAX_SUBLIMB_MASK) : this->zero_idx;
1647 sublimb_indices[2] =
1648 sublimb_masks[2] != 0 ? this->add_variable((limb >> 28) & MAX_SUBLIMB_MASK) : this->zero_idx;
1649 sublimb_indices[3] =
1650 sublimb_masks[3] != 0 ? this->add_variable((limb >> 42) & MAX_SUBLIMB_MASK) : this->zero_idx;
1651 sublimb_indices[4] =
1652 sublimb_masks[4] != 0 ? this->add_variable((limb >> 56) & MAX_SUBLIMB_MASK) : this->zero_idx;
1653 return sublimb_indices;
1654 };
1655
1656 const auto get_limb_masks = [](size_t limb_bits) {
1657 std::array<uint64_t, 5> sublimb_masks;
1658 sublimb_masks[0] = limb_bits >= 14 ? 14 : limb_bits;
1659 sublimb_masks[1] = limb_bits >= 28 ? 14 : (limb_bits > 14 ? limb_bits - 14 : 0);
1660 sublimb_masks[2] = limb_bits >= 42 ? 14 : (limb_bits > 28 ? limb_bits - 28 : 0);
1661 sublimb_masks[3] = limb_bits >= 56 ? 14 : (limb_bits > 42 ? limb_bits - 42 : 0);
1662 sublimb_masks[4] = (limb_bits > 56 ? limb_bits - 56 : 0);
1663
1664 for (auto& mask : sublimb_masks) {
1665 mask = (1ULL << mask) - 1ULL;
1666 }
1667 return sublimb_masks;
1668 };
1669
1670 const auto lo_masks = get_limb_masks(lo_limb_bits);
1671 const auto hi_masks = get_limb_masks(hi_limb_bits);
1672 const std::array<uint32_t, 5> lo_sublimbs = get_sublimbs(lo_idx, lo_masks);
1673 const std::array<uint32_t, 5> hi_sublimbs = get_sublimbs(hi_idx, hi_masks);
1674
1675 blocks.nnf.populate_wires(lo_sublimbs[0], lo_sublimbs[1], lo_sublimbs[2], lo_idx);
1676 blocks.nnf.populate_wires(lo_sublimbs[3], lo_sublimbs[4], hi_sublimbs[0], hi_sublimbs[1]);
1677 blocks.nnf.populate_wires(hi_sublimbs[2], hi_sublimbs[3], hi_sublimbs[4], hi_idx);
1678
1679 apply_nnf_selectors(NNF_SELECTORS::LIMB_ACCUMULATE_1);
1680 apply_nnf_selectors(NNF_SELECTORS::LIMB_ACCUMULATE_2);
1681 apply_nnf_selectors(NNF_SELECTORS::NNF_NONE);
1682 this->num_gates += 3;
1683
1684 for (size_t i = 0; i < 5; i++) {
1685 if (lo_masks[i] != 0) {
1686 create_new_range_constraint(lo_sublimbs[i], lo_masks[i]);
1687 }
1688 if (hi_masks[i] != 0) {
1689 create_new_range_constraint(hi_sublimbs[i], hi_masks[i]);
1690 }
1691 }
1692};
1693
1704template <typename ExecutionTrace>
1705std::array<uint32_t, 2> UltraCircuitBuilder_<ExecutionTrace>::decompose_non_native_field_double_width_limb(
1706 const uint32_t limb_idx, const size_t num_limb_bits)
1707{
1708 BB_ASSERT_LT(uint256_t(this->get_variable_reference(limb_idx)), (uint256_t(1) << num_limb_bits));
1709 constexpr FF LIMB_MASK = (uint256_t(1) << DEFAULT_NON_NATIVE_FIELD_LIMB_BITS) - 1;
1710 const uint256_t value = this->get_variable(limb_idx);
1711 const uint256_t low = value & LIMB_MASK;
1712 const uint256_t hi = value >> DEFAULT_NON_NATIVE_FIELD_LIMB_BITS;
1713 BB_ASSERT_EQ(low + (hi << DEFAULT_NON_NATIVE_FIELD_LIMB_BITS), value);
1714
1715 const uint32_t low_idx = this->add_variable(low);
1716 const uint32_t hi_idx = this->add_variable(hi);
1717
1718 BB_ASSERT_GT(num_limb_bits, DEFAULT_NON_NATIVE_FIELD_LIMB_BITS);
1719 const size_t lo_bits = DEFAULT_NON_NATIVE_FIELD_LIMB_BITS;
1720 const size_t hi_bits = num_limb_bits - DEFAULT_NON_NATIVE_FIELD_LIMB_BITS;
1721 range_constrain_two_limbs(low_idx, hi_idx, lo_bits, hi_bits);
1722
1723 return std::array<uint32_t, 2>{ low_idx, hi_idx };
1724}
1725
1742template <typename ExecutionTrace>
1743std::array<uint32_t, 2> UltraCircuitBuilder_<ExecutionTrace>::evaluate_non_native_field_multiplication(
1744 const non_native_multiplication_witnesses<FF>& input)
1745{
1746
1747 std::array<fr, 4> a{
1748 this->get_variable(input.a[0]),
1749 this->get_variable(input.a[1]),
1750 this->get_variable(input.a[2]),
1751 this->get_variable(input.a[3]),
1752 };
1753 std::array<fr, 4> b{
1754 this->get_variable(input.b[0]),
1755 this->get_variable(input.b[1]),
1756 this->get_variable(input.b[2]),
1757 this->get_variable(input.b[3]),
1758 };
1759 std::array<fr, 4> q{
1760 this->get_variable(input.q[0]),
1761 this->get_variable(input.q[1]),
1762 this->get_variable(input.q[2]),
1763 this->get_variable(input.q[3]),
1764 };
1765 std::array<fr, 4> r{
1766 this->get_variable(input.r[0]),
1767 this->get_variable(input.r[1]),
1768 this->get_variable(input.r[2]),
1769 this->get_variable(input.r[3]),
1770 };
1771 constexpr FF LIMB_SHIFT = uint256_t(1) << DEFAULT_NON_NATIVE_FIELD_LIMB_BITS;
1772 constexpr FF LIMB_RSHIFT = FF(1) / FF(uint256_t(1) << DEFAULT_NON_NATIVE_FIELD_LIMB_BITS);
1773 constexpr FF LIMB_RSHIFT_2 = FF(1) / FF(uint256_t(1) << (2 * DEFAULT_NON_NATIVE_FIELD_LIMB_BITS));
1774
1775 FF lo_0 = a[0] * b[0] - r[0] + (a[1] * b[0] + a[0] * b[1]) * LIMB_SHIFT;
1776 FF lo_1 = (lo_0 + q[0] * input.neg_modulus[0] +
1777 (q[1] * input.neg_modulus[0] + q[0] * input.neg_modulus[1] - r[1]) * LIMB_SHIFT) *
1778 LIMB_RSHIFT_2;
1779
1780 FF hi_0 = a[2] * b[0] + a[0] * b[2] + (a[0] * b[3] + a[3] * b[0] - r[3]) * LIMB_SHIFT;
1781 FF hi_1 = hi_0 + a[1] * b[1] - r[2] + (a[1] * b[2] + a[2] * b[1]) * LIMB_SHIFT;
1782 FF hi_2 = (hi_1 + lo_1 + q[2] * input.neg_modulus[0] +
1783 (q[3] * input.neg_modulus[0] + q[2] * input.neg_modulus[1]) * LIMB_SHIFT);
1784 FF hi_3 = (hi_2 + (q[0] * input.neg_modulus[3] + q[1] * input.neg_modulus[2]) * LIMB_SHIFT +
1785 (q[0] * input.neg_modulus[2] + q[1] * input.neg_modulus[1])) *
1786 LIMB_RSHIFT_2;
1787
1788 const uint32_t lo_0_idx = this->add_variable(lo_0);
1789 const uint32_t lo_1_idx = this->add_variable(lo_1);
1790 const uint32_t hi_0_idx = this->add_variable(hi_0);
1791 const uint32_t hi_1_idx = this->add_variable(hi_1);
1792 const uint32_t hi_2_idx = this->add_variable(hi_2);
1793 const uint32_t hi_3_idx = this->add_variable(hi_3);
1794
1795 // TODO(https://github.com/AztecProtocol/barretenberg/issues/879): Originally this was a single arithmetic gate.
1796 // With trace sorting, we must add a dummy gate since the add gate would otherwise try to read into an nnf gate that
1797 // has been sorted out of sequence.
1798 // product gate 1
1799 // (lo_0 + q_0(p_0 + p_1*2^b) + q_1(p_0*2^b) - (r_1)2^b)2^-2b - lo_1 = 0
1800 create_big_add_gate({ input.q[0],
1801 input.q[1],
1802 input.r[1],
1803 lo_1_idx,
1804 input.neg_modulus[0] + input.neg_modulus[1] * LIMB_SHIFT,
1805 input.neg_modulus[0] * LIMB_SHIFT,
1806 -LIMB_SHIFT,
1807 -LIMB_SHIFT.sqr(),
1808 0 },
1809 true);
1810 create_dummy_gate(blocks.arithmetic, this->zero_idx, this->zero_idx, this->zero_idx, lo_0_idx);
1811 //
1812 // a = (a3 || a2 || a1 || a0) = (a3 * 2^b + a2) * 2^b + (a1 * 2^b + a0)
1813 // b = (b3 || b2 || b1 || b0) = (b3 * 2^b + b2) * 2^b + (b1 * 2^b + b0)
1814 //
1815 // Check if lo_0 was computed correctly.
1816 // The gate structure for the nnf gates is as follows:
1817 //
1818 // | a1 | b1 | r0 | lo_0 | <-- product gate 1: check lo_0
1819 // | a0 | b0 | a3 | b3 |
1820 // | a2 | b2 | r3 | hi_0 |
1821 // | a1 | b1 | r2 | hi_1 |
1822 //
1823 // Constaint: lo_0 = (a1 * b0 + a0 * b1) * 2^b + (a0 * b0) - r0
1824 // w4 = (w1 * w'2 + w'1 * w2) * 2^b + (w'1 * w'2) - w3
1825 //
1826 blocks.nnf.populate_wires(input.a[1], input.b[1], input.r[0], lo_0_idx);
1827 apply_nnf_selectors(NNF_SELECTORS::NON_NATIVE_FIELD_1);
1828 ++this->num_gates;
1829
1830 //
1831 // Check if hi_0 was computed correctly.
1832 //
1833 // | a1 | b1 | r0 | lo_0 |
1834 // | a0 | b0 | a3 | b3 | <-- product gate 2: check hi_0
1835 // | a2 | b2 | r3 | hi_0 |
1836 // | a1 | b1 | r2 | hi_1 |
1837 //
1838 // Constaint: hi_0 = (a0 * b3 + a3 * b0 - r3) * 2^b + (a0 * b2 + a2 * b0) - r2
1839 // w'4 = (w1 * w4 + w2 * w3 - w'3) * 2^b + (w1 * w'2 + w'1 * w2) - w'3
1840 //
1841 blocks.nnf.populate_wires(input.a[0], input.b[0], input.a[3], input.b[3]);
1842 apply_nnf_selectors(NNF_SELECTORS::NON_NATIVE_FIELD_2);
1843 ++this->num_gates;
1844
1845 //
1846 // Check if hi_1 was computed correctly.
1847 //
1848 // | a1 | b1 | r0 | lo_0 |
1849 // | a0 | b0 | a3 | b3 |
1850 // | a2 | b2 | r3 | hi_0 | <-- product gate 3: check hi_1
1851 // | a1 | b1 | r2 | hi_1 |
1852 //
1853 // Constaint: hi_1 = hi_0 + (a2 * b1 + a1 * b2) * 2^b + (a1 * b1)
1854 // w'4 = w4 + (w1 * w'2 + w'1 * w2) * 2^b + (w'1 * w'2)
1855 //
1856 blocks.nnf.populate_wires(input.a[2], input.b[2], input.r[3], hi_0_idx);
1857 apply_nnf_selectors(NNF_SELECTORS::NON_NATIVE_FIELD_3);
1858 ++this->num_gates;
1859
1860 //
1861 // Does nothing, but is used by the previous gate to read the hi_1 limb.
1862 //
1863 blocks.nnf.populate_wires(input.a[1], input.b[1], input.r[2], hi_1_idx);
1864 apply_nnf_selectors(NNF_SELECTORS::NNF_NONE);
1865 ++this->num_gates;
1866
1873 create_big_add_gate(
1874 {
1875 input.q[2],
1876 input.q[3],
1877 lo_1_idx,
1878 hi_1_idx,
1879 -input.neg_modulus[1] * LIMB_SHIFT - input.neg_modulus[0],
1880 -input.neg_modulus[0] * LIMB_SHIFT,
1881 -1,
1882 -1,
1883 0,
1884 },
1885 true);
1886
1892 create_big_add_gate({
1893 hi_3_idx,
1894 input.q[0],
1895 input.q[1],
1896 hi_2_idx,
1897 -1,
1898 input.neg_modulus[3] * LIMB_RSHIFT + input.neg_modulus[2] * LIMB_RSHIFT_2,
1899 input.neg_modulus[2] * LIMB_RSHIFT + input.neg_modulus[1] * LIMB_RSHIFT_2,
1900 LIMB_RSHIFT_2,
1901 0,
1902 });
1903
1904 return std::array<uint32_t, 2>{ lo_1_idx, hi_3_idx };
1905}
1906
1911template <typename ExecutionTrace> void UltraCircuitBuilder_<ExecutionTrace>::populate_public_inputs_block()
1912{
1913 PROFILE_THIS_NAME("populate_public_inputs_block");
1914
1915 // Update the public inputs block
1916 for (const auto& idx : this->public_inputs()) {
1917 // first two wires get a copy of the public inputs
1918 blocks.pub_inputs.populate_wires(idx, idx, this->zero_idx, this->zero_idx);
1919 for (auto& selector : this->blocks.pub_inputs.get_selectors()) {
1920 selector.emplace_back(0);
1921 }
1922 }
1923}
1924
1930template <typename ExecutionTrace> void UltraCircuitBuilder_<ExecutionTrace>::process_non_native_field_multiplications()
1931{
1932 for (size_t i = 0; i < cached_partial_non_native_field_multiplications.size(); ++i) {
1933 auto& c = cached_partial_non_native_field_multiplications[i];
1934 for (size_t j = 0; j < c.a.size(); ++j) {
1935 c.a[j] = this->real_variable_index[c.a[j]];
1936 c.b[j] = this->real_variable_index[c.b[j]];
1937 }
1938 }
1939 cached_partial_non_native_field_multiplication::deduplicate(cached_partial_non_native_field_multiplications, this);
1940
1941 // iterate over the cached items and create constraints
1942 for (const auto& input : cached_partial_non_native_field_multiplications) {
1943
1944 blocks.nnf.populate_wires(input.a[1], input.b[1], this->zero_idx, input.lo_0);
1945 apply_nnf_selectors(NNF_SELECTORS::NON_NATIVE_FIELD_1);
1946 ++this->num_gates;
1947
1948 blocks.nnf.populate_wires(input.a[0], input.b[0], input.a[3], input.b[3]);
1949 apply_nnf_selectors(NNF_SELECTORS::NON_NATIVE_FIELD_2);
1950 ++this->num_gates;
1951
1952 blocks.nnf.populate_wires(input.a[2], input.b[2], this->zero_idx, input.hi_0);
1953 apply_nnf_selectors(NNF_SELECTORS::NON_NATIVE_FIELD_3);
1954 ++this->num_gates;
1955
1956 blocks.nnf.populate_wires(input.a[1], input.b[1], this->zero_idx, input.hi_1);
1957 apply_nnf_selectors(NNF_SELECTORS::NNF_NONE);
1958 ++this->num_gates;
1959 }
1960}
1961
1970template <typename ExecutionTrace>
1971std::array<uint32_t, 2> UltraCircuitBuilder_<ExecutionTrace>::queue_partial_non_native_field_multiplication(
1972 const non_native_partial_multiplication_witnesses<FF>& input)
1973{
1974
1975 std::array<fr, 4> a{
1976 this->get_variable(input.a[0]),
1977 this->get_variable(input.a[1]),
1978 this->get_variable(input.a[2]),
1979 this->get_variable(input.a[3]),
1980 };
1981 std::array<fr, 4> b{
1982 this->get_variable(input.b[0]),
1983 this->get_variable(input.b[1]),
1984 this->get_variable(input.b[2]),
1985 this->get_variable(input.b[3]),
1986 };
1987
1988 constexpr FF LIMB_SHIFT = uint256_t(1) << DEFAULT_NON_NATIVE_FIELD_LIMB_BITS;
1989
1990 FF lo_0 = a[0] * b[0] + (a[1] * b[0] + a[0] * b[1]) * LIMB_SHIFT;
1991
1992 FF hi_0 = a[2] * b[0] + a[0] * b[2] + (a[0] * b[3] + a[3] * b[0]) * LIMB_SHIFT;
1993 FF hi_1 = hi_0 + a[1] * b[1] + (a[1] * b[2] + a[2] * b[1]) * LIMB_SHIFT;
1994
1995 const uint32_t lo_0_idx = this->add_variable(lo_0);
1996 const uint32_t hi_0_idx = this->add_variable(hi_0);
1997 const uint32_t hi_1_idx = this->add_variable(hi_1);
1998
1999 // Add witnesses into the multiplication cache
2000 // (when finalising the circuit, we will remove duplicates; several dups produced by biggroup.hpp methods)
2001 cached_partial_non_native_field_multiplication cache_entry{
2002 .a = input.a,
2003 .b = input.b,
2004 .lo_0 = lo_0_idx,
2005 .hi_0 = hi_0_idx,
2006 .hi_1 = hi_1_idx,
2007 };
2008 cached_partial_non_native_field_multiplications.emplace_back(cache_entry);
2009 return std::array<uint32_t, 2>{ lo_0_idx, hi_1_idx };
2010}
2011
2017template <typename ExecutionTrace>
2018std::array<uint32_t, 5> UltraCircuitBuilder_<ExecutionTrace>::evaluate_non_native_field_addition(
2019 add_simple limb0, add_simple limb1, add_simple limb2, add_simple limb3, std::tuple<uint32_t, uint32_t, FF> limbp)
2020{
2021 const auto& x_0 = std::get<0>(limb0).first;
2022 const auto& x_1 = std::get<0>(limb1).first;
2023 const auto& x_2 = std::get<0>(limb2).first;
2024 const auto& x_3 = std::get<0>(limb3).first;
2025 const auto& x_p = std::get<0>(limbp);
2026
2027 const auto& x_mulconst0 = std::get<0>(limb0).second;
2028 const auto& x_mulconst1 = std::get<0>(limb1).second;
2029 const auto& x_mulconst2 = std::get<0>(limb2).second;
2030 const auto& x_mulconst3 = std::get<0>(limb3).second;
2031
2032 const auto& y_0 = std::get<1>(limb0).first;
2033 const auto& y_1 = std::get<1>(limb1).first;
2034 const auto& y_2 = std::get<1>(limb2).first;
2035 const auto& y_3 = std::get<1>(limb3).first;
2036 const auto& y_p = std::get<1>(limbp);
2037
2038 const auto& y_mulconst0 = std::get<1>(limb0).second;
2039 const auto& y_mulconst1 = std::get<1>(limb1).second;
2040 const auto& y_mulconst2 = std::get<1>(limb2).second;
2041 const auto& y_mulconst3 = std::get<1>(limb3).second;
2042
2043 // constant additive terms
2044 const auto& addconst0 = std::get<2>(limb0);
2045 const auto& addconst1 = std::get<2>(limb1);
2046 const auto& addconst2 = std::get<2>(limb2);
2047 const auto& addconst3 = std::get<2>(limb3);
2048 const auto& addconstp = std::get<2>(limbp);
2049
2050 // get value of result limbs
2051 const auto z_0value = this->get_variable(x_0) * x_mulconst0 + this->get_variable(y_0) * y_mulconst0 + addconst0;
2052 const auto z_1value = this->get_variable(x_1) * x_mulconst1 + this->get_variable(y_1) * y_mulconst1 + addconst1;
2053 const auto z_2value = this->get_variable(x_2) * x_mulconst2 + this->get_variable(y_2) * y_mulconst2 + addconst2;
2054 const auto z_3value = this->get_variable(x_3) * x_mulconst3 + this->get_variable(y_3) * y_mulconst3 + addconst3;
2055 const auto z_pvalue = this->get_variable(x_p) + this->get_variable(y_p) + addconstp;
2056
2057 const auto z_0 = this->add_variable(z_0value);
2058 const auto z_1 = this->add_variable(z_1value);
2059 const auto z_2 = this->add_variable(z_2value);
2060 const auto z_3 = this->add_variable(z_3value);
2061 const auto z_p = this->add_variable(z_pvalue);
2062
2076 // GATE 1
2077 // | 1 | 2 | 3 | 4 |
2078 // |-----|-----|-----|-----|
2079 // | y.p | x.0 | y.0 | z.p | (b.p + b.p - c.p = 0) AND (a.0 + b.0 - c.0 = 0)
2080 // | x.p | x.1 | y.1 | z.0 | (a.1 + b.1 - c.1 = 0)
2081 // | x.2 | y.2 | z.2 | z.1 | (a.2 + b.2 - c.2 = 0)
2082 // | x.3 | y.3 | z.3 | --- | (a.3 + b.3 - c.3 = 0)
2083 // TODO(https://github.com/AztecProtocol/barretenberg/issues/896): descrepency between above comment and the actual
2084 // implementation below.
2085 auto& block = blocks.arithmetic;
2086 block.populate_wires(y_p, x_0, y_0, x_p);
2087 block.populate_wires(z_p, x_1, y_1, z_0);
2088 block.populate_wires(x_2, y_2, z_2, z_1);
2089 block.populate_wires(x_3, y_3, z_3, this->zero_idx);
2090
2091 block.q_m().emplace_back(addconstp);
2092 block.q_1().emplace_back(0);
2093 block.q_2().emplace_back(-x_mulconst0 *
2094 2); // scale constants by 2. If q_arith = 3 then w_4_omega value (z0) gets scaled by 2x
2095 block.q_3().emplace_back(-y_mulconst0 * 2); // z_0 - (x_0 * -xmulconst0) - (y_0 * ymulconst0) = 0 => z_0 = x_0 + y_0
2096 block.q_4().emplace_back(0);
2097 block.q_c().emplace_back(-addconst0 * 2);
2098 block.q_arith().emplace_back(3);
2099
2100 block.q_m().emplace_back(0);
2101 block.q_1().emplace_back(0);
2102 block.q_2().emplace_back(-x_mulconst1);
2103 block.q_3().emplace_back(-y_mulconst1);
2104 block.q_4().emplace_back(0);
2105 block.q_c().emplace_back(-addconst1);
2106 block.q_arith().emplace_back(2);
2107
2108 block.q_m().emplace_back(0);
2109 block.q_1().emplace_back(-x_mulconst2);
2110 block.q_2().emplace_back(-y_mulconst2);
2111 block.q_3().emplace_back(1);
2112 block.q_4().emplace_back(0);
2113 block.q_c().emplace_back(-addconst2);
2114 block.q_arith().emplace_back(1);
2115
2116 block.q_m().emplace_back(0);
2117 block.q_1().emplace_back(-x_mulconst3);
2118 block.q_2().emplace_back(-y_mulconst3);
2119 block.q_3().emplace_back(1);
2120 block.q_4().emplace_back(0);
2121 block.q_c().emplace_back(-addconst3);
2122 block.q_arith().emplace_back(1);
2123
2124 for (size_t i = 0; i < 4; ++i) {
2125 block.q_delta_range().emplace_back(0);
2126 block.q_lookup_type().emplace_back(0);
2127 block.q_elliptic().emplace_back(0);
2128 block.q_memory().emplace_back(0);
2129 block.q_nnf().emplace_back(0);
2130 block.q_poseidon2_external().emplace_back(0);
2131 block.q_poseidon2_internal().emplace_back(0);
2132 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
2133 block.pad_additional();
2134 }
2135 }
2136 check_selector_length_consistency();
2137
2138 this->num_gates += 4;
2139 return std::array<uint32_t, 5>{
2140 z_0, z_1, z_2, z_3, z_p,
2141 };
2142}
2143
2144template <typename ExecutionTrace>
2145std::array<uint32_t, 5> UltraCircuitBuilder_<ExecutionTrace>::evaluate_non_native_field_subtraction(
2146 add_simple limb0, add_simple limb1, add_simple limb2, add_simple limb3, std::tuple<uint32_t, uint32_t, FF> limbp)
2147{
2148 const auto& x_0 = std::get<0>(limb0).first;
2149 const auto& x_1 = std::get<0>(limb1).first;
2150 const auto& x_2 = std::get<0>(limb2).first;
2151 const auto& x_3 = std::get<0>(limb3).first;
2152 const auto& x_p = std::get<0>(limbp);
2153
2154 const auto& x_mulconst0 = std::get<0>(limb0).second;
2155 const auto& x_mulconst1 = std::get<0>(limb1).second;
2156 const auto& x_mulconst2 = std::get<0>(limb2).second;
2157 const auto& x_mulconst3 = std::get<0>(limb3).second;
2158
2159 const auto& y_0 = std::get<1>(limb0).first;
2160 const auto& y_1 = std::get<1>(limb1).first;
2161 const auto& y_2 = std::get<1>(limb2).first;
2162 const auto& y_3 = std::get<1>(limb3).first;
2163 const auto& y_p = std::get<1>(limbp);
2164
2165 const auto& y_mulconst0 = std::get<1>(limb0).second;
2166 const auto& y_mulconst1 = std::get<1>(limb1).second;
2167 const auto& y_mulconst2 = std::get<1>(limb2).second;
2168 const auto& y_mulconst3 = std::get<1>(limb3).second;
2169
2170 // constant additive terms
2171 const auto& addconst0 = std::get<2>(limb0);
2172 const auto& addconst1 = std::get<2>(limb1);
2173 const auto& addconst2 = std::get<2>(limb2);
2174 const auto& addconst3 = std::get<2>(limb3);
2175 const auto& addconstp = std::get<2>(limbp);
2176
2177 // get value of result limbs
2178 const auto z_0value = this->get_variable(x_0) * x_mulconst0 - this->get_variable(y_0) * y_mulconst0 + addconst0;
2179 const auto z_1value = this->get_variable(x_1) * x_mulconst1 - this->get_variable(y_1) * y_mulconst1 + addconst1;
2180 const auto z_2value = this->get_variable(x_2) * x_mulconst2 - this->get_variable(y_2) * y_mulconst2 + addconst2;
2181 const auto z_3value = this->get_variable(x_3) * x_mulconst3 - this->get_variable(y_3) * y_mulconst3 + addconst3;
2182 const auto z_pvalue = this->get_variable(x_p) - this->get_variable(y_p) + addconstp;
2183
2184 const auto z_0 = this->add_variable(z_0value);
2185 const auto z_1 = this->add_variable(z_1value);
2186 const auto z_2 = this->add_variable(z_2value);
2187 const auto z_3 = this->add_variable(z_3value);
2188 const auto z_p = this->add_variable(z_pvalue);
2189
2202 // GATE 1
2203 // | 1 | 2 | 3 | 4 |
2204 // |-----|-----|-----|-----|
2205 // | y.p | x.0 | y.0 | z.p | (b.p + c.p - a.p = 0) AND (a.0 - b.0 - c.0 = 0)
2206 // | x.p | x.1 | y.1 | z.0 | (a.1 - b.1 - c.1 = 0)
2207 // | x.2 | y.2 | z.2 | z.1 | (a.2 - b.2 - c.2 = 0)
2208 // | x.3 | y.3 | z.3 | --- | (a.3 - b.3 - c.3 = 0)
2209 auto& block = blocks.arithmetic;
2210 block.populate_wires(y_p, x_0, y_0, z_p);
2211 block.populate_wires(x_p, x_1, y_1, z_0);
2212 block.populate_wires(x_2, y_2, z_2, z_1);
2213 block.populate_wires(x_3, y_3, z_3, this->zero_idx);
2214
2215 block.q_m().emplace_back(-addconstp);
2216 block.q_1().emplace_back(0);
2217 block.q_2().emplace_back(-x_mulconst0 * 2);
2218 block.q_3().emplace_back(y_mulconst0 * 2); // z_0 + (x_0 * -xmulconst0) + (y_0 * ymulconst0) = 0 => z_0 = x_0 - y_0
2219 block.q_4().emplace_back(0);
2220 block.q_c().emplace_back(-addconst0 * 2);
2221 block.q_arith().emplace_back(3);
2222
2223 block.q_m().emplace_back(0);
2224 block.q_1().emplace_back(0);
2225 block.q_2().emplace_back(-x_mulconst1);
2226 block.q_3().emplace_back(y_mulconst1);
2227 block.q_4().emplace_back(0);
2228 block.q_c().emplace_back(-addconst1);
2229 block.q_arith().emplace_back(2);
2230
2231 block.q_m().emplace_back(0);
2232 block.q_1().emplace_back(-x_mulconst2);
2233 block.q_2().emplace_back(y_mulconst2);
2234 block.q_3().emplace_back(1);
2235 block.q_4().emplace_back(0);
2236 block.q_c().emplace_back(-addconst2);
2237 block.q_arith().emplace_back(1);
2238
2239 block.q_m().emplace_back(0);
2240 block.q_1().emplace_back(-x_mulconst3);
2241 block.q_2().emplace_back(y_mulconst3);
2242 block.q_3().emplace_back(1);
2243 block.q_4().emplace_back(0);
2244 block.q_c().emplace_back(-addconst3);
2245 block.q_arith().emplace_back(1);
2246
2247 for (size_t i = 0; i < 4; ++i) {
2248 block.q_delta_range().emplace_back(0);
2249 block.q_lookup_type().emplace_back(0);
2250 block.q_elliptic().emplace_back(0);
2251 block.q_memory().emplace_back(0);
2252 block.q_nnf().emplace_back(0);
2253 block.q_poseidon2_external().emplace_back(0);
2254 block.q_poseidon2_internal().emplace_back(0);
2255 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
2256 block.pad_additional();
2257 }
2258 }
2259 check_selector_length_consistency();
2260
2261 this->num_gates += 4;
2262 return std::array<uint32_t, 5>{
2263 z_0, z_1, z_2, z_3, z_p,
2264 };
2265}
2266
2277template <typename ExecutionTrace>
2278size_t UltraCircuitBuilder_<ExecutionTrace>::create_ROM_array(const size_t array_size)
2279{
2280 return this->rom_ram_logic.create_ROM_array(array_size);
2281}
2282
2293template <typename ExecutionTrace>
2294size_t UltraCircuitBuilder_<ExecutionTrace>::create_RAM_array(const size_t array_size)
2295{
2296 return this->rom_ram_logic.create_RAM_array(array_size);
2297}
2298
2306template <typename ExecutionTrace>
2307void UltraCircuitBuilder_<ExecutionTrace>::init_RAM_element(const size_t ram_id,
2308 const size_t index_value,
2309 const uint32_t value_witness)
2310{
2311 this->rom_ram_logic.init_RAM_element(this, ram_id, index_value, value_witness);
2312}
2313
2314template <typename ExecutionTrace>
2315uint32_t UltraCircuitBuilder_<ExecutionTrace>::read_RAM_array(const size_t ram_id, const uint32_t index_witness)
2316{
2317 return this->rom_ram_logic.read_RAM_array(this, ram_id, index_witness);
2318}
2319
2320template <typename ExecutionTrace>
2321void UltraCircuitBuilder_<ExecutionTrace>::write_RAM_array(const size_t ram_id,
2322 const uint32_t index_witness,
2323 const uint32_t value_witness)
2324{
2325 this->rom_ram_logic.write_RAM_array(this, ram_id, index_witness, value_witness);
2326}
2327
2342template <typename ExecutionTrace>
2343void UltraCircuitBuilder_<ExecutionTrace>::set_ROM_element(const size_t rom_id,
2344 const size_t index_value,
2345 const uint32_t value_witness)
2346{
2347 this->rom_ram_logic.set_ROM_element(this, rom_id, index_value, value_witness);
2348}
2349
2357template <typename ExecutionTrace>
2358void UltraCircuitBuilder_<ExecutionTrace>::set_ROM_element_pair(const size_t rom_id,
2359 const size_t index_value,
2360 const std::array<uint32_t, 2>& value_witnesses)
2361{
2362 this->rom_ram_logic.set_ROM_element_pair(this, rom_id, index_value, value_witnesses);
2363}
2364
2372template <typename ExecutionTrace>
2373uint32_t UltraCircuitBuilder_<ExecutionTrace>::read_ROM_array(const size_t rom_id, const uint32_t index_witness)
2374{
2375 return this->rom_ram_logic.read_ROM_array(this, rom_id, index_witness);
2376}
2377
2385template <typename ExecutionTrace>
2386std::array<uint32_t, 2> UltraCircuitBuilder_<ExecutionTrace>::read_ROM_array_pair(const size_t rom_id,
2387 const uint32_t index_witness)
2388{
2389 return this->rom_ram_logic.read_ROM_array_pair(this, rom_id, index_witness);
2390}
2391
2395template <typename FF>
2396void UltraCircuitBuilder_<FF>::create_poseidon2_external_gate(const poseidon2_external_gate_<FF>& in)
2397{
2398 auto& block = this->blocks.poseidon2_external;
2399 block.populate_wires(in.a, in.b, in.c, in.d);
2400 block.q_m().emplace_back(0);
2401 block.q_1().emplace_back(crypto::Poseidon2Bn254ScalarFieldParams::round_constants[in.round_idx][0]);
2402 block.q_2().emplace_back(crypto::Poseidon2Bn254ScalarFieldParams::round_constants[in.round_idx][1]);
2403 block.q_3().emplace_back(crypto::Poseidon2Bn254ScalarFieldParams::round_constants[in.round_idx][2]);
2404 block.q_c().emplace_back(0);
2405 block.q_arith().emplace_back(0);
2406 block.q_4().emplace_back(crypto::Poseidon2Bn254ScalarFieldParams::round_constants[in.round_idx][3]);
2407 block.q_delta_range().emplace_back(0);
2408 block.q_lookup_type().emplace_back(0);
2409 block.q_elliptic().emplace_back(0);
2410 block.q_memory().emplace_back(0);
2411 block.q_nnf().emplace_back(0);
2412 block.q_poseidon2_external().emplace_back(1);
2413 block.q_poseidon2_internal().emplace_back(0);
2414 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
2415 block.pad_additional();
2416 }
2417 this->check_selector_length_consistency();
2418 ++this->num_gates;
2419}
2420
2424template <typename FF>
2425void UltraCircuitBuilder_<FF>::create_poseidon2_internal_gate(const poseidon2_internal_gate_<FF>& in)
2426{
2427 auto& block = this->blocks.poseidon2_internal;
2428 block.populate_wires(in.a, in.b, in.c, in.d);
2429 block.q_m().emplace_back(0);
2430 block.q_1().emplace_back(crypto::Poseidon2Bn254ScalarFieldParams::round_constants[in.round_idx][0]);
2431 block.q_2().emplace_back(0);
2432 block.q_3().emplace_back(0);
2433 block.q_c().emplace_back(0);
2434 block.q_arith().emplace_back(0);
2435 block.q_4().emplace_back(0);
2436 block.q_delta_range().emplace_back(0);
2437 block.q_lookup_type().emplace_back(0);
2438 block.q_elliptic().emplace_back(0);
2439 block.q_memory().emplace_back(0);
2440 block.q_nnf().emplace_back(0);
2441 block.q_poseidon2_external().emplace_back(0);
2442 block.q_poseidon2_internal().emplace_back(1);
2443 if constexpr (HasAdditionalSelectors<ExecutionTrace>) {
2444 block.pad_additional();
2445 }
2446 this->check_selector_length_consistency();
2447 ++this->num_gates;
2448}
2449
2456template <typename ExecutionTrace> msgpack::sbuffer UltraCircuitBuilder_<ExecutionTrace>::export_circuit()
2457{
2458 // You should not name `zero` by yourself
2459 // but it will be rewritten anyway
2460 auto first_zero_idx = this->get_first_variable_in_class(this->zero_idx);
2461 if (!this->variable_names.contains(first_zero_idx)) {
2462 this->set_variable_name(this->zero_idx, "zero");
2463 } else {
2464 this->variable_names[first_zero_idx] = "zero";
2465 }
2466 using base = CircuitBuilderBase<FF>;
2467 CircuitSchemaInternal<FF> cir;
2468
2469 std::array<uint64_t, 4> modulus = {
2470 FF::Params::modulus_0, FF::Params::modulus_1, FF::Params::modulus_2, FF::Params::modulus_3
2471 };
2472 std::stringstream buf;
2473 buf << std::hex << std::setfill('0') << std::setw(16) << modulus[3] << std::setw(16) << modulus[2] << std::setw(16)
2474 << modulus[1] << std::setw(16) << modulus[0];
2475
2476 cir.modulus = buf.str();
2477
2478 for (uint32_t i = 0; i < this->num_public_inputs(); i++) {
2479 cir.public_inps.push_back(this->real_variable_index[this->public_inputs()[i]]);
2480 }
2481
2482 for (auto& tup : base::variable_names) {
2483 cir.vars_of_interest.insert({ this->real_variable_index[tup.first], tup.second });
2484 }
2485
2486 for (const auto& var : this->get_variables()) {
2487 cir.variables.push_back(var);
2488 }
2489
2490 FF curve_b;
2491 if constexpr (FF::modulus == bb::fq::modulus) {
2492 curve_b = bb::g1::curve_b;
2493 } else if constexpr (FF::modulus == grumpkin::fq::modulus) {
2494 curve_b = grumpkin::g1::curve_b;
2495 } else {
2496 curve_b = 0;
2497 }
2498
2499 for (auto& block : blocks.get()) {
2500 std::vector<std::vector<FF>> block_selectors;
2501 std::vector<std::vector<uint32_t>> block_wires;
2502 for (size_t idx = 0; idx < block.size(); ++idx) {
2503 std::vector<FF> tmp_sel = { block.q_m()[idx],
2504 block.q_1()[idx],
2505 block.q_2()[idx],
2506 block.q_3()[idx],
2507 block.q_4()[idx],
2508 block.q_c()[idx],
2509 block.q_arith()[idx],
2510 block.q_delta_range()[idx],
2511 block.q_elliptic()[idx],
2512 block.q_memory()[idx],
2513 block.q_nnf()[idx],
2514 block.q_lookup_type()[idx],
2515 curve_b };
2516
2517 std::vector<uint32_t> tmp_w = {
2518 this->real_variable_index[block.w_l()[idx]],
2519 this->real_variable_index[block.w_r()[idx]],
2520 this->real_variable_index[block.w_o()[idx]],
2521 this->real_variable_index[block.w_4()[idx]],
2522 };
2523
2524 if (idx < block.size() - 1) {
2525 tmp_w.push_back(block.w_l()[idx + 1]);
2526 tmp_w.push_back(block.w_r()[idx + 1]);
2527 tmp_w.push_back(block.w_o()[idx + 1]);
2528 tmp_w.push_back(block.w_4()[idx + 1]);
2529 } else {
2530 tmp_w.push_back(0);
2531 tmp_w.push_back(0);
2532 tmp_w.push_back(0);
2533 tmp_w.push_back(0);
2534 }
2535
2536 block_selectors.push_back(tmp_sel);
2537 block_wires.push_back(tmp_w);
2538 }
2539 cir.selectors.push_back(block_selectors);
2540 cir.wires.push_back(block_wires);
2541 }
2542
2543 cir.real_variable_index = this->real_variable_index;
2544
2545 for (const auto& table : this->lookup_tables) {
2546 const FF table_index(table.table_index);
2547 info("Table no: ", table.table_index);
2548 std::vector<std::vector<FF>> tmp_table;
2549 for (size_t i = 0; i < table.size(); ++i) {
2550 tmp_table.push_back({ table.column_1[i], table.column_2[i], table.column_3[i] });
2551 }
2552 cir.lookup_tables.push_back(tmp_table);
2553 }
2554
2555 cir.real_variable_tags = this->real_variable_tags;
2556
2557 for (const auto& list : range_lists) {
2558 cir.range_tags[list.second.range_tag] = list.first;
2559 }
2560
2561 for (auto& rom_table : this->rom_ram_logic.rom_arrays) {
2562 std::sort(rom_table.records.begin(), rom_table.records.end());
2563
2564 std::vector<std::vector<uint32_t>> table;
2565 table.reserve(rom_table.records.size());
2566 for (const auto& rom_entry : rom_table.records) {
2567 table.push_back({
2568 this->real_variable_index[rom_entry.index_witness],
2569 this->real_variable_index[rom_entry.value_column1_witness],
2570 this->real_variable_index[rom_entry.value_column2_witness],
2571 });
2572 }
2573 cir.rom_records.push_back(table);
2574 cir.rom_states.push_back(rom_table.state);
2575 }
2576
2577 for (auto& ram_table : this->rom_ram_logic.ram_arrays) {
2578 std::sort(ram_table.records.begin(), ram_table.records.end());
2579
2580 std::vector<std::vector<uint32_t>> table;
2581 table.reserve(ram_table.records.size());
2582 for (const auto& ram_entry : ram_table.records) {
2583 table.push_back({ this->real_variable_index[ram_entry.index_witness],
2584 this->real_variable_index[ram_entry.value_witness],
2585 this->real_variable_index[ram_entry.timestamp_witness],
2586 ram_entry.access_type });
2587 }
2588 cir.ram_records.push_back(table);
2589 cir.ram_states.push_back(ram_table.state);
2590 }
2591
2592 cir.circuit_finalized = this->circuit_finalized;
2593
2594 msgpack::sbuffer buffer;
2595 msgpack::pack(buffer, cir);
2596 return buffer;
2597}
2598
2599template class UltraCircuitBuilder_<UltraExecutionTraceBlocks>;
2600template class UltraCircuitBuilder_<MegaExecutionTraceBlocks>;
2601// To enable this we need to template plookup
2602// template class UltraCircuitBuilder_<grumpkin::fr>;
2603
2604} // namespace bb
BB_ASSERT_GT
#define BB_ASSERT_GT(left, right,...)
Definition assert.hpp:87
BB_ASSERT_EQ
#define BB_ASSERT_EQ(actual, expected,...)
Definition assert.hpp:59
BB_ASSERT_LTE
#define BB_ASSERT_LTE(left, right,...)
Definition assert.hpp:129
BB_ASSERT_LT
#define BB_ASSERT_LT(left, right,...)
Definition assert.hpp:115
ASSERT
#define ASSERT(expression,...)
Definition assert.hpp:49
bb::UltraCircuitBuilder_
Definition ultra_circuit_builder.hpp:42
bb::UltraCircuitBuilder_::create_add_gate
void create_add_gate(const add_triple_< FF > &in) override
Create an addition gate, where in.a * in.a_scaling + in.b * in.b_scaling + in.c * in....
Definition ultra_circuit_builder.cpp:294
bb::UltraCircuitBuilder_::fix_witness
void fix_witness(const uint32_t witness_index, const FF &witness_value)
Add a gate equating a particular witness to a constant, fixing its value.
Definition ultra_circuit_builder.cpp:751
bb::UltraCircuitBuilder_::init_RAM_element
void init_RAM_element(const size_t ram_id, const size_t index_value, const uint32_t value_witness)
Initialize a RAM cell to equal value_witness
Definition ultra_circuit_builder.cpp:2307
bb::UltraCircuitBuilder_::create_ecc_dbl_gate
void create_ecc_dbl_gate(const ecc_dbl_gate_< FF > &in)
Create an elliptic curve doubling gate.
Definition ultra_circuit_builder.cpp:690
bb::UltraCircuitBuilder_::add_gates_to_ensure_all_polys_are_non_zero
void add_gates_to_ensure_all_polys_are_non_zero()
Ensure all polynomials have at least one non-zero coefficient to avoid commiting to the zero-polynomi...
Definition ultra_circuit_builder.cpp:83
bb::UltraCircuitBuilder_::process_range_list
void process_range_list(RangeList &list)
Definition ultra_circuit_builder.cpp:1072
bb::UltraCircuitBuilder_::create_poseidon2_internal_gate
void create_poseidon2_internal_gate(const poseidon2_internal_gate_< FF > &in)
Poseidon2 internal round gate, activates the q_poseidon2_internal selector and relation.
Definition ultra_circuit_builder.cpp:2425
bb::UltraCircuitBuilder_::create_RAM_array
size_t create_RAM_array(const size_t array_size)
Create a new updatable memory region.
Definition ultra_circuit_builder.cpp:2294
bb::UltraCircuitBuilder_::create_big_mul_gate
void create_big_mul_gate(const mul_quad_< FF > &in)
Create a basic multiplication gate q_m * a * b + q_1 * a + q_2 * b + q_3 * c + q_4 * d + q_c = 0 (q_a...
Definition ultra_circuit_builder.cpp:461
bb::UltraCircuitBuilder_::MEMORY_SELECTORS
MEMORY_SELECTORS
Definition ultra_circuit_builder.hpp:69
bb::UltraCircuitBuilder_::create_big_mul_add_gate
void create_big_mul_add_gate(const mul_quad_< FF > &in, const bool use_next_gate_w_4=false)
Create a big multiplication-addition gate, where in.a * in.b * in.mul_scaling + in....
Definition ultra_circuit_builder.cpp:329
bb::UltraCircuitBuilder_::process_range_lists
void process_range_lists()
Definition ultra_circuit_builder.cpp:1126
bb::UltraCircuitBuilder_::range_constrain_two_limbs
void range_constrain_two_limbs(const uint32_t lo_idx, const uint32_t hi_idx, const size_t lo_limb_bits=DEFAULT_NON_NATIVE_FIELD_LIMB_BITS, const size_t hi_limb_bits=DEFAULT_NON_NATIVE_FIELD_LIMB_BITS)
Definition ultra_circuit_builder.cpp:1626
bb::UltraCircuitBuilder_::decompose_into_default_range
std::vector< uint32_t > decompose_into_default_range(const uint32_t variable_index, const uint64_t num_bits, const uint64_t target_range_bitnum=DEFAULT_PLOOKUP_RANGE_BITNUM, std::string const &msg="decompose_into_default_range")
Definition ultra_circuit_builder.cpp:904
bb::UltraCircuitBuilder_::export_circuit
msgpack::sbuffer export_circuit() override
Definition ultra_circuit_builder.cpp:2456
bb::UltraCircuitBuilder_::create_sort_constraint_with_edges
void create_sort_constraint_with_edges(const std::vector< uint32_t > &variable_index, const FF &, const FF &)
Definition ultra_circuit_builder.cpp:1204
bb::UltraCircuitBuilder_::add_simple
std::tuple< scaled_witness, scaled_witness, FF > add_simple
Definition ultra_circuit_builder.hpp:759
bb::UltraCircuitBuilder_::read_RAM_array
uint32_t read_RAM_array(const size_t ram_id, const uint32_t index_witness)
Definition ultra_circuit_builder.cpp:2315
bb::UltraCircuitBuilder_::create_big_add_gate
void create_big_add_gate(const add_quad_< FF > &in, const bool use_next_gate_w_4=false)
Create a big addition gate, where in.a * in.a_scaling + in.b * in.b_scaling + in.c * in....
Definition ultra_circuit_builder.cpp:364
bb::UltraCircuitBuilder_::FF
typename ExecutionTrace::FF FF
Definition ultra_circuit_builder.hpp:45
bb::UltraCircuitBuilder_::evaluate_non_native_field_addition
std::array< uint32_t, 5 > evaluate_non_native_field_addition(add_simple limb0, add_simple limb1, add_simple limb2, add_simple limb3, std::tuple< uint32_t, uint32_t, FF > limbp)
Definition ultra_circuit_builder.cpp:2018
bb::UltraCircuitBuilder_::create_ROM_array
size_t create_ROM_array(const size_t array_size)
Create a new read-only memory region.
Definition ultra_circuit_builder.cpp:2278
bb::UltraCircuitBuilder_::create_balanced_add_gate
void create_balanced_add_gate(const add_quad_< FF > &in)
Definition ultra_circuit_builder.cpp:490
bb::UltraCircuitBuilder_::create_gates_from_plookup_accumulators
plookup::ReadData< uint32_t > create_gates_from_plookup_accumulators(const plookup::MultiTableId &id, const plookup::ReadData< FF > &read_values, const uint32_t key_a_index, std::optional< uint32_t > key_b_index=std::nullopt)
Perform a series of lookups, one for each 'row' in read_values.
Definition ultra_circuit_builder.cpp:816
bb::UltraCircuitBuilder_::decompose_non_native_field_double_width_limb
std::array< uint32_t, 2 > decompose_non_native_field_double_width_limb(const uint32_t limb_idx, const size_t num_limb_bits=(2 *DEFAULT_NON_NATIVE_FIELD_LIMB_BITS))
Decompose a single witness into two, where the lowest is DEFAULT_NON_NATIVE_FIELD_LIMB_BITS (68) rang...
Definition ultra_circuit_builder.cpp:1705
bb::UltraCircuitBuilder_::get_table
plookup::BasicTable & get_table(const plookup::BasicTableId id)
Get the basic table with provided ID from the set of tables for the present circuit; create it if it ...
Definition ultra_circuit_builder.cpp:799
bb::UltraCircuitBuilder_::apply_nnf_selectors
void apply_nnf_selectors(const NNF_SELECTORS type)
Enable the nnf gate of particular type.
Definition ultra_circuit_builder.cpp:1521
bb::UltraCircuitBuilder_::create_bool_gate
void create_bool_gate(const uint32_t a) override
Generate an arithmetic gate equivalent to x^2 - x = 0, which forces x to be 0 or 1.
Definition ultra_circuit_builder.cpp:558
bb::UltraCircuitBuilder_::create_ecc_add_gate
void create_ecc_add_gate(const ecc_add_gate_< FF > &in)
Create an elliptic curve addition gate.
Definition ultra_circuit_builder.cpp:628
bb::UltraCircuitBuilder_::finalize_circuit
void finalize_circuit(const bool ensure_nonzero)
Definition ultra_circuit_builder.cpp:29
bb::UltraCircuitBuilder_::create_sort_constraint
void create_sort_constraint(const std::vector< uint32_t > &variable_index)
Definition ultra_circuit_builder.cpp:1147
bb::UltraCircuitBuilder_::create_poly_gate
void create_poly_gate(const poly_triple_< FF > &in) override
A plonk gate with disabled (set to zero) fourth wire. q_m * a * b + q_1 * a + q_2 * b + q_3.
Definition ultra_circuit_builder.cpp:592
bb::UltraCircuitBuilder_::create_poseidon2_external_gate
void create_poseidon2_external_gate(const poseidon2_external_gate_< FF > &in)
Poseidon2 external round gate, activates the q_poseidon2_external selector and relation.
Definition ultra_circuit_builder.cpp:2396
bb::UltraCircuitBuilder_::evaluate_non_native_field_multiplication
std::array< uint32_t, 2 > evaluate_non_native_field_multiplication(const non_native_multiplication_witnesses< FF > &input)
Queue up non-native field multiplication data.
Definition ultra_circuit_builder.cpp:1743
bb::UltraCircuitBuilder_::populate_public_inputs_block
void populate_public_inputs_block()
Copy the public input idx data into the public inputs trace block.
Definition ultra_circuit_builder.cpp:1911
bb::UltraCircuitBuilder_::read_ROM_array
uint32_t read_ROM_array(const size_t rom_id, const uint32_t index_witness)
Read a single element from ROM.
Definition ultra_circuit_builder.cpp:2373
bb::UltraCircuitBuilder_::create_range_list
RangeList create_range_list(const uint64_t target_range)
Definition ultra_circuit_builder.cpp:870
bb::UltraCircuitBuilder_::put_constant_variable
uint32_t put_constant_variable(const FF &variable)
Definition ultra_circuit_builder.cpp:778
bb::UltraCircuitBuilder_::set_ROM_element
void set_ROM_element(const size_t rom_id, const size_t index_value, const uint32_t value_witness)
Initialize a rom cell to equal value_witness
Definition ultra_circuit_builder.cpp:2343
bb::UltraCircuitBuilder_::decompose_into_default_range_better_for_oddlimbnum
std::vector< uint32_t > decompose_into_default_range_better_for_oddlimbnum(const uint32_t variable_index, const size_t num_bits, std::string const &msg="decompose_into_default_range_better_for_oddlimbnum")
Definition ultra_circuit_builder.cpp:1280
bb::UltraCircuitBuilder_::create_mul_gate
void create_mul_gate(const mul_triple_< FF > &in) override
Create a multiplication gate with q_m * a * b + q_3 * c + q_const = 0.
Definition ultra_circuit_builder.cpp:527
bb::UltraCircuitBuilder_::write_RAM_array
void write_RAM_array(const size_t ram_id, const uint32_t index_witness, const uint32_t value_witness)
Definition ultra_circuit_builder.cpp:2321
bb::UltraCircuitBuilder_::create_dummy_constraints
void create_dummy_constraints(const std::vector< uint32_t > &variable_index)
Definition ultra_circuit_builder.cpp:1185
bb::UltraCircuitBuilder_::set_ROM_element_pair
void set_ROM_element_pair(const size_t rom_id, const size_t index_value, const std::array< uint32_t, 2 > &value_witnesses)
Initialize a ROM array element with a pair of witness values.
Definition ultra_circuit_builder.cpp:2358
bb::UltraCircuitBuilder_::read_ROM_array_pair
std::array< uint32_t, 2 > read_ROM_array_pair(const size_t rom_id, const uint32_t index_witness)
Read a pair of elements from ROM.
Definition ultra_circuit_builder.cpp:2386
bb::UltraCircuitBuilder_::NNF_SELECTORS
NNF_SELECTORS
Definition ultra_circuit_builder.hpp:79
bb::UltraCircuitBuilder_::queue_partial_non_native_field_multiplication
std::array< uint32_t, 2 > queue_partial_non_native_field_multiplication(const non_native_partial_multiplication_witnesses< FF > &input)
Definition ultra_circuit_builder.cpp:1971
bb::UltraCircuitBuilder_::evaluate_non_native_field_subtraction
std::array< uint32_t, 5 > evaluate_non_native_field_subtraction(add_simple limb0, add_simple limb1, add_simple limb2, add_simple limb3, std::tuple< uint32_t, uint32_t, FF > limbp)
Definition ultra_circuit_builder.cpp:2145
bb::UltraCircuitBuilder_::apply_memory_selectors
void apply_memory_selectors(const MEMORY_SELECTORS type)
Enable the memory gate of particular type.
Definition ultra_circuit_builder.cpp:1370
bb::UltraCircuitBuilder_::create_big_add_gate_with_bit_extraction
void create_big_add_gate_with_bit_extraction(const add_quad_< FF > &in)
A legacy method that was used to extract a bit from c-4d by using gate selectors in the Turboplonk,...
Definition ultra_circuit_builder.cpp:397
bb::UltraCircuitBuilder_::process_non_native_field_multiplications
void process_non_native_field_multiplications()
Called in compute_proving_key when finalizing circuit. Iterates over the cached_non_native_field_mult...
Definition ultra_circuit_builder.cpp:1930
bb::UltraCircuitBuilder_::create_new_range_constraint
void create_new_range_constraint(const uint32_t variable_index, const uint64_t target_range, std::string const msg="create_new_range_constraint")
Constrain a variable to a range.
Definition ultra_circuit_builder.cpp:1019
bb::group::curve_b
static constexpr Fq curve_b
Definition group.hpp:51
bb::numeric::uint256_t
Definition uint256.hpp:32
bb::numeric::uint256_t::data
uint64_t data[4]
Definition uint256.hpp:208
bb::numeric::uint256_t::slice
constexpr uint256_t slice(uint64_t start, uint64_t end) const
Definition uint256_impl.hpp:291
bb::numeric::uint256_t::get_msb
constexpr uint64_t get_msb() const
Definition uint256_impl.hpp:329
bb::plookup::ReadData
Container type for lookup table reads.
Definition types.hpp:418
bb::plookup::ReadData::lookup_entries
std::vector< BasicTable::LookupEntry > lookup_entries
Definition types.hpp:424
info
void info(Args... args)
Definition log.hpp:70
data
const std::vector< FF > data
Definition data_copy.test.cpp:61
a
FF a
Definition field_gt.test.cpp:51
b
FF b
Definition field_gt.test.cpp:52
buf
uint8_t const * buf
Definition data_store.hpp:9
buffer
uint8_t buffer[RANDOM_BUFFER_SIZE]
Definition engine.cpp:34
msgpack_impl.hpp
bb::plookup::get_lookup_accumulators
ReadData< bb::fr > get_lookup_accumulators(const MultiTableId id, const fr &key_a, const fr &key_b, const bool is_2_to_1_lookup)
Given a table ID and the key(s) for a key-value lookup, return the lookup accumulators.
Definition plookup_tables.cpp:173
bb::plookup::HONK_DUMMY_MULTI
@ HONK_DUMMY_MULTI
Definition types.hpp:132
bb::plookup::create_basic_table
BasicTable create_basic_table(const BasicTableId id, const size_t index)
Definition plookup_tables.cpp:258
bb::plookup::get_multitable
const MultiTable & get_multitable(const MultiTableId id)
Return the multitable with the provided ID; construct all MultiTables if not constructed already.
Definition plookup_tables.cpp:147
bb
Entry point for Barretenberg command-line interface.
Definition acir_format_getters.cpp:6
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:16
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
PROFILE_THIS_NAME
#define PROFILE_THIS_NAME(name)
Definition op_count.hpp:16
poseidon2_params.hpp
value
FF value
Definition public_data_tree.test.cpp:96
ref_vector.hpp
rom_ram_logic.hpp
bb::CircuitSchemaInternal
Serialized state of a circuit.
Definition circuit_builder_base.hpp:269
bb::CircuitSchemaInternal::selectors
std::vector< std::vector< std::vector< FF > > > selectors
Definition circuit_builder_base.hpp:274
bb::CircuitSchemaInternal::real_variable_index
std::vector< uint32_t > real_variable_index
Definition circuit_builder_base.hpp:276
bb::CircuitSchemaInternal::range_tags
std::unordered_map< uint32_t, uint64_t > range_tags
Definition circuit_builder_base.hpp:279
bb::CircuitSchemaInternal::vars_of_interest
std::unordered_map< uint32_t, std::string > vars_of_interest
Definition circuit_builder_base.hpp:272
bb::CircuitSchemaInternal::ram_states
std::vector< std::vector< uint32_t > > ram_states
Definition circuit_builder_base.hpp:283
bb::CircuitSchemaInternal::rom_states
std::vector< std::vector< std::array< uint32_t, 2 > > > rom_states
Definition circuit_builder_base.hpp:281
bb::CircuitSchemaInternal::ram_records
std::vector< std::vector< std::vector< uint32_t > > > ram_records
Definition circuit_builder_base.hpp:282
bb::CircuitSchemaInternal::rom_records
std::vector< std::vector< std::vector< uint32_t > > > rom_records
Definition circuit_builder_base.hpp:280
bb::CircuitSchemaInternal::lookup_tables
std::vector< std::vector< std::vector< FF > > > lookup_tables
Definition circuit_builder_base.hpp:277
bb::CircuitSchemaInternal::real_variable_tags
std::vector< uint32_t > real_variable_tags
Definition circuit_builder_base.hpp:278
bb::CircuitSchemaInternal::public_inps
std::vector< uint32_t > public_inps
Definition circuit_builder_base.hpp:271
bb::CircuitSchemaInternal::wires
std::vector< std::vector< std::vector< uint32_t > > > wires
Definition circuit_builder_base.hpp:275
bb::UltraCircuitBuilder_::RangeList
Definition ultra_circuit_builder.hpp:88
bb::UltraCircuitBuilder_::RangeList::range_tag
uint32_t range_tag
Definition ultra_circuit_builder.hpp:90
bb::UltraCircuitBuilder_::RangeList::target_range
uint64_t target_range
Definition ultra_circuit_builder.hpp:89
bb::UltraCircuitBuilder_::RangeList::tau_tag
uint32_t tau_tag
Definition ultra_circuit_builder.hpp:91
bb::UltraCircuitBuilder_::RangeList::variable_indices
std::vector< uint32_t > variable_indices
Definition ultra_circuit_builder.hpp:92
bb::UltraCircuitBuilder_::cached_partial_non_native_field_multiplication
Used to store instructions to create partial_non_native_field_multiplication gates....
Definition ultra_circuit_builder.hpp:105
bb::UltraCircuitBuilder_::cached_partial_non_native_field_multiplication::a
std::array< uint32_t, 4 > a
Definition ultra_circuit_builder.hpp:106
bb::add_quad_
Definition gate_data.hpp:26
bb::add_quad_::a
uint32_t a
Definition gate_data.hpp:27
bb::add_quad_::b
uint32_t b
Definition gate_data.hpp:28
bb::add_quad_::const_scaling
FF const_scaling
Definition gate_data.hpp:35
bb::add_quad_::a_scaling
FF a_scaling
Definition gate_data.hpp:31
bb::add_quad_::c_scaling
FF c_scaling
Definition gate_data.hpp:33
bb::add_quad_::d
uint32_t d
Definition gate_data.hpp:30
bb::add_quad_::b_scaling
FF b_scaling
Definition gate_data.hpp:32
bb::add_quad_::c
uint32_t c
Definition gate_data.hpp:29
bb::add_quad_::d_scaling
FF d_scaling
Definition gate_data.hpp:34
bb::add_triple_
Definition gate_data.hpp:16
bb::add_triple_::a
uint32_t a
Definition gate_data.hpp:17
bb::add_triple_::const_scaling
FF const_scaling
Definition gate_data.hpp:23
bb::add_triple_::b_scaling
FF b_scaling
Definition gate_data.hpp:21
bb::add_triple_::c_scaling
FF c_scaling
Definition gate_data.hpp:22
bb::add_triple_::c
uint32_t c
Definition gate_data.hpp:19
bb::add_triple_::a_scaling
FF a_scaling
Definition gate_data.hpp:20
bb::add_triple_::b
uint32_t b
Definition gate_data.hpp:18
bb::crypto::Poseidon2Bn254ScalarFieldParams::round_constants
static constexpr std::array< std::array< FF, t >, rounds_f+rounds_p > round_constants
Definition poseidon2_params.hpp:58
bb::ecc_add_gate_
Definition gate_data.hpp:127
bb::ecc_add_gate_::x1
uint32_t x1
Definition gate_data.hpp:128
bb::ecc_add_gate_::x2
uint32_t x2
Definition gate_data.hpp:130
bb::ecc_add_gate_::y2
uint32_t y2
Definition gate_data.hpp:131
bb::ecc_add_gate_::y1
uint32_t y1
Definition gate_data.hpp:129
bb::ecc_add_gate_::y3
uint32_t y3
Definition gate_data.hpp:133
bb::ecc_add_gate_::x3
uint32_t x3
Definition gate_data.hpp:132
bb::ecc_add_gate_::sign_coefficient
FF sign_coefficient
Definition gate_data.hpp:134
bb::ecc_dbl_gate_
Definition gate_data.hpp:136
bb::ecc_dbl_gate_::x1
uint32_t x1
Definition gate_data.hpp:137
bb::ecc_dbl_gate_::y1
uint32_t y1
Definition gate_data.hpp:138
bb::ecc_dbl_gate_::x3
uint32_t x3
Definition gate_data.hpp:139
bb::ecc_dbl_gate_::y3
uint32_t y3
Definition gate_data.hpp:140
bb::field< Bn254FrParams >::one
static constexpr field one()
Definition field_declarations.hpp:242
bb::field< Bn254FrParams >::modulus
static constexpr uint256_t modulus
Definition field_declarations.hpp:197
bb::field::to_montgomery_form
BB_INLINE constexpr field to_montgomery_form() const noexcept
Definition field_impl.hpp:283
bb::mul_quad_
Definition gate_data.hpp:37
bb::mul_quad_::b
uint32_t b
Definition gate_data.hpp:39
bb::mul_quad_::const_scaling
FF const_scaling
Definition gate_data.hpp:47
bb::mul_quad_::a
uint32_t a
Definition gate_data.hpp:38
bb::mul_quad_::mul_scaling
FF mul_scaling
Definition gate_data.hpp:42
bb::mul_quad_::c_scaling
FF c_scaling
Definition gate_data.hpp:45
bb::mul_quad_::d_scaling
FF d_scaling
Definition gate_data.hpp:46
bb::mul_quad_::d
uint32_t d
Definition gate_data.hpp:41
bb::mul_quad_::b_scaling
FF b_scaling
Definition gate_data.hpp:44
bb::mul_quad_::a_scaling
FF a_scaling
Definition gate_data.hpp:43
bb::mul_quad_::c
uint32_t c
Definition gate_data.hpp:40
bb::mul_triple_
Definition gate_data.hpp:49
bb::mul_triple_::const_scaling
FF const_scaling
Definition gate_data.hpp:55
bb::mul_triple_::c
uint32_t c
Definition gate_data.hpp:52
bb::mul_triple_::b
uint32_t b
Definition gate_data.hpp:51
bb::mul_triple_::a
uint32_t a
Definition gate_data.hpp:50
bb::mul_triple_::c_scaling
FF c_scaling
Definition gate_data.hpp:54
bb::mul_triple_::mul_scaling
FF mul_scaling
Definition gate_data.hpp:53
bb::non_native_multiplication_witnesses
Definition ultra_circuit_builder.hpp:26
bb::non_native_multiplication_witnesses::a
std::array< uint32_t, 4 > a
Definition ultra_circuit_builder.hpp:28
bb::non_native_multiplication_witnesses::q
std::array< uint32_t, 4 > q
Definition ultra_circuit_builder.hpp:30
bb::non_native_multiplication_witnesses::b
std::array< uint32_t, 4 > b
Definition ultra_circuit_builder.hpp:29
bb::non_native_multiplication_witnesses::r
std::array< uint32_t, 4 > r
Definition ultra_circuit_builder.hpp:31
bb::non_native_multiplication_witnesses::neg_modulus
std::array< FF, 4 > neg_modulus
Definition ultra_circuit_builder.hpp:32
bb::non_native_partial_multiplication_witnesses
Definition ultra_circuit_builder.hpp:35
bb::non_native_partial_multiplication_witnesses::b
std::array< uint32_t, 4 > b
Definition ultra_circuit_builder.hpp:38
bb::non_native_partial_multiplication_witnesses::a
std::array< uint32_t, 4 > a
Definition ultra_circuit_builder.hpp:37
bb::plookup::BasicTable
A basic table from which we can perform lookups (for example, an xor table)
Definition types.hpp:348
bb::poly_triple_
Definition gate_data.hpp:57
bb::poly_triple_::q_c
FF q_c
Definition gate_data.hpp:65
bb::poly_triple_::a
uint32_t a
Definition gate_data.hpp:58
bb::poly_triple_::c
uint32_t c
Definition gate_data.hpp:60
bb::poly_triple_::q_m
FF q_m
Definition gate_data.hpp:61
bb::poly_triple_::q_l
FF q_l
Definition gate_data.hpp:62
bb::poly_triple_::q_r
FF q_r
Definition gate_data.hpp:63
bb::poly_triple_::b
uint32_t b
Definition gate_data.hpp:59
bb::poly_triple_::q_o
FF q_o
Definition gate_data.hpp:64
bb::poseidon2_external_gate_
Definition gate_data.hpp:149
bb::poseidon2_external_gate_::a
uint32_t a
Definition gate_data.hpp:150
bb::poseidon2_external_gate_::d
uint32_t d
Definition gate_data.hpp:153
bb::poseidon2_external_gate_::round_idx
size_t round_idx
Definition gate_data.hpp:154
bb::poseidon2_external_gate_::c
uint32_t c
Definition gate_data.hpp:152
bb::poseidon2_external_gate_::b
uint32_t b
Definition gate_data.hpp:151
bb::poseidon2_internal_gate_
Definition gate_data.hpp:158
bb::poseidon2_internal_gate_::a
uint32_t a
Definition gate_data.hpp:159
bb::poseidon2_internal_gate_::d
uint32_t d
Definition gate_data.hpp:162
bb::poseidon2_internal_gate_::c
uint32_t c
Definition gate_data.hpp:161
bb::poseidon2_internal_gate_::round_idx
size_t round_idx
Definition gate_data.hpp:163
bb::poseidon2_internal_gate_::b
uint32_t b
Definition gate_data.hpp:160
ultra_circuit_builder.hpp