#include <nullifier_tree_check.hpp>

Inheritance diagram for bb::avm2::simulation::NullifierTreeCheck:

Public Member Functions
	NullifierTreeCheck (Poseidon2Interface &poseidon2, MerkleCheckInterface &merkle_check, FieldGreaterThanInterface &field_gt, EventEmitterInterface< NullifierTreeCheckEvent > &event_emitter)

void	assert_read (const FF &nullifier, std::optional< AztecAddress > contract_address, bool exists, const NullifierTreeLeafPreimage &low_leaf_preimage, uint64_t low_leaf_index, std::span< const FF > sibling_path, const AppendOnlyTreeSnapshot &snapshot) override
	Performs a nullifier membership/non-membership check on the nullifier tree.

AppendOnlyTreeSnapshot	write (const FF &nullifier, std::optional< AztecAddress > contract_address, uint64_t nullifier_counter, const NullifierTreeLeafPreimage &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
	Inserts a nullifier into the nullifier tree or verifies it already exists.

void	on_checkpoint_created () override
	Emits a checkpoint creation event for the nullifier tree.

void	on_checkpoint_committed () override
	Emits a checkpoint commit event, finalizing pending nullifier tree changes.

void	on_checkpoint_reverted () override
	Emits a checkpoint revert event, rolling back pending nullifier tree changes.

Public Member Functions inherited from bb::avm2::simulation::NullifierTreeCheckInterface
virtual	~NullifierTreeCheckInterface ()=default

Public Member Functions inherited from bb::avm2::simulation::CheckpointNotifiable
virtual	~CheckpointNotifiable ()=default

Private Member Functions
FF	silo_nullifier (const FF &nullifier, AztecAddress contract_address)
	Computes the siloed nullifier by hashing the contract address with the nullifier.

void	validate_low_leaf (const FF &nullifier, const NullifierTreeLeafPreimage &low_leaf_preimage, bool exists)
	Validates the low leaf preimage against the nullifier for membership/non-membership checks.

Private Attributes
EventEmitterInterface< NullifierTreeCheckEvent > &	events

Poseidon2Interface &	poseidon2

MerkleCheckInterface &	merkle_check

FieldGreaterThanInterface &	field_gt

Detailed Description

Definition at line 19 of file nullifier_tree_check.hpp.

Constructor & Destructor Documentation

◆ NullifierTreeCheck()

bb::avm2::simulation::NullifierTreeCheck::NullifierTreeCheck	(	Poseidon2Interface &	poseidon2,
		MerkleCheckInterface &	merkle_check,
		FieldGreaterThanInterface &	field_gt,
		EventEmitterInterface< NullifierTreeCheckEvent > &	event_emitter
	)

inline

Definition at line 21 of file nullifier_tree_check.hpp.

Member Function Documentation

◆ assert_read()

void bb::avm2::simulation::NullifierTreeCheck::assert_read	(	const FF &	source_nullifier,
		std::optional< AztecAddress >	contract_address,
		bool	exists,
		const NullifierTreeLeafPreimage &	low_leaf_preimage,
		uint64_t	low_leaf_index,
		std::span< const FF >	sibling_path,
		const AppendOnlyTreeSnapshot &	snapshot
	)

overridevirtual

Performs a nullifier membership/non-membership check on the nullifier tree.

This method verifies whether a nullifier exists or does not exist in the nullifier tree at a given snapshot, using the indexed tree low-leaf membership proof technique. It optionally silos the nullifier with a contract address before checking.

The low leaf must be proven to be a member of the tree via Merkle proof. Then the nullifier is validated against the low leaf according to the indexed tree invariants (see validate_low_leaf).

Parameters

source_nullifier	The raw (possibly unsiloed) nullifier to check.
contract_address	If present, the nullifier is siloed with this address before checking.
exists	True to prove membership, false to prove non-membership.
low_leaf_preimage	The preimage of the low leaf for the nullifier.
low_leaf_index	The index of the low leaf in the tree.
sibling_path	The Merkle sibling path for the low leaf.
snapshot	The tree snapshot to verify against.

Exceptions

std::runtime_error If validation fails.

Implements bb::avm2::simulation::NullifierTreeCheckInterface.

Definition at line 83 of file nullifier_tree_check.cpp.

◆ on_checkpoint_committed()

void bb::avm2::simulation::NullifierTreeCheck::on_checkpoint_committed ( )

overridevirtual

Emits a checkpoint commit event, finalizing pending nullifier tree changes.

Implements bb::avm2::simulation::CheckpointNotifiable.

Definition at line 221 of file nullifier_tree_check.cpp.

◆ on_checkpoint_created()

void bb::avm2::simulation::NullifierTreeCheck::on_checkpoint_created ( )

overridevirtual

Emits a checkpoint creation event for the nullifier tree.

Implements bb::avm2::simulation::CheckpointNotifiable.

Definition at line 215 of file nullifier_tree_check.cpp.

◆ on_checkpoint_reverted()

void bb::avm2::simulation::NullifierTreeCheck::on_checkpoint_reverted ( )

overridevirtual

Emits a checkpoint revert event, rolling back pending nullifier tree changes.

Implements bb::avm2::simulation::CheckpointNotifiable.

Definition at line 227 of file nullifier_tree_check.cpp.

◆ silo_nullifier()

FF bb::avm2::simulation::NullifierTreeCheck::silo_nullifier	(	const FF &	nullifier,
		AztecAddress	contract_address
	)

private

Computes the siloed nullifier by hashing the contract address with the nullifier.

Siloing binds a nullifier to its originating contract, preventing cross-contract collisions. Uses Poseidon2 with a domain separator for siloed nullifiers.

Parameters

nullifier	The original (inner) nullifier.
contract_address	The address of the contract that created the nullifier.

Returns: The siloed nullifier: Poseidon2(DOM_SEP__SILOED_NULLIFIER, contract_address, nullifier).

Definition at line 19 of file nullifier_tree_check.cpp.

◆ validate_low_leaf()

void bb::avm2::simulation::NullifierTreeCheck::validate_low_leaf	(	const FF &	nullifier,
		const NullifierTreeLeafPreimage &	low_leaf_preimage,
		bool	exists
	)

private

Validates the low leaf preimage against the nullifier for membership/non-membership checks.

In an indexed nullifier tree, the low leaf contains the largest nullifier less than the target nullifier. This function validates the low leaf properties to prove either membership (when the low leaf nullifier equals the nullifier) or non-membership (when the nullifier falls between the low leaf nullifier and its next key). Note that the presence of the low leaf in the tree needs to be proven separately.

For membership ( exists = true ): the low leaf's nullifier must equal nullifier. For non-membership ( exists = false ): the nullifier must be greater than the low leaf's nullifier and (if nextKey != 0) less than the low leaf's nextKey.

Parameters

nullifier	The (possibly siloed) nullifier being checked.
low_leaf_preimage	The preimage of the low leaf in the nullifier tree.
exists	True if proving membership, false if proving non-membership.

Exceptions

std::runtime_error If validation fails (e.g., membership check when low leaf doesn't match).

Definition at line 41 of file nullifier_tree_check.cpp.

◆ write()

AppendOnlyTreeSnapshot bb::avm2::simulation::NullifierTreeCheck::write	(	const FF &	source_nullifier,
		std::optional< AztecAddress >	contract_address,
		uint64_t	nullifier_counter,
		const NullifierTreeLeafPreimage &	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
	)

overridevirtual

Inserts a nullifier into the nullifier tree or verifies it already exists.

This method handles both successful and failing nullifier writes. If the nullifier already exists in the tree ( insertion_sibling_path is nullopt ), it validates membership. Otherwise, it performs an indexed tree insertion by updating the low leaf's next pointer and appending the new nullifier as a leaf.

The nullifier is optionally siloed with a contract address before insertion. The low leaf must be validated via indexed tree invariants. For a new insertion, two Merkle writes occur:

Update the low leaf to point to the new nullifier.
Insert the new nullifier leaf at the next available index.

Parameters

source_nullifier	The raw (possibly unsiloed) nullifier to insert.
contract_address	If present, the nullifier is siloed with this address before insertion.
nullifier_counter	The index of the nullifier within this transaction.
low_leaf_preimage	The preimage of the low leaf for the nullifier.
low_leaf_index	The index of the low leaf in the tree.
low_leaf_sibling_path	The Merkle sibling path for the low leaf.
prev_snapshot	The tree snapshot before the write.
insertion_sibling_path	If present, the sibling path for inserting a new leaf. If nullopt, the nullifier already exists and no insertion occurs.

Returns: The updated tree snapshot after the write (unchanged if nullifier already exists).

Exceptions

std::runtime_error If validation fails.

Implements bb::avm2::simulation::NullifierTreeCheckInterface.

Definition at line 140 of file nullifier_tree_check.cpp.

Member Data Documentation

◆ events

EventEmitterInterface<NullifierTreeCheckEvent>& bb::avm2::simulation::NullifierTreeCheck::events

private

Definition at line 55 of file nullifier_tree_check.hpp.

◆ field_gt

FieldGreaterThanInterface& bb::avm2::simulation::NullifierTreeCheck::field_gt

private

Definition at line 58 of file nullifier_tree_check.hpp.

◆ merkle_check

MerkleCheckInterface& bb::avm2::simulation::NullifierTreeCheck::merkle_check

private

Definition at line 57 of file nullifier_tree_check.hpp.

◆ poseidon2

Poseidon2Interface& bb::avm2::simulation::NullifierTreeCheck::poseidon2

private

Definition at line 56 of file nullifier_tree_check.hpp.

The documentation for this class was generated from the following files:

src/barretenberg/vm2/simulation/gadgets/nullifier_tree_check.hpp
src/barretenberg/vm2/simulation/gadgets/nullifier_tree_check.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ NullifierTreeCheck()

Member Function Documentation

◆ assert_read()

◆ on_checkpoint_committed()

◆ on_checkpoint_created()

◆ on_checkpoint_reverted()

◆ silo_nullifier()

◆ validate_low_leaf()

◆ write()

Member Data Documentation

◆ events

◆ field_gt

◆ merkle_check

◆ poseidon2