1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
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
|
