# Merkle Tree
Hash each block, then hash the pairs upward until one root remains. The root commits to every byte, and log n sibling hashes prove any block.
**Time:** O(n)
**Space:** O(n)
**Difficulty:** MEDIUM
*[Interactive widget: merkle-tree-builder (Merkle Tree Builder) — open the HTML page]*
Canonical: https://scaleengineer.com/algorithms/merkle-tree
---
A Merkle tree turns a set of data blocks into one short hash\. Hash each block to get the leaves\. Hash each pair of leaves to get the level above\. Keep going until one hash remains: the root\. The root commits to every byte of every block, so two copies of the same dataset always produce the same root, and one changed byte anywhere produces a different one\.

The figure above builds a tree over four blocks: alpha, beta, gamma, and delta\. Press play and watch the hashes climb from the leaves to the root\. The figure uses a short four\-character hash so the values fit on screen\. A real Merkle tree uses SHA\-256, and every step is identical\. Ralph Merkle patented the scheme in 1979, and it still underpins systems that verify data they never store\.

## Build from the bottom up

Every leaf holds the hash of one block\. In the figure, `H("alpha") = 61d0` and `H("beta") = 46c4`\. A leaf commits to exactly one block, and it says nothing about any other\.

Press play again and watch the order\. The leaves fill in left to right, then the branches, then the root\. A hash appears only after the values it consumes, so the tree builds level by level, never mid\-air\.

Each branch node holds the hash of its two children, concatenated in order\. The left branch computes `H(61d0 · 46c4) = 3c60`, and the right branch computes `H(1388 · b94c) = 27ea`\. Order matters, because H\(a · b\) and H\(b · a\) are different hashes\. A branch commits to its children and to which child sat on the left\.

One more round combines the branches, and the root `7acf` commits to all four blocks\. For `n` blocks the tree holds `2n − 1` hashes in total, so building one costs `O(n)` hashing and `O(n)` space\.

Commit has a precise meaning here\. Given only the root, nobody can produce a different dataset with the same root, because that would mean beating the hash function at some level of the tree\. The root is small, but it stands for everything beneath it\.

Real datasets rarely come in neat powers of two\. When a level has an odd number of hashes, the last hash is duplicated to make a pair, and the build continues\. The demo trees never trigger the rule, but every implementation needs it\.

## One edit reaches the root

Open the figure again and change `beta` to `beta!` in the block input\. Three hashes flip, one per level\. The leaf `46c4` becomes `1ed8`, the branch `3c60` becomes `e16b`, and the root `7acf` becomes `5d68`\. The other four hashes never move\.

The cascade is the hash function's doing\. A hash mixes its input, so a one\-character change produces an unrelated output\. The branch above the edited leaf consumes the new hash, so the branch changes, and so does every node up to the root\. The path from a leaf to the root has `log₂ n` nodes, so an edit costs `O(log n)` recomputes, not a rebuild\.

This cascade is the trick the whole structure exists for\. To check whether two copies of a dataset agree, compare the roots\. Equal roots mean equal data, with near\-certainty\. Different roots mean something diverged, and comparing children walks straight to the differing subtree in `log₂ n` steps\. Two machines can audit a billion blocks by exchanging a handful of hashes\.

The rest of the tree stays untouched because its inputs stay untouched\. A hash covers exactly the nodes beneath it, so a change travels only along the path from the edited leaf to the root\. Everything off that path keeps its value, and nobody recomputes it\.

The build fits in a dozen lines\. Leaves hash with a 0x00 prefix and branches with 0x01, so a leaf can never be mistaken for a pair of children\. The implementation panel below adds proof generation and verification, in Python and JavaScript\.

```python
import hashlib

def H(data: bytes) -> bytes:
	return hashlib.sha256(data).digest()

def merkle_root(blocks: list[bytes]) -> bytes:
	level = [H(b"\x00" + block) for block in blocks]
	while len(level) > 1:
		if len(level) % 2 == 1:
			level.append(level[-1])  # duplicate the odd hash
		level = [H(b"\x01" + level[i] + level[i + 1])
				 for i in range(0, len(level), 2)]
	return level[0]
```

## A proof shows one block without the rest

The root has a second use, and it is the surprising one\. Say you store eight blocks, and a verifier trusts the root `c1f3`\. To prove that `gamma` is in the tree, you could send all eight blocks and let the verifier rebuild the tree\. Or you could send `gamma` and three hashes\.

The three hashes are the siblings on the path from `gamma`'s leaf to the root: `b94c` beside the leaf, `3c60` beside the first branch, and `5866` beside the second\. The block plus those siblings is the proof\. Everything else in the tree stays hidden\.

The verifier hashes `gamma` to get `1388`, then combines the running hash with each sibling, on the side the sibling came from\. First `H(1388 · b94c) = 27ea`, then `H(3c60 · 27ea) = 7acf`, then `H(7acf · 5866) = c1f3`\. The candidate root equals the known root, so the block is in\. Had any byte of `gamma` differed, the first hash would differ, and the mismatch would climb to the root exactly as it does in the edit demo\.

The prover has an easy job too\. Walking from the leaf to the root and collecting the sibling at each level takes `log₂ n` reads from a stored tree, so serving a proof is as cheap as checking one\.

*[Interactive widget: merkle-proof — open the HTML page]*

Step through the figure\. The dashed nodes are hashes the verifier never sees: eight of the fifteen\. Flip the tamper switch to change one byte of the block, and the candidate root lands on `d9ed` instead of `c1f3`\. The proof fails before the data is even stored\.

A proof cannot be faked, because faking one means finding different input that hashes to a value already in the tree\. That is a second\-preimage attack on the hash function, and for SHA\-256 no practical attack exists\. The tree's safety is exactly the hash function's safety\.

Notice what the verifier had to store: one root, thirty\-two bytes with SHA\-256\. From that alone it can check any block anyone ever shows it, against a dataset it has never seen\. That is the exchange a Merkle tree offers\. A little trust at the top buys certainty about everything below\.

## What a proof costs

A proof holds one sibling hash per level, and a tree over `n` blocks has `log₂ n` levels\. Verification costs the same number of hashes\. Both grow painfully slowly:

| Blocks | Proof size | Hashes to verify |
| --- | --- | --- |
| `8` | `3` | `3` |
| `1,024` | `10` | `10` |
| `1,048,576` | `20` | `20` |
| `1,073,741,824` | `30` | `30` |

A billion blocks prove with thirty hashes\. A Bitcoin block with two thousand transactions proves any one of them with eleven\. That asymmetry is the whole point: one side stores everything, the other side stores almost nothing, and the root ties them together\.

## Where it earns its keep

Merkle trees show up wherever a small commitment must stand in for a large dataset:

- **Bitcoin\. **Every transaction in a block feeds into a Merkle tree, and the block header carries only the root\. A light wallet downloads no transactions at all\. It verifies a payment from a proof\.
- **Git\. **A repository is a Merkle tree of blobs, trees, and commits, and the commit hash is the root\. That is why rewriting one commit rewrites the hash of every commit after it\.
- **Certificate Transparency\. **Logs append every issued certificate to a Merkle tree and publish signed roots, so anyone can prove a certificate was logged\.
- **BitTorrent and IPFS\. **A file is named by the root of its chunk tree\. Each downloaded chunk is verified against its path before it is used, so untrusted peers can serve the pieces\.
- **Ethereum\. **Every block commits to the entire state of the chain through a Merkle\-style trie, so a light client can ask for one account balance and check the proof itself\.
- **Distributed databases\. **Dynamo and Cassandra compare per\-range Merkle trees between replicas\. Matching roots skip the data entirely, and mismatching subtrees mark the rows to repair\.

## What a Merkle tree cannot do

Three limits follow from the design:

- **Prove absence\. **A proof shows that a block is in the tree\. Showing that a block is nowhere in the tree needs a different structure, such as a sparse Merkle tree\.
- **Vouch for itself\. **A proof is only as honest as the root it checks against\. The root must come from a source you trust: signed, published, or pinned ahead of time\.
- **Hold the data\. **The tree stores hashes, not blocks\. Someone must keep the blocks, because the root cannot rebuild them\.

Keep the two directions straight and the practice problems below get easier: hashing climbs from the leaves, and trust flows down from the root\. Several are tree problems whose fast solution is a Merkle tree in disguise\. Hash each subtree, then compare roots\.

## Code examples

### Merkle tree build, proof, and verify (Python)

```python
import hashlib

def H(data: bytes) -> bytes:
    return hashlib.sha256(data).digest()

def hash_leaf(block: bytes) -> bytes:
    # The 0x00 / 0x01 prefixes keep leaves and branches in separate domains.
    return H(b"\x00" + block)

def hash_pair(left: bytes, right: bytes) -> bytes:
    return H(b"\x01" + left + right)

def build_tree(blocks: list[bytes]) -> list[list[bytes]]:
    """Return the levels of the tree, leaves first, root last."""
    levels = [[hash_leaf(block) for block in blocks]]
    while len(levels[-1]) > 1:
        level = levels[-1]
        if len(level) % 2 == 1:
            level = level + [level[-1]]  # duplicate the odd hash
        levels.append([
            hash_pair(level[i], level[i + 1])
            for i in range(0, len(level), 2)
        ])
    return levels

def merkle_proof(blocks: list[bytes], index: int) -> list[tuple[bytes, str]]:
    """Sibling hashes on the path from blocks[index] up to the root."""
    proof = []
    for level in build_tree(blocks)[:-1]:
        if len(level) % 2 == 1:
            level = level + [level[-1]]
        is_right_child = index % 2 == 1
        sibling = index - 1 if is_right_child else index + 1
        side = "left" if is_right_child else "right"
        proof.append((level[sibling], side))
        index //= 2
    return proof

def verify_proof(
    block: bytes, proof: list[tuple[bytes, str]], root: bytes
) -> bool:
    acc = hash_leaf(block)
    for sibling, side in proof:
        acc = hash_pair(sibling, acc) if side == "left" else hash_pair(acc, sibling)
    return acc == root

```

### Merkle tree build, proof, and verify (JavaScript)

```javascript
const { createHash } = require("crypto");

const H = (data) => createHash("sha256").update(data).digest();

// The 0x00 / 0x01 prefixes keep leaves and branches in separate domains.
const hashLeaf = (block) => H(Buffer.concat([Buffer.from([0x00]), block]));
const hashPair = (left, right) =>
  H(Buffer.concat([Buffer.from([0x01]), left, right]));

/** Return the levels of the tree, leaves first, root last. */
function buildTree(blocks) {
  const levels = [blocks.map(hashLeaf)];
  while (levels[levels.length - 1].length > 1) {
    let level = levels[levels.length - 1];
    if (level.length % 2 === 1) {
      level = [...level, level[level.length - 1]]; // duplicate the odd hash
    }
    const next = [];
    for (let i = 0; i < level.length; i += 2) {
      next.push(hashPair(level[i], level[i + 1]));
    }
    levels.push(next);
  }
  return levels;
}

/** Sibling hashes on the path from blocks[index] up to the root. */
function merkleProof(blocks, index) {
  const proof = [];
  for (const level of buildTree(blocks).slice(0, -1)) {
    const padded =
      level.length % 2 === 1 ? [...level, level[level.length - 1]] : level;
    const isRightChild = index % 2 === 1;
    proof.push({
      sibling: padded[isRightChild ? index - 1 : index + 1],
      side: isRightChild ? "left" : "right",
    });
    index = Math.floor(index / 2);
  }
  return proof;
}

function verifyProof(block, proof, root) {
  let acc = hashLeaf(block);
  for (const { sibling, side } of proof) {
    acc = side === "left" ? hashPair(sibling, acc) : hashPair(acc, sibling);
  }
  return acc.equals(root);
}

```

### Merkle tree build, proof, and verify (Java)

```java
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MerkleTree {
    public record ProofStep(byte[] hash, boolean siblingIsLeft) {}

    private static final byte LEAF_PREFIX = 0x00;
    private static final byte NODE_PREFIX = 0x01;

    private final List<byte[][]> levels = new ArrayList<>();

    public MerkleTree(List<byte[]> blocks) {
        if (blocks == null || blocks.isEmpty())
            throw new IllegalArgumentException("need at least one block");

        byte[][] leaves = new byte[blocks.size()][];
        for (int i = 0; i < blocks.size(); i++) leaves[i] = hashLeaf(blocks.get(i));
        levels.add(leaves);

        byte[][] level = leaves;
        while (level.length > 1) {
            byte[][] next = new byte[(level.length + 1) / 2][];
            for (int i = 0, j = 0; i < level.length; i += 2, j++) {
                // odd node promotes unchanged — never duplicated
                next[j] = (i + 1 < level.length)
                        ? hashNode(level[i], level[i + 1])
                        : level[i];
            }
            levels.add(next);
            level = next;
        }
    }

    private static MessageDigest sha256() {
        try {
            return MessageDigest.getInstance("SHA-256");
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException("SHA-256 unavailable", e);
        }
    }

    private static byte[] hashLeaf(byte[] data) {
        MessageDigest md = sha256();
        md.update(LEAF_PREFIX);
        md.update(data);
        return md.digest();
    }

    private static byte[] hashNode(byte[] left, byte[] right) {
        MessageDigest md = sha256();
        md.update(NODE_PREFIX);
        md.update(left);
        md.update(right);
        return md.digest();
    }

    public byte[] root() { return levels.get(levels.size() - 1)[0]; }

    public String rootHex() {
        StringBuilder sb = new StringBuilder();
        for (byte b : root()) sb.append(String.format("%02x", b));
        return sb.toString();
    }

    public List<ProofStep> proof(int index) {
        if (index < 0 || index >= levels.get(0).length)
            throw new IndexOutOfBoundsException("index out of bounds");

        List<ProofStep> steps = new ArrayList<>();
        int i = index;

        for (int l = 0; l < levels.size() - 1; l++) {
            byte[][] level = levels.get(l);
            int sibling = i ^ 1;
            if (sibling < level.length) {   // absent => this node was promoted
                steps.add(new ProofStep(level[sibling], sibling < i));
            }
            i >>= 1;
        }
        return steps;
    }

    public static boolean verify(byte[] block, List<ProofStep> proof, byte[] root) {
        byte[] h = hashLeaf(block);
        for (ProofStep step : proof) {
            h = step.siblingIsLeft()
                    ? hashNode(step.hash(), h)
                    : hashNode(h, step.hash());
        }
        return MessageDigest.isEqual(h, root);   // constant-time comparison
    }
}
```

### Merkle tree build, proof, and verify (CPP)

```cpp
// Requires OpenSSL: g++ merkle.cpp -lcrypto
#include <openssl/evp.h>

#include <array>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>

class MerkleTree {
public:
    using Hash = std::array<uint8_t, 32>;
    struct ProofStep { Hash hash; bool siblingIsLeft; };

    explicit MerkleTree(const std::vector<std::vector<uint8_t>>& blocks) {
        if (blocks.empty()) throw std::invalid_argument("need at least one block");

        std::vector<Hash> leaves;
        leaves.reserve(blocks.size());
        for (const auto& b : blocks) leaves.push_back(hashLeaf(b));
        levels_.push_back(std::move(leaves));

        while (levels_.back().size() > 1) {
            const auto& level = levels_.back();
            std::vector<Hash> next;
            next.reserve((level.size() + 1) / 2);

            for (std::size_t i = 0; i < level.size(); i += 2) {
                // odd node promotes unchanged — never duplicated
                next.push_back(i + 1 < level.size()
                                   ? hashNode(level[i], level[i + 1])
                                   : level[i]);
            }
            levels_.push_back(std::move(next));
        }
    }

    const Hash& root() const { return levels_.back()[0]; }

    std::string rootHex() const {
        static const char* hex = "0123456789abcdef";
        std::string out;
        out.reserve(64);
        for (uint8_t b : root()) { out += hex[b >> 4]; out += hex[b & 0x0F]; }
        return out;
    }

    std::vector<ProofStep> proof(std::size_t index) const {
        if (index >= levels_[0].size()) throw std::out_of_range("index out of bounds");

        std::vector<ProofStep> steps;
        std::size_t i = index;

        for (std::size_t l = 0; l + 1 < levels_.size(); ++l) {
            const auto& level = levels_[l];
            std::size_t sibling = i ^ 1;
            if (sibling < level.size()) {   // absent => this node was promoted
                steps.push_back({level[sibling], sibling < i});
            }
            i >>= 1;
        }
        return steps;
    }

    static bool verify(const std::vector<uint8_t>& block,
                       const std::vector<ProofStep>& proof,
                       const Hash& root) {
        Hash h = hashLeaf(block);
        for (const auto& step : proof) {
            h = step.siblingIsLeft ? hashNode(step.hash, h) : hashNode(h, step.hash);
        }
        return h == root;
    }

private:
    static Hash sha256(const uint8_t* data, std::size_t len) {
        Hash out{};
        unsigned int outLen = 0;
        if (EVP_Digest(data, len, out.data(), &outLen, EVP_sha256(), nullptr) != 1) {
            throw std::runtime_error("SHA-256 failed");
        }
        return out;
    }

    static Hash hashLeaf(const std::vector<uint8_t>& data) {
        std::vector<uint8_t> buf;
        buf.reserve(1 + data.size());
        buf.push_back(0x00);
        buf.insert(buf.end(), data.begin(), data.end());
        return sha256(buf.data(), buf.size());
    }

    static Hash hashNode(const Hash& left, const Hash& right) {
        uint8_t buf[1 + 32 + 32];
        buf[0] = 0x01;
        std::copy(left.begin(), left.end(), buf + 1);
        std::copy(right.begin(), right.end(), buf + 33);
        return sha256(buf, sizeof(buf));
    }

    std::vector<std::vector<Hash>> levels_;   // levels_[0] = leaves
};
```

### Merkle tree build, proof, and verify (C)

```c
/* Requires OpenSSL: cc merkle.c -lcrypto */
#include <openssl/evp.h>

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define HASH_LEN 32

typedef struct { uint8_t bytes[HASH_LEN]; } Hash;

typedef struct { Hash hash; int sibling_is_left; } ProofStep;

typedef struct {
    Hash  **levels;      /* levels[0] = leaves, levels[nlevels-1] = {root} */
    size_t *counts;
    size_t  nlevels;
} MerkleTree;

static int sha256(const uint8_t *data, size_t len, Hash *out) {
    unsigned int out_len = 0;
    return EVP_Digest(data, len, out->bytes, &out_len, EVP_sha256(), NULL) == 1
           && out_len == HASH_LEN ? 0 : -1;
}

static int hash_leaf(const uint8_t *data, size_t len, Hash *out) {
    uint8_t *buf = malloc(1 + len);
    if (!buf) return -1;
    buf[0] = 0x00;                      /* leaf domain separator */
    memcpy(buf + 1, data, len);
    int rc = sha256(buf, 1 + len, out);
    free(buf);
    return rc;
}

static int hash_node(const Hash *left, const Hash *right, Hash *out) {
    uint8_t buf[1 + 2 * HASH_LEN];
    buf[0] = 0x01;                      /* internal domain separator */
    memcpy(buf + 1, left->bytes, HASH_LEN);
    memcpy(buf + 1 + HASH_LEN, right->bytes, HASH_LEN);
    return sha256(buf, sizeof buf, out);
}

void merkle_free(MerkleTree *t) {
    if (!t) return;
    if (t->levels) for (size_t i = 0; i < t->nlevels; ++i) free(t->levels[i]);
    free(t->levels);
    free(t->counts);
    free(t);
}

/* blocks/lens describe n data blocks. Returns NULL on bad input or allocation failure. */
MerkleTree *merkle_create(const uint8_t **blocks, const size_t *lens, size_t n) {
    if (n == 0) return NULL;

    MerkleTree *t = calloc(1, sizeof *t);
    if (!t) return NULL;

    /* ceil(log2(n)) + 1 levels is always enough */
    size_t max_levels = 1;
    for (size_t s = n; s > 1; s = (s + 1) / 2) max_levels++;

    t->levels = calloc(max_levels, sizeof *t->levels);
    t->counts = calloc(max_levels, sizeof *t->counts);
    if (!t->levels || !t->counts) { merkle_free(t); return NULL; }

    Hash *leaves = malloc(n * sizeof *leaves);
    if (!leaves) { merkle_free(t); return NULL; }
    for (size_t i = 0; i < n; ++i) {
        if (hash_leaf(blocks[i], lens[i], &leaves[i]) != 0) {
            free(leaves); merkle_free(t); return NULL;
        }
    }
    t->levels[0] = leaves;
    t->counts[0] = n;
    t->nlevels = 1;

    while (t->counts[t->nlevels - 1] > 1) {
        Hash  *cur = t->levels[t->nlevels - 1];
        size_t cnt = t->counts[t->nlevels - 1];
        size_t nxt_cnt = (cnt + 1) / 2;

        Hash *nxt = malloc(nxt_cnt * sizeof *nxt);
        if (!nxt) { merkle_free(t); return NULL; }

        for (size_t i = 0, j = 0; i < cnt; i += 2, ++j) {
            if (i + 1 < cnt) {
                if (hash_node(&cur[i], &cur[i + 1], &nxt[j]) != 0) {
                    free(nxt); merkle_free(t); return NULL;
                }
            } else {
                nxt[j] = cur[i];        /* promote, never duplicate */
            }
        }
        t->levels[t->nlevels] = nxt;
        t->counts[t->nlevels] = nxt_cnt;
        t->nlevels++;
    }
    return t;
}

const Hash *merkle_root(const MerkleTree *t) {
    return &t->levels[t->nlevels - 1][0];
}

/* Writes up to *nsteps entries; sets *nsteps to the count used. Returns 0 or -1. */
int merkle_proof(const MerkleTree *t, size_t index, ProofStep *out, size_t *nsteps) {
    if (index >= t->counts[0]) return -1;

    size_t used = 0, i = index;
    for (size_t l = 0; l + 1 < t->nlevels; ++l) {
        size_t sibling = i ^ 1;
        if (sibling < t->counts[l]) {          /* absent => node was promoted */
            if (used >= *nsteps) return -1;
            out[used].hash = t->levels[l][sibling];
            out[used].sibling_is_left = (sibling < i);
            used++;
        }
        i >>= 1;
    }
    *nsteps = used;
    return 0;
}

/* Returns 1 if the proof validates against root, 0 otherwise. */
int merkle_verify(const uint8_t *block, size_t len,
                  const ProofStep *proof, size_t nsteps, const Hash *root) {
    Hash h;
    if (hash_leaf(block, len, &h) != 0) return 0;

    for (size_t i = 0; i < nsteps; ++i) {
        Hash next;
        int rc = proof[i].sibling_is_left
                     ? hash_node(&proof[i].hash, &h, &next)
                     : hash_node(&h, &proof[i].hash, &next);
        if (rc != 0) return 0;
        h = next;
    }
    return CRYPTO_memcmp(h.bytes, root->bytes, HASH_LEN) == 0;
}
```

### Merkle tree build, proof, and verify (CSharp)

```csharp
using System;
using System.Collections.Generic;
using System.Security.Cryptography;

public class MerkleTree
{
    public readonly record struct ProofStep(byte[] Hash, bool SiblingIsLeft);

    private const byte LeafPrefix = 0x00;
    private const byte NodePrefix = 0x01;

    private readonly List<byte[][]> levels = new();   // levels[0] = leaves

    public MerkleTree(IReadOnlyList<byte[]> blocks)
    {
        if (blocks is null || blocks.Count == 0)
            throw new ArgumentException("need at least one block", nameof(blocks));

        var leaves = new byte[blocks.Count][];
        for (int i = 0; i < blocks.Count; i++) leaves[i] = HashLeaf(blocks[i]);
        levels.Add(leaves);

        var level = leaves;
        while (level.Length > 1)
        {
            var next = new byte[(level.Length + 1) / 2][];
            for (int i = 0, j = 0; i < level.Length; i += 2, j++)
            {
                // odd node promotes unchanged — never duplicated
                next[j] = (i + 1 < level.Length)
                    ? HashNode(level[i], level[i + 1])
                    : level[i];
            }
            levels.Add(next);
            level = next;
        }
    }

    private static byte[] HashLeaf(byte[] data)
    {
        var buf = new byte[1 + data.Length];
        buf[0] = LeafPrefix;
        Buffer.BlockCopy(data, 0, buf, 1, data.Length);
        return SHA256.HashData(buf);
    }

    private static byte[] HashNode(byte[] left, byte[] right)
    {
        var buf = new byte[1 + left.Length + right.Length];
        buf[0] = NodePrefix;
        Buffer.BlockCopy(left, 0, buf, 1, left.Length);
        Buffer.BlockCopy(right, 0, buf, 1 + left.Length, right.Length);
        return SHA256.HashData(buf);
    }

    public byte[] Root => levels[^1][0];

    public string RootHex => Convert.ToHexString(Root).ToLowerInvariant();

    public List<ProofStep> Proof(int index)
    {
        if (index < 0 || index >= levels[0].Length)
            throw new ArgumentOutOfRangeException(nameof(index));

        var steps = new List<ProofStep>();
        int i = index;

        for (int l = 0; l < levels.Count - 1; l++)
        {
            var level = levels[l];
            int sibling = i ^ 1;
            if (sibling < level.Length)      // absent => this node was promoted
                steps.Add(new ProofStep(level[sibling], sibling < i));
            i >>= 1;
        }
        return steps;
    }

    public static bool Verify(byte[] block, IEnumerable<ProofStep> proof, byte[] root)
    {
        byte[] h = HashLeaf(block);
        foreach (var step in proof)
        {
            h = step.SiblingIsLeft
                ? HashNode(step.Hash, h)
                : HashNode(h, step.Hash);
        }
        return CryptographicOperations.FixedTimeEquals(h, root);   // constant-time
    }
}
```