diff options
Diffstat (limited to 'include/Merkle.h')
| -rw-r--r-- | include/Merkle.h | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/include/Merkle.h b/include/Merkle.h new file mode 100644 index 0000000..8380093 --- /dev/null +++ b/include/Merkle.h @@ -0,0 +1,164 @@ +#pragma once + +#include "IStorageBackend.h" + +#include <array> +#include <cstddef> +#include <cstdint> +#include <string> +#include <vector> + +/** + * @file Merkle.h + * @brief Sorted content-addressed B-tree over SHA-256 tuple hash hex strings. + * + * Each node is stored as an immutable blob in IStorageBackend via Put/Get. + * All three operations load only the nodes on the path from root to the target + * leaf — O(log_B(n)) nodes in memory at once, never the whole tree. + * + * **Branching factor B = 64**: leaves hold up to 64 hashes; internal nodes hold + * up to 64 child entries. At B=64 and 1 billion tuples the tree is at most + * 5 levels deep (~20 KB peak working set). + * + * **Immutability**: nodes are never overwritten once written (content-addressed). + * Insert and Remove produce new nodes only along the modified path; old nodes + * remain valid for any snapshot that still holds their root hash. + * + * **Internal node entry layout** (leaf_count | min_hash | child_hash): + * - `leaf_count` enables O(log_B(n) + limit) offset navigation for Page() + * without loading sibling subtrees. + * - `min_hash` (smallest tuple hash in the subtree) is the routing key. + * - `child_hash` is the content-addressed hash of the child node blob. + * + * **Invariants** (asserted in debug builds): + * - No leaf or internal node is ever empty. + * - Internal node entries are sorted ascending by min_hash. + * - All public entry points that accept a hex hash throw `std::invalid_argument` + * when the string is not exactly 64 lowercase hex characters. + * + * @todo Add bounds checking in decode_leaf / decode_internal: validate that the + * reported entry count does not exceed the actual blob size before reading. + * Currently a truncated or corrupt blob causes out-of-bounds reads. + */ + +namespace nt { + +class Merkle { +public: + static constexpr size_t B = 64; + + /** + * @brief Insert a tuple hash into the tree. + * @param store KV backend for node serialization. + * @param root_hex Current root hash (empty string = empty tree). + * @param hash_hex 64-char hex SHA-256 of the tuple to insert. + * @return New root hash. Equal to root_hex when the hash was already present. + */ + static std::string Insert(IStorageBackend& store, + const std::string& root_hex, + const std::string& hash_hex); + + /** + * @brief Remove a tuple hash from the tree. + * @param store KV backend. + * @param root_hex Current root hash. + * @param hash_hex 64-char hex SHA-256 of the tuple to remove. + * @return New root hash. Empty string when the tree becomes empty. + */ + static std::string Remove(IStorageBackend& store, + const std::string& root_hex, + const std::string& hash_hex); + + /** + * @brief Page through tuple hashes in sorted order. + * + * Descends to the leaf at logical position @p offset using cumulative + * leaf_counts stored in internal nodes, then walks forward collecting at + * most @p limit hashes. Only the nodes on the active path are loaded; + * sibling subtrees are never touched. + * + * @param store KV backend. + * @param root_hex Current root hash. + * @param offset Zero-based logical tuple offset. + * @param limit Maximum number of hashes to return. + * @return Hex hash strings in sorted order. Empty when past the end. + */ + static std::vector<std::string> Page(IStorageBackend& store, + const std::string& root_hex, + size_t offset, + size_t limit); + +private: + using Hash32 = std::array<uint8_t, 32>; + + struct LeafNode { + std::vector<Hash32> hashes; // sorted ascending, len ≤ B + }; + + // Wire: 8-byte leaf_count | 32-byte min_hash | 32-byte child_hash + struct ChildEntry { + uint64_t leaf_count; // number of tuple hashes in this subtree + Hash32 min_hash; // smallest tuple hash in the subtree + Hash32 child_hash; // content-addressed hash of the child node + }; + + struct InternalNode { + std::vector<ChildEntry> entries; // sorted by min_hash, len ≤ B + }; + + // 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); + + // Hex / binary + static Hash32 hex_to_bin(const std::string& hex); + static std::string bin_to_hex(const Hash32& bin); + + // 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); + + // Returns the minimum hash of the subtree rooted at node_hex. + static Hash32 subtree_min(IStorageBackend& store, const std::string& node_hex); + + // Recursive insert result: new node hash, subtree leaf count, optional split. + struct InsertResult { + std::string new_hash; + uint64_t leaf_count = 0; + bool did_split = false; + uint64_t split_leaf_count = 0; + Hash32 split_min_hash = {}; + std::string split_hash; + }; + + static InsertResult insert_into(IStorageBackend& store, + const std::string& node_hex, + const Hash32& tuple_hash); + + // Recursive remove result: new node hash (empty = node gone), leaf count. + struct RemoveResult { + std::string new_hash; + uint64_t leaf_count = 0; + }; + + static RemoveResult remove_from(IStorageBackend& store, + const std::string& node_hex, + const Hash32& tuple_hash); + + // Page collection — offset consumed as we descend. + static void page_from(IStorageBackend& store, + const std::string& node_hex, + size_t& offset, + size_t limit, + std::vector<Hash32>& out); + + // Find which child to route into (rightmost whose min_hash ≤ target). + static size_t route(const InternalNode& node, const Hash32& target); +}; + +} // namespace nt |