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