Finally, check ( h_k \stackrel?= R_\textknown ). Theorem 3 (Optimal proof size): The minimal number of hash values required to authenticate a single leaf in an ( n )-leaf Merkle tree is ( \lceil \log_2 n \rceil ).

Proof sketch: Each verification step halves the candidate set of possible leaves. Information-theoretically, distinguishing among ( n ) leaves requires ( \log_2 n ) bits of decision, but each hash provides a full cryptographic digest (e.g., 256 bits). However, combinatorially, the proof must provide one hash per tree level — ( \log_2 n ) levels. Any authentication scheme with fewer than ( \log_2 n ) hashes would imply a collision or truncation of the binary decision tree, violating security.

A Merkle tree is binding : Given a root ( R ) and a leaf index ( i ), the prover cannot find two different leaf values ( L, L' ) such that both verify against ( R ).

Proof size = ( O(\log n) ) still holds, but path pruning reduces storage. For append-only logs without fixed ( n ), Merkle Mountain Ranges (MMRs) allow dynamic insertion with ( O(\log n) ) proof updates. The structure is a set of perfect binary trees (peaks).

Suppose adversary finds ( L \neq L' ) and valid Merkle proofs ( P, P' ) for the same root ( R ) and same leaf index ( i ). Following the recomputation path, the first point where hash inputs differ (but yield same output) produces a collision in ( H ).

Thus, Merkle trees achieve (information-theoretically optimal) proof size up to constant factors. 4. Security Analysis: Collision Resistance and Binding 4.1 Formal Security Model Let ( H : 0,1^* \to 0,1^m ) be a cryptographic hash function (assumed collision-resistant).

: For total size ( n ), the binary representation of ( n ) determines the peaks. If ( n = \sum_j=1^t 2^k_j ) (binary expansion), there are ( t ) peaks. 7. Complexity Bounds: Why Merkle is "Top" 7.1 Lower bound for static data authentication Theorem 5 (Lower bound): Any authentication scheme for ( n ) independent data blocks that allows verification of a single block with less than ( \log_2 n ) transmitted cryptographic digests is insecure against a computationally unbounded adversary, assuming no pre-verifier state beyond root.

If ( H ) is ( \epsilon )-collision-resistant (max probability ( \epsilon ) of finding collision in time ( t )), then the Merkle tree is ( \epsilon' )-binding where ( \epsilon' \leq \epsilon ) (and verification time ( O(\log n) )). 4.2 Inclusion Proof Security Probability a random forgery succeeds: Without access to preimages, the adversary must guess a sibling hash that recomputes to ( R ). This is as hard as finding a second preimage for ( H ).