Table of Contents

MerkleTree Class

Definition

Namespace
Bodu.Security.Cryptography
Assembly
Bodu.Security.Cryptography.dll
Package
Bodu.Security.Cryptography 1.2.0
Source
MerkleTree.BlockArithmetic.cs

The block arithmetic every consumer of block mode shares - the number of blocks a byte length divides into, and the offset and length of each one.

public sealed class MerkleTree
Inheritance
MerkleTree
Inherited Members
Extension Methods

Examples

using System.Security.Cryptography;
using Bodu.Security.Cryptography;

var tree = new MerkleTree(SHA256.Create);

ReadOnlyMemory<byte>[] entries = [ new byte[0], new byte[] { 0x00 }, new byte[] { 0x10 } ];
byte[] root = tree.ComputeRoot(entries);
byte[][] path = tree.AuthenticationPath(entries, leafIndex: 2);

// Large inputs: the same tree, leaves hashed on every core.
var parallel = new MerkleTree(SHA256.Create, maxDegreeOfParallelism: -1);
using var stream = File.OpenRead("archive.bin");
byte[] sameRoot = parallel.ComputeRootOfBlocks(stream, blockSize: 1 << 20);

Remarks

A byte stream becomes an ordered sequence of tree entries by cutting it into fixed-size blocks. Every block but the last is blockSize bytes; the last is short whenever the length is not a whole multiple, and is hashed at its actual length rather than padded - padding would make a short final block indistinguishable from a full block of the same bytes followed by zeros.

A zero-length input has zero blocks, not one empty block. Its root is therefore the empty tree's - the hash of zero bytes - rather than the hash of one empty leaf.

These three functions are trivial and are nonetheless published, because a consumer that computes the final block's length incorrectly does not fail loudly - it produces a different, wrong root. A MerkleBlockComputation answers the same questions for its own input and additionally rejects a block that does not exist.

Constructors

MerkleTree(Func<HashAlgorithm>, int, int)

Initializes a new instance of the MerkleTree class using the specified hash algorithm factory delegate, fan-out and degree of parallelism.

public MerkleTree(Func<HashAlgorithm> algorithmFactory, int fanOut = 2, int maxDegreeOfParallelism = 1)

Parameters

algorithmFactory Func<HashAlgorithm>

A delegate supplying the HashAlgorithm used for every leaf, node and root. Must not be null and must return a fresh instance on each call.

fanOut int

The number of children hashed into each parent. Two, the default, is RFC 6962's tree; a larger value is the package's own non-RFC mode, on which the proof members are unavailable.

maxDegreeOfParallelism int

The greatest number of leaves to hash concurrently: one, the default, hashes on the calling thread; -1 uses the processor count; any larger count bounds the workers.

Remarks

The factory is invoked once here to establish HashLength, so a factory that cannot produce an algorithm fails at construction rather than at the first computation.

Exceptions

ArgumentNullException

algorithmFactory is null.

ArgumentException

The factory returned null, or an algorithm whose digest length is not positive.

ArgumentOutOfRangeException

fanOut is less than two, or maxDegreeOfParallelism is zero or below -1.

Properties

FanOut

Gets the number of children hashed into each parent.

public int FanOut { get; }

Property Value

int

Two for RFC 6962's tree; a larger value for the package's own non-RFC mode.

HashLength

Gets the length, in bytes, of every leaf hash, node hash and root this instance produces.

public int HashLength { get; }

Property Value

int

The configured algorithm's digest length in bytes - 32 for SHA-256, 64 for SHA-512.

IsBinary

Gets a value indicating whether this instance builds RFC 6962's binary tree, on which the proof members are available.

public bool IsBinary { get; }

Property Value

bool

MaxDegreeOfParallelism

Gets the greatest number of leaves hashed concurrently.

public int MaxDegreeOfParallelism { get; }

Property Value

int

One when leaves are hashed on the calling thread; -1 for the processor count; otherwise the bound.

Methods

AuthenticationPath(IReadOnlyList<byte[]>, long)

Produces the authentication path for one leaf from hashes already computed - what a party that streamed a large input past itself can answer without re-reading it.

public byte[][] AuthenticationPath(IReadOnlyList<byte[]> leafHashes, long leafIndex)

Parameters

leafHashes IReadOnlyList<byte[]>

The ordered leaf hashes, each HashLength bytes long.

leafIndex long

The zero-based index of the leaf to prove.

Returns

byte[][]

The path, leaf-upward.

Remarks

The leaf hashes of a streamed computation are available from LeafHashes.

Exceptions

ArgumentNullException

leafHashes is null.

ArgumentException

An element is null or is not HashLength bytes long.

ArgumentOutOfRangeException

leafIndex is negative or is not less than the number of leaf hashes.

NotSupportedException

This instance's FanOut is not two.

AuthenticationPath(IReadOnlyList<ReadOnlyMemory<byte>>, long)

Produces the authentication path for one entry of a tree: the sibling subtree roots from the leaf upward.

public byte[][] AuthenticationPath(IReadOnlyList<ReadOnlyMemory<byte>> entries, long leafIndex)

Parameters

entries IReadOnlyList<ReadOnlyMemory<byte>>

The tree's entries, in order.

leafIndex long

The zero-based index of the entry to prove.

Returns

byte[][]

The path, leaf-upward. Empty for a one-entry tree, whose leaf hash is already the root.

Exceptions

ArgumentNullException

entries is null.

ArgumentOutOfRangeException

leafIndex is negative or is not less than the number of entries.

NotSupportedException

This instance's FanOut is not two.

BindRoot(ReadOnlySpan<byte>, long)

Binds a value into a root as H(0x02 || u64_be(boundValue) || root), producing a commitment that names one tree and no other.

public byte[] BindRoot(ReadOnlySpan<byte> root, long boundValue)

Parameters

root ReadOnlySpan<byte>

The tree head to bind, HashLength bytes long.

boundValue long

The value to bind - the entry count in entry mode, or the input's byte length in block mode.

Returns

byte[]

The bound root, HashLength bytes long.

Remarks

This is an addition to RFC 6962, not part of it, and it closes a real hole. RFC 6962's verifier takes the tree size from its caller; when the caller obtains that size from the party being examined, the party can understate it. A four-entry tree's first authentication path has exactly the length a three-entry tree's first path wants and walks to the same head, so the unbound verifier accepts both. A holder that has lost its last entry can therefore declare a smaller tree, never be asked for that entry, and pass every challenge.

Binding the size into the published commitment makes a disagreeing size produce a different root, so the challenge fails closed. In block mode bind the byte length rather than the block count: it is strictly stronger, because it also pins the final block's length.

Exceptions

ArgumentException

root is not HashLength bytes long.

ArgumentOutOfRangeException

boundValue is negative.

BlockCount(long, int)

Returns the number of blocks that an input of the specified length divides into.

public static long BlockCount(long inputLength, int blockSize)

Parameters

inputLength long

The total length, in bytes, of the input.

blockSize int

The size, in bytes, of each block.

Returns

long

The number of blocks, which is zero when inputLength is zero, and otherwise ceil(inputLength / blockSize).

Exceptions

ArgumentOutOfRangeException

inputLength is negative, or blockSize is less than or equal to zero.

BlockLength(long, long, int)

Returns the length of the specified block, which is shorter than blockSize only for the final block of an input whose length is not a whole multiple of it.

public static int BlockLength(long inputLength, long blockIndex, int blockSize)

Parameters

inputLength long

The total length, in bytes, of the input.

blockIndex long

The zero-based index of the block.

blockSize int

The size, in bytes, of each block.

Returns

int

The length, in bytes, of the block; zero when the block begins at or beyond inputLength.

Exceptions

ArgumentOutOfRangeException

inputLength or blockIndex is negative, or blockSize is less than or equal to zero.

BlockOffset(long, int)

Returns the byte offset at which the specified block begins.

public static long BlockOffset(long blockIndex, int blockSize)

Parameters

blockIndex long

The zero-based index of the block.

blockSize int

The size, in bytes, of each block.

Returns

long

The offset, in bytes, from the start of the input.

Remarks

The multiplication is performed in 64-bit arithmetic, so an offset beyond MaxValue is returned correctly rather than wrapping.

Exceptions

ArgumentOutOfRangeException

blockIndex is negative, or blockSize is less than or equal to zero.

ComputeBlocked(byte[], int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of an array, together with its leaf hashes.

public MerkleBlockComputation ComputeBlocked(byte[] source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source byte[]

The bytes to divide into blocks.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed while hashing.

Returns

MerkleBlockComputation

The computation's root, input length, block size and leaf hashes.

Exceptions

ArgumentNullException

source is null.

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeBlocked(Stream, int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of a stream and returns it together with the ordered leaf hashes, so one pass serves both publishing a root and answering authentication paths.

public MerkleBlockComputation ComputeBlocked(Stream source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source Stream

The stream to read to its end. Must be readable.

blockSize int

The size, in bytes, of each block - the chunk one leaf covers.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed between blocks.

Returns

MerkleBlockComputation

The computation's root, input length, block size and leaf hashes.

Remarks

The stream is read once, forward only, and never buffered in full. Retaining the leaf hashes costs leafCount × HashLength bytes - 16 KiB for a 512 MiB input at one-mebibyte blocks. When only the root is wanted, prefer ComputeRootOfBlocks(Stream, int, MerkleTreeDiagnostics?, CancellationToken), which holds a logarithmic number of hashes instead.

A zero-length stream yields zero leaves and the empty tree's root, not one empty leaf. A final short block is hashed at its actual length and never padded.

Exceptions

ArgumentNullException

source is null.

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeBlocked(ReadOnlyMemory<byte>, int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of a buffer already in memory, together with its leaf hashes.

public MerkleBlockComputation ComputeBlocked(ReadOnlyMemory<byte> source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source ReadOnlyMemory<byte>

The bytes to divide into blocks.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed while hashing.

Returns

MerkleBlockComputation

The computation's root, input length, block size and leaf hashes.

Remarks

The overload to prefer on a parallel instance when the bytes are already in memory: every block is sliced and hashed inside its own worker, so nothing is copied and the whole per-block cost parallelizes.

Exceptions

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeBlocked(ReadOnlySpan<byte>, int, MerkleTreeDiagnostics?)

Computes the root over fixed-size blocks of a buffer already in memory, together with its leaf hashes.

public MerkleBlockComputation ComputeBlocked(ReadOnlySpan<byte> source, int blockSize, MerkleTreeDiagnostics? diagnostics = null)

Parameters

source ReadOnlySpan<byte>

The bytes to divide into blocks.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

Returns

MerkleBlockComputation

The computation's root, input length, block size and leaf hashes.

Remarks

Equivalent to the ReadOnlyMemory<T> overload; on a parallel instance the span is copied into a pooled buffer first, because a span cannot be captured by workers, so prefer that overload when a memory is at hand.

Exceptions

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

ComputeBlockedAsync(Stream, int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of a stream asynchronously and returns it together with the ordered leaf hashes.

public Task<MerkleBlockComputation> ComputeBlockedAsync(Stream source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source Stream

The stream to read to its end. Must be readable.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed between blocks and by every read.

Returns

Task<MerkleBlockComputation>

A task whose result is the computation's root, input length, block size and leaf hashes.

Remarks

Reads are awaited, so the calling thread is free while the stream is slow; leaf hashing happens on the continuation thread, or on parallel workers when the instance is configured for them. The result is the same ComputeBlocked(Stream, int, MerkleTreeDiagnostics?, CancellationToken) returns.

Exceptions

ArgumentNullException

source is null.

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeRoot(IReadOnlyList<ReadOnlyMemory<byte>>, MerkleTreeDiagnostics?, CancellationToken)

Computes the Merkle Tree Hash over an ordered sequence of variable-length entries.

public byte[] ComputeRoot(IReadOnlyList<ReadOnlyMemory<byte>> entries, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

entries IReadOnlyList<ReadOnlyMemory<byte>>

The entries, in order. May be empty; individual entries may be empty.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed while hashing.

Returns

byte[]

The tree's root: H() when entries is empty, the single entry's leaf hash when it holds one, and the recursive node hash otherwise.

Remarks

On a parallel instance the entries are hashed concurrently, which is worthwhile only when they are individually large; for a log of short entries the thread coordination outweighs the leaf hashing.

Exceptions

ArgumentNullException

entries is null.

OperationCanceledException

cancellationToken was cancelled.

ComputeRootOfBlocks(byte[], int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of an array.

public byte[] ComputeRootOfBlocks(byte[] source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source byte[]

The bytes to divide into blocks.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed while hashing.

Returns

byte[]

The tree's root.

Exceptions

ArgumentNullException

source is null.

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeRootOfBlocks(Stream, int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of a stream while holding only a logarithmic number of hashes.

public byte[] ComputeRootOfBlocks(Stream source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source Stream

The stream to read to its end. Must be readable.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed between blocks.

Returns

byte[]

The tree's root.

Remarks

Peak memory is O(blockSize + log n × HashLength) on a sequential instance: the read buffer, plus at most fanOut − 1 pending nodes per level. A parallel instance adds the batch of block buffers. The root is identical to ComputeBlocked(Stream, int, MerkleTreeDiagnostics?, CancellationToken)'s - this overload simply cannot produce an authentication path afterwards, because it does not keep the leaf hashes.

Leaves are folded as they arrive, level by level: a level holds at most fanOut − 1 pending nodes, and the moment it fills the group is hashed and the parent carried up. At the end a lone node is promoted unchanged, never re-hashed - which is what reproduces RFC 6962's shape at a fan-out of two without ever having held the whole tree. Recording into diagnostics retains one entry per node, so the memory bound does not hold while a recorder is supplied.

Exceptions

ArgumentNullException

source is null.

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeRootOfBlocks(ReadOnlyMemory<byte>, int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of a buffer already in memory.

public byte[] ComputeRootOfBlocks(ReadOnlyMemory<byte> source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source ReadOnlyMemory<byte>

The bytes to divide into blocks.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed while hashing.

Returns

byte[]

The tree's root.

Exceptions

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeRootOfBlocks(ReadOnlySpan<byte>, int, MerkleTreeDiagnostics?)

Computes the root over fixed-size blocks of a buffer already in memory.

public byte[] ComputeRootOfBlocks(ReadOnlySpan<byte> source, int blockSize, MerkleTreeDiagnostics? diagnostics = null)

Parameters

source ReadOnlySpan<byte>

The bytes to divide into blocks.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

Returns

byte[]

The tree's root.

Remarks

On a sequential instance each block is hashed straight out of the span and folded at once, holding a logarithmic number of hashes; on a parallel instance the span is copied into a pooled buffer first, so prefer the ReadOnlyMemory<T> overload there.

Exceptions

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

ComputeRootOfBlocksAsync(Stream, int, MerkleTreeDiagnostics?, CancellationToken)

Computes the root over fixed-size blocks of a stream asynchronously while holding only a logarithmic number of hashes.

public Task<byte[]> ComputeRootOfBlocksAsync(Stream source, int blockSize, MerkleTreeDiagnostics? diagnostics = null, CancellationToken cancellationToken = default)

Parameters

source Stream

The stream to read to its end. Must be readable.

blockSize int

The size, in bytes, of each block.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

cancellationToken CancellationToken

A token observed between blocks and by every read.

Returns

Task<byte[]>

A task whose result is the tree's root.

Remarks

The asynchronous twin of ComputeRootOfBlocks(Stream, int, MerkleTreeDiagnostics?, CancellationToken): reads are awaited, the fold runs on the continuation thread, and a parallel instance hashes each batch of leaves on workers before folding.

Exceptions

ArgumentNullException

source is null.

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

OperationCanceledException

cancellationToken was cancelled.

ComputeRootOfLeafHashes(IReadOnlyList<byte[]>, MerkleTreeDiagnostics?)

Computes the Merkle Tree Hash over leaf hashes that have already been computed.

public byte[] ComputeRootOfLeafHashes(IReadOnlyList<byte[]> leafHashes, MerkleTreeDiagnostics? diagnostics = null)

Parameters

leafHashes IReadOnlyList<byte[]>

The ordered leaf hashes, each HashLength bytes long.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

Returns

byte[]

The tree's root, or H() when leafHashes is empty.

Remarks

This is the entry point for a caller that streamed the underlying bytes past itself and kept only the leaf hashes, and so cannot supply the entries again. The reduction alone is never parallel; there is nothing in it worth spreading.

Exceptions

ArgumentNullException

leafHashes is null.

ArgumentException

An element is null or is not HashLength bytes long.

ConsistencyProof(IReadOnlyList<ReadOnlyMemory<byte>>, long)

Produces the consistency proof that the first firstSize entries of entries form a prefix of the whole.

public byte[][] ConsistencyProof(IReadOnlyList<ReadOnlyMemory<byte>> entries, long firstSize)

Parameters

entries IReadOnlyList<ReadOnlyMemory<byte>>

The later tree's entries, in order.

firstSize long

The number of entries in the earlier tree.

Returns

byte[][]

The proof, or an empty proof when the two sizes are equal or the earlier tree is empty - in both cases the consistency is established by the sizes and roots alone.

Exceptions

ArgumentNullException

entries is null.

ArgumentOutOfRangeException

firstSize is negative or exceeds the number of entries.

NotSupportedException

This instance's FanOut is not two.

ConsistencyProofOfLeafHashes(IReadOnlyList<byte[]>, long)

Produces the consistency proof from leaf hashes already computed.

public byte[][] ConsistencyProofOfLeafHashes(IReadOnlyList<byte[]> leafHashes, long firstSize)

Parameters

leafHashes IReadOnlyList<byte[]>

The later tree's ordered leaf hashes.

firstSize long

The number of entries in the earlier tree.

Returns

byte[][]

The proof, or an empty proof when the sizes are equal or the earlier tree is empty.

Exceptions

ArgumentNullException

leafHashes is null.

ArgumentException

An element is null or is not HashLength bytes long.

ArgumentOutOfRangeException

firstSize is negative or exceeds the number of leaf hashes.

NotSupportedException

This instance's FanOut is not two.

CreateBlockAccumulator(int, bool, MerkleTreeDiagnostics?)

Creates an accumulator that builds the root over fixed-size blocks from bytes appended as they are written, so a writer can feed the tree from the same calls that feed its flat digest.

public MerkleBlockAccumulator CreateBlockAccumulator(int blockSize, bool retainLeafHashes = false, MerkleTreeDiagnostics? diagnostics = null)

Parameters

blockSize int

The size, in bytes, of each block - the chunk one leaf covers.

retainLeafHashes bool

true to keep every leaf hash so the accumulator can return a MerkleBlockComputation for authentication paths; false to hold only a logarithmic number of hashes.

diagnostics MerkleTreeDiagnostics

The recorder that receives the tree's nodes as they are produced, or null to record nothing.

Returns

MerkleBlockAccumulator

A new accumulator owning one algorithm from this tree's factory.

Remarks

The accumulator's root is identical to ComputeRootOfBlocks(Stream, int, MerkleTreeDiagnostics?, CancellationToken)'s over the same bytes at this instance's fan-out, and its FinishBound() is BindRoot(ReadOnlySpan<byte>, long) of that root and the byte length - the published shape for a possession check. It is sequential by nature: one writer appends, and each leaf is hashed as its block completes, whatever MaxDegreeOfParallelism is.

Exceptions

ArgumentOutOfRangeException

blockSize is less than or equal to zero.

InvalidOperationException

The algorithm factory returned null.

HashLeaf(ReadOnlySpan<byte>)

Computes the leaf hash of an entry as H(0x00 || entry).

public byte[] HashLeaf(ReadOnlySpan<byte> entry)

Parameters

entry ReadOnlySpan<byte>

The entry's bytes. May be empty.

Returns

byte[]

The leaf hash, HashLength bytes long.

Remarks

The prefix is what makes a one-entry tree's root differ from the entry's bare digest, and is not optional: HashLeaf(d) is never H(d).

HashNode(ReadOnlySpan<byte>, ReadOnlySpan<byte>)

Computes an internal node hash from its two child hashes as H(0x01 || left || right).

public byte[] HashNode(ReadOnlySpan<byte> left, ReadOnlySpan<byte> right)

Parameters

left ReadOnlySpan<byte>

The left child's hash.

right ReadOnlySpan<byte>

The right child's hash.

Returns

byte[]

The node hash, HashLength bytes long.

Remarks

Order is significant: HashNode(a, b) is not HashNode(b, a).

Exceptions

ArgumentException

left or right is not HashLength bytes long.

VerifyBlockInclusion(ReadOnlySpan<byte>, long, int, long, ReadOnlySpan<byte>, IReadOnlyList<ReadOnlyMemory<byte>>)

Verifies that a block occupies the stated position of a block-mode tree whose bound root pins the input's byte length, and that the block is exactly the length that position requires.

public bool VerifyBlockInclusion(ReadOnlySpan<byte> boundRoot, long inputLength, int blockSize, long blockIndex, ReadOnlySpan<byte> block, IReadOnlyList<ReadOnlyMemory<byte>> path)

Parameters

boundRoot ReadOnlySpan<byte>

The published bound root, binding inputLength.

inputLength long

The input's total length in bytes, as the publisher committed to it.

blockSize int

The block size the tree was built with.

blockIndex long

The zero-based index of the block being proved.

block ReadOnlySpan<byte>

The block's bytes.

path IReadOnlyList<ReadOnlyMemory<byte>>

The authentication path, leaf-upward.

Returns

bool

true when the block is where it is claimed to be; otherwise false.

Remarks

This is the possession-check shape: the tree size is derived from the bound length and block size rather than supplied, so there is no size for a holder to misstate. It additionally requires block to be exactly BlockLength(long, long, int) bytes - a check the entry-mode overloads cannot make, because a variable-length entry has no expected length.

The block's bytes are the proof. A party that retained the authentication path but discarded the block can still produce the path and still cannot answer, which is the difference between this and a digest it could have cached on receipt.

Exceptions

ArgumentNullException

path is null.

NotSupportedException

This instance's FanOut is not two.

VerifyConsistency(ReadOnlySpan<byte>, long, ReadOnlySpan<byte>, long, IReadOnlyList<ReadOnlyMemory<byte>>)

Verifies that a tree of firstSize entries with root firstRoot is a prefix of a tree of secondSize entries with root secondRoot.

public bool VerifyConsistency(ReadOnlySpan<byte> firstRoot, long firstSize, ReadOnlySpan<byte> secondRoot, long secondSize, IReadOnlyList<ReadOnlyMemory<byte>> proof)

Parameters

firstRoot ReadOnlySpan<byte>

The earlier tree's published root.

firstSize long

The earlier tree's entry count.

secondRoot ReadOnlySpan<byte>

The later tree's published root.

secondSize long

The later tree's entry count.

proof IReadOnlyList<ReadOnlyMemory<byte>>

The consistency proof.

Returns

bool

true when the proof reconstructs both roots; otherwise false.

Remarks

This is RFC 6962 §2.1.2. Unlike inclusion verification, both sizes and both roots are inputs, and the proof must reconstruct both - so there is no analogue here of the tree-size ambiguity that the bound root exists to close.

Three degenerate cases are decided before the walk. A secondSize below firstSize is rejected outright: a log cannot shrink. Equal sizes require an empty proof and identical roots - a non-empty proof between equal sizes is rejected rather than walked, because the only evidence that could be offered is evidence of something else. A firstSize of zero likewise requires an empty proof, since every tree extends the empty tree.

Like the inclusion verifiers, this returns false for every malformed input rather than throwing, and only a null proof throws.

Exceptions

ArgumentNullException

proof is null.

NotSupportedException

This instance's FanOut is not two.

VerifyInclusion(ReadOnlySpan<byte>, long, long, ReadOnlySpan<byte>, IReadOnlyList<ReadOnlyMemory<byte>>)

Verifies that an entry occupies the stated position of a tree with the stated root.

public bool VerifyInclusion(ReadOnlySpan<byte> root, long treeSize, long leafIndex, ReadOnlySpan<byte> entry, IReadOnlyList<ReadOnlyMemory<byte>> path)

Parameters

root ReadOnlySpan<byte>

The trusted root to check against.

treeSize long

The number of entries the tree is claimed to hold.

leafIndex long

The zero-based index the entry is claimed to occupy.

entry ReadOnlySpan<byte>

The entry's bytes, which are hashed as a leaf.

path IReadOnlyList<ReadOnlyMemory<byte>>

The authentication path, leaf-upward.

Returns

bool

true when the path carries entry to root; otherwise false.

Remarks

treeSize is trusted input. RFC 6962's verifier takes the tree size from its caller and cannot detect a false one. A caller that obtains the size from the party being examined has no soundness guarantee: a four-entry tree's first authentication path has exactly the length a three-entry tree's first path wants and walks to the same head, so this method returns true for both. A holder that has lost its last entry can therefore declare a smaller tree, never be asked for that entry, and pass every challenge for ever.

That behaviour is RFC 6962 working as specified, not a defect here. When the size comes from an untrusted party, verify against a length-bound root with VerifyInclusionBound(ReadOnlySpan<byte>, long, long, long, ReadOnlySpan<byte>, IReadOnlyList<ReadOnlyMemory<byte>>) instead, which fails closed on a size the publisher did not commit to.

Every malformed input returns false rather than throwing - a wrong index, a path that is too long or too short, an element of the wrong width, a zero tree size - because a verifier sits directly behind untrusted input and an exception where a false belongs is a denial of service.

Exceptions

ArgumentNullException

path is null.

NotSupportedException

This instance's FanOut is not two.

VerifyInclusionBound(ReadOnlySpan<byte>, long, long, long, ReadOnlySpan<byte>, IReadOnlyList<ReadOnlyMemory<byte>>)

Verifies an inclusion proof against a length-bound root, so a tree size the publisher did not commit to is rejected even when the unbound walk would accept it.

public bool VerifyInclusionBound(ReadOnlySpan<byte> boundRoot, long boundValue, long treeSize, long leafIndex, ReadOnlySpan<byte> entry, IReadOnlyList<ReadOnlyMemory<byte>> path)

Parameters

boundRoot ReadOnlySpan<byte>

The published bound root.

boundValue long

The value the publisher bound - the entry count, or the input's byte length.

treeSize long

The number of entries the tree is claimed to hold.

leafIndex long

The zero-based index the entry is claimed to occupy.

entry ReadOnlySpan<byte>

The entry's bytes, which are hashed as a leaf.

path IReadOnlyList<ReadOnlyMemory<byte>>

The authentication path, leaf-upward.

Returns

bool

true when the path carries entry to a head that binds to boundRoot under boundValue; otherwise false.

Remarks

This is the overload to use when the tree size comes from the party being examined. Because the bound value is hashed into the commitment, a claimed size that disagrees with the published one produces a different root and the check fails closed.

Exceptions

ArgumentNullException

path is null.

NotSupportedException

This instance's FanOut is not two.

VerifyInclusionOfLeafHash(ReadOnlySpan<byte>, long, long, ReadOnlySpan<byte>, IReadOnlyList<ReadOnlyMemory<byte>>)

Verifies an inclusion proof from a leaf hash rather than the entry's bytes.

public bool VerifyInclusionOfLeafHash(ReadOnlySpan<byte> root, long treeSize, long leafIndex, ReadOnlySpan<byte> leafHash, IReadOnlyList<ReadOnlyMemory<byte>> path)

Parameters

root ReadOnlySpan<byte>

The trusted root to check against.

treeSize long

The number of entries the tree is claimed to hold.

leafIndex long

The zero-based index the leaf is claimed to occupy.

leafHash ReadOnlySpan<byte>

The leaf's hash, HashLength bytes long.

path IReadOnlyList<ReadOnlyMemory<byte>>

The authentication path, leaf-upward.

Returns

bool

true when the path carries leafHash to root; otherwise false.

Remarks

Prefer VerifyInclusion(ReadOnlySpan<byte>, long, long, ReadOnlySpan<byte>, IReadOnlyList<ReadOnlyMemory<byte>>) where the entry's bytes are available. Possession of a leaf hash proves nothing about possession of the data: a party that kept its leaf hashes and discarded the bytes can still satisfy this overload.

treeSize is trusted input here for the same reason and with the same consequence as in the entry overload.

Exceptions

ArgumentNullException

path is null.

NotSupportedException

This instance's FanOut is not two.

Applies to

ProductVersions
.NET8, 10

See Also

MerkleBlockComputation
MerkleBlockAccumulator
MerkleTreeDiagnostics