Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
emit_nullifier.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/memory_types.hpp"
7#include "barretenberg/vm2/constraining/flavor_settings.hpp"
8#include "barretenberg/vm2/constraining/testing/check_relation.hpp"
9#include "barretenberg/vm2/generated/relations/execution.hpp"
10#include "barretenberg/vm2/simulation/events/indexed_tree_check_event.hpp"
11#include "barretenberg/vm2/simulation/gadgets/indexed_tree_check.hpp"
12#include "barretenberg/vm2/simulation/lib/merkle.hpp"
13#include "barretenberg/vm2/simulation/testing/mock_field_gt.hpp"
14#include "barretenberg/vm2/simulation/testing/mock_indexed_tree_check.hpp"
15#include "barretenberg/vm2/simulation/testing/mock_merkle_check.hpp"
16#include "barretenberg/vm2/simulation/testing/mock_poseidon2.hpp"
17#include "barretenberg/vm2/simulation/testing/mock_range_check.hpp"
18#include "barretenberg/vm2/testing/macros.hpp"
19#include "barretenberg/vm2/tracegen/execution_trace.hpp"
20#include "barretenberg/vm2/tracegen/indexed_tree_check_trace.hpp"
21#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
22
23namespace bb::avm2::constraining {
24namespace {
25
26using tracegen::ExecutionTraceBuilder;
27using tracegen::IndexedTreeCheckTraceBuilder;
28using tracegen::TestTraceContainer;
29
30using simulation::EventEmitter;
31using simulation::IndexedTreeCheck;
32using simulation::IndexedTreeCheckEvent;
33using simulation::IndexedTreeLeafData;
34using simulation::IndexedTreeSiloingParameters;
35using simulation::MockFieldGreaterThan;
36using simulation::MockMerkleCheck;
37using simulation::MockPoseidon2;
38using simulation::MockRangeCheck;
39using simulation::NullifierTreeLeafPreimage;
40
41using testing::_;
42using testing::Return;
43using testing::StrictMock;
44
45using FF = AvmFlavorSettings::FF;
46using C = Column;
47using emit_nullifier = bb::avm2::emit_nullifier<FF>;
48using RawPoseidon2 = crypto::Poseidon2<crypto::Poseidon2Bn254ScalarFieldParams>;
49
50TEST(EmitNullifierConstrainingTest, Positive)
51{
52 uint64_t prev_num_nullifiers_emitted = MAX_NULLIFIERS_PER_TX - 1;
53 TestTraceContainer trace({ {
54 { C::execution_sel_execute_emit_nullifier, 1 },
55 { C::execution_register_0_, /*nullifier=*/42 },
56 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
57 { C::execution_remaining_nullifiers_inv, FF(MAX_NULLIFIERS_PER_TX - prev_num_nullifiers_emitted).invert() },
58 { C::execution_sel_write_nullifier, 1 },
59 { C::execution_sel_opcode_error, 0 },
60 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
61 { C::execution_prev_nullifier_tree_size, 1 },
62 { C::execution_nullifier_tree_size, 2 },
63 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
64 { C::execution_nullifier_pi_offset,
65 prev_num_nullifiers_emitted + AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX },
66 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted + 1 },
67 { C::execution_nullifier_siloing_separator, DOM_SEP__SILOED_NULLIFIER },
68 { C::execution_nullifier_tree_height, NULLIFIER_TREE_HEIGHT },
69 } });
70 check_relation<emit_nullifier>(trace);
71}
72
73TEST(EmitNullifierConstrainingTest, LimitReached)
74{
75 uint64_t prev_num_nullifiers_emitted = MAX_NULLIFIERS_PER_TX;
76 TestTraceContainer trace({ {
77 { C::execution_sel_execute_emit_nullifier, 1 },
78 { C::execution_register_0_, /*nullifier=*/42 },
79 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
80 { C::execution_sel_reached_max_nullifiers, 1 },
81 { C::execution_remaining_nullifiers_inv, 0 },
82 { C::execution_sel_write_nullifier, 0 },
83 { C::execution_sel_opcode_error, 1 },
84 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
85 { C::execution_prev_nullifier_tree_size, 1 },
86 { C::execution_nullifier_tree_size, 1 },
87 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
88 { C::execution_nullifier_pi_offset,
89 prev_num_nullifiers_emitted + AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX },
90 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted },
91 } });
92 check_relation<emit_nullifier>(trace);
93
94 // Negative test: sel_reached_max_nullifiers must be 1
95 trace.set(C::execution_sel_reached_max_nullifiers, 0, 0);
96 EXPECT_THROW_WITH_MESSAGE(check_relation<emit_nullifier>(trace, emit_nullifier::SR_MAX_NULLIFIER_WRITES_REACHED),
97 "MAX_NULLIFIER_WRITES_REACHED");
98 trace.set(C::execution_sel_reached_max_nullifiers, 0, 1);
99
100 // Negative test: sel_opcode_error must be on
101 trace.set(C::execution_sel_opcode_error, 0, 0);
102 EXPECT_THROW_WITH_MESSAGE(
103 check_relation<emit_nullifier>(trace, emit_nullifier::SR_OPCODE_ERROR_IF_VALIDATION_ERROR),
104 "OPCODE_ERROR_IF_VALIDATION_ERROR");
105 trace.set(C::execution_sel_opcode_error, 0, 1);
106
107 // Negative test: nullifier tree root must be the same
108 trace.set(C::execution_nullifier_tree_root, 0, 28);
109 EXPECT_THROW_WITH_MESSAGE(
110 check_relation<emit_nullifier>(trace, emit_nullifier::SR_EMIT_NULLIFIER_TREE_ROOT_NOT_CHANGED),
111 "EMIT_NULLIFIER_TREE_ROOT_NOT_CHANGED");
112
113 // Negative test: tree size must be the same
114 trace.set(C::execution_nullifier_tree_size, 0, 2);
115 EXPECT_THROW_WITH_MESSAGE(
116 check_relation<emit_nullifier>(trace, emit_nullifier::SR_EMIT_NULLIFIER_TREE_SIZE_INCREASE),
117 "EMIT_NULLIFIER_TREE_SIZE_INCREASE");
118
119 // Negative test: num nullifiers emitted must be the same
120 trace.set(C::execution_num_nullifiers_emitted, 0, prev_num_nullifiers_emitted + 1);
121 EXPECT_THROW_WITH_MESSAGE(
122 check_relation<emit_nullifier>(trace, emit_nullifier::SR_EMIT_NULLIFIER_NUM_NULLIFIERS_EMITTED_INCREASE),
123 "EMIT_NULLIFIER_NUM_NULLIFIERS_EMITTED_INCREASE");
124}
125
126TEST(EmitNullifierConstrainingTest, Interactions)
127{
128 StrictMock<MockPoseidon2> poseidon2;
129 StrictMock<MockMerkleCheck> merkle_check;
130 StrictMock<MockRangeCheck> range_check;
131 StrictMock<MockFieldGreaterThan> field_gt;
132
133 EventEmitter<IndexedTreeCheckEvent> indexed_tree_check_event_emitter;
134 IndexedTreeCheck indexed_tree_check(poseidon2, merkle_check, field_gt, indexed_tree_check_event_emitter);
135
136 FF nullifier = 42;
137 auto siloing_params = IndexedTreeSiloingParameters{
138 .address = 0xdeadbeef,
139 .siloing_separator = DOM_SEP__SILOED_NULLIFIER,
140 };
141 FF siloed_nullifier = 66;
142 FF low_leaf_nullifier = 99; // siloed nullifier != low leaf nullifier (NO COLLISION)
143 FF low_leaf_hash = 77;
144 FF updated_low_leaf_hash = 101;
145 FF new_leaf_hash = 111;
146 FF pre_write_root = 27;
147 FF intermediate_root = 33;
148 FF post_write_root = 88;
149
150 // insertion sibling path
151 std::vector<FF> insertion_sibling_path = { 1, 2, 3 };
152
153 AppendOnlyTreeSnapshot prev_snapshot = AppendOnlyTreeSnapshot{
154 .root = pre_write_root,
155 .next_available_leaf_index = 128,
156 };
157 uint32_t prev_num_nullifiers_emitted = 2;
158
159 // mock the nullifier > low leaf nullifier to return true
160 EXPECT_CALL(field_gt, ff_gt).WillOnce(Return(true));
161 // mock siloing, low leaf hashing, updated low leaf hashing, new leaf hashing
162 EXPECT_CALL(poseidon2, hash)
163 .WillOnce(Return(siloed_nullifier))
164 .WillOnce(Return(low_leaf_hash))
165 .WillOnce(Return(updated_low_leaf_hash))
166 .WillOnce(Return(new_leaf_hash));
167 // mock merkle check write
168 EXPECT_CALL(merkle_check, write).WillOnce(Return(intermediate_root)).WillOnce(Return(post_write_root));
169
170 // low leaf preimage
171 IndexedTreeLeafData low_leaf_preimage = {
172 .value = low_leaf_nullifier,
173 .next_value = 0,
174 .next_index = 0,
175 };
176 std::vector<FF> low_leaf_sibling_path(NULLIFIER_TREE_HEIGHT);
177
178 AppendOnlyTreeSnapshot next_snapshot = indexed_tree_check.write(
179 nullifier,
180 siloing_params,
181 prev_num_nullifiers_emitted + AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX,
182 low_leaf_preimage,
183 0,
184 low_leaf_sibling_path,
185 prev_snapshot,
186 insertion_sibling_path);
187
188 TestTraceContainer trace({ {
189 { C::execution_sel_execute_emit_nullifier, 1 },
190 { C::execution_register_0_, nullifier },
191 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
192 { C::execution_remaining_nullifiers_inv, FF(MAX_NULLIFIERS_PER_TX - prev_num_nullifiers_emitted).invert() },
193 { C::execution_sel_write_nullifier, 1 },
194 { C::execution_sel_opcode_error, 0 }, // No errors!
195 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
196 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
197 { C::execution_nullifier_pi_offset,
198 prev_num_nullifiers_emitted + AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX },
199 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted + 1 }, // increment on success
200 { C::execution_prev_nullifier_tree_root, prev_snapshot.root },
201 { C::execution_nullifier_tree_root, next_snapshot.root },
202 { C::execution_prev_nullifier_tree_size, prev_snapshot.next_available_leaf_index },
203 { C::execution_nullifier_tree_size, next_snapshot.next_available_leaf_index },
204 { C::execution_contract_address, siloing_params.address },
205 { C::execution_nullifier_siloing_separator, DOM_SEP__SILOED_NULLIFIER },
206 { C::execution_nullifier_tree_height, NULLIFIER_TREE_HEIGHT },
207 } });
208
209 IndexedTreeCheckTraceBuilder indexed_tree_check_trace_builder;
210 indexed_tree_check_trace_builder.process(indexed_tree_check_event_emitter.dump_events(), trace);
211 check_relation<emit_nullifier>(trace);
212
213 check_interaction<ExecutionTraceBuilder, lookup_emit_nullifier_write_nullifier_settings>(trace);
214}
215
216TEST(EmitNullifierConstrainingTest, InteractionsCollision)
217{
218 StrictMock<MockPoseidon2> poseidon2;
219 StrictMock<MockMerkleCheck> merkle_check;
220 StrictMock<MockRangeCheck> range_check;
221 StrictMock<MockFieldGreaterThan> field_gt;
222
223 EventEmitter<IndexedTreeCheckEvent> indexed_tree_check_event_emitter;
224 IndexedTreeCheck indexed_tree_check(poseidon2, merkle_check, field_gt, indexed_tree_check_event_emitter);
225
226 FF nullifier = 42;
227 auto siloing_params = IndexedTreeSiloingParameters{
228 .address = 0xdeadbeef,
229 .siloing_separator = DOM_SEP__SILOED_NULLIFIER,
230 };
231 FF siloed_nullifier = 66;
232 FF low_leaf_hash = 77;
233 FF pre_write_root = 27;
234
235 AppendOnlyTreeSnapshot prev_snapshot = AppendOnlyTreeSnapshot{
236 .root = pre_write_root,
237 .next_available_leaf_index = 128,
238 };
239 uint32_t prev_num_nullifiers_emitted = 2;
240
241 // mock siloing and low leaf hashing
242 EXPECT_CALL(poseidon2, hash).WillOnce(Return(siloed_nullifier)).WillOnce(Return(low_leaf_hash));
243 // mock merkle check assert membership
244 EXPECT_CALL(merkle_check, assert_membership).WillOnce(Return());
245
246 // low leaf preimage
247 IndexedTreeLeafData low_leaf_preimage = {
248 .value = siloed_nullifier,
249 .next_value = 0,
250 .next_index = 0,
251 };
252
253 std::vector<FF> low_leaf_sibling_path(NULLIFIER_TREE_HEIGHT);
254
255 AppendOnlyTreeSnapshot next_snapshot = indexed_tree_check.write(
256 nullifier,
257 siloing_params,
258 AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX + prev_num_nullifiers_emitted,
259 low_leaf_preimage,
260 0,
261 low_leaf_sibling_path,
262 prev_snapshot,
263 std::nullopt);
264
265 TestTraceContainer trace({ {
266 { C::execution_sel_execute_emit_nullifier, 1 },
267 { C::execution_register_0_, nullifier },
268 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
269 { C::execution_remaining_nullifiers_inv, FF(MAX_NULLIFIERS_PER_TX - prev_num_nullifiers_emitted).invert() },
270 { C::execution_sel_write_nullifier, 1 },
271 { C::execution_sel_opcode_error, 1 }, // collision
272 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
273 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
274 { C::execution_nullifier_pi_offset,
275 prev_num_nullifiers_emitted + AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX },
276 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted }, // No increment on error
277 { C::execution_prev_nullifier_tree_root, prev_snapshot.root },
278 { C::execution_nullifier_tree_root, next_snapshot.root },
279 { C::execution_prev_nullifier_tree_size, prev_snapshot.next_available_leaf_index },
280 { C::execution_nullifier_tree_size, next_snapshot.next_available_leaf_index },
281 { C::execution_contract_address, siloing_params.address },
282 { C::execution_nullifier_siloing_separator, DOM_SEP__SILOED_NULLIFIER },
283 { C::execution_nullifier_tree_height, NULLIFIER_TREE_HEIGHT },
284 } });
285
286 IndexedTreeCheckTraceBuilder indexed_tree_check_trace_builder;
287 indexed_tree_check_trace_builder.process(indexed_tree_check_event_emitter.dump_events(), trace);
288 check_relation<emit_nullifier>(trace);
289
290 check_interaction<ExecutionTraceBuilder, lookup_emit_nullifier_write_nullifier_settings>(trace);
291}
292
293} // namespace
294} // namespace bb::avm2::constraining
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessageRegex)
Definition assert.hpp:193
AVM_EXEC_OP_ID_EMIT_NULLIFIER
#define AVM_EXEC_OP_ID_EMIT_NULLIFIER
Definition aztec_constants.hpp:97
AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX
#define AVM_PUBLIC_INPUTS_AVM_ACCUMULATED_DATA_NULLIFIERS_ROW_IDX
Definition aztec_constants.hpp:171
DOM_SEP__SILOED_NULLIFIER
#define DOM_SEP__SILOED_NULLIFIER
Definition aztec_constants.hpp:263
NULLIFIER_TREE_HEIGHT
#define NULLIFIER_TREE_HEIGHT
Definition aztec_constants.hpp:9
MAX_NULLIFIERS_PER_TX
#define MAX_NULLIFIERS_PER_TX
Definition aztec_constants.hpp:15
field_gt
FieldGreaterThan field_gt
Definition bc_retrieval.test.cpp:309
merkle_check
MerkleCheck merkle_check
Definition bc_retrieval.test.cpp:307
indexed_tree_check
IndexedTreeCheck indexed_tree_check
Definition bc_retrieval.test.cpp:310
indexed_tree_check_event_emitter
EventEmitter< simulation::IndexedTreeCheckEvent > indexed_tree_check_event_emitter
Definition bc_retrieval.test.cpp:298
range_check
RangeCheck range_check
Definition bc_retrieval.test.cpp:308
check_relation.hpp
bb::avm2::emit_nullifier
Definition emit_nullifier.hpp:33
bb::avm2::emit_nullifier::SR_OPCODE_ERROR_IF_VALIDATION_ERROR
static constexpr size_t SR_OPCODE_ERROR_IF_VALIDATION_ERROR
Definition emit_nullifier.hpp:40
bb::avm2::emit_nullifier::SR_EMIT_NULLIFIER_TREE_ROOT_NOT_CHANGED
static constexpr size_t SR_EMIT_NULLIFIER_TREE_ROOT_NOT_CHANGED
Definition emit_nullifier.hpp:41
bb::avm2::emit_nullifier::SR_EMIT_NULLIFIER_NUM_NULLIFIERS_EMITTED_INCREASE
static constexpr size_t SR_EMIT_NULLIFIER_NUM_NULLIFIERS_EMITTED_INCREASE
Definition emit_nullifier.hpp:43
bb::avm2::emit_nullifier::SR_MAX_NULLIFIER_WRITES_REACHED
static constexpr size_t SR_MAX_NULLIFIER_WRITES_REACHED
Definition emit_nullifier.hpp:38
bb::avm2::emit_nullifier::SR_EMIT_NULLIFIER_TREE_SIZE_INCREASE
static constexpr size_t SR_EMIT_NULLIFIER_TREE_SIZE_INCREASE
Definition emit_nullifier.hpp:42
bb::avm2::simulation::IndexedTreeCheck::write
AppendOnlyTreeSnapshot write(const FF &value, std::optional< IndexedTreeSiloingParameters > siloing_params, std::optional< uint64_t > public_inputs_index, const IndexedTreeLeafData &low_leaf_preimage, uint64_t low_leaf_index, std::span< const FF > low_leaf_sibling_path, const AppendOnlyTreeSnapshot &prev_snapshot, std::optional< std::span< const FF > > insertion_sibling_path) override
Writes a value into an indexed tree, or validates it already exists.
Definition indexed_tree_check.cpp:137
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:39
trace
TestTraceContainer trace
Definition data_copy.test.cpp:63
execution_trace.hpp
flavor_settings.hpp
indexed_tree_check_event.hpp
indexed_tree_check_trace.hpp
memory_types.hpp
mock_field_gt.hpp
mock_indexed_tree_check.hpp
mock_merkle_check.hpp
mock_poseidon2.hpp
mock_range_check.hpp
bb::avm2::constraining::TEST
TEST(AvmFixedVKTests, FixedVKCommitments)
Test that the fixed VK commitments agree with the ones computed from precomputed columns.
Definition avm_fixed_vk.test.cpp:52
bb::avm2::simulation::NullifierTreeLeafPreimage
crypto::merkle_tree::IndexedLeaf< crypto::merkle_tree::NullifierLeafValue > NullifierTreeLeafPreimage
Definition db_types.hpp:12
bb::avm2::simulation::poseidon2
crypto::Poseidon2< crypto::Poseidon2Bn254ScalarFieldParams > poseidon2
Definition contract_crypto.cpp:9
bb::avm2::simulation::IndexedTreeCheckEvent
std::variant< IndexedTreeReadWriteEvent, CheckPointEventType > IndexedTreeCheckEvent
Definition indexed_tree_check_event.hpp:64
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
bb::write
void write(B &buf, field2< base_field, Params > const &value)
Definition field2_declarations.hpp:151
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
indexed_tree_check.hpp
bb::field::invert
constexpr field invert() const noexcept
Definition field_impl.hpp:397
test_trace_container.hpp