Error-free, information-theoretically secure asynchronous Multi-Valued Validated Byzantine Agreement (MVBA) reaches agreement on a long input message among n nodes with up to t Byzantine faults using only a common-coin assumption, with no signatures or hashing. The OciorMVBA construction attains optimal resilience n >= 3t+1 with near-optimal expected communication O(n|w| log n + n^2 log q) bits, O(log n) rounds, and O(log n) common coins by combining reliable broadcast, asynchronous complete information dispersal via erasure/error-correction codes, and a common coin; being error-free means every required MVBA property holds in every execution.
This paper introduces OciorMVBA, an error-free, information-theoretically secure asynchronous Multi-valued Validated Byzantine Agreement (MVBA) protocol. On an input message w in an n-node network wi…