Paper 2021/180

Unique Chain Rule and its Applications

Adithya Bhat, Purdue University West Lafayette
Akhil Bandarupalli, Purdue University West Lafayette
Saurabh Bagchi, Purdue University West Lafayette
Aniket Kate, Purdue University West Lafayette
Michael Reiter, Duke University
Abstract

Most existing Byzantine fault-tolerant State Machine Replication (SMR) protocols rely explicitly on either equivocation detection or quorum certificate formations to ensure protocol safety. These mechanisms inherently require $O(n^2)$ communication overhead among $n$ participating servers. This work proposes the Unique Chain Rule (UCR), a simple rule for hash chains where extending a block by including its hash in the next block, is treated as a vote for the proposed block \textit{and its ancestors}. When a block obtains a vote from at least one correct server, we can commit the block and its ancestors. While this idea was used implicitly earlier in conjunction with equivocation detection or quorum certificate generation, this work employs it explicitly to show safety. We present three applications of UCR.\@ We design \emph{Apollo}, and \emph{Artemis}: two novel synchronous SMR protocols with linear best-case communication complexity using round-robin, and stable leaders, respectively as the first two applications. Next, we employ UCR in a black-box fashion toward making any SMR commits publicly verifiable, where clients will no longer have to wait for $2f+1$ confirmations on every block, where $\kappa$ is a security parameter and $f$ is the number of Byzantine faults tolerated by the protocol, but can instead collect a UCR proof consisting of $\min({\kappa, f)}+1$ extensions on a block. This results in faster syncing times for clients as the publicly verifiable proofs can also be gossiped with every new block extension confirming a new block.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. FC 2023
Keywords
Distributed computingblockchainsconsensus protocolsSMRSynchrony
Contact author(s)
abhatk @ purdue edu
abandaru @ purdue edu
sbagchi @ purdue edu
aniket @ purdue edu
Michael reiter @ duke edu
History
2023-05-01: revised
2021-02-20: received
See all versions
Short URL
https://ia.cr/2021/180
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/180,
      author = {Adithya Bhat and Akhil Bandarupalli and Saurabh Bagchi and Aniket Kate and Michael Reiter},
      title = {Unique Chain Rule and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/180},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/180}},
      url = {https://eprint.iacr.org/2021/180}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.