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

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.

Available format(s)
Publication info
Published elsewhere. FC 2023
Distributed computingblockchainsconsensus protocolsSMRSynchrony
Contact author(s)
abhatk @ purdue edu
abandaru @ purdue edu
sbagchi @ purdue edu
aniket @ purdue edu
Michael reiter @ duke edu
2023-05-01: revised
2021-02-20: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.