Afgjort - A Semi-Synchronous Finality Layer for Blockchains

Thomas Dinsdale-Young, Bernardo Magri, Christian Matt, Jesper Buus Nielsen, Daniel Tschudi
Afgjort - A Semi-Synchronous Finality Layer for Blockchains
Security and Cryptography for Networks. SCN 2020, 12238 :24–44, 2020.

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 we ran with an implementation of our protocol. The experiments confirm that finality is reached much faster than without a finality layer.

DOI PDF