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->construct_zk_columns();
458
459 // Generate random EccOpQueue actions
460
461 for (size_t i = 0; i < (mini_circuit_size >> 1) / 2; i++) {
462 switch (engine.get_random_uint8() % 3) {
463 case 0:
464 op_queue->eq_and_reset();
465 break;
466 case 1:
467 op_queue->add_accumulate(GroupElement::random_element(&engine));
468 break;
469 case 2:
470 op_queue->mul_accumulate(GroupElement::random_element(&engine), FF::random_element(&engine));
471 break;
472 }
473 }
474 op_queue->merge();
475 for (size_t i = 0; i < 100; i++) {
476 switch (engine.get_random_uint8() % 3) {
477 case 0:
478 op_queue->eq_and_reset();
479 break;
480 case 1:
481 op_queue->add_accumulate(GroupElement::random_element(&engine));
482 break;
483 case 2:
484 op_queue->mul_accumulate(GroupElement::random_element(&engine), FF::random_element(&engine));
485 break;
486 }
487 }
488 op_queue->random_op_ultra_only();
489 op_queue->random_op_ultra_only();
490 op_queue->merge_fixed_append(op_queue->get_append_offset());
491
492 const auto batching_challenge_v = BF::random_element(&engine);
493 const auto evaluation_input_x = BF::random_element(&engine);
494
495 // Generating all the values is pretty tedious, so just use CircuitBuilder
496 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge_v, evaluation_input_x, op_queue);
497
498 // The non-native field relation uses limbs of evaluation_input_x and powers of batching_challenge_v as inputs
499 RelationParameters<FF> params;
500 auto v_power = BF::one();
501 for (size_t i = 0; i < 4 /*Number of powers of v that we need {1,2,3,4}*/; i++) {
502 v_power *= batching_challenge_v;
503 auto uint_v_power = uint256_t(v_power);
504 params.batching_challenge_v.at(i) = { uint_v_power.slice(0, NUM_LIMB_BITS),
505 uint_v_power.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
506 uint_v_power.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
507 uint_v_power.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
508 uint_v_power };
509 }
510 auto uint_input_x = uint256_t(evaluation_input_x);
511 params.evaluation_input_x = { uint_input_x.slice(0, NUM_LIMB_BITS),
512 uint_input_x.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
513 uint_input_x.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
514 uint_input_x.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
515 uint_input_x };
516
517 // Create storage for polynomials
518 ProverPolynomials prover_polynomials = TranslatorFlavor::ProverPolynomials();
519 // Copy values of wires used in the non-native field relation from the circuit builder
520 for (size_t i = Builder::NUM_RANDOM_OPS_START; i < circuit_builder.num_gates() - Builder::NUM_RANDOM_OPS_END; i++) {
521 prover_polynomials.op.at(i) = circuit_builder.get_variable(circuit_builder.wires[circuit_builder.OP][i]);
522 prover_polynomials.p_x_low_limbs.at(i) =
523 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_X_LOW_LIMBS][i]);
524 prover_polynomials.p_x_high_limbs.at(i) =
525 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_X_HIGH_LIMBS][i]);
526 prover_polynomials.p_y_low_limbs.at(i) =
527 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_Y_LOW_LIMBS][i]);
528 prover_polynomials.p_y_high_limbs.at(i) =
529 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_Y_HIGH_LIMBS][i]);
530 prover_polynomials.z_low_limbs.at(i) =
531 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.Z_LOW_LIMBS][i]);
532 prover_polynomials.z_high_limbs.at(i) =
533 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.Z_HIGH_LIMBS][i]);
534 prover_polynomials.accumulators_binary_limbs_0.at(i) =
535 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_0][i]);
536 prover_polynomials.accumulators_binary_limbs_1.at(i) =
537 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_1][i]);
538 prover_polynomials.accumulators_binary_limbs_2.at(i) =
539 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_2][i]);
540 prover_polynomials.accumulators_binary_limbs_3.at(i) =
541 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_3][i]);
542 prover_polynomials.quotient_low_binary_limbs.at(i) =
543 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.QUOTIENT_LOW_BINARY_LIMBS][i]);
544 prover_polynomials.quotient_high_binary_limbs.at(i) =
545 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.QUOTIENT_HIGH_BINARY_LIMBS][i]);
546 prover_polynomials.relation_wide_limbs.at(i) =
547 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.RELATION_WIDE_LIMBS][i]);
548 }
549
550 // Fill in lagrange odd polynomial
551 for (size_t i = Flavor::RESULT_ROW; i < mini_circuit_size_without_masking; i += 2) {
552 prover_polynomials.lagrange_even_in_minicircuit.at(i) = 1;
553 prover_polynomials.lagrange_odd_in_minicircuit.at(i + 1) = 1;
554 }
555
556 // Check that Non-Native Field relation is satisfied across each row of the prover polynomials
557 RelationChecker<Flavor>::check<TranslatorNonNativeFieldRelation<FF>>(
558 prover_polynomials, params, "TranslatorNonNativeFieldRelation");
559}
560
561TEST_F(TranslatorRelationCorrectnessTests, ZeroKnowledgePermutation)
562{
563 using Flavor = TranslatorFlavor;
564 using FF = typename Flavor::FF;
565 using ProverPolynomials = typename Flavor::ProverPolynomials;
566
567 auto& engine = numeric::get_debug_randomness();
568
569 TranslatorProvingKey key{};
570 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
571 ProverPolynomials& prover_polynomials = key.proving_key->polynomials;
572
573 // Fill required relation parameters
574 RelationParameters<FF> params{ .beta = FF::random_element(), .gamma = FF::random_element() };
575
576 // Populate the group polynomials with appropriate values and also enough random values to mask their commitment
577 // and evaluation
578 auto fill_polynomial_with_random_14_bit_values = [&](auto& polynomial) {
579 for (size_t i = polynomial.start_index(); i < polynomial.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; i++) {
580 polynomial.at(i) = engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1);
581 }
582 for (size_t i = polynomial.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; i < polynomial.end_index(); i++) {
583 polynomial.at(i) = FF::random_element();
584 }
585 };
586
587 for (const auto& group : prover_polynomials.get_groups_to_be_concatenated()) {
588 for (auto& poly : group) {
589 // Skip null padding slots (empty zero polynomials in group 4)
590 if (poly.is_empty()) {
591 continue;
592 }
593 fill_polynomial_with_random_14_bit_values(poly);
594 }
595 }
596
597 key.compute_lagrange_polynomials();
598 key.compute_concatenated_polynomials();
599 key.compute_extra_range_constraint_numerator();
600 key.compute_translator_range_constraint_ordered_polynomials();
601
602 // Compute the grand product polynomial
603 compute_grand_product<Flavor, bb::TranslatorPermutationRelation<FF>>(prover_polynomials, params);
604
605 // Check that permutation relation is satisfied across each row of the prover polynomials
606 auto perm_failures = RelationChecker<Flavor>::check<TranslatorPermutationRelation<FF>>(
607 prover_polynomials, params, "TranslatorPermutationRelation");
608 EXPECT_TRUE(perm_failures.empty());
609 auto delta_failures = RelationChecker<Flavor>::check<TranslatorDeltaRangeConstraintRelation<FF>>(
610 prover_polynomials, params, "TranslatorDeltaRangeConstraintRelation");
611 EXPECT_TRUE(delta_failures.empty());
612}
613
614TEST_F(TranslatorRelationCorrectnessTests, ZeroKnowledgeDeltaRange)
615{
616 using Flavor = TranslatorFlavor;
617 using FF = typename Flavor::FF;
618 using ProverPolynomials = typename Flavor::ProverPolynomials;
619 auto& engine = numeric::get_debug_randomness();
620
621 TranslatorProvingKey key;
622 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
623 ProverPolynomials& prover_polynomials = key.proving_key->polynomials;
624
625 const size_t dyadic_circuit_size_without_masking = TranslatorProvingKey::dyadic_circuit_size_without_masking;
626
627 key.compute_lagrange_polynomials();
628
629 // Create a vector and fill with necessary steps for the DeltaRangeConstraint relation
630 auto sorted_steps = TranslatorProvingKey::get_sorted_steps();
631 std::vector<uint64_t> vector_for_sorting(sorted_steps.begin(), sorted_steps.end());
632
633 // Add random values in the appropriate range to fill the leftover space (before masking region)
634 for (size_t i = sorted_steps.size();
635 i < prover_polynomials.ordered_range_constraints_0.size() - Flavor::MAX_RANDOM_VALUES_PER_ORDERED;
636 i++) {
637 vector_for_sorting.emplace_back(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
638 }
639
640 // Get ordered polynomials
641 auto polynomial_pointers = std::vector{ &prover_polynomials.ordered_range_constraints_0,
642 &prover_polynomials.ordered_range_constraints_1,
643 &prover_polynomials.ordered_range_constraints_2,
644 &prover_polynomials.ordered_range_constraints_3,
645 &prover_polynomials.ordered_range_constraints_4 };
646
647 std::sort(vector_for_sorting.begin(), vector_for_sorting.end());
648
649 // Add masking values
650 for (size_t i = dyadic_circuit_size_without_masking; i < key.dyadic_circuit_size; i++) {
651 vector_for_sorting.emplace_back(FF::random_element());
652 }
653
654 // Copy values, transforming them into Finite Field elements
655 std::transform(vector_for_sorting.cbegin(),
656 vector_for_sorting.cend(),
657 prover_polynomials.ordered_range_constraints_0.coeffs().begin(),
658 [](uint64_t in) { return FF(in); });
659
660 // Copy the same polynomial into the 4 other ordered polynomials (they are not the same in an actual proof, but
661 // we only need to check the correctness of the relation and it acts independently on each polynomial)
662 for (size_t i = 0; i < 4; ++i) {
663 std::copy(prover_polynomials.ordered_range_constraints_0.coeffs().begin(),
664 prover_polynomials.ordered_range_constraints_0.coeffs().end(),
665 polynomial_pointers[i + 1]->coeffs().begin());
666 }
667
668 // Check that DeltaRangeConstraint relation is satisfied across each row of the prover polynomials
669 auto delta_range_failures = RelationChecker<Flavor>::check<TranslatorDeltaRangeConstraintRelation<FF>>(
670 prover_polynomials, RelationParameters<FF>(), "TranslatorDeltaRangeConstraintRelation");
671 EXPECT_TRUE(delta_range_failures.empty());
672}
673
680TEST_F(TranslatorRelationCorrectnessTests, ConcatenatedPolynomialLayout)
681{
682 using Flavor = TranslatorFlavor;
683 using FF = typename Flavor::FF;
684
685 auto& engine = numeric::get_debug_randomness();
686
687 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
688
689 TranslatorProvingKey key{};
690 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
691 auto& pp = key.proving_key->polynomials;
692
693 // Fill group wire polynomials with deterministic 14-bit values in circuit region, random values in masking rows
694 auto groups = pp.get_groups_to_be_concatenated();
695 for (size_t i = 0; i < groups.size(); i++) {
696 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
697 auto& poly = groups[i][j];
698 if (poly.is_empty()) {
699 continue;
700 }
701 // Fill circuit region with deterministic 14-bit values
702 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
703 poly.at(k) = FF(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
704 }
705 // Fill masking rows with random FF values
706 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
707 poly.at(k) = FF::random_element();
708 }
709 }
710 }
711
712 key.compute_concatenated_polynomials();
713
714 auto concatenated = pp.get_concatenated();
715
716 // Re-fetch groups (they are RefVectors, so point to same data)
717 auto groups_after = pp.get_groups_to_be_concatenated();
718
719 for (size_t i = 0; i < groups_after.size(); i++) {
720 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
721 auto& poly = groups_after[i][j];
722
723 // Null padding slots in group 4 (lanes 13-15): all positions should be zero
724 if (i == 4 && j >= 13) {
725 for (size_t k = 0; k < MINI; k++) {
726 EXPECT_EQ(concatenated[i][j * MINI + k], FF(0))
727 << "Null padding not zero at group=" << i << " lane=" << j << " row=" << k;
728 }
729 continue;
730 }
731
732 // Position 0 in each block should be zero (below start_index=1)
733 EXPECT_EQ(concatenated[i][j * MINI + 0], FF(0)) << "Position 0 not zero at group=" << i << " lane=" << j;
734
735 // Non-zero region: values should match original wire values
736 for (size_t k = poly.start_index(); k < poly.end_index(); k++) {
737 EXPECT_EQ(concatenated[i][j * MINI + k], poly[k])
738 << "Mismatch at group=" << i << " lane=" << j << " row=" << k;
739 }
740 }
741 }
742}
743
750TEST_F(TranslatorRelationCorrectnessTests, RandomnessRedistributionIntegrity)
751{
752 using Flavor = TranslatorFlavor;
753 using FF = typename Flavor::FF;
754
755 auto& engine = numeric::get_debug_randomness();
756
757 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
758 constexpr size_t full_circuit_size = MINI * Flavor::CONCATENATION_GROUP_SIZE;
759
760 TranslatorProvingKey key{};
761 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
762 auto& pp = key.proving_key->polynomials;
763
764 // Fill group wire polynomials
765 for (const auto& group : pp.get_groups_to_be_concatenated()) {
766 for (auto& poly : group) {
767 if (poly.is_empty()) {
768 continue;
769 }
770 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
771 poly.at(k) = FF(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
772 }
773 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
774 poly.at(k) = FF::random_element();
775 }
776 }
777 }
778
779 key.compute_concatenated_polynomials();
780 key.compute_extra_range_constraint_numerator();
781
782 // Collect random values from scattered masking positions in concatenated[0..3] BEFORE redistribution
783 auto concatenated = pp.get_concatenated();
784 std::multiset<uint256_t> random_values_from_concat;
785 for (size_t i = 0; i < 4; i++) { // Only first 4 (range constraint) concatenated polys
786 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
787 size_t block_masking_start = j * MINI + (MINI - NUM_DISABLED_ROWS_IN_SUMCHECK);
788 size_t block_masking_end = j * MINI + MINI;
789 for (size_t k = block_masking_start; k < block_masking_end; k++) {
790 random_values_from_concat.insert(uint256_t(concatenated[i][k]));
791 }
792 }
793 }
794
795 // Total expected: 4 concat polys * 16 blocks * NUM_DISABLED_ROWS_IN_SUMCHECK rows
796 const size_t expected_total = 4 * Flavor::CONCATENATION_GROUP_SIZE * NUM_DISABLED_ROWS_IN_SUMCHECK;
797 EXPECT_EQ(random_values_from_concat.size(), expected_total);
798
799 // Now compute ordered polynomials (which calls split_concatenated_random_coefficients_to_ordered)
800 key.compute_translator_range_constraint_ordered_polynomials();
801
802 // Collect random values from contiguous masking region at end of ordered polys.
803 // The random values from the 4 concatenated polys (4*16*4 = 256 values) are redistributed across 5 ordered polys,
804 // with each ordered poly getting at most MAX_RANDOM_VALUES_PER_ORDERED positions. Not all positions may be filled,
805 // so we collect only non-padding (non-zero) values. Since random FF elements are zero with negligible probability
806 // (1/p), this is safe.
807 auto ordered = pp.get_ordered_range_constraints();
808 std::multiset<uint256_t> random_values_from_ordered;
809 for (size_t i = 0; i < ordered.size(); i++) {
810 for (size_t pos = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED; pos < full_circuit_size; pos++) {
811 FF val = ordered[i][pos];
812 if (val != FF(0)) {
813 random_values_from_ordered.insert(uint256_t(val));
814 }
815 }
816 }
817
818 // The multisets should be equal (same values with same multiplicities)
819 EXPECT_EQ(random_values_from_concat, random_values_from_ordered);
820
821 // Verify non-masking region of ordered polys has values in [0, 16383]
822 const size_t max_range_value = (1 << Flavor::MICRO_LIMB_BITS) - 1;
823 for (size_t i = 0; i < ordered.size(); i++) {
824 for (size_t pos = 1; pos < full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED; pos++) {
825 uint256_t val = uint256_t(ordered[i][pos]);
826 EXPECT_LE(val, max_range_value) << "Out-of-range value in ordered poly " << i << " at position " << pos;
827 }
828 }
829}
830
836TEST_F(TranslatorRelationCorrectnessTests, BlockBoundaryEdgeCases)
837{
838 using Flavor = TranslatorFlavor;
839 using FF = typename Flavor::FF;
840
841 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
842
843 TranslatorProvingKey key{};
844 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
845 auto& pp = key.proving_key->polynomials;
846
847 const FF circuit_sentinel(42);
848 const FF masking_sentinel(9999);
849
850 // Fill wires with sentinels
851 auto groups = pp.get_groups_to_be_concatenated();
852 for (size_t i = 0; i < groups.size(); i++) {
853 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
854 auto& poly = groups[i][j];
855 if (poly.is_empty()) {
856 continue;
857 }
858 // Circuit region: fill with circuit_sentinel
859 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
860 poly.at(k) = circuit_sentinel;
861 }
862 // Masking region: fill with masking_sentinel
863 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
864 poly.at(k) = masking_sentinel;
865 }
866 }
867 }
868
869 key.compute_concatenated_polynomials();
870
871 auto concatenated = pp.get_concatenated();
872
873 // Check boundary positions for each block in each group
874 for (size_t i = 0; i < groups.size(); i++) {
875 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
876 if (i == 4 && j >= 13) {
877 continue; // skip null padding
878 }
879
880 // Last non-masking row: j*MINI + MINI - NUM_MASKED - 1
881 // Note: NUM_DISABLED_ROWS_IN_SUMCHECK = NUM_MASKED_ROWS_END (== 4 for translator)
882 size_t last_circuit_row = j * MINI + (MINI - NUM_DISABLED_ROWS_IN_SUMCHECK - 1);
883 EXPECT_EQ(concatenated[i][last_circuit_row], circuit_sentinel)
884 << "Last circuit row mismatch at group=" << i << " block=" << j;
885
886 // First masking row: j*MINI + MINI - NUM_MASKED
887 size_t first_masking_row = j * MINI + (MINI - NUM_DISABLED_ROWS_IN_SUMCHECK);
888 EXPECT_EQ(concatenated[i][first_masking_row], masking_sentinel)
889 << "First masking row mismatch at group=" << i << " block=" << j;
890
891 // Last masking row: j*MINI + MINI - 1
892 size_t last_masking_row = j * MINI + MINI - 1;
893 EXPECT_EQ(concatenated[i][last_masking_row], masking_sentinel)
894 << "Last masking row mismatch at group=" << i << " block=" << j;
895
896 // First row of next block (if exists): should be zero (position 0 below start_index)
897 if (j + 1 < Flavor::CONCATENATION_GROUP_SIZE) {
898 size_t next_block_row_0 = (j + 1) * MINI + 0;
899 EXPECT_EQ(concatenated[i][next_block_row_0], FF(0))
900 << "Next block row 0 not zero at group=" << i << " block=" << j;
901
902 // Second row of next block: should be circuit_sentinel (first circuit value, start_index=1)
903 // But only if not a null padding slot
904 if (!(i == 4 && (j + 1) >= 13)) {
905 size_t next_block_row_1 = (j + 1) * MINI + 1;
906 EXPECT_EQ(concatenated[i][next_block_row_1], circuit_sentinel)
907 << "Next block row 1 mismatch at group=" << i << " block=" << j;
908 }
909 }
910 }
911 }
912}
913
919TEST_F(TranslatorRelationCorrectnessTests, OrderedPolynomialBoundary)
920{
921 using Flavor = TranslatorFlavor;
922 using FF = typename Flavor::FF;
923
924 auto& engine = numeric::get_debug_randomness();
925
926 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
927 constexpr size_t full_circuit_size = MINI * Flavor::CONCATENATION_GROUP_SIZE;
928 const size_t max_range_value = (1 << Flavor::MICRO_LIMB_BITS) - 1;
929
930 TranslatorProvingKey key{};
931 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
932 auto& pp = key.proving_key->polynomials;
933
934 // Fill group wire polynomials with random 14-bit values and random masking values
935 for (const auto& group : pp.get_groups_to_be_concatenated()) {
936 for (auto& poly : group) {
937 if (poly.is_empty()) {
938 continue;
939 }
940 for (size_t k = poly.start_index(); k < poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k++) {
941 poly.at(k) = FF(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
942 }
943 for (size_t k = poly.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; k < poly.end_index(); k++) {
944 poly.at(k) = FF::random_element();
945 }
946 }
947 }
948
949 key.compute_lagrange_polynomials();
950 key.compute_extra_range_constraint_numerator();
951 key.compute_concatenated_polynomials();
952 key.compute_translator_range_constraint_ordered_polynomials();
953
954 auto ordered = pp.get_ordered_range_constraints();
955 const size_t last_non_masking = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED - 1;
956
957 // The last non-masking position should hold the max range value (sorted_steps start from max)
958 for (size_t i = 0; i < ordered.size(); i++) {
959 EXPECT_EQ(ordered[i][last_non_masking], FF(max_range_value))
960 << "Max range value not at last_non_masking for ordered poly " << i;
961 }
962
963 // Ordered values should be non-descending in [1, last_non_masking]
964 for (size_t i = 0; i < ordered.size(); i++) {
965 for (size_t pos = 2; pos <= last_non_masking; pos++) {
966 uint256_t prev = uint256_t(ordered[i][pos - 1]);
967 uint256_t curr = uint256_t(ordered[i][pos]);
968 EXPECT_LE(prev, curr) << "Non-monotonic at ordered poly " << i << " position " << pos;
969 }
970 }
971
972 // Position 0 in each ordered poly should be 0 (virtual zero for shift)
973 for (size_t i = 0; i < ordered.size(); i++) {
974 EXPECT_EQ(ordered[i][0], FF(0)) << "Position 0 not zero for ordered poly " << i;
975 }
976}
977
983TEST_F(TranslatorRelationCorrectnessTests, LagrangeSelectorBoundaryCorrectness)
984{
985 using Flavor = TranslatorFlavor;
986 using FF = typename Flavor::FF;
987
988 constexpr size_t MINI = Flavor::MINI_CIRCUIT_SIZE;
989 constexpr size_t full_circuit_size = MINI * Flavor::CONCATENATION_GROUP_SIZE;
990 constexpr size_t NUM_MASKED = Flavor::NUM_MASKED_ROWS_END;
991
992 TranslatorProvingKey key{};
993 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
994 auto& pp = key.proving_key->polynomials;
995
996 key.compute_lagrange_polynomials();
997
998 // --- lagrange_masking (scattered): 1 at last NUM_MASKED rows of each block ---
999 for (size_t j = 0; j < Flavor::CONCATENATION_GROUP_SIZE; j++) {
1000 size_t block_masking_start = j * MINI + (MINI - NUM_MASKED);
1001 // Row before masking should be 0
1002 EXPECT_EQ(pp.lagrange_masking[block_masking_start - 1], FF(0))
1003 << "lagrange_masking should be 0 before masking block " << j;
1004 // All masking rows should be 1
1005 for (size_t k = block_masking_start; k < j * MINI + MINI; k++) {
1006 EXPECT_EQ(pp.lagrange_masking[k], FF(1)) << "lagrange_masking should be 1 at block=" << j << " pos=" << k;
1007 }
1008 }
1009
1010 // --- lagrange_ordered_masking (contiguous at end) ---
1011 EXPECT_EQ(pp.lagrange_ordered_masking[full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED - 1], FF(0))
1012 << "lagrange_ordered_masking should be 0 one position before masking region";
1013 for (size_t i = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED; i < full_circuit_size; i++) {
1014 EXPECT_EQ(pp.lagrange_ordered_masking[i], FF(1)) << "lagrange_ordered_masking should be 1 at position " << i;
1015 }
1016
1017 // --- lagrange_real_last ---
1018 const size_t real_last_pos = full_circuit_size - Flavor::MAX_RANDOM_VALUES_PER_ORDERED - 1;
1019 EXPECT_EQ(pp.lagrange_real_last[real_last_pos], FF(1)) << "lagrange_real_last should be 1 at real_last position";
1020 EXPECT_EQ(pp.lagrange_real_last[real_last_pos - 1], FF(0))
1021 << "lagrange_real_last should be 0 before real_last position";
1022 EXPECT_EQ(pp.lagrange_real_last[real_last_pos + 1], FF(0))
1023 << "lagrange_real_last should be 0 after real_last position";
1024}
bb::ECCVMFlavor::ProverPolynomials
A container for the prover polynomials.
Definition eccvm_flavor.hpp:484
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:19
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:1029
bb::TranslatorFlavor::MINI_CIRCUIT_SIZE
static constexpr size_t MINI_CIRCUIT_SIZE
Definition translator_flavor.hpp:89
bb::TranslatorFlavor::NUM_MASKED_ROWS_END
static constexpr size_t NUM_MASKED_ROWS_END
Definition translator_flavor.hpp:107
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:103
bb::TranslatorProvingKey::dyadic_circuit_size_without_masking
static constexpr size_t dyadic_circuit_size_without_masking
Definition translator_proving_key.hpp:32
bb::TranslatorProvingKey::dyadic_mini_circuit_size_without_masking
static constexpr size_t dyadic_mini_circuit_size_without_masking
Definition translator_proving_key.hpp:30
bb::group
group class. Represents an elliptic curve group element. Group is parametrised by Fq and Fr
Definition group.hpp:38
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:336
ProverPolynomials
typename ECCVMFlavor::ProverPolynomials ProverPolynomials
Definition eccvm_trace_checker.cpp:10
engine
numeric::RNG & engine
Definition eccvm_transcript.test.cpp:282
grand_product_library.hpp
key
FF key
Definition indexed_memory_tree.test.cpp:19
bb::numeric::get_debug_randomness
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:245
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:777
translator_flavor.hpp
translator_proving_key.hpp