merkle_tree.hpp

#pragma once
#include "barretenberg/stdlib/primitives/field/field.hpp"
#include "hash_path.hpp"
 
namespace proof_system::plonk {
namespace stdlib {
namespace merkle_tree {
 
using namespace barretenberg;
 
class MemoryStore;
 
template <typename Store> class MerkleTree {
  public:
    typedef uint256_t index_t;
 
    MerkleTree(Store& store, size_t depth, uint8_t tree_id = 0);
    MerkleTree(MerkleTree const& other) = delete;
    MerkleTree(MerkleTree&& other);
    ~MerkleTree();
 
    fr_hash_path get_hash_path(index_t index);
 
    fr_sibling_path get_sibling_path(index_t index);
 
    fr update_element(index_t index, fr const& value);
 
    fr root() const;
 
    size_t depth() const { return depth_; }
 
    index_t size() const;
 
  protected:
    void load_metadata();
 
    fr update_element(fr const& root, fr const& value, index_t index, size_t height);
 
    fr get_element(fr const& root, index_t index, size_t height);
 
    fr compute_zero_path_hash(size_t height, index_t index, fr const& value);
 
    fr binary_put(index_t a_index, fr const& a, fr const& b, size_t height);
 
    fr fork_stump(
        fr const& value1, index_t index1, fr const& value2, index_t index2, size_t height, size_t stump_height);
 
    void put(fr const& key, fr const& left, fr const& right);
 
    void put_stump(fr const& key, index_t index, fr const& value);
 
    void remove(fr const& key);
 
  protected:
    Store& store_;
    std::vector<fr> zero_hashes_;
    size_t depth_;
    uint8_t tree_id_;
};
 
extern template class MerkleTree<MemoryStore>;
 
} // namespace merkle_tree
} // namespace stdlib
} // namespace proof_system::plonk