Our construction relies on hashing with common-prefix proofs, a new variant of collision resistance hashing. A family 74 provides hashing with common-prefix proofs if for any H is an element of 7, given two strings X and Y equal up to position i, a prover can convince anyone that X[1..i] is a prefix of Y by sending only H(X), H(Y), and a small proof. We believe that this new primitive will lead to other interesting applications.