Turritopsis: Practical Dynamic Asynchronous BFT

Recent progress of randomized fully asynchronous BFT consensus not only presents appealing performance but also ensures superior robustness against an asynchronous adversary that can arbitrarily delay network communication. But these results are mostly discussed in a static setting with fixed nodes. The root reason for the limit is the heavy dependence on a pre-configured threshold cryptosystem, which is critical to practically generate common randomness for overcoming FLP impossibility, but also fixes a designated set of participants. Even worse, most existing asynchronous BFT protocols rely on another strong assumption that messages sent among honest nodes must eventually be delivered, which could be plausible in the static setting (as all nodes can stay online forever to deliver messages) but becomes elusive in a dynamic blockchain, because a departing node might stop transmitting messages and subsequently cause inevitable message omissions as well as potential security violations To accommodate the enticing asynchronous BFT consensus into real-world blockchains where participating nodes are joining and leaving, we introduce Turritopsis, a novel dynamic asynchronous BFT framework that can (i) efficiently re-configure threshold cryptosystem to accommodate the change of consensus nodes and (ii) tolerate admissible message omissions caused by leaving participants. We first propose a dedicatedly optimized asynchronous distributed key refresh protocol that can quickly reset key materials of discrete logarithm threshold cryptosystem (e.g. BLS threshold signature), from which common randomness can be derived to ensure both safety and liveness despite the rotation of participating nodes. We then extend asynchronous BFT to tolerate a combination of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</i> Byzantine nodes and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> honest leaving nodes, where 3<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</i> + 2<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> is smaller than the total number <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> of currently participating nodes. This allows us to tolerate up to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> leaving nodes that might behave like crashes due to their departures, while simultaneously preserving maximal resilience against ꜖(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> – 2<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i>)/3˩ malicious corruptions. We instantiated Turritopsis and implemented it in Python 3. Extensive experiments were conducted, spanning a network of up to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> = 60 AWS EC2 nodes across 15 cities, revealing that Turritopsis exhibits performance closely comparable to its fixed-committee counterpart in both latency and throughput.