2026-07-25T22:06:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21240 2024-10-24T07:40:08Z ddc:004 open_access

Efficient Signature-Free Validated Agreement Civit, Pierre Dzulfikar, Muhammad Ayaz Gilbert, Seth Guerraoui, Rachid Komatovic, Jovan Vidigueira, Manuel Zablotchi, Igor Validated Byzantine agreement Bit complexity Round complexity Byzantine agreement enables n processes to agree on a common L-bit value, despite up to t > 0 arbitrary failures. A long line of work has been dedicated to improving the bit complexity of Byzantine agreement in synchrony. This has culminated in COOL, an error-free (deterministically secure against a computationally unbounded adversary) solution that achieves O(nL + n² log n) worst-case bit complexity (which is optimal for L ≥ n log n according to the Dolev-Reischuk lower bound). COOL satisfies strong unanimity: if all correct processes propose the same value, only that value can be decided. Whenever correct processes do not agree a priori (there is no unanimity), they may decide a default value ⊥ from COOL. Strong unanimity is, however, not sufficient for today’s state machine replication (SMR) and blockchain protocols. These systems value progress and require a decided value to always be valid (according to a predetermined predicate), excluding default decisions (such as ⊥) even in cases where there is no unanimity a priori. Validated Byzantine agreement satisfies this property (called external validity). Yet, the best error-free (or even signature-free) validated agreement solutions achieve only O(n²L) bit complexity, a far cry from the Ω(nL+n²) Dolev-Reischuk lower bound. Is it possible to bridge this complexity gap? We answer the question affirmatively. Namely, we present two new synchronous algorithms for validated Byzantine agreement, HashExt and ErrorFreeExt, with different trade-offs. Both algorithms are (1) signature-free, (2) optimally resilient (tolerate up to t < n / 3 failures), and (3) early-stopping (terminate in O(f+1) rounds, where f ≤ t denotes the actual number of failures). On the one hand, HashExt uses only hashes and achieves O(nL + n³κ) bit complexity, which is optimal for L ≥ n²κ (where κ is the size of a hash). On the other hand, ErrorFreeExt is error-free, using no cryptography whatsoever, and achieves O((nL + n²)log n) bit complexity, which is near-optimal for any L. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Civit and Muhammad Ayaz Dzulfikar and Seth Gilbert and Rachid Guerraoui and Jovan Komatovic and Manuel Vidigueira and Igor Zablotchi 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.14 urn:nbn:de:0030-drops-212408 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode