#include <indexed_tree_check.hpp>

Inheritance diagram for bb::avm2::simulation::IndexedTreeCheck:

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

void	assert_read (const FF &value, std::optional< IndexedTreeSiloingParameters > siloing_params, bool exists, const IndexedTreeLeafData &low_leaf_preimage, uint64_t low_leaf_index, std::span< const FF > sibling_path, const AppendOnlyTreeSnapshot &snapshot) override
	Performs a membership/non-membership read check on an indexed tree.

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.

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

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

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

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

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

Private Member Functions
FF	silo (const FF &nullifier, IndexedTreeSiloingParameters siloing_params)
	Computes the siloed value by hashing the separator, address, and value via Poseidon2.

void	validate_low_leaf (const FF &value, const IndexedTreeLeafData &low_leaf_preimage, bool exists)
	Validates the low leaf preimage against the target value for membership/non-membership.

Private Attributes
EventEmitterInterface< IndexedTreeCheckEvent > &	events

Poseidon2Interface &	poseidon2

MerkleCheckInterface &	merkle_check

FieldGreaterThanInterface &	field_gt

Detailed Description

Definition at line 19 of file indexed_tree_check.hpp.

Constructor & Destructor Documentation

◆ IndexedTreeCheck()

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

inline

Definition at line 21 of file indexed_tree_check.hpp.

Member Function Documentation

◆ assert_read()

void bb::avm2::simulation::IndexedTreeCheck::assert_read	(	const FF &	source_value,
		std::optional< IndexedTreeSiloingParameters >	siloing_params,
		bool	exists,
		const IndexedTreeLeafData &	low_leaf_preimage,
		uint64_t	low_leaf_index,
		std::span< const FF >	sibling_path,
		const AppendOnlyTreeSnapshot &	snapshot
	)

overridevirtual

Performs a membership/non-membership read check on an indexed tree.

Verifies whether a value exists or does not exist in a given indexed tree at a given snapshot, using the low leaf membership proof technique. The value is optionally siloed before checking.

The low leaf is proven to be a member of the tree via Merkle proof, then validated against the target value according to indexed tree invariants (see validate_low_leaf).

Parameters

source_value	The raw (possibly unsiloed) value to check.
siloing_params	If present, the value is siloed with this address and separator before checking.
exists	True to prove membership, false to prove non-membership.
low_leaf_preimage	The preimage of the low leaf.
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::IndexedTreeCheckInterface.

Definition at line 77 of file indexed_tree_check.cpp.

◆ on_checkpoint_committed()

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

overridevirtual

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

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

Definition at line 222 of file indexed_tree_check.cpp.

◆ on_checkpoint_created()

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

overridevirtual

Emits a checkpoint creation event for the indexed tree.

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

Definition at line 216 of file indexed_tree_check.cpp.

◆ on_checkpoint_reverted()

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

overridevirtual

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

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

Definition at line 228 of file indexed_tree_check.cpp.

◆ silo()

FF bb::avm2::simulation::IndexedTreeCheck::silo	(	const FF &	value,
		IndexedTreeSiloingParameters	siloing_params
	)

private

Computes the siloed value by hashing the separator, address, and value via Poseidon2.

Siloing binds a value to its originating contract, preventing cross-contract collisions.

Parameters

value	The original (inner) value.
siloing_params	The siloing parameters (address and domain separator).

Returns: The siloed value: Poseidon2(separator, address, value).

Definition at line 16 of file indexed_tree_check.cpp.

◆ validate_low_leaf()

void bb::avm2::simulation::IndexedTreeCheck::validate_low_leaf	(	const FF &	value,
		const IndexedTreeLeafData &	low_leaf_preimage,
		bool	exists
	)

private

Validates the low leaf preimage against the target value for membership/non-membership.

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

For membership ( exists = true ): the low leaf value must equal value. For non-membership ( exists = false ): value must be greater than the low leaf value, and (if next_value != 0) less than the low leaf next_value.

Parameters

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

Exceptions

std::runtime_error If validation fails.

Definition at line 38 of file indexed_tree_check.cpp.

◆ write()

AppendOnlyTreeSnapshot bb::avm2::simulation::IndexedTreeCheck::write	(	const FF &	source_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
	)

overridevirtual

Writes a value into an indexed tree, or validates it already exists.

Handles both new insertions and duplicate writes. If the value 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 leaf.

The value is optionally siloed before insertion. The low leaf is validated via indexed tree invariants. For a new insertion, two Merkle writes occur:

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

Parameters

source_value	The raw (possibly unsiloed) value to insert.
siloing_params	If present, the value is siloed with these parameters before insertion.
public_inputs_index	If present, the index into public inputs for this write.
low_leaf_preimage	The preimage of the low leaf.
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 value already exists and no insertion occurs.

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

Exceptions

std::runtime_error If validation fails.

Implements bb::avm2::simulation::IndexedTreeCheckInterface.

Definition at line 137 of file indexed_tree_check.cpp.

Member Data Documentation

◆ events

EventEmitterInterface<IndexedTreeCheckEvent>& bb::avm2::simulation::IndexedTreeCheck::events

private

Definition at line 55 of file indexed_tree_check.hpp.

◆ field_gt

FieldGreaterThanInterface& bb::avm2::simulation::IndexedTreeCheck::field_gt

private

Definition at line 58 of file indexed_tree_check.hpp.

◆ merkle_check

MerkleCheckInterface& bb::avm2::simulation::IndexedTreeCheck::merkle_check

private

Definition at line 57 of file indexed_tree_check.hpp.

◆ poseidon2

Poseidon2Interface& bb::avm2::simulation::IndexedTreeCheck::poseidon2

private

Definition at line 56 of file indexed_tree_check.hpp.

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

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ IndexedTreeCheck()

Member Function Documentation

◆ assert_read()

◆ on_checkpoint_committed()

◆ on_checkpoint_created()

◆ on_checkpoint_reverted()

◆ silo()

◆ validate_low_leaf()

◆ write()

Member Data Documentation

◆ events

◆ field_gt

◆ merkle_check

◆ poseidon2