Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
relation_correctness.test.cpp
Go to the documentation of this file.
1#include "barretenberg/common/thread.hpp"
2#include "barretenberg/honk/library/grand_product_library.hpp"
3#include "barretenberg/honk/relation_checker.hpp"
4#include "barretenberg/translator_vm/translator_flavor.hpp"
5#include "barretenberg/translator_vm/translator_proving_key.hpp"
6
7#include <gtest/gtest.h>
8#include <set>
9using namespace bb;
10
11class TranslatorRelationCorrectnessTests : public ::testing::Test {
12 protected:
13 static void SetUpTestSuite() { bb::srs::init_file_crs_factory(bb::srs::bb_crs_path()); }
14};
15
21TEST_F(TranslatorRelationCorrectnessTests, TranslatorExtraRelationsCorrectness)
22{
23 using Flavor = TranslatorFlavor;
24 using FF = typename Flavor::FF;
25 using ProverPolynomials = typename Flavor::ProverPolynomials;
26
27 auto& engine = numeric::get_debug_randomness();
28
29 // We only use accumulated_result from relation parameters in this relation
30 RelationParameters<FF> params;
31 params.accumulated_result = {
32 FF::random_element(), FF::random_element(), FF::random_element(), FF::random_element()
33 };
34
35 // Create storage for polynomials
36 ProverPolynomials prover_polynomials;
37 constexpr size_t mini_circuit_size_without_masking = TranslatorProvingKey::dyadic_mini_circuit_size_without_masking;
38 // Fill in lagrange even and odd polynomials (only in first minicircuit, not the full concatenated circuit)
39 for (size_t i = Flavor::RESULT_ROW; i < mini_circuit_size_without_masking; i += 2) {
40 prover_polynomials.lagrange_even_in_minicircuit.at(i) = 1;
41 prover_polynomials.lagrange_odd_in_minicircuit.at(i + 1) = 1;
42 }
43 constexpr size_t NUMBER_OF_POSSIBLE_OPCODES = 3;
44 constexpr std::array<uint64_t, NUMBER_OF_POSSIBLE_OPCODES> possible_opcode_values = { 3, 4, 8 };
45
46 // Assign random opcode values
47 for (size_t i = Flavor::RESULT_ROW; i < mini_circuit_size_without_masking; i += 2) {
48 prover_polynomials.op.at(i) =
49 possible_opcode_values[static_cast<size_t>(engine.get_random_uint8() % NUMBER_OF_POSSIBLE_OPCODES)];
50 }
51
52 // Initialize used lagrange polynomials
53 prover_polynomials.lagrange_result_row.at(Flavor::RESULT_ROW) = 1;
54 prover_polynomials.lagrange_last_in_minicircuit.at(mini_circuit_size_without_masking - 1) = 1;
55
56 // Put random values in accumulator binary limbs (values should be preserved across even->next odd shift)
57 for (size_t i = Flavor::RESULT_ROW + 1; i < mini_circuit_size_without_masking - 1; i += 2) {
58 prover_polynomials.accumulators_binary_limbs_0.at(i) = FF ::random_element();
59 prover_polynomials.accumulators_binary_limbs_1.at(i) = FF ::random_element();
60 prover_polynomials.accumulators_binary_limbs_2.at(i) = FF ::random_element();
61 prover_polynomials.accumulators_binary_limbs_3.at(i) = FF ::random_element();
62 prover_polynomials.accumulators_binary_limbs_0.at(i + 1) = prover_polynomials.accumulators_binary_limbs_0[i];
63 prover_polynomials.accumulators_binary_limbs_2.at(i + 1) = prover_polynomials.accumulators_binary_limbs_2[i];
64 prover_polynomials.accumulators_binary_limbs_1.at(i + 1) = prover_polynomials.accumulators_binary_limbs_1[i];
65 prover_polynomials.accumulators_binary_limbs_3.at(i + 1) = prover_polynomials.accumulators_binary_limbs_3[i];
66 }
67
68 // The values of accumulator binary limbs at index 1 should equal the accumulated result from relation parameters
69 prover_polynomials.accumulators_binary_limbs_0.at(Flavor::RESULT_ROW) = params.accumulated_result[0];
70 prover_polynomials.accumulators_binary_limbs_1.at(Flavor::RESULT_ROW) = params.accumulated_result[1];
71 prover_polynomials.accumulators_binary_limbs_2.at(Flavor::RESULT_ROW) = params.accumulated_result[2];
72 prover_polynomials.accumulators_binary_limbs_3.at(Flavor::RESULT_ROW) = params.accumulated_result[3];
73
74 // Check that Opcode Constraint relation is satisfied across each row of the prover polynomials
75 auto translator_op_code_failures = RelationChecker<Flavor>::check<TranslatorOpcodeConstraintRelation<FF>>(
76 prover_polynomials, params, "TranslatorOpcodeConstraintRelation");
77 EXPECT_TRUE(translator_op_code_failures.empty());
78 // Check that Accumulator Transfer relation is satisfied across each row of the prover polynomials
79 auto translator_accumulator_transfer_failures =
80 RelationChecker<Flavor>::check<TranslatorAccumulatorTransferRelation<FF>>(
81 prover_polynomials, params, "TranslatorAccumulatorTransferRelation");
82 EXPECT_TRUE(translator_accumulator_transfer_failures.empty());
83 // Check that Zero Constraint relation is satisfied across each row of the prover polynomials
84 auto translator_zero_constraints_failures = RelationChecker<Flavor>::check<TranslatorZeroConstraintsRelation<FF>>(
85 prover_polynomials, params, "TranslatorZeroConstraintsRelation");
86 EXPECT_TRUE(translator_zero_constraints_failures.empty());
87}
92TEST_F(TranslatorRelationCorrectnessTests, Decomposition)
93{
94 using Flavor = TranslatorFlavor;
95 using FF = typename Flavor::FF;
96 using BF = typename Flavor::BF;
97 using ProverPolynomials = typename Flavor::ProverPolynomials;
98 auto& engine = numeric::get_debug_randomness();
99
100 constexpr size_t mini_circuit_size = Flavor::MINI_CIRCUIT_SIZE;
101
102 // Decomposition relation doesn't use any relation parameters
103 RelationParameters<FF> params;
104
105 // Create storage for polynomials
106 ProverPolynomials prover_polynomials;
107 constexpr size_t full_circuit_size = Flavor::MINI_CIRCUIT_SIZE * Flavor::CONCATENATION_GROUP_SIZE;
108
109 // Reallocate to start at index 0: the constructor allocates lagrange_odd starting at RESULT_ROW+1,
110 // but this test needs it filled from index 0 to cover the full decomposition check range.
111 prover_polynomials.lagrange_odd_in_minicircuit = typename Flavor::Polynomial(full_circuit_size);
112
113 // Fill in lagrange odd polynomial (the only non-witness one we are using)
114 for (size_t i = 0; i < full_circuit_size; i += 2) {
115 prover_polynomials.lagrange_odd_in_minicircuit.at(i) = 1;
116 }
117
118 constexpr size_t NUM_LIMB_BITS = Flavor::CircuitBuilder::NUM_LIMB_BITS;
119 constexpr size_t HIGH_WIDE_LIMB_WIDTH =
120 Flavor::CircuitBuilder::NUM_LIMB_BITS + Flavor::CircuitBuilder::NUM_LAST_LIMB_BITS;
121 constexpr size_t LOW_WIDE_LIMB_WIDTH = Flavor::CircuitBuilder::NUM_LIMB_BITS * 2;
122 constexpr size_t Z_LIMB_WIDTH = 128;
123 constexpr size_t MICRO_LIMB_WIDTH = Flavor::MICRO_LIMB_BITS;
124 constexpr size_t SHIFT_12_TO_14 = 4;
125 constexpr size_t SHIFT_10_TO_14 = 16;
126 constexpr size_t SHIFT_8_TO_14 = 64;
127 constexpr size_t SHIFT_4_TO_14 = 1024;
128
134 auto decompose_standard_limb =
135 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& limb_4, auto& shifted_limb) {
136 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
137 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
138 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
139 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
140 limb_4 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 4, MICRO_LIMB_WIDTH * 5);
141 shifted_limb = limb_4 * SHIFT_12_TO_14;
142 };
143
149 auto decompose_standard_top_limb =
150 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& shifted_limb) {
151 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
152 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
153 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
154 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
155 shifted_limb = limb_3 * SHIFT_8_TO_14;
156 };
157
163 auto decompose_standard_top_z_limb =
164 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& limb_4, auto& shifted_limb) {
165 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
166 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
167 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
168 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
169 limb_4 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 4, MICRO_LIMB_WIDTH * 5);
170 shifted_limb = limb_4 * SHIFT_4_TO_14;
171 };
172
178 auto decompose_top_quotient_limb =
179 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& shifted_limb) {
180 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
181 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
182 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
183 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
184 shifted_limb = limb_3 * SHIFT_10_TO_14;
185 };
186
191 auto decompose_relation_limb =
192 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& limb_4, auto& limb_5) {
193 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
194 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
195 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
196 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
197 limb_4 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 4, MICRO_LIMB_WIDTH * 5);
198 limb_5 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 5, MICRO_LIMB_WIDTH * 6);
199 };
200
201 // Put random values in all the non-interleaved constraint polynomials used to range constrain the values
202 for (size_t i = 1; i < mini_circuit_size - 1; i += 2) {
203 // P.x
204 prover_polynomials.x_lo_y_hi.at(i) =
205 FF(engine.get_random_uint256() & ((uint256_t(1) << LOW_WIDE_LIMB_WIDTH) - 1));
206 prover_polynomials.x_hi_z_1.at(i) =
207 FF(engine.get_random_uint256() & ((uint256_t(1) << HIGH_WIDE_LIMB_WIDTH) - 1));
208
209 // P.y
210 prover_polynomials.y_lo_z_2.at(i) =
211 FF(engine.get_random_uint256() & ((uint256_t(1) << LOW_WIDE_LIMB_WIDTH) - 1));
212 prover_polynomials.x_lo_y_hi.at(i + 1) =
213 FF(engine.get_random_uint256() & ((uint256_t(1) << HIGH_WIDE_LIMB_WIDTH) - 1));
214
215 // z1 and z2
216 prover_polynomials.x_hi_z_1.at(i + 1) = FF(engine.get_random_uint256() & ((uint256_t(1) << Z_LIMB_WIDTH) - 1));
217 prover_polynomials.y_lo_z_2.at(i + 1) = FF(engine.get_random_uint256() & ((uint256_t(1) << Z_LIMB_WIDTH) - 1));
218
219 // Slice P.x into chunks
220 prover_polynomials.p_x_low_limbs.at(i) = uint256_t(prover_polynomials.x_lo_y_hi.at(i)).slice(0, NUM_LIMB_BITS);
221 prover_polynomials.p_x_low_limbs.at(i + 1) =
222 uint256_t(prover_polynomials.x_lo_y_hi.at(i)).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
223 prover_polynomials.p_x_high_limbs.at(i) = uint256_t(prover_polynomials.x_hi_z_1[i]).slice(0, NUM_LIMB_BITS);
224 prover_polynomials.p_x_high_limbs.at(i + 1) =
225 uint256_t(prover_polynomials.x_hi_z_1.at(i)).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
226
227 // Slice P.y into chunks
228 prover_polynomials.p_y_low_limbs.at(i) = uint256_t(prover_polynomials.y_lo_z_2[i]).slice(0, NUM_LIMB_BITS);
229 prover_polynomials.p_y_low_limbs.at(i + 1) =
230 uint256_t(prover_polynomials.y_lo_z_2[i]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
231 prover_polynomials.p_y_high_limbs.at(i) =
232 uint256_t(prover_polynomials.x_lo_y_hi[i + 1]).slice(0, NUM_LIMB_BITS);
233 prover_polynomials.p_y_high_limbs.at(i + 1) =
234 uint256_t(prover_polynomials.x_lo_y_hi[i + 1]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
235
236 // Slice z1 and z2 into chunks
237 prover_polynomials.z_low_limbs.at(i) = uint256_t(prover_polynomials.x_hi_z_1[i + 1]).slice(0, NUM_LIMB_BITS);
238 prover_polynomials.z_low_limbs.at(i + 1) =
239 uint256_t(prover_polynomials.y_lo_z_2[i + 1]).slice(0, NUM_LIMB_BITS);
240 prover_polynomials.z_high_limbs.at(i) =
241 uint256_t(prover_polynomials.x_hi_z_1[i + 1]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
242 prover_polynomials.z_high_limbs.at(i + 1) =
243 uint256_t(prover_polynomials.y_lo_z_2[i + 1]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
244
245 // Slice accumulator
246 auto tmp = uint256_t(BF::random_element(&engine));
247 prover_polynomials.accumulators_binary_limbs_0.at(i) = tmp.slice(0, NUM_LIMB_BITS);
248 prover_polynomials.accumulators_binary_limbs_1.at(i) = tmp.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2);
249 prover_polynomials.accumulators_binary_limbs_2.at(i) = tmp.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3);
250 prover_polynomials.accumulators_binary_limbs_3.at(i) = tmp.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4);
251
252 // Slice low limbs of P.x into range constraint microlimbs
253 decompose_standard_limb(prover_polynomials.p_x_low_limbs.at(i),
254 prover_polynomials.p_x_low_limbs_range_constraint_0.at(i),
255 prover_polynomials.p_x_low_limbs_range_constraint_1.at(i),
256 prover_polynomials.p_x_low_limbs_range_constraint_2.at(i),
257 prover_polynomials.p_x_low_limbs_range_constraint_3.at(i),
258 prover_polynomials.p_x_low_limbs_range_constraint_4.at(i),
259 prover_polynomials.p_x_low_limbs_range_constraint_tail.at(i));
260
261 decompose_standard_limb(prover_polynomials.p_x_low_limbs.at(i + 1),
262 prover_polynomials.p_x_low_limbs_range_constraint_0.at(i + 1),
263 prover_polynomials.p_x_low_limbs_range_constraint_1.at(i + 1),
264 prover_polynomials.p_x_low_limbs_range_constraint_2.at(i + 1),
265 prover_polynomials.p_x_low_limbs_range_constraint_3.at(i + 1),
266 prover_polynomials.p_x_low_limbs_range_constraint_4.at(i + 1),
267 prover_polynomials.p_x_low_limbs_range_constraint_tail.at(i + 1));
268
269 // Slice high limbs of P.x into range constraint microlimbs
270 decompose_standard_limb(prover_polynomials.p_x_high_limbs.at(i),
271 prover_polynomials.p_x_high_limbs_range_constraint_0.at(i),
272 prover_polynomials.p_x_high_limbs_range_constraint_1.at(i),
273 prover_polynomials.p_x_high_limbs_range_constraint_2.at(i),
274 prover_polynomials.p_x_high_limbs_range_constraint_3.at(i),
275 prover_polynomials.p_x_high_limbs_range_constraint_4.at(i),
276 prover_polynomials.p_x_high_limbs_range_constraint_tail.at(i));
277
278 decompose_standard_top_limb(prover_polynomials.p_x_high_limbs.at(i + 1),
279 prover_polynomials.p_x_high_limbs_range_constraint_0.at(i + 1),
280 prover_polynomials.p_x_high_limbs_range_constraint_1.at(i + 1),
281 prover_polynomials.p_x_high_limbs_range_constraint_2.at(i + 1),
282 prover_polynomials.p_x_high_limbs_range_constraint_3.at(i + 1),
283 prover_polynomials.p_x_high_limbs_range_constraint_4.at(i + 1));
284
285 // Slice low limbs of P.y into range constraint microlimbs
286 decompose_standard_limb(prover_polynomials.p_y_low_limbs.at(i),
287 prover_polynomials.p_y_low_limbs_range_constraint_0.at(i),
288 prover_polynomials.p_y_low_limbs_range_constraint_1.at(i),
289 prover_polynomials.p_y_low_limbs_range_constraint_2.at(i),
290 prover_polynomials.p_y_low_limbs_range_constraint_3.at(i),
291 prover_polynomials.p_y_low_limbs_range_constraint_4.at(i),
292 prover_polynomials.p_y_low_limbs_range_constraint_tail.at(i));
293
294 decompose_standard_limb(prover_polynomials.p_y_low_limbs.at(i + 1),
295 prover_polynomials.p_y_low_limbs_range_constraint_0.at(i + 1),
296 prover_polynomials.p_y_low_limbs_range_constraint_1.at(i + 1),
297 prover_polynomials.p_y_low_limbs_range_constraint_2.at(i + 1),
298 prover_polynomials.p_y_low_limbs_range_constraint_3.at(i + 1),
299 prover_polynomials.p_y_low_limbs_range_constraint_4.at(i + 1),
300 prover_polynomials.p_y_low_limbs_range_constraint_tail.at(i + 1));
301
302 // Slice high limbs of P.y into range constraint microlimbs
303 decompose_standard_limb(prover_polynomials.p_y_high_limbs.at(i),
304 prover_polynomials.p_y_high_limbs_range_constraint_0.at(i),
305 prover_polynomials.p_y_high_limbs_range_constraint_1.at(i),
306 prover_polynomials.p_y_high_limbs_range_constraint_2.at(i),
307 prover_polynomials.p_y_high_limbs_range_constraint_3.at(i),
308 prover_polynomials.p_y_high_limbs_range_constraint_4.at(i),
309 prover_polynomials.p_y_high_limbs_range_constraint_tail.at(i));
310
311 decompose_standard_top_limb(prover_polynomials.p_y_high_limbs.at(i + 1),
312 prover_polynomials.p_y_high_limbs_range_constraint_0.at(i + 1),
313 prover_polynomials.p_y_high_limbs_range_constraint_1.at(i + 1),
314 prover_polynomials.p_y_high_limbs_range_constraint_2.at(i + 1),
315 prover_polynomials.p_y_high_limbs_range_constraint_3.at(i + 1),
316 prover_polynomials.p_y_high_limbs_range_constraint_4.at(i + 1));
317
318 // Slice low limb of of z1 and z2 into range constraints
319 decompose_standard_limb(prover_polynomials.z_low_limbs.at(i),
320 prover_polynomials.z_low_limbs_range_constraint_0.at(i),
321 prover_polynomials.z_low_limbs_range_constraint_1.at(i),
322 prover_polynomials.z_low_limbs_range_constraint_2.at(i),
323 prover_polynomials.z_low_limbs_range_constraint_3.at(i),
324 prover_polynomials.z_low_limbs_range_constraint_4.at(i),
325 prover_polynomials.z_low_limbs_range_constraint_tail.at(i));
326
327 decompose_standard_limb(prover_polynomials.z_low_limbs.at(i + 1),
328 prover_polynomials.z_low_limbs_range_constraint_0.at(i + 1),
329 prover_polynomials.z_low_limbs_range_constraint_1.at(i + 1),
330 prover_polynomials.z_low_limbs_range_constraint_2.at(i + 1),
331 prover_polynomials.z_low_limbs_range_constraint_3.at(i + 1),
332 prover_polynomials.z_low_limbs_range_constraint_4.at(i + 1),
333 prover_polynomials.z_low_limbs_range_constraint_tail.at(i + 1));
334
335 // Slice high limb of of z1 and z2 into range constraints
336 decompose_standard_top_z_limb(prover_polynomials.z_high_limbs.at(i),
337 prover_polynomials.z_high_limbs_range_constraint_0.at(i),
338 prover_polynomials.z_high_limbs_range_constraint_1.at(i),
339 prover_polynomials.z_high_limbs_range_constraint_2.at(i),
340 prover_polynomials.z_high_limbs_range_constraint_3.at(i),
341 prover_polynomials.z_high_limbs_range_constraint_4.at(i),
342 prover_polynomials.z_high_limbs_range_constraint_tail.at(i));
343
344 decompose_standard_top_z_limb(prover_polynomials.z_high_limbs.at(i + 1),
345 prover_polynomials.z_high_limbs_range_constraint_0.at(i + 1),
346 prover_polynomials.z_high_limbs_range_constraint_1.at(i + 1),
347 prover_polynomials.z_high_limbs_range_constraint_2.at(i + 1),
348 prover_polynomials.z_high_limbs_range_constraint_3.at(i + 1),
349 prover_polynomials.z_high_limbs_range_constraint_4.at(i + 1),
350 prover_polynomials.z_high_limbs_range_constraint_tail.at(i + 1));
351
352 // Slice accumulator limbs into range constraints
353 decompose_standard_limb(prover_polynomials.accumulators_binary_limbs_0.at(i),
354 prover_polynomials.accumulator_low_limbs_range_constraint_0.at(i),
355 prover_polynomials.accumulator_low_limbs_range_constraint_1.at(i),
356 prover_polynomials.accumulator_low_limbs_range_constraint_2.at(i),
357 prover_polynomials.accumulator_low_limbs_range_constraint_3.at(i),
358 prover_polynomials.accumulator_low_limbs_range_constraint_4.at(i),
359 prover_polynomials.accumulator_low_limbs_range_constraint_tail.at(i));
360 decompose_standard_limb(prover_polynomials.accumulators_binary_limbs_1.at(i),
361 prover_polynomials.accumulator_low_limbs_range_constraint_0.at(i + 1),
362 prover_polynomials.accumulator_low_limbs_range_constraint_1.at(i + 1),
363 prover_polynomials.accumulator_low_limbs_range_constraint_2.at(i + 1),
364 prover_polynomials.accumulator_low_limbs_range_constraint_3.at(i + 1),
365 prover_polynomials.accumulator_low_limbs_range_constraint_4.at(i + 1),
366 prover_polynomials.accumulator_low_limbs_range_constraint_tail.at(i + 1));
367
368 decompose_standard_limb(prover_polynomials.accumulators_binary_limbs_2.at(i),
369 prover_polynomials.accumulator_high_limbs_range_constraint_0.at(i),
370 prover_polynomials.accumulator_high_limbs_range_constraint_1.at(i),
371 prover_polynomials.accumulator_high_limbs_range_constraint_2.at(i),
372 prover_polynomials.accumulator_high_limbs_range_constraint_3.at(i),
373 prover_polynomials.accumulator_high_limbs_range_constraint_4.at(i),
374 prover_polynomials.accumulator_high_limbs_range_constraint_tail.at(i));
375 decompose_standard_top_limb(prover_polynomials.accumulators_binary_limbs_3.at(i),
376 prover_polynomials.accumulator_high_limbs_range_constraint_0.at(i + 1),
377 prover_polynomials.accumulator_high_limbs_range_constraint_1.at(i + 1),
378 prover_polynomials.accumulator_high_limbs_range_constraint_2.at(i + 1),
379 prover_polynomials.accumulator_high_limbs_range_constraint_3.at(i + 1),
380 prover_polynomials.accumulator_high_limbs_range_constraint_4.at(i + 1));
381
382 // Slice quotient limbs into range constraints
383 decompose_standard_limb(prover_polynomials.quotient_low_binary_limbs.at(i),
384 prover_polynomials.quotient_low_limbs_range_constraint_0.at(i),
385 prover_polynomials.quotient_low_limbs_range_constraint_1.at(i),
386 prover_polynomials.quotient_low_limbs_range_constraint_2.at(i),
387 prover_polynomials.quotient_low_limbs_range_constraint_3.at(i),
388 prover_polynomials.quotient_low_limbs_range_constraint_4.at(i),
389 prover_polynomials.quotient_low_limbs_range_constraint_tail.at(i));
390 decompose_standard_limb(prover_polynomials.quotient_low_binary_limbs_shift.at(i),
391 prover_polynomials.quotient_low_limbs_range_constraint_0.at(i + 1),
392 prover_polynomials.quotient_low_limbs_range_constraint_1.at(i + 1),
393 prover_polynomials.quotient_low_limbs_range_constraint_2.at(i + 1),
394 prover_polynomials.quotient_low_limbs_range_constraint_3.at(i + 1),
395 prover_polynomials.quotient_low_limbs_range_constraint_4.at(i + 1),
396 prover_polynomials.quotient_low_limbs_range_constraint_tail.at(i + 1));
397
398 decompose_standard_limb(prover_polynomials.quotient_high_binary_limbs.at(i),
399 prover_polynomials.quotient_high_limbs_range_constraint_0.at(i),
400 prover_polynomials.quotient_high_limbs_range_constraint_1.at(i),
401 prover_polynomials.quotient_high_limbs_range_constraint_2.at(i),
402 prover_polynomials.quotient_high_limbs_range_constraint_3.at(i),
403 prover_polynomials.quotient_high_limbs_range_constraint_4.at(i),
404 prover_polynomials.quotient_high_limbs_range_constraint_tail.at(i));
405
406 decompose_top_quotient_limb(prover_polynomials.quotient_high_binary_limbs_shift.at(i),
407 prover_polynomials.quotient_high_limbs_range_constraint_0.at(i + 1),
408 prover_polynomials.quotient_high_limbs_range_constraint_1.at(i + 1),
409 prover_polynomials.quotient_high_limbs_range_constraint_2.at(i + 1),
410 prover_polynomials.quotient_high_limbs_range_constraint_3.at(i + 1),
411 prover_polynomials.quotient_high_limbs_range_constraint_4.at(i + 1));
412
413 // Decompose wide relation limbs into range constraints
414 decompose_relation_limb(prover_polynomials.relation_wide_limbs.at(i),
415 prover_polynomials.relation_wide_limbs_range_constraint_0.at(i),
416 prover_polynomials.relation_wide_limbs_range_constraint_1.at(i),
417 prover_polynomials.relation_wide_limbs_range_constraint_2.at(i),
418 prover_polynomials.relation_wide_limbs_range_constraint_3.at(i),
419 prover_polynomials.p_x_high_limbs_range_constraint_tail.at(i + 1),
420 prover_polynomials.accumulator_high_limbs_range_constraint_tail.at(i + 1));
421
422 decompose_relation_limb(prover_polynomials.relation_wide_limbs.at(i + 1),
423 prover_polynomials.relation_wide_limbs_range_constraint_0.at(i + 1),
424 prover_polynomials.relation_wide_limbs_range_constraint_1.at(i + 1),
425 prover_polynomials.relation_wide_limbs_range_constraint_2.at(i + 1),
426 prover_polynomials.relation_wide_limbs_range_constraint_3.at(i + 1),
427 prover_polynomials.p_y_high_limbs_range_constraint_tail.at(i + 1),
428 prover_polynomials.quotient_high_limbs_range_constraint_tail.at(i + 1));
429 }
430
431 // Check that Decomposition relation is satisfied across each row of the prover polynomials
432 RelationChecker<Flavor>::check<TranslatorDecompositionRelation<FF>>(
433 prover_polynomials, params, "TranslatorDecompositionRelation");
434}
435
440TEST_F(TranslatorRelationCorrectnessTests, NonNative)
441{
442 using Flavor = TranslatorFlavor;
443 using Builder = Flavor::CircuitBuilder;
444 using FF = typename Flavor::FF;
445 using BF = typename Flavor::BF;
446 using ProverPolynomials = typename Flavor::ProverPolynomials;
447 using GroupElement = typename Flavor::GroupElement;
448
449 constexpr size_t NUM_LIMB_BITS = Flavor::NUM_LIMB_BITS;
450 constexpr size_t mini_circuit_size = TranslatorFlavor::MINI_CIRCUIT_SIZE;
451 constexpr size_t mini_circuit_size_without_masking =
452 TranslatorFlavor::MINI_CIRCUIT_SIZE - TranslatorFlavor::NUM_MASKED_ROWS_END;
453
454 auto& engine = numeric::get_debug_randomness();
455
456 auto op_queue = std::make_shared<bb::ECCOpQueue>();
457 op_queue->no_op_ultra_only();
458 op_queue->random_op_ultra_only();
459 op_queue->random_op_ultra_only();
460 op_queue->random_op_ultra_only();
461
462 // Generate random EccOpQueue actions
463
464 for (size_t i = 0; i < (mini_circuit_size >> 1) / 2; i++) {
465 switch (engine.get_random_uint8() & 3) {
466 case 0:
467 op_queue->no_op_ultra_only();
468 break;
469 case 1:
470 op_queue->eq_and_reset();
471 break;
472 case 2:
473 op_queue->add_accumulate(GroupElement::random_element(&engine));
474 break;
475 case 3:
476 op_queue->mul_accumulate(GroupElement::random_element(&engine), FF::random_element(&engine));
477 break;
478 }
479 }
480 op_queue->merge();
481 for (size_t i = 0; i < 100; i++) {
482 switch (engine.get_random_uint8() & 3) {
483 case 0:
484 op_queue->no_op_ultra_only();
485 break;
486 case 1:
487 op_queue->eq_and_reset();
488 break;
489 case 2:
490 op_queue->add_accumulate(GroupElement::random_element(&engine));
491 break;
492 case 3:
493 op_queue->mul_accumulate(GroupElement::random_element(&engine), FF::random_element(&engine));
494 break;
495 }
496 }
497 op_queue->random_op_ultra_only();
498 op_queue->random_op_ultra_only();
499 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
500
501 const auto batching_challenge_v = BF::random_element(&engine);
502 const auto evaluation_input_x = BF::random_element(&engine);
503
504 // Generating all the values is pretty tedious, so just use CircuitBuilder
505 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge_v, evaluation_input_x, op_queue);
506
507 // The non-native field relation uses limbs of evaluation_input_x and powers of batching_challenge_v as inputs
508 RelationParameters<FF> params;
509 auto v_power = BF::one();
510 for (size_t i = 0; i < 4 /*Number of powers of v that we need {1,2,3,4}*/; i++) {
511 v_power *= batching_challenge_v;
512 auto uint_v_power = uint256_t(v_power);
513 params.batching_challenge_v.at(i) = { uint_v_power.slice(0, NUM_LIMB_BITS),
514 uint_v_power.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
515 uint_v_power.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
516 uint_v_power.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
517 uint_v_power };
518 }
519 auto uint_input_x = uint256_t(evaluation_input_x);
520 params.evaluation_input_x = { uint_input_x.slice(0, NUM_LIMB_BITS),
521 uint_input_x.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
522 uint_input_x.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
523 uint_input_x.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
524 uint_input_x };
525
526 // Create storage for polynomials
527 ProverPolynomials prover_polynomials = TranslatorFlavor::ProverPolynomials();
528 // Copy values of wires used in the non-native field relation from the circuit builder
529 for (size_t i = Builder::NUM_NO_OPS_START + Builder::NUM_RANDOM_OPS_START;
530 i < circuit_builder.num_gates() - Builder::NUM_RANDOM_OPS_END;
531 i++) {
532 prover_polynomials.op.at(i) = circuit_builder.get_variable(circuit_builder.wires[circuit_builder.OP][i]);
533 prover_polynomials.p_x_low_limbs.at(i) =
534 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_X_LOW_LIMBS][i]);
535 prover_polynomials.p_x_high_limbs.at(i) =
536 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_X_HIGH_LIMBS][i]);
537 prover_polynomials.p_y_low_limbs.at(i) =
538 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_Y_LOW_LIMBS][i]);
539 prover_polynomials.p_y_high_limbs.at(i) =
540 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_Y_HIGH_LIMBS][i]);
541 prover_polynomials.z_low_limbs.at(i) =
542 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.Z_LOW_LIMBS][i]);
543 prover_polynomials.z_high_limbs.at(i) =
544 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.Z_HIGH_LIMBS][i]);
545 prover_polynomials.accumulators_binary_limbs_0.at(i) =
546 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_0][i]);
547 prover_polynomials.accumulators_binary_limbs_1.at(i) =
548 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_1][i]);
549 prover_polynomials.accumulators_binary_limbs_2.at(i) =
550 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_2][i]);
551 prover_polynomials.accumulators_binary_limbs_3.at(i) =
552 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_3][i]);
553 prover_polynomials.quotient_low_binary_limbs.at(i) =
554 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.QUOTIENT_LOW_BINARY_LIMBS][i]);
555 prover_polynomials.quotient_high_binary_limbs.at(i) =
556 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.QUOTIENT_HIGH_BINARY_LIMBS][i]);
557 prover_polynomials.relation_wide_limbs.at(i) =
558 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.RELATION_WIDE_LIMBS][i]);
559 }
560
561 // Fill in lagrange odd polynomial
562 for (size_t i = Flavor::RESULT_ROW; i < mini_circuit_size_without_masking; i += 2) {
563 prover_polynomials.lagrange_even_in_minicircuit.at(i) = 1;
564 prover_polynomials.lagrange_odd_in_minicircuit.at(i + 1) = 1;
565 }
566
567 // Check that Non-Native Field relation is satisfied across each row of the prover polynomials
568 RelationChecker<Flavor>::check<TranslatorNonNativeFieldRelation<FF>>(
569 prover_polynomials, params, "TranslatorNonNativeFieldRelation");
570}
571
572TEST_F(TranslatorRelationCorrectnessTests, ZeroKnowledgePermutation)
573{
574 using Flavor = TranslatorFlavor;
575 using FF = typename Flavor::FF;
576 using ProverPolynomials = typename Flavor::ProverPolynomials;
577
578 auto& engine = numeric::get_debug_randomness();
579
580 TranslatorProvingKey key{};
581 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
582 ProverPolynomials& prover_polynomials = key.proving_key->polynomials;
583
584 // Fill required relation parameters
585 RelationParameters<FF> params{ .beta = FF::random_element(), .gamma = FF::random_element() };
586
587 // Populate the group polynomials with appropriate values and also enough random values to mask their commitment
588 // and evaluation
589 auto fill_polynomial_with_random_14_bit_values = [&](auto& polynomial) {
590 for (size_t i = polynomial.start_index(); i < polynomial.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; i++) {
591 polynomial.at(i) = engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1);
592 }
593 for (size_t i = polynomial.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; i < polynomial.end_index(); i++) {
594 polynomial.at(i) = FF::random_element();
595 }
596 };
597
598 for (const auto& group : prover_polynomials.get_groups_to_be_concatenated()) {
599 for (auto& poly : group) {
600 // Skip null padding slots (empty zero polynomials in group 4)
601 if (poly.is_empty()) {
602 continue;
603 }
604 fill_polynomial_with_random_14_bit_values(poly);
605 }
606 }
607
608 key.compute_lagrange_polynomials();
609 key.compute_concatenated_polynomials();
610 key.compute_extra_range_constraint_numerator();
611 key.compute_translator_range_constraint_ordered_polynomials();
612
613 // Compute the grand product polynomial
614 compute_grand_product<Flavor, bb::TranslatorPermutationRelation<FF>>(prover_polynomials, params);
615
616 // Check that permutation relation is satisfied across each row of the prover polynomials
617 auto perm_failures = RelationChecker<Flavor>::check<TranslatorPermutationRelation<FF>>(
618 prover_polynomials, params, "TranslatorPermutationRelation");
619 EXPECT_TRUE(perm_failures.empty());
620 auto delta_failures = RelationChecker<Flavor>::check<TranslatorDeltaRangeConstraintRelation<FF>>(
621 prover_polynomials, params, "TranslatorDeltaRangeConstraintRelation");
622 EXPECT_TRUE(delta_failures.empty());
623}
624
625TEST_F(TranslatorRelationCorrectnessTests, ZeroKnowledgeDeltaRange)
626{
627 using Flavor = TranslatorFlavor;
628 using FF = typename Flavor::FF;
629 using ProverPolynomials = typename Flavor::ProverPolynomials;
630 auto& engine = numeric::get_debug_randomness();
631
632 TranslatorProvingKey key;
633 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
634 ProverPolynomials& prover_polynomials = key.proving_key->polynomials;
635
636 const size_t dyadic_circuit_size_without_masking = TranslatorProvingKey::dyadic_circuit_size_without_masking;
637
638 key.compute_lagrange_polynomials();
639
640 // Create a vector and fill with necessary steps for the DeltaRangeConstraint relation
641 auto sorted_steps = TranslatorProvingKey::get_sorted_steps();
642 std::vector<uint64_t> vector_for_sorting(sorted_steps.begin(), sorted_steps.end());
643
644 // Add random values in the appropriate range to fill the leftover space (before masking region)
645 for (size_t i = sorted_steps.size();
646 i < prover_polynomials.ordered_range_constraints_0.size() - Flavor::MAX_RANDOM_VALUES_PER_ORDERED;
647 i++) {
648 vector_for_sorting.emplace_back(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
649 }
650
651 // Get ordered polynomials
652 auto polynomial_pointers = std::vector{ &prover_polynomials.ordered_range_constraints_0,
653 &prover_polynomials.ordered_range_constraints_1,
654 &prover_polynomials.ordered_range_constraints_2,
655 &prover_polynomials.ordered_range_constraints_3,
656 &prover_polynomials.ordered_range_constraints_4 };
657
658 std::sort(vector_for_sorting.begin(), vector_for_sorting.end());
659
660 // Add masking values
661 for (size_t i = dyadic_circuit_size_without_masking; i < key.dyadic_circuit_size; i++) {
662 vector_for_sorting.emplace_back(FF::random_element());
663 }
664
665 // Copy values, transforming them into Finite Field elements
666 std::transform(vector_for_sorting.cbegin(),
667 vector_for_sorting.cend(),
668 prover_polynomials.ordered_range_constraints_0.coeffs().begin(),
669 [](uint64_t in) { return FF(in); });
670
671 // Copy the same polynomial into the 4 other ordered polynomials (they are not the same in an actual proof, but
672 // we only need to check the correctness of the relation and it acts independently on each polynomial)
673 for (size_t i = 0; i < 4; ++i) {
674 std::copy(prover_polynomials.ordered_range_constraints_0.coeffs().begin(),
675 prover_polynomials.ordered_range_constraints_0.coeffs().end(),
676 polynomial_pointers[i + 1]->coeffs().begin());
677 }
678
679 // Check that DeltaRangeConstraint relation is satisfied across each row of the prover polynomials
680 auto delta_range_failures = RelationChecker<Flavor>::check<TranslatorDeltaRangeConstraintRelation<FF>>(
681 prover_polynomials, RelationParameters<FF>(), "TranslatorDeltaRangeConstraintRelation");
682 EXPECT_TRUE(delta_range_failures.empty());
683}
684
691TEST_F(TranslatorRelationCorrectnessTests, ConcatenatedPolynomialLayout)
692{
693 using Flavor = TranslatorFlavor;
694 using FF = typename Flavor::FF;
695
696 auto& engine = numeric::get_debug_randomness();
697
698 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
699
700 TranslatorProvingKey key{};
701 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
702 auto& pp = key.proving_key->polynomials;
703
704 // Fill group wire polynomials with deterministic 14-bit values in circuit region, random values in masking rows
705 auto groups = pp.get_groups_to_be_concatenated();
706 for (size_t i = 0; i < groups.size(); i++) {
707 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
708 auto& poly = groups[i][j];
709 if (poly.is_empty()) {
710 continue;
711 }
712 // Fill circuit region with deterministic 14-bit values
713 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
714 poly.at(k) = FF(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
715 }
716 // Fill masking rows with random FF values
717 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
718 poly.at(k) = FF::random_element();
719 }
720 }
721 }
722
723 key.compute_concatenated_polynomials();
724
725 auto concatenated = pp.get_concatenated();
726
727 // Re-fetch groups (they are RefVectors, so point to same data)
728 auto groups_after = pp.get_groups_to_be_concatenated();
729
730 for (size_t i = 0; i < groups_after.size(); i++) {
731 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
732 auto& poly = groups_after[i][j];
733
734 // Null padding slots in group 4 (lanes 13-15): all positions should be zero
735 if (i == 4 && j >= 13) {
736 for (size_t k = 0; k < MINI; k++) {
737 EXPECT_EQ(concatenated[i][j * MINI + k], FF(0))
738 << "Null padding not zero at group=" << i << " lane=" << j << " row=" << k;
739 }
740 continue;
741 }
742
743 // Position 0 in each block should be zero (below start_index=1)
744 EXPECT_EQ(concatenated[i][j * MINI + 0], FF(0)) << "Position 0 not zero at group=" << i << " lane=" << j;
745
746 // Non-zero region: values should match original wire values
747 for (size_t k = poly.start_index(); k < poly.end_index(); k++) {
748 EXPECT_EQ(concatenated[i][j * MINI + k], poly[k])
749 << "Mismatch at group=" << i << " lane=" << j << " row=" << k;
750 }
751 }
752 }
753}
754
761TEST_F(TranslatorRelationCorrectnessTests, RandomnessRedistributionIntegrity)
762{
763 using Flavor = TranslatorFlavor;
764 using FF = typename Flavor::FF;
765
766 auto& engine = numeric::get_debug_randomness();
767
768 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
769 constexpr size_t full_circuit_size = MINI * Flavor::CONCATENATION_GROUP_SIZE;
770
771 TranslatorProvingKey key{};
772 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
773 auto& pp = key.proving_key->polynomials;
774
775 // Fill group wire polynomials
776 for (const auto& group : pp.get_groups_to_be_concatenated()) {
777 for (auto& poly : group) {
778 if (poly.is_empty()) {
779 continue;
780 }
781 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
782 poly.at(k) = FF(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
783 }
784 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
785 poly.at(k) = FF::random_element();
786 }
787 }
788 }
789
790 key.compute_concatenated_polynomials();
791 key.compute_extra_range_constraint_numerator();
792
793 // Collect random values from scattered masking positions in concatenated[0..3] BEFORE redistribution
794 auto concatenated = pp.get_concatenated();
795 std::multiset<uint256_t> random_values_from_concat;
796 for (size_t i = 0; i < 4; i++) { // Only first 4 (range constraint) concatenated polys
797 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
798 size_t block_masking_start = j * MINI + (MINI - NUM_DISABLED_ROWS_IN_SUMCHECK);
799 size_t block_masking_end = j * MINI + MINI;
800 for (size_t k = block_masking_start; k < block_masking_end; k++) {
801 random_values_from_concat.insert(uint256_t(concatenated[i][k]));
802 }
803 }
804 }
805
806 // Total expected: 4 concat polys * 16 blocks * NUM_DISABLED_ROWS_IN_SUMCHECK rows
807 const size_t expected_total = 4 * Flavor::CONCATENATION_GROUP_SIZE * NUM_DISABLED_ROWS_IN_SUMCHECK;
808 EXPECT_EQ(random_values_from_concat.size(), expected_total);
809
810 // Now compute ordered polynomials (which calls split_concatenated_random_coefficients_to_ordered)
811 key.compute_translator_range_constraint_ordered_polynomials();
812
813 // Collect random values from contiguous masking region at end of ordered polys.
814 // The random values from the 4 concatenated polys (4*16*4 = 256 values) are redistributed across 5 ordered polys,
815 // with each ordered poly getting at most MAX_RANDOM_VALUES_PER_ORDERED positions. Not all positions may be filled,
816 // so we collect only non-padding (non-zero) values. Since random FF elements are zero with negligible probability
817 // (1/p), this is safe.
818 auto ordered = pp.get_ordered_range_constraints();
819 std::multiset<uint256_t> random_values_from_ordered;
820 for (size_t i = 0; i < ordered.size(); i++) {
821 for (size_t pos = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED; pos < full_circuit_size; pos++) {
822 FF val = ordered[i][pos];
823 if (val != FF(0)) {
824 random_values_from_ordered.insert(uint256_t(val));
825 }
826 }
827 }
828
829 // The multisets should be equal (same values with same multiplicities)
830 EXPECT_EQ(random_values_from_concat, random_values_from_ordered);
831
832 // Verify non-masking region of ordered polys has values in [0, 16383]
833 const size_t max_range_value = (1 << Flavor::MICRO_LIMB_BITS) - 1;
834 for (size_t i = 0; i < ordered.size(); i++) {
835 for (size_t pos = 1; pos < full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED; pos++) {
836 uint256_t val = uint256_t(ordered[i][pos]);
837 EXPECT_LE(val, max_range_value) << "Out-of-range value in ordered poly " << i << " at position " << pos;
838 }
839 }
840}
841
847TEST_F(TranslatorRelationCorrectnessTests, BlockBoundaryEdgeCases)
848{
849 using Flavor = TranslatorFlavor;
850 using FF = typename Flavor::FF;
851
852 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
853
854 TranslatorProvingKey key{};
855 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
856 auto& pp = key.proving_key->polynomials;
857
858 const FF circuit_sentinel(42);
859 const FF masking_sentinel(9999);
860
861 // Fill wires with sentinels
862 auto groups = pp.get_groups_to_be_concatenated();
863 for (size_t i = 0; i < groups.size(); i++) {
864 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
865 auto& poly = groups[i][j];
866 if (poly.is_empty()) {
867 continue;
868 }
869 // Circuit region: fill with circuit_sentinel
870 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
871 poly.at(k) = circuit_sentinel;
872 }
873 // Masking region: fill with masking_sentinel
874 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
875 poly.at(k) = masking_sentinel;
876 }
877 }
878 }
879
880 key.compute_concatenated_polynomials();
881
882 auto concatenated = pp.get_concatenated();
883
884 // Check boundary positions for each block in each group
885 for (size_t i = 0; i < groups.size(); i++) {
886 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
887 if (i == 4 && j >= 13) {
888 continue; // skip null padding
889 }
890
891 // Last non-masking row: j*MINI + MINI - NUM_MASKED - 1
892 // Note: NUM_DISABLED_ROWS_IN_SUMCHECK = NUM_MASKED_ROWS_END (== 4 for translator)
893 size_t last_circuit_row = j * MINI + (MINI - NUM_DISABLED_ROWS_IN_SUMCHECK - 1);
894 EXPECT_EQ(concatenated[i][last_circuit_row], circuit_sentinel)
895 << "Last circuit row mismatch at group=" << i << " block=" << j;
896
897 // First masking row: j*MINI + MINI - NUM_MASKED
898 size_t first_masking_row = j * MINI + (MINI - NUM_DISABLED_ROWS_IN_SUMCHECK);
899 EXPECT_EQ(concatenated[i][first_masking_row], masking_sentinel)
900 << "First masking row mismatch at group=" << i << " block=" << j;
901
902 // Last masking row: j*MINI + MINI - 1
903 size_t last_masking_row = j * MINI + MINI - 1;
904 EXPECT_EQ(concatenated[i][last_masking_row], masking_sentinel)
905 << "Last masking row mismatch at group=" << i << " block=" << j;
906
907 // First row of next block (if exists): should be zero (position 0 below start_index)
908 if (j + 1 < Flavor::CONCATENATION_GROUP_SIZE) {
909 size_t next_block_row_0 = (j + 1) * MINI + 0;
910 EXPECT_EQ(concatenated[i][next_block_row_0], FF(0))
911 << "Next block row 0 not zero at group=" << i << " block=" << j;
912
913 // Second row of next block: should be circuit_sentinel (first circuit value, start_index=1)
914 // But only if not a null padding slot
915 if (!(i == 4 && (j + 1) >= 13)) {
916 size_t next_block_row_1 = (j + 1) * MINI + 1;
917 EXPECT_EQ(concatenated[i][next_block_row_1], circuit_sentinel)
918 << "Next block row 1 mismatch at group=" << i << " block=" << j;
919 }
920 }
921 }
922 }
923}
924
930TEST_F(TranslatorRelationCorrectnessTests, OrderedPolynomialBoundary)
931{
932 using Flavor = TranslatorFlavor;
933 using FF = typename Flavor::FF;
934
935 auto& engine = numeric::get_debug_randomness();
936
937 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
938 constexpr size_t full_circuit_size = MINI * Flavor::CONCATENATION_GROUP_SIZE;
939 const size_t max_range_value = (1 << Flavor::MICRO_LIMB_BITS) - 1;
940
941 TranslatorProvingKey key{};
942 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
943 auto& pp = key.proving_key->polynomials;
944
945 // Fill group wire polynomials with random 14-bit values and random masking values
946 for (const auto& group : pp.get_groups_to_be_concatenated()) {
947 for (auto& poly : group) {
948 if (poly.is_empty()) {
949 continue;
950 }
951 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
952 poly.at(k) = FF(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
953 }
954 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
955 poly.at(k) = FF::random_element();
956 }
957 }
958 }
959
960 key.compute_lagrange_polynomials();
961 key.compute_extra_range_constraint_numerator();
962 key.compute_concatenated_polynomials();
963 key.compute_translator_range_constraint_ordered_polynomials();
964
965 auto ordered = pp.get_ordered_range_constraints();
966 const size_t last_non_masking = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED - 1;
967
968 // The last non-masking position should hold the max range value (sorted_steps start from max)
969 for (size_t i = 0; i < ordered.size(); i++) {
970 EXPECT_EQ(ordered[i][last_non_masking], FF(max_range_value))
971 << "Max range value not at last_non_masking for ordered poly " << i;
972 }
973
974 // Ordered values should be non-descending in [1, last_non_masking]
975 for (size_t i = 0; i < ordered.size(); i++) {
976 for (size_t pos = 2; pos <= last_non_masking; pos++) {
977 uint256_t prev = uint256_t(ordered[i][pos - 1]);
978 uint256_t curr = uint256_t(ordered[i][pos]);
979 EXPECT_LE(prev, curr) << "Non-monotonic at ordered poly " << i << " position " << pos;
980 }
981 }
982
983 // Position 0 in each ordered poly should be 0 (virtual zero for shift)
984 for (size_t i = 0; i < ordered.size(); i++) {
985 EXPECT_EQ(ordered[i][0], FF(0)) << "Position 0 not zero for ordered poly " << i;
986 }
987}
988
994TEST_F(TranslatorRelationCorrectnessTests, LagrangeSelectorBoundaryCorrectness)
995{
996 using Flavor = TranslatorFlavor;
997 using FF = typename Flavor::FF;
998
999 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
1000 constexpr size_t full_circuit_size = MINI * Flavor::CONCATENATION_GROUP_SIZE;
1001 constexpr size_t NUM_MASKED = Flavor::NUM_MASKED_ROWS_END;
1002
1003 TranslatorProvingKey key{};
1004 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
1005 auto& pp = key.proving_key->polynomials;
1006
1007 key.compute_lagrange_polynomials();
1008
1009 // --- lagrange_masking (scattered): 1 at last NUM_MASKED rows of each block ---
1010 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
1011 size_t block_masking_start = j * MINI + (MINI - NUM_MASKED);
1012 // Row before masking should be 0
1013 EXPECT_EQ(pp.lagrange_masking[block_masking_start - 1], FF(0))
1014 << "lagrange_masking should be 0 before masking block " << j;
1015 // All masking rows should be 1
1016 for (size_t k = block_masking_start; k < j * MINI + MINI; k++) {
1017 EXPECT_EQ(pp.lagrange_masking[k], FF(1)) << "lagrange_masking should be 1 at block=" << j << " pos=" << k;
1018 }
1019 }
1020
1021 // --- lagrange_ordered_masking (contiguous at end) ---
1022 EXPECT_EQ(pp.lagrange_ordered_masking[full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED - 1], FF(0))
1023 << "lagrange_ordered_masking should be 0 one position before masking region";
1024 for (size_t i = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED; i < full_circuit_size; i++) {
1025 EXPECT_EQ(pp.lagrange_ordered_masking[i], FF(1)) << "lagrange_ordered_masking should be 1 at position " << i;
1026 }
1027
1028 // --- lagrange_real_last ---
1029 const size_t real_last_pos = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED - 1;
1030 EXPECT_EQ(pp.lagrange_real_last[real_last_pos], FF(1)) << "lagrange_real_last should be 1 at real_last position";
1031 EXPECT_EQ(pp.lagrange_real_last[real_last_pos - 1], FF(0))
1032 << "lagrange_real_last should be 0 before real_last position";
1033 EXPECT_EQ(pp.lagrange_real_last[real_last_pos + 1], FF(0))
1034 << "lagrange_real_last should be 0 after real_last position";
1035}
bb::ECCOpQueue::OP_QUEUE_SIZE
static const size_t OP_QUEUE_SIZE
Definition ecc_op_queue.hpp:64
bb::ECCVMFlavor::ProverPolynomials
A container for the prover polynomials.
Definition eccvm_flavor.hpp:460
bb::ECCVMFlavor::FF
typename Curve::ScalarField FF
Definition eccvm_flavor.hpp:43
bb::ECCVMFlavor::CircuitBuilder
ECCVMCircuitBuilder CircuitBuilder
Definition eccvm_flavor.hpp:39
bb::ECCVMFlavor::BF
typename Curve::BaseField BF
Definition eccvm_flavor.hpp:44
bb::ECCVMFlavor::Polynomial
bb::Polynomial< FF > Polynomial
Definition eccvm_flavor.hpp:45
bb::ECCVMFlavor::GroupElement
typename G1::element GroupElement
Definition eccvm_flavor.hpp:46
bb::RelationChecker
A debugging utility for checking whether a set of polynomials satisfies the relations for a given Fla...
Definition relation_checker.hpp:15
bb::Relation
A wrapper for Relations to expose methods used by the Sumcheck prover or verifier to add the contribu...
Definition relation_types.hpp:96
bb::TranslatorCircuitBuilder
TranslatorCircuitBuilder creates a circuit that evaluates the correctness of the evaluation of EccOpQ...
Definition translator_circuit_builder.hpp:69
bb::TranslatorFlavor::ProverPolynomials
A container for the prover polynomials handles.
Definition translator_flavor.hpp:996
bb::TranslatorFlavor::MINI_CIRCUIT_SIZE
static constexpr size_t MINI_CIRCUIT_SIZE
Definition translator_flavor.hpp:80
bb::TranslatorFlavor::NUM_MASKED_ROWS_END
static constexpr size_t NUM_MASKED_ROWS_END
Definition translator_flavor.hpp:98
bb::TranslatorProvingKey::get_sorted_steps
static std::array< size_t, Flavor::SORTED_STEPS_COUNT > get_sorted_steps()
Create the array of steps inserted in each ordered range constraint to ensure they respect the approp...
Definition translator_proving_key.hpp:106
bb::TranslatorProvingKey::dyadic_circuit_size_without_masking
static constexpr size_t dyadic_circuit_size_without_masking
Definition translator_proving_key.hpp:33
bb::TranslatorProvingKey::dyadic_mini_circuit_size_without_masking
static constexpr size_t dyadic_mini_circuit_size_without_masking
Definition translator_proving_key.hpp:31
bb::group
group class. Represents an elliptic curve group element. Group is parametrised by Fq and Fr
Definition group.hpp:36
bb::numeric::RNG::get_random_uint8
virtual uint8_t get_random_uint8()=0
bb::numeric::RNG::get_random_uint16
virtual uint16_t get_random_uint16()=0
bb::numeric::RNG::get_random_uint256
virtual uint256_t get_random_uint256()=0
bb::numeric::uint256_t
Definition uint256.hpp:32
bb::numeric::uint256_t::slice
constexpr uint256_t slice(uint64_t start, uint64_t end) const
Definition uint256_impl.hpp:330
ProverPolynomials
typename ECCVMFlavor::ProverPolynomials ProverPolynomials
Definition eccvm_trace_checker.cpp:10
engine
numeric::RNG & engine
Definition eccvm_transcript.test.cpp:285
grand_product_library.hpp
key
FF key
Definition indexed_memory_tree.test.cpp:18
bb::numeric::get_debug_randomness
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:217
bb::srs::bb_crs_path
std::filesystem::path bb_crs_path()
Definition global_crs.cpp:14
bb::srs::init_file_crs_factory
void init_file_crs_factory(const std::filesystem::path &path)
Definition global_crs.hpp:14
bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
bb::TEST_F
TEST_F(IPATest, ChallengesAreZero)
Definition ipa.test.cpp:155
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
relation_checker.hpp
bb::RelationParameters
Container for parameters used by the grand product (permutation, lookup) Honk relations.
Definition relation_parameters.hpp:18
bb::RelationParameters::batching_challenge_v
std::array< std::array< T, NUM_BINARY_LIMBS_IN_GOBLIN_TRANSLATOR+NUM_NATIVE_LIMBS_IN_GOBLIN_TRANSLATOR >, NUM_CHALLENGE_POWERS_IN_GOBLIN_TRANSLATOR > batching_challenge_v
Definition relation_parameters.hpp:64
bb::RelationParameters::accumulated_result
std::array< T, NUM_BINARY_LIMBS_IN_GOBLIN_TRANSLATOR > accumulated_result
Definition relation_parameters.hpp:58
bb::RelationParameters::evaluation_input_x
std::array< T, NUM_BINARY_LIMBS_IN_GOBLIN_TRANSLATOR+NUM_NATIVE_LIMBS_IN_GOBLIN_TRANSLATOR > evaluation_input_x
Definition relation_parameters.hpp:59
bb::field< bb::Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:783
translator_flavor.hpp
translator_proving_key.hpp