Randomness Summit 2023 / 2023.03.30
/ Tokyo, Japan
Most algorithms solving Byzantine agreement that are implemented and used in practice today rely on some form of synchrony assumptions. Especially when used in blockchain systems, where scalability is of great importance, purely asynchronous solutions suffer from high message complexity or strong assumptions that weaken the adversary. In particular, an adaptive adversary (roughly translating to DoS attacks in practice) is difficult to overcome without any synchrony assumptions while also keeping message complexity low. We are exploring an idea targeting exactly such an algorithm. Starting from Bracha’s algorithm for randomized Byzantine agreement with quadratic message complexity, we derive a protocol for multi-valued agreement with sub-quadratic message complexity.
