Non-interactive Cryptographic Timestamping Based on Verifiable Delay Functions

We present the first treatment of non-interactive publicly-verifiable timestamping schemes in the Universal Composability framework. Inspired by the timestamping properties of Bitcoin, we use non-parallelizable computational work that relates to elapsed time to avoid previous impossibility results on non-interactive timestamping. We introduce models of verifiable delay functions (VDF) related to a clock and non-interactive timestamping in the UC-framework. These are used to present a secure construction that provides improvements over previous concrete constructions. Namely, timestamps forged by the adversary are now limited to a certain time-window that depends only on the adversary’s ability to compute VDFs more quickly and on the length of corruption. Finally, we discuss how our construction can be added to non-PoW blockchain protocols to prevent costless simulation attacks.