There are instances when it is useful to prove that a document, D, exists on a certain date. In order to facilitate such proofs, Bob collects a group of documents, D₁, D₂,...,D_n, every day from people wanting time stamps for their documents on that day. Bob constructs a complete binary tree, T, with n leaves, of height [log n], with each leaf, i, associated with a document, D_i. He stores at i the result, hi = H(D_i), of a one-way hash function computed on Di. For each internal node, v, with children x and y, he stores h_v = H(h_x||h_y), where || denotes concatenation. Finally, he publishes the value, hr, for the root, r, of T in a classified advertisement in a local newspaper. How can Bob give each document owner a set of O(log n) numbers so that together with the classified advertisement, each document owner can prove the existence of his or her document on the date the ad appeared, with the confidence of the security properties of the one-way hash function, H?