How to Prove Appends, Updates and Deletes in a Merkle Tree

An inclusion proof shows that one record belongs to a dataset with a known Merkle root. It says nothing about how the dataset got from one root to the next. A verifier that follows a changing dataset by its root alone needs a different kind of proof, one that shows the new root is the old root plus a stated change and nothing else.

Sphere10 Framework's merkle trees generate and verify these proofs for appended, updated and deleted leaves, and for consistency between two sizes of the same tree. This article covers what each proof contains, when it must be generated, and which MerkleMath method checks it.

A merkle tree whose root changes as leaves are appended and replaced.
A merkle tree whose root changes as leaves are appended and replaced.
💡 In short. Generate and verify Merkle proofs that a tree changed only by a stated append, update or delete, and consistency proofs between two sizes, using the IMerkleTree proof generators and MerkleMath verifiers.

1. Build a tree

FlatMerkleTree is the general-purpose dynamic tree. Its Leafs list holds leaf digests, and the tree recomputes the affected nodes whenever that list changes. The sample hashes short strings into leaves. 


var tree = new FlatMerkleTree(Chf);
tree.Leafs.AddRange(Enumerable.Range(0, 5).Select(index => Leaf($"record-{index}")));



private static byte[] Leaf(string text) => Hashers.Hash(Chf, Encoding.UTF8.GetBytes(text));

Chf is CHF.SHA2_256. The same hash function must be passed to every verifier.

2. Prove an append

Capture the old root and size, generate the proof, and only then add the leaves. 


var oldRoot = tree.Root;
var oldSize = tree.Size;
var appendProof = tree.GenerateAppendProof().ToArray();
var appended = new[] { Leaf("record-5"), Leaf("record-6") };
tree.Leafs.AddRange(appended);
var appendAccepted = MerkleMath.VerifyAppendProof(Chf, oldRoot, tree.Root, oldSize, appended, appendProof);

VerifyAppendProof takes the old root, the new root, the old MerkleSize, the appended leaf digests and the proof. Changing any one of the appended leaves makes it return false, which the sample checks with a substituted leaf.

3. The four change proofs

Every tree implements IMerkleTree, which reports Root, Size and the hash at any node. The proof generators are extension methods on that interface, and the verifiers are static methods on MerkleMath. A proof is always a sequence of node hashes, IEnumerable<byte[]>.

Proof Shows Generate it
Append New leaves were added to the end Before adding
Update Chosen leaves were replaced Before replacing
Delete Leaves were removed from the end Before removing
Consistency An older tree is a prefix of this one After growing

The timing matters because three of the proofs are built from the old tree. An append proof, for example, is the list of the old tree's sub-roots, which are the roots of the perfect subtrees its leaves divide into. A tree of five leaves has two of them.

The verifier aggregates the sub-roots to confirm they produce the old root, then adds the new leaves to them one at a time and compares the result with the new root. It never sees the existing leaves.

Diagram source 
%%{init: {"flowchart": {"nodeSpacing": 20, "rankSpacing": 28}, "themeVariables": {"fontSize": "16px"}}}%%
flowchart TB
    R["Root<br/>5 leaves"] --> A["Sub-root<br/>leaves 0 to 3"]
    R --> B["Sub-root<br/>leaf 4"]

4. Prove an update

An update proof is generated for specific leaf positions, again before the change. It carries the old values of those leaves together with the hashes needed to rebuild the root around them. 


oldRoot = tree.Root;
var updateProof = tree.GenerateUpdateProof(2, 1).ToArray();
var replacement = Leaf("record-2 (edited)");
tree.Leafs.Update(2, replacement);
var updateAccepted = MerkleMath.VerifyUpdateProof(Chf, oldRoot, tree.Size, tree.Root, 2, new[] { replacement }, updateProof);

GenerateUpdateProof(2, 1) covers one leaf starting at index 2, and an overload accepts any set of indices. The verifier first confirms that the proof commits to the old root, then substitutes the new leaves, recomputes the path to the root and compares it with the new root. The exchange between the party that holds the tree and the party that holds only roots looks like this.

Diagram source 
---
config:
  sequence:
    actorMargin: 8
    width: 96
    mirrorActors: false
    messageMargin: 28
    noteMargin: 8
---
sequenceDiagram
    participant P as Tree holder
    participant V as Verifier
    Note over V: knows old root
    Note over P: GenerateUpdateProof
    Note over P: Leafs.Update
    P->>V: new root, new leaf, proof
    Note over V: VerifyUpdateProof

5. Prove a delete and check consistency

A delete proof covers leaves removed from the end of the tree. It is generated before the removal, and its verifier takes the leaf count before the delete and the number of leaves removed. 


oldRoot = tree.Root;
var deleteProof = tree.GenerateDeleteProof(2).ToArray();
tree.Leafs.RemoveRange(5, 2);
var deleteAccepted = MerkleMath.VerifyDeleteProof(Chf, oldRoot, 7, tree.Root, 2, deleteProof);

A consistency proof is the one proof generated from the newer tree. It shows that the tree at an earlier leaf count is a prefix of the current one, without listing the leaves added since. 


var consistencyProof = tree.GenerateConsistencyProof(5).ToArray();
var consistent = MerkleMath.VerifyConsistencyProof(Chf, oldRoot, 5, tree.Root, 7, consistencyProof);

In the sample this check runs straight after the append, while oldRoot still holds the five-leaf root. A delete is a consistency proof read in the opposite direction, which is why VerifyDeleteProof takes the same kind of arguments.

6. Choose a tree implementation

The proof methods work on any IMerkleTree, so the choice of tree is about storage and mutation.

  • FlatMerkleTree keeps every perfect node in one buffer. Reads are constant time, and an append or update recomputes only the affected ancestors.
  • SimpleMerkleTree keeps every level in lists and recomputes all of them after a change. It suits small trees.
  • LongMerkleTree keeps only the sub-root hashes. It accepts appends and nothing else, and it cannot read nodes inside a sub-root, so proofs that need interior nodes are not available from it.
ℹ️ A proof binds a change to two roots. It does not say who made the change or whether the roots themselves are trustworthy, so the verifier must obtain the old root from a source it already trusts, such as a signed checkpoint.

7. Get the package and run the sample

The merkle types are part of the core Sphere10.Framework package, in the Sphere10.Framework namespace. 


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

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

Each line reports the size of one proof and the verifier's answer, including the two forged cases. 


Append 5 -> 7 leaves: 2 proof hashes, accepted True, forged leaf accepted False
Consistency 5 -> 7 leaves: 4 proof hashes, accepted True
Update leaf 2: 4 proof hashes, accepted True, forged leaf accepted False
Delete 7 -> 5 leaves: 4 proof hashes, accepted True

The Merkle Trees guide lists every tree type and proof method, and the dynamic merkle-tree paper describes the algorithms behind them.

sample.zip
Download the complete worked example and build instructions (ZIP).

The Sphere10 Framework overview describes the rest of the toolkit.

📚 Continue the series

Author: Herman Schoenfeld