Scalable and Adaptively Secure Any-Trust Distributed Key Generation and All-hands Checkpointing

Hanwen Feng; Tiancheng Mai; Qiang Tang

Paper 2023/1773

Scalable and Adaptively Secure Any-Trust Distributed Key Generation and All-hands Checkpointing

Hanwen Feng

, University of Sydney

Tiancheng Mai

, University of Sydney

Qiang Tang, University of Sydney

Abstract

The classical distributed key generation protocols (DKG) are resurging due to their widespread applications in blockchain. While efforts have been made to improve DKG communication, practical large-scale deployments are still yet to come due to various challenges, including the heavy computation and communication (particularly broadcast) overhead in their adversarial cases. In this paper, we propose a practical DKG for DLog-based cryptosystems, which achieves (quasi-)linear computation and communication per-node cost with the help of a common coin, even in the face of the maximal amount of Byzantine nodes. Moreover, our protocol is secure against adaptive adversaries, which can corrupt less than half of all nodes. The key to our improvements lies in delegating the most costly operations to an Any-Trust group together with a set of techniques for adaptive security. This group is randomly sampled and consists of a small number of individuals. The population only trusts that at least one member in the group is honest, without knowing which one. Moreover, we present a generic transformer that enables us to efficiently deploy a conventional distributed protocol like our DKG, even when the participants have different weights. Additionally, we introduce an extended broadcast channel based on a blockchain and data dispersal network (such as IPFS), enabling reliable broadcasting of arbitrary-size messages at the cost of constant-size blockchain storage. Our DKG leads to a fully practical instantiation of Filecoin's checkpointing mechanism, in which all validators of a Proof-of-Stake (PoS) blockchain periodically run DKG and threshold signing to create checkpoints on Bitcoin, to enhance the security of the PoS chain. In comparison with the recent checkpointing approach of Babylon (Oakland, 2023), ours enjoys a significantly smaller cost of Bitcoin transaction fees. For $2^{12}$ validators, our cost is merely 0.4\% of that incurred by Babylon's approach.

Note: Minor revision.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. ACM CCS 2024
DOI: 10.1145/3658644.3690253
Keywords: Distributed Key Generation Threshold Cryptography Long-range Attacks Bitcoin Checkpointing
Contact author(s): hanwen feng @ sydney edu au
tiancheng mai @ sydney edu au
qiang tang @ sydney edu au
History: 2024-10-07: last of 5 revisions; 2023-11-16: received; See all versions
Short URL: https://ia.cr/2023/1773
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1773,
      author = {Hanwen Feng and Tiancheng Mai and Qiang Tang},
      title = {Scalable and Adaptively Secure Any-Trust Distributed Key Generation and All-hands Checkpointing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1773},
      year = {2023},
      doi = {10.1145/3658644.3690253},
      url = {https://eprint.iacr.org/2023/1773}
}