Optimal Multilevel Slashing for Blockchains

Blockchains are distributed systems with the task of (i) collecting concurrent transactions that originate from its users; (ii) order these transactions into a history, which is often expressed as a linear sequence of blocks, with each block containing an internal sequence of transactions; and (iii) maintain such history stored into a permanent, distributed ledger that reflects a global system state given the history. The ledger state could represent monetary balances or even the state of replicated programs (smart contracts) that execute in a virtual machine collectively simulated by participant nodes [26, 6, 33, 16, 2, 19]. Throughout this paper, we may refer to participant nodes, processes, and blockchain validators interchangeably.

Deciding how to group transactions into blocks and how to order blocks into the blockchain ledger is an application of Byzantine consensus, typically with some other properties and requirements in place, including: (i) participants always use digital signatures when they interact with the system; (ii) participation is dynamic, meaning that nodes join and leave the system at undetermined times; and (iii) in certain cases, participation is permissionless, meaning that certain system actions (say, performing transactions or even participating in the consensus itself) require no previous global registration or identity-based approval. For example, Bitcoin participation is permissionless as any node that can produce a token demonstrating the completion of a certain computationally-expensive hashing task is allowed to participate in the consensus protocol, regardless of that node’s identity. This is called a proof-of-work blockchain. Note that any two nodes could produce the tokens mentioned above roughly at the same time, so the ledger can fork during the system execution, and participants then heuristically define the longest chain of blocks as the authoritative one. In contrast, systems such as [6, 33, 16, 2, 19] work overall as follows. Discrete time slots are defined, each associated with a committee of participants. At each slot, the corresponding committee produces or acknowledges the next block of transactions by having some well-defined fraction of its participants to attest – that is, vote – for such next block. If a Byzantine committee participant votes for two conflicting blocks (on different branches), which is prohibited by the voting mechanics, the participant is subject to slashing: the participant’s pre-deposited assets (called its stake) are penalized, and the deducted penalty is distributed to other participants in the system. Having such pre-deposited assets is a prerequisite for participating in committees (and thus in the consensus protocol), and slashing is the incentive for nodes to behave correctly. This setting characterizes a proof-of-stake blockchain.

An operational advantage of using committees rather than having a global vote procedure is that committees can initially restrict expensive communication primitives [37, 4, 7] to its own participants, and later generate a compact committee signature that indicates internal agreement on a certain next block $v$ (say, using a threshold signature scheme such as [3, 36]). Those compact committee signatures can then be communicated globally with the intention to reach global consensus on $v$.

Just as in proof-of-work systems, the ledger in proof-of-stake systems can also fork because committees can be temporarily or permanently isolated from the network due to technical outages, making attestations arrive asynchronously in different parts of the network, and thus creating multiple descendants of a given block. Hence, it is common to have a heuristic-based fork-choice rule that constantly defines the “best chain” of ongoing operations¹¹1Just like Bitcoin does, except that Bitcoin’s heuristic is simply defined as the longest chain., along with a separate finalization gadget, which chooses one unique, canonical chain to be “final” [29, 5, 38]. The blockchain literature often refers to the fork-choice’s “best chain” as the available chain, because its relatively simple heuristics allow applications to identify it quickly, thus settle quickly on the current state of the system. That is in contrast with what is often referred as the final chain, which has been subject to the finalization gadget, and often depends on partially-synchronous assumptions for progress ([9, 40] among many others).

The problem we solve is that blockchain applications often need to know whether a transaction is “confirmed” (perhaps to settle a sale), which requires (a) observing a ledger block that includes such transaction; and (b) obtaining some guarantee that this block will be finalized later. However, currently, applications can either (i) quickly identify the transaction in the available chain, but have no guarantees that this chain will eventually be finalized; or (ii) slowly identify the transaction in the finalized chain, but be subject to an infeasible wait time that might completely break the application’s functional requirements (user satisfaction, quick response to financial events, etc).

Our solution creates a “sliding window” in the latency-trust spectrum in settling transactions, and the applications can tradeoff speed and certainty according to their very particular functional requirements. In other words, applications will not only have the fork-choice rule (a temporary “accounting mechanism”) or the finalization event (the permanent but slowly-moving global consensus) to deem that a particular block (or a particular transaction therein) is “confirmed”. Specifically, we create a distributed mechanism where increasing levels of trust can be obtained at increasing latency costs by querying other participant nodes as well as passively observing network events. Importantly, our design does not introduce any central control or “hotspots”, as it is defined using the highly symmetrical mathematical structure of projective spaces over finite fields.

In essence, our construction can be interpreted as an intermediary, flexible trust phase between the initial attestation tallying and the finalization. In this phase, a participant can obtain information from multiple sets of validators – which we call quorums – indicating that a block $v$ is about to be finalized. If another participant obtains the same information for a different block $v^{\prime }$, the intersection property of our structural construction will result in a significant amount of funds being slashed from the adversary. Importantly, we give the applications the flexibility to choose the balance of trust and potential adversarial slashing with our construction.

We note that this functionality, if further integrated into a blockchain system, can also be seen as (i) a form of an early, slashing-based block finalization, as the block confirmation guarantees are now much more continuous between the quick, yet unreliable, fork-choice rule and the slow, yet reliable, finalization; or (ii) a service for reorg tolerance. Reorgs [35, 30] are situations where applications consider some chain $v$ as the logical continuation of the blockchain ledger because a fraction of nodes attest $v$, but later are forced to consider $v^{\prime }$ as such because a (typically larger) fraction of nodes became visible while attesting $v^{\prime }$. In our system, once applications obtain a certain number of levels of assurance that $v$ is the next block to be finalized, a different block $v^{\prime }$ that takes its place will incur significant adversarial slashing, optimal with respect to the magnitude of assurance levels originally obtained.

Our technical contributions are described below at a high level, but with pointers to the sections where we present our concrete constructions and proofs.

1. 1.

   We design a distributed architecture to support multilevel slashing by applying projective spaces over finite fields to committee-based consensus (Section 3), a generalization of a previous approach that only used projective planes [32] in a context where slashing was irrelevant.

2. 2.

   We define and analyze slashability – the relation of the query size/time and the magnitude of slashing associated with a level of trust. In particular, we show that our construction is optimal with respect to worst-case message complexity and validator load, demonstrating a fundamental trade off between slashability, message complexity, and load (Section 4).

3. 3.

   We prove that a general class of similarly-designed intersection systems based on disjoint subsets of elements achieve asymptotic high availability under reasonable conditions (Section 5).

Our construction creates an intersection pattern among sets of blockchain nodes in a manner that is reminiscent of quorum systems [27, 23, 24, 8, 14] (among others, discussed in Section 6), but our purpose – and design – are not the same. Specifically, the mathematical intersections among sets of nodes intentionally uses a projective-space-based construction in order to define an additional level of transaction confirmation on top of existing blockchains that follow the availability-finality paradigm of [29]. We note that obtaining the higher-dimensional structures used to define our quorums is expensive, but can be done a priori for reasonable parameters, and later mapped to a running system, which we consider viable in practice. We discuss some practical scenarios in Section 3.

In addition to the core technical sections pointed to above, we include background on intersection systems and projective spaces in Section 2; we present our system design concretely in Section 3; we discuss related work in Section 6; and we conclude with final remarks in Section 7.

In this section, we present basic definitions on intersection systems and projective spaces over finite fields, used in our intersection system construction, provided in Section 3. In this paper we use the following standard combinatorial notation: for a positive integer $m$, we denote by $[m]$ the set $\{1,\mathrm{\dots },m\}$. For probability computations, $𝐏(A)$ denotes the probability of an event $A$ and $𝐄X$ denotes an expectation of a random variable $X$.

Consider a system of $n$ processes $\mathbb{P}=\{P_1,\mathrm{\dots },P_n\}$. We assume that processes are non-faulty independently with probability $p$ (and faulty with probability $1-p$); similar failure models have been used in [27, 32]. For practical applications, we use values $p$ of the form $\frac{2}{3}+ϵ$ for a small $ϵ$, so that the probability that at least $1/3$ of nodes display Byzantine behavior is negligible (so basic network primitives such as [4, 37] work). We assume authenticated channels, that is, every message sent has a digital signature for which it is computationally infeasible for an adversary to forge.

We now describe a multilevel intersection system where, each level has an intersection system of its own with ground set composed of committees in $\mathbb{P}$. Obtaining a quorum asserting block $v$ within each level will increase the assurance that a $v$ is bound to be finalized in the global consensus – that is, increase the associated slashing in case $v$ is not finalized. We do this while allowing small quorums relative to system size (thus less communication complexity) and very high slashing relative to the size of the quorums. Our system also ensures a small load, as every committee is in the same number of quorums and no committee is particularly over-represented. Our construction is defined as follows.

1. 1.

   Assume a set-up procedure to generate $|\mathrm{PG}(k,q)|$ committees that equitably partition²²2An equitable partition of a finite set $S$ is a partition of $S$ such that the sizes of the sets in the partition differ by at most 1. the set of processes $\mathbb{P}$, where $k\ge 0$ is an integer and $q$ is a prime power such that $n\ge |\mathrm{PG}(k,q)|$. Note that when $q$ is a prime power, this is always well-defined. Denote the set of these committees by $𝒞$, so that $|𝒞|=|\mathrm{PG}(k,q)|$.

2. 2.

   Next, define a one-to-one correspondence $\mathrm{com}:\mathrm{PG}(k,q)\to 𝒞$, and two weakly increasing sequences with length $\mathrm{\ell }$, the total number of levels:

   • $\mathrm{■}$

     ${(d_j)}_{j\in [\mathrm{\ell }]}$ of integers in $(\frac{k}{2},k)$;

   • $\mathrm{■}$

     ${(r_j)}_{j\in [\mathrm{\ell }]}$ of real numbers in $(\frac{1}{2},p)$.

3. 3.

   For each level $j\in [\mathrm{\ell }]$, the $j$th level committee intersection system is defined to be

   $${\mathbb{Q}}_j=\{\mathrm{com}(S):S\in {\mathrm{PG}}_{d_j}(k,q)\}.$$

4. 4.

   Finally, for all $j\in [\mathrm{\ell }]$, the $j$th level process intersection system is defined as

   $${𝒬}_j={\mathbb{P}}_{r_j}({\mathbb{Q}}_j).$$

Notice that each ${\mathbb{Q}}_j$ is indeed an intersection system as ${\mathrm{PG}}_{d_j}(k,q)$ is an intersection system by Corollary 13. In addition, observe that for all , every quorum in ${𝒬}_j$ contains a quorum in ${𝒬}_i$; since every $d_j$-dimensional projective subspace of $\mathrm{PG}(k,q)$ contains a $d_i$-dimensional projective subspace (this follows from $d_1\le d_2\mathrm{\cdots }\le d_{\mathrm{\ell }}$). Thus, we say that a process trusts a block $v$ with $j$ degrees of assurance if that process obtains a quorum accepting $v$ from ${𝒬}_j$.

In this section, we show that our intersection system ${𝒬}_j$ has asymptotically optimal slashability, over a general class of intersection systems constructed from committees. We prove a formalization of the following: The slashability of the $j$th-level intersection system ${𝒬}_j={\mathbb{P}}_{r_j}({\mathbb{Q}}_j)$ is asymptotically optimal over all intersection systems built with the same set of committees and the same threshold $(r_j)$ with at least as good overall message complexity and load, allowing a certain trade off between the two quantities.

The proof of the statement above is given in Theorem 20, following some useful lemmas. First, let us compute the size of the quorums in ${\mathbb{Q}}_j$ and the slashability of ${𝒬}_j$.

Consider the system with parameters as above, all viewed as a function of the number of processes $n$. Fix some $j\in [\mathrm{\ell }]$ (also a function of $n$). For a more formalized treatment of asymptotic notations as in this section, see Section 5. Given functions $f$ and $g$ from $\mathbb{N}$ to $ℝ$, we say $f$ and $g$ are asymptotically equivalent, written $f\sim g$, if ${lim}_{n\to \mathrm{\infty }}\frac{f(n)}{g(n)}=1$.

These first two lemmas compute $\mathrm{msg}({\mathbb{Q}}_j)$ and $\mathrm{slash}({\mathbb{Q}}_j)$.

In this section we demonstrate that under only mild assumptions, any multilevel intersection system that generalizes our approach has an asymptotically high availability (including the case when the number of levels is 1). We consider the results of this section relevant on their own, thus the results will be presented with a more general notation (from Section 2), rather than relying on specific notation from of our concrete construction in Section 3. With inspiration from some proof ideas seen in [32], we prove a formalized version of the following: Suppose processes are available with probability $p$. Suppose $𝒞$ is a partition of the processes into committees and $\mathbb{Q}$ is any intersection system with ground set $𝒞$. If and the smallest committee has size $\mathrm{\Omega }(\log n)$, then the intersection system ${\mathbb{P}}_r(\mathbb{Q})$ has availability converging to 1.

The formal statement and proof of this statement is concluded in Corollary 24, following some useful lemmas below. Lets start by formalizing our assumptions. For each $n\ge 1$, let ${𝒞}^n$ be a partition of an $n$-element set of processes, and let ${\mathbb{Q}}^n$ be an intersection system with ground set ${𝒞}^n$. Let $p$ be the probability a process is available in its steady-state, with $p>1/2$. For each $n\ge 1$, let $r_n\in (\frac{1}{2},p)$ so that ${(r_n)}_{n\in \mathbb{N}}$ is weakly increasing and .⁵⁵5Note that the $r$’s presented in this section are not related to the $\mathrm{\ell }$ different $r$-values used to define our multilevel intersection system in Section 3. Finally, define $c_n={\min }_{C\in {𝒞}^n}|C|$; that is, $c_n$ the smallest size of any set within the partition ${𝒞}^n$ (that, more generally, models committees).

Now let us bound the probability that a committee of size $c$ does not have at least $rc$ available processes. Denote this probability by $F_p(c;r)$. Define the function $a_1(x)=\frac{{(p-x)}^2}{2-p-x}$ for $x\in [0,r]$.

It is common practice [6, 33, 16, 2, 19] for proof-of-stake blockchains to employ fork-choice rules in order to define an available chain, and rely in an additional “finalization gadget” to execute global consensus. In particular, we note the role of Casper in Ethereum [5], and point to a well-documented conceptual separation of available vs. final chains in [29]. The later paper also points to the fact that this separation, besides practical, is also more general in the sense that a diverse set of consensus algorithms [9, 40, 10] (among others) could be applicable. Reorg attacks [35, 30] are also related to our work as our multilevel construction can precisely quantify a lower bound on slashing if a reorg were to take place – so our work could be seen as a tool to mitigate the functional effects of reorgs.

As noted in the introduction, our work is reminiscent to (and certainly it is inspired by) previous work in quorum systems. Quorum systems are set structures whose elements are typically distributed processes (say, servers in a distributed system), so that any two such sets (called quorums) intersect in at least one process. The idea is that applications can obtain an acknowledgment of an operation from all members of a chosen quorum, so that any two such acknowledgements are consistent, due to the intersecting property. Quorum systems have been studied extensively [27, 24, 15], with applications to consensus [25], database synchronization [1], finite-state-machine replication [17], mutual exclusion [22], among many others.

We are interested in some crucial metrics, such as server load and system availability, that are also found in the extensive literature of quorum systems, for example in [27, 31]. We note that quorum system design is also quite diverse, being highly impacted by its target applications. For abstract-data-type replication, ADT-specific information can play a role [17, 18]. Another interesting application showing high impact on quorum design is federated Byzantine consensus: in this case, non-uniform quorum systems, where each participant has its own notion of membership, are studied in [15], with ideas originating from practical systems such as the Stellar consensus protocol [25]. An additional important considerations for quorum design are whether the system allows dynamic participation [28, 8].

Block designs are well-studied structures in combinatorics [12] which provide a rich family of parameterized quorum systems [13]. A well-known family of block designs corresponds to finite projective planes and their respective quorum systems. One of its earliest applications in distributed systems is an algorithm that uses $O(\sqrt{n})$ messages to create mutual exclusion in a network, where $n$ is the number or nodes [22]. Although finite projective planes that yield small quorums are desirable due to reduction in communication complexity, asymptotically their availability goes to zero [32, 20]. However, a construction with finite projective planes where points are disjoint subsets that cover the ground set and quorums are achieved on an $r$ fraction of elements in the subsets yields asymptotic high availability [32]. A novel way of leveraging projective spaces in quorum systems for the in-network data storage paradigm is introduced and explored in [34, 21], where a 2D network is “lifted” onto a sphere using a projective map to enable more flexible quorums.

In this work, we propose an application of combinatorial designs using projective spaces over finite fields to provide gradual levels of consensus – that is, getting gradual assurance that a certain block is bound to be finalized in a global consensus procedure. We combine our design with a committee-based approach, in order to provide high availability. In fact, we prove not only that our construction is subject to high availability, but we show that any approach that uses our “sliding window” of obtaining attestations in the range strictly between $\frac{1}{2}$ and the individual process availability also forms a highly available intersection system. In addition, we demonstrate that our construction has optimal slashability – the extent we penalize an adversary’s assets upon protocol non-compliance – compared to other systems that operate under similar load and message complexity.

We consider the potential applicability of our system very exciting, as we envision that highly-connected participant nodes can even buy and sell “trust certificates” associated with assurances that a block is bound to be finalized. That is, nodes obtain collections of individual and threshold signatures that form multiple quorums, and then offer these trust certificates as insurance to blockchain applications.

Having a more gradual consensus – a “sliding window” of trust – can enable large improvements in blockchain usability, providing services such as early slashing-based finalization, reorg tolerance, and even supporting transaction insurance for reorgs. We are excited to spearhead initial theoretical work in this direction.