Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
gas.test.cpp
Go to the documentation of this file.
1#include <gmock/gmock.h>
2#include <gtest/gtest.h>
3
4#include <cstdint>
5
6#include "barretenberg/vm2/common/aztec_constants.hpp"
7#include "barretenberg/vm2/common/tagged_value.hpp"
8#include "barretenberg/vm2/constraining/flavor_settings.hpp"
9#include "barretenberg/vm2/constraining/testing/check_relation.hpp"
10#include "barretenberg/vm2/generated/columns.hpp"
11#include "barretenberg/vm2/generated/relations/gas.hpp"
12#include "barretenberg/vm2/generated/relations/lookups_execution.hpp"
13#include "barretenberg/vm2/testing/fixtures.hpp"
14#include "barretenberg/vm2/testing/macros.hpp"
15#include "barretenberg/vm2/tracegen/execution_trace.hpp"
16#include "barretenberg/vm2/tracegen/lib/lookup_builder.hpp"
17#include "barretenberg/vm2/tracegen/precomputed_trace.hpp"
18#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
19
20namespace bb::avm2::constraining {
21namespace {
22
23using tracegen::ExecutionTraceBuilder;
24using tracegen::PrecomputedTraceBuilder;
25using tracegen::TestTraceContainer;
26using FF = AvmFlavorSettings::FF;
27using C = Column;
28using gas = bb::avm2::gas<FF>;
29using execution = bb::avm2::execution<FF>;
30
31TEST(GasConstrainingTest, EmptyRow)
32{
33 check_relation<gas>(testing::empty_trace());
34}
35
36TEST(GasConstrainingTest, AllSubrelations)
37{
38 uint32_t opcode_l2_gas = 100;
39 uint32_t addressing_gas = 50;
40 uint32_t base_da_gas = 3;
41 uint32_t dynamic_l2_gas = 10;
42 uint32_t dynamic_da_gas = 5;
43 uint32_t dynamic_l2_gas_factor = 2;
44 uint32_t dynamic_da_gas_factor = 1;
45 uint32_t l2_gas_limit = 1000;
46 uint32_t da_gas_limit = 800;
47 uint32_t prev_l2_gas_used = 500;
48 uint32_t prev_da_gas_used = 200;
49 uint64_t limit_used_l2_cmp_diff =
50 l2_gas_limit - (prev_l2_gas_used + opcode_l2_gas + addressing_gas + dynamic_l2_gas * dynamic_l2_gas_factor);
51 uint64_t limit_used_da_cmp_diff =
52 da_gas_limit - (prev_da_gas_used + base_da_gas + dynamic_da_gas * dynamic_da_gas_factor);
53
54 TestTraceContainer trace({ {
55 { C::execution_sel_should_check_gas, 1 },
56 { C::execution_constant_64, 64 },
57 // looked up in execution.pil
58 { C::execution_opcode_gas, opcode_l2_gas },
59 { C::execution_addressing_gas, addressing_gas },
60 { C::execution_base_da_gas, base_da_gas },
61 { C::execution_dynamic_l2_gas, dynamic_l2_gas },
62 { C::execution_dynamic_da_gas, dynamic_da_gas },
63 // event
64 { C::execution_l2_gas_limit, l2_gas_limit },
65 { C::execution_da_gas_limit, da_gas_limit },
66 { C::execution_prev_l2_gas_used, prev_l2_gas_used },
67 { C::execution_prev_da_gas_used, prev_da_gas_used },
68 { C::execution_dynamic_l2_gas_factor, dynamic_l2_gas_factor },
69 { C::execution_dynamic_da_gas_factor, dynamic_da_gas_factor },
70 { C::execution_limit_used_l2_cmp_diff, limit_used_l2_cmp_diff },
71 { C::execution_limit_used_da_cmp_diff, limit_used_da_cmp_diff },
72 // out
73 { C::execution_out_of_gas_l2, 0 },
74 { C::execution_out_of_gas_da, 0 },
75 { C::execution_sel_out_of_gas, 0 },
76 } });
77 check_relation<gas>(trace);
78
79 // Can't cheat OOG.
80 trace.set(0,
81 { {
82 { C::execution_out_of_gas_l2, 0 },
83 { C::execution_out_of_gas_da, 0 },
84 { C::execution_sel_out_of_gas, 1 },
85 } });
86 EXPECT_THROW(check_relation<gas>(trace), std::runtime_error);
87 trace.set(0,
88 { {
89 { C::execution_out_of_gas_l2, 1 },
90 { C::execution_out_of_gas_da, 1 },
91 { C::execution_sel_out_of_gas, 1 },
92 } });
93 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_L2_CMP_DIFF), "L2_CMP_DIFF");
94 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_DA_CMP_DIFF), "DA_CMP_DIFF");
95}
96
97TEST(GasConstrainingTest, LimitDiffs)
98{
99 uint32_t opcode_l2_gas = 100;
100 uint32_t addressing_gas = 50;
101 uint32_t base_da_gas = 3;
102 uint32_t dynamic_l2_gas = 10;
103 uint32_t dynamic_da_gas = 5;
104 uint32_t dynamic_l2_gas_factor = 2;
105 uint32_t dynamic_da_gas_factor = 1;
106 uint32_t l2_gas_limit = 1000;
107 uint32_t da_gas_limit = 800;
108 uint32_t prev_l2_gas_used = 500;
109 uint32_t prev_da_gas_used = 200;
110
111 TestTraceContainer trace({ {
112 { C::execution_sel_should_check_gas, 1 },
113 { C::execution_constant_64, 64 },
114 // looked up in execution.pil
115 { C::execution_opcode_gas, opcode_l2_gas },
116 { C::execution_addressing_gas, addressing_gas },
117 { C::execution_base_da_gas, base_da_gas },
118 { C::execution_dynamic_l2_gas, dynamic_l2_gas },
119 { C::execution_dynamic_da_gas, dynamic_da_gas },
120 // event
121 { C::execution_l2_gas_limit, l2_gas_limit },
122 { C::execution_da_gas_limit, da_gas_limit },
123 { C::execution_prev_l2_gas_used, prev_l2_gas_used },
124 { C::execution_prev_da_gas_used, prev_da_gas_used },
125 { C::execution_dynamic_l2_gas_factor, dynamic_l2_gas_factor },
126 { C::execution_dynamic_da_gas_factor, dynamic_da_gas_factor },
127 { C::execution_limit_used_l2_cmp_diff, 20 }, // Wrong diff.
128 { C::execution_limit_used_da_cmp_diff, 30 }, // Wrong diff.
129 // out
130 { C::execution_out_of_gas_l2, 0 },
131 { C::execution_out_of_gas_da, 0 },
132 { C::execution_sel_out_of_gas, 0 },
133 } });
134 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_L2_CMP_DIFF), "L2_CMP_DIFF");
135 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_DA_CMP_DIFF), "DA_CMP_DIFF");
136}
137
138TEST(GasConstrainingTest, OutOfGasBase)
139{
140 uint32_t opcode_l2_gas = 100;
141 uint32_t addressing_gas = 50;
142 uint32_t base_da_gas = 100;
143 uint32_t dynamic_l2_gas = 0;
144 uint32_t dynamic_da_gas = 0;
145 uint32_t dynamic_l2_gas_factor = 2;
146 uint32_t dynamic_da_gas_factor = 1;
147 uint32_t l2_gas_limit = 100;
148 uint32_t da_gas_limit = 80;
149 uint32_t prev_l2_gas_used = 0;
150 uint32_t prev_da_gas_used = 0;
151 uint64_t limit_used_l2_cmp_diff =
152 (prev_l2_gas_used + opcode_l2_gas + addressing_gas + dynamic_l2_gas * dynamic_l2_gas_factor) - l2_gas_limit - 1;
153 uint64_t limit_used_da_cmp_diff =
154 (prev_da_gas_used + base_da_gas + dynamic_da_gas * dynamic_da_gas_factor) - da_gas_limit - 1;
155
156 TestTraceContainer trace({ {
157 { C::execution_sel_should_check_gas, 1 },
158 { C::execution_constant_64, 64 },
159 // looked up in execution.pil
160 { C::execution_opcode_gas, opcode_l2_gas },
161 { C::execution_addressing_gas, addressing_gas },
162 { C::execution_base_da_gas, base_da_gas },
163 { C::execution_dynamic_l2_gas, dynamic_l2_gas },
164 { C::execution_dynamic_da_gas, dynamic_da_gas },
165 // event
166 { C::execution_l2_gas_limit, l2_gas_limit },
167 { C::execution_da_gas_limit, da_gas_limit },
168 { C::execution_prev_l2_gas_used, prev_l2_gas_used },
169 { C::execution_prev_da_gas_used, prev_da_gas_used },
170 { C::execution_dynamic_l2_gas_factor, dynamic_l2_gas_factor },
171 { C::execution_dynamic_da_gas_factor, dynamic_da_gas_factor },
172 { C::execution_limit_used_l2_cmp_diff, limit_used_l2_cmp_diff },
173 { C::execution_limit_used_da_cmp_diff, limit_used_da_cmp_diff },
174 // out
175 { C::execution_out_of_gas_l2, 1 },
176 { C::execution_out_of_gas_da, 1 },
177 { C::execution_sel_out_of_gas, 1 },
178 } });
179 check_relation<gas>(trace);
180
181 // Can't cheat OOG.
182 trace.set(0,
183 { {
184 { C::execution_out_of_gas_l2, 0 },
185 { C::execution_out_of_gas_da, 0 },
186 { C::execution_sel_out_of_gas, 0 },
187 } });
188 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_L2_CMP_DIFF), "L2_CMP_DIFF");
189 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_DA_CMP_DIFF), "DA_CMP_DIFF");
190}
191
192TEST(GasConstrainingTest, OutOfGasDynamic)
193{
194 uint32_t opcode_l2_gas = 1;
195 uint32_t addressing_gas = 0;
196 uint32_t base_da_gas = 3;
197 uint32_t dynamic_l2_gas = 10;
198 uint32_t dynamic_da_gas = 9;
199 uint32_t dynamic_l2_gas_factor = 10;
200 uint32_t dynamic_da_gas_factor = 10;
201 uint32_t l2_gas_limit = 100;
202 uint32_t da_gas_limit = 80;
203 uint32_t prev_l2_gas_used = 0;
204 uint32_t prev_da_gas_used = 0;
205 uint64_t limit_used_l2_cmp_diff =
206 (prev_l2_gas_used + opcode_l2_gas + addressing_gas + dynamic_l2_gas * dynamic_l2_gas_factor) - l2_gas_limit - 1;
207 uint64_t limit_used_da_cmp_diff =
208 (prev_da_gas_used + base_da_gas + dynamic_da_gas * dynamic_da_gas_factor) - da_gas_limit - 1;
209
210 TestTraceContainer trace({ {
211 { C::execution_sel_should_check_gas, 1 },
212 { C::execution_constant_64, 64 },
213 // looked up in execution.pil
214 { C::execution_opcode_gas, opcode_l2_gas },
215 { C::execution_addressing_gas, addressing_gas },
216 { C::execution_base_da_gas, base_da_gas },
217 { C::execution_dynamic_l2_gas, dynamic_l2_gas },
218 { C::execution_dynamic_da_gas, dynamic_da_gas },
219 // event
220 { C::execution_l2_gas_limit, l2_gas_limit },
221 { C::execution_da_gas_limit, da_gas_limit },
222 { C::execution_prev_l2_gas_used, prev_l2_gas_used },
223 { C::execution_prev_da_gas_used, prev_da_gas_used },
224 { C::execution_dynamic_l2_gas_factor, dynamic_l2_gas_factor },
225 { C::execution_dynamic_da_gas_factor, dynamic_da_gas_factor },
226 { C::execution_limit_used_l2_cmp_diff, limit_used_l2_cmp_diff },
227 { C::execution_limit_used_da_cmp_diff, limit_used_da_cmp_diff },
228 // out
229 { C::execution_out_of_gas_l2, 1 },
230 { C::execution_out_of_gas_da, 1 },
231 { C::execution_sel_out_of_gas, 1 },
232 } });
233 check_relation<gas>(trace);
234
235 // Can't cheat OOG.
236 trace.set(0,
237 { {
238 { C::execution_out_of_gas_l2, 0 },
239 { C::execution_out_of_gas_da, 0 },
240 { C::execution_sel_out_of_gas, 0 },
241 } });
242 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_L2_CMP_DIFF), "L2_CMP_DIFF");
243 EXPECT_THROW_WITH_MESSAGE(check_relation<gas>(trace, gas::SR_DA_CMP_DIFF), "DA_CMP_DIFF");
244}
245
246TEST(GasConstrainingTest, NoCheckNoOOG)
247{
248 TestTraceContainer trace({ {
249 { C::execution_sel_should_check_gas, 0 },
250 // out
251 { C::execution_out_of_gas_l2, 0 },
252 { C::execution_out_of_gas_da, 0 },
253 { C::execution_sel_out_of_gas, 0 },
254 } });
255 check_relation<gas>(trace);
256
257 // Can't cheat OOG.
258 trace.set(0,
259 { {
260 { C::execution_out_of_gas_l2, 1 },
261 { C::execution_out_of_gas_da, 1 },
262 { C::execution_sel_out_of_gas, 1 },
263 } });
264 EXPECT_THROW(check_relation<gas>(trace), std::runtime_error);
265}
266
267TEST(GasConstrainingTest, DynGasFactorBitwise)
268{
269 PrecomputedTraceBuilder precomputed_builder;
270 TestTraceContainer trace({
271 {
272 { C::execution_sel, 1 },
273 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(ValueTag::U16) },
274 { C::execution_sel_gas_bitwise, 1 },
275 { C::execution_dynamic_l2_gas_factor, get_tag_bytes(ValueTag::U16) },
276 },
277 });
278
279 precomputed_builder.process_tag_parameters(trace);
280 precomputed_builder.process_misc(trace, 7); // Need at least clk values from 0-6 for the lookup
281 check_interaction<ExecutionTraceBuilder, lookup_execution_dyn_l2_factor_bitwise_settings>(trace);
282
283 trace.set(C::execution_dynamic_l2_gas_factor, 0, 100); // Set to some random value that can't be looked up
284 EXPECT_THROW_WITH_MESSAGE(
285 (check_interaction<tracegen::ExecutionTraceBuilder, lookup_execution_dyn_l2_factor_bitwise_settings>(trace)),
286 "Failed.*EXECUTION_DYN_L2_FACTOR_BITWISE. Could not find tuple in destination.");
287}
288
289TEST(GasConstrainingTest, DynGasFactorToRadix)
290{
291 PrecomputedTraceBuilder precomputed_builder;
292
293 uint32_t radix = 10;
294 uint32_t num_limbs = 20;
295 uint32_t num_p_limbs = static_cast<uint32_t>(get_p_limbs_per_radix()[radix].size());
296 TestTraceContainer trace(
297 { {
298 { C::execution_sel, 1 },
299 { C::execution_register_1_, radix },
300 { C::execution_register_2_, num_limbs },
301 { C::execution_sel_should_check_gas, 1 },
302 // To Radix BE Dynamic Gas
303 { C::execution_sel_gas_to_radix, 1 },
304 { C::execution_dyn_gas_id, AVM_DYN_GAS_ID_TORADIX },
305 { C::execution_two_five_six, 256 },
306 { C::execution_sel_radix_gt_256, 0 },
307 { C::execution_sel_lookup_num_p_limbs, 1 },
308 { C::execution_num_p_limbs, num_p_limbs },
309 { C::execution_sel_use_num_limbs, num_limbs > num_p_limbs ? 1 : 0 },
310 { C::execution_dynamic_l2_gas_factor, num_limbs > num_p_limbs ? num_limbs : num_p_limbs },
311 // GT Trace, used to check if radix > 256
312 { C::gt_sel, 1 },
313 { C::gt_input_a, radix },
314 { C::gt_input_b, 256 },
315 { C::gt_res, 0 },
316 },
317 {
318 // Gt Trace, compare num_limbs > num_p_limbs
319 { C::gt_sel, 1 },
320 { C::gt_input_a, num_limbs },
321 { C::gt_input_b, num_p_limbs },
322 { C::gt_res, num_limbs > num_p_limbs ? 1 : 0 },
323 } });
324
325 precomputed_builder.process_misc(trace, 257);
326 precomputed_builder.process_to_radix_safe_limbs(trace);
327
328 check_interaction<ExecutionTraceBuilder,
329 lookup_execution_check_radix_gt_256_settings,
330 lookup_execution_get_p_limbs_settings,
331 lookup_execution_get_max_limbs_settings>(trace);
332 check_relation<execution>(trace, execution::SR_DYN_L2_FACTOR_TO_RADIX_BE, execution::SR_DYN_GAS_ID_DECOMPOSITION);
333
334 trace.set(C::execution_dynamic_l2_gas_factor, 0, 100); // Set to some random value is incorrect
335 EXPECT_THROW_WITH_MESSAGE((check_relation<execution>(trace, execution::SR_DYN_L2_FACTOR_TO_RADIX_BE)),
336 ".*subrelation DYN_L2_FACTOR_TO_RADIX_BE failed.*");
337}
338
339TEST(GasConstrainingTest, DynGasFactorInvalidRadix)
340{
341 PrecomputedTraceBuilder precomputed_builder;
342
343 uint32_t radix = 1000;
344 uint32_t num_limbs = 20;
345 uint32_t num_p_limbs = 32; // When radix > 256, we set num_p_limbs to 32.
346 TestTraceContainer trace(
347 { {
348 { C::execution_sel, 1 },
349 { C::execution_register_1_, radix },
350 { C::execution_register_2_, num_limbs },
351 { C::execution_sel_should_check_gas, 1 },
352 // To Radix BE Dynamic Gas
353 { C::execution_sel_gas_to_radix, 1 },
354 { C::execution_dyn_gas_id, AVM_DYN_GAS_ID_TORADIX },
355 { C::execution_two_five_six, 256 },
356 { C::execution_sel_radix_gt_256, radix > 256 ? 1 : 0 },
357 { C::execution_sel_lookup_num_p_limbs, radix <= 256 ? 1 : 0 },
358 { C::execution_num_p_limbs, num_p_limbs },
359 { C::execution_sel_use_num_limbs, num_limbs > num_p_limbs ? 1 : 0 },
360 { C::execution_dynamic_l2_gas_factor, num_limbs > num_p_limbs ? num_limbs : num_p_limbs },
361 // GT Trace, used to check if radix > 256
362 { C::gt_sel, 1 },
363 { C::gt_input_a, radix },
364 { C::gt_input_b, 256 },
365 { C::gt_res, radix > 256 ? 1 : 0 },
366 },
367 {
368 // Gt Trace, compare num_limbs > num_p_limbs
369 { C::gt_sel, 1 },
370 { C::gt_input_a, num_limbs },
371 { C::gt_input_b, num_p_limbs },
372 { C::gt_res, num_limbs > num_p_limbs ? 1 : 0 },
373 } });
374
375 precomputed_builder.process_misc(trace, 257);
376 precomputed_builder.process_to_radix_safe_limbs(trace);
377
378 check_interaction<ExecutionTraceBuilder,
379 lookup_execution_check_radix_gt_256_settings,
380 lookup_execution_get_p_limbs_settings,
381 lookup_execution_get_max_limbs_settings>(trace);
382 check_relation<execution>(trace,
383 execution::SR_NUM_P_LIMBS_CEIL,
384 execution::SR_DYN_L2_FACTOR_TO_RADIX_BE,
385 execution::SR_DYN_GAS_ID_DECOMPOSITION);
386}
387
388} // namespace
389} // namespace bb::avm2::constraining
aztec_constants.hpp
AVM_DYN_GAS_ID_TORADIX
#define AVM_DYN_GAS_ID_TORADIX
Definition aztec_constants.hpp:63
check_relation.hpp
bb::avm2::execution::SR_DYN_L2_FACTOR_TO_RADIX_BE
static constexpr size_t SR_DYN_L2_FACTOR_TO_RADIX_BE
Definition execution.hpp:114
bb::avm2::execution::SR_DYN_GAS_ID_DECOMPOSITION
static constexpr size_t SR_DYN_GAS_ID_DECOMPOSITION
Definition execution.hpp:118
bb::avm2::execution::SR_NUM_P_LIMBS_CEIL
static constexpr size_t SR_NUM_P_LIMBS_CEIL
Definition execution.hpp:113
bb::avm2::gas::SR_DA_CMP_DIFF
static constexpr size_t SR_DA_CMP_DIFF
Definition gas.hpp:50
bb::avm2::gas::SR_L2_CMP_DIFF
static constexpr size_t SR_L2_CMP_DIFF
Definition gas.hpp:49
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:36
precomputed_builder
PrecomputedTraceBuilder precomputed_builder
Definition alu.test.cpp:119
trace
TestTraceContainer trace
Definition data_copy.test.cpp:59
execution_trace.hpp
flavor_settings.hpp
lookup_builder.hpp
lookups_execution.hpp
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessage)
Definition macros.hpp:7
bb::avm2::constraining::check_interaction
void check_interaction(tracegen::TestTraceContainer &trace)
Definition check_relation.hpp:76
bb::avm2::constraining::TEST
TEST(TxExecutionConstrainingTest, WriteTreeValue)
Definition tx.test.cpp:508
bb::avm2::testing::empty_trace
TestTraceContainer empty_trace()
Definition fixtures.cpp:153
bb::avm2::get_p_limbs_per_radix
const std::array< std::vector< uint8_t >, 257 > & get_p_limbs_per_radix()
Definition to_radix.cpp:33
bb::avm2::lookup_execution_get_p_limbs_settings
lookup_settings< lookup_execution_get_p_limbs_settings_ > lookup_execution_get_p_limbs_settings
Definition lookups_execution.hpp:281
bb::avm2::lookup_execution_check_radix_gt_256_settings
lookup_settings< lookup_execution_check_radix_gt_256_settings_ > lookup_execution_check_radix_gt_256_settings
Definition lookups_execution.hpp:258
bb::avm2::lookup_execution_get_max_limbs_settings
lookup_settings< lookup_execution_get_max_limbs_settings_ > lookup_execution_get_max_limbs_settings
Definition lookups_execution.hpp:305
bb::avm2::get_tag_bytes
uint8_t get_tag_bytes(ValueTag tag)
Definition tagged_value.cpp:174
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:16
precomputed_trace.hpp
tagged_value.hpp
test_trace_container.hpp
execution
NiceMock< MockExecution > execution
Definition tx_execution.test.cpp:30