### Transparent Batchable Time-lock Puzzles and Applications to Byzantine Consensus

##### Abstract

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)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Time-lock puzzles Byzantine broadcast Batch solving Nakamoto consensus Mobile-sluggish faults
Contact author(s)
sshravan @ cs umd edu
t srikrishnan @ gmail com
History
2022-10-24: approved
See all versions
Short URL
https://ia.cr/2022/1421

CC BY

BibTeX

@misc{cryptoeprint:2022/1421,
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{https://eprint.iacr.org/2022/1421}},
url = {https://eprint.iacr.org/2022/1421}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.