2024/05/04 by Qianyu Yu, Giuliano Losa, Yu, Qianyu +3 · 3 citations
Computer Science · #Business #Computer science #Cryptography and Security (cs.CR) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Latency (audio) #Parallel Computing and Optimization Techniques #Telecommunications
paper · pdf · doi:10.48550/arxiv.2405.02615
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2024/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
This paper presents TetraBFT, a novel unauthenticated Byzantine fault tolerant protocol for solving consensus in partial synchrony, eliminating the need for public key cryptography and ensuring resilience against computationally unbounded adversaries. TetraBFT has several compelling features: it necessitates only constant local storage, has optimal communication complexity, satisfies optimistic responsiveness -- allowing the protocol to operate at actual network speeds under ideal conditions -- and can achieve consensus in just 5 message delays, which outperforms all known unauthenticated protocols achieving the other properties listed. We validate the correctness of TetraBFT through rigorous security analysis and formal verification. Furthermore, we extend TetraBFT into a multi-shot, chained consensus protocol, making a pioneering effort in applying pipelining techniques to unauthenticated protocols. This positions TetraBFT as a practical and deployable solution for blockchain systems aiming for high efficiency.