Longest-chain blockchain protocols, such as Bitcoin, guarantee liveness even when the number of actively participating users is variable, i.e., they are adaptive. However, they are not safe under network partitions, i.e., they do not guarantee finality. On the other hand, classical blockchain protocols, like PBFT, achieve finality but not adaptivity. Indeed, the CAP theorem in the context of blockchains asserts that no protocol can simultaneously offer both adaptivity and finality. We propose a new blockchain protocol, called the checkpointed longest chain, that offers individual users the choice between finality and adaptivity instead of imposing it at a system-wide level. This protocol’s salient feature is that it supports two distinct confirmation rules: one that guarantees adaptivity and the other finality. The more optimistic adaptive rule always confirms blocks that are marked as finalized by the more conservative rule, and may possibly confirm more blocks during variable participation levels. Clients (users) make a local choice between the confirmation rules as per their personal preference, while miners follow a fixed block proposal rule that is consistent with both confirmation rules. The proposed protocol has the additional benefit of intrinsic validity: the finalized blocks always lie on a single blockchain, and therefore miners can attest to the validity of transactions while proposing blocks. Our protocol builds on the notion of a finality gadget, a popular technique for adding finality to longest-chain protocols.

This research is supported in part by a gift from IOHK Inc., an Army Research Office grant W911NF1810332 and by the National Science Foundation under grants CCF 17-05007 and CCF 19-00636.

Authors and Affiliations

1. University of Illinois, Urbana-Champaign, IL, 61801, USA

   Suryanarayana Sankagiri, Xuechao Wang & Pramod Viswanath

2. University of Washington at Seattle, Seattle, WA, USA

   Sreeram Kannan

Corresponding author

Correspondence toSuryanarayana Sankagiri.

Editors and Affiliations

1. University of Illinois at Urbana-Champaign, Urbana, IL, USA

   Nikita Borisov

2. KU Leuven, Leuven, Belgium

   Claudia Diaz

Appendix

A Algorand BA is a Checkpointing Protocol

We outline the full Algorand Byzantine Agreement (BA) protocol below for completeness. A minor modification (marked in red), adding validation, is the only addition to the original protocol. Honest checkpointers run a multi-iteration BA to commit checkpoints. The goal of thei-th iteration is to achieve consensus on thei-th checkpoint. Each iteration is divided into multiple periods and view changes will happen across periods.

All checkpointers start period 1 of iteration 1 at the same time (time 0). Checkpointeri starts period 1 of iterationn after it receives\(2t + 1\) cert-votes for some valuev for the same periodp of iteration\(n-1\) and waits for another fixed timee, and only if it has not yet started an iteration\(n' > n\). Checkpointeri starts period\(p \ge 2\) of iterationn after it receives\(2t + 1\) next-votes for some valuev for period\(p - 1\) of iterationn, and only if it has not yet started a period\(p' > p\) for the same iterationn, or some iteration\(n' > n\). For any iterationn, checkpointeri sets its starting value for period\(p \ge 2\),\(st^p_i\), tov (the value for which\(2t+1\) next-votes were received and based on which the new period was started). For\(p = 1\),\(st^1_i = \perp \). The moment checkpointeri starts periodp of iterationn, he finishes all previous periods and iterations and resets a local timer\({clock}_i\) to 0. At the beginning of every period, every honest checkpointeri sets\(v_i\) to be the checkpointed longest chain in its view at that time.

Each period has a unique leader known to all checkpointers. The leader is assigned in an i.i.d. fashion by the permitter oracleO. Each checkpointeri keeps a timer\({clock}_i\) which it resets to 0 every time it starts a new period. As long asi remains in the same period,\({clock}_i\) keeps counting. Recall that we assume the checkpointers’ individual timers have the same speed. In each period, an honest checkpointer executes the following instructions step by step.

Step 1: [Value Proposal by leader]. The leader of the period does the following when\({clock}_i = 0\); the rest do nothing. If\((p = 1)\) OR\(((p \ge 2)\) AND (the leader has received\(2t + 1\) next-votes for\(\perp \) for period\(p - 1\) of iterationn)), then it proposes its value\(v_i\). Else if\(((p \ge 2)\) AND (the leader has received\(2t + 1\) next-votes for some value\(v \ne \perp \) for period\(p - 1\) of iterationn)), then the leader proposesv.

Step 2: [The Filtering Step]. Checkpointeri does the following when\({clock}_i = 2\varDelta \). If\((p = 1)\) OR\(((p \ge 2)\) AND (i has received\(2t + 1\) next-votes for\(\perp \) for period\(p - 1\) of iterationn)), theni soft-votes the valuev proposed by the leader of current period. Else if\(((p \ge 2)\) AND (i has received\(2t + 1\) next-votes for some value\(v \ne \perp \) for period\(p - 1\) of iterationn)), theni soft-votesv.

Step 3: [The Certifying Step]. Checkpointeri does the following when\({clock}_i \in (2\varDelta ,4\varDelta )\). Ifi sees\(2t + 1\) soft-votes for some value\(v \ne \perp \), theni cert-votes v.

Step 4: [The Period’s First Finishing Step]. Checkpointeri does the following when\({clock}_i = 4\varDelta \). Ifi has certified some valuev for periodp, he next-votesv. Else if (\((p \ge 2)\) AND (i has seen\(2t+1\) next-votes for\(\perp \) for period\(p-1\) of iterationn)), he next-votes\(\perp \). Else he next-votes his starting value\(st^p_i\).

Step 5: [The Period’s Second Finishing Step]. Checkpointeri does the following when\({clock}_i \in (4\varDelta ,\infty )\) until he is able to finish periodp. Ifi sees\(2t + 1\) soft-votes for some value\(v\ne \perp \) for periodp, theni next-votesv. If\(( (p \ge 2)\) AND (i sees\(2t + 1\) next-votes for\(\perp \) for period\(p-1\)) AND (i has not certified in periodp)), theni next-votes\(\perp \).

Halting condition: Checkpointeri HALTS current iteration if he sees\(2t+1\) cert-votes for some valuev for the same periodp, and setsv to be his output. Those cert-votes form a certificate forv. The block that is exactlyk-deep inv is chosen as the checkpoint in current iteration.

A proposed valuev (with blockB being exactlyk-deep in it) from periodp of iterationn is VALID for checkpointeri (in the same period and iteration) if:

• Valuev is proposed by the leader of that period;

• BlockB is a descendant of all previously checkpointed blocks with smaller iteration number;

• BlockB is contained in the checkpointed longest chain that the checkpointeri holds when entering periodp.

The only modification to the protocol is in Step 2, in the first condition, where the notion of validity is introduced. This is the only place where new proposals are considered. The validity notion helps transform the Algorand BA protocol into the multi-iteration checkpointing protocol that we desire. In Appendix B (see full version [23]), we show that this protocol indeed satisfies propertiesCP0–CP3, as mentioned in Sect. 4.

Reprints and permissions

© 2021 International Financial Cryptography Association

Policies and ethics