Not eXactly Byzantine: Efficient and Resilient TEE-Based State Machine Replication

Marc Leinweber, Hannes Hartenstein · 2025

Read Not eXactly Byzantine: Efficient and Resilient TEE-Based State Machine Replication by Marc Leinweber, Hannes Hartenstein (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-2501-11051.txt.

Introduction

Leinweber and Hartenstein (2025) present NxBFT, a protocol that keeps copies of a system in agreement using trusted execution environments. State machine replication must survive faults, and classic designs force a choice between tolerating simple crashes and tolerating malicious behavior. Their protocol targets a middle ground: replicas run inside protected hardware enclaves, which rules out the wildest attacks while keeping the design light. The agreement layer has no leader, works without timing assumptions, and spreads requests across replicas.

In the fault-free case, decisions take just two network round trips. The authors also show that crash recovery with such enclaves runs into a basic problem in fully asynchronous settings, so their design leans on timing for liveness. In tests with up to 40 replicas, NxBFT reached the highest throughput of the protocols compared, and real crash faults barely dented its performance, unlike leader-based rivals.

Catalog record

CREATORMarc Leinweber, Hannes Hartenstein
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11051

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Not eXactly Byzantine: Efficient and Resilient TEE-Based State Machine Replication Marc Leinweber, Hannes Hartenstein Abstract We propose, implement, and evaluate NxBFT, a resilient and efficient State Machine Replication protocol using Trusted Execution Environments (TEEs). NxBFT focuses on a “Not eXactly Byzantine” ( NxB ) operating model as a middle ground between crash and Byzantine fault tolerance. NxBFT’s consensus layer is asynchronous, graph-based, leaderless, and optimized for the NxB operating model, enabling load-balancing of requests between replicas and, in fault-free cases, two network round trips between decisions. We identify fundamental issues with crash recovery due the use of TEEs in asynchrony that only can be circumvented by relying on synchrony for liveness. We provide a throughput-latency trade-off analysis of NxBFT, Chained-Damysus (rotating leader), and MinBFT (static leader) for up to 40 replicas and network round trip latencies up to 150 ms. NxBFT achieves the highest throughput in all scenarios. When small latencies are required, MinBFT and Damysus are at an advantage with Damysus benefiting from the NxB model in terms of throughput for small deployments. In contrast to leader-based approaches, NxBFT’s performance is almost not impacted when actual crash faults occur. I Introduction In this paper, we focus on federations in the permissioned blockchain model, where a set of operators (federation members) are running a State Machine Replication (SMR) protocol [ 1 ] to provide a common service. We assume that the federation consists, at most, of tens of operators and typically is spread over a country or continent. We also assume a main motivation of this operating model to be sovereignty reasons, that is, to have equal power and rights. Still, we assume that the federation members run a Byzantine atomic broadcast for resilience reasons. However, we deviate from classical Byzantine fault tolerant (BFT) SMR by assuming that a replica does not show Byzantine behavior in its interaction with its clients. We consider this assumption valid for use cases where the federation members are highly regulated and manipulation towards the client is directly observable and correctable, for example when logging check-ins and check-outs as part of a ticketing system for mobility-as-a-service federation [ 2 , 3 ] . In this example, operators can be mobility providers or public parties, e.g., states of a federal state or member states of a supranational union. This scenario also generalizes to similar transaction processing tasks for electric vehicle charging or smart grid scenarios [ 4 ] and, potentially, even to some Central Bank Digital Currency [ 5 , 6 ] scenarios. These use cases require high throughput, at least in the tens of thousands of transactions per second, high availability, and resilience. Thus, we are interested in understanding how such a “Not eXactly Byzantine” ( NxB ) fault model can be exploited by protocol design and, correspondingly, to evaluate gains and trade-offs. We propose an approach called NxBFT that makes use of Trusted Execution Environments (TEEs) as well as asynchronous and graph-based atomic broadcast. TEEs are chosen since they are able to significantly increase efficiency and performance [ 7 , 8 , 9 ] . Asynchronous, graph-based atomic broadcast is chosen since it has demonstrated resilience and impressive throughput [ 10 ] . NxBFT is based on TEE-Rider [ 11 ] , an asynchronous and graph-based atomic broadcast protocol with a Byzantine fault tolerance of n>2f , where n denotes the number of replicas and f the number of faulty nodes. TEE-Rider itself is based on DAG-Rider [ 12 ] . To increase resilience, throughput and practicality , we extend the NxB fault model to an operating model: While, in general, operating in a Byzantine and asynchronous environment, we assume that operators (1) do not attack their TEE themselves, (2) do not manipulate the business logic of their application, and (3) enable sufficiently long phases of synchrony required for “maintenance work”. The NxB model allows maximum utilization of the inherent parallelism of TEE-Rider, thereby increasing throughput significantly, and to overcome fundamental issues with crash recovery. The main contribution of this paper is to show that the combination of the NxB operating model and the NxBFT approach is highly beneficial in terms of efficiency, crash resilience, and throughput. In particular, our contributions are as follows: Co-Design of Assumptions and Algorithms With NxBFT, we designed a performance and resilience-oriented SMR protocol with crash recovery optimized for the NxB model. NxBFT requires only half a network round trip for a logical round. NxBFT uses a small TEE for non-equivocation and a common coin; the goal is to reduce costly cryptography and context switches. We exploit the NxB model such that each message exchanged between replicas at the same time distributes new client requests and drives the consensus process. Practicality in the Light of Fundamental Challenges We observed that the intricacies of the combination of TEE and asynchrony have not yet been fully explored. Recovery of a crashed replica p_{c} requires resetting the TEE of p_{c} and agreement between all correct replicas on the message history of p_{c} , i.e., agreement on a checkpoint. Asynchrony makes it impossible for a replica to be sure that it has received the same of p_{c} ’s messages as other replicas, denying quorum-based checkpoint establishment. We discuss these issues and a corresponding workaround relying on synchrony for liveness. Additionally, we propose a pragmatic setup procedure. High Throughput and Resilience We implemented NxBFT and provide a throughput-latency trade-off analysis in comparison to Chained-Damysus [ 13 ] (rotating leader) and MinBFT [ 14 ] (static leader) for up to 40 replicas and network round trip latencies up to 150\,\mathrm{ms} 1 1 1 All implementations are available at https://blinded.for/review . NxBFT outperforms MinBFT and Damysus in terms of throughput in all settings. For n=40 , NxBFT achieves a throughput of 178\,\mathrm{kOp}/\mathrm{s} for datacenter deployments and 20\,\mathrm{kOp}/\mathrm{s} for world-wide deployments. The throughput-oriented optimizations based on the NxB model have a latency penalty that we deem reasonable. When small latencies are required, MinBFT and Damysus are at an advantage, with Damysus benefiting from the NxB model in terms of throughput for small deployments. In contrast to MinBFT and Damysus, NxBFT’s performance is almost not affected by actual crash faults. Please note that a general comparison between TEE-based and non-TEE-based approaches is not a goal of this paper. The remainder of this paper is structured as follows. We give an overview on related work on hybrid fault models, asynchronous consensus, and recovery procedures in Sec. II . In Sec. III , we define the NxB model and give an overview on NxBFT. We describe the NxBFT design in Sec. IV in detail. Our experimental setup and empirical findings are presented in Sec. V . We discuss the implications of our approach and future research directions in Sec. VI and conclude with Sec. VII . II Background and Related Work Since NxB is a variant of a hybrid fault model and NxBFT is constructed and optimized using atomic broadcast based on directed acyclic graphs (DAGs), we present corresponding related work. Furthermore, since recovery is particularly challenging when TEEs are used, we also address this specific aspect. We assume the reader is familiar with the concepts of State Machine Replication (SMR) [ 1 ] and of classical Byzantine fault tolerant

Read the complete text