Paper 2022/1421

Transparent Batchable Time-lock Puzzles and Applications to Byzantine Consensus

Shravan Srinivasan, University of Maryland, College Park
Julian Loss, CISPA Helmoltz Center for Information
Giulio Malavolta, Max Planck Institute for Security and Privacy
Kartik Nayak, Duke University
Charalampos Papamanthou, Yale University
Sri AravindaKrishnan Thyagarajan, NTT Research

Time-lock puzzles (TLP) are a fascinating type of cryptographic problem that is easy to generate, but takes a certain time to solve, even when arbitrary parallel speedup is allowed. TLPs have wide-ranging applications including fairness, round efficient computation, and more. To reduce the effort needed to solve large numbers of TLPs, prior work has proposed batching techniques to reduce the cost of solving. However, these proposals either require: (1) a trusted setup or (2) the puzzle size linear in the maximum batch size, which implies setting an a priori bound on the maximum size of the batch. Any of these limitations restrict the utility of TLPs in decentralized and dynamic settings like permissionless blockchains. In this work, we demonstrate the feasibility and usefulness of a TLP that overcomes all of the above limitations. Our construction is based on indistinguishable obfuscation and shows that there are no fundamental barriers in achieving such a TLP construction. As a main application of our TLP, we show how to improve the resilience of consensus protocols toward network-level adversaries in the following two settings: (1) We show a generic compiler that boosts the resilience of a Byzantine broadcast protocol $\Pi$ as follows: if $\Pi$ is secure against $t<n$ weakly adaptive corruptions, then the compiled protocol is secure against $t<n$ strongly adaptive corruptions. Here, `strong' refers to adaptively corrupting a party and deleting messages that it sent while still honest. Our compiler is round and communication preserving, and gives the first expected constant-round Byzantine broadcast protocol against a strongly adaptive adversary for the dishonest majority setting. (2) We adapt the Nakamoto consensus protocol to a weak model of synchrony where the adversary can adaptively create minority partitions in the network. Unlike prior works, we do not assume that all honest messages are delivered within a known upper bound on the message delay. To the best of our knowledge, this is the first work to show that it is possible to achieve consensus in the permissionless setting even after relaxing the standard synchrony assumption.

Available format(s)
Cryptographic protocols
Publication info
Time-lock puzzles Byzantine broadcast Batch solving Nakamoto consensus Mobile-sluggish faults
Contact author(s)
sshravan @ cs umd edu
t srikrishnan @ gmail com
2022-10-24: approved
2022-10-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shravan Srinivasan and Julian Loss and Giulio Malavolta and Kartik Nayak and Charalampos Papamanthou and Sri AravindaKrishnan Thyagarajan},
      title = {Transparent Batchable Time-lock Puzzles and Applications to Byzantine Consensus},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1421},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.