Efficient Byzantine Broadcast From Succinct Erasure Coding Proof System

Byzantine broadcast (BC) is a fundamental problem in distributed systems. To build communication-efficient BC protocols, erasure coding is a key tool. In systems under the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> < <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>/3 setting, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> is the total number of parties (also called replicas) and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> is the number of Byzantine failures, correct replicas can simply encode the data block through erasure coding, share data fragments, and interact to validate that the decoded data is consistent with the original data block. Such a paradigm is powerful in primitives such as BC, asynchronous verifiable information dispersal, and atomic broadcast. However, in systems with corrupt majority or even in the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> < <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>/2 setting, it becomes less straightforward to use erasure coding to build communication-efficient protocols. In this work, we introduce an erasure coding proof (ECP) system which allows the encoder to prove succinctly and non-interactively that an erasure-coded fragment is consistent with a constant-sized commitment to the original data block. Each fragment can be verified independently of the other fragments. We present two synchronous BC protocols from the ECP system, one under the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> < (1 − ϵ)<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> assumption and one under the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</i> < <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>/2 assumption, where ϵ is a constant and ϵ ∈ (0, 1). Both protocols improve the communication complexity and time complexity compared to the state-of-the-art BC protocols.