Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
keccakf1600_trace.test.cpp
Go to the documentation of this file.
1#include <algorithm>
2#include <gmock/gmock.h>
3#include <gtest/gtest.h>
4
5#include "barretenberg/vm2/common/aztec_constants.hpp"
6#include "barretenberg/vm2/common/constants.hpp"
7#include "barretenberg/vm2/common/memory_types.hpp"
8#include "barretenberg/vm2/simulation/events/keccakf1600_event.hpp"
9#include "barretenberg/vm2/simulation/gadgets/keccakf1600.hpp"
10#include "barretenberg/vm2/testing/keccakf1600_fixture.test.hpp"
11#include "barretenberg/vm2/testing/macros.hpp"
12#include "barretenberg/vm2/tracegen/keccakf1600_trace.hpp"
13#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
14
15namespace bb::avm2::tracegen {
16namespace {
17
18using ::testing::Field;
19
20using R = TestTraceContainer::Row;
21using C = Column;
22
23simulation::KeccakF1600Event create_standard_event_mem_slice()
24{
25 simulation::KeccakF1600Event event;
26 event.src_addr = 100;
27 event.dst_addr = 200;
28 event.space_id = 23;
29
30 // Initialize source memory values with U64 tags and state values
31 for (size_t i = 0; i < 5; i++) {
32 for (size_t j = 0; j < 5; j++) {
33 const uint64_t input_value = (i * 5 + j) + 1000;
34 const uint64_t output_value = (i * 5 + j) + 10000;
35 event.src_mem_values[i][j] = MemoryValue::from<uint64_t>(input_value);
36 event.rounds[0].state[i][j] = input_value;
37 if (i == 0 && j == 0) {
38 event.rounds[AVM_KECCAKF1600_NUM_ROUNDS - 1].state_iota_00 = output_value;
39 } else {
40 event.rounds[AVM_KECCAKF1600_NUM_ROUNDS - 1].state_chi[i][j] = output_value;
41 }
42 }
43 }
44
45 return event;
46}
47
48TEST(KeccakF1600TraceGenTest, MemorySliceReadAndWrite)
49{
50 TestTraceContainer trace;
51 KeccakF1600TraceBuilder builder;
52
53 // Create a standard event
54 auto event = create_standard_event_mem_slice();
55
56 // Process the event
57 builder.process_memory_slices({ event }, trace);
58
59 // Get the rows
60 auto rows = trace.as_rows();
61
62 // Check that we have the correct number of rows (2 * AVM_KECCAKF1600_STATE_SIZE for read and write)
63 ASSERT_EQ(rows.size(), 2 * AVM_KECCAKF1600_STATE_SIZE + 1); // +1 for the initial empty row
64
65 // Check the first row of the read operation
66 EXPECT_THAT(rows.at(1),
67 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
68 ROW_FIELD_EQ(keccak_memory_ctr, 1),
69 ROW_FIELD_EQ(keccak_memory_start_read, 1),
70 ROW_FIELD_EQ(keccak_memory_start_write, 0),
71 ROW_FIELD_EQ(keccak_memory_last, 0),
72 ROW_FIELD_EQ(keccak_memory_ctr_end, 0),
73 ROW_FIELD_EQ(keccak_memory_rw, 0),
74 ROW_FIELD_EQ(keccak_memory_addr, 100),
75 ROW_FIELD_EQ(keccak_memory_space_id, 23),
76 ROW_FIELD_EQ(keccak_memory_val00, 1000),
77 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
78 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
79 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
80 ROW_FIELD_EQ(keccak_memory_ctr_inv, 1),
81 ROW_FIELD_EQ(keccak_memory_state_size_min_ctr_inv, (FF(AVM_KECCAKF1600_STATE_SIZE - 1)).invert()),
82 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 0)));
83
84 // Check the last row of the read operation
85 EXPECT_THAT(rows.at(AVM_KECCAKF1600_STATE_SIZE),
86 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
87 ROW_FIELD_EQ(keccak_memory_ctr, AVM_KECCAKF1600_STATE_SIZE),
88 ROW_FIELD_EQ(keccak_memory_start_read, 0),
89 ROW_FIELD_EQ(keccak_memory_start_write, 0),
90 ROW_FIELD_EQ(keccak_memory_last, 1),
91 ROW_FIELD_EQ(keccak_memory_ctr_end, 1),
92 ROW_FIELD_EQ(keccak_memory_rw, 0),
93 ROW_FIELD_EQ(keccak_memory_addr, 100 + AVM_KECCAKF1600_STATE_SIZE - 1),
94 ROW_FIELD_EQ(keccak_memory_space_id, 23),
95 ROW_FIELD_EQ(keccak_memory_val00, 1000 + AVM_KECCAKF1600_STATE_SIZE - 1),
96 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
97 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
98 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
99 ROW_FIELD_EQ(keccak_memory_ctr_inv, FF(AVM_KECCAKF1600_STATE_SIZE).invert()),
100 ROW_FIELD_EQ(keccak_memory_state_size_min_ctr_inv, 0),
101 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 0)));
102
103 // Check the first row of the write operation (after read operation)
104 EXPECT_THAT(rows.at(AVM_KECCAKF1600_STATE_SIZE + 1),
105 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
106 ROW_FIELD_EQ(keccak_memory_ctr, 1),
107 ROW_FIELD_EQ(keccak_memory_start_read, 0),
108 ROW_FIELD_EQ(keccak_memory_start_write, 1),
109 ROW_FIELD_EQ(keccak_memory_last, 0),
110 ROW_FIELD_EQ(keccak_memory_ctr_end, 0),
111 ROW_FIELD_EQ(keccak_memory_rw, 1),
112 ROW_FIELD_EQ(keccak_memory_addr, 200),
113 ROW_FIELD_EQ(keccak_memory_space_id, 23),
114 ROW_FIELD_EQ(keccak_memory_val00, 10000),
115 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
116 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
117 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
118 ROW_FIELD_EQ(keccak_memory_ctr_inv, 1),
119 ROW_FIELD_EQ(keccak_memory_state_size_min_ctr_inv, (FF(AVM_KECCAKF1600_STATE_SIZE - 1)).invert()),
120 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 0)));
121
122 // Check the last row of the write operation
123 EXPECT_THAT(rows.at(2 * AVM_KECCAKF1600_STATE_SIZE),
124 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
125 ROW_FIELD_EQ(keccak_memory_ctr, AVM_KECCAKF1600_STATE_SIZE),
126 ROW_FIELD_EQ(keccak_memory_start_read, 0),
127 ROW_FIELD_EQ(keccak_memory_start_write, 0),
128 ROW_FIELD_EQ(keccak_memory_last, 1),
129 ROW_FIELD_EQ(keccak_memory_ctr_end, 1),
130 ROW_FIELD_EQ(keccak_memory_rw, 1),
131 ROW_FIELD_EQ(keccak_memory_addr, 200 + AVM_KECCAKF1600_STATE_SIZE - 1),
132 ROW_FIELD_EQ(keccak_memory_space_id, 23),
133 ROW_FIELD_EQ(keccak_memory_val00, 10000 + AVM_KECCAKF1600_STATE_SIZE - 1),
134 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
135 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
136 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
137 ROW_FIELD_EQ(keccak_memory_ctr_inv, FF(AVM_KECCAKF1600_STATE_SIZE).invert()),
138 ROW_FIELD_EQ(keccak_memory_state_size_min_ctr_inv, 0),
139 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 0)));
140}
141
142// We use simulation to generate the trace of a positive keccakf1600 event.
143TEST(KeccakF1600TraceGenTest, MainKeccakTraceWithSimulation)
144{
145 TestTraceContainer trace;
146
147 const MemoryAddress src_addr = 123;
148 const MemoryAddress dst_addr = 456;
149 const uint16_t space_id = 23;
150
151 testing::generate_keccak_trace(trace, { dst_addr }, { src_addr }, space_id);
152
153 // Get the rows
154 auto rows = trace.as_rows();
155
156 ASSERT_GT(rows.size(), AVM_KECCAKF1600_NUM_ROUNDS);
157
158 // Specific checks on the first row of the keccakf1600 permutation subtrace.
159 // A memory slice read is active.
160 EXPECT_THAT(
161 rows.at(1),
162 AllOf(ROW_FIELD_EQ(keccakf1600_start, 1),
163 ROW_FIELD_EQ(keccakf1600_highest_slice_address, AVM_HIGHEST_MEM_ADDRESS - AVM_KECCAKF1600_STATE_SIZE + 1),
164 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 1),
165 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0),
166 ROW_FIELD_EQ(keccakf1600_src_addr, src_addr),
167 ROW_FIELD_EQ(keccakf1600_last, 0)));
168
169 // Check values on all rows of the keccakf1600 permutation subtrace.
170 for (size_t i = 1; i < AVM_KECCAKF1600_NUM_ROUNDS + 1; i++) {
171 EXPECT_THAT(rows.at(i),
172 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 1),
173 ROW_FIELD_EQ(keccakf1600_clk, 1),
174 ROW_FIELD_EQ(keccakf1600_round, i),
175 ROW_FIELD_EQ(keccakf1600_dst_addr, dst_addr),
176 ROW_FIELD_EQ(keccakf1600_bitwise_xor_op_id, static_cast<uint8_t>(BitwiseOperation::XOR)),
177 ROW_FIELD_EQ(keccakf1600_bitwise_and_op_id, static_cast<uint8_t>(BitwiseOperation::AND)),
178 ROW_FIELD_EQ(keccakf1600_tag_u64, static_cast<uint8_t>(MemoryTag::U64)),
179 ROW_FIELD_EQ(keccakf1600_round_cst, simulation::keccak_round_constants[i - 1]),
180 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 0),
181 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 0),
182 ROW_FIELD_EQ(keccakf1600_tag_error, 0),
183 ROW_FIELD_EQ(keccakf1600_error, 0),
184 ROW_FIELD_EQ(keccakf1600_sel_no_error, 1)));
185 }
186
187 // Specific checks on the last row of the keccakf1600 permutation subtrace.
188 EXPECT_THAT(rows.at(AVM_KECCAKF1600_NUM_ROUNDS),
189 AllOf(ROW_FIELD_EQ(keccakf1600_start, 0),
190 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
191 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 1),
192 ROW_FIELD_EQ(keccakf1600_src_addr, 0),
193 ROW_FIELD_EQ(keccakf1600_last, 1)));
194}
195
196// We test when the memory tag is not U64 for a read value at index (1, 2).
197// We check that the tag_error is 1 for this index (flattened index 7) and that
198// we correctly propagate the error to the top.
199// We also check that tag_min_u64_inv is correctly computed.
200TEST(KeccakF1600TraceGenTest, TagErrorHandling)
201{
202 TestTraceContainer trace;
203
204 const MemoryAddress src_addr = 0;
205 const MemoryAddress dst_addr = 200;
206 const uint16_t space_id = 79;
207
208 // Position (1,2) in the 5x5 matrix corresponds to index 7 in the flattened array
209 const size_t error_offset = 7; // (1 * 5) + 2 = 7
210 const MemoryTag error_tag = MemoryTag::U32; // Using U32 instead of U64 to trigger error
211
212 testing::generate_keccak_trace_with_tag_error(trace, dst_addr, src_addr, error_offset, error_tag, space_id);
213
214 const auto& rows = trace.as_rows();
215
216 ASSERT_GT(rows.size(), std::max(static_cast<size_t>(AVM_KECCAKF1600_NUM_ROUNDS), error_offset + 2));
217
218 // Checks on the whole active keccak_memory subtrace.
219 for (size_t i = 1; i < error_offset + 2; i++) {
220 EXPECT_THAT(rows.at(i),
221 AllOf(ROW_FIELD_EQ(keccak_memory_ctr, i),
222 ROW_FIELD_EQ(keccak_memory_sel, 1),
223 ROW_FIELD_EQ(keccak_memory_rw, 0),
224 ROW_FIELD_EQ(keccak_memory_ctr_end, 0),
225 ROW_FIELD_EQ(keccak_memory_tag_error, 1),
226 ROW_FIELD_EQ(keccak_memory_space_id, space_id)));
227 }
228
229 // Checks on the whole active keccak_memory subtrace except the last row.
230 for (size_t i = 1; i < error_offset + 1; i++) {
231 EXPECT_THAT(rows.at(i),
232 AllOf(ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
233 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 0),
234 ROW_FIELD_EQ(keccak_memory_last, 0)));
235 }
236
237 // Specific checks on the last row of the active keccak_memory subtrace.
238 EXPECT_THAT(
239 rows.at(error_offset + 1),
240 AllOf(ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv,
241 (FF(static_cast<uint8_t>(error_tag)) - FF(static_cast<uint8_t>(MemoryTag::U64))).invert()),
242 ROW_FIELD_EQ(keccak_memory_last, 1)));
243
244 // Next row is not active in keccak_memory.
245 EXPECT_THAT(rows.at(error_offset + 2), ROW_FIELD_EQ(keccak_memory_sel, 0));
246
247 // Check that the keccakf1600 permutation subtrace is correct.
248
249 // Check that the first row of the keccakf1600 permutation subtrace is correct.
250 EXPECT_THAT(rows.at(1),
251 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 1),
252 ROW_FIELD_EQ(keccakf1600_clk, 1),
253 ROW_FIELD_EQ(keccakf1600_start, 1),
254 ROW_FIELD_EQ(keccakf1600_round, 1),
255 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 1),
256 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0),
257 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 0),
258 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 0),
259 ROW_FIELD_EQ(keccakf1600_tag_error, 1),
260 ROW_FIELD_EQ(keccakf1600_error, 1),
261 ROW_FIELD_EQ(keccakf1600_sel_no_error, 0),
262 ROW_FIELD_EQ(keccakf1600_last, 1))); // We set last at the initial row when there is an error.
263
264 // Check that all the subsequent rows have inactive selectors.
265 for (size_t i = 2; i < AVM_KECCAKF1600_NUM_ROUNDS + 1; i++) {
266 EXPECT_THAT(rows.at(i),
267 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 0),
268 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
269 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0)));
270 }
271}
272
273// We test when the src address is out of bounds.
274// We check that the src_out_of_range_error is 1 and that the sel_no_error is propagated to the bottom.
275// We also check that the sel_slice_read and sel_slice_write are 0 and that row == 1 of keccak_memory
276// slice is inactive.
277TEST(KeccakF1600TraceGenTest, SrcAddressOutOfBounds)
278{
279 TestTraceContainer trace;
280
281 const MemoryAddress src_addr = AVM_HIGHEST_MEM_ADDRESS - AVM_KECCAKF1600_STATE_SIZE + 2;
282 const MemoryAddress dst_addr = 456;
283 const uint16_t space_id = 23;
284
285 testing::generate_keccak_trace_with_slice_error(trace, dst_addr, src_addr, space_id);
286
287 const auto& rows = trace.as_rows();
288
289 ASSERT_GT(rows.size(), AVM_KECCAKF1600_NUM_ROUNDS);
290
291 // Check that the keccakf1600 permutation subtrace is correct.
292 EXPECT_THAT(rows.at(1),
293 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 1),
294 ROW_FIELD_EQ(keccakf1600_round, 1),
295 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
296 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0),
297 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 1),
298 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 0),
299 ROW_FIELD_EQ(keccakf1600_tag_error, 0),
300 ROW_FIELD_EQ(keccakf1600_error, 1),
301 ROW_FIELD_EQ(keccakf1600_sel_no_error, 0),
302 ROW_FIELD_EQ(keccakf1600_last, 1))); // We set last at the initial row when there is an error.
303
304 // Check that all the subsequent rows have inactive selectors.
305 for (size_t i = 2; i < AVM_KECCAKF1600_NUM_ROUNDS + 1; i++) {
306 EXPECT_THAT(rows.at(i),
307 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 0),
308 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
309 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0)));
310 }
311
312 // Check that first row of keccak_memory is inactive.
313 EXPECT_THAT(rows.at(1), ROW_FIELD_EQ(keccak_memory_sel, 0));
314}
315
316// We test when the dst address is out of bounds.
317// We check that the src_out_of_range_error is 1 and that the sel_no_error is propagated to the bottom.
318// We also check that the sel_slice_read and sel_slice_write are 0 and that row == 1 of keccak_memory
319// slice is inactive.
320TEST(KeccakF1600TraceGenTest, DstAddressOutOfBounds)
321{
322 TestTraceContainer trace;
323
324 const MemoryAddress src_addr = 123;
325 const MemoryAddress dst_addr = AVM_HIGHEST_MEM_ADDRESS - AVM_KECCAKF1600_STATE_SIZE + 2;
326 const uint16_t space_id = 23;
327
328 testing::generate_keccak_trace_with_slice_error(trace, dst_addr, src_addr, space_id);
329
330 const auto& rows = trace.as_rows();
331
332 ASSERT_GT(rows.size(), AVM_KECCAKF1600_NUM_ROUNDS);
333
334 // Check that the keccakf1600 permutation subtrace is correct.
335 EXPECT_THAT(rows.at(1),
336 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 1),
337 ROW_FIELD_EQ(keccakf1600_round, 1),
338 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
339 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0),
340 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 0),
341 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 1),
342 ROW_FIELD_EQ(keccakf1600_tag_error, 0),
343 ROW_FIELD_EQ(keccakf1600_error, 1),
344 ROW_FIELD_EQ(keccakf1600_sel_no_error, 0),
345 ROW_FIELD_EQ(keccakf1600_last, 1))); // We set last at the initial row when there is an error.
346
347 // Check that all the subsequent rows have inactive selectors.
348 for (size_t i = 2; i < AVM_KECCAKF1600_NUM_ROUNDS + 1; i++) {
349 EXPECT_THAT(rows.at(i),
350 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 0),
351 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
352 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0)));
353 }
354
355 // Check that first row of keccak_memory is inactive.
356 EXPECT_THAT(rows.at(1), ROW_FIELD_EQ(keccak_memory_sel, 0));
357}
358
359} // namespace
360} // namespace bb::avm2::tracegen
aztec_constants.hpp
AVM_KECCAKF1600_STATE_SIZE
#define AVM_KECCAKF1600_STATE_SIZE
Definition aztec_constants.hpp:50
AVM_HIGHEST_MEM_ADDRESS
#define AVM_HIGHEST_MEM_ADDRESS
Definition aztec_constants.hpp:44
AVM_KECCAKF1600_NUM_ROUNDS
#define AVM_KECCAKF1600_NUM_ROUNDS
Definition aztec_constants.hpp:49
bb::avm2::tracegen::TestTraceContainer::as_rows
std::vector< AvmFullRowConstRef > as_rows() const
Definition test_trace_container.cpp:28
builder
AluTraceBuilder builder
Definition alu.test.cpp:123
dst_addr
uint32_t dst_addr
Definition data_copy.test.cpp:63
trace
TestTraceContainer trace
Definition data_copy.test.cpp:62
keccakf1600_event.hpp
keccakf1600_fixture.test.hpp
keccakf1600_trace.hpp
ROW_FIELD_EQ
#define ROW_FIELD_EQ(field_name, expression)
Definition macros.hpp:15
memory_types.hpp
bb::avm2::simulation::TEST
TEST(EmitUnencryptedLogTest, Basic)
Definition emit_unencrypted_log.test.cpp:20
bb::avm2::simulation::keccak_round_constants
constexpr std::array< uint64_t, 24 > keccak_round_constants
Definition keccakf1600.hpp:41
bb::avm2::testing::generate_keccak_trace
void generate_keccak_trace(TestTraceContainer &trace, const std::vector< MemoryAddress > &dst_addresses, const std::vector< MemoryAddress > &src_addresses, uint16_t space_id)
Definition keccakf1600_fixture.test.cpp:92
bb::avm2::testing::generate_keccak_trace_with_slice_error
void generate_keccak_trace_with_slice_error(TestTraceContainer &trace, MemoryAddress dst_address, MemoryAddress src_address, uint16_t space_id)
Definition keccakf1600_fixture.test.cpp:148
bb::avm2::testing::generate_keccak_trace_with_tag_error
void generate_keccak_trace_with_tag_error(TestTraceContainer &trace, MemoryAddress dst_address, MemoryAddress src_address, size_t error_offset, MemoryTag error_tag, uint16_t space_id)
Definition keccakf1600_fixture.test.cpp:115
bb::avm2::MemoryAddress
uint32_t MemoryAddress
Definition memory_types.hpp:11
bb::avm2::MemoryTag
ValueTag MemoryTag
Definition memory_types.hpp:9
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
event
simulation::PublicDataTreeReadWriteEvent event
Definition public_data_tree_trace.cpp:24
test_trace_container.hpp