nullifier_leaf.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
#include "barretenberg/crypto/merkle_tree/types.hpp"
#include "barretenberg/crypto/pedersen_commitment/pedersen.hpp"
#include "barretenberg/serialize/msgpack.hpp"
#include "barretenberg/stdlib/hash/poseidon2/poseidon2.hpp"
 
namespace bb::crypto::merkle_tree {
 
struct indexed_nullifier_leaf {
    fr value;
    index_t nextIndex;
    fr nextValue;
 
    // For serialization, update with any new fields
    MSGPACK_FIELDS(value, nextIndex, nextValue);
    bool operator==(indexed_nullifier_leaf const&) const = default;
 
    std::ostream& operator<<(std::ostream& os)
    {
        os << "value = " << value << "\nnextIdx = " << nextIndex << "\nnextVal = " << nextValue;
        return os;
    }
 
    std::vector<fr> get_hash_inputs() const { return std::vector<fr>{ value, nextValue, nextIndex }; }
 
    static indexed_nullifier_leaf zero()
    {
        return indexed_nullifier_leaf{ .value = 0, .nextIndex = 0, .nextValue = 0 };
    }
};
 
template <typename HashingPolicy> class WrappedNullifierLeaf {
 
  public:
    // Initialize with a nullifier leaf
    WrappedNullifierLeaf(indexed_nullifier_leaf value)
        : data(value)
    {}
    // Initialize an empty leaf
    WrappedNullifierLeaf()
        : data(std::nullopt)
    {}
 
    bool operator==(WrappedNullifierLeaf const&) const = default;
 
    bool has_value() const { return data.has_value(); }
 
    indexed_nullifier_leaf unwrap() const { return data.value(); }
 
    void set(indexed_nullifier_leaf value) { data.emplace(value); }
 
    bb::fr hash() const
    {
        return data.has_value() ? HashingPolicy::hash(data.value().get_hash_inputs()) : bb::fr::zero();
    }
 
    static WrappedNullifierLeaf<HashingPolicy> zero() { return WrappedNullifierLeaf<HashingPolicy>(); }
 
  private:
    // Underlying data
    std::optional<indexed_nullifier_leaf> data;
};
 
template <typename HashingPolicy>
inline std::pair<size_t, bool> find_closest_leaf(std::vector<WrappedNullifierLeaf<HashingPolicy>> const& leaves_,
                                                 fr const& new_value)
{
    std::vector<uint256_t> diff;
    bool repeated = false;
    auto new_value_ = uint256_t(new_value);
 
    for (size_t i = 0; i < leaves_.size(); i++) {
 
        if (!leaves_[i].has_value()) {
            diff.push_back(new_value_);
            continue;
        }
 
        auto leaf_value_ = uint256_t(leaves_[i].unwrap().value);
        if (leaf_value_ > new_value_) {
            diff.push_back(leaf_value_);
        } else if (leaf_value_ == new_value_) {
            repeated = true;
            return std::make_pair(i, repeated);
        } else {
            diff.push_back(new_value_ - leaf_value_);
        }
    }
    auto it = std::min_element(diff.begin(), diff.end());
    return std::make_pair(static_cast<size_t>(it - diff.begin()), repeated);
}
 
} // namespace bb::crypto::merkle_tree