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 <unordered_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 polynomial
39 for (size_t i = prover_polynomials.lagrange_even_in_minicircuit.start_index();
40 i < prover_polynomials.lagrange_even_in_minicircuit.end_index();
41 i += 2) {
42 prover_polynomials.lagrange_even_in_minicircuit.at(i) = 1;
43 prover_polynomials.lagrange_odd_in_minicircuit.at(i + 1) = 1;
44 }
45 constexpr size_t NUMBER_OF_POSSIBLE_OPCODES = 3;
46 constexpr std::array<uint64_t, NUMBER_OF_POSSIBLE_OPCODES> possible_opcode_values = { 3, 4, 8 };
47
48 // Assign random opcode values
49 for (size_t i = Flavor::RESULT_ROW; i < mini_circuit_size_without_masking; i += 2) {
50 prover_polynomials.op.at(i) =
51 possible_opcode_values[static_cast<size_t>(engine.get_random_uint8() % NUMBER_OF_POSSIBLE_OPCODES)];
52 }
53
54 // Initialize used lagrange polynomials
55 prover_polynomials.lagrange_result_row.at(Flavor::RESULT_ROW) = 1;
56 prover_polynomials.lagrange_last_in_minicircuit.at(mini_circuit_size_without_masking - 1) = 1;
57
58 // Put random values in accumulator binary limbs (values should be preserved across even->next odd shift)
59 for (size_t i = Flavor::RESULT_ROW + 1; i < mini_circuit_size_without_masking - 1; i += 2) {
60 prover_polynomials.accumulators_binary_limbs_0.at(i) = FF ::random_element();
61 prover_polynomials.accumulators_binary_limbs_1.at(i) = FF ::random_element();
62 prover_polynomials.accumulators_binary_limbs_2.at(i) = FF ::random_element();
63 prover_polynomials.accumulators_binary_limbs_3.at(i) = FF ::random_element();
64 prover_polynomials.accumulators_binary_limbs_0.at(i + 1) = prover_polynomials.accumulators_binary_limbs_0[i];
65 prover_polynomials.accumulators_binary_limbs_2.at(i + 1) = prover_polynomials.accumulators_binary_limbs_2[i];
66 prover_polynomials.accumulators_binary_limbs_1.at(i + 1) = prover_polynomials.accumulators_binary_limbs_1[i];
67 prover_polynomials.accumulators_binary_limbs_3.at(i + 1) = prover_polynomials.accumulators_binary_limbs_3[i];
68 }
69
70 // The values of accumulator binary limbs at index 1 should equal the accumulated result from relation parameters
71 prover_polynomials.accumulators_binary_limbs_0.at(Flavor::RESULT_ROW) = params.accumulated_result[0];
72 prover_polynomials.accumulators_binary_limbs_1.at(Flavor::RESULT_ROW) = params.accumulated_result[1];
73 prover_polynomials.accumulators_binary_limbs_2.at(Flavor::RESULT_ROW) = params.accumulated_result[2];
74 prover_polynomials.accumulators_binary_limbs_3.at(Flavor::RESULT_ROW) = params.accumulated_result[3];
75
76 // Check that Opcode Constraint relation is satisfied across each row of the prover polynomials
77 RelationChecker<Flavor>::check<TranslatorOpcodeConstraintRelation<FF>>(
78 prover_polynomials, params, "TranslatorOpcodeConstraintRelation");
79
80 // Check that Accumulator Transfer relation is satisfied across each row of the prover polynomials
81 RelationChecker<Flavor>::check<TranslatorAccumulatorTransferRelation<FF>>(
82 prover_polynomials, params, "TranslatorAccumulatorTransferRelation");
83
84 // Check that Zero Constraint relation is satisfied across each row of the prover polynomials
85 RelationChecker<Flavor>::check<TranslatorZeroConstraintsRelation<FF>>(
86 prover_polynomials, params, "TranslatorZeroConstraintsRelation");
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
108 auto lagrange_odd_in_minicircuit = prover_polynomials.lagrange_odd_in_minicircuit;
109 // Fill in lagrange odd polynomial (the only non-witness one we are using)
110 for (size_t i = prover_polynomials.lagrange_odd_in_minicircuit.start_index();
111 i < lagrange_odd_in_minicircuit.end_index();
112 i += 2) {
113 prover_polynomials.lagrange_odd_in_minicircuit.at(i) = 1;
114 }
115
116 constexpr size_t NUM_LIMB_BITS = Flavor::CircuitBuilder::NUM_LIMB_BITS;
117 constexpr size_t HIGH_WIDE_LIMB_WIDTH =
118 Flavor::CircuitBuilder::NUM_LIMB_BITS + Flavor::CircuitBuilder::NUM_LAST_LIMB_BITS;
119 constexpr size_t LOW_WIDE_LIMB_WIDTH = Flavor::CircuitBuilder::NUM_LIMB_BITS * 2;
120 constexpr size_t Z_LIMB_WIDTH = 128;
121 constexpr size_t MICRO_LIMB_WIDTH = Flavor::MICRO_LIMB_BITS;
122 constexpr size_t SHIFT_12_TO_14 = 4;
123 constexpr size_t SHIFT_10_TO_14 = 16;
124 constexpr size_t SHIFT_8_TO_14 = 64;
125 constexpr size_t SHIFT_4_TO_14 = 1024;
126
132 auto decompose_standard_limb =
133 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& limb_4, auto& shifted_limb) {
134 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
135 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
136 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
137 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
138 limb_4 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 4, MICRO_LIMB_WIDTH * 5);
139 shifted_limb = limb_4 * SHIFT_12_TO_14;
140 };
141
147 auto decompose_standard_top_limb =
148 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& shifted_limb) {
149 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
150 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
151 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
152 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
153 shifted_limb = limb_3 * SHIFT_8_TO_14;
154 };
155
161 auto decompose_standard_top_z_limb =
162 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& limb_4, auto& shifted_limb) {
163 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
164 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
165 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
166 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
167 limb_4 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 4, MICRO_LIMB_WIDTH * 5);
168 shifted_limb = limb_4 * SHIFT_4_TO_14;
169 };
170
176 auto decompose_top_quotient_limb =
177 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& shifted_limb) {
178 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
179 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
180 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
181 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
182 shifted_limb = limb_3 * SHIFT_10_TO_14;
183 };
184
189 auto decompose_relation_limb =
190 [](auto& input, auto& limb_0, auto& limb_1, auto& limb_2, auto& limb_3, auto& limb_4, auto& limb_5) {
191 limb_0 = uint256_t(input).slice(0, MICRO_LIMB_WIDTH);
192 limb_1 = uint256_t(input).slice(MICRO_LIMB_WIDTH, MICRO_LIMB_WIDTH * 2);
193 limb_2 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 2, MICRO_LIMB_WIDTH * 3);
194 limb_3 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 3, MICRO_LIMB_WIDTH * 4);
195 limb_4 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 4, MICRO_LIMB_WIDTH * 5);
196 limb_5 = uint256_t(input).slice(MICRO_LIMB_WIDTH * 5, MICRO_LIMB_WIDTH * 6);
197 };
198
199 // Put random values in all the non-interleaved constraint polynomials used to range constrain the values
200 for (size_t i = 1; i < mini_circuit_size - 1; i += 2) {
201 // P.x
202 prover_polynomials.x_lo_y_hi.at(i) =
203 FF(engine.get_random_uint256() & ((uint256_t(1) << LOW_WIDE_LIMB_WIDTH) - 1));
204 prover_polynomials.x_hi_z_1.at(i) =
205 FF(engine.get_random_uint256() & ((uint256_t(1) << HIGH_WIDE_LIMB_WIDTH) - 1));
206
207 // P.y
208 prover_polynomials.y_lo_z_2.at(i) =
209 FF(engine.get_random_uint256() & ((uint256_t(1) << LOW_WIDE_LIMB_WIDTH) - 1));
210 prover_polynomials.x_lo_y_hi.at(i + 1) =
211 FF(engine.get_random_uint256() & ((uint256_t(1) << HIGH_WIDE_LIMB_WIDTH) - 1));
212
213 // z1 and z2
214 prover_polynomials.x_hi_z_1.at(i + 1) = FF(engine.get_random_uint256() & ((uint256_t(1) << Z_LIMB_WIDTH) - 1));
215 prover_polynomials.y_lo_z_2.at(i + 1) = FF(engine.get_random_uint256() & ((uint256_t(1) << Z_LIMB_WIDTH) - 1));
216
217 // Slice P.x into chunks
218 prover_polynomials.p_x_low_limbs.at(i) = uint256_t(prover_polynomials.x_lo_y_hi.at(i)).slice(0, NUM_LIMB_BITS);
219 prover_polynomials.p_x_low_limbs.at(i + 1) =
220 uint256_t(prover_polynomials.x_lo_y_hi.at(i)).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
221 prover_polynomials.p_x_high_limbs.at(i) = uint256_t(prover_polynomials.x_hi_z_1[i]).slice(0, NUM_LIMB_BITS);
222 prover_polynomials.p_x_high_limbs.at(i + 1) =
223 uint256_t(prover_polynomials.x_hi_z_1.at(i)).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
224
225 // Slice P.y into chunks
226 prover_polynomials.p_y_low_limbs.at(i) = uint256_t(prover_polynomials.y_lo_z_2[i]).slice(0, NUM_LIMB_BITS);
227 prover_polynomials.p_y_low_limbs.at(i + 1) =
228 uint256_t(prover_polynomials.y_lo_z_2[i]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
229 prover_polynomials.p_y_high_limbs.at(i) =
230 uint256_t(prover_polynomials.x_lo_y_hi[i + 1]).slice(0, NUM_LIMB_BITS);
231 prover_polynomials.p_y_high_limbs.at(i + 1) =
232 uint256_t(prover_polynomials.x_lo_y_hi[i + 1]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
233
234 // Slice z1 and z2 into chunks
235 prover_polynomials.z_low_limbs.at(i) = uint256_t(prover_polynomials.x_hi_z_1[i + 1]).slice(0, NUM_LIMB_BITS);
236 prover_polynomials.z_low_limbs.at(i + 1) =
237 uint256_t(prover_polynomials.y_lo_z_2[i + 1]).slice(0, NUM_LIMB_BITS);
238 prover_polynomials.z_high_limbs.at(i) =
239 uint256_t(prover_polynomials.x_hi_z_1[i + 1]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
240 prover_polynomials.z_high_limbs.at(i + 1) =
241 uint256_t(prover_polynomials.y_lo_z_2[i + 1]).slice(NUM_LIMB_BITS, 2 * NUM_LIMB_BITS);
242
243 // Slice accumulator
244 auto tmp = uint256_t(BF::random_element(&engine));
245 prover_polynomials.accumulators_binary_limbs_0.at(i) = tmp.slice(0, NUM_LIMB_BITS);
246 prover_polynomials.accumulators_binary_limbs_1.at(i) = tmp.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2);
247 prover_polynomials.accumulators_binary_limbs_2.at(i) = tmp.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3);
248 prover_polynomials.accumulators_binary_limbs_3.at(i) = tmp.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4);
249
250 // Slice low limbs of P.x into range constraint microlimbs
251 decompose_standard_limb(prover_polynomials.p_x_low_limbs.at(i),
252 prover_polynomials.p_x_low_limbs_range_constraint_0.at(i),
253 prover_polynomials.p_x_low_limbs_range_constraint_1.at(i),
254 prover_polynomials.p_x_low_limbs_range_constraint_2.at(i),
255 prover_polynomials.p_x_low_limbs_range_constraint_3.at(i),
256 prover_polynomials.p_x_low_limbs_range_constraint_4.at(i),
257 prover_polynomials.p_x_low_limbs_range_constraint_tail.at(i));
258
259 decompose_standard_limb(prover_polynomials.p_x_low_limbs.at(i + 1),
260 prover_polynomials.p_x_low_limbs_range_constraint_0.at(i + 1),
261 prover_polynomials.p_x_low_limbs_range_constraint_1.at(i + 1),
262 prover_polynomials.p_x_low_limbs_range_constraint_2.at(i + 1),
263 prover_polynomials.p_x_low_limbs_range_constraint_3.at(i + 1),
264 prover_polynomials.p_x_low_limbs_range_constraint_4.at(i + 1),
265 prover_polynomials.p_x_low_limbs_range_constraint_tail.at(i + 1));
266
267 // Slice high limbs of P.x into range constraint microlimbs
268 decompose_standard_limb(prover_polynomials.p_x_high_limbs.at(i),
269 prover_polynomials.p_x_high_limbs_range_constraint_0.at(i),
270 prover_polynomials.p_x_high_limbs_range_constraint_1.at(i),
271 prover_polynomials.p_x_high_limbs_range_constraint_2.at(i),
272 prover_polynomials.p_x_high_limbs_range_constraint_3.at(i),
273 prover_polynomials.p_x_high_limbs_range_constraint_4.at(i),
274 prover_polynomials.p_x_high_limbs_range_constraint_tail.at(i));
275
276 decompose_standard_top_limb(prover_polynomials.p_x_high_limbs.at(i + 1),
277 prover_polynomials.p_x_high_limbs_range_constraint_0.at(i + 1),
278 prover_polynomials.p_x_high_limbs_range_constraint_1.at(i + 1),
279 prover_polynomials.p_x_high_limbs_range_constraint_2.at(i + 1),
280 prover_polynomials.p_x_high_limbs_range_constraint_3.at(i + 1),
281 prover_polynomials.p_x_high_limbs_range_constraint_4.at(i + 1));
282
283 // Slice low limbs of P.y into range constraint microlimbs
284 decompose_standard_limb(prover_polynomials.p_y_low_limbs.at(i),
285 prover_polynomials.p_y_low_limbs_range_constraint_0.at(i),
286 prover_polynomials.p_y_low_limbs_range_constraint_1.at(i),
287 prover_polynomials.p_y_low_limbs_range_constraint_2.at(i),
288 prover_polynomials.p_y_low_limbs_range_constraint_3.at(i),
289 prover_polynomials.p_y_low_limbs_range_constraint_4.at(i),
290 prover_polynomials.p_y_low_limbs_range_constraint_tail.at(i));
291
292 decompose_standard_limb(prover_polynomials.p_y_low_limbs.at(i + 1),
293 prover_polynomials.p_y_low_limbs_range_constraint_0.at(i + 1),
294 prover_polynomials.p_y_low_limbs_range_constraint_1.at(i + 1),
295 prover_polynomials.p_y_low_limbs_range_constraint_2.at(i + 1),
296 prover_polynomials.p_y_low_limbs_range_constraint_3.at(i + 1),
297 prover_polynomials.p_y_low_limbs_range_constraint_4.at(i + 1),
298 prover_polynomials.p_y_low_limbs_range_constraint_tail.at(i + 1));
299
300 // Slice high limbs of P.y into range constraint microlimbs
301 decompose_standard_limb(prover_polynomials.p_y_high_limbs.at(i),
302 prover_polynomials.p_y_high_limbs_range_constraint_0.at(i),
303 prover_polynomials.p_y_high_limbs_range_constraint_1.at(i),
304 prover_polynomials.p_y_high_limbs_range_constraint_2.at(i),
305 prover_polynomials.p_y_high_limbs_range_constraint_3.at(i),
306 prover_polynomials.p_y_high_limbs_range_constraint_4.at(i),
307 prover_polynomials.p_y_high_limbs_range_constraint_tail.at(i));
308
309 decompose_standard_top_limb(prover_polynomials.p_y_high_limbs.at(i + 1),
310 prover_polynomials.p_y_high_limbs_range_constraint_0.at(i + 1),
311 prover_polynomials.p_y_high_limbs_range_constraint_1.at(i + 1),
312 prover_polynomials.p_y_high_limbs_range_constraint_2.at(i + 1),
313 prover_polynomials.p_y_high_limbs_range_constraint_3.at(i + 1),
314 prover_polynomials.p_y_high_limbs_range_constraint_4.at(i + 1));
315
316 // Slice low limb of of z1 and z2 into range constraints
317 decompose_standard_limb(prover_polynomials.z_low_limbs.at(i),
318 prover_polynomials.z_low_limbs_range_constraint_0.at(i),
319 prover_polynomials.z_low_limbs_range_constraint_1.at(i),
320 prover_polynomials.z_low_limbs_range_constraint_2.at(i),
321 prover_polynomials.z_low_limbs_range_constraint_3.at(i),
322 prover_polynomials.z_low_limbs_range_constraint_4.at(i),
323 prover_polynomials.z_low_limbs_range_constraint_tail.at(i));
324
325 decompose_standard_limb(prover_polynomials.z_low_limbs.at(i + 1),
326 prover_polynomials.z_low_limbs_range_constraint_0.at(i + 1),
327 prover_polynomials.z_low_limbs_range_constraint_1.at(i + 1),
328 prover_polynomials.z_low_limbs_range_constraint_2.at(i + 1),
329 prover_polynomials.z_low_limbs_range_constraint_3.at(i + 1),
330 prover_polynomials.z_low_limbs_range_constraint_4.at(i + 1),
331 prover_polynomials.z_low_limbs_range_constraint_tail.at(i + 1));
332
333 // Slice high limb of of z1 and z2 into range constraints
334 decompose_standard_top_z_limb(prover_polynomials.z_high_limbs.at(i),
335 prover_polynomials.z_high_limbs_range_constraint_0.at(i),
336 prover_polynomials.z_high_limbs_range_constraint_1.at(i),
337 prover_polynomials.z_high_limbs_range_constraint_2.at(i),
338 prover_polynomials.z_high_limbs_range_constraint_3.at(i),
339 prover_polynomials.z_high_limbs_range_constraint_4.at(i),
340 prover_polynomials.z_high_limbs_range_constraint_tail.at(i));
341
342 decompose_standard_top_z_limb(prover_polynomials.z_high_limbs.at(i + 1),
343 prover_polynomials.z_high_limbs_range_constraint_0.at(i + 1),
344 prover_polynomials.z_high_limbs_range_constraint_1.at(i + 1),
345 prover_polynomials.z_high_limbs_range_constraint_2.at(i + 1),
346 prover_polynomials.z_high_limbs_range_constraint_3.at(i + 1),
347 prover_polynomials.z_high_limbs_range_constraint_4.at(i + 1),
348 prover_polynomials.z_high_limbs_range_constraint_tail.at(i + 1));
349
350 // Slice accumulator limbs into range constraints
351 decompose_standard_limb(prover_polynomials.accumulators_binary_limbs_0.at(i),
352 prover_polynomials.accumulator_low_limbs_range_constraint_0.at(i),
353 prover_polynomials.accumulator_low_limbs_range_constraint_1.at(i),
354 prover_polynomials.accumulator_low_limbs_range_constraint_2.at(i),
355 prover_polynomials.accumulator_low_limbs_range_constraint_3.at(i),
356 prover_polynomials.accumulator_low_limbs_range_constraint_4.at(i),
357 prover_polynomials.accumulator_low_limbs_range_constraint_tail.at(i));
358 decompose_standard_limb(prover_polynomials.accumulators_binary_limbs_1.at(i),
359 prover_polynomials.accumulator_low_limbs_range_constraint_0.at(i + 1),
360 prover_polynomials.accumulator_low_limbs_range_constraint_1.at(i + 1),
361 prover_polynomials.accumulator_low_limbs_range_constraint_2.at(i + 1),
362 prover_polynomials.accumulator_low_limbs_range_constraint_3.at(i + 1),
363 prover_polynomials.accumulator_low_limbs_range_constraint_4.at(i + 1),
364 prover_polynomials.accumulator_low_limbs_range_constraint_tail.at(i + 1));
365
366 decompose_standard_limb(prover_polynomials.accumulators_binary_limbs_2.at(i),
367 prover_polynomials.accumulator_high_limbs_range_constraint_0.at(i),
368 prover_polynomials.accumulator_high_limbs_range_constraint_1.at(i),
369 prover_polynomials.accumulator_high_limbs_range_constraint_2.at(i),
370 prover_polynomials.accumulator_high_limbs_range_constraint_3.at(i),
371 prover_polynomials.accumulator_high_limbs_range_constraint_4.at(i),
372 prover_polynomials.accumulator_high_limbs_range_constraint_tail.at(i));
373 decompose_standard_top_limb(prover_polynomials.accumulators_binary_limbs_3.at(i),
374 prover_polynomials.accumulator_high_limbs_range_constraint_0.at(i + 1),
375 prover_polynomials.accumulator_high_limbs_range_constraint_1.at(i + 1),
376 prover_polynomials.accumulator_high_limbs_range_constraint_2.at(i + 1),
377 prover_polynomials.accumulator_high_limbs_range_constraint_3.at(i + 1),
378 prover_polynomials.accumulator_high_limbs_range_constraint_4.at(i + 1));
379
380 // Slice quotient limbs into range constraints
381 decompose_standard_limb(prover_polynomials.quotient_low_binary_limbs.at(i),
382 prover_polynomials.quotient_low_limbs_range_constraint_0.at(i),
383 prover_polynomials.quotient_low_limbs_range_constraint_1.at(i),
384 prover_polynomials.quotient_low_limbs_range_constraint_2.at(i),
385 prover_polynomials.quotient_low_limbs_range_constraint_3.at(i),
386 prover_polynomials.quotient_low_limbs_range_constraint_4.at(i),
387 prover_polynomials.quotient_low_limbs_range_constraint_tail.at(i));
388 decompose_standard_limb(prover_polynomials.quotient_low_binary_limbs_shift.at(i),
389 prover_polynomials.quotient_low_limbs_range_constraint_0.at(i + 1),
390 prover_polynomials.quotient_low_limbs_range_constraint_1.at(i + 1),
391 prover_polynomials.quotient_low_limbs_range_constraint_2.at(i + 1),
392 prover_polynomials.quotient_low_limbs_range_constraint_3.at(i + 1),
393 prover_polynomials.quotient_low_limbs_range_constraint_4.at(i + 1),
394 prover_polynomials.quotient_low_limbs_range_constraint_tail.at(i + 1));
395
396 decompose_standard_limb(prover_polynomials.quotient_high_binary_limbs.at(i),
397 prover_polynomials.quotient_high_limbs_range_constraint_0.at(i),
398 prover_polynomials.quotient_high_limbs_range_constraint_1.at(i),
399 prover_polynomials.quotient_high_limbs_range_constraint_2.at(i),
400 prover_polynomials.quotient_high_limbs_range_constraint_3.at(i),
401 prover_polynomials.quotient_high_limbs_range_constraint_4.at(i),
402 prover_polynomials.quotient_high_limbs_range_constraint_tail.at(i));
403
404 decompose_top_quotient_limb(prover_polynomials.quotient_high_binary_limbs_shift.at(i),
405 prover_polynomials.quotient_high_limbs_range_constraint_0.at(i + 1),
406 prover_polynomials.quotient_high_limbs_range_constraint_1.at(i + 1),
407 prover_polynomials.quotient_high_limbs_range_constraint_2.at(i + 1),
408 prover_polynomials.quotient_high_limbs_range_constraint_3.at(i + 1),
409 prover_polynomials.quotient_high_limbs_range_constraint_4.at(i + 1));
410
411 // Decompose wide relation limbs into range constraints
412 decompose_relation_limb(prover_polynomials.relation_wide_limbs.at(i),
413 prover_polynomials.relation_wide_limbs_range_constraint_0.at(i),
414 prover_polynomials.relation_wide_limbs_range_constraint_1.at(i),
415 prover_polynomials.relation_wide_limbs_range_constraint_2.at(i),
416 prover_polynomials.relation_wide_limbs_range_constraint_3.at(i),
417 prover_polynomials.p_x_high_limbs_range_constraint_tail.at(i + 1),
418 prover_polynomials.accumulator_high_limbs_range_constraint_tail.at(i + 1));
419
420 decompose_relation_limb(prover_polynomials.relation_wide_limbs.at(i + 1),
421 prover_polynomials.relation_wide_limbs_range_constraint_0.at(i + 1),
422 prover_polynomials.relation_wide_limbs_range_constraint_1.at(i + 1),
423 prover_polynomials.relation_wide_limbs_range_constraint_2.at(i + 1),
424 prover_polynomials.relation_wide_limbs_range_constraint_3.at(i + 1),
425 prover_polynomials.p_y_high_limbs_range_constraint_tail.at(i + 1),
426 prover_polynomials.quotient_high_limbs_range_constraint_tail.at(i + 1));
427 }
428
429 // Check that Decomposition relation is satisfied across each row of the prover polynomials
430 RelationChecker<Flavor>::check<TranslatorDecompositionRelation<FF>>(
431 prover_polynomials, params, "TranslatorDecompositionRelation");
432}
433
438TEST_F(TranslatorRelationCorrectnessTests, NonNative)
439{
440 using Flavor = TranslatorFlavor;
441 using Builder = Flavor::CircuitBuilder;
442 using FF = typename Flavor::FF;
443 using BF = typename Flavor::BF;
444 using ProverPolynomials = typename Flavor::ProverPolynomials;
445 using GroupElement = typename Flavor::GroupElement;
446
447 constexpr size_t NUM_LIMB_BITS = Flavor::NUM_LIMB_BITS;
448 constexpr size_t mini_circuit_size = TranslatorFlavor::MINI_CIRCUIT_SIZE;
449 constexpr size_t mini_circuit_size_without_masking =
450 TranslatorFlavor::MINI_CIRCUIT_SIZE - TranslatorFlavor::NUM_MASKED_ROWS_END;
451
452 auto& engine = numeric::get_debug_randomness();
453
454 auto op_queue = std::make_shared<bb::ECCOpQueue>();
455 op_queue->no_op_ultra_only();
456 op_queue->random_op_ultra_only();
457 op_queue->random_op_ultra_only();
458 op_queue->random_op_ultra_only();
459
460 // Generate random EccOpQueue actions
461
462 for (size_t i = 0; i < (mini_circuit_size >> 1) / 2; i++) {
463 switch (engine.get_random_uint8() & 3) {
464 case 0:
465 op_queue->no_op_ultra_only();
466 break;
467 case 1:
468 op_queue->eq_and_reset();
469 break;
470 case 2:
471 op_queue->add_accumulate(GroupElement::random_element(&engine));
472 break;
473 case 3:
474 op_queue->mul_accumulate(GroupElement::random_element(&engine), FF::random_element(&engine));
475 break;
476 }
477 }
478 op_queue->merge();
479 for (size_t i = 0; i < 100; i++) {
480 switch (engine.get_random_uint8() & 3) {
481 case 0:
482 op_queue->no_op_ultra_only();
483 break;
484 case 1:
485 op_queue->eq_and_reset();
486 break;
487 case 2:
488 op_queue->add_accumulate(GroupElement::random_element(&engine));
489 break;
490 case 3:
491 op_queue->mul_accumulate(GroupElement::random_element(&engine), FF::random_element(&engine));
492 break;
493 }
494 }
495 op_queue->random_op_ultra_only();
496 op_queue->random_op_ultra_only();
497 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
498
499 const auto batching_challenge_v = BF::random_element(&engine);
500 const auto evaluation_input_x = BF::random_element(&engine);
501
502 // Generating all the values is pretty tedious, so just use CircuitBuilder
503 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge_v, evaluation_input_x, op_queue);
504
505 // The non-native field relation uses limbs of evaluation_input_x and powers of batching_challenge_v as inputs
506 RelationParameters<FF> params;
507 auto v_power = BF::one();
508 for (size_t i = 0; i < 4 /*Number of powers of v that we need {1,2,3,4}*/; i++) {
509 v_power *= batching_challenge_v;
510 auto uint_v_power = uint256_t(v_power);
511 params.batching_challenge_v.at(i) = { uint_v_power.slice(0, NUM_LIMB_BITS),
512 uint_v_power.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
513 uint_v_power.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
514 uint_v_power.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
515 uint_v_power };
516 }
517 auto uint_input_x = uint256_t(evaluation_input_x);
518 params.evaluation_input_x = { uint_input_x.slice(0, NUM_LIMB_BITS),
519 uint_input_x.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2),
520 uint_input_x.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3),
521 uint_input_x.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4),
522 uint_input_x };
523
524 // Create storage for polynomials
525 ProverPolynomials prover_polynomials = TranslatorFlavor::ProverPolynomials();
526
527 // Copy values of wires used in the non-native field relation from the circuit builder
528 for (size_t i = Builder::NUM_NO_OPS_START + Builder::NUM_RANDOM_OPS_START;
529 i < circuit_builder.num_gates - Builder::NUM_RANDOM_OPS_END;
530 i++) {
531 prover_polynomials.op.at(i) = circuit_builder.get_variable(circuit_builder.wires[circuit_builder.OP][i]);
532 prover_polynomials.p_x_low_limbs.at(i) =
533 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_X_LOW_LIMBS][i]);
534 prover_polynomials.p_x_high_limbs.at(i) =
535 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_X_HIGH_LIMBS][i]);
536 prover_polynomials.p_y_low_limbs.at(i) =
537 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_Y_LOW_LIMBS][i]);
538 prover_polynomials.p_y_high_limbs.at(i) =
539 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.P_Y_HIGH_LIMBS][i]);
540 prover_polynomials.z_low_limbs.at(i) =
541 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.Z_LOW_LIMBS][i]);
542 prover_polynomials.z_high_limbs.at(i) =
543 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.Z_HIGH_LIMBS][i]);
544 prover_polynomials.accumulators_binary_limbs_0.at(i) =
545 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_0][i]);
546 prover_polynomials.accumulators_binary_limbs_1.at(i) =
547 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_1][i]);
548 prover_polynomials.accumulators_binary_limbs_2.at(i) =
549 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_2][i]);
550 prover_polynomials.accumulators_binary_limbs_3.at(i) =
551 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.ACCUMULATORS_BINARY_LIMBS_3][i]);
552 prover_polynomials.quotient_low_binary_limbs.at(i) =
553 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.QUOTIENT_LOW_BINARY_LIMBS][i]);
554 prover_polynomials.quotient_high_binary_limbs.at(i) =
555 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.QUOTIENT_HIGH_BINARY_LIMBS][i]);
556 prover_polynomials.relation_wide_limbs.at(i) =
557 circuit_builder.get_variable(circuit_builder.wires[circuit_builder.RELATION_WIDE_LIMBS][i]);
558 }
559
560 // Fill in lagrange odd polynomial
561 for (size_t i = Flavor::RESULT_ROW; i < mini_circuit_size_without_masking; i += 2) {
562 prover_polynomials.lagrange_even_in_minicircuit.at(i) = 1;
563 prover_polynomials.lagrange_odd_in_minicircuit.at(i + 1) = 1;
564 }
565
566 // Check that Non-Native Field relation is satisfied across each row of the prover polynomials
567 RelationChecker<Flavor>::check<TranslatorNonNativeFieldRelation<FF>>(
568 prover_polynomials, params, "TranslatorNonNativeFieldRelation");
569}
570
571TEST_F(TranslatorRelationCorrectnessTests, ZeroKnowledgePermutation)
572{
573 using Flavor = TranslatorFlavor;
574 using FF = typename Flavor::FF;
575 using ProverPolynomials = typename Flavor::ProverPolynomials;
576
577 const size_t full_circuit_size = Flavor::MINI_CIRCUIT_SIZE * Flavor::INTERLEAVING_GROUP_SIZE;
578 auto& engine = numeric::get_debug_randomness();
579 const size_t full_masking_offset = NUM_DISABLED_ROWS_IN_SUMCHECK * Flavor::INTERLEAVING_GROUP_SIZE;
580
581 TranslatorProvingKey key{};
582 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
583 ProverPolynomials& prover_polynomials = key.proving_key->polynomials;
584 const size_t dyadic_circuit_size_without_masking = full_circuit_size - full_masking_offset;
585
586 // Fill required relation parameters
587 RelationParameters<FF> params{ .beta = FF::random_element(), .gamma = FF::random_element() };
588
589 // Populate the group polynomials with appropriate values and also enough random values to mask their commitment
590 // and evaluation
591 auto fill_polynomial_with_random_14_bit_values = [&](auto& polynomial) {
592 for (size_t i = polynomial.start_index(); i < polynomial.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; i++) {
593 polynomial.at(i) = engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1);
594 }
595 for (size_t i = polynomial.end_index() - NUM_DISABLED_ROWS_IN_SUMCHECK; i < polynomial.end_index(); i++) {
596 polynomial.at(i) = FF::random_element();
597 }
598 };
599
600 for (const auto& group : prover_polynomials.get_groups_to_be_interleaved()) {
601 for (auto& poly : group) {
602 fill_polynomial_with_random_14_bit_values(poly);
603 }
604 }
605
606 // Fill in lagrange polynomials used in the permutation relation
607 prover_polynomials.lagrange_first.at(0) = 1;
608 prover_polynomials.lagrange_real_last.at(dyadic_circuit_size_without_masking - 1) = 1;
609 prover_polynomials.lagrange_last.at(full_circuit_size - 1) = 1;
610 for (size_t i = dyadic_circuit_size_without_masking; i < full_circuit_size; i++) {
611 prover_polynomials.lagrange_masking.at(i) = 1;
612 }
613
614 key.compute_interleaved_polynomials();
615 key.compute_extra_range_constraint_numerator();
616 key.compute_translator_range_constraint_ordered_polynomials();
617
618 // Compute the grand product polynomial
619 compute_grand_product<Flavor, bb::TranslatorPermutationRelation<FF>>(prover_polynomials, params);
620
621 // Check that permutation relation is satisfied across each row of the prover polynomials
622 RelationChecker<Flavor>::check<TranslatorPermutationRelation<FF>>(
623 prover_polynomials, params, "TranslatorPermutationRelation");
624 RelationChecker<Flavor>::check<TranslatorDeltaRangeConstraintRelation<FF>>(
625 prover_polynomials, params, "TranslatorPermutationRelation");
626}
627
628TEST_F(TranslatorRelationCorrectnessTests, ZeroKnowledgeDeltaRange)
629{
630 using Flavor = TranslatorFlavor;
631 using FF = typename Flavor::FF;
632 using ProverPolynomials = typename Flavor::ProverPolynomials;
633 auto& engine = numeric::get_debug_randomness();
634
635 TranslatorProvingKey key;
636 key.proving_key = std::make_shared<typename Flavor::ProvingKey>();
637 ProverPolynomials& prover_polynomials = key.proving_key->polynomials;
638
639 const size_t full_masking_offset = NUM_DISABLED_ROWS_IN_SUMCHECK * Flavor::INTERLEAVING_GROUP_SIZE;
640 const size_t dyadic_circuit_size_without_masking = TranslatorProvingKey::dyadic_circuit_size_without_masking;
641
642 // Construct lagrange polynomials that are needed for Translator's DeltaRangeConstraint Relation
643 prover_polynomials.lagrange_first.at(0) = 0;
644 prover_polynomials.lagrange_real_last.at(dyadic_circuit_size_without_masking - 1) = 1;
645
646 for (size_t i = dyadic_circuit_size_without_masking; i < key.dyadic_circuit_size; i++) {
647 prover_polynomials.lagrange_masking.at(i) = 1;
648 }
649
650 // Create a vector and fill with necessary steps for the DeltaRangeConstraint relation
651 auto sorted_steps = TranslatorProvingKey::get_sorted_steps();
652 std::vector<uint64_t> vector_for_sorting(sorted_steps.begin(), sorted_steps.end());
653
654 // Add random values in the appropriate range to fill the leftover space
655 for (size_t i = sorted_steps.size();
656 i < prover_polynomials.ordered_range_constraints_0.size() - full_masking_offset;
657 i++) {
658 vector_for_sorting.emplace_back(engine.get_random_uint16() & ((1 << Flavor::MICRO_LIMB_BITS) - 1));
659 }
660
661 // Get ordered polynomials
662 auto polynomial_pointers = std::vector{ &prover_polynomials.ordered_range_constraints_0,
663 &prover_polynomials.ordered_range_constraints_1,
664 &prover_polynomials.ordered_range_constraints_2,
665 &prover_polynomials.ordered_range_constraints_3,
666 &prover_polynomials.ordered_range_constraints_4 };
667
668 std::sort(vector_for_sorting.begin(), vector_for_sorting.end());
669
670 // Add masking values
671 for (size_t i = dyadic_circuit_size_without_masking; i < key.dyadic_circuit_size; i++) {
672 vector_for_sorting.emplace_back(FF::random_element());
673 }
674
675 // Copy values, transforming them into Finite Field elements
676 std::transform(vector_for_sorting.cbegin(),
677 vector_for_sorting.cend(),
678 prover_polynomials.ordered_range_constraints_0.coeffs().begin(),
679 [](uint64_t in) { return FF(in); });
680
681 // Copy the same polynomial into the 4 other ordered polynomials (they are not the same in an actual proof, but
682 // we only need to check the correctness of the relation and it acts independently on each polynomial)
683 for (size_t i = 0; i < 4; ++i) {
684 std::copy(prover_polynomials.ordered_range_constraints_0.coeffs().begin(),
685 prover_polynomials.ordered_range_constraints_0.coeffs().end(),
686 polynomial_pointers[i + 1]->coeffs().begin());
687 }
688
689 // Check that DeltaRangeConstraint relation is satisfied across each row of the prover polynomials
690 RelationChecker<Flavor>::check<TranslatorDeltaRangeConstraintRelation<FF>>(
691 prover_polynomials, RelationParameters<FF>(), "TranslatorDeltaRangeConstraintRelation");
692}
bb::ECCOpQueue::OP_QUEUE_SIZE
static const size_t OP_QUEUE_SIZE
Definition ecc_op_queue.hpp:51
bb::ECCVMFlavor::ProverPolynomials
A container for the prover polynomials.
Definition eccvm_flavor.hpp:438
bb::ECCVMFlavor::BF
typename Curve::BaseField BF
Definition eccvm_flavor.hpp:43
bb::MegaFlavor::FF
Curve::ScalarField FF
Definition mega_flavor.hpp:37
bb::MegaFlavor::GroupElement
Curve::Element GroupElement
Definition mega_flavor.hpp:38
bb::MegaFlavor::CircuitBuilder
MegaCircuitBuilder CircuitBuilder
Definition mega_flavor.hpp:35
bb::RelationChecker
A debugging utility for checking whether a set of polynomials satisfies the relations for a given Fla...
Definition relation_checker.hpp:21
bb::Relation
A wrapper for Relations to expose methods used by the Sumcheck prover or verifier to add the contribu...
Definition relation_types.hpp:153
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:660
bb::TranslatorFlavor::MINI_CIRCUIT_SIZE
static constexpr size_t MINI_CIRCUIT_SIZE
Definition translator_flavor.hpp:73
bb::TranslatorFlavor::NUM_MASKED_ROWS_END
static constexpr size_t NUM_MASKED_ROWS_END
Definition translator_flavor.hpp:91
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:108
bb::TranslatorProvingKey::dyadic_circuit_size_without_masking
static constexpr size_t dyadic_circuit_size_without_masking
Definition translator_proving_key.hpp:35
bb::TranslatorProvingKey::proving_key
std::shared_ptr< ProvingKey > proving_key
Definition translator_proving_key.hpp:38
bb::TranslatorProvingKey::dyadic_mini_circuit_size_without_masking
static constexpr size_t dyadic_mini_circuit_size_without_masking
Definition translator_proving_key.hpp:33
bb::group
group class. Represents an elliptic curve group element. Group is parametrised by Fq and Fr
Definition group.hpp:36
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:291
ProverPolynomials
typename ECCVMFlavor::ProverPolynomials ProverPolynomials
Definition eccvm_trace_checker.cpp:16
grand_product_library.hpp
engine
auto & engine
Definition graph_description_protogalaxy.test.cpp:15
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:190
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 acir_format_getters.cpp:6
bb::TEST_F
TEST_F(IPATest, ChallengesAreZero)
Definition ipa.test.cpp:188
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:15
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:19
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:48
bb::RelationParameters::accumulated_result
std::array< T, NUM_BINARY_LIMBS_IN_GOBLIN_TRANSLATOR > accumulated_result
Definition relation_parameters.hpp:42
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:43
translator_flavor.hpp
translator_proving_key.hpp