A Merkle root is only useful while it matches the data it commits to. Maintaining a tree by hand beside a collection means hashing every item on the way in, mirroring every insert, update and removal into the tree, and never letting the two drift apart.

Sphere10 Framework's merkleized collections do that bookkeeping inside the collection. They behave as an ordinary list, dictionary or set, and expose a MerkleTree whose root always reflects the current contents. This article shows the in-memory list adapter, the stream-backed dictionary and set, how their leaves are formed, and what the root does and does not tell you.

1. Merkleize a list in memory

MerkleListAdapter<TItem> decorates an extended list. Constructed without a list, it creates its own and works as a stand-alone merkleized list. By default it hashes each item's serialized bytes with SHA2-256 and keeps the digests in a FlatMerkleTree.

var list = new MerkleListAdapter<string>(Chf);
list.AddRange(new[] { "alpha", "beta", "gamma" });
var original = list.MerkleTree.Root;

list.Update(1, "BETA");
var edited = list.MerkleTree.Root;
list.Update(1, "beta");
var restored = list.MerkleTree.Root;

edited differs from original, and restored equals it again, because the root is a function of the items and their order and of nothing else. Insert and remove are mirrored as well. In a FlatMerkleTree they move the later leaves, so they cost more than an append or an update.

Because the tree is a full IMerkleTree, a proof about one item comes straight from the list.

var hasher = new ItemDigestor<string>(Chf, ItemSerializer<string>.Default);
var proof = list.MerkleTree.GenerateExistenceProof(1).ToArray();
var proven = MerkleMath.VerifyExistenceProof(Chf, list.MerkleTree.Root, list.MerkleTree.Size, 1, hasher.Hash("beta"), proof);

The verifier computes the leaf with the same ItemDigestor<TItem> the list uses. Supply your own IItemSerializer<TItem> or IItemHasher<TItem> to the adapter when the item's default serialization is not the form you want to commit to.

2. What a merkleized collection is

Every merkleized collection implements IMerkleObject, which has one member, MerkleTree. The specialised interfaces combine it with a collection contract.

• IMerkleList<TItem> is an extended list whose ordered items are tracked by a tree.
• IMerkleDictionary<TKey, TValue> is a dictionary whose key and value pairs are tracked.
• IMerkleSet<TItem> is a set whose members are tracked.

---
config:
  sequence:
    actorMargin: 8
    width: 96
    mirrorActors: false
    messageMargin: 28
    noteMargin: 8
---
sequenceDiagram
    participant C as Caller
    participant L as Merkle list
    participant T as Merkle tree
    C->>L: Update(1, item)
    Note over L: hash the item
    L->>T: Leafs.Update(1, digest)
    Note over L: store the item
    C->>L: MerkleTree.Root
    L-->>C: new root

3. Keep the tree in the same stream as the data

The stream-mapped variants persist both the items and the tree. StreamMappedMerkleDictionary<TKey, TValue> is a stream-mapped dictionary that registers a merkle-tree index inside its own clustered storage, so reopening the stream restores the root without rehashing anything in application code.

private static StreamMappedMerkleDictionary<string, string> OpenDictionary(Stream stream)
	=> new(
		stream.AsNonClosing(),
		256,
		new StringSerializer(),
		new StringSerializer().AsNullableSerializer(),
		keyChecksummer: new ItemDigestor<string>(Chf, new StringSerializer()),
		hashAlgorithm: Chf,
		autoLoad: true
	);

The arguments are the backing stream, the cluster size, the key and value serializers, a key checksummer and the hash function. A variable-length key such as a string needs the checksummer so that lookups do not read every key, and the value serializer must accept null. The sample writes two entries, disposes the dictionary and opens it again over the same stream.

using (var reopened = OpenDictionary(stream)) {
	SampleChecks.Require(reopened.MerkleTree.Root.SequenceEqual(committed), "Reopened dictionary root differs.");
	reopened["beta"] = "3";
	SampleChecks.Require(!reopened.MerkleTree.Root.SequenceEqual(committed), "Changed value kept the old root.");
	Console.WriteLine($"Dictionary: {reopened.Count} entries, root kept across reopen, changed by one value");
}

A dictionary leaf commits to both halves of an entry. It is the join of the digest of the stored key bytes and the digest of the stored value bytes, which the sample confirms for the first slot.

var leaf = Hashers.JoinHash(Chf, Hashers.Hash(Chf, dictionary.ReadKeyBytes(0)), Hashers.Hash(Chf, dictionary.ReadValueBytes(0)));

%%{init: {"flowchart": {"nodeSpacing": 20, "rankSpacing": 28}, "themeVariables": {"fontSize": "16px"}}}%%
flowchart TB
    L["Dictionary leaf<br/>JoinHash"] --> K["Hash of<br/>key bytes"]
    L --> V["Hash of<br/>value bytes"]

StreamMappedMerkleHashSet<TItem> gives a set the same treatment. It is stored as a merkle dictionary keyed by item digests, so adding a member that is already present changes neither the set nor the root.

using var set = new StreamMappedMerkleHashSet<string>(stream, 256, ItemSerializer<string>.Default, Chf);
if (set.RequiresLoad)
	set.Load();
set.Add("alpha");
var one = set.MerkleTree.Root;
set.Add("beta");
var two = set.MerkleTree.Root;
var duplicateAdded = set.Add("alpha");

StreamMappedMerkleList<TItem> and StreamMappedMerkleRecyclableList<TItem> complete the family for positional data.

4. What the root does and does not cover

5. Get the package and run the sample

The collections are part of the core Sphere10.Framework package.

dotnet new console --framework net10.0 --name ArticleSample
cd ArticleSample
dotnet add package Sphere10.Framework

The complete MIT-licensed sample contains the program shown in this article. Extract the download over the generated project and run it.

dotnet run -c Release

List: 3 items, root follows edits, item 1 proven with 2 hashes
Dictionary: 2 entries, root kept across reopen, changed by one value
Set: 2 members, duplicate add left the root unchanged

The Merkle Trees guide lists every merkleized collection, and the stream-mapped merkle tests show them under load.

The Sphere10 Framework overview describes the rest of the toolkit.

Author: Herman Schoenfeld