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/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(
67 rows.at(1),
68 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
69 ROW_FIELD_EQ(keccak_memory_ctr, 1),
70 ROW_FIELD_EQ(keccak_memory_start_read, 1),
71 ROW_FIELD_EQ(keccak_memory_start_write, 0),
72 ROW_FIELD_EQ(keccak_memory_last, 0),
73 ROW_FIELD_EQ(keccak_memory_ctr_end, 0),
74 ROW_FIELD_EQ(keccak_memory_rw, 0),
75 ROW_FIELD_EQ(keccak_memory_addr, 100),
76 ROW_FIELD_EQ(keccak_memory_space_id, 23),
77 ROW_FIELD_EQ(keccak_memory_val00, 1000),
78 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
79 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
80 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
81 ROW_FIELD_EQ(keccak_memory_ctr_inv, 1),
82 ROW_FIELD_EQ(keccak_memory_ctr_min_state_size_inv, (FF(1) - FF(AVM_KECCAKF1600_STATE_SIZE)).invert()),
83 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 1)));
84
85 // Check the last row of the read operation
86 EXPECT_THAT(rows.at(AVM_KECCAKF1600_STATE_SIZE),
87 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
88 ROW_FIELD_EQ(keccak_memory_ctr, AVM_KECCAKF1600_STATE_SIZE),
89 ROW_FIELD_EQ(keccak_memory_start_read, 0),
90 ROW_FIELD_EQ(keccak_memory_start_write, 0),
91 ROW_FIELD_EQ(keccak_memory_last, 1),
92 ROW_FIELD_EQ(keccak_memory_ctr_end, 1),
93 ROW_FIELD_EQ(keccak_memory_rw, 0),
94 ROW_FIELD_EQ(keccak_memory_addr, 100 + AVM_KECCAKF1600_STATE_SIZE - 1),
95 ROW_FIELD_EQ(keccak_memory_space_id, 23),
96 ROW_FIELD_EQ(keccak_memory_val00, 1000 + AVM_KECCAKF1600_STATE_SIZE - 1),
97 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
98 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
99 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
100 ROW_FIELD_EQ(keccak_memory_ctr_inv, FF(AVM_KECCAKF1600_STATE_SIZE).invert()),
101 ROW_FIELD_EQ(keccak_memory_ctr_min_state_size_inv, 1),
102 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 1)));
103
104 // Check the first row of the write operation (after read operation)
105 EXPECT_THAT(
106 rows.at(AVM_KECCAKF1600_STATE_SIZE + 1),
107 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
108 ROW_FIELD_EQ(keccak_memory_ctr, 1),
109 ROW_FIELD_EQ(keccak_memory_start_read, 0),
110 ROW_FIELD_EQ(keccak_memory_start_write, 1),
111 ROW_FIELD_EQ(keccak_memory_last, 0),
112 ROW_FIELD_EQ(keccak_memory_ctr_end, 0),
113 ROW_FIELD_EQ(keccak_memory_rw, 1),
114 ROW_FIELD_EQ(keccak_memory_addr, 200),
115 ROW_FIELD_EQ(keccak_memory_space_id, 23),
116 ROW_FIELD_EQ(keccak_memory_val00, 10000),
117 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
118 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
119 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
120 ROW_FIELD_EQ(keccak_memory_ctr_inv, 1),
121 ROW_FIELD_EQ(keccak_memory_ctr_min_state_size_inv, (FF(1) - FF(AVM_KECCAKF1600_STATE_SIZE)).invert()),
122 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 1)));
123
124 // Check the last row of the write operation
125 EXPECT_THAT(rows.at(2 * AVM_KECCAKF1600_STATE_SIZE),
126 AllOf(ROW_FIELD_EQ(keccak_memory_sel, 1),
127 ROW_FIELD_EQ(keccak_memory_ctr, AVM_KECCAKF1600_STATE_SIZE),
128 ROW_FIELD_EQ(keccak_memory_start_read, 0),
129 ROW_FIELD_EQ(keccak_memory_start_write, 0),
130 ROW_FIELD_EQ(keccak_memory_last, 1),
131 ROW_FIELD_EQ(keccak_memory_ctr_end, 1),
132 ROW_FIELD_EQ(keccak_memory_rw, 1),
133 ROW_FIELD_EQ(keccak_memory_addr, 200 + AVM_KECCAKF1600_STATE_SIZE - 1),
134 ROW_FIELD_EQ(keccak_memory_space_id, 23),
135 ROW_FIELD_EQ(keccak_memory_val00, 10000 + AVM_KECCAKF1600_STATE_SIZE - 1),
136 ROW_FIELD_EQ(keccak_memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
137 ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
138 ROW_FIELD_EQ(keccak_memory_tag_error, 0),
139 ROW_FIELD_EQ(keccak_memory_ctr_inv, FF(AVM_KECCAKF1600_STATE_SIZE).invert()),
140 ROW_FIELD_EQ(keccak_memory_ctr_min_state_size_inv, 1),
141 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 1)));
142}
143
144// We use simulation to generate the trace of a positive keccakf1600 event.
145TEST(KeccakF1600TraceGenTest, MainKeccakTraceWithSimulation)
146{
147 TestTraceContainer trace;
148
149 const MemoryAddress src_addr = 123;
150 const MemoryAddress dst_addr = 456;
151 const uint32_t space_id = 23;
152
153 testing::generate_keccak_trace(trace, { dst_addr }, { src_addr }, space_id);
154
155 // Get the rows
156 auto rows = trace.as_rows();
157
158 ASSERT_GT(rows.size(), AVM_KECCAKF1600_NUM_ROUNDS);
159
160 // Specific checks on the first row of the keccakf1600 permutation subtrace.
161 // A memory slice read is active.
162 EXPECT_THAT(rows.at(1),
163 AllOf(ROW_FIELD_EQ(keccakf1600_start, 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_thirty_two, AVM_MEMORY_NUM_BITS),
181 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 0),
182 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 0),
183 ROW_FIELD_EQ(keccakf1600_tag_error, 0),
184 ROW_FIELD_EQ(keccakf1600_error, 0),
185 ROW_FIELD_EQ(keccakf1600_sel_no_error, 1)));
186 }
187
188 // Specific checks on the last row of the keccakf1600 permutation subtrace.
189 EXPECT_THAT(rows.at(AVM_KECCAKF1600_NUM_ROUNDS),
190 AllOf(ROW_FIELD_EQ(keccakf1600_start, 0),
191 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
192 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 1),
193 ROW_FIELD_EQ(keccakf1600_src_addr, 0),
194 ROW_FIELD_EQ(keccakf1600_last, 1)));
195}
196
197// We test when the memory tag is not U64 for a read value at index (1, 2).
198// We check that the tag_error is 1 for this index (flattened index 7) and that
199// we correctly propagate the error to the top.
200// We also check that tag_min_u64_inv is correctly computed.
201TEST(KeccakF1600TraceGenTest, TagErrorHandling)
202{
203 TestTraceContainer trace;
204
205 const MemoryAddress src_addr = 0;
206 const MemoryAddress dst_addr = 200;
207 const uint32_t space_id = 79;
208
209 // Position (1,2) in the 5x5 matrix corresponds to index 7 in the flattened array
210 const size_t error_offset = 7; // (1 * 5) + 2 = 7
211 const MemoryTag error_tag = MemoryTag::U32; // Using U32 instead of U64 to trigger error
212
213 testing::generate_keccak_trace_with_tag_error(trace, dst_addr, src_addr, error_offset, error_tag, space_id);
214
215 const auto& rows = trace.as_rows();
216
217 ASSERT_GT(rows.size(), std::max(static_cast<size_t>(AVM_KECCAKF1600_NUM_ROUNDS), error_offset + 2));
218
219 // Checks on the whole active keccak_memory subtrace.
220 for (size_t i = 1; i < error_offset + 2; i++) {
221 EXPECT_THAT(rows.at(i),
222 AllOf(ROW_FIELD_EQ(keccak_memory_ctr, i),
223 ROW_FIELD_EQ(keccak_memory_sel, 1),
224 ROW_FIELD_EQ(keccak_memory_rw, 0),
225 ROW_FIELD_EQ(keccak_memory_ctr_end, 0),
226 ROW_FIELD_EQ(keccak_memory_tag_error, 1),
227 ROW_FIELD_EQ(keccak_memory_space_id, space_id)));
228 }
229
230 // Checks on the whole active keccak_memory subtrace except the last row.
231 for (size_t i = 1; i < error_offset + 1; i++) {
232 EXPECT_THAT(rows.at(i),
233 AllOf(ROW_FIELD_EQ(keccak_memory_single_tag_error, 0),
234 ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv, 1),
235 ROW_FIELD_EQ(keccak_memory_last, 0)));
236 }
237
238 // Specific checks on the last row of the active keccak_memory subtrace.
239 EXPECT_THAT(
240 rows.at(error_offset + 1),
241 AllOf(ROW_FIELD_EQ(keccak_memory_tag_min_u64_inv,
242 (FF(static_cast<uint8_t>(error_tag)) - FF(static_cast<uint8_t>(MemoryTag::U64))).invert()),
243 ROW_FIELD_EQ(keccak_memory_last, 1)));
244
245 // Next row is not active in keccak_memory.
246 EXPECT_THAT(rows.at(error_offset + 2), ROW_FIELD_EQ(keccak_memory_sel, 0));
247
248 // Check that the keccakf1600 permutation subtrace is correct.
249
250 // Check that the first row of the keccakf1600 permutation subtrace is correct.
251 EXPECT_THAT(rows.at(1),
252 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 1),
253 ROW_FIELD_EQ(keccakf1600_clk, 1),
254 ROW_FIELD_EQ(keccakf1600_start, 1),
255 ROW_FIELD_EQ(keccakf1600_round, 1),
256 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 1),
257 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0),
258 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 0),
259 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 0),
260 ROW_FIELD_EQ(keccakf1600_tag_error, 1),
261 ROW_FIELD_EQ(keccakf1600_error, 1),
262 ROW_FIELD_EQ(keccakf1600_sel_no_error, 0),
263 ROW_FIELD_EQ(keccakf1600_last, 1))); // We set last at the initial row when there is an error.
264
265 // Check that all the subsequent rows have inactive selectors.
266 for (size_t i = 2; i < AVM_KECCAKF1600_NUM_ROUNDS + 1; i++) {
267 EXPECT_THAT(rows.at(i),
268 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 0),
269 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
270 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0)));
271 }
272}
273
274// We test when the src address is out of bounds.
275// We check that the src_out_of_range_error is 1 and that the sel_no_error is propagated to the bottom.
276// We also check that the sel_slice_read and sel_slice_write are 0 and that row == 1 of keccak_memory
277// slice is inactive.
278TEST(KeccakF1600TraceGenTest, SrcAddressOutOfBounds)
279{
280 TestTraceContainer trace;
281
282 const MemoryAddress src_addr = AVM_HIGHEST_MEM_ADDRESS - AVM_KECCAKF1600_STATE_SIZE + 2;
283 const MemoryAddress dst_addr = 456;
284 const uint32_t space_id = 23;
285
286 testing::generate_keccak_trace_with_slice_error(trace, dst_addr, src_addr, space_id);
287
288 const auto& rows = trace.as_rows();
289
290 ASSERT_GT(rows.size(), AVM_KECCAKF1600_NUM_ROUNDS);
291
292 // Check that the keccakf1600 permutation subtrace is correct.
293 EXPECT_THAT(rows.at(1),
294 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 1),
295 ROW_FIELD_EQ(keccakf1600_round, 1),
296 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
297 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0),
298 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 1),
299 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 0),
300 ROW_FIELD_EQ(keccakf1600_tag_error, 0),
301 ROW_FIELD_EQ(keccakf1600_error, 1),
302 ROW_FIELD_EQ(keccakf1600_sel_no_error, 0),
303 ROW_FIELD_EQ(keccakf1600_last, 1))); // We set last at the initial row when there is an error.
304
305 // Check that all the subsequent rows have inactive selectors.
306 for (size_t i = 2; i < AVM_KECCAKF1600_NUM_ROUNDS + 1; i++) {
307 EXPECT_THAT(rows.at(i),
308 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 0),
309 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
310 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0)));
311 }
312
313 // Check that first row of keccak_memory is inactive.
314 EXPECT_THAT(rows.at(1), ROW_FIELD_EQ(keccak_memory_sel, 0));
315}
316
317// We test when the dst address is out of bounds.
318// We check that the src_out_of_range_error is 1 and that the sel_no_error is propagated to the bottom.
319// We also check that the sel_slice_read and sel_slice_write are 0 and that row == 1 of keccak_memory
320// slice is inactive.
321TEST(KeccakF1600TraceGenTest, DstAddressOutOfBounds)
322{
323 TestTraceContainer trace;
324
325 const MemoryAddress src_addr = 123;
326 const MemoryAddress dst_addr = AVM_HIGHEST_MEM_ADDRESS - AVM_KECCAKF1600_STATE_SIZE + 2;
327 const uint32_t space_id = 23;
328
329 testing::generate_keccak_trace_with_slice_error(trace, dst_addr, src_addr, space_id);
330
331 const auto& rows = trace.as_rows();
332
333 ASSERT_GT(rows.size(), AVM_KECCAKF1600_NUM_ROUNDS);
334
335 // Check that the keccakf1600 permutation subtrace is correct.
336 EXPECT_THAT(rows.at(1),
337 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 1),
338 ROW_FIELD_EQ(keccakf1600_round, 1),
339 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
340 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0),
341 ROW_FIELD_EQ(keccakf1600_src_out_of_range_error, 0),
342 ROW_FIELD_EQ(keccakf1600_dst_out_of_range_error, 1),
343 ROW_FIELD_EQ(keccakf1600_tag_error, 0),
344 ROW_FIELD_EQ(keccakf1600_error, 1),
345 ROW_FIELD_EQ(keccakf1600_sel_no_error, 0),
346 ROW_FIELD_EQ(keccakf1600_last, 1))); // We set last at the initial row when there is an error.
347
348 // Check that all the subsequent rows have inactive selectors.
349 for (size_t i = 2; i < AVM_KECCAKF1600_NUM_ROUNDS + 1; i++) {
350 EXPECT_THAT(rows.at(i),
351 AllOf(ROW_FIELD_EQ(keccakf1600_sel, 0),
352 ROW_FIELD_EQ(keccakf1600_sel_slice_read, 0),
353 ROW_FIELD_EQ(keccakf1600_sel_slice_write, 0)));
354 }
355
356 // Check that first row of keccak_memory is inactive.
357 EXPECT_THAT(rows.at(1), ROW_FIELD_EQ(keccak_memory_sel, 0));
358}
359
360} // namespace
361} // namespace bb::avm2::tracegen
aztec_constants.hpp
AVM_KECCAKF1600_STATE_SIZE
#define AVM_KECCAKF1600_STATE_SIZE
Definition aztec_constants.hpp:46
AVM_HIGHEST_MEM_ADDRESS
#define AVM_HIGHEST_MEM_ADDRESS
Definition aztec_constants.hpp:40
AVM_KECCAKF1600_NUM_ROUNDS
#define AVM_KECCAKF1600_NUM_ROUNDS
Definition aztec_constants.hpp:45
AVM_MEMORY_NUM_BITS
#define AVM_MEMORY_NUM_BITS
Definition aztec_constants.hpp:41
bb::avm2::tracegen::TestTraceContainer::as_rows
std::vector< AvmFullRowConstRef > as_rows() const
Definition test_trace_container.cpp:41
builder
AluTraceBuilder builder
Definition alu.test.cpp:123
dst_addr
uint32_t dst_addr
Definition data_copy.test.cpp:60
trace
TestTraceContainer trace
Definition data_copy.test.cpp:59
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:39
bb::avm2::testing::generate_keccak_trace_with_slice_error
void generate_keccak_trace_with_slice_error(TestTraceContainer &trace, MemoryAddress dst_address, MemoryAddress src_address, uint32_t space_id)
Definition keccakf1600_fixture.test.cpp:138
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, uint32_t space_id)
Definition keccakf1600_fixture.test.cpp:105
bb::avm2::testing::generate_keccak_trace
void generate_keccak_trace(TestTraceContainer &trace, const std::vector< MemoryAddress > &dst_addresses, const std::vector< MemoryAddress > &src_addresses, uint32_t space_id)
Definition keccakf1600_fixture.test.cpp:82
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:20
test_trace_container.hpp