Verify an append-only log with a consistency proof

A transparency log, the kind behind Certificate Transparency, promises never to change an entry once it is published. A client remembers the last size and root it saw. When the log has grown, the client asks for a consistency proof that the new tree still begins with exactly the old one; a log that rewrote history cannot produce one. Write the client's check.

Hashing. H(s) is 32-bit FNV-1a over the characters of s, all ASCII: start from 2166136261, and for each character xor in its code, then multiply by 16777619 modulo 2^32. A hash is written as 8 lowercase hex digits. A leaf's hash is H("L" + data) and an inner node's is H("N" + left + right), with left and right the two children's hex hashes. FNV is not a cryptographic hash; it stands in for SHA-256 so the exercise runs anywhere.

The tree. The root of the leaves D[0], ..., D[n-1], written MTH(D), is the leaf's hash when n is 1. Otherwise, with k the largest power of two smaller than n, it is the node hash of MTH(D[0:k]) and MTH(D[k:n]).

The proof. For 0 < m < n, the log sends SUB(m, D, true), where SUB(m, D, flag), with n the length of D, is:

• if m equals n: an empty list when flag is true, otherwise the one hash [MTH(D)]
• otherwise, with k the largest power of two smaller than n:
  • if m <= k: SUB(m, D[0:k], flag) followed by MTH(D[k:n])
  • if m > k: SUB(m - k, D[k:n], false) followed by MTH(D[0:k])

Where flag is still true, the range is exactly the old tree, which the client already holds as old_root, so the log leaves it out.

The check. verify_consistency(old_size, new_size, old_root, new_root, proof) returns true when proof has exactly the length the definition gives for these two sizes, and the old and new roots it determines (each entry is the root of a known range of leaves) are exactly old_root and new_root. Return false otherwise. When the sizes are equal, accept only an empty proof with equal roots, and never accept an old_size below 1 or above new_size.

Examples, for the leaves "e0" to "e5":

• verify_consistency(3, 4, "8f95baab", "e967a87f", ["ecf5f6e8", "edf5f87b", "941b2778"]) returns true: the proof holds the leaf hashes of e2 and e3, then the node over e0 and e1.
• The same call with old_root "f9604deb", the root of three different leaves, returns false.
• verify_consistency(4, 6, "e967a87f", "73e5518f", ["f47a82a2"]) returns true: the old tree is a whole power of two, so the proof is just the root of e4 and e5.