Afgjort: A Partially Synchronous Finality Layer for Blockchains

Thomas Dinsdale-Young; Bernardo Magri; Christian Matt; Jesper Buus Nielsen; Daniel Tschudi

Paper 2019/504

Afgjort: A Partially Synchronous Finality Layer for Blockchains

Thomas Dinsdale-Young, Bernardo Magri, Christian Matt, Jesper Buus Nielsen, and Daniel Tschudi

Abstract

Most existing blockchains either rely on a Nakamoto-style of consensus, where the chain can fork and produce rollbacks, or on a committee-based Byzantine fault tolerant (CBFT) consensus, where no rollbacks are possible. While the latter ones offer better consistency, the former tolerate more corruptions. To achieve the best of both worlds, we initiate the formal study of finality layers. Such a finality layer can be combined with a Nakamoto-style blockchain (NSB) and periodically declare blocks as final, preventing rollbacks beyond final blocks. As conceptual contributions, we formalize the concept of a finality layer and identify the following properties to be crucial for finality layers: finalized blocks form a chain (chain-forming), all parties agree on the finalized blocks (agreement), the last finalized block does not fall too far behind the last block in the underlying blockchain (updated), and all finalized blocks at some point have been on the chain adopted by honest parties holding at least $k$ units of the resource on which consensus is based, e.g., stake or computing power ($k$-support). As technical contributions, we propose two variants of a finality layer protocol we call Afgjort. The first variant satisfies all of the aforementioned requirements when combined with an arbitrary blockchain that satisfies the usual common-prefix, chain-growth, and chain-quality properties. The second one needs an additional, mild assumption on the underlying blockchain, but is more efficient and has higher support. For both variants, we prove these properties in the setting with less than $1/3$ corruption among the finalizers and a partially synchronous network. We further show that tolerating less than $1/3$ corruption is optimal for partially synchronous finality layers. Finally, we provide data from experiments ran with an implementation of our protocol; the data confirms that finality is reached much faster than without our finality layer.

Note: This is a major revision of the paper. We added experimental results and improved the overall presentation.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. Proceedings of the 12th Conference on Security and Cryptography for Networks (SCN 2020)
DOI: 10.1007/978-3-030-57990-6_2
Keywords: blockchain finality Byzantine agreement
Contact author(s): ty @ concordium com
magri @ cs au dk
cm @ concordium com
jbn @ cs au dk
dt @ concordium com
History: 2020-11-17: last of 5 revisions; 2019-05-20: received; See all versions
Short URL: https://ia.cr/2019/504
License: CC BY

BibTeX

@misc{cryptoeprint:2019/504,
      author = {Thomas Dinsdale-Young and Bernardo Magri and Christian Matt and Jesper Buus Nielsen and Daniel Tschudi},
      title = {Afgjort: A Partially Synchronous Finality Layer for Blockchains},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/504},
      year = {2019},
      doi = {10.1007/978-3-030-57990-6_2},
      url = {https://eprint.iacr.org/2019/504}
}