Byzantine Fault Tolerant Protocols with Near-Constant Work per Node without Signatures

Philipp Schneider · 2025

Read Byzantine Fault Tolerant Protocols with Near-Constant Work per Node without Signatures by Philipp Schneider (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05377.txt.

Introduction

Philipp Schneider presents random protocols that let a network reach firm joint choices even when a fixed share of nodes cheat or fail at will. The work appeared in twenty twenty-five. Firm classic protocols need each node to sift most of the network, which costs too much in huge networks. Random probes cut that cost but past ones capped how much fault they could bear.

Schneider's protocols join facts, spread news, settle joint choices, and flip fair shared coins. They need no signed proofs and keep work per node near flat as the network grows. The core trick is a pre-built web of small witness groups. That pre-step can then serve each task again and again.

Catalog record

CREATORPhilipp Schneider
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05377

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Byzantine Fault Tolerant Protocols with Near-Constant Work per Node without Signatures Thanks: Philipp Schneider has been supported by a grant from Avalanche, Inc. to the University of Bern. We thank Christian Cachin for valuable discussions. Philipp Schneider Abstract Numerous distributed tasks have to be handled in a setting where a fraction of nodes behaves Byzantine, that is, deviates arbitrarily from the intended protocol. Resilient, deterministic protocols rely on the detection of majorities to avoid inconsistencies if there is a Byzantine minority, which requires individual nodes to handle a communication workload that is proportional to the size of the network — an intolerable disadvantage in large networks. Randomized protocols circumvent this by probing only small parts of the network, thus allowing for consistent decisions quickly and with a high level of confidence with communication that is near-constant in the network size. However, such protocols usually come with the drawback of limiting the fault tolerance of the protocol, for instance, by severely restricting the number or type of failures that the protocol can tolerate. We present randomized protocols to reliably aggregate and broadcast information, form consensus and compute common coins that tolerate a constant fraction of Byzantine failures, do not require cryptographic signatures and have a near-constant time and message complexity per node. Our main technique is to compute a system of witness committees as a pre-computation step almost optimally. This pre-computation step allows to solve the aforementioned distributed tasks repeatedly and efficiently, but may have far reaching further applications, e.g., for sharding of distributed data structures. 1 Introduction Distributed algorithms such as reliable broadcast and consensus are routinely used in applications such as maintaining replicated state machines, in particular for distributed databases, cloud computing and blockchains. When designing such algorithms, resilience to node failures is essential to ensure safety against technical malfunctions and adversarial attacks to maintain consistent system operation and trust. Algorithms for consensus and reliable broadcast are widely used but inherently challenging, since fundamental impossibility results under various synchrony assumptions of the network [ 10 , 14 ] have to be taken into account. Most deterministic algorithms ensure consistency via quorums that intersect in non-failing nodes but are usually linear in size, thus limiting scalability. Scalable randomized approaches either sacrifice resiliency [ 1 , 15 ] or rely on computationally expensive cryptography [ 12 , 3 ] . The main motivation of this paper is to address distributed problems such as consensus, reliable broadcast and computing common coins with following three main properties. • The algorithms achieve near-constant work per node, meaning that the communication load per node grows negligibly with network size. • Resilience against a constant fraction of Byzantine nodes that can deviate arbitrarily from the protocol, in a comparatively strong adversarial model. • Avoiding cryptographic primitives such as public-key cryptography, signatures, threshold schemes or verifiable random functions. This has the following advantages. First, it allows scalability to massive networks where individual nodes have relatively low bandwidth. For example, for data aggregation in vast sensor networks or industrial internet of things [ 4 ] , or for coordinating micro-grids and energy storage systems in decentralized energy grids, where thousands or even millions of nodes with limited computational power and bandwidth must collaborate while ensuring resilience towards node failures and minimizing overhead from cryptographic operations. Second, we admit a constant fraction of Byzantine nodes and at the same time respect impossibility results by restricting the adversary in reasonable ways. Third, our approach eliminates computational overhead from the typically complex cryptographic operations the necessity to maintain a secret (which can be stolen) and reliance on certain assumptions, such as a computationally bounded adversary and the existence of trapdoor one-way functions required for public-key cryptography (certainly untrue if P=NP , but not necessarily true if P\neq NP ). It also makes the solution future-proof in the event that quantum computers become practical, which will invalidate certain cryptographic protocols. Typical distributed systems that run in large-scale networks require solving fundamental distributed problems such as consensus and reliable broadcast repeatedly throughout their lifetime to ensure their consistency. This raises the natural question whether the amortized cost can be decreased by dividing algorithms into a pre-computation step and more efficient execution step to solve each individual problem instance. We answer this question affirmatively by computing a generic structure called a system of witness committees in the pre-computation step that is resilient to a constant fraction of adversarial nodes. We then leverage this structure in the execution step to solve aforementioned problems with near-constant time and workload per node. 1 1 1 While witness committees have been used in the context of reliable broadcast and consensus before to minimize total message complexity [ 12 , 3 ] , these approaches typically use only a single witness committee, have up to linear workload per node and rely heavily on cryptographic methods to obtain them. By contrast, we aim to compute a large number of such committees almost optimally without such cryptographic methods. The pre-computation step establishes a large number of small node sets, the witness committees, each containing a majority of non-failing nodes, and makes them known network-wide. We show that this approach allows for a degree of parallelization that significantly improves efficiency in terms of round complexity and per-node workload in the execution step. Systems of witness committees have potential applications beyond the problems discussed here, perhaps most prominently for sharding of blockchains. The separation into a pre-computation and execution step also introduces a degree of modularity. Notably, any assumptions that we make about the adversary are confined to the pre-computation phase to obtain a system of witness committees, as the execution phase relies only on the existence of such witness committees. This also admits the system to be permissionless to a certain degree after the pre-computation phase, since nodes can be added without jeopardizing the honest majorities within the committees. Furthermore, we believe that this generic approach allows for easier adaptation to varying performance requirements or modeling assumptions in both the pre-computation and execution phases, facilitating further improvements in future research. 1.1 Contributions We start with some basic definitions sufficient to state our contributions. We consider a network of n nodes which we denote with the set V (standing for vertices, or validators). The set of nodes V=V_{h}+V_{b} is partitioned into a set of honest nodes V_{h} that adhere to the protocol and Byzantine nodes V_{b} that may deviate arbitrarily from the protocol. Besides an upper bound t\geq|V_{b}| , this partition is unknown to honest nodes. We consider a worst case adversary controlling the Byzantine nodes V_{b} , which can be seen as the nodes V_{b} colluding in order to undermine the protocol. The network is assumed to have reliable, private point-to-point links between any pair of nodes, meaning that we assume messages are not modified when sent over the network and a receiver can always identify the sender. In this paper, the (communication) workload per node refers to the number of bits a node has to send during an algorithm. Specifically, we assume that nodes have a limited bandwidth for sending information formalized with \sigma denoting the number of bits each node may send per round. Nodes are capable to receive any

Read the complete text