The Longest-Chain Protocol Under Random Delays

1. Introduction

Blockchains are peer-to-peer systems that maintain ever-growing ledgers. The first blockchain system to be proposed was Bitcoin (Nakamoto 2008), a peer-to-peer electronic payment system. Over the last decade, the basic idea behind Bitcoin has been generalized to many other systems. In all blockchain systems, the ledger is maintained in the form of a chain of blocks, with each block containing some ordered records. The term blockchain arises from this linked-list-like data structure. The parties (i.e., participants) engage in a consensus protocol to ensure that they maintain consistent copies of the ledger. Although the blockchain data structure itself has remained fairly standard, associated consensus protocols have proliferated (see Bano et al. (2019) and Garay and Kiayias (2020) for surveys on consensus protocols). The longest-chain protocol, also known as the Nakamoto consensus protocol, is one such popular consensus mechanism. It is the protocol being used by Bitcoin.

The longest-chain protocol has a simple description. At any point in time, each party stores a blockchain in its memory, which is the longest blockchain it has heard of up to that point. This blockchain is the party’s local copy of the ledger. Periodically, a party is elected as a leader via a randomized mechanism. The mechanism may be proof-of-work mining, as in Bitcoin, or some proof-of-stake mechanism, as in Ouroboros (Kiayias et al. 2017, David et al. 2018). In the former setting, a party’s chance of getting elected is proportional to its mining (computational) power; in the latter, it is proportional to the amount of wealth one has staked in the system. Once elected, a leader creates a new block at the end of its blockchain and broadcasts the block to other parties, who hear of (i.e., receive) the block after some delay. This process continues indefinitely, producing an ever growing chain of blocks. The protocol is said to be secure if all parties have consistent, ever-growing copies of the ledger at all times.

Blockchains, by virtue of being peer-to-peer systems, may be subject to security attacks from malicious parties. One possible attack is the double-spend attack, also known as the private attack, which proceeds as follows. Here, the attacker makes a payment to some merchant in exchange for a product or service and issues the transaction to the blockchain. It then secretly creates an alternate chain of blocks that forks from the publicly known one at a point before the transaction in question is recorded. If the attacker is successful in creating a longer chain than the public one, it will release its chain, and the alternate chain will be adopted by all parties. Effectively, the transaction is erased from the ledger and the attacker is free to spend its money elsewhere.

The double-spend attack was identified as a potential security threat by Nakamoto (2008) itself. To protect against this threat, the k-deep rule was proposed, which says that parties should treat a block as confirmed only when it has been buried below k blocks (or after k units of time has passed since the block’s creation). Assuming that the fraction of adversarial mining power is less than a half, the chance that the double-spend attack will succeed in erasing a k-deep block decreases exponentially with k (Nakamoto 2008). The intuition behind this result is the following: the adversary’s success boils down to whether it can overtake the honest, public chain with its own private chain. If the latter grows slower than the former on average, the adversary’s success chance decreases with time. Later works give a more detailed analysis of the success probability of the double-spend attack (Rosenfeld 2014, Goffard 2019).

The analysis of Nakamoto (2008) assumes that messages are delivered instantaneously. Upon factoring in network delays, it turns out that the adversary gets an additional advantage. As shown by Sompolinsky and Zohar (2015), the fraction of adversarial mining power required for the double-spend attack to be successful reduces as the network delay increases. This phenomenon can be understood as follows. If a leader does not hear of the previous block at the time it is elected, its block does not extend the blockchain and is thus wasted. If network delays are large, this happens frequently, and the rate at which the honest parties grow their blockchain slows down. Effectively, the honest participation reduces, giving the adversary an advantage.

A drawback of Sompolinsky and Zohar (2015) is that it does not factor into account all possible actions of the malicious parties. The work of Garay et al. (2015) was the first to account for arbitrary adversarial actions by analyzing the security of the longest-chain protocol in the formal security framework of consensus protocols. In this framework, the longest-chain protocol’s security can be distilled down to two properties: a safety property, namely consistency, and a liveness property, namely chain quality. The consistency property (aka persistence, settlement or common prefix) states that blocks in the blockchain that were created more than k time units ago become settled, that is, remain in the ledger forever after or remain out. The chain quality property states that every k time units, at least one block created by an honest leader will appear in the blockchain. Without chain quality, the adversary can keep out some transactions from the ledger, which would constitute a denial-of-service. The double-spend attack violates both the consistency and the chain quality properties.

Garay et al. (2015) show that, under appropriate modeling assumptions, both consistency and chain quality hold with high probability, irrespective of adversarial actions. Following Garay et al. (2015), many works have given rigorous security guarantees for the longest-chain protocol under a variety of modeling assumptions (Kiayias et al. 2017; Pass and Shi 2017; Pass et al. 2017; Dembo et al. 2020; Gaži et al. 2020, 2022). However, all of these works assume the synchronous network model, where any message sent from one honest party to another suffers a delay of at most Δ, where Δ is a constant. Recent papers have given tight security guarantees under this communication model. Dembo et al. (2020) and Gaži et al. (2020) show that the longest chain protocol is secure if and only if

where β denotes the fraction of adversarial mining power, f denotes the leader election rate, and Δ denotes the network delay. More recently, Gaži et al. (2022) give tight finite-time guarantees on the probability of security being broken for any $(\beta ,f,\mathrm{\Delta })$ that satisfies (1). The security threshold, that is, the supremum of β for which the protocol is secure, decreases with $f\mathrm{\Delta }$ (set the inequality in (1) to equality). Moreover, the results of Gaži et al. (2022) show that smaller the gap between β and the security threshold, larger is the adversary’s chance of success. To summarize, network delays have a detrimental effect on security.

In a real-world network, the worst-case message delays may be much larger than typical delays (see, for example, the empirical study in Decker and Wattenhofer (2013)). Often, these are from random factors such as network traffic or noise in the channels. In such a scenario, the only guarantees from the synchronous model are obtained by setting Δ to the maximum possible delay in (1). However, this may yield pessimistic guarantees: the fraction of honest blocks wasted would typically be less than that suggested by the worst-case delay. We posit that better security guarantees may be obtained by studying the protocol under a new communication model that allows for random delays.

1.1. Our Contributions

The main contribution of this paper is to analyze the security of the longest-chain protocol in a network with random, possibly unbounded, delays. Briefly, the network model we consider is as follows. Each peer-to-peer communication is subject to an independent and identically distributed (i.i.d.) delay bound. Thus, different recipients of a broadcast may receive the same broadcast message at different times. This model generalizes the synchronous model and has not been studied in prior work on blockchain security. For this model, we obtain security results that are qualitatively similar to those in the synchronous model. For simplicity, this work focuses on the simpler proof-of-work (PoW) setting instead of the more general proof-of-stake setting (see Blum et al. (2020) for a comparison between the modeling assumptions in these two settings).

A secondary contribution of ours is that we explicitly state and distinguish between two forms of security properties: intensive and extensive. These terms are borrowed from statistical physics. Intensive properties capture the security of localized portions of blockchains, whereas extensive properties provide global security guarantees. Prior works typically state properties in either one of these forms; those that state properties in both forms do not formally distinguish them. We show that guarantees for the intensive forms imply guarantees for the extensive forms.

Our main result, Theorem 1, states that the longest-chain protocol is secure in the random delay model, except with probability that decays exponentially in the wait time (or security parameter) k. The condition for security is that the probability of the following event must be greater than a half, irrespective of the past: the leader of a block is honest and it has heard of the previously created block. This condition allows for delay distributions with a long, possibly unbounded, tail. When delays are zero, this reduces to the honest majority condition. The result addresses the consistency and the chain quality property jointly. We provide simple, explicit error bounds. The guarantees hold for infinite-horizon executions.

On a finer note, our work shows that communication delays have both global and local effects. Delays from past leaders to future ones have a global effect: They influence the growth of the longest chain and impact the security of all honest parties. We incorporate these delays in our definition of the characteristic string (Section 4.2). In contrast, delays from leaders to a given honest party h have local impact: they affect the length of the chain held by h, and therefore h’s security alone. We account for these delays in the term ${\mathsf{\text{Unheard}}}_h$ (Section 4.3). This dual role is reflected in Theorem 1, where the error bounds have two terms. One is a bound on the probability of atypical behavior of the characteristic string, while the other is a bound on the probability of atypical behavior of ${\mathsf{\text{Unheard}}}_h$ for every honest party h.

1.2. Comparison with Prior Work

1.2.1. Communication Model.

The random delay model of this paper is a relaxation of the synchronous network model. There are two other relaxations that are popular in the literature: the partially synchronous model (Dwork et al. 1988) and the sleepy user model (Pass and Shi 2017). Both models relax the synchronous assumption by allowing the adversary to arbitrarily delay some messages. The partially synchronous model assumes that message delays are unbounded until an adversarially chosen time $\mathsf{\text{GST}}$ and are bounded thereafter. In this model, the protocol is secure only after $O(\mathsf{\text{GST}})$ time (Neu et al. 2021). In the sleepy model, the adversary has the power to set honest parties to sleep for arbitrarily long; these sleepy parties suffer unbounded delay. The longest-chain protocol is secure in the sleepy model, provided the fraction of awake honest parties always exceeds the fraction of corrupt parties (Pass and Shi 2017).

A key point in the previous models is that for those parties suffering from unbounded delay, it is impossible to provide any security guarantees. In comparison, for the random delay model, we are able to provide security guarantees that hold for any (finite set of) parties at all times. This is possible precisely because delays are random; it is unlikely that a given party suffers large delays for a long period of time. In conclusion, each of these models capture different facets of suboptimal network behavior. For a real-world network, the appropriate model may be any one of these and may even change over time. Moreover, these models are not exclusive; for example, in the sleepy model, the awake parties can be modeled as having random delays.

Two other works, namely Fanti et al. (2019) and Gopalan et al. (2020), study the longest-chain protocol under random, unbounded delay. These works model the network as a graph of interconnected nodes, and assume that delays between two neighboring nodes in the network are exponentially distributed and i.i.d. In this work, we only model end-to-end communication (equivalently, we assume the network is a complete graph). However, we allow for arbitrary delay distributions. More importantly, these papers do not consider the security of the protocol against an adversary. They are thus different in scope.

1.2.2. Security Statements.

Many papers on the security analysis of the longest-chain protocol consider both a safety property and a liveness property. However, there are minor differences in the precise statements used. The consistency (safety) property we use is inspired from the work of Blum et al. (2020) (they use the term settlement instead of consistency). Just like Blum et al. (2020), we state this property in both intensive and extensive forms, and show that guarantees for the former lead to guarantees for the latter. The chain quality (liveness) property of this work, in its extensive form, is the same as the existential chain quality property of Badertscher et al. (2018). However, we obtain tighter bounds for the same property than Badertscher et al. (2018), owing to our proof technique of obtaining bounds for intensive properties and then deriving bounds for the extensive ones.

1.2.3. Security Analysis.

At a high level, our security analysis follows that of other works analyzing the PoW longest-chain protocol (Garay et al. 2015; Pass et al. 2017; Ren 2019; Gaži et al. 2020, 2022; Li et al. 2021). We first use deterministic, combinatorial arguments to map events concerning chains to events concerning some random processes and then use probabilistic analysis to bound the probability of their atypical behavior. The novelty of this paper lies in constructing random objects that, on the one hand, give sufficient conditions for security in the random delay model, and on the other hand, are amenable to probabilistic analysis.

To conclude, the security threshold obtained in this work is not tight. This can be seen by comparing our security threshold with (1) for the special case of a constant Δ. The works of Dembo et al. (2020) and Gaži et al. (2020) give a tight characterization of the security regime in the synchronous model. Extending their results to the random delay model is a direction of future research.

2. System Model

This section contains the mathematical model for a PoW blockchain system. This includes the protocol specifications (Section 2.2), adversarial powers (Section 2.2), the leader election mechanism (Section 2.3) and the communication network model (Section 2.4). The novel aspects of the model are the one-time leader election mechanism and the random network delays in the communication network model. The other elements of our model are similar to those studied in earlier work.

2.1. Preliminaries

The longest-chain protocol is run by a set of parties that aim to achieve consensus (or agreement) on an ever-growing sequence of blocks. The protocol proceeds in discrete time slots that are indexed by $\mathbb{N}$ and runs for an infinite duration. We assume that clocks of all parties are perfectly synchronized. Blocks are treated as abstract data structures containing an integer timestamp, a hash pointer to a parent block with a smaller timestamp, a cryptographic signature of the block’s creator, some transactions and other relevant information. The timestamp of a block is the index of the slot in which the block was created. A special genesis block, with timestamp zero and no parent, is known to all parties at the start of the protocol.

Parties in the Protocol. The parties in the protocol comprise of multiple honest ones and a single adversary $\mathcal{A}$. (Replacing all corrupt parties by a single one is done for simplicity.) The set of honest parties is represented by $\mathcal{H}$ and may be finite or infinite. Arbitrary honest parties are denoted by $h,h_1,h_2,$ and so on. In our model, the adversary can never corrupt an honest party and the honest parties never go offline. Honest parties follow the longest-chain protocol, whereas the adversary can deviate from the protocol in certain ways. The prescribed behavior for honest parties and the powers of the adversary are described in Section 2.2.

Blockchains. From any block, a unique sequence of blocks leading back to the genesis block can be identified via the hash pointers. We call such a sequence a chain (short for blockchain). A generic chain is denoted by $\mathcal{C}$. The convention is that the genesis block is the first block of the chain, and the terminating block is called the tip. The blocks of a chain can be indexed by the timestamps of the blocks. The timestamps of blocks in a chain must strictly increase, going from the genesis to the tip. At any given slot, each honest party stores a single chain in its memory. We use ${\mathcal{C}}_i^h$ to denote the chain held by an honest party h at (the end of) slot i. We use $\mathcal{C}[i_1:i_2]$ to represent the portion of a chain $\mathcal{C}$ consisting of blocks with timestamps in the interval $\{i_1,\dots ,i_2\}$. The length of a chain $\mathcal{C}$, denoted by $|\mathcal{C}|$, is defined to be the number of blocks in the chain, excluding the genesis block. Likewise, $|\mathcal{C}[i_1:i_2]|$ denotes the number of blocks in $\mathcal{C}$ that are created in the interval $\{i_1,\dots ,i_2\}$. The height of a block with timestamp i in a chain $\mathcal{C}$ is $|\mathcal{C}[1:i]|.$

Blocktrees. The set of all blocks created up to a given slot i forms a directed tree. Let ${\mathcal{F}}_i$ be the directed graph (V, E), where V is the set of blocks created up to slot i, including those created by the adversary, and E is the set of parent-child block pairs. These edges point from parent to child, in the opposite direction of the hash pointers. The genesis block is the root of the tree, with no parent. In addition, the timestamp of block v is denoted by $\mathcal{\ell }(v)$. Every chain ${\mathcal{C}}_i^h$ is a directed path in ${\mathcal{F}}_i$ that begins at the genesis block.

2.2. Honest Protocol and Adversarial Powers

Honest Protocol. Whenever an honest party is elected as a leader, it creates a new block with the timestamp of the current slot, appends it to the chain it holds, and broadcasts this new chain to all the other parties. The adversary hears of this new chain immediately, whereas other honest parties hear of the chain after some delay (more details about the delay are given in Section 2.4).

An honest party always holds the longest chain that it has heard of thus far. Whenever it hears of a chain that is longer than the one it currently holds, it swaps the old chain for the new one, irrespective of the extent to which the two chains differ. Ties between chains of equal length are broken based on the content of the blocks in the chain; since we are oblivious to the block’s contents, we assume ties are broken arbitrarily.

Adversarial Powers. The adversary has two special powers. First, it can select which chain to extend, not necessarily the longest, when it creates a new block as a leader. It can only create a block when it is a leader and it cannot create a block between two existing blocks. Second, it has the power to control message delays. To elaborate, messages between honest parties have arbitrary delays, subject to deadlines imposed by the network (Section 2.4). The messages from the adversary to honest parties have arbitrary delays without constraint. In particular, the adversary can privately hold some of the blocks it created and release them later at some opportune time.

Ordering of Events in a Slot. Events occur in a slot in the following order. First, a leader is selected (if any) by the leader election mechanism. The selected leader then creates a block and broadcasts the corresponding chain. Next, any messages to be received in the slot are delivered to the respective honest parties. Finally, honest parties appropriately update their chains.

2.3. Leader Election Mechanism

The leader election mechanism in our model is an idealized model of the PoW mining process (see Garay et al. (2015) for more details about mining). In each slot, the mechanism chooses at most one leader among the parties at random, whose role is to create a new block. This random process can be described as follows. Whether a slot is empty forms a Bernoulli process, that is, a sequence of i.i.d. Bernoulli random variables. Let f be the probability of a nonempty slot. In PoW parlance, f is the mining rate of the protocol. In particular, this implies that the interval between two nonempty slots is geometrically distributed with parameter f (which we denote by $\mathsf{\text{geom}}(f)$). Throughout this paper, geometric random variables take values in $\{1,2,\dots \}$. Furthermore, among the nonempty slots, the sequence of honest and adversarial leaders also forms a Bernoulli process. Given that a slot is nonempty, let α be the probability that the leader is honest; the leader is $\mathcal{A}$ with probability $\beta =1-\alpha$. Thus, α is the fraction of honest mining power in the system. Such a leader election process is also considered in Gaži et al. (2020).

Within this framework, we consider two slightly different leader election models, namely the i.i.d. leader election model and the one-time leader election model. In the i.i.d. leader election model, the sequence of honest leaders are chosen independently from $\mathcal{H}$, all with the same probability distribution. In particular, it is possible that the same honest party is elected twice in consecutive slots. In the one-time leader election model, each honest party can be a leader at most once. In particular, this implies that there are infinitely many honest parties. The model is the asymptotic limit of a system with a large number of parties with similar mining powers.

Arguably, the i.i.d. leader model is more realistic than the one-time leader model. However, the security analysis of the former has some subtleties. These arise from the possibility that the same honest party is elected a leader multiple times in close succession (see Appendix B for more detail). Therefore, we prove our results for the one-time leader model in the main text and give the necessary additional arguments for the i.i.d. leader model in the appendix. Interestingly, the model with random delays forces us to pay attention to the identities of the honest leaders. In contrast, these identities do not appear in the analysis in the synchronous model (Blum et al. 2020, Gaži et al. 2020). Finally, we only consider the possibility of zero or one leader per slot; this is for simplicity’s sake. Strictly speaking, a discretized version of the continuous-time mining process should allow for multiple leaders to be elected in a slot, but this event can be made negligibly rare by taking the slot duration to be very small.

2.4. Communication Model

The communication network is modeled as follows. For every message sent by one honest party to another, the network imposes an upper bound on the delay. Equivalently, the network sets a deadline for the message to be delivered. The actual delay is decided by the adversary, respecting the message deadline. Thus, each message can have a delay smaller than or equal to the bound set for it by the network. Successive messages between the same pair of parties could have different delay bounds. We adopt the convention that the minimum possible delay is zero. If the delay is zero, a message sent in a time slot is received by the end of that slot.

We assume that the delay bounds set by the network are random variables, which can take any value in ${\mathbb{Z}}_{+}$. The delay bounds of different messages are assumed to be i.i.d. across all messages. Let Δ denote a random variable with the common distribution, which we call the delay distribution. While the delay bounds are random, the actual delays are arbitrary (subject to the upper bounds). We consider a broadcast to be a set of different end-to-end messages. Thus, different honest parties may hear of a message broadcast by an honest leader at different times. As mentioned before, messages from honest parties to the adversary have zero delay, whereas messages from the adversary to the honest parties have arbitrary delay (without any bound). Last, the synchronous network model is a special case of this model with a constant Δ.

In the i.i.d. leader election model, we have an additional requirement, namely, the delay distribution must have a nondecreasing failure rate function. The failure rate function for the delay distribution Δ is defined as

Roughly speaking, the requirement implies that the longer one has waited for a message, the sooner it is likely to arrive. A geometric random variable has a constant failure rate. A constant Δ has a failure rate function that is zero up to the constant and one thereafter. Therefore, they are both admissible. However, the condition precludes heavy-tailed distributions. This technical condition is required to handle the subtlety mentioned in Section 2.3: the case where the same leader is elected multiple times in close succession. The one-time leader model does not require these conditions. It even permits distributions with positive probability for $\mathrm{\Delta }=\infty$, that is, where messages are not delivered.

Messages in a blockchain network are spread via a protocol wherein the growing number of parties with a message relay it on to other parties. Therefore, the end-to-end delay distribution is likely to have a geometrically bounded tail. Thus, we argue that the nondecreasing failure rate assumption is realistic. Moreover, given the power of the adversary to deliver honest messages earlier than scheduled, a system with a given delay distribution Δ can be emulated by a system that has a different delay distribution $\tilde{\mathrm{\Delta }}$, provided the latter stochastically dominates the former. If $\tilde{\mathrm{\Delta }}$ satisfies the nondecreasing failure rate restriction, guarantees for a system with delay Δ can be given in terms of the distribution $\tilde{\mathrm{\Delta }}$.

3. Desired Security Properties

This section contains the formal definitions of our security properties, the condition under which the properties hold (with high probability), and the main theorem that bounds the probability that these are violated. The two security properties are consistency (a safety property) and chain quality (a liveness property). Both are stated in intensive and extensive forms, and these forms are compared. The security properties and the guarantees for them hold for both models introduced in Section 2: the i.i.d. leader model with the delay distribution having a nondecreasing failure rate function and the one-time leader model with a general delay distribution.

Each security property refers to a desirable condition over an execution. An execution of the protocol refers to a particular instantiation of the random components (i.e., leader election and communication delays) and the actions of the adversary. Whether a certain property holds or not in an execution depends on both these factors. The adversary’s actions are arbitrary and the security guarantees are stated for the worst-case scenario of all possible adversarial actions.

3.1. Property Definitions

We first define the consistency property, in both its intensive and extensive forms.

Definition 1

(Intensive Consistency). In an execution, the intensive consistency property with parameters $s,k\in \mathbb{N}$ and $\mathcal{I}\subseteq \mathcal{H}$ holds if, for any pair of honest parties $h,h\prime \in \mathcal{I}$ and slots $i,i\prime$ such that $s+k\le i\le i\prime$, it holds that ${\mathcal{C}}_i^h[1:s]={\mathcal{C}}_{i\prime }^{h\prime }[1:s]$.

Definition 2

(Extensive Consistency). In an execution, the extensive consistency property with parameters $T,k\in \mathbb{N}$ and $\mathcal{I}\subseteq \mathcal{H}$ holds if, for any pair of honest parties $h,h\prime \in \mathcal{I}$ and slots $s,i,i\prime$ such that $s\le T$ and $s+k\le i\le i\prime$, it holds that ${\mathcal{C}}_i^h[1:s]={\mathcal{C}}_{i\prime }^{h\prime }[1:s]$.

For brevity, we use the notation ($s,k,\mathcal{I}$)-property to refer to any property with parameters s, k, and $\mathcal{I}$.

The intensive and extensive forms of consistency have a subtle difference, which is illustrated with the following example. Let T be some large number. The $(T,k,\mathcal{I})$-intensive consistency property means the parties in $\mathcal{I}$ agree forever after slot T + k about the chain up to slot T. This immediately implies that all parties in $\mathcal{I}$ agree forever about the chain up to slot s, after slot T + k, for any $s\le T$. This does not, however, imply that all parties in $\mathcal{I}$ agree forever about the chain up to time s, after slot s + k, for all s with $s\le T$. This latter statement, which is stronger, is captured by the extensive form of the consistency property. The following lemma relates the two forms of consistency. The proof follows easily from the definitions and is left to the reader.

Lemma 1.

Fix a set of honest parties $\mathcal{I}\subseteq \mathcal{H}$ and parameters $T,k\in \mathbb{N}$. The $(T,k,\mathcal{I})$-extensive consistency property holds if and only if the $(s,k,\mathcal{I})$-intensive consistency property holds for all $s\le T$.

The chain quality property is stated next, first in its intensive form and then in its extensive form.

Definition 3

(Intensive Chain Quality). In an execution, the intensive chain quality property with parameters $s,k\in \mathbb{N}$ and $\mathcal{I}\subseteq \mathcal{H}$ holds if, for any honest player $h\in \mathcal{I}$ and slot $i\ge s+k,\hspace{0.17em}{\mathcal{C}}_i^h[s+1:s+k]$ contains at least one honestly created block.

Definition 4

(Extensive Chain Quality). In an execution, the extensive chain quality property with parameters $T,k\in \mathbb{N}$ and $\mathcal{I}\subseteq \mathcal{H}$ holds if, for any honest player $h\in \mathcal{I}$ and slots s, i such that $s\le T$ and $i\ge s+k,\hspace{0.17em}{\mathcal{C}}_i^h[s+1:s+k]$ contains at least one honestly created block.

The relation between the intensive and extensive versions of chain quality parallels that between the intensive and extensive forms of the consistency property noted in Lemma 1 and is stated next (without proof).

Lemma 2.

Fix a set of honest parties $\mathcal{I}\subseteq \mathcal{H}$ and parameters $T,k\in \mathbb{N}$. The $(T,k,\mathcal{I})$-extensive chain quality property holds if and only if the $(s,k,\mathcal{I})$-intensive chain quality property holds for all $s\le T$.

The subset of honest parties $\mathcal{I}$ is explicitly mentioned in the security properties. This is because the probability with which the properties are violated increases with the size of this set (see Theorem 1). This is inevitable in the random delay model with unbounded delay distributions. Consider a setting with infinitely many honest parties in a system with geometrically distributed delays. Then, for any fixed T, there will almost surely exist an honest party that has not heard of any honest block up to slot T. Clearly, such a party cannot be guaranteed to have any security results. This issue does not arise if delays are bounded. Therefore, in earlier works that deal with the constant Δ setting (Garay et al. 2015, Kiayias et al. 2017), the subset of honest parties $\mathcal{I}$ is implicitly taken to be the entire set $\mathcal{H}$.

3.2. Main Result

The main result of this paper, Theorem 1, is a bound on the probability that either of the intensive security properties are violated. Naturally, such a security result can be proven only under the condition that the fraction of honest mining power is large enough (at least half) and that the typical delay is small enough compared with the mining rate. In this work, the security results hold under the ϵ-honest majority condition, which is defined next.

Definition 5

(ϵ-Honest Majority). Consider the longest-chain protocol where the leader election process has parameters α and f and the network’s delay distribution is represented by a random variable Δ. Let $G\sim \mathsf{\text{geom}}(f)$ be a random variable that is independent of Δ, which denotes the typical interval between nonempty slots. Let $p\triangleq \alpha \mathbb{P}(\mathrm{\Delta }<G).$ Suppose the system’s parameters are such that p > 0.5. Let ϵ be such that $p=(1+ϵ)/2$. We say that such a protocol has ϵ-honest majority.

Theorem 1

(Main Result). Consider the longest-chain protocol with ϵ-honest majority. Then for any $\mathcal{I}\subseteq \mathcal{H},\hspace{0.17em}s\in \mathbb{N}$, and $k\in \mathbb{N}$,

$$\begin{array}{l}\mathbb{P}((s,k,\mathcal{I})-\mathit{\text{intnsive}}\hspace{0.17em}\mathit{\text{consistency}}\hspace{0.17em}\mathit{\text{property}}\hspace{0.17em}is\hspace{0.17em}\mathit{\text{violated}}\hspace{0.17em}OR\hfill \\ (s,k,\mathcal{I})-\mathit{\text{intensive}}\hspace{0.17em}\mathit{\text{chain}}\hspace{0.17em}\mathit{\text{quality}}\hspace{0.17em}\mathit{\text{property}}\hspace{0.17em}is\hspace{0.17em}\mathit{\text{violated}})\le p_{\mathsf{\text{char}}-\mathsf{\text{string}}}+|\mathcal{I}|p_{\mathsf{\text{unheard}}}\hfill \end{array},$$

where

$$p_{\mathsf{\text{char}}-\mathsf{\text{string}}}=4\exp (-(3/32){ϵ}^{2}fk)\hspace{1em}\hspace{1em}{p}_{\mathsf{\text{unheard}}}=(8/ϵ)\exp (-(1/32)ϵfk).$$(2)

Theorem 1 implies the following result about the extensive safety and liveness properties.

Corollary 1.

Consider the longest-chain protocol with ϵ-honest majority. Then for any $\mathcal{I}\subseteq \mathcal{H},\hspace{0.17em}T\in \mathbb{N}$ and $k\in \mathbb{N}$,

$$\begin{array}{l}\mathbb{P}((T,k,\mathcal{I})\mathit{\text{-extensive}}\hspace{0.17em}\mathit{\text{consistency}}\hspace{0.17em}\mathit{\text{property}}\hspace{0.17em}is\hspace{0.17em}\mathit{\text{violated}}\hspace{0.17em}OR\hfill \\ (T,k,\mathcal{I})\mathit{\text{-extensive}}\hspace{0.17em}\mathit{\text{chain}}\hspace{0.17em}\mathit{\text{quality}}\hspace{0.17em}\mathit{\text{property}}\hspace{0.17em}is\hspace{0.17em}\mathit{\text{violated}}))\le T\hspace{0.17em}(p_{\mathsf{\text{char}}-\mathsf{\text{string}}}+\text{|}\mathcal{I}\text{|}{p}_{\mathsf{\text{unheard}}})\hfill \end{array}.$$

The key difference between intensive and extensive properties can be seen by the guarantees on them. The probability of the intensive properties being violated is bounded independently of T (Theorem 1). The bound on the probability of the extensive properties being violated grows linearly with T (Corollary 1). Corollary 1 follows from Theorem 1, Lemmas 1 and 2, and the union bound.

To gain some intuition behind Theorem 1, consider the security guarantees obtained from this result for a special case, namely, exponentially distributed delay bounds. Although our results are stated for discrete time, they suggest corresponding results in continuous time by taking a limit, as described in Gaži et al. (2020). In continuous time, the leaders are elected at times of a Poisson process of rate f, with a leader being the adversary with probability β and honest with probability $1-\beta .$ The sufficient condition for security reduces to $(1-\beta )\mathbb{P}(\mathrm{\Delta }<\mathsf{\text{Exp}}(f))>\frac{1}{2},$ where $\mathsf{\text{Exp}}(f)$ denotes an exponentially distributed random variable with rate parameter f (mean $1/f$). In case Δ has the $\mathsf{\text{Exp}}(1/\eta )$ distribution (with mean η), the sufficient condition for security becomes $\beta <\frac{1-\eta f}{2}.$ Therefore, $\frac{1-\eta f}{2}$ is a lower bound on the security threshold of a system parameterized by $(f,\mathrm{\Delta }\sim \mathsf{\text{Exp}}(1/\eta ))$. (Recall that the security threshold is the supremum of the adversarial power that can be tolerated and it depends on the system’s mining rate and delay parameters.) We plot the aforementioned lower bound as function of $f\eta$ in Figure 1. For comparison, the boundaries of the security region guaranteed for bounded delay (according to (1)) for $\mathrm{\Delta }\equiv \eta ,$ $\mathrm{\Delta }\equiv 4\eta ,$ and $\mathrm{\Delta }\equiv 16\eta$ are also given.

Figure 1 shows that the adversarial tolerance guarantees provided by this work with $\mathrm{\Delta }\sim \mathsf{\text{Exp}}(1/\eta )$ are better than the best possible guarantees with $\mathrm{\Delta }\equiv 16\eta$ in the range $f\eta <0.8$. Consider, for the sake of illustration, a system such that Δ has the distribution that is identical to $\mathsf{\text{Exp}}(1/\eta )$ from $[0,16\eta ]$ and concentrates the rest of the mass at $16\eta$. Such a distribution is stochastically dominated by both $\mathsf{\text{Exp}}(1/\eta )$ and the constant delay $16\eta$; thus, guarantees for both models apply. For such a system, the security region of the protocol as guaranteed by Theorem 1 is greater than what can be established via the synchronous model alone. This shows that explicitly accounting for random delays can provide better security guarantees than simply working with the worst-case delay.

The upper bound on the probability of a successful attack, as given in Theorem 1, decreases exponentially as a function of fk. To explore the constant in the exponent, we perform a Monte Carlo simulation of the private attack. Figure 2 shows the estimated probability of success of the attack. The simulations show an exponential decrease in the probability of a successful attack. Moreover, the plot also illustrates that the adversary’s chance of success increases with the mean delay; this trend is also reflected in Theorem 1. Comparing the bounds given in Theorem 1 to the simulation results, we observe that the constants in the exponent in our bounds are not tight. We chose to express our theorems with simple, explicit bounds, rather than bounds that require numerical optimization or sophisticated analysis. We leave it for future work to obtain numerically tighter bounds.

3.3. Proof Sketch

The basic intuition guiding the security analysis in this work is the following. The security properties are likely to be violate if the adversary can build two equally long chains that fork far back in time. There are two factors that contribute to long forked chains, namely, adversarial blocks and network delays among honest parties. To elaborate, the adversary can purposely deviate from the longest-chain rule and use its blocks to extend the shorter of two competing chains. In addition, due to network delays, it is possible that some honest parties extend the shorter of two forked chains, simply because they have not heard of the latest block(s) on the longer chain. If the number of adversarial blocks and the number of forked honest blocks are small relative to the length of the chains of honest parties, the protocol remains secure.

To distinguish between honest blocks that grow the chain from those that do not, we introduce the notion of special honest slots. These are recursively defined such that the leader of each special honest slot has necessarily heard of the message sent by the leader of the previous slot. It immediately follows that blocks from special honest slots are always built at ever-increasing heights on the blocktree, contributing to its growth. All other honest blocks are treated as adversarial, as they could be placed arbitrarily in the blocktree. (This is one of the reasons our bounds are loose; tighter bounds on the security analysis would require a more careful analysis of all honest blocks.)

Whether a given honest slot s is special honest is determined by two random entities: the time passed since the last special honest slot, and the delay in conveying that block to the leader of s. Both these factors are beyond the adversary’s control; they depend solely on the mining rate f and the delay distribution Δ. The ϵ-honest majority condition required for security (Definition 5) is simply the requirement that every new block is special honest with probability at least a half. If this condition holds, then over any considerable interval, the number of special honest slots exceed the number of adversarial slots with high probability. We show that this is sufficient to guarantee security.

The rest of the paper is devoted to the proof of Theorem 1. Section 4 introduces some key notation and the definition of special honest slots. The proof is split into two main components. First, via a deterministic, combinatorial analysis, we obtain a sufficient condition for security, ${\mathcal{E}}_{\mathsf{\text{secure}}}$ (Section 5). Second, we provide an upper bound on the probability of ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ occurring (Section 6). Together, these results provide the desired security guarantee (Section 7).

4. Definitions of Key Random Processes

All random processes in our model are discrete-time processes, indexed by $\mathbb{N},\hspace{0.17em}{\mathbb{Z}}_{+}$, or $\mathbb{Z}$ (the relevant indexing will be specified when the process is defined). For a random process $\mathsf{\text{Process}}$, the notation for the ith variable is $\mathsf{\text{Process}}[i]$. Denote an interval of slots $\{i_1,\dots ,i_2\}$ by $[i_1:i_2]$. The portion of the process over such an interval is denoted by $\mathsf{\text{Process}}[i_1:i_2]$. If $i_2<i_1,\hspace{0.17em}[i_1:i_2]$ (and by extension, $\mathsf{\text{Process}}[i_1:i_2]$) denotes an empty interval (or string).

4.1. $\mathsf{\text{LeaderString}}$ as a Stationary Renewal Process

We start by defining $\mathsf{\text{LeaderString}}$, a random process which represents the sequence of leaders in each slot without the leader identities. We then extend this process to negative time. $\mathsf{\text{LeaderString}}$ takes values in $\{\perp ,0,1\}$. For $i\ge 1$,

$\mathsf{\text{LeaderString}}$ is an i.i.d. process with $\mathbb{P}(\mathsf{\text{LeaderString}}[i]=\perp )$ $=1-f,\hspace{0.17em}\mathbb{P}(\mathsf{\text{LeaderString}}[i]=0)$ $=\alpha f$ and $\mathbb{P}(\mathsf{\text{LeaderString}}[i]=1)$ $=(1-\alpha )f$ (see Section 2.3). Extend this process to negative time by defining $(\mathsf{\text{LeaderString}}[i]:i\le 0)$ to be a sequence of i.i.d. random variables with the same probabilities as noted above. Call all slots with $\mathsf{\text{LeaderString}}[i]\ne \perp$ as nonempty slots and those with $\mathsf{\text{LeaderString}}[i]=0$ as honest slots. Let $1\le T_1<T_2<\cdots$ denote the indices of the nonempty slots of $\mathsf{\text{LeaderString}}$ from slot 1 onward. Similarly, let $0\ge T_0>T_{-1}>T_{-2}>\cdots$ index the nonempty slots before or up to slot zero, going backward in time. For any interval $[i_1:i_2]$, define $N[i_1:i_2]$ to be the number of nonempty slots in that interval.

A random process is stationary if its distribution is invariant under any deterministic time shift. A renewal process is an arrival process (a sequence of events or arrivals) where the intervals between arrivals are i.i.d. The times of the arrivals are called renewal points, and the gap between renewal points is called the lifetime. The set of nonempty slots forms a stationary renewal process with lifetime distribution $\mathsf{\text{geom}}(f).$ Given the locations of all the renewal points, the labels at the renewal points are i.i.d. Bernoulli random variables with $\mathbb{P}(0)=\alpha$. For any $j\ne 1,\hspace{0.17em}{T}_j-T_{j-1}$ has distribution $\mathsf{\text{geom}}(f)$, whereas $T_1-T_0=T_1+(1-T_0)-1,$ so that $T_1-T_0$ is the sum of two independent $\mathsf{\text{geom}}(f)$ random variables minus one. In the terminology of renewal theory, $T_1-T_0$ is the sampled lifetime sampled at time 0. In the Ouroboros line of works (Kiayias et al. 2017, Badertscher et al. 2018, David et al. 2018), the process $\mathsf{\text{LeaderString}}$ is called the characteristic string. We reserve that term for a slightly different process, which is defined next.

4.2. Special Honest Slots and $\mathsf{\text{CharString}}$

We now introduce a new concept called special honest slots, which can be thought of as a generalization of Δ-isolated slots from Pass et al. (2017) and David et al. (2018). Simultaneously, we also define the notion of the characteristic string, denoted by $\mathsf{\text{CharString}}$. The process $\mathsf{\text{CharString}}$ is a process indexed by $\mathbb{Z}$, taking values in $\{\perp ,0,1\}$. In $\mathsf{\text{CharString}}$, special honest slots are marked with symbol 0, other nonempty slots with symbol 1, and empty slots with the symbol $\perp$. Thus, $\mathsf{\text{CharString}}$ is obtained from $\mathsf{\text{LeaderString}}$, by converting some zero symbols to one (those honest slots that are not special).

The precise definition of $\mathsf{\text{CharString}}$ for the one-time leader model is given in the remainder of this section. (The construction in the i.i.d. leader model is given in Appendix B.) In the construction of $\mathsf{\text{CharString}}$, consider the entire process $\mathsf{\text{LeaderString}}$ (in particular, $\{T_j:j\in \mathbb{Z}\}$) and all the previously defined quantities as given. We introduce some additional notation for convenience. For all j > 0 such that T_j is an honest slot, let h_j denote the leader of the slot. Let $\mathsf{\text{delay}}(T_j\to h)$ denote the delay bound (set by the network) in the message sent by h_j in slot T_j to an honest party $h\in \mathcal{H}$. Finally, let $\mathsf{\text{delay}}(T_j\to h)$ be random variables with the same distribution as Δ for all honest slots $T_j<0$.

For all $i\in \mathbb{Z}$ such that $\mathsf{\text{LeaderString}}[i]\in \{1,\perp \}$, let $\mathsf{\text{CharString}}[i]=\mathsf{\text{LeaderString}}[i]$. For $j\le 0$, if $\mathsf{\text{LeaderString}}[T_j]=0$, let $\mathsf{\text{CharString}}[T_j]$ be zero with probability $\mathbb{P}(\mathrm{\Delta }<T_j-T_{j-1}|T_j-T_{j-1})$, and let $\mathsf{\text{CharString}}[T_j]$ be one otherwise. The aforementioned choices are conditionally independent across all $j\le 0.$ It remains to define $\mathsf{\text{CharString}}[T_j]$ for all $j\ge 1$ such that slot T_j is honest. This is done sequentially. For $j\ge 1$, let $T_{j^{*}}$ denote the last special honest slot, that is, slot with $\mathsf{\text{CharString}}[T_{j^{*}}]=0,$ strictly before T_j. Let $\mathsf{\text{CharString}}[T_j]=0$ if slot T_j is honest and $R_j<T_j-T_{j-1}$, where $R_j\triangleq \mathsf{\text{delay}}(T_{j^{*}}\to h_j)$. Otherwise, let $\mathsf{\text{CharString}}[T_j]=1.$ The $\mathsf{\text{CharString}}$ process for negative time was used to define the first special honest slot in positive time. This concludes the construction of $\mathsf{\text{CharString}}$, given $\mathsf{\text{LeaderString}}$, the identities of the honest leaders h_j, and the delay bounds among all honest parties $\mathsf{\text{delay}}(T_j\to h)$. All these are random entities, not controlled by the adversary. Later, in Section 6.2, we characterize the distribution of $\mathsf{\text{CharString}}$. In particular, it is a stationary process, a property that is useful in our security analysis.

Special honest slots are the slots T_j where $\mathsf{\text{CharString}}[T_j]=0$. Those nonempty slots that are not special honest are defined to be adversarial. This includes those slots that are honest, but not special honest. Define the blocks that are created by the leaders of special honest slots to be special honest blocks.

For any interval $[i_1:i_2]$, define $N_{\mathsf{\text{spl}}}[i_1:i_2]$ to be the number of special honest slots, and let $N_{\mathsf{\text{adv}}}[i_1:i_2]$ denote the number of adversarial slots, in that interval. It follows that $\mathsf{N}[i_1:i_2]=N_{\mathsf{\text{spl}}}[i_1:i_2]+N_{\mathsf{\text{adv}}}[i_1:i_2].$ Special honest slots have the following key property: blocks created in successive special honest slots are built at strictly increasing heights. Note that h_j receives the message from the previous special honest slot at or before time $T_{j^{*}}+R_j$. If T_j is special honest, then $T_{j^{*}}+R_j<T_{j^{*}}+T_j-T_{j-1}\le T_j.$ Thus, the condition for T_j to be a special honest slot is sufficient, but not necessary, for h_j to have heard of the message from the previous special honest slot. From this, the aforementioned property follows. This property is used to lower bound the length of the portion of chains in Lemmas 3 and 4. It is also used in Lemma 5 to derive a necessary condition for consistency violation.

4.3. The $\mathsf{\text{Unheard}}$ Process

For an honest party h and $i\ge 1,$ let $\mathsf{\text{LatestHear}}{\mathsf{d}}_h[i]$ denote the special honest slot with greatest index such that the broadcast in that slot must have been heard by h by the end of slot i (even if the adversary maximally delays the messages). That is,

We use the convention that the maximum of an empty set is zero. Thus, $0\le \mathsf{\text{LatestHear}}{\mathsf{d}}_h[i]\le i$.

Let ${\mathsf{\text{Unheard}}}_h[i]$ denote the number of special honest slots in the interval $[\mathsf{\text{LatestHear}}{\mathsf{d}}_h[i]+1,i]$. In other words,

The interpretation here is that ${\mathsf{\text{Unheard}}}_h[i]$ is an upper bound on the number of consecutive special honest slots that party h has not heard the messages from by slot i, counting backward from i. (It is an upper bound because it’s defined in terms of the delay upper bounds, not the true delays.) For example, ${\mathsf{\text{Unheard}}}_h[i]=2$ means that by the end of slot i, h might not have heard the messages from the last two special honest slots occurring before or at i but it either must have heard the message sent in the third most recent special honest slot before slot i or there were only two special honest slots during $[1:i].$ Looking ahead, ${\mathsf{\text{Unheard}}}_h[i]$ is used to lower bound the length of the chain ${\mathcal{C}}_i^h$, as shown in Lemma 4. In turn, this lower bound is used to derive necessary conditions for consistency and chain quality violation in Lemmas 5 and 6.

Finally, given a set of honest parties $\mathcal{I}$, let

that is, ${\mathsf{\text{Unheard}}}_{\mathcal{I}}[i]$ is the least upper bound for ${\mathsf{\text{Unheard}}}_h[i]$ over all $h\in \mathcal{I}$.

5. Lemmas on Deterministic Properties

This section derives a necessary condition for the consistency property and the chain quality property to be violated. The necessary conditions for both the security properties turn out to be identical. The condition is expressed as an inequality in terms of the $\mathsf{\text{CharString}}$ and $\mathsf{\text{Unheard}}$ processes. This inequality must hold if the adversary has violated the security properties. It can be worded as follows: over some sizable interval, the number of nonspecial honest blocks must exceed the number of special honest blocks, barring a term of $\mathsf{\text{Unheard}}$ (see (7) for the exact condition). In deriving this necessary condition, we factor out the arbitrary actions of the adversary; equivalently, we consider the worst-case adversarial actions. With this analysis, the proof of Theorem 1 is reduced to bounding the probability of an event concerning the random processes $\mathsf{\text{CharString}}$ and $\mathsf{\text{Unheard}}$.

Before formally proving these reductions, we introduce the notion of the latest special honest chain (at slot i), and use this notion to give two forms of the chain growth property. Such a property has been used by other works that analyze PoW blockchains (Garay et al. 2015, Pass et al. 2017) in their security analysis.

Definition 6

(Latest Special Honest Chain). For any slot $i\in \mathbb{N}$, let ${\mathcal{C}}_i^{*}$ denote the chain broadcast by the leader of the last special honest slot at or before slot i. Call this the latest special honest chain at slot i. In ${\mathcal{F}}_i,\hspace{0.17em}{\mathcal{C}}_i^{*}$ is the longest chain that ends in a special honest block. ${\mathcal{C}}_0^{*}$ is the genesis block.

Two simple facts follow immediately from the definition. First, if i is a special honest slot, then ${\mathcal{C}}_i^{*}$ is the chain that is broadcast by the leader of slot i. Second, if a chain $\mathcal{C}$ contains a block created in a special honest slot s, then $\mathcal{C}[1:s]={\mathcal{C}}_s^{*}$. These facts are used frequently in the following proofs. The following chain growth lemma is also easily proven.

Lemma 3

(Chain Growth–Special Honest). Between any two time slots $i,i\prime \in \mathbb{N}$ such that $i\le i\prime$, the increase in the length of the latest special honest chain is bounded below by the number of special honest slots in the interval $[i+1,i\prime ]$. I.e.,

$$|{\mathcal{C}}_{i\prime }^{*}|\ge |{\mathcal{C}}_i^{*}|+N_{\mathsf{\text{spl}}}[i+1:i\prime ],\hspace{1em}\forall i\le i\prime .$$(6)

Proof.

The property of special honest slots implies that the chains broadcast in successive special honest slots must have strictly increasing lengths. This implies (6). □

As it stands, the prevous lemma only lower bounds the growth of latest special honest chains, ${\mathcal{C}}_i^{*}$. However, it is useful in bounding the chain growth of any honestly held chain, as shown next.

Lemma 4

(Chain Growth–Honest). For any $i\in \mathbb{N}$ and any $h\in \mathcal{H}$, suppose ${\mathcal{C}}_i^h$ contains a special honest block created in slot r, or let r = 0. Then

$$|{\mathcal{C}}_i^h|\ge |{\mathcal{C}}_r^{*}|+N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_h[i].$$

Equivalently,

$$|{\mathcal{C}}_i^h[r+1:i]|\ge N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_h[i].$$

Proof.

By the definition of $\mathsf{\text{LatestHeard}}$ (Section 4.3), the honest party h must have heard of the chain ${\mathcal{C}}_l^{*}$ by slot i, where $l\triangleq \mathsf{\text{LatestHear}}{\mathsf{d}}_h[i]$. Therefore, the chain it holds at slot i must be at least as long as ${\mathcal{C}}_l^{*}$, that is, $|{\mathcal{C}}_i^h|\ge |{\mathcal{C}}_l^{*}|.$ By Lemma 3, $|{\mathcal{C}}_l^{*}|\ge |{\mathcal{C}}_r^{*}|+N_{\mathsf{\text{spl}}}[r+1:l],$ provided $l\ge r$. We know that ${\mathsf{\text{Unheard}}}_h[i]=N_{\mathsf{\text{spl}}}[l+1:i]$ (by (5)). Putting the previous inequalities together, we get

$$\begin{array}{ll}|{\mathcal{C}}_i^h|\ge |{\mathcal{C}}_l^{*}|\hfill & \ge |{\mathcal{C}}_r^{*}|+N_{\mathsf{\text{spl}}}[r+1:l]\hfill \\ \hfill & =|{\mathcal{C}}_r^{*}|+N_{\mathsf{\text{spl}}}[r+1:i]-N_{\mathsf{\text{spl}}}[l+1:i]\hfill \\ \hfill & =|{\mathcal{C}}_r^{*}|+N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_h[i].\hfill \end{array}$$

This proves the first statement, under the condition $l\ge r$. If l < r,

$$N_{\mathsf{\text{spl}}}[r+1:i]\le N_{\mathsf{\text{spl}}}[l+1:i]={\mathsf{\text{Unheard}}}_h[i].$$

Under this condition, the lemma is trivially true: ${\mathcal{C}}_i^h$ must be at least as long as ${\mathcal{C}}_r^{*}$, as it contains the block created in slot r.

The second statement can be obtained from the first, as follows. Observe that ${\mathcal{C}}_i^h[1:r]={\mathcal{C}}_r^{*}$, and therefore

$$|{\mathcal{C}}_i^h|=|{\mathcal{C}}_i^h[1:r]|+|{\mathcal{C}}_i^h[r+1:i]|=|{\mathcal{C}}_r^{*}|+|{\mathcal{C}}_i^h[r+1:i]|.\hspace{1em}\square$$

The remainder of this section shows that if either the $(s,k,\mathcal{I})$ consistency or the $(s,k,\mathcal{I})$-intensive chain quality is violated, then the event ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ must occur, where

The analysis for the consistency property is given in Section 5.1 and that for the chain quality property is given in Section 5.2. The two analyses have a similar outline. First, the chain growth properties (Lemmas 3 and 4) are used to lower bound the length of a certain portion of a chain, namely $\mathcal{C}[r+1:i]$. Next, the fact that the consistency (or chain quality) property is violated is used to upper bound the same quantity with the number of adversarial blocks created in that interval, $N_{\mathsf{\text{adv}}}[r+1:i]$. These bounds give us the lower bound on $N_{\mathsf{\text{adv}}}[r+1:i]$ as stated in (7).

5.1. Consistency Violation Condition

Recall, from Definition 1, that the consistency property with parameters $s,k\in \mathbb{N}$ and $\mathcal{I}\subseteq \mathcal{H}$ holds in an execution if the following event occurs:

As such, if the property is violated, it implies that at two (possibly) different points in time (i, $i\prime$), two honest parties held different chains. It is more convenient to argue in terms of events that are more local in time. To this end, define the event:

From (8), it follows that

${\mathcal{E}}_{i-\mathsf{\text{consistency}}}$ states that honest parties in $\mathcal{I}$ agree with each other at slot i, and with themselves across slots i and i + 1. If ${\mathcal{E}}_{i-\mathsf{\text{consistency}}}$ occurs for all slots $i\ge s+k$, then all parties in $\mathcal{I}$ agree with each other from slot s + k onward. This can be shown by induction on i. Therefore,

We now have all the ingredients to prove a necessary condition for consistency violation.

Lemma 5

(Consistency Violation–Necessary Condition). Suppose, in an execution, the consistency property with parameters $(s,k,\mathcal{I})$ is violated (i.e., ${\mathcal{E}}_{\mathsf{\text{consistency}}}^c$ occurs). Then, for some r < s and $i\ge s+k$,

$$N_{\mathsf{\text{adv}}}[r+1:i]\ge N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_{\mathcal{I}}[i],$$(11)

which implies that ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ occurs.

Proof.

Suppose ${\mathcal{E}}_{\mathsf{\text{consistency}}}^c$ occurs. Then, by (10), there exists $i\ge s+k$ such that ${\mathcal{E}}_{i-\mathsf{\text{consistency}}}^c$ occurs. Therefore, it suffices to show that the event ${\mathcal{E}}_{i-\mathsf{\text{consistency}}}^c$ implies (11) for some r < s. By (9), ${\mathcal{E}}_{i-\mathsf{\text{consistency}}}^c$ implies one of two events: either there are two different honest parties that have disjoint chains at slot i, or the same honest party has disjoint chains at slot i and i + 1. The arguments for both cases are presented together; they are very similar.

In the first case, let ${\mathcal{C}}_1\triangleq C_i^h,\hspace{0.17em}{\mathcal{C}}_2\triangleq C_i^{h\prime }$, and assume, without loss of generality, that $|{\mathcal{C}}_2|\ge |{\mathcal{C}}_1|$. In the second case, let ${\mathcal{C}}_1$ be $C_i^h$ and ${\mathcal{C}}_2$ be $C_{i+1}^h[1:i]$. Here too, $|{\mathcal{C}}_2|\ge |{\mathcal{C}}_1|$, as the following argument shows. In slot i + 1, party h must have adopted a new chain; otherwise, consistency would not be violated. This new chain ($C_{i+1}^h$) must be strictly longer than the chain it held at slot i ($C_i^h$, i.e., C₁). Because ${\mathcal{C}}_2$ is shorter than $C_{i+1}^h$ by at most one block, it follows that $|{\mathcal{C}}_2|\ge |{\mathcal{C}}_1|$.

In both cases, ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ are disjoint onward from slot s or before. Put differently, all blocks on the common prefix of ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ are created strictly before slot s. Let r be the slot of the last special honest block in the common prefix of ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$. Similarly, define $r\prime$ to be the slot of the last block in the common prefix of ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$. In general, $r\le r\prime$, with equality holding if and only if the last common block of ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ is special honest.

Keeping the definitions of r and $r\prime$ in mind, note that ${\mathcal{C}}_1[r+1:r\prime ]$ contains only adversarial blocks, which implies $|{\mathcal{C}}_1[r+1:r\prime ]|\le N_{\mathsf{\text{adv}}}[r+1:r\prime ]$. Moreover, observe that for every block on ${\mathcal{C}}_1[r\prime +1:i]$, there is a different block on ${\mathcal{C}}_2$ at the same height. Consider a pair of blocks at the same height, one each on ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$. Between these blocks, at least one must be adversarial, because two special honest blocks can never be at the same height on the blocktree. Therefore, $|{\mathcal{C}}_1[r\prime +1:i]|\le N_{\mathsf{\text{adv}}}[r\prime +1:i]$. Putting these inequalities together gives

$$|{\mathcal{C}}_1[r+1:i]|=|{\mathcal{C}}_1[r+1:r\prime ]|+|{\mathcal{C}}_1[r\prime +1:i]|\le N_{\mathsf{\text{adv}}}[r+1:r\prime ]+N_{\mathsf{\text{adv}}}[r\prime +1:i]=N_{\mathsf{\text{adv}}}[r+1:i].$$

Recall that for any $h\in \mathcal{I},\hspace{0.17em}{\mathsf{\text{Unheard}}}_{\mathcal{I}}[i]\ge {\mathsf{\text{Unheard}}}_h[i]$. Using this fact along with Lemma 4 gives a lower bound for $|{\mathcal{C}}_1[r+1:i]|$:

$$|{\mathcal{C}}_1[r+1:i]|\ge N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_h[i]\ge N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_{\mathcal{I}}[i].$$

Together, the upper and lower bounds for $|{\mathcal{C}}_1[r+1:i]|$ lead to (11):

$$N_{\mathsf{\text{adv}}}[r+1:i]\ge |{\mathcal{C}}_1[r+1:i]|\ge N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_{\mathcal{I}}[i].$$

We have proven that consistency violation implies (11) holds for some r < s and $i\ge s+k$. This, in turn, implies ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ occurs. In defining ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$, we have allowed for the possibility of r = s as well to include chain quality violation within the same event. □

5.2. Chain Quality Violation

The necessary condition for the chain quality property to be violated is identical to that of the consistency property begin violated, and the analysis has a similar flavor as well.

Lemma 6

(Intensive Chain Quality Violation–Necessary Condition). Suppose, in an execution, the $(s,k,\mathcal{I})$-intensive chain quality property is violated. Then, for some $r\le s$ and $i\ge s+k$,

$$N_{\mathsf{\text{adv}}}[r+1:i]\ge N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_{\mathcal{I}}[i],$$

that is, ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ occurs.

Proof.

Consider an execution where the intensive chain quality with parameters s, k, and $\mathcal{I}$ is violated. This means that for some honest party $h\in \mathcal{I}$ and $i\prime \ge s+k$, there are no special honest blocks in ${\mathcal{C}}_{i\prime }^h[s+1:s+k]$. Let $r\le s,i\ge s+k$ be chosen such that ${\mathcal{C}}_{i\prime }^h[r+1:i]$ is a maximal portion of the chain ${\mathcal{C}}_{i\prime }^h$ without any special honest blocks. Thus, r is the slot of the last special honest block on the portion of the chain ${\mathcal{C}}_{i\prime }^h[1:s]$, or zero if there is no such block. In either case, ${\mathcal{C}}_i^h[1:r]={\mathcal{C}}_r^{*}$. Similarly, if the portion of the chain ${\mathcal{C}}_{i\prime }^h[s+k+1:i\prime ]$ contains at least one special honest block, then i + 1 is the slot of the first such block; else, $i=i\prime$. We know that all blocks in ${\mathcal{C}}_{i\prime }^h[r+1:i]$ must be adversarial blocks, created in the interval $\{r+1,\dots ,i\}$. Therefore, $|{\mathcal{C}}_{i\prime }^h[r+1:i]|\le N_{\mathsf{\text{adv}}}[r+1:i].$ To prove the lemma, it thus suffices to show

$$|{\mathcal{C}}_{i\prime }^h[r+1:i]|\ge N_{\mathsf{\text{spl}}}[r+1:i]-{\mathsf{\text{Unheard}}}_h[i].$$(12)

The proof of (12) is divided into the cases $i<i\prime$ and $i=i\prime .$

($i<i\prime$). In this case, we know that i + 1 is a special honest slot, and the block created in that slot is part of the chain ${\mathcal{C}}_{i\prime }^h$. This implies the following facts:

• ${\mathcal{C}}_{i\prime }^h[1:i+1]={\mathcal{C}}_{i+1}^{*}$. Moreover, $|{\mathcal{C}}_{i\prime }^h[1:i]|=|{\mathcal{C}}_{i+1}^{*}|-1$.

• $N_{\mathsf{\text{spl}}}[r+1:i+1]-1=N_{\mathsf{\text{spl}}}[r+1:i]$.

Also, ${\mathcal{C}}_{i\prime }^h[1:r]={\mathcal{C}}_r^{*}$. Using these facts, we get

$$|{\mathcal{C}}_{i\prime }^h[r+1:i]|=|{\mathcal{C}}_{i\prime }^h[1:i]|-|{\mathcal{C}}_{i\prime }^h[1:r]|=|{\mathcal{C}}_{i+1}^{*}|-1-|{\mathcal{C}}_r^{*}|\ge N_{\mathsf{\text{spl}}}[r+1:i+1]-1=N_{\mathsf{\text{spl}}}[r+1:i].$$

The previous inequality follows from Lemma 3. This implies (12), as ${\mathsf{\text{Unheard}}}_h[i]$ is always nonnegative.

($i=i\prime$) In this case, (12) follows immediately from the second statement of Lemma 4. □

5.3. $\mathsf{\text{Reach}}$

We conclude this section by introducing the notion of $\mathsf{\text{Reach}}$, which allows us to reformulate ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ in a way that is easier to analyze.

Definition 7

(Reach). Let $\mathsf{\text{Reach}}[0]=0$, and for any $i\in \mathbb{N}$, let

$$\mathsf{\text{Reach}}[i]=\underset{j:0\le j\le i}{\max }{N}_{\mathsf{\text{adv}}}[j+1:i]-N_{\mathsf{\text{spl}}}[j+1:i].$$

In the previous definition, $N_{\mathsf{\text{adv}}}[i+1:i],N_{\mathsf{\text{spl}}}[i+1:i]$ are zero because the interval $[i+1:i]$ is empty. Thus, $\mathsf{\text{Reach}}$ is a random process that is a function of $\mathsf{\text{CharString}}$ and it takes values in ${\mathbb{Z}}_{+}$.

The Ouroboros line of works Kiayias et al. (2017), David et al. (2018), Badertscher et al. (2018), and Blum et al. (2020) define $\mathsf{\text{Reach}}[i]$ as an upper bound on the extent to which an adversarial chain can “reach” beyond any honest chain in the blocktree ${\mathcal{F}}_i$. The two definitions can be shown to be equivalent. With this definition in place, we can rewrite ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ as

This can be proved by first splitting $N_{\mathsf{\text{spl}}}[r+1:i]$ as $(N_{\mathsf{\text{spl}}}[r+1:s]+N_{\mathsf{\text{spl}}}(\mathsf{\text{CharString}}[s+1:i])$ (and likewise for $N_{\mathsf{\text{adv}}}[r+1:i]$), and then noting that for any value x,

The remaining paper is devoted to finding a bound on $\mathbb{P}({\mathcal{E}}_{\mathsf{\text{secure}}}^c)$.

6. Lemmas on Probabilistic Properties

Consider the expression of ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ in (13). To bound $\mathbb{P}({\mathcal{E}}_{\mathsf{\text{secure}}}^c)$, we need to bound the three terms $N_{\mathsf{\text{adv}}}[s+1:i]-N_{\mathsf{\text{spl}}}[s+1:i],\hspace{0.17em}{\mathsf{\text{Unheard}}}_{\mathcal{I}}[i]$ and $\mathsf{\text{Reach}}[s]$. The first two terms should be viewed as processes, that is, functions of i. These processes need to be bounded for all time (beyond slot s + k). To obtain such bounds, we work with compressed versions of these processes, obtained by sampling them at nonempty slots alone. Section 6.1 defines the necessary terms and results to perform this mapping between time scales. Sections 6.2, 6.3, and 6.4 analyze the distribution of the processes $\mathsf{\text{CharString}},\hspace{0.17em}\mathsf{\text{Unheard}}$, and $\mathsf{\text{Reach}}$, respectively. The results of this section are combined to give an upper bound on $\mathbb{P}({\mathcal{E}}_{\mathsf{\text{secure}}}^c)$ in Section 7.

6.1. Reduction to Compressed Time Scale

Define a new time scale driven by the arrival of nonempty slots: The clock ticks by one whenever a new nonempty slot occurs. Call this event-driven time scale the compressed time scale. The following notation is used to define the processes $\mathsf{\text{CharString}}$ and $\mathsf{\text{Unheard}}$ on the compressed time scale. For $s\ge 0$ and $j\ge 1$, let

In other words, $T_j^s$ is the $j\text{th}$ nonempty slot strictly after time s. Clearly, $T_j^0=T_j$. For any $s\ge 0,$ $T_1^s$ and the random variables ${\{T_j^s-T_{j-1}^s\}}_{j\ge 2}$ are i.i.d. with distribution $\mathsf{\text{geom}}(f).$ Let $\mathsf{\text{CompressedCharStrin}}{\mathsf{g}}_s$ denote the time-shifted, compressed version of relative to reference slot s:

$\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{h,s}$ and $\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{\mathcal{I},s}$, which are the compressed versions of ${\mathsf{\text{Unheard}}}_h$ and ${\mathsf{\text{Unheard}}}_{\mathcal{I}}$ respectively, are also defined in a similar manner. Finally, let $N_{\mathsf{\text{spl}}}^s$ and $N_{\mathsf{\text{adv}}}^s$ be time-shifted, compressed versions of $N_{\mathsf{\text{spl}}}$ and $N_{\mathsf{\text{adv}}}$ respectively. Specifically,

$N_{\mathsf{\text{adv}}}^s[1:j]$ is defined similarly. We now state the main result of this section.

Lemma 7.

Given $k\prime \ge 1$, let

$$\begin{array}{ll}{F}_0\hfill & =\{T_{k\prime }^s>k\} \mathit{\text{and}}\hfill \\ F_1\hfill & =\{N_{\mathsf{\text{adv}}}^s[1:j]-N_{\mathsf{\text{spl}}}^s[1:j]\hspace{0.17em}+\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{\mathcal{I},s}[j]+\mathsf{\text{Reach}}[s]\ge 0\hspace{0.17em}\mathit{\text{for}}\hspace{0.17em}\mathit{\text{some}}\hspace{0.17em}j\ge k\prime \}.\hfill \end{array}$$

Then, the event ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ satisfies ${\mathcal{E}}_{\mathsf{\text{secure}}}^c\subseteq F_0\cup F_1$, which implies $\mathbb{P}({\mathcal{E}}_{\mathsf{\text{secure}}}^c)\le \mathbb{P}(F_0)+\mathbb{P}(F_1).$

Proof.

First, both $N_{\mathsf{\text{adv}}}[s+1:i]$ and $N_{\mathsf{\text{spl}}}[s+1:i]$, as functions of i, are constant over intervals of the form $[T_j^s:T_{j+1}^s-1]$. Second, the process ${\mathsf{\text{Unheard}}}_{\mathcal{I}}[i]$ is nonincreasing over such intervals. This is because ${\mathsf{\text{Unheard}}}_{\mathcal{I}}[i]$ only increases at special honest slots. Now, suppose the event ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ holds. If j is such that $s+T_j^s$ is the last renewal time less than or equal to i, then

$$N_{\mathsf{\text{adv}}}^s[1:j]-N_{\mathsf{\text{spl}}}^s[1:j]+\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{\mathcal{I},s}[j]+\mathsf{\text{Reach}}[s]\ge 0.$$

If F₀ does not hold, then $s+T_{k\prime }^s\le s+k$. This implies that $j\ge k\prime$, and hence F₁ is true. This completes the proof of the first claim. This claim implies that $\mathbb{P}({\mathcal{E}}_{\mathsf{\text{secure}}}^c)$ is bounded above by $\mathbb{P}(F_0\cup F_1)$. This, by the union bound, is bounded above by $\mathbb{P}(F_0)+\mathbb{P}(F_1)$. This shows the second claim. □

The following lemma, proven in Appendix A, Section A.1, gives a bound on $\mathbb{P}(F_0)$, that is, $\mathbb{P}(T_{k\prime }^s>k).$

Lemma 8.

Suppose $k\prime =\lceil \mathit{\text{rkf}}\rceil$ such that $0<r<1.$ Then $\mathbb{P}(T_{k\prime }^s>k)\le \exp (-kf{(1-r)}^2/2).$

The results in the following subsections are used to bound $\mathbb{P}(F_1)$.

6.2. On $\mathsf{\text{CharString}}$

The main result of this subsection, Lemma 9, characterizes the distribution of $\mathsf{\text{CharString}}$. In essence, it specifies how to construct a process with identical distribution to $\mathsf{\text{CharString}}$. First, generate a stationary renewal process on $\mathbb{Z}$ with lifetime distribution $\mathsf{\text{geom}}(f).$ At all slots except the renewal points, set the symbol to $\perp$. Let the renewal points be indexed by $j\in \mathbb{Z}$. At each renewal point j, set the symbol to zero with probability $\alpha \mathbb{P}(\mathrm{\Delta }<g_j|g_j)$ and to one otherwise, and do so independently for every renewal point; here, g_j is the gap between the jth and $(j-1)\text{th}$ renewal point. Here, we give the proof for the one-time leader model. The identical statement for the i.i.d. leader model is proven in Appendix B.

Lemma 9

(Distribution of $\mathsf{\text{CharString}}$). The sequence of nonempty slots, $(T_j:j\in \mathbb{Z}),$ forms a stationary renewal process with lifetime distribution $\mathsf{\text{geom}}(f).$ Conditioned on $(T_j:j\in \mathbb{Z}),$ the random variables $(\mathsf{\text{CharString}}[T_j]:j\in \mathbb{Z})$ are independent and Bernoulli with the following distribution:

$$\mathbb{P}(\mathsf{\text{CharString}}[T_j]=0|T_{j\prime }:j\prime \in \mathbb{Z})=\alpha \mathbb{P}(\mathrm{\Delta }<T_j-T_{j-1}|T_j-T_{j-1})\hspace{1em}\forall j\in \mathbb{Z}.$$

In particular, $\mathsf{\text{CharString}}$ is a stationary process.

Proof.

The first claim is already established in Section 4.1; it follows from the distribution of $\mathsf{\text{LeaderString}}$. The second claim is true for $j\le 0$ by construction, as shown in Section 4.2. We now show the second claim for $j\ge 1$. Recall, from Section 4.2, $\mathsf{\text{CharString}}[T_j]=0$ if $\mathsf{\text{LeaderString}}[T_j]=0$ and $R_j<T_j-T_{j-1}$, where R_j is the delay from the last special honest slot before T_j to h_j. The sequence $(\mathsf{\text{LeaderString}}[T_j]:j\in \mathbb{Z})$ is a Bernoulli process with probability of zero being α. Moreover, it is independent of the sequence $(T_j:j\in \mathbb{Z})$. It therefore suffices to show that given $\mathsf{\text{LeaderString}}$, the sequence of random variables $(R_j:j\in \mathbb{N},\mathsf{\text{LeaderString}}[T_j]=0)$ are i.i.d. with the same distribution as Δ.

The last statement can be shown in three steps. First, given $\mathsf{\text{LeaderString}}$, the message delays are mutually independent with the same distribution as Δ. Second, the sequence $(R_j:j\in \mathbb{N},$ $\mathsf{\text{LeaderString}}[T_j]=0)$ is a subset of all the delay random variables, and whether a delay variable is in this sequence or not is independent of its value. Third, as a consequence of the one-time leader model, each R_j represents a different message’s delay. This is because the recipient h_j is always different, even if the sender $h_{j^{*}}$ may be the same for different js.

The fact that the nonempty slots form a stationary process with independent lifetimes, together with the fact that the value of $\mathsf{\text{CharString}}$ at the nonempty slots is determined by the immediate lifetime, implies that $\mathsf{\text{CharString}}$ is a stationary process. □

From Lemma 9, we get the following result, which states that the process $\mathsf{\text{CompressedCharStrin}}{\mathsf{g}}_s$ is nearly a Bernoulli process, and in fact, can be stochastically dominated by one.

Lemma 10

(Distribution of $\mathsf{\text{CompressedCharString}}$). For any $s\ge 0$,

$$\mathbb{P}(\mathsf{\text{CompressedCharStrin}}{\mathsf{g}}_s[1]=0|\mathsf{\text{CharString}}[\hspace{0.17em}:s])\ge p.$$

Furthermore, for any $s\ge 0$ and $j\ge 2$,

$$\mathbb{P}(\mathsf{\text{CompressedCharStrin}}{\mathsf{g}}_s[j]=0|\mathsf{\text{CharString}}[\hspace{0.17em}:s+T_{j-1}^s])=p.$$

Here, $p=\alpha \mathbb{P}(\mathrm{\Delta }<G)$ is the parameter defined in Definition 5, and $\mathsf{\text{CharString}}[\hspace{0.17em}:s]$ denotes the portion of $\mathsf{\text{CharString}}$ indexed by $j\in \mathbb{Z}:j\le s$.

Proof.

By the stationarity of $\mathsf{\text{CharString}}$ (from Lemma 9), it suffices to prove the lemma for s = 0. The desired result follows from Lemma 9 and carefully arguing about conditional probabilities.

Pick any $j\in \mathbb{N}$. Lemma 9 implies the following: If we condition on $(T_{j\prime }:j\prime \le j)$ and $(\mathsf{\text{CharString}}[T_{j\prime }]:j\prime \le j-1)$, the conditional probability of $\mathsf{\text{CharString}}[T_j]=0$ is $\alpha \mathbb{P}(\mathrm{\Delta }<T_j-T_{j-1}|T_j-T_{j-1})$. Now consider taking out T_j from the conditioned variables. In other words, restrict the information being conditioned on to $(T_{j\prime }:j\prime \le j-1)$ and $(\mathsf{\text{CharString}}[T_{j\prime }]:j\prime \le j-1)$. The conditional probability of $\mathsf{\text{CharString}}[T_j]=0$ is now $\alpha \mathbb{P}(\mathrm{\Delta }<T_j-T_{j-1})$, where $T_j-T_{j-1}$ is independent of Δ.

If $j\ge 2,\hspace{0.17em}{T}_j-T_{j-1}$ has the lifetime distribution, $\mathsf{\text{geom}}(f)$. Thus, the conditional probability above is simply p. For j = 1, $T_1-T_0$ has the sampled lifetime distribution, which is the sum of two independent $\mathsf{\text{geom}}(f)$ random variables minus one (see Section 4.1). This distribution stochastically dominates the $\mathsf{\text{geom}}(f)$ distribution. Therefore, the conditional probability above is lower bounded by p. Finally, $\mathsf{\text{CharString}}[\hspace{0.17em}:T_{j-1}]$ is a deterministic function of the sequences $(T_{j\prime }:j\prime \le j-1)$ and $(\mathsf{\text{CharString}}[T_{j\prime }]:j\prime \le j-1)$. Therefore, the statements of the lemma follow. □

The last result of this section gives a bound on the process $(N_{\mathsf{\text{adv}}}^s[1:j]-N_{\mathsf{\text{spl}}}^s[1:j],j\ge 1)$. It states that the process eventually remains below a line whose slope is greater than its drift. The result is proven in Appendix A, Section A.2.

Lemma 11.

For any $c<ϵ$,

$$\mathbb{P}(N_{\mathsf{\text{adv}}}^s[1:j]-N_{\mathsf{\text{spl}}}^s[1:j])\ge -cj\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\mathit{\text{for}}\hspace{0.17em}\mathit{\text{some}}\hspace{0.17em}j\ge k\prime )\le 2\hspace{0.17em}\exp (-k\prime {(ϵ-c)}^2/3).$$

6.3. On $\mathsf{\text{Unheard}}$

The main result of this section, Lemma 12, states that the marginal distribution of both ${\mathsf{\text{Unheard}}}_h$ and $\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{h,s}$ are stochastically dominated by a geometric distribution with an appropriate parameter. The statement is easy to foresee through the following understanding. A given honest party h is sent a fresh new message at every special honest slot. Therefore, ${\mathsf{\text{Unheard}}}_h[i]$ has the interpretation of the number of consecutive failed trials until the first success; here, each trial corresponds to a different special honest slot and success implies the message from that special honest slot being heard by slot i. These trials are independent. By upper bounding the probability of failure away from one, we obtain a geometric bound on ${\mathsf{\text{Unheard}}}_h[i]$.

Lemma 12

(Distribution of Unheard). Let $q\triangleq \mathbb{P}(\mathrm{\Delta }\le \mathsf{\text{geom}}(f)).$ The following statements hold:

• (a) For any $i\ge 1,\hspace{0.17em}\mathbb{P}({\mathsf{\text{Unheard}}}_h[i]>a)\le {(1-q)}^a$ for all integers $a\ge 0.$

• (b) For any $s,j\ge 1,\hspace{0.17em}\mathbb{P}(\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{h,s}[j]>a)\le {(1-q)}^a$ for all integers $a\ge 0.$

Proof.

Fix $i\ge 1.$ It is possible that i itself is a special honest slot and h has not heard it by slot i. In any case, ${\mathsf{\text{Unheard}}}_h[i]$ is less than or equal to one plus the number of consecutive special honest slots from strictly before slot i that h has not heard by slot i. The nonempty slots form both a Bernoulli process with parameter f and a renewal process. Let $D_1,D_2,\dots$ denote the lifetimes of the renewal process going backward from slot i. Thus, $i-D_1-\cdots -D_j$ is the $j\text{th}$ nonempty slot before i. The random variables D_i are independent with the $\mathsf{\text{geom}}(f)$ distribution.

The last special honest slot before slot i must be at least D₁ slots before slot i, so the probability h has heard that special honest slot is at least q. In general, for $j\ge 1$, the $j\text{th}$ from the last special honest slot before slot i must be at least D_j slots before slot i. (Here D_j is used as a lower bound on $D_1+\cdots +D_j.$) Thus, no matter which of the last j − 1 special honest slots before slot i that h has heard, the probability h hears the $j\text{th}$ from last special honest slot before i is at least q. Therefore, ${\mathsf{\text{Unheard}}}_h[i]$ can be viewed as at most one plus the number of consecutive failures in a sequence of trials, such that each successive trial is successful with probability at least q. Thus, ${\mathsf{\text{Unheard}}}_h[i]$ is stochastically dominated by the $\mathsf{\text{geom}}(q)$ distribution, which is the conclusion of (a).

The proof of (b) is obtained in a similar fashion by replacing i with $s+T_j^s$, for a fixed $s\ge 1$ and $j\ge 1.$ There is just one subtlety that we note here. If we consider the renewal process from the perspective of slot $s+T_j^s,$ which is the $j\text{th}$ renewal point after slot s, the $j\text{th}$ lifetime going backward has the sampled lifetime distribution; all the other lifetimes have the $\mathsf{\text{geom}}(f)$ distribution. The sampled lifetime distribution is equivalent to the sum of two independent $\mathsf{\text{geom}}(f)$ random variables minus one, and is stochastically greater that the typical lifetime distribution, $\mathsf{\text{geom}}(f).$ Thus, the arguments in the proof of (a) continue to hold. Importantly, these lifetimes are mutually independent. □

Lemma 13, proven in Appendix A.3, follows from the above result and the union bound.

Lemma 13.

For any $k\prime \in \mathbb{N},\hspace{0.17em}b\ge 0$ and c > 0,

$$\mathbb{P}(\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{h,s}[j]\ge b+1+c(j-k\prime )\hspace{0.17em}\mathit{\text{for}}\hspace{0.17em}\mathit{\text{some}}\hspace{0.17em}j\ge k\prime )\le \left[\frac{1}{(1-{(1-q)}^c)}\right]\exp (-bq).$$

6.4. On $\mathsf{\text{Reach}}$

In this section, we show that the distribution of $\mathsf{\text{Reach}}$ has a geometric tail. From Definition 7, it follows by induction on i that $\mathsf{\text{Reach}}$ satisfies the following recursion:

The initial condition of the recursion, $\mathsf{\text{Reach}}[0]=0$, is given in Definition 7 itself.

Next, define $\mathsf{B}$ to be the backward residual lifetime process for the locations of the nonempty slots in $\mathsf{\text{CharString}}$, counting from zero. Mathematically,

The next lemma characterizes the joint process $(\mathsf{B},\mathsf{\text{Reach}})$. The proof is given in Appendix A.4.

Lemma 14.

The process $(\mathsf{B}[i],\mathsf{\text{Reach}}[i])$ is a discrete-time Markov process with equilibrium probability mass function given by

$$\pi (b,r)=f{(1-f)}^b\left(1-\frac{1-p}{p}\right){\left(\frac{1-p}{p}\right)}^r.$$

In other words, under the equilibrium distribution, $\mathsf{B}[i]$ is independent of $\mathsf{\text{Reach}}[i],$ $\mathsf{B}[i]$ has the $\mathsf{\text{geom}}(f)-1$ distribution and $\mathsf{\text{Reach}}[i]$ has the $\mathsf{\text{geom}}((1-p)/p)-1$ distribution.

This result gives us a handle on the marginal distribution of $\mathsf{\text{Reach}}[i]$, as shown here.

Lemma 15

(Distribution of Reach). For all $i\in {\mathbb{Z}}_{+},\hspace{0.17em}a\in {\mathbb{R}}_{+},\hspace{0.17em}\mathbb{P}(\mathsf{\text{Reach}}[i]\ge a)\le {\left(\frac{1-p}{p}\right)}^a$.

Proof.

The initialization of $\mathsf{\text{Reach}}$ is $\mathsf{\text{Reach}}[0]=0.$ Consider a comparison system such that $\mathsf{\text{Reach}}[0]$ is a random variable independent of $\mathsf{\text{CharString}}$ with the $\mathsf{\text{geom}}((1-p)/p)-1$ distribution. Then in the comparison system, $((\mathsf{B}[i],\mathsf{\text{Reach}}[0]):i\ge 0)$ is a stationary Markov process, and in particular, $\mathsf{\text{Reach}}[i]$ has the $\mathsf{\text{geom}}((1-p)/p)-1$ distribution for all i. Now, for $\mathsf{\text{CharString}}$ fixed, all the variables $((\mathsf{B}[i],\mathsf{\text{Reach}}[i]):t\ge 0)$ are nondecreasing functions of the initial state $(B[0],\mathsf{\text{Reach}}[0])$, as can be readily shown by induction on i. Because the actual initial state of the original system is less than the initial state of the comparison system, it follows that $\mathsf{\text{Reach}}[i]$ in the original system is stochastically dominated by the $\mathsf{\text{geom}}((1-p)/p)-1$ distribution. □

7. Proof of Theorem 1

Theorem 1 provides an upper bound on the probability that either consistency or intensive chain quality is violated in an execution. In Section 5, we showed that if either security property is violated, then ${\mathcal{E}}_{\mathsf{\text{secure}}}^c$ must necessarily occur. Furthermore, Lemma 7 shows that $\mathbb{P}({\mathcal{E}}_{\mathsf{\text{secure}}}^c)\le \mathbb{P}(F_0)+\mathbb{P}(F_1)$ for appropriately defined events F₀ and F₁. Thus, to prove Theorem 1, it suffices to show

By Lemma 8, for any $r\in (0,1)$,

Recall from Lemma 7 that

Consider the following bounds on the terms that appear in the expression of F₁:

The first bound follows from Lemma 11 (replace c by ϵc), the second from Lemma 13 (replace b by $ϵ(c-a)k\prime$ and c by ϵc), and the third from Lemma 15 (replace a by $ϵak\prime$ and use the fact that $\log ((1+ϵ)/(1-ϵ))\ge 2ϵ$). Here, a, r, and c are free parameters belonging to the set (0, 1) and $k\prime =\lceil \mathit{\text{rkf}}\rceil$. By the union bound, (19), (20), and (21) give the following result:

In obtaining this bound, we use the following fact: for three discrete terms x, y, z, the condition $x+y+z\ge 0$ implies either $x\ge 0,\hspace{0.17em}y\ge 0$, or $z\ge 1$. We also use the fact that $\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{\mathcal{I},s}$ is the maximum of $\mathsf{\text{CompressedUnhear}}{\mathsf{d}}_{h,s}$ for all $h\in \mathcal{I}$.

With bounds on F₀ and F₁ (namely, (18) and (22)), it remains to set the free variables. Let $r=1/2,c=1/4$ and a = 1/8. This implies $k\prime \ge fk/2$. Also use the fact that $q\ge p\ge 0.5$ (see Lemma 12 for q). Last, use the bound $\left[1/(1-{(1/2)}^{ϵ/4})\right]\le (8/ϵ)$, which follows from $(1/(1-{(1-x)}^y))\le 1/xy$ for $x,y<1$. The previous steps show that (17) holds for

This concludes the proof of Theorem 1.