TEE is not a Healer: Rollback-Resistant Reliable Storage
Sadegh Keshavarzi, Gregory Chockler, Alexey Gotsman · 2025
Read TEE is not a Healer: Rollback-Resistant Reliable Storage by Sadegh Keshavarzi, Gregory Chockler, Alexey Gotsman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18648.txt.
Introduction
Sadegh Keshavarzi, Gregory Chockler and Alexey Gotsman wrote a 2025 paper on safe storage built on secure hardware. Chips like Intel SGX can shield code and state while a program runs. Once power is off, saved state can be rolled back to an old version without a trace. That breaks trust in the stored data.
The team models several failure types that can hit such systems. They set tight bounds on how much fault such storage can bear. Their method, TEE-Rex, rebuilds state after faults in a sound way. It needs no special counters or lasting safe storage. Both steady and shifting fault cases are covered.
Catalog record
| CREATOR | Sadegh Keshavarzi, Gregory Chockler, Alexey Gotsman |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 138 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-18648
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
TEE is not a Healer: Rollback-Resistant Reliable Storage Sadegh Keshavarzi, Gregory Chockler, Alexey Gotsman Abstract Recent advances in secure hardware technologies, such as Intel SGX or ARM TrustZone, offer an opportunity to substantially reduce the costs of Byzantine fault-tolerance by placing the program code and state within a secure enclave known as a Trusted Execution Environment (TEE) . However, the protection offered by a TEE only applies during program execution. Once power is switched off, the non-volatile portion of the program state becomes vulnerable to rollback attacks wherein it is undetectably reverted to an older version. In this paper, we consider a problem of implementing reliable read/write registers out of failure-prone replicas subject to state rollbacks. To this end, we introduce a new unified model that captures the multiple failure types that can affect a TEE-based system. We then establish tight bounds on the fault-tolerance of register constructions in this model for both the static case, where failure thresholds hold throughout the entire execution, and the dynamic case, where they only hold eventually. Our dynamic register emulation algorithm resolves a long-standing question of how to correctly rebuild replica state upon restart without relying on additional hardware assumptions such as trusted monotonic counters. \declaretheorem [name=Corollary, sibling=theorem]corollaryr \declaretheorem [name=Property, sibling=theorem]propertyr \declaretheorem [name=Lemma, sibling=theorem]lemmar University of Surrey, Guildford, [email protected] University of Surrey, Guildford, [email protected] IMDEA Software Institute, Madrid, Spain 1 Introduction 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 both message complexity [ 14 ] and latency [ 2 , 41 ] as well as the number of replicas required [ 37 , 31 , 15 ] . 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) . Additionally, applications can use integrity metadata stored inside the enclave to detect any runtime alterations to state stored outside of its protection domain. These mechanisms together can then be used to convert Byzantine failures to simple crash or omission failures, which are less expensive to tolerate [ 39 , 29 , 6 , 40 ] . 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 [ 11 ] 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 [ 34 , 38 , 7 , 40 , 12 ] . In this paper, we initiate a systematic study of theoretical foundations for building reliable distributed systems in the presence of state rollbacks. We start by introducing crash-restart-rollback ( \mathsf{CRR} ), a new unified failure model that formalizes rollbacks alongside other types of failures that can occur in a TEE-based system. In this model, the processes can use local non-volatile storage to store their states and are assumed to behave correctly while they are executing. A \mathsf{CRR} -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 assume that upon restart, a process executes an on restart handler where it can take steps to ensure it continues operating from a correct state. We then study the problem of implementing reliable read/write registers in an asynchronous message-passing system in which the register’s state is stored at a collection of n dedicated \mathsf{CRR} failure-prone replicas accessed by arbitrarily many crash-prone clients . We give fine-grained characterization of failure resilience, time complexity, and non-volatile storage requirements of a register implementation in terms of the thresholds k and r on the number of \mathsf{CRR} and rollback failures, respectively, and the threshold b on the number of correct replicas that can crash at least once, but are eventually up. We also address the cases when either r or b is a priori unknown as well as a stronger failure model where the \mathsf{CRR} failure threshold k is only guaranteed to hold eventually. For the model where the threshold k is guaranteed to hold from the beginning of every execution, our main failure resilience result establishes the following: an implementation of a wait-free atomic multi-writer/multi-reader (MWMR) register tolerating k \mathsf{CRR} failures exists if and only if n\geq 2k+\min(b,r)+1 . For the lower bound, we prove that this number of processes is necessary even for implementing a single-writer/single-reader (SWSR) obstruction-free [ 19 ] safe [ 26 ] register. Our resilience bounds demonstrate that when r\leq b , rollback failures are no different from Byzantine failures in terms of failure resilience: The number of replicas n\geq 2k+r+1 required in this case is the same as that needed for implementing Byzantine-resilient registers when at most r out of k faulty replicas can behave arbitrarily [ 17 ] . On the other hand, the bounds are separated when b<r as in this case, k -tolerant wait-free atomic register is implementable with 2k+b+1\leq n<2k+r+1 replicas, which is strictly less than n\geq 2k+r+1 replicas required by Byzantine fault-tolerant implementations. Our lower bound for non-volatile storage consumption establishes that in order to match the above resilience bound when 2k+r+1\leq n<2k+b+1 , at least 2k+r+1 replicas must store their states persistently on their local non-volatile storage. Since non-volatile storage is not protected by TEEs, applications must rely on expensive mechanisms to monitor its integrity at runtime, e.g., using TEE-protected integrity metadata, such as Merkle trees. Our results show that for some resilience levels these overheads are unavoidable. For the upper bound, we present \mathcal{A} – a k -tolerant implementation of a wait-free MWMR atomic register, which matches our resilience and non-volatile storage bounds, for both known and unknown r and b (Figure 1 ). Algorithm \mathcal{A} ’s time complexity matches that of crash fault-tolerant implementations [ 32 , 10 ] , and is therefore optimal. This stands in a sharp contrast with the Byzantine-resilient register constructions where the write and read latencies of 4 and 8 message delays are inherent even for implementing a single-writer/multi-reader (SWMR) wait-free atomic register [ 13 ] . Next, we analyze register implementability under a stronger failure model, \diamond k , where the \mathsf{CRR} failure threshold k is only guaranteed to hold from some a priori unknown time t\geq 0 . Since under \diamond k , all replicas can simultaneously crash and restart with their state rolled back, no implementation of a register with non-trivial safety properties can guarantee wait freedom in all executions. We therefore, only require wait freedom to hold conditionally in executions where either the threshold k holds from the beginning, or