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

We propose, implement, and evaluate NxBFT, a practical State Machine Replication protocol that tolerates minority corruptions by using Trusted Execution Environments (TEEs). NxBFT focuses on a "Not eXactly Byzantine" operating model as a middle ground between crash and Byzantine fault tolerance. NxBFT is designed as an asynchronous protocol except for liveness of setup and recovery. As a leaderless protocol based on TEE-Rider, it provides build-in load balancing in the number of replicas, which is in contrast to leader-based and leader-rotating approaches. With quadratic communication complexity, a TEE-based common coin as source of randomness, a crash recovery procedure, solutions for request deduplication, and progress in low-load scenarios, NxBFT achieves a throughput of 400 kOp/s at an average end-to-end-latency of 1 s for 40 replicas and shows competitive performance under faults. We provide a comparison with a leader-based (MinBFT) and a leader-rotating protocol (Damysus) and analyze benefits and challenges that result from the combination of asynchrony and TEEs.