Blockchain CAP Theorem Allows User-Dependent Adaptivity and Finality

Abstract

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.

S. Sankagiri and X. Wang—Equal contribution.

Appendices

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 the i-th iteration is to achieve consensus on the i-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). Checkpointer i starts period 1 of iteration n after it receives $2t + 1$ cert-votes for some value v for the same period p of iteration $n-1$ and waits for another fixed time e, and only if it has not yet started an iteration $n' > n$. Checkpointer i starts period $p \ge 2$ of iteration n after it receives $2t + 1$ next-votes for some value v for period $p - 1$ of iteration n, and only if it has not yet started a period $p' > p$ for the same iteration n, or some iteration $n' > n$. For any iteration n, checkpointer i sets its starting value for period $p \ge 2$, $st^p_i$, to v (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 checkpointer i starts period p of iteration n, he finishes all previous periods and iterations and resets a local timer ${clock}_i$ to 0. At the beginning of every period, every honest checkpointer i 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 oracle O. Each checkpointer i keeps a timer ${clock}_i$ which it resets to 0 every time it starts a new period. As long as i 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 iteration n)), 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 iteration n)), then the leader proposes v.

Step 2: [The Filtering Step]. Checkpointer i 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 iteration n)), then i soft-votes the value v 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 iteration n)), then i soft-votes v.

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

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

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

Halting condition: Checkpointer i HALTS current iteration if he sees $2t+1$ cert-votes for some value v for the same period p, and sets v to be his output. Those cert-votes form a certificate for v. The block that is exactly k-deep in v is chosen as the checkpoint in current iteration.

A proposed value v (with block B being exactly k-deep in it) from period p of iteration n is VALID for checkpointer i (in the same period and iteration) if:

• Value v is proposed by the leader of that period;

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

• Block B is contained in the checkpointed longest chain that the checkpointer i holds when entering period p.

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 properties CP0–CP3, as mentioned in Sect. 4.