I think that there is an even easier time stamping service than that described by Eric Hollander. It too requires a trusted service with a trusted clock. It has just two key pairs, A and B. The protocol is that you send it a message, perhaps with payment under public-A. It returns the message joined with the time provided by its clock under key private-B. The returned message provides evidence in the future that you held the original message at the time indicated in the returned message. This protocol requires no data base of keys. It was once the practice (perhaps still) to mail oneself (US mail) a certified envelope with information that one might want to prove that he had had at some earlier date. One would then keep but not open the delivered envelope.