This package implements a Merkle Patricia Tree (MPT) stored on disk.
A Merkle Patricia Tree (MPT) is a map that stores key-value pairs, where each key and value is an opaque 256-bit value (typically a SHA256 hash). Analogous to a transparent log, an MPT can cryptographically prove that a given key-value pair exists (or that a key does not exist) in a given tree root. By recording the sequence of tree roots in a transparent log, a server can publish an record of the history of a key-value database, in such a way that auditors can check that the database was correct at all times, and clients can be sure the responses they received came from the recorded database history.
Certificate Transparency (CT) records a transparent log of all issued HTTPS certificates, but it is expensive for a domain owner to read the entire log looking for certificates for one or a few domains. It would be useful to provide a server mapping from domain to certificate lists, backed by an auditable MPT to verify (after the fact) that the server has been behaving correctly.
CT logs contain about 2 billion entries and are growing by about 75 entries/second. Let's Encrypt currently issues 90-day certificates but plans to start issuing short-lived, six-day certificates, which they estimate could result in 20X as many certificates. The number of domains does not change, so the overall MPT size would stay at around 2 billion entries, but the update rate would grow to perhaps 75×20 = 1,500 updates/second. It would be good to be able to handle 75×50 = 3,750 updates/second to provide extra headroom. We'd like to handle this load comfortably on one reasonably configured server.
Let's assume we have a single server with a decent amount of memory and a fast disk. For example, a Google Cloud “m4-megamem-56” server with 56 vCPUs, 744 GiB of memory costs $3,230/month (before sustained use or negotiated discounts). Connecting two 1 TiB “balanced hyperdisks” each with 20,000 IOPS and 1200 MiB/s throughput adds $418/month. (Pricing calculator) For people running servers in their own data centers or behind their own couches, a Thelio Astra with 512 GB of memory and 2 4TB NVMe SSDs can be had for $5,462.
We will aim to be able to store, update, and serve an MPT of 2 billion entries with 4,000 updates/second easily on those servers.
If we are to serve 4,000 updates/second, each update must cost less than 250µs. And if our budget is 20,000 I/O operations/second, each update must cost less than 5 I/O operations. A tree of two billion entries has height at least 30: we don't have enough I/O budget even to read nodes from disk during updates, not to mention lookups. The inevitable conclusion is that we must keep the entire tree in memory, streaming updates to disk in batches. So we will do exactly that.
A hybrid approach is also possible, where each lookup or set requires O(1) disk I/O operations in exchange for not keeping leaf data in memory. This reduces the memory overhead from 112 bytes per entry to 48 bytes per entry. After describing the fully in-memory version, we describe the hybrid version.
An MPT starts with the concept of a binary tree of depth 256, where the key-value pairs are stored in the leaves at depth 256, and a lookup proceeds by walking left or right according to each of the 256 key bits. The root node represents the empty key prefix, its children represent key bit prefixes 0 and 1, their children represent key bit prefixes 00, 01, 10, 11, and so on: at depth d, the nodes represent key prefixes of d bits. The original Key Transparency system at Google used exactly this data structure, a Merkle-hashed binary radix tree. Since then, the transparency community has realized that it works better to apply Merkle hashing to a Patricia tree, which adds three optimizations to the binary radix tree.
First, the tree is “path-compressed,” by removing inner nodes with a single child: a node that would have pointed at a single-child node is replaced by its child, recursively. Every node is therefore either a leaf or an inner node with two children. The path compression ensures that there are exactly N inner nodes for a tree with N+1 leaf nodes.
Second, unlike in a normal binary tree, an inner node stores only the bit position that determines whether a lookup should proceed to the left or right child. A lookup walks inner nodes down to some leaf, checking one bit at each step. Only upon reaching the leaf does it do a full key comparison. If it takes O(K) time to compare two keys, a normal binary tree would take O(K log N) time for a walk; this optimization cuts the time to O(K + log N). Furthermore, inner nodes need not store associated keys, cutting the number of stored keys by a factor of two.
Third, nodes are “joined” by merging one inner node and one leaf node into a single stored node. (After joining N inner nodes to N leaf nodes, that leaves one “leaf-only” node not paired to an inner node, but the node is still stored using the joined representation.) Whether a stored node represents an inner node or leaf node depends on how it is reached while walking the tree. This trick is not essential, but it simplifies storage management to have only one type of stored node.
The path-compression optimization implies that an inner node for key prefix p exists if and only if the tree contains at least one key with prefix _p_0 and at least one key with prefix _p_1. That is, the specific inner nodes that exist in a Patricia depend only on which keys are present in the tree, not on their insertion order. This implies that we can batch or otherwise reorder insertions of distinct keys without affecting the final tree structure.
For more about standard Patricia trees, see TODO REFERENCE.
Cominbing the Merkle and Patricia pieces, a Merkle Patricia Tree provides the following operations:
- Set(key, val): add a new key-value pair to the map.
- Snap(version): set the tree's version and return the tree root's key prefix and hash.
- Prove(key): return a proof of the result of looking up a given key in the current snapshot. A separate library function
Verifyverifies a proof and returns the lookup result (whether the key was found and, if so, its associated value). - Sync(): flush recent changes to disk.
The recursive hash of an MPT is defined as follows:
- The hash of a leaf node is the hash of its key and value.
- The hash of an inner node is the hash of its bit position and its left and right children's hashes.
A proof confirming that a key-value pair exists in an MPT with a given recursive hash is the value followed by the bit position and sibling hash for every inner node along the path back to the root. The key-value pair can be hashed to obtain the hash of the leaf node, and then the running hash can be hashed with the parent's bit position and sibling hash to obtain the hash of the next inner node toward the root. (Whether the running hash is the left or right child is determined by checking the specified bit of the key.) Recomputing the root's actual hash proves the lookup.
A proof denying that a target key exists in an MPT is almost identical. It consists of the “other key” whose leaf would be found by looking up the key in the tree, followed by the proof that that other key is in the tree. The verification checks that the other key's proof is valid and also that the target key and other key agree at every relevant bit position.
An in-memory MPT implementation is in mem.go. It was useful to write and debug that version before adding the complexity of attempting to store the tree on disk. If future algorithmic bugs are found, it may still be helpful to debug them in that version first. It may also be useful read and understand that implementation before proceeding to the disk implementation.
Any MPT implementation must define the exact encodings it uses. The encodings used by this package are as follows.
An empty tree is a special case that is otherwise independent of the tree hash definition. In this implementation, the hash of an empty tree is SHA256(e), the hash of the empty string (e3b0c442...7852b855).
The hash of a leaf node is the hash of the concatenation of the key and value (both fixed-size 32-byte sequences).
The hash of an inner node at bit position b with left and right child hashes left and right is SHA256(left || right || b) where left and right are 32-byte values and b is a one-byte value.
Proofs are variable length strings beginning with the 8-byte sequence mptproof.
In Go the verifier's signature is:
func Verify(snap Snapshot, key Key, proof Proof) (val Val, ok bool, err error)
The verifier is given a tree hash (called a snapshot), a specific key, and a proof, and it returns three results: (1) the value associated with the key, if the proof proved the existence of the key in the tree, (2) whether the proved result confirms or denies the existence of the key, and (3) an error if the proof was invalid or did not match the tree hash.
A proof of the empty tree is mptproof followed by a 0x00 byte.
It only applies when the tree hash is the empty tree hash,
and it disproves the existence of all possible keys.
A proof confirming the existence of a key starts with mptproof followed by a 0x01 byte
and then a 32-byte value v.
The hash of the key's leaf node can be recomputed as h = SHA256(key || v).
If the tree is a single node, that is the entire proof: the verifier must check that
h = snap.
If the tree contains more than one node, the proof continues with
one or more descriptions of sibling nodes along the path back to the tree root.
Each sibling node is encoded as 33 bytes: a one-byte bit position b
followed by a 32-byte sibling hash sib.
The verifier must check whether the b'th bit of key is 0 or 1
and then update the running tree hash accordingly:
- h = SHA256(h || sib || b) if bit b of key is 0, or
- h = SHA256(sib || h || b) if bit b of key is 1.
Then, as before, the recomputed tree hash h can be compared against the actual tree hash.
A proof denying the existence of a key starts with mptproof followed by a 0x02 byte
and then a 32-byte key k and 32-byte value v,
describing a leaf node with hash h = SHA256(k || v).
If the tree is a single node, that is the entire proof: the verifier
must check that h = snap and that k ≠ key.
Otherwise the proof format contains one or more siblings
encoded exactly as in the the existence proofs.
Verification also proceeds as in the existence proofs,
checking along the way that k and key agree on every bit b.
(Otherwise the proof would not describe the path taken
to walk through the tree in search of key.)
At the end, the verifier must check that h = snap and that k ≠ key.
The worst case length of an existence proof is 8+1+32+33*256 = 8489 bytes, although random keys will never produce a path of length 256.
The worst case length of a non-existence proof is 8+1+64+33*255 = 8488 bytes. A non-existence proof can only have 255 siblings because otherwise the proof would describe a key k that agrees with key at all 256 bit positions, but then k ≠ key could not be true. Again, random keys will never produce a path length of 256.
Note: This encoding is considerably more compact than some others. For example, the Rust akd crate's MembershipProof is:
pub struct MembershipProof {
pub label: NodeLabel,
pub hash_val: AzksValue,
pub sibling_proofs: Vec<SiblingProof>,
}
NodeLabel is a key plus a bit length, 32+4 = 36 bytes.
AzksValue is 32 bytes.
SiblingProof is:
pub struct SiblingProof {
pub label: NodeLabel,
pub siblings: [AzksElement; 1],
pub direction: Direction,
}
AzksElement is a NodeLabel and AzksValue, 64 bytes.
Direction is a single byte.
So SiblingProof is 36+64+1 = 101 bytes, and the overall worst case MembershipProof, if there are 256 siblings, is 36+32+101*256 = 25,924 bytes. The largest contributor to the difference is that the siblings include two node labels when zero node labels suffice. The result is a factor of three in the size of the proofs generated (and sent over the network).
There are two potentially important computations MPT hashes that can be done without creating an explicit tree representation.
The first computation is a whole-tree hash, meaning to calculate a tree hash from a sorted list of key, value pairs (sorted in key order). Obviously the tree could be constructed and then hashed, but the hash can be calculated more directly as follows.
The algorithm maintains a stack s, and we will denote the top element by s[−1], the one below it by s[−2], and the one below that by s[−3]. The algorithm is:
func treehash(list) -> (hash)
s = {}
for each k, v in list
s = reduce(push(s, leaf(k, v)))
return stackhash(s)
func leaf(k, v) -> (node)
return {key: k, bits: 256, hash: SHA256(k || v)}
func reduce(s) -> (stack)
while len(s) >= 3 and overlap(s[-3], s[-2]) > overlap(s[-2], s[-1])
s = push(s[:-3], merge(s[-3], s[-2]), s[-1])
return s
func stackhash(s) -> (hash)
if len(s) == 0
return SHA256()
while len(s) >= 2
s = push(s[:-2], merge(s[-2], s[-1]))
return s[-1].hash
func overlap(x, y) -> (bool)
return number of bits in shared prefix of x and y (at most min(x.bits, y.bits))
func merge(x, y) -> (node)
b = overlap(x, y)
return {key: x.key, bits: b, hash: SHA256(x.hash || y.hash || b)}
Treehash maintains a stack corresponding to completed subtrees. Each step pushes a new leaf node onto the stack and then reduces the stack by the following observation. When the stack has top values x, y, z, and x and y have more bits in common (join together deeper in the tree) than y and z, then x and y can be merged into a single subtree, since z and all keys that follow will only be joined to it higher up in the tree. Once the entire key-value list has been pushed on to the stack and reduced, all that remains is for stackhash to merge the final fringe up the right side into a complete tree.
The run time of this algorithm is N pushes of leaves, N calls to reduce, and N_−1 total merges. Each call to reduce ends in a failed overlap comparison, and the number of successful overlap comparisons is less than N (since there are only N_−1 merges), so there are at most 2_N overlap comparisons, or 4_N overlap calls. That's O(N K) time, where K is again the time for a key comparison.
The second computation is a predicted tree hash, meaning to calculate a tree hash that would result from starting with an existing tree and inserting a sorted list of key, value pairs that may replace existing nodes or add new ones. The trick is that we want to compute this hash without editing the existing tree.
If every node in the tree stored the key corresponding to that node, then we could use the following algorithm to produce a sorted list of nodes corresponding to subtrees of the existing tree or new leaves, and then we could apply a variant of treehash to that list of nodes to compute the overall tree hash.
func updatehash(tree, list) -> (hash)
s, list = update({}, tree, list)
for k, v in list
s = reduce(push(s, leaf(k, v)))
return stackhash(s)
func update(s, node, list) -> (stack, list)
// push modifications before node
while len(list) > 0 or list[0].key < node.key comparing only node.bits bits
k, v = list[0]
list = list[1:]
s = reduce(push(s, leaf(k, v)))
// push entire subtree if no modifications inside it
if len(list) == 0 or node.key < list[0].key comparing only node.bits bits
return reduce(push(s, node)), list
// replace leaf if node is a leaf
if node.bits == 256
k, v = list[0]
list = list[1:]
return reduce(push(s, leaf(k, v))), list
// apply modifications within subtree
s, list = update(s, node.left, list)
s, list = update(s, node.right, list)
return s, list
The only problem is that the second Patricia optimization removed the .key field in the tree nodes. The solution is that the third Patricia optimization added it back implicitly. Each new combined node is constructed during the insertion of a key k to hold the leaf k, v_ as well as being the new inner node representing a previously unexamined bit b that separates k from an existing subtree. Both k and the subtree have the same key prefix of b bits, so the inner node's key is simply k truncated to b bits. So the key stored in the combined node turns out to describe both the inner node and the leaf. We still don't want to use it as an inner node key during lookups, as that would turn our O(K + log N) back into O(K log N), where K is a key comparison. But it's there, and we can use it while computing the predicted tree hash.
Let's say there are N items in the list and T items in the existing tree and that the tree has height O(log T). Then as a worst case we can estimate that each item requires enumerating O(log T) subtree nodes to make room for the insertion of the new leaf, a total of O(N log T) nodes pushed onto the stack, which will require O(N K log T) time for the comparisons in the reduction to a single tree hash. It also required one comparison per update call, and there were asymptotically the same number of update calls as nodes pushed, so the total time is still O(N K log T).
There may be some way to use the Patricia property to avoid the repeated comparisons in the algorithm described above, but it would not change the stack reduction time, so the overall asymptotic runtime would remain.
Although the working tree is stored in memory, we of course want to recover from crashes by persisting the tree to a disk file as well. The disk file consists of a memory image of a tree followed by a sequence of patches of the form “at offset O, write these N bytes”. Each update requires only a single disk write to append its patches to the file. (Multiple updates can also be batched into a single write.)
There is only one problem with this representation: it grows without bound, and faster than the tree. A write of an existing key-value pair requires no additional memory at all, but it requires 30 or so patches to existing nodes, to update the hashes of the inner nodes along the path back to the root. A write of a new key-value pair requires only one new allocated node, but it too requires the same 30 or so patches. There must be some kind of compaction.
The simplest way to compact one file is to write out a second disk file. After all, the in-memory copy has all the patches applied already. Conceptually, we can stop updates, write the current tree memory to a new file, delete the old file, and then resume updates, now writing patches to the new file. It is worth introducing two complications. First, we can reuse the old file as the output for the next compaction, alternating between a pair of files instead of continually deleting and recreating files. Second, we can let updates proceed concurrently with compaction, so that updates aren't blocked waiting to write a few hundred gigabytes to disk.
The memory format of the tree must be suitable for writing to disk and then reading back into a different memory location, so it cannot contain actual Go pointers. Instead, the memory format is one very large byte array that is interpreted as higher-level data structures “on demand,” when accessing or modifying it. Each actual update happens by writing to the memory as bytes and also logging the mutation to a patch that will be written to disk.
The tree memory starts with a header with the form:
version [ 8 bytes]
dirty [ 1 byte]
pad [ 1 byte]
root [ 6 bytes]
hash [32 bytes]
nodes [ 8 bytes]
All numbers are stored in big-endian order for legibility when reading hex dumps.
- “version” is a number for clients to use to match the tree contents to a position in the underlying transparent log.
- “root” is a pointer to the tree's root node, represented as a 48-bit byte offset within the tree memory.
- “nodes” field counts the number of nodes (leaves) stored in the tree.
- “hash” is the Merkle hash of the tree root. When “dirty” is set, the hash is stale and needs to be recomputed.
- “pad” pads “root” to a 16-bit boundary and “hash” and “nodes” to a 64-bit boundary.
The header is immediately followed by a sequence of Patricia nodes, each with the form:
key [32 bytes]
val [32 bytes]
bit [ 1 byte]
dirty [ 1 byte]
pad [ 2 bytes]
left [ 6 bytes]
right [ 6 bytes]
ihash [32 bytes]
Remember that each Patricia node represents both one leaf node and one inner node.
- “key” and “val” are the key and value for the leaf node.
- “left” and “right” are pointers to the inner node's left and right children; “bit” is the bit position to use to decide between them during a lookup. Since keys are 32 bytes, bit positions 0..255 fit in a single byte. The leaf-only node is an exception: it needs a bit position set to -1, but it can be identified by having “left” and “right” set to 0 (nil pointer) and treated as a special case when reading “bit”.
- “ihash” is the Merkle hash of the inner node. When “dirty” is set, the hash is stale and needs to be recomputed. The Merkle hash of the leaf node is not stored explicitly. It is recomputed from “key” and “val” whenever it is needed.
After setting the value associated with a given key, the “ihash” values in all nodes back to the root need to be recomputed. If we are writing N new values between taking snapshots, we would end up recomputing the root hash _N_−1 times unnecessarily, recomputing the root's two children's hashes N/2−1 times unnecessarily, and so on. Since everything else is in memory, batched, and cheap, these SHA256 computations end up being the serving bottleneck. To avoid the unnecessary hashes, we don't recompute any hash during a write of a new value. Instead, we set the “dirty” field on all nodes back to the root. The snapshot operation restores each hash by recomputing it from its children, restoring those hashes first as needed. In effect, it rewalks the entire modified area of the tree, computing all the new hashes then. Snapshots are still amortized O(1) but not an actual O(1). If the snapshot operations caused problematic latency hiccups, this lazy recomputation could be abandoned.
Notice that a Patricia node takes 112 bytes, so a 2-billion node tree requires about 224 GB of memory, well within the 512 GB we allotted ourselves on our “reasonably configured server”. The actual memory for the tree is obtained directly using the operating system, not from the Go heap. Using mmap(2), we can reserve a very large amount of space but then only map the memory we need as the tree grows. This allows extending the tree without having to move it. It also has the side benefit of not skewing the Go garbage collector's pacing with one extremely large allocation.
The file format allows grouping memory updates into atomic units, so that partially applied updates are never observed when loading a tree from disk.
A file consists of the magic string "mpt tree\n\x00\x00\x00\x00\x00\x00\x00"
followed by a sequence of variable-length frames.
Each frame has the form:
treeID [16 bytes]
treeSeq [ 8 bytes]
N [ 8 bytes]
data [ N bytes]
checksum [32 bytes]
The “treeID” is randomly chosen when a tree is first created, and the “treeSeq” is a sequence number incremented each time a new tree file is written. Both ensure that when files are reused (either for a new tree or a new version of the same tree), old frames are not misinterpreted as new ones.
The “checksum” is a SHA256 checksum of the preceding fields. Verifying the checksum detects corruption but also provides atomicity of frame writes: either the whole frame is written to disk and the checksum matches, or none of it is used.
The file starts with one very large frame containing a snapshot of the tree memory. As we will see, concurrent compaction means that this memory snapshot may not itself be a valid tree: the patches in the rest of the file must be applied not just to obtain the latest tree, but also to obtain a valid tree.
The second and subsequent frames in the file each hold a patch block, which holds one or more mutations of the form:
offset [varint]
N [varint]
data [N bytes]
That mutation says to write data of length N at
offset in the tree memory.
There is no guarantee that a file ends after a valid patch block frame. If a frame was only partially written before a process or system crash, we still want to read the tree before that point. We do this by reading as many valid (checksum-matching) frames as possible from the file and stopping at EOF or when we reach a frame that is truncated or does not have a valid checksum.
When the current disk file holding a tree has grown too large, compaction writes and then switches to a new smaller file, at which point the old one can be abandoned. In practice, the implementation reuses the old one for the next compaction.
Logically, compaction is shortening the old file by writing the patches directly to the tree memory. However, it is not reading the old file: the tree can be written directly from memory instead of consulting the old file. So technically compaction may be a misnomer: the old file not being compacted so much as it is being obsoleted.
One approach would be to pause all tree updates, write the tree to the new file, and then continue updates, writing patches to the new file. If the tree is 224 GB, then even if we can write at a relatively fast 10 GB/s, that would be a 22-second pause. Instead, we can allow tree updates to proceed concurrently with compaction.
The concurrent compaction algorithm works as follows:
- Record the current tree memory size M.
- Arrange to write future patch frames to both the current tree file and the next tree file. In the next tree, the patches start at the offset where a tree of size M would end.
- Each time a new megabyte (or other chosen chunk size) of patches is written, write the next megabyte of tree memory to the next tree file as well.
- Once all the tree memory has been written to the next file, sync it to disk and write its incremented tree sequence number so that a future open will choose that file.
- Now the old next file has become the new current one, and the old current one will be reused for as next for the next compaction.
Note that the compaction is concurrent but not parallel: the compaction writes are interleaved with non-compaction writes, not run in a separate goroutine.
Suppose we start a compaction when the in-memory tree is M bytes and the current tree file is 2M bytes long. Compaction will finish when another M bytes of patches have been written, meaning the current file will be 3M bytes when it is retired, and the next tree file will be 2M bytes long. After installing next as the new current, it will be time for a new compaction. The result is continuous, just-in-time compaction: each one finishes exactly as the next needs to begin.
For the actual implementation, it seemed safer to write two megabytes of tree for each megabyte of patches, rather than dance on that knife's edge. If writing a megabyte of patches to two different trees (current and next) allows writing two megabytes of tree memory as well, then the implementation writes the same amount of tree bytes and patch bytes to disk when compaction is running. At worst, compaction is always running, so that the number of tree bytes written equals the number of patch bytes written.
If each memory change is written to two patch files, and those writes justify writing the same amount of tree bytes, then the write amplification factor is no worse than 4. This constant factor is much better than the O(log N) amplification in log-structured merge trees. The improvement is possible because we keep all the data in memory at all times.
On my circa-2023 home server with 128 GB of RAM and an NVMe disk using LVM encryption, storing 834 million hashes takes about 250 minutes, or about 55,000 Set operations per second. This is with constant disk compaction, and I suspect something in my kernel stack of slowing disk I/O.
A “lazy hash” optimization that delays recomputing all inner node hashes is delayed until the Sync operation can avoid spending time computing hashes that will be overwritten by a subsequent Set, but it dramatically increases the latency of Sync. More important than not computing the hashes is not writing them to disk, especially for the somewhat special case of writing all new entries when populating a new tree. In that case, the lazy hash's lower disk usage also avoids any compaction: only new data is being written, so the disk file never reaches twice the memory size. In that case, the 834 million hashes can be written in 45 minutes, followed by a 7 minute sync, or about 260,000 Set operations second.
A limited lazy hash that is lazy only up to a fixed number of Set operations may be the best of both worlds.
Prove operations run in microseconds.
Snap is effectively free.
On crash and restart, the persistent disk implementation guarantees to have a state equivalent to some prefix of the operations that had been executed prior to the crash. That is, some recent operations may have been lost, but if operation K is observed, then all operations prior to K will also be observed.
If the client calls Snap with a version number at regular intervals, then after a crash, if the tree loads with version V, it means that all of the Set calls before Snap(V) has been retained, and some of the Set calls between Snap(V) and Snap(V+1) may also have been retained. It suffices to replay all the Set operations between Snap(V) and Snap(V+1) and then Snap(V+1) to get a consistent tree.
The approach described so far is the original in-memory approach. It is tagged as mpt v0.1.0.
This section describes a hybrid approach implemented in later versions. The hybrid approach trades a constant number of disk I/O per Set or Prove operation for reduced memory requirements. In the hybrid approach, the leaf nodes (meaning the key and value fields) are all stored in a “leaf file” not stored in memory. Writes to the leaf file are still recorded in patch blocks, so that after recovery the leaf file is always at least as up to date as the main tree memory image. However, writes to the leaf file also happen immediately, so after recovery, the leaf file may also contain writes beyond those reflected in the main tree memory image. Having a leaf file that is “too new” cannot affect the structure of the overall tree, since keys are never changed after a node is allocated. However, the leaf file being too new can mean that values that are “too new” are recorded for leaf nodes, so the client must recover by replaying all the Set operations that may have happened after the point where the memory image was recovered. Once those are replayed, the memory image and the leaf file will be in sync.
To support the recovery operation, there is a new method Tree.Version:
// Version returns the version number of the tree's last complete snapshot.
// All Set calls made prior to Snap(version) are guaranteed to be
// recorded in the tree. However, if exact is false, then the tree may
// include the effect of Set calls made after that snapshot.
// In that case, to bring the tree into a consistent state, the client is
// expected to replay all Set calls up to the next version.
Version() (version int64, exact bool)
In this new approach, calling Prove requires two disk I/Os: one to read the leaf key and value at the end of the lookup, and one to read that node's sibling for inclusion in the proof. Calling set requires three disk I/Os: the same two reads needed by Prove as well as one write to update or create a leaf.
In exchange for these two or three disk I/Os per operation, the memory requirements are reduced from 112 bytes per record to 48 bytes per record.