Paper 2022/1421
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
Metadata
- Available format(s)
-
PDF
- 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
- 2022-10-19: received
- See all versions
- Short URL
- https://ia.cr/2022/1421
- License
-
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}, url = {https://eprint.iacr.org/2022/1421} }