Finality in the Concordium Blockchain
Achieving finality in blockchain protocols is a challenging issue that has recently become the focus of major research efforts. In this article, we first explain the issue of finality and then discuss how Concordium has tackled the challenge of building an efficient and scalable blockchain with strong finality guarantees. Besides the Concordium’s finality layer, we also introduce the exciting new feature of Finality as a Service (FaaS), which will allow third-party decentralized applications to benefit from Concordium’s strong finality guarantees.
From Byzantine Agreement to Blockchains
Blockchain systems introduced a clever new way to solve a variation of an old problem: Byzantine Agreement [LSP82]. In its classical form, this problem states that three generals from the Byzantine Empire who are physically separated and can only communicate through unreliable horse-riding messengers must agree on whether they will attack the enemy or not.
However, one of the generals is malicious and will try to confuse the other two. It turns out that this problem is impossible to solve in its original form since it can only be solved if strictly less than a third of the generals is malicious but in this formulation exactly one-third acts maliciously [FLP83].
Imagine, however, that we substitute the honest generals for larger groups of users running software, the horse-riding messenger for internet connections, the malicious general for a malicious user and the “attack or no attack” message for complex transactions. In this modern setting, we face the problem of allowing the users to communicate through the internet to agree on a complex piece of information even if a malicious user attempts to confuse them. Since the first breakthrough by Lamport and Shostak in the 1980s [SL80], this problem has been solved in many different ways through so-called Byzantine agreement protocols (or consensus protocols). Such protocols are a sequence of instructions on how the users’ software must communicate in order to ensure that all honest users agree on the same information regardless of the malicious users’ actions.
The goal of a blockchain-based consensus protocol is to allow users to create a blockchain structure where they can read and write information with the guarantee that written information eventually becomes immutable, agreed upon and accessible by all users.
Moreover, a blockchain protocol allows a large number of users to participate at any time in reading and writing information or even in maintaining the blockchain itself without the need for previous registration or authorization from a central entity. In other words, blockchain systems are scalable and permissionless, standing out in comparison to traditional permissioned Byzantine agreement protocols, which can only efficiently support a small number of users and rely on all of them knowing each other’s identities (or even public encryption keys) in advance. Moreover, traditional Byzantine agreement protocols guarantee no security if a third or more of the users are malicious [FLP83], while most blockchain protocols ensure security even if less than half of the users are malicious [GKL15] (or rather, less than half of the resources needed to execute the protocol are controlled by malicious users).
The Finality Issue
Security against stronger malicious behavior, scalability, and support for the permissionless setting come at a cost: honest users in a blockchain protocol only eventually achieve a partial guarantee that a given piece of information has been agreed upon and has become immutable. In contrast to traditional Byzantine agreement protocols where the participants have 100% assurance that they have agreed on some information as soon as the protocol is finished, blockchain protocols are continuously executed as more blocks containing new information are added on top of each other in order to form the blockchain structure.
As the protocol is executed and more blocks are added to the chain, the protocol gives a stronger (but never absolute) guarantee that older blocks located deeper back in the chain seen by honest users are indeed immutable. This guarantee is usually referred to as eventual consensus.
While executing a blockchain protocol among honest users would yield a single valid blockchain structure, malicious users can temporarily create “forks”. A fork happens when a malicious user (or even an accidental network communication error) makes different honest users see two or more different versions of the chain starting from a common sequence of blocks but diverging after a certain block.
When a fork happens, the protocol guarantees that eventually, all honest users will again start seeing (and agreeing upon) a single version of the chain, while the other alternative versions are discarded. Moreover, blockchain protocols guarantee that when a certain number of blocks (or more) are added after a given block, there’s very little chance that this block is part of a fork that will be discarded.
This means that the more blocks are built on top of a given block, the highest chance that this block will become immutable.
Unfortunately, this state of affairs introduces two issues in blockchain protocols:
- There is always a chance that a block is a part of a fork that will be discarded (causing the block’s information to be lost)
- In order to make this chance very small, users need to wait for a long time after this piece of information is included in a block (so that enough new blocks are added to the chain).
For example, in the Bitcoin system, the rule of thumb is that blocks are considered immutable when 6 new blocks are added after them. In blockchain lingo, a block that is considered immutable is called “finalized” and the transactions (or data) contained in such a block are called “confirmed”.
However, regular blockchain protocols are not able to guarantee that a block is finalized with 100% certainty since there is always a chance that this block might be part of a fork that will be discarded.
Additionally, in order to safely conduct financial transactions, a user must wait for a long time after a transaction is included in a block before it can be considered confirmed, which is necessary for avoiding double-spending.
Achieving Finality with Afgjort
In order to address the finality issue, members of the Concordium team led by Professor Jesper Buus Nielsen of the Concordium Blockchain Research Center Aarhus (COBRA) have designed Afgjort (pronounced ow-gui-ort), a new finality layer that ensures that blocks become quickly finalized with 100% certainty. Named after the Danish expression for “agreed upon”, Afgjort [DMM+19] has been formally analyzed and proven secure, meaning that there is a mathematical proof that Afgjort achieves the desired finality guarantees.
Moreover, this finality layer can be added on top of any blockchain protocol that satisfies the basic blockchain properties similar to those of Bitcoin [GKL15]. In particular, Afgjort is also compatible with efficient Proof-of-Stake (PoS) based blockchain protocols such as Ouroboros Praos [DGKR18], adding strong finalization guarantees and improved performance to these protocols so that they can serve as a solid basis for the Concordium blockchain.
As many consensus protocols, Afgjort is a protocol executed by a committee of users randomly selected among all users of the system.
This committee constantly observes the blockchain maintained by all the users of the underlying blockchain protocol and, from time to time, finalizes a block.
In order to finalize a block, the users in the committee communicate among each other employing a number of new tricks and techniques from a traditional Byzantine agreement in order to agree upon which block will be finalized.
When they reach an agreement on which block to be finalized, the users in the committee have 100% certainty that they all agree on the same block. In this process, they also write a small amount of information to the blockchain, allowing the other users who are not part of the committee to verify that the whole committee has agreed that a certain block has been finalized with 100% certainty.
After the finalization process is over, the users in the committee wait for more new blocks to be added to the chain and repeat the process for one of these new blocks.
Once a block is considered finalized by the Afgjort committee, all other users running the underlying blockchain protocol can verify that this block was indeed finalized and consider it finalized themselves.
Considering a block finalized has the important consequence that all other alternative forks that might have occurred between the last finalized block and the new finalized block are automatically discarded, leaving only one remaining valid chain reaching the new finalized block.
In turn, all the blocks that appear in the chain before the new finalized block are also considered finalized, since there is 100% certainty that all other alternative forks have been discarded. This mechanism allows Afgjort to quickly finalize many blocks by performing the finalization process for a single block, which makes it very efficient.
Differently from usual blockchain protocols, Afgjort provides finality with 100% certainty as in traditional Byzantine agreement protocols, a task that requires a committee where less than one-third of the users are corrupted [FLP83].
Since Afgjort runs as a finality layer on top of an existing blockchain protocol, it requires that less than a third of the resources (for example stake) in this blockchain protocol to be controlled by malicious users (so that the committee can be selected in a permissionless way).
Notice, however, that the underlying blockchain protocol still keeps its usual security guarantees even if almost a half of the resources are controlled by malicious users, since the higher number of malicious users affects only the extra finality guarantees provided by Afgjort. This means that the blockchain will still achieve eventual consensus and ensure that previous finalized blocks remain immutable even if malicious users assume control of more than a third of the stake in an underlying PoS blockchain protocol.
Finality as a Service (FaaS)
It is certainly a major challenge to engineer a high assurance implementation of a finality layer such as Afgjort and execute it over a blockchain protocol with a large enough user base (and a proper stake distribution) guaranteeing that less than one-third of the committee is malicious.
While Concordium’s engineering team is tackling this challenge, our researchers are already hard at work on one of the most innovative features of the Concordium blockchain: Finality as a Service (FaaS). Concordium’s FaaS will make strong finality guarantees accessible to third party decentralized applications without the need for their users (or operators) to execute Afgjort.
Concordium’s FaaS will allow third-party applications to submit data to be finalized by Afgjort running on Concordium’s blockchain. For example, a third-party blockchain protocol can submit block hashes to have its own blocks finalized by Concordium’s FaaS.
Alternatively, a mission-critical third-party smart contract conducting high valued financial transactions can submit transaction data and smart contract states for FaaS finalization.
Once these data are finalized by FaaS, they enjoy the same strong finality guarantees provided by the Concordium blockchain itself. More importantly, it does not matter that the third party application has a small user base or that it cannot guarantee the selection of a committee with less than a-third malicious users since the finality guarantees of FaaS will be provided by Afgjort being executed with the full resources of the Concordium network.
References
[SL80] Reaching Agreement in the Presence of Faults. Marshall C. Pease, Robert E. Shostak, Leslie Lamport. J. ACM 27, 1980.
[LSP82] The Byzantine Generals Problem. Leslie Lamport, Robert E. Shostak, Marshall C. Pease. ACM Trans. Program. Lang. Syst. 4, 1982.
[FLP83] Impossibility of Distributed Consensus with One Faulty Process. Michael J. Fischer, Nancy A. Lynch, Mike Paterson. PODS 1983.
[GKL15] The Bitcoin Backbone Protocol: Analysis and Applications. Juan A. Garay, Aggelos Kiayias, Nikos Leonardos. EUROCRYPT 2015.
[DGKR18] Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain. Bernardo David, Peter Gazi, Aggelos Kiayias, Alexander Russell. EUROCRYPT 2018.
[DMM+19] Afgjort: A Partially Synchronous Finality Layer for Blockchains. Thomas Dinsdale-Young, Bernardo Magri, Christian Matt, Jesper Buus Nielsen, Daniel Tschudi. https://eprint.iacr.org/2019/504
Join #TeamConcordium in our different channels:
Twitter: https://twitter.com/ConcordiumNet
Telegram: https://t.me/concordium_official
Reddit: https://www.reddit.com/r/Concordium_Official
Developers Hub: https://developers.concordium.com/tech
Gitter: https://gitter.im/concordium_official/community
Discord: https://discord.gg/xWmQ5tp
Learn more: https://concordium.com
