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/nullifier_tree_check_event.hpp"
11#include "barretenberg/vm2/simulation/lib/merkle.hpp"
12#include "barretenberg/vm2/simulation/testing/mock_field_gt.hpp"
13#include "barretenberg/vm2/simulation/testing/mock_merkle_check.hpp"
14#include "barretenberg/vm2/simulation/testing/mock_nullifier_tree_check.hpp"
15#include "barretenberg/vm2/simulation/testing/mock_poseidon2.hpp"
16#include "barretenberg/vm2/simulation/testing/mock_range_check.hpp"
17#include "barretenberg/vm2/testing/macros.hpp"
18#include "barretenberg/vm2/tracegen/execution_trace.hpp"
19#include "barretenberg/vm2/tracegen/nullifier_tree_check_trace.hpp"
20#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
21
22namespace bb::avm2::constraining {
23namespace {
24
25using tracegen::ExecutionTraceBuilder;
26using tracegen::NullifierTreeCheckTraceBuilder;
27using tracegen::TestTraceContainer;
28
29using simulation::EventEmitter;
30using simulation::MockFieldGreaterThan;
31using simulation::MockMerkleCheck;
32using simulation::MockPoseidon2;
33using simulation::MockRangeCheck;
34using simulation::NullifierTreeCheck;
35using simulation::NullifierTreeCheckEvent;
36using simulation::NullifierTreeLeafPreimage;
37
38using testing::_;
39using testing::Return;
40using testing::StrictMock;
41
42using FF = AvmFlavorSettings::FF;
43using C = Column;
44using emit_nullifier = bb::avm2::emit_nullifier<FF>;
45using RawPoseidon2 = crypto::Poseidon2<crypto::Poseidon2Bn254ScalarFieldParams>;
46
47TEST(EmitNullifierConstrainingTest, Positive)
48{
49 uint64_t prev_num_nullifiers_emitted = MAX_NULLIFIERS_PER_TX - 1;
50 TestTraceContainer trace({ {
51 { C::execution_sel_execute_emit_nullifier, 1 },
52 { C::execution_register_0_, /*nullifier=*/42 },
53 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
54 { C::execution_remaining_nullifiers_inv, FF(MAX_NULLIFIERS_PER_TX - prev_num_nullifiers_emitted).invert() },
55 { C::execution_sel_write_nullifier, 1 },
56 { C::execution_sel_opcode_error, 0 },
57 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
58 { C::execution_prev_nullifier_tree_size, 1 },
59 { C::execution_nullifier_tree_size, 2 },
60 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
61 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted + 1 },
62 } });
63 check_relation<emit_nullifier>(trace);
64}
65
66TEST(EmitNullifierConstrainingTest, LimitReached)
67{
68 uint64_t prev_num_nullifiers_emitted = MAX_NULLIFIERS_PER_TX;
69 TestTraceContainer trace({ {
70 { C::execution_sel_execute_emit_nullifier, 1 },
71 { C::execution_register_0_, /*nullifier=*/42 },
72 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
73 { C::execution_sel_reached_max_nullifiers, 1 },
74 { C::execution_remaining_nullifiers_inv, 0 },
75 { C::execution_sel_write_nullifier, 0 },
76 { C::execution_sel_opcode_error, 1 },
77 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
78 { C::execution_prev_nullifier_tree_size, 1 },
79 { C::execution_nullifier_tree_size, 1 },
80 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
81 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted },
82 } });
83 check_relation<emit_nullifier>(trace);
84
85 // Negative test: sel_reached_max_nullifiers must be 1
86 trace.set(C::execution_sel_reached_max_nullifiers, 0, 0);
87 EXPECT_THROW_WITH_MESSAGE(check_relation<emit_nullifier>(trace, emit_nullifier::SR_MAX_NULLIFIER_WRITES_REACHED),
88 "MAX_NULLIFIER_WRITES_REACHED");
89 trace.set(C::execution_sel_reached_max_nullifiers, 0, 1);
90
91 // Negative test: sel_opcode_error must be on
92 trace.set(C::execution_sel_opcode_error, 0, 0);
93 EXPECT_THROW_WITH_MESSAGE(
94 check_relation<emit_nullifier>(trace, emit_nullifier::SR_OPCODE_ERROR_IF_VALIDATION_ERROR),
95 "OPCODE_ERROR_IF_VALIDATION_ERROR");
96 trace.set(C::execution_sel_opcode_error, 0, 1);
97
98 // Negative test: nullifier tree root must be the same
99 trace.set(C::execution_nullifier_tree_root, 0, 28);
100 EXPECT_THROW_WITH_MESSAGE(
101 check_relation<emit_nullifier>(trace, emit_nullifier::SR_EMIT_NULLIFIER_TREE_ROOT_NOT_CHANGED),
102 "EMIT_NULLIFIER_TREE_ROOT_NOT_CHANGED");
103
104 // Negative test: tree size must be the same
105 trace.set(C::execution_nullifier_tree_size, 0, 2);
106 EXPECT_THROW_WITH_MESSAGE(
107 check_relation<emit_nullifier>(trace, emit_nullifier::SR_EMIT_NULLIFIER_TREE_SIZE_INCREASE),
108 "EMIT_NULLIFIER_TREE_SIZE_INCREASE");
109
110 // Negative test: num nullifiers emitted must be the same
111 trace.set(C::execution_num_nullifiers_emitted, 0, prev_num_nullifiers_emitted + 1);
112 EXPECT_THROW_WITH_MESSAGE(
113 check_relation<emit_nullifier>(trace, emit_nullifier::SR_EMIT_NULLIFIER_NUM_NULLIFIERS_EMITTED_INCREASE),
114 "EMIT_NULLIFIER_NUM_NULLIFIERS_EMITTED_INCREASE");
115}
116
117TEST(EmitNullifierConstrainingTest, Interactions)
118{
119 StrictMock<MockPoseidon2> poseidon2;
120 StrictMock<MockMerkleCheck> merkle_check;
121 StrictMock<MockRangeCheck> range_check;
122 StrictMock<MockFieldGreaterThan> field_gt;
123
124 EventEmitter<NullifierTreeCheckEvent> nullifier_tree_check_event_emitter;
125 NullifierTreeCheck nullifier_tree_check(poseidon2, merkle_check, field_gt, nullifier_tree_check_event_emitter);
126
127 FF nullifier = 42;
128 AztecAddress contract_address = 0xdeadbeef;
129 FF siloed_nullifier = 66;
130 FF low_leaf_nullifier = 99; // siloed nullifier != low leaf nullifier (NO COLLISION)
131 FF low_leaf_hash = 77;
132 FF updated_low_leaf_hash = 101;
133 FF new_leaf_hash = 111;
134 FF pre_write_root = 27;
135 FF intermediate_root = 33;
136 FF post_write_root = 88;
137
138 // insertion sibling path
139 std::vector<FF> insertion_sibling_path = { 1, 2, 3 };
140
141 AppendOnlyTreeSnapshot prev_snapshot = AppendOnlyTreeSnapshot{
142 .root = pre_write_root,
143 .nextAvailableLeafIndex = 128,
144 };
145 uint32_t prev_num_nullifiers_emitted = 2;
146
147 // mock the nullifier > low leaf nullifier to return true
148 EXPECT_CALL(field_gt, ff_gt).WillOnce(Return(true));
149 // mock siloing, low leaf hashing, updated low leaf hashing, new leaf hashing
150 EXPECT_CALL(poseidon2, hash)
151 .WillOnce(Return(siloed_nullifier))
152 .WillOnce(Return(low_leaf_hash))
153 .WillOnce(Return(updated_low_leaf_hash))
154 .WillOnce(Return(new_leaf_hash));
155 // mock merkle check write
156 EXPECT_CALL(merkle_check, write).WillOnce(Return(intermediate_root)).WillOnce(Return(post_write_root));
157
158 // low leaf preimage
159 NullifierTreeLeafPreimage low_leaf_preimage = { NullifierLeafValue(low_leaf_nullifier), 0, 0 };
160
161 AppendOnlyTreeSnapshot next_snapshot = nullifier_tree_check.write(nullifier,
162 contract_address,
163 prev_num_nullifiers_emitted,
164 low_leaf_preimage,
165 0,
166 {},
167 prev_snapshot,
168 insertion_sibling_path);
169
170 TestTraceContainer trace({ {
171 { C::execution_sel_execute_emit_nullifier, 1 },
172 { C::execution_register_0_, nullifier },
173 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
174 { C::execution_remaining_nullifiers_inv, FF(MAX_NULLIFIERS_PER_TX - prev_num_nullifiers_emitted).invert() },
175 { C::execution_sel_write_nullifier, 1 },
176 { C::execution_sel_opcode_error, 0 }, // No errors!
177 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
178 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
179 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted + 1 }, // increment on success
180 { C::execution_prev_nullifier_tree_root, prev_snapshot.root },
181 { C::execution_nullifier_tree_root, next_snapshot.root },
182 { C::execution_prev_nullifier_tree_size, prev_snapshot.nextAvailableLeafIndex },
183 { C::execution_nullifier_tree_size, next_snapshot.nextAvailableLeafIndex },
184 { C::execution_contract_address, contract_address },
185 } });
186
187 NullifierTreeCheckTraceBuilder nullifier_tree_check_trace_builder;
188 nullifier_tree_check_trace_builder.process(nullifier_tree_check_event_emitter.dump_events(), trace);
189 check_relation<emit_nullifier>(trace);
190
191 check_interaction<ExecutionTraceBuilder, lookup_emit_nullifier_write_nullifier_settings>(trace);
192}
193
194TEST(EmitNullifierConstrainingTest, InteractionsCollision)
195{
196 StrictMock<MockPoseidon2> poseidon2;
197 StrictMock<MockMerkleCheck> merkle_check;
198 StrictMock<MockRangeCheck> range_check;
199 StrictMock<MockFieldGreaterThan> field_gt;
200
201 EventEmitter<NullifierTreeCheckEvent> nullifier_tree_check_event_emitter;
202 NullifierTreeCheck nullifier_tree_check(poseidon2, merkle_check, field_gt, nullifier_tree_check_event_emitter);
203
204 FF nullifier = 42;
205 AztecAddress contract_address = 0xdeadbeef;
206 FF siloed_nullifier = 66;
207 FF low_leaf_hash = 77;
208 FF pre_write_root = 27;
209
210 AppendOnlyTreeSnapshot prev_snapshot = AppendOnlyTreeSnapshot{
211 .root = pre_write_root,
212 .nextAvailableLeafIndex = 128,
213 };
214 uint32_t prev_num_nullifiers_emitted = 2;
215
216 // mock siloing and low leaf hashing
217 EXPECT_CALL(poseidon2, hash).WillOnce(Return(siloed_nullifier)).WillOnce(Return(low_leaf_hash));
218 // mock merkle check assert membership
219 EXPECT_CALL(merkle_check, assert_membership).WillOnce(Return());
220
221 // low leaf preimage
222 NullifierTreeLeafPreimage low_leaf_preimage = { NullifierLeafValue(siloed_nullifier), 0, 0 };
223
224 AppendOnlyTreeSnapshot next_snapshot = nullifier_tree_check.write(nullifier,
225 contract_address,
226 prev_num_nullifiers_emitted,
227 low_leaf_preimage,
228 0,
229 {},
230 prev_snapshot,
231 std::nullopt);
232
233 TestTraceContainer trace({ {
234 { C::execution_sel_execute_emit_nullifier, 1 },
235 { C::execution_register_0_, nullifier },
236 { C::execution_mem_tag_reg_0_, static_cast<uint8_t>(MemoryTag::FF) },
237 { C::execution_remaining_nullifiers_inv, FF(MAX_NULLIFIERS_PER_TX - prev_num_nullifiers_emitted).invert() },
238 { C::execution_sel_write_nullifier, 1 },
239 { C::execution_sel_opcode_error, 1 }, // collision
240 { C::execution_subtrace_operation_id, AVM_EXEC_OP_ID_EMIT_NULLIFIER },
241 { C::execution_prev_num_nullifiers_emitted, prev_num_nullifiers_emitted },
242 { C::execution_num_nullifiers_emitted, prev_num_nullifiers_emitted }, // No increment on error
243 { C::execution_prev_nullifier_tree_root, prev_snapshot.root },
244 { C::execution_nullifier_tree_root, next_snapshot.root },
245 { C::execution_prev_nullifier_tree_size, prev_snapshot.nextAvailableLeafIndex },
246 { C::execution_nullifier_tree_size, next_snapshot.nextAvailableLeafIndex },
247 { C::execution_contract_address, contract_address },
248 } });
249
250 NullifierTreeCheckTraceBuilder nullifier_tree_check_trace_builder;
251 nullifier_tree_check_trace_builder.process(nullifier_tree_check_event_emitter.dump_events(), trace);
252 check_relation<emit_nullifier>(trace);
253
254 check_interaction<ExecutionTraceBuilder, lookup_emit_nullifier_write_nullifier_settings>(trace);
255}
256
257} // namespace
258} // namespace bb::avm2::constraining
AVM_EXEC_OP_ID_EMIT_NULLIFIER
#define AVM_EXEC_OP_ID_EMIT_NULLIFIER
Definition aztec_constants.hpp:86
MAX_NULLIFIERS_PER_TX
#define MAX_NULLIFIERS_PER_TX
Definition aztec_constants.hpp:11
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:59
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:60
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:62
bb::avm2::emit_nullifier::SR_MAX_NULLIFIER_WRITES_REACHED
static constexpr size_t SR_MAX_NULLIFIER_WRITES_REACHED
Definition emit_nullifier.hpp:57
bb::avm2::emit_nullifier::SR_EMIT_NULLIFIER_TREE_SIZE_INCREASE
static constexpr size_t SR_EMIT_NULLIFIER_TREE_SIZE_INCREASE
Definition emit_nullifier.hpp:61
bb::avm2::tracegen::TraceContainer::set
void set(Column col, uint32_t row, const FF &value)
Definition trace_container.cpp:36
range_check
RangeCheck range_check
Definition data_copy.test.cpp:49
trace
TestTraceContainer trace
Definition data_copy.test.cpp:59
nullifier
FF nullifier
Definition nullifier_tree_check.test.cpp:72
contract_address
AztecAddress contract_address
Definition written_public_data_slots_tree_check.test.cpp:96
execution_trace.hpp
flavor_settings.hpp
EXPECT_THROW_WITH_MESSAGE
#define EXPECT_THROW_WITH_MESSAGE(code, expectedMessage)
Definition macros.hpp:7
memory_types.hpp
hash
void hash(State &state) noexcept
Definition merkle_tree.bench.cpp:28
mock_field_gt.hpp
mock_merkle_check.hpp
mock_nullifier_tree_check.hpp
mock_poseidon2.hpp
mock_range_check.hpp
bb::avm2::constraining::FF
AvmFlavorSettings::FF FF
Definition poseidon2.test.cpp:38
bb::avm2::constraining::TEST
TEST(TxExecutionConstrainingTest, WriteTreeValue)
Definition tx.test.cpp:508
bb::avm2::simulation::poseidon2
crypto::Poseidon2< crypto::Poseidon2Bn254ScalarFieldParams > poseidon2
Definition contract_crypto.cpp:9
bb::avm2::simulation::NullifierLeafValue
::bb::crypto::merkle_tree::NullifierLeafValue NullifierLeafValue
Definition db_interfaces.hpp:30
bb::avm2::simulation::NullifierTreeLeafPreimage
IndexedLeaf< NullifierLeafValue > NullifierTreeLeafPreimage
Definition nullifier_tree_check_event.hpp:12
bb::avm2::simulation::NullifierTreeCheckEvent
std::variant< NullifierTreeReadWriteEvent, CheckPointEventType > NullifierTreeCheckEvent
Definition nullifier_tree_check_event.hpp:47
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:16
bb::write
void write(B &buf, field2< base_field, Params > const &value)
Definition field2_declarations.hpp:155
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
nullifier_tree_check_event.hpp
nullifier_tree_check_trace.hpp
test_trace_container.hpp
field_gt
NiceMock< MockFieldGreaterThan > field_gt
Definition tx_execution.test.cpp:31