# Napkin Math: Costs of a Merkle Tree

This note describes the computational costs associated with constructing Merkle trees and verifying Merkle inclusion proofs.

We assume a radix-2 Merkle tree with $n$ leaves. Assume 256-bit nodes, and assume we store $k$ bytes of information per leaf.

Assume a hash such as SHA-256 that compresses 512-bit inputs into 256-bit digests.

## Prover Complexity: $\log(k) + n$
The Prover computes $\log(k) + n$ hashes in order to construct the entire Merkle tree. The first term counts the `leaf hashing`, and the second term counts the `layer hashing`.
1. `leaf hashing`: the leaf contents are hashed in order to construct the digest for each leaf node.
2. `layer hashing`: for each layer, the nodes are hashed pair-wise to compute the next layer.

## Proof Size: $k + \log(n)$ bytes
A Merkle inclusion proof consists of:
- purported leaf contents, $k$ bytes
- a purported branch, $\log(n)$ bytes

## Verifier Complexity: $\log(k) + \log(n)$
To verify the correctness of an inclusion proof, the Verifier computes:
- $\log(k)$ hashes to check that the purported leaf contents align with the purported leaf digest, and
- $log(n)$ hashes to check that the purported leaf node aligns with the prior root commitment.