How to Prove One Record Belongs to a Dataset
A verifier often holds only a small commitment to a large dataset and needs to check that one record is part of it. Sending the whole dataset answers the question, but the cost grows with the dataset. A Merkle inclusion proof answers it with the record and a handful of hashes.
This article generates and verifies an inclusion proof with Sphere10 Framework. It uses StreamMappedMerkleList<T>, a persistent list that maintains a Merkle tree over its items, together with GenerateExistenceProof and MerkleMath.VerifyExistenceProof.
1. Build a merkleized list
StreamMappedMerkleList<T> stores its items in a stream and keeps the tree in the same stream, so the root is always available without rehashing the data.
const CHF algorithm = CHF.SHA2_256;
using var raw = new MemoryStream();
using var records = new StreamMappedMerkleList<string>(raw, algorithm, 256, itemSerializer: StringSerializer.UTF8, autoLoad: true);
records.AddRange(Enumerable.Range(0, 4096).Select(index => $"record-{index:D4}"));
var trustedRoot = (byte[])records.MerkleTree.Root.Clone();
var treeSize = records.MerkleTree.Size;
The constructor takes the backing stream, the hash algorithm, the cluster size of the underlying storage and the item serializer. A FileStream in place of the MemoryStream makes the list persistent.
MerkleTree.Root and MerkleTree.Size are the two values a verifier needs in advance. Size is a MerkleSize that records the leaf count and the height of the tree. The root is copied here because it changes whenever the list changes.
Each leaf is the hash of the item's serialized bytes, exactly as the list stores them. ObjectStream.GetItemBytes(index) returns those bytes, which makes it the right source for the payload that accompanies a proof.
2. How an inclusion proof works
A Merkle tree hashes every item into a leaf, then hashes pairs of nodes upward until one root remains. The root commits to every item and to its position.
To prove that one leaf belongs under a root, the prover supplies the sibling hash at each level between that leaf and the root. The verifier hashes the record, combines the result with each sibling in turn and compares the final value with the root it already holds.
In this four-leaf tree, the proof for leaf 2 is two hashes, proof[0] and proof[1]. The verifier never sees leaves 0 and 1. The proof grows with the height of the tree rather than with the number of items, so a list of 4,096 items needs twelve sibling hashes.
3. Generate the proof
GenerateExistenceProof is an extension method on any IMerkleTree. It takes the leaf index and returns the sibling hashes ordered from the leaf towards the root.
var payload = records.ObjectStream.GetItemBytes(recordIndex);
var proof = records.MerkleTree.GenerateExistenceProof(recordIndex).ToArray();The prover sends three things to the verifier: the payload, its zero-based index and the proof. For the sample's 4,096 items the proof holds twelve 32-byte hashes.
4. Verify the proof
Verification needs no access to the list. MerkleMath.VerifyExistenceProof is a static function over values the verifier already holds and values it received.
var valid = MerkleMath.VerifyExistenceProof(algorithm, trustedRoot, treeSize, recordIndex, Hashers.HashWithNullSupport(algorithm, payload), proof);| Argument | Source | Meaning |
algorithm |
Agreed in advance | The hash function used by the tree. |
trustedRoot |
Held by the verifier | The commitment to the dataset. |
treeSize |
Held by the verifier | The size of the tree the root belongs to. |
recordIndex |
Sent by the prover | The claimed position of the record. |
| Leaf hash | Computed by the verifier | The hash of the received payload. |
proof |
Sent by the prover | The sibling hashes. |
The verifier computes the leaf hash itself from the received bytes. The function derives the left and right order of every step from the tree size and the index, so the proof carries no direction flags.
A changed payload produces a different leaf hash and fails. The genuine payload presented at a different index also fails, because the index determines how the siblings are combined. The sample checks both cases.
var modifiedPayload = (byte[])payload.Clone();
modifiedPayload[^1] ^= 1;
var modifiedAccepted = MerkleMath.VerifyExistenceProof(algorithm, trustedRoot, treeSize, recordIndex, Hashers.HashWithNullSupport(algorithm, modifiedPayload), proof);
var wrongIndexAccepted = MerkleMath.VerifyExistenceProof(algorithm, trustedRoot, treeSize, 0, Hashers.HashWithNullSupport(algorithm, payload), proof);5. What the proof does and does not establish
-
The root must be trusted separately. A proof checked against a root supplied by the prover proves nothing. Obtain the root through an authenticated channel, such as a signed manifest.
-
The root and size belong together. A proof is a statement about one version of the list. After the list changes, older proofs still verify against the older root and size, and not against the new ones.
-
Both sides must agree on the encoding. The leaf is a hash of serialized bytes, so the hash algorithm and the item serializer are part of the protocol.
The Merkle domain also provides consistency, contains, update, append and delete proofs through the same IMerkleTree extensions and MerkleMath verifiers.
6. Get the package and run the sample
Add the package to a .NET 10 project.
dotnet add package Sphere10.Framework
The sample uses the .NET 10 SDK and the Sphere10.Framework package. Download the sample project and run it.
dotnet run -c ReleaseThe sample builds the list, generates the proof for one record and verifies it with the genuine bytes, with one bit changed and at the wrong index.
Records: 4096
Proof hashes: 12 (384 bytes)
Genuine record accepted: True
Modified record accepted: False
Wrong index accepted: FalseThe Sphere10 Framework overview describes the rest of the toolkit.
Author: Herman Schoenfeld
