Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
field_gt.test.cpp
Go to the documentation of this file.
1#include <gmock/gmock.h>
2#include <gtest/gtest.h>
3
20
21namespace bb::avm2::constraining {
22namespace {
23
24using ::testing::NiceMock;
25using ::testing::TestWithParam;
26
27using tracegen::FieldGreaterThanTraceBuilder;
28using tracegen::RangeCheckTraceBuilder;
29using tracegen::TestTraceContainer;
30
31using simulation::EventEmitter;
32using simulation::FieldGreaterThan;
33using simulation::FieldGreaterThanEvent;
34using simulation::MockRangeCheck;
35using simulation::RangeCheck;
36using simulation::RangeCheckEvent;
37using simulation::U256Decomposition;
38
40using C = Column;
41using ff_gt = bb::avm2::ff_gt<FF>;
42
43const uint256_t TWO_POW_128 = uint256_t{ 1 } << 128;
44
45TEST(FieldGreaterThanConstrainingTest, EmptyRow)
46{
47 check_relation<ff_gt>(testing::empty_trace());
48}
49
50struct GtTestParams {
54};
55struct DecTestParams {
56 FF a;
57 U256Decomposition expected_result;
58};
59
60std::vector<GtTestParams> comparison_tests = {
61 // GT
62 GtTestParams{ 27, 0, true },
63 GtTestParams{ TWO_POW_128, 0, true },
64 GtTestParams{ -1, 0, true },
65 // EQ
66 GtTestParams{ 27, 27, false },
67 GtTestParams{ TWO_POW_128, TWO_POW_128, false },
68 GtTestParams{ -1, -1, false },
69 // LT
70 GtTestParams{ 0, 1, false },
71 GtTestParams{ 0, TWO_POW_128, false },
72 GtTestParams{ 0, -1, false }
73};
74
75std::vector<DecTestParams> decomposition_tests = {
76 DecTestParams{ 0, { .lo = 0, .hi = 0 } },
77 DecTestParams{ 1, { .lo = 1, .hi = 0 } },
78 DecTestParams{ uint256_t(1) << 128, { .lo = 0, .hi = 1 } },
79 DecTestParams{ (uint256_t(1) << 200) - 1,
80 { .lo = static_cast<uint128_t>((uint256_t(1) << 128) - 1), .hi = (uint128_t(1) << 72) - 1 } },
81};
82
83class GtBasicTest : public TestWithParam<GtTestParams> {};
84
85TEST_P(GtBasicTest, BasicComparison)
86{
87 const auto& param = GetParam();
88
89 NiceMock<MockRangeCheck> range_check;
90 EventEmitter<FieldGreaterThanEvent> event_emitter;
91 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
92
93 EXPECT_EQ(field_gt_simulator.ff_gt(param.a, param.b), param.expected_result);
94
95 TestTraceContainer trace = TestTraceContainer::from_rows({
96 { .precomputed_first_row = 1 },
97 });
98
99 FieldGreaterThanTraceBuilder builder;
100 builder.process(event_emitter.dump_events(), trace);
101 EXPECT_EQ(trace.get_num_rows(), /*start_row=*/1 + 5);
102 check_relation<ff_gt>(trace);
103}
104
105INSTANTIATE_TEST_SUITE_P(FieldGreaterThanConstrainingTest, GtBasicTest, ::testing::ValuesIn(comparison_tests));
106
107class DecBasicTest : public TestWithParam<DecTestParams> {};
108
109TEST_P(DecBasicTest, BasicDecomposition)
110{
111 const auto& param = GetParam();
112
113 NiceMock<MockRangeCheck> range_check;
114 EventEmitter<FieldGreaterThanEvent> event_emitter;
115 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
116
117 EXPECT_EQ(field_gt_simulator.canon_dec(param.a), param.expected_result);
118
119 TestTraceContainer trace = TestTraceContainer::from_rows({
120 { .precomputed_first_row = 1 },
121 });
122
123 FieldGreaterThanTraceBuilder builder;
124 builder.process(event_emitter.dump_events(), trace);
125 EXPECT_EQ(trace.get_num_rows(), /*start_row=*/1 + 2);
126 check_relation<ff_gt>(trace);
127}
128
129INSTANTIATE_TEST_SUITE_P(FieldGreaterThanConstrainingTest, DecBasicTest, ::testing::ValuesIn(decomposition_tests));
130
131class GtInteractionTests : public TestWithParam<GtTestParams> {};
132
133TEST_P(GtInteractionTests, InteractionsWithRangeCheck)
134{
135 const auto& param = GetParam();
136
137 EventEmitter<RangeCheckEvent> range_check_event_emitter;
139 EventEmitter<FieldGreaterThanEvent> event_emitter;
140 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
141
142 EXPECT_EQ(field_gt_simulator.ff_gt(param.a, param.b), param.expected_result);
143
144 TestTraceContainer trace = TestTraceContainer::from_rows({
145 { .precomputed_first_row = 1 },
146 });
147
148 FieldGreaterThanTraceBuilder builder;
149 RangeCheckTraceBuilder range_check_builder;
150
151 builder.process(event_emitter.dump_events(), trace);
153
154 check_interaction<FieldGreaterThanTraceBuilder, //
157
158 check_relation<ff_gt>(trace);
159}
160
161INSTANTIATE_TEST_SUITE_P(FieldGreaterThanConstrainingTest, GtInteractionTests, ::testing::ValuesIn(comparison_tests));
162
163class DecInteractionTests : public TestWithParam<DecTestParams> {};
164
165TEST_P(DecInteractionTests, InteractionsWithRangeCheck)
166{
167 const auto& param = GetParam();
168
169 EventEmitter<RangeCheckEvent> range_check_event_emitter;
171 EventEmitter<FieldGreaterThanEvent> event_emitter;
172 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
173
174 EXPECT_EQ(field_gt_simulator.canon_dec(param.a), param.expected_result);
175
176 TestTraceContainer trace = TestTraceContainer::from_rows({
177 { .precomputed_first_row = 1 },
178 });
179
180 FieldGreaterThanTraceBuilder builder;
181 RangeCheckTraceBuilder range_check_builder;
182
183 builder.process(event_emitter.dump_events(), trace);
185
186 check_interaction<FieldGreaterThanTraceBuilder, //
189
190 check_relation<ff_gt>(trace);
191}
192
193INSTANTIATE_TEST_SUITE_P(FieldGreaterThanConstrainingTest,
194 DecInteractionTests,
195 ::testing::ValuesIn(decomposition_tests));
196
197TEST(FieldGreaterThanConstrainingTest, NegativeManipulatedDecompositions)
198{
199 NiceMock<MockRangeCheck> range_check;
200 EventEmitter<FieldGreaterThanEvent> event_emitter;
201 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
202
203 field_gt_simulator.ff_gt(0, 0);
204
205 TestTraceContainer trace = TestTraceContainer::from_rows({
206 { .precomputed_first_row = 1 },
207 });
208
209 FieldGreaterThanTraceBuilder builder;
210 builder.process(event_emitter.dump_events(), trace);
211 check_relation<ff_gt>(trace);
212
213 trace.set(Column::ff_gt_a_lo, 1, 1);
214 trace.set(Column::ff_gt_b_hi, 1, 1);
215
216 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_A_DECOMPOSITION), "A_DECOMPOSITION");
217 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_B_DECOMPOSITION), "B_DECOMPOSITION");
218}
219
220TEST(FieldGreaterThanConstrainingTest, NegativeManipulatedComparisonsWithP)
221{
222 NiceMock<MockRangeCheck> range_check;
223 EventEmitter<FieldGreaterThanEvent> event_emitter;
224 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
225
226 field_gt_simulator.ff_gt(0, 0);
227
228 TestTraceContainer trace = TestTraceContainer::from_rows({
229 { .precomputed_first_row = 1 },
230 });
231
232 FieldGreaterThanTraceBuilder builder;
233 builder.process(event_emitter.dump_events(), trace);
234 check_relation<ff_gt>(trace);
235
236 auto p_limbs = simulation::decompose(FF::modulus);
237 uint256_t p_lo = uint256_t::from_uint128(p_limbs.lo);
238 uint256_t p_hi = uint256_t::from_uint128(p_limbs.hi);
239
240 // Manipulate the decomposition in a way that passes the decomposition check due to overflow
241 trace.set(Column::ff_gt_a_lo, 1, p_lo);
242 trace.set(Column::ff_gt_a_hi, 1, p_hi);
243 trace.set(Column::ff_gt_b_lo, 1, p_lo);
244 trace.set(Column::ff_gt_b_hi, 1, p_hi);
245
246 trace.set(Column::ff_gt_p_sub_a_hi, 1, p_lo - 1);
247 trace.set(Column::ff_gt_p_sub_a_lo, 1, p_hi - 1);
248 trace.set(Column::ff_gt_p_sub_b_hi, 1, p_lo - 1);
249 trace.set(Column::ff_gt_p_sub_b_lo, 1, p_hi - 1);
250
251 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_P_SUB_A_LO), "P_SUB_A_LO");
252 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_P_SUB_A_HI), "P_SUB_A_HI");
253 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_P_SUB_B_LO), "P_SUB_B_LO");
254 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_P_SUB_B_HI), "P_SUB_B_HI");
255}
256
257TEST(FieldGreaterThanConstrainingTest, NegativeLessRangeChecks)
258{
259 NiceMock<MockRangeCheck> range_check;
260 EventEmitter<FieldGreaterThanEvent> event_emitter;
261 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
262
263 field_gt_simulator.ff_gt(0, 0);
264
265 TestTraceContainer trace = TestTraceContainer::from_rows({
266 { .precomputed_first_row = 1 },
267 });
268
269 FieldGreaterThanTraceBuilder builder;
270 builder.process(event_emitter.dump_events(), trace);
271 check_relation<ff_gt>(trace);
272
273 trace.set(Column::ff_gt_cmp_rng_ctr, 1, 3);
274 trace.set(Column::ff_gt_cmp_rng_ctr, 2, 0);
275
276 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_RNG_CTR_GT_INIT), "RNG_CTR_GT_INIT");
277 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_RNG_CTR_DECREMENT), "RNG_CTR_DECREMENT");
278}
279
280TEST(FieldGreaterThanConstrainingTest, NegativeRangeCheckCtrInitInDec)
281{
282 NiceMock<MockRangeCheck> range_check;
283 EventEmitter<FieldGreaterThanEvent> event_emitter;
284 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
285
286 field_gt_simulator.canon_dec(0);
287
288 TestTraceContainer trace = TestTraceContainer::from_rows({
289 { .precomputed_first_row = 1 },
290 });
291
292 FieldGreaterThanTraceBuilder builder;
293 builder.process(event_emitter.dump_events(), trace);
294 check_relation<ff_gt>(trace);
295
296 trace.set(Column::ff_gt_cmp_rng_ctr, 1, 4);
297 trace.set(Column::ff_gt_cmp_rng_ctr, 2, 2);
298
299 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_RNG_CTR_DEC_INIT), "RNG_CTR_DEC_INIT");
300 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_RNG_CTR_DECREMENT), "RNG_CTR_DECREMENT");
301}
302
303TEST(FieldGreaterThanConstrainingTest, NegativeSelectorConsistency)
304{
305 NiceMock<MockRangeCheck> range_check;
306 EventEmitter<FieldGreaterThanEvent> event_emitter;
307 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
308
309 field_gt_simulator.ff_gt(0, 0);
310
311 TestTraceContainer trace = TestTraceContainer::from_rows({
312 { .precomputed_first_row = 1 },
313 });
314
315 FieldGreaterThanTraceBuilder builder;
316 builder.process(event_emitter.dump_events(), trace);
317 check_relation<ff_gt>(trace);
318
319 // Disable the selector after the first row
320 trace.set(Column::ff_gt_sel, 2, 0);
321
322 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_SEL_CONSISTENCY), "SEL_CONSISTENCY");
323}
324
325TEST(FieldGreaterThanConstrainingTest, NegativeEraseShift)
326{
327 NiceMock<MockRangeCheck> range_check;
328 EventEmitter<FieldGreaterThanEvent> event_emitter;
329 FieldGreaterThan field_gt_simulator(range_check, event_emitter);
330
331 field_gt_simulator.ff_gt(42, 27);
332
333 TestTraceContainer trace = TestTraceContainer::from_rows({
334 { .precomputed_first_row = 1 },
335 });
336
337 FieldGreaterThanTraceBuilder builder;
338 builder.process(event_emitter.dump_events(), trace);
339 check_relation<ff_gt>(trace);
340
341 trace.set(Column::ff_gt_a_lo, 2, 0);
342 trace.set(Column::ff_gt_a_hi, 2, 0);
343 trace.set(Column::ff_gt_p_sub_a_lo, 2, 0);
344 trace.set(Column::ff_gt_p_sub_a_hi, 2, 0);
345 trace.set(Column::ff_gt_b_lo, 2, 0);
346 trace.set(Column::ff_gt_b_hi, 2, 0);
347 trace.set(Column::ff_gt_p_sub_b_lo, 2, 0);
348 trace.set(Column::ff_gt_p_sub_b_hi, 2, 0);
349
350 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_SHIFT_0), "SHIFT_0");
351 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_SHIFT_1), "SHIFT_1");
352 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_SHIFT_2), "SHIFT_2");
353 EXPECT_THROW_WITH_MESSAGE(check_relation<ff_gt>(trace, ff_gt::SR_SHIFT_3), "SHIFT_3");
354}
355
356} // namespace
357} // namespace bb::avm2::constraining
INSTANTIATE_TEST_SUITE_P(AcirTests, AcirIntegrationSingleTest, testing::Values("a_1327_concrete_in_generic", "a_1_mul", "a_2_div", "a_3_add", "a_4_sub", "a_5_over", "a_6", "a_6_array", "a_7", "a_7_function", "aes128_encrypt", "arithmetic_binary_operations", "array_dynamic", "array_dynamic_blackbox_input", "array_dynamic_main_output", "array_dynamic_nested_blackbox_input", "array_eq", "array_if_cond_simple", "array_len", "array_neq", "array_sort", "array_to_slice", "array_to_slice_constant_length", "assert", "assert_statement", "assign_ex", "bigint", "bit_and", "bit_not", "bit_shifts_comptime", "bit_shifts_runtime", "blake3", "bool_not", "bool_or", "break_and_continue", "brillig_acir_as_brillig", "brillig_array_eq", "brillig_array_to_slice", "brillig_arrays", "brillig_assert", "brillig_bit_shifts_runtime", "brillig_blake2s", "brillig_blake3", "brillig_calls", "brillig_calls_array", "brillig_calls_conditionals", "brillig_conditional", "brillig_cow", "brillig_cow_assign", "brillig_cow_regression", "brillig_ecdsa_secp256k1", "brillig_ecdsa_secp256r1", "brillig_embedded_curve", "brillig_fns_as_values", "brillig_hash_to_field", "brillig_identity_function", "brillig_keccak", "brillig_loop", "brillig_nested_arrays", "brillig_not", "brillig_oracle", "brillig_pedersen", "brillig_recursion", "brillig_references", "brillig_schnorr", "brillig_sha256", "brillig_signed_cmp", "brillig_signed_div", "brillig_slices", "brillig_to_be_bytes", "brillig_to_bits", "brillig_to_bytes_integration", "brillig_to_le_bytes", "brillig_top_level", "brillig_uninitialized_arrays", "brillig_wrapping", "cast_bool", "closures_mut_ref", "conditional_1", "conditional_2", "conditional_regression_421", "conditional_regression_547", "conditional_regression_661", "conditional_regression_short_circuit", "conditional_regression_underflow", "custom_entry", "databus", "debug_logs", "diamond_deps_0", "double_verify_nested_proof", "double_verify_proof", "ecdsa_secp256k1", "ecdsa_secp256r1", "ecdsa_secp256r1_3x", "eddsa", "embedded_curve_ops", "field_attribute", "generics", "global_consts", "hash_to_field", "hashmap", "higher_order_functions", "if_else_chain", "import", "inline_never_basic", "integer_array_indexing", "keccak256", "main_bool_arg", "main_return", "merkle_insert", "missing_closure_env", "modules", "modules_more", "modulus", "nested_array_dynamic", "nested_array_dynamic_simple", "nested_array_in_slice", "nested_arrays_from_brillig", "no_predicates_basic", "no_predicates_brillig", "no_predicates_numeric_generic_poseidon", "operator_overloading", "pedersen_check", "pedersen_commitment", "pedersen_hash", "poseidon_bn254_hash", "poseidonsponge_x5_254", "pred_eq", "prelude", "references", "regression", "regression_2660", "regression_3051", "regression_3394", "regression_3607", "regression_3889", "regression_4088", "regression_4124", "regression_4202", "regression_4449", "regression_4709", "regression_5045", "regression_capacity_tracker", "regression_mem_op_predicate", "regression_method_cannot_be_found", "regression_struct_array_conditional", "schnorr", "sha256", "sha2_byte", "side_effects_constrain_array", "signed_arithmetic", "signed_comparison", "signed_division", "simple_2d_array", "simple_add_and_ret_arr", "simple_array_param", "simple_bitwise", "simple_comparison", "simple_mut", "simple_not", "simple_print", "simple_program_addition", "simple_radix", "simple_shield", "simple_shift_left_right", "slice_coercion", "slice_dynamic_index", "slice_loop", "slices", "strings", "struct", "struct_array_inputs", "struct_fields_ordering", "struct_inputs", "submodules", "to_be_bytes", "to_bytes_consistent", "to_bytes_integration", "to_le_bytes", "trait_as_return_type", "trait_impl_base_type", "traits_in_crates_1", "traits_in_crates_2", "tuple_inputs", "tuples", "type_aliases", "u128", "u16_support", "unconstrained_empty", "unit_value", "unsafe_range_constraint", "witness_compression", "xor"))
TEST_P(AcirIntegrationSingleTest, DISABLED_ProveAndVerifyProgram)
static constexpr size_t SR_P_SUB_B_LO
Definition ff_gt.hpp:84
static constexpr size_t SR_RNG_CTR_GT_INIT
Definition ff_gt.hpp:88
static constexpr size_t SR_SEL_CONSISTENCY
Definition ff_gt.hpp:96
static constexpr size_t SR_RNG_CTR_DECREMENT
Definition ff_gt.hpp:90
static constexpr size_t SR_P_SUB_A_LO
Definition ff_gt.hpp:81
static constexpr size_t SR_SHIFT_2
Definition ff_gt.hpp:94
static constexpr size_t SR_B_DECOMPOSITION
Definition ff_gt.hpp:83
static constexpr size_t SR_P_SUB_B_HI
Definition ff_gt.hpp:85
static constexpr size_t SR_SHIFT_1
Definition ff_gt.hpp:93
static constexpr size_t SR_SHIFT_3
Definition ff_gt.hpp:95
static constexpr size_t SR_SHIFT_0
Definition ff_gt.hpp:92
static constexpr size_t SR_P_SUB_A_HI
Definition ff_gt.hpp:82
static constexpr size_t SR_A_DECOMPOSITION
Definition ff_gt.hpp:80
static constexpr size_t SR_RNG_CTR_DEC_INIT
Definition ff_gt.hpp:89
static TestTraceContainer from_rows(const std::vector< AvmFullRow > &rows)
void set(Column col, uint32_t row, const FF &value)
static constexpr uint256_t from_uint128(const uint128_t a) noexcept
Definition uint256.hpp:94
RangeCheckTraceBuilder range_check_builder
Definition alu.test.cpp:120
AluTraceBuilder builder
Definition alu.test.cpp:123
EventEmitter< RangeCheckEvent > range_check_event_emitter
EventEmitter< DataCopyEvent > event_emitter
RangeCheck range_check
TestTraceContainer trace
FF a
FF b
bool expected_result
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessage)
Definition macros.hpp:7
void check_interaction(tracegen::TestTraceContainer &trace)
TEST(TxExecutionConstrainingTest, WriteTreeValue)
Definition tx.test.cpp:508
U256Decomposition decompose(const uint256_t &x)
const uint256_t TWO_POW_128
TestTraceContainer empty_trace()
Definition fixtures.cpp:153
lookup_settings< lookup_ff_gt_a_lo_range_settings_ > lookup_ff_gt_a_lo_range_settings
lookup_settings< lookup_ff_gt_a_hi_range_settings_ > lookup_ff_gt_a_hi_range_settings
typename Flavor::FF FF
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
unsigned __int128 uint128_t
Definition serialize.hpp:44