Merkle.h

Go to the documentation of this file.

#pragma once
 
#include "IStorageBackend.h"
 
#include <array>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <vector>

 
namespace nt {

    using Hash32 = std::array<uint8_t, 32>;

    Hash32 hex_to_bin(const std::string& hex);

    std::string bin_to_hex(const Hash32& bin);
 
    template <typename Key> class Merkle {
      public:
        static constexpr size_t B = 64;

        static std::string Insert(IStorageBackend& store, const std::string& root_hex,
                                  const Key& key, const Hash32& payload);

        static std::string Remove(IStorageBackend& store, const std::string& root_hex,
                                  const Key& key);

        static std::optional<Hash32> Get(IStorageBackend& store, const std::string& root_hex,
                                         const Key& key);

        struct Entry {
            Key key;
            Hash32 payload;
        };

        static std::vector<Entry> Page(IStorageBackend& store, const std::string& root_hex,
                                       size_t offset, size_t limit);
 
      private:
        struct LeafEntry {
            Key key;
            Hash32 payload;
        };
 
        struct LeafNode {
            std::vector<LeafEntry> entries;
        };
 
        struct ChildEntry {
            uint64_t leaf_count;
            Key min_key;
            Hash32 child_hash;
        };
 
        struct InternalNode {
            std::vector<ChildEntry> entries;
        };
 
        // Wire format
        static std::vector<uint8_t> encode_leaf(const LeafNode& n);
        static std::vector<uint8_t> encode_internal(const InternalNode& n);
        static LeafNode decode_leaf(const std::vector<uint8_t>& bytes);
        static InternalNode decode_internal(const std::vector<uint8_t>& bytes);
        static bool is_leaf_bytes(const std::vector<uint8_t>& bytes);
 
        // Storage helpers
        static std::vector<uint8_t> load_node(IStorageBackend& store, const std::string& hash_hex);
        static std::string store_leaf(IStorageBackend& store, const LeafNode& n);
        static std::string store_internal(IStorageBackend& store, const InternalNode& n);

        static Key subtree_min_key(IStorageBackend& store, const std::string& node_hex);

        static size_t route(const InternalNode& node, const Key& target);
 
        struct InsertResult {
            std::string new_hash;
            uint64_t leaf_count = 0;
            bool did_split = false;
            uint64_t split_leaf_count = 0;
            Key split_min_key{};
            std::string split_hash;
        };
 
        static InsertResult insert_into(IStorageBackend& store, const std::string& node_hex,
                                        const Key& key, const Hash32& payload);
 
        struct RemoveResult {
            std::string new_hash;
            uint64_t leaf_count = 0;
        };
 
        static RemoveResult remove_from(IStorageBackend& store, const std::string& node_hex,
                                        const Key& key);
 
        static void page_from(IStorageBackend& store, const std::string& node_hex, size_t& offset,
                              size_t limit, std::vector<Entry>& out);
 
        static std::optional<Hash32> get_from(IStorageBackend& store, const std::string& node_hex,
                                              const Key& key);
    };
 
} // namespace nt