TEE Is Not a Healer: Rollback-Resistant Reliable Storage

Tolerating Byzantine failures plays a major role in designing modern reliable distributed systems, and in particular blockchains. Unfortunately, tolerating Byzantine failures is expensive in terms of message complexity [15], latency [2, 43], and the number of replicas required [39, 32, 16]. Recent advances in secure hardware technologies, such as Intel SGX or ARM TrustZone, offer an opportunity to substantially reduce these costs by placing the program’s code and a portion of its state in a secure enclave known as a Trusted Execution Environments (TEE). Applications can furthermore detect any runtime alterations to the state stored outside the enclave using integrity metadata stored inside it. These mechanisms together can then be used to convert Byzantine failures to simple crash or omission failures, which are less expensive to tolerate [41, 31, 7, 42].

However, a TEE is a not a panacea, because the protection it offers only applies during program execution. Once power is switched off, the non-volatile portion of the program state becomes vulnerable to tampering by an attacker. To address this, hardware manufacturers provide a sealing mechanism [12] that allows programs to encrypt a portion of their state using a device-specific key before storing it in non-volatile storage. When the machine restarts, the TEE can check whether the sealed state was indeed written by it in the past. However, it cannot determine whether this state is the most recent version. This limitation makes TEE-based systems vulnerable to rollback attacks where the sealed state is undetectably replaced with an older version [35, 40, 8, 42, 13].

In this paper we study theoretical foundations for building reliable distributed systems in the presence of rollbacks. We start by introducing crash-restart-rollback ($\mathrm{𝖢𝖱𝖱}$), a new unified failure model that formalizes rollbacks alongside other types of failures that can occur in a TEE-based system. In this model, processes can use local non-volatile storage to persist their states and are assumed to behave correctly while they are executing. A $\mathrm{𝖢𝖱𝖱}$-faulty process can permanently crash, crash and restart infinitely often, or crash and restart with the content of its non-volatile storage being undetectably reverted to an older version.

We then study the problem of implementing reliable read/write registers in an asynchronous message-passing system where the register’s state is stored at a collection of $n$ $\mathrm{𝖢𝖱𝖱}$ failure-prone replicas accessed by arbitrarily many crash-prone clients. We consider two sub-classes of the above $\mathrm{𝖢𝖱𝖱}$ failure model for replicas – static and dynamic. Static failure models assume the existence of a priori fixed thresholds restricting the number of replicas that can experience failures of various types in every execution; this is similar to the classical crash or Byzantine failure models. The dynamic failure models generalize the static ones by permitting any number of replicas to roll back in exchange for requiring that these failures do not occur too often.

We consider an asynchronous message-passing system consisting of a collection of failure-prone processes $𝒫=\{p_1,p_2,\mathrm{\dots }\}$ implementing a high-level object abstraction. The set of processes is partitioned into a set $ℛ=\{p_1,\mathrm{\dots },p_n\}$ of $n>1$ replicas, and a set $\{p_{n+1},p_{n+2},\mathrm{\dots }\}$ of possibly infinitely many clients. Similarly to the classical faulty shared memory model of [24, 3], the replicas are responsible for storing the object state, and the clients interact with the replicas to handle the requests supported by the implemented object type. To study tradeoffs between failure resilience and non-volatile storage consumption, we assume that $s\ge 0$ replicas have access to non-volatile storage.

Formally, an object implementation is a composition of client and replica automata. An execution of an implementation is a sequence of states interleaved with atomic send and receive actions starting from an initial state. The action atomicity ensures that all non-volatile storage modifications performed as part of the received message handling are failure atomic [9], i.e., their effects are either persisted in their entirety or not at all.

In this section we give a full characterization of the costs of implementing a register under static failure models in terms of its failure resilience, time complexity, and non-volatile storage requirements. For resilience, the following theorem establishes a tight bound on the total number of replicas $n$ as a function of thresholds on the number of replicas of different types.

When $r=0$, the bound in the theorem specializes to $n\ge 2k+1$, the same as for crash fault-tolerant register implementations. When $r\le b$, the bound specializes to $n\ge 2k+r+1$. This matches the known generalization [18] of the $n\ge 3k+1$ Byzantine implementability bound for registers [34, 14] to the case when at most $r$ out of $k$ faulty replicas can behave arbitrarily and the rest can crash but not deviate from the prescribed protocol. On the other hand, if , then the theorem shows that we can implement a $\mathrm{𝖢𝖱𝖱}(k,r,b)$-tolerant wait-free atomic register with replicas – strictly fewer than in the Byzantine case. We next refine Theorem 1 to additionally give a tight bound on the number of replicas that must be equipped with non-volatile storage.

Note that the constraint on $n$ in Theorem 2 implies that in Theorem 1; we illustrate the constraint in Figure 1. The above theorem shows that, when $n\ge 2k+b+1$, atomic registers can be implemented without any stable storage at all. In practice, avoiding non-volatile storage offers substantial performance gains when the register state fits within the TEE-protected RAM, as it avoids the overheads of monitoring storage integrity at runtime.

Finally, the result in Theorem 2 can be strengthened along several dimensions:

• $\mathrm{■}$

  The time complexity of the upper bound we present in §3.1 is always $4$ message delays for both writes and reads. This matches the time complexity of crash fault-tolerant implementations, which is optimal. This property stands in a sharp contrast with Byzantine-resilient register constructions, where write and read latencies of $4$ and $8$ message delays, respectively, are inherent even for single-writer/multi-reader (SWMR) wait-free atomic registers [14].

• $\mathrm{■}$

  The lower bound in Theorem 2 is established for obstruction-free safe implementations of SWSR registers.

• $\mathrm{■}$

  When either of $b$ or $r$ is unknown, a tight bound is obtained from Theorem 2 by letting $b\triangleq n$ or $r\triangleq k$.

• $\mathrm{■}$

  If the number of replicas is less than the resilience bound (), the upper bound does not sacrifice safety, but only liveness (the top-left box in Figure 1). In §4 we leverage this property to develop a register construction under dynamic failure models that do not require all failure thresholds to hold for the entire execution.

Our findings collectively demonstrate that, while existing Byzantine fault-tolerant register constructions [34, 1, 18, 14] can be used for implementing $\mathrm{𝖢𝖱𝖱}(k,r,b)$-tolerant atomic registers, they are not well-suited for this purpose due to their sub-optimal failure resilience and latency. We next present an algorithm that gives a witness for our upper bound; we defer the proofs of the other results to [26, §A].

In this section we study the implementability of registers under failure models where any number of replicas can experience $\mathrm{𝖢𝖱𝖱}$ failures throughout an execution. By Theorem 1, no register implementation can be simultaneously safe and live in all executions if . To circumvent this impossibility, we introduce a family of dynamic failure models $\mathrm{𝖢𝖱𝖱}\text{-}𝖣$, defined as follows.

We assume a constant $\mathrm{\Delta }$ such that, in any execution, every message sent by a process $p_i$ to a process $p_j$ at time $t$ is guaranteed to be received by $p_j$ by $t+\mathrm{\Delta }$, provided $p_i$ and $p_j$ are up in $[t,t+\mathrm{\Delta }]$. Note that this assumption does not make the model stronger than asynchronous: since we do not assume a lower bound on message delays or processing times, processes do not have a means to measure time passage and thus take advantage of the existence of $\mathrm{\Delta }$ [6].

Intuitively, the parameter $d$ captures the upper bound on the number of replicas that are not eventually up in $\alpha$, and must be known to any register implementation. Conditions 1 and 2 further restrict failure scenarios: either failures must be separated by at least $M$ message delays, or at most $c\ge d$ replicas can crash in $\alpha$. The former is similar to the churn-limiting assumptions used to model process participation in dynamic and reconfigurable systems [6]. The parameter $M$ is implementation-specific and captures the minimum time required for a replica to recover its state before the next crash occurs.

We show that every static failure model $\mathrm{𝖢𝖱𝖱}(k,r,b)$ from §3 is a special case of a dynamic model $\mathrm{𝖢𝖱𝖱}\text{-}𝖣(k,k+b,\text{\_})$. Thus, any $\mathrm{𝖢𝖱𝖱}\text{-}𝖣(k,k+b,\text{\_})$-tolerant register implementation is also $\mathrm{𝖢𝖱𝖱}(k,r,b)$-tolerant.

The classical crash-recovery failure model assumed that every process is equipped with durable storage that cannot be rolled back [22]. This assumption was lifted by Aguilera et al. [4], who analyzed consensus solvability as a function of the number of processes with and without durable storage. The same model was also used by Guerraoui et al. [17] to derive tight bounds for a reliable register construction. In these models the processes are assumed to know whether they are equipped with durable storage, which they can trust to be incorruptible. In contrast, in our $\mathrm{𝖢𝖱𝖱}$ model a recovering process cannot trust its non-volatile storage to be up-to-date, leading to different resilience bounds. Furthermore, in the register implementation of Guerraoui et al. a restarted replica is considered up-to-date once it accepts a single $\mathrm{𝚆𝚁𝙸𝚃𝙴}$ request. As we show in [26, §C], this leads to a safety violation.

Dinis et al. [13] proposed a rollback-recovery (RR) model to capture rollback attacks in TEE-based systems. This model is weaker than $\mathrm{𝖢𝖱𝖱}$ as it disallows permanent process crashes. Furthermore, the register implementation of Dinis et al. uses ordinary quorums for writes, without crash-consistency checks. As we show in [26, §D], this leads to a safety violation similar to the one in Example 9. The implementation also does not guarantee wait-freedom for reads. In contrast, our $\mathrm{𝖢𝖱𝖱}$ framework captures the full spectrum of failures in TEE-based systems and enables developing correct solutions for these environments.

The crash-recovery failure model where the processes do not have access to incorruptible durable storage was assumed by Chandra et al. [10], Kończak et al. [27], and Liskov et al. [30] in the context of their efforts to develop practical variants of Paxos [29] and viewstamped replication [38]. The proposed solutions, however, did not use crash-consistent quorums for storing their state, and as a result, were shown in [36] to violate safety.

Jehl et al. [25] proposed a versioning scheme similar to crash vectors that allows quickly replacing a failed replica in Paxos. This technique was subsequently generalized to the notion of crash-consistent quorums by Michael et al. [36], who also demonstrated how it can be used to implement a recoverable atomic register. However, the safety of these versioning schemes critically depends on the replicas’ ability to track their incarnations across restarts. In turn, supporting this capability in TEE-based systems requires hardware-based persistent counters. These counters are implemented using flash memory, resulting in poor write performance and quick wear-out [35]. Furthermore, they are not universally supported by TEE manufacturers, and have been recently deprecated by Intel SGX [23].

Although the technical report version [37] of the work by Michael et al. suggests that such incarnation numbers can be supported by means of a distributed mechanism, it does not provide a full implementation. In addition, while the recoverable register implementation of [36, 37] is always safe, its liveness under the static failure models requires $n=2c+1$, which is strictly worse than our bound of $n\ge d+c+1$.

Persistent monotonic hardware counters have been demonstrated in [40] to be a powerful mechanism to guard against rollback attacks. In TEE-based systems they can be used together with sealing (§1) to validate state freshness upon restart [12]. Unfortunately, these solutions inherit the drawbacks of persistent counters we explained above.

ROTE [35] guards against rollbacks using a rollback-resistant distributed counter. Its implementation relies on a two-round protocol where a new value of the counter is first written to a write quorum, and then read back from the same write quorum to validate that it was stored reliably. Although this solution is safe, it does not ensure liveness, as the same write quorum cannot be guaranteed to be available two times in a row under failures and asynchrony. Engraft [42] uses a similar protocol, so is subject to the same liveness issue.