Paper 2022/1494

The DAG KNIGHT Protocol: A Parameterless Generalization of Nakamoto Consensus

Yonatan Sompolinsky, Harvard University
Michael Sutton
Abstract

In 2008 Satoshi wrote the first permissionless consensus protocol, known as Nakamoto Consensus (NC), and implemented in Bitcoin. A large body of research was dedicated since to modify and extend NC, in various aspects: speed, throughput, energy consumption, computation model, and more. One line of work focused on alleviating the security-speed tradeoff which NC suffers from by generalizing Satoshi's blockchain into a directed acyclic graph of blocks, a block DAG. Indeed, the block creation rate in Bitcoin must be suppressed in order to ensure that the block interval is much longer than the worst case latency in the network. In contrast, the block DAG paradigm allows for arbitrarily high block creation rate and block sizes, as long as the capacity of nodes and of the network backbone are not exceeded. Still, these protocols, as well as other permissionless protocols, assume an a priori bound on the worst case latency, and hardcode a corresponding parameter in the protocol. Confirmation times then depend on this worst case bound, even when the network is healthy and messages propagate very fast. In this work we set out to alleviate this constraint, and create the first permissionless protocol which contains no a priori in-protocol bound over latency. DAG-KNIGHT is thus responsive to network conditions, while tolerating a corruption of up to 50% of the computational power (hashrate) in the network. To circumvent an impossibility result by Pass and Shi, we require that the client specifies locally an upper bound over the maximum adversarial recent latency in the network. DAG-KNIGHT is an evolution of the PHANTOM paradigm, which is a parameterized generalization of NC.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
Distributed SystemsConsensusScalability
Contact author(s)
yonatan sompolinsky @ gmail com
michael sutton @ mail huji ac il
History
2023-02-24: last of 2 revisions
2022-10-31: received
See all versions
Short URL
https://ia.cr/2022/1494
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1494,
      author = {Yonatan Sompolinsky and Michael Sutton},
      title = {The DAG KNIGHT Protocol: A Parameterless Generalization of Nakamoto Consensus},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1494},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1494}},
      url = {https://eprint.iacr.org/2022/1494}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.