Cryptology ePrint Archive: Report 2019/504

Afgjort: A Partially Synchronous Finality Layer for Blockchains

Thomas Dinsdale-Young and Bernardo Magri and Christian Matt and 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.

Category / Keywords: cryptographic protocols / blockchain, finality, Byzantine agreement

Original Publication (with major differences): Proceedings of the 12th Conference on Security and Cryptography for Networks (SCN 2020)
DOI:
10.1007/978-3-030-57990-6_2

Date: received 15 May 2019, last revised 17 Nov 2020

Contact author: ty at concordium com, magri at cs au dk, cm at concordium com, jbn at cs au dk, dt at concordium com

Available format(s): PDF | BibTeX Citation

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

Version: 20201117:203718 (All versions of this report)

Short URL: ia.cr/2019/504


[ Cryptology ePrint archive ]