TinyThunder: enabling asynchronous Byzantine fault tolerance with optimal communication efficiency

The paper introduces TinyThunder, an asynchronous Byzantine fault tolerance (BFT) protocol designed to minimize communication overhead during inter-node message transmission. Regardless of the original transaction sizes, TinyThunder optimizes the acknowledgment overhead for a transaction to a constant size (e.g. 8 bytes). This optimization is based on a key observation in BFT systems: each transaction is redundantly stored by at least one honest node. Instead of transmitting the original transaction, TinyThunder only needs to send a specific feature value to confirm a transaction, leading to the development of our new compact reliable broadcast protocol. Additionally, we introduce a novel block compensation protocol that ensures the consistency of recovering these feature values and enables TinyThunder to achieve the desirable property of strong validity. The implementation and evaluation of TinyThunder in large-scale wide-area network environments demonstrate its superiority over the well-known HoneyBadgerBFT, with higher throughput (increased by 122%) and lower latency (reduced by 54%). Notably, TinyThunder also exhibits significant bandwidth savings for larger individual transaction sizes. For transactions of 250B in size, TinyThunder reduces bandwidth consumption by 56% compared to HoneyBadgerBFT.