indexed_tree_check.cpp

Go to the documentation of this file.

#include "barretenberg/vm2/simulation/gadgets/indexed_tree_check.hpp"
 
#include <stdexcept>
 
namespace bb::avm2::simulation {
 
FF IndexedTreeCheck::silo(const FF& value, IndexedTreeSiloingParameters siloing_params)
{
    return poseidon2.hash({ siloing_params.siloing_separator, siloing_params.address, value });
}
 
void IndexedTreeCheck::validate_low_leaf(const FF& value, const IndexedTreeLeafData& low_leaf_preimage, bool exists)
{
    bool low_leaf_matches = low_leaf_preimage.value == value;
    // We base the checking on whether the low leaf matches instead of exists, to match PIL behavior.
    if (low_leaf_matches) {
        if (!exists) {
            throw std::runtime_error("Indexed tree non-membership check failed");
        }
    } else {
        if (!field_gt.ff_gt(value, low_leaf_preimage.value)) {
            throw std::runtime_error("Low leaf value is GTE leaf value");
        }
        if (low_leaf_preimage.next_value != 0 && !field_gt.ff_gt(low_leaf_preimage.next_value, value)) {
            throw std::runtime_error("Leaf value is GTE low leaf next value");
        }
        if (exists) {
            throw std::runtime_error("Indexed tree membership check failed");
        }
    }
}
 
void 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)
{
    FF value = source_value;
    std::optional<IndexedLeafSiloingData> siloing_data = std::nullopt;
    if (siloing_params.has_value()) {
        value = silo(value, siloing_params.value());
        siloing_data = IndexedLeafSiloingData{
            .siloed_value = value,
            .parameters = siloing_params.value(),
        };
    }
    // Low leaf membership
    FF low_leaf_hash = poseidon2.hash(low_leaf_preimage.get_hash_inputs());
    merkle_check.assert_membership(
        merkle_hash_domain_separator, low_leaf_hash, low_leaf_index, sibling_path, snapshot.root);
 
    // Low leaf and value validation
    validate_low_leaf(value, low_leaf_preimage, exists);
 
    events.emit(IndexedTreeReadWriteEvent{
        .value = source_value,
        .prev_snapshot = snapshot,
        .next_snapshot = snapshot,
        .tree_height = sibling_path.size(),
        .merkle_hash_separator = FF(merkle_hash_domain_separator),
        .low_leaf_data = low_leaf_preimage,
        .low_leaf_hash = low_leaf_hash,
        .low_leaf_index = low_leaf_index,
        .siloing_data = siloing_data,
    });
}
 
AppendOnlyTreeSnapshot 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)
{
    FF value = source_value;
    std::optional<IndexedLeafSiloingData> siloing_data = std::nullopt;
    if (siloing_params.has_value()) {
        value = silo(value, siloing_params.value());
        siloing_data = IndexedLeafSiloingData{ .siloed_value = value, .parameters = siloing_params.value() };
    }
    bool exists = !insertion_sibling_path.has_value();
 
    // Low leaf validation
    validate_low_leaf(value, low_leaf_preimage, exists);
 
    AppendOnlyTreeSnapshot next_snapshot = prev_snapshot;
    std::optional<IndexedLeafAppendData> append_data = std::nullopt;
 
    FF low_leaf_hash = poseidon2.hash(low_leaf_preimage.get_hash_inputs());
 
    if (exists) {
        merkle_check.assert_membership(
            merkle_hash_domain_separator, low_leaf_hash, low_leaf_index, low_leaf_sibling_path, prev_snapshot.root);
    } else {
        // Low leaf update
        IndexedTreeLeafData updated_low_leaf_preimage = low_leaf_preimage;
        updated_low_leaf_preimage.next_index = prev_snapshot.next_available_leaf_index;
        updated_low_leaf_preimage.next_value = value;
        FF updated_low_leaf_hash = poseidon2.hash(updated_low_leaf_preimage.get_hash_inputs());
 
        FF intermediate_root = merkle_check.write(merkle_hash_domain_separator,
                                                  low_leaf_hash,
                                                  updated_low_leaf_hash,
                                                  low_leaf_index,
                                                  low_leaf_sibling_path,
                                                  prev_snapshot.root);
 
        // Insertion
        IndexedTreeLeafData new_leaf_preimage = {
            .value = value,
            .next_value = low_leaf_preimage.next_value,
            .next_index = low_leaf_preimage.next_index,
        };
 
        FF new_leaf_hash = poseidon2.hash(new_leaf_preimage.get_hash_inputs());
 
        FF write_root = merkle_check.write(merkle_hash_domain_separator,
                                           FF(0),
                                           new_leaf_hash,
                                           prev_snapshot.next_available_leaf_index,
                                           insertion_sibling_path.value(),
                                           intermediate_root);
 
        next_snapshot = AppendOnlyTreeSnapshot{
            .root = write_root,
            .next_available_leaf_index = prev_snapshot.next_available_leaf_index + 1,
        };
        append_data = IndexedLeafAppendData{
            .updated_low_leaf_hash = updated_low_leaf_hash,
            .new_leaf_hash = new_leaf_hash,
            .intermediate_root = intermediate_root,
        };
    }
 
    events.emit(IndexedTreeReadWriteEvent{ .value = source_value,
                                           .prev_snapshot = prev_snapshot,
                                           .next_snapshot = next_snapshot,
                                           .tree_height = low_leaf_sibling_path.size(),
                                           .merkle_hash_separator = FF(merkle_hash_domain_separator),
                                           .low_leaf_data = low_leaf_preimage,
                                           .low_leaf_hash = low_leaf_hash,
                                           .low_leaf_index = low_leaf_index,
                                           .write = true,
                                           .siloing_data = siloing_data,
                                           .public_inputs_index = public_inputs_index,
                                           .append_data = append_data });
 
    return next_snapshot;
}
 
void IndexedTreeCheck::on_checkpoint_created()
{
    events.emit(CheckPointEventType::CREATE_CHECKPOINT);
}
 
void IndexedTreeCheck::on_checkpoint_committed()
{
    events.emit(CheckPointEventType::COMMIT_CHECKPOINT);
}
 
void IndexedTreeCheck::on_checkpoint_reverted()
{
    events.emit(CheckPointEventType::REVERT_CHECKPOINT);
}
 
} // namespace bb::avm2::simulation