Multi-instance publicly verifiable time-lock puzzle and its applications

Time-lock puzzles are elegant protocols that enable a party to lock a message such that no one else can unlock it until a certain time elapses. Nevertheless, existing schemes are not suitable for the case where a server is given multiple instances of a puzzle scheme at once and it must unlock them at different points in time. If the schemes are naively used in this setting, then the server has to start solving all puzzles as soon as it receives them, that ultimately imposes significant computation cost and demands a high level of parallelisation. We put forth and formally define a primitive called “multi-instance time-lock puzzle” which allows composing a puzzle’s instances. We propose a candidate construction: “chained time-lock puzzle” (C-TLP). It allows the server, given instances’ composition, to solve puzzles sequentially, without having to run parallel computations on them. C-TLP makes black-box use of a standard time-lock puzzle scheme and is accompanied by a lightweight publicly verifiable algorithm. It is the first time-lock puzzle that offers a combination of the above features. We use C-TLP to build the first “outsourced proofs of retrievability” that can support real-time detection and fair payment while having lower overhead than the state of the art. As another application of C-TLP, we illustrate in certain cases, one can substitute a “verifiable delay function” with C-TLP, to gain much better efficiency.