2024/12/31 by Jinyuan Chen, Chen, Jinyuan
Computer Science · #Embedded Systems Design Techniques #Interconnection Networks and Systems #Real-Time Systems Scheduling
paper · pdf · doi:10.48550/arxiv.2501.00214
In this work, we propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. This protocol achieves MVBA consensus on a message \boldsymbolw with expected O(n |\boldsymbolw|log n + n2 log q) communication bits, expected O(n2) messages, expected O(log n) rounds, and expected O(log n) common coins, under optimal resilience n ≥ 3t + 1 in an n-node network, where up to t nodes may be dishonest. Here, q denotes the alphabet size of the error correction code used in the protocol. When error correction codes with a constant alphabet size (e.g., Expander Codes) are used, q becomes a constant. An MVBA protocol that guarantees all required properties without relying on any cryptographic assumptions, such as signatures or hashing, except for the common coin assumption, is said to be information-theoretically secure (IT secure). Under the common coin assumption, an MVBA protocol that guarantees all required properties in all executions is said to be error-free. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr. This protocol achieves MVBA consensus with expected O(n |\boldsymbolw| + n2 log n) communication bits, expected O(1) rounds, and expected O(1) common coins, under a relaxed resilience (RR) of n ≥ 5t + 1. Additionally, we propose a hash-based asynchronous MVBA protocol, called OciorMVBAh. This protocol achieves MVBA consensus with expected O(n |\boldsymbolw| + n3) bits, expected O(1) rounds, and expected O(1) common coins, under optimal resilience n ≥ 3t + 1.