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