Consider the time stamping problem from the previous exercise, but now suppose that each day that there is one document added to the set, and one document that is removed from the set, but all of the remaining documents still need to be proven to exist as a part of the set on that day. Explain how Bob can update the tree, T, in O(log n) time, to reflect these changes?

Data From Previous Exercise

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?