memory_tree.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/common/assert.hpp"
#include "hash_path.hpp"
 
namespace bb::crypto::merkle_tree {
 
template <typename HashingPolicy> class MemoryTree {
  public:
    MemoryTree(size_t depth);
 
    fr_hash_path get_hash_path(size_t index) const;
 
    fr_sibling_path get_sibling_path(size_t index) const;
 
    fr update_element(size_t index, fr const& value);
 
    fr root() const { return root_; }
 
    fr get_node(uint32_t level, size_t index) const;
 
  public:
    size_t depth_;
    size_t total_size_;
    bb::fr root_;
    std::vector<bb::fr> hashes_;
};
 
template <typename HashingPolicy>
MemoryTree<HashingPolicy>::MemoryTree(size_t depth)
    : depth_(depth)
{
 
    BB_ASSERT_GTE(depth_, 1U);
    BB_ASSERT_LTE(depth, 20U);
    total_size_ = 1UL << depth_;
    hashes_.resize(total_size_ * 2 - 2);
 
    // Build the entire tree.
    auto current = fr(0);
    size_t layer_size = total_size_;
    for (size_t offset = 0; offset < hashes_.size(); offset += layer_size, layer_size /= 2) {
        for (size_t i = 0; i < layer_size; ++i) {
            hashes_[offset + i] = current;
        }
        current = HashingPolicy::hash_pair(current, current);
    }
 
    root_ = current;
}
 
template <typename HashingPolicy> fr MemoryTree<HashingPolicy>::get_node(uint32_t level, size_t index) const
{
    auto offset = 0UL;
    for (size_t i = depth_; i > level; i--) {
        offset += 1UL << i;
    }
    return hashes_[offset + index];
}
 
template <typename HashingPolicy> fr_hash_path MemoryTree<HashingPolicy>::get_hash_path(size_t index) const
{
    fr_hash_path path(depth_);
    size_t offset = 0;
    size_t layer_size = total_size_;
    for (size_t i = 0; i < depth_; ++i) {
        index -= index & 0x1;
        path[i] = std::make_pair(hashes_[offset + index], hashes_[offset + index + 1]);
        offset += layer_size;
        layer_size >>= 1;
        index >>= 1;
    }
    return path;
}
 
template <typename HashingPolicy> fr_sibling_path MemoryTree<HashingPolicy>::get_sibling_path(size_t index) const
{
    fr_sibling_path path(depth_);
    size_t offset = 0;
    size_t layer_size = total_size_;
    for (size_t i = 0; i < depth_; i++) {
        if (index % 2 == 0) {
            path[i] = hashes_[offset + index + 1];
        } else {
            path[i] = hashes_[offset + index - 1];
        }
        offset += layer_size;
        layer_size >>= 1;
        index >>= 1;
    }
    return path;
}
 
template <typename HashingPolicy> fr MemoryTree<HashingPolicy>::update_element(size_t index, fr const& value)
{
    size_t offset = 0;
    size_t layer_size = total_size_;
    fr current = value;
    for (size_t i = 0; i < depth_; ++i) {
        hashes_[offset + index] = current;
        index &= (~0ULL) - 1;
        current = HashingPolicy::hash_pair(hashes_[offset + index], hashes_[offset + index + 1]);
        offset += layer_size;
        layer_size >>= 1;
        index >>= 1;
    }
    root_ = current;
    return root_;
}
 
} // namespace bb::crypto::merkle_tree