pith. sign in

arxiv: 2410.12755 · v3 · pith:LZ2KHF5Mnew · submitted 2024-10-16 · 💻 cs.DC

Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience

Jovan Komatovic , Joachim Neu , Tim Roughgarden This is my paper

Pith reviewed 2026-05-23 18:58 UTC · model grok-4.3

classification 💻 cs.DC
keywords MVBAByzantine agreementasynchronous networksadaptive faultshash-based protocolsoptimal complexityresilienceSMBA
0
0 comments X

The pith

Reducer achieves optimal O(n^2) message complexity for asynchronous MVBA while raising resilience to t < n/4 using only collision-resistant hashes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Reducer as an MVBA protocol that matches HMVBA's optimal message and bit complexity but improves fault tolerance from t < n/5 to t < n/4 in the asynchronous adaptive setting. It does so by introducing and composing with a new primitive called strong multi-valued Byzantine agreement, which forces the agreed value to originate from a correct process. A second protocol, Reducer++, further increases resilience to t < (1/3 - ε)n for any fixed ε > 0 by modeling hashes as random oracles, while preserving constant time and near-quadratic bit complexity. A sympathetic reader would care because these results narrow the long-standing gap between optimal complexity and optimal resilience in hash-based agreement without introducing new cryptographic assumptions beyond collision resistance.

Core claim

Reducer is an MVBA protocol that achieves O(n^2) message complexity, O(nℓ + n²λ log n) bit complexity, and O(1) time complexity while tolerating t < n/4 adaptive failures and relying exclusively on collision-resistant hash functions. Its design centers on an internal strong multi-valued Byzantine agreement (SMBA) primitive that guarantees any decided value was proposed by a correct process. Reducer++ extends the approach to t < (1/3 - ε)n for arbitrary constant ε > 0 by using random-oracle hashes to ensure termination, retaining the same asymptotic complexities with constants that depend on ε.

What carries the argument

Strong multi-valued Byzantine agreement (SMBA), a new variant of Byzantine agreement that ensures the decided value originates from a correct process and is used internally by Reducer to improve resilience without raising complexity.

If this is right

  • Hash-based asynchronous MVBA can now tolerate a larger fraction of adaptive faults while preserving the optimal O(n²) message complexity achieved by prior work.
  • SMBA serves as a reusable sub-protocol that enforces correct-process proposals inside larger agreement constructions.
  • Reducer++ demonstrates that random-oracle modeling allows resilience to approach the classical 1/3 bound arbitrarily closely while keeping time complexity constant and bit complexity quasi-quadratic.
  • The gap between optimal-complexity protocols and optimally resilient protocols is reduced, showing that collision-resistant hashes suffice for t < n/4.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The SMBA construction could be lifted to other primitives such as reliable broadcast or leader election that also require provenance guarantees.
  • Reaching exact t < n/3 without random oracles or with standard-model hashes remains open and would close the remaining resilience gap.
  • These protocols could be substituted into existing blockchain or consensus stacks to increase fault tolerance at essentially the same communication cost.

Load-bearing premise

The SMBA primitive can be realized with the claimed security and complexity bounds under only collision-resistant hashes, and this realization composes into the outer MVBA without extra assumptions on the adaptive adversary or message delivery schedule.

What would settle it

An explicit construction of SMBA (or a proof of its impossibility) that meets the stated security properties, O(n) message complexity, and near-linear bit complexity under collision-resistant hashes alone.

Figures

Figures reproduced from arXiv: 2410.12755 by Joachim Neu, Jovan Komatovic, Tim Roughgarden.

Figure 1
Figure 1. Figure 1: Depiction of HMVBA’s structure. The depiction focuses on a good iteration k, where leader(k) has disseminated its valid proposal v ⋆ (k) and the corresponding digest z ⋆ (k). We abridge leader ≜ leader(k), z ⋆ ≜ z ⋆ (k), v ⋆ ≜ v ⋆ (k). Once process pi receives n−t = 4t+1 done messages, which implies that at least (n−t)−t = 3t+1 correct processes completed their dissemination, process pi broadcasts a finish… view at source ↗
Figure 2
Figure 2. Figure 2: Depiction of Reducer’s structure. The depiction focuses on a good iteration k in which the first two SMBA invocations decide adversarial digests z1 and z2, respectively. Finally, the third invocation decides the “good” digest z ⋆ (k) of the leader(k)’s valid proposal v ⋆ (k). See [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Depiction of Reducer++’s structure. The depiction focuses on a good iteration k where correct processes decide on the leader(k)’s valid proposal v ⋆ (k) whose digest is z ⋆ (k). See Figs. 1 and 4 for “Dissem￾ination” and “Trial” sub-protocols, respectively. We abridge leader ≜ leader(k), z ⋆ ≜ z ⋆ (k), v ⋆ ≜ v ⋆ (k). p1 p2 . . . pn z ⋆ z ⋆ z ⋆ Noise ϕ ϕ ϕ . . . z ⋆ z ⋆ z ⋆ z ⋆ z ⋆ z ⋆ hash(·, ϕ) hash(·, ϕ)… view at source ↗
Figure 4
Figure 4. Figure 4: Depiction of Reducer++’s adoption procedure. The depiction focuses on a case where ϕ happens to be such that the “good” digest z ⋆ (k) is smallest according to hash(·, ϕ) and is thus adopted by all correct processes. See [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

Multi-valued validated Byzantine agreement (MVBA), a fundamental primitive of distributed computing, allows $n$ processes to agree on a valid $\ell$-bit value, despite $t$ faulty processes behaving maliciously. Among hash-based solutions for the asynchronous setting with adaptive faults, the state-of-the-art HMVBA protocol achieves optimal $O(n^2)$ message complexity, (near-)optimal $O(n \ell + n^2 \lambda \log n)$ bit complexity, and optimal $O(1)$ time complexity. However, it only tolerates $t < \frac15 n$ failures. In contrast, the best-known optimally-resilient protocol, SQ, incurs a higher bit complexity of $O(n^2 \ell + n^3 \lambda)$. This poses a fundamental question: Can a hash-based protocol be designed for the asynchronous setting with adaptive faults that simultaneously achieves optimal complexity and optimal resilience? This paper takes a significant step toward answering this question. Namely, we introduce Reducer, an MVBA protocol that retains HMVBA's optimal complexity while improving its resilience to $t < \frac14 n$. Like HMVBA and SQ, Reducer relies exclusively on collision-resistant hash functions. A key innovation in Reducer's design is its internal use of strong multi-valued Byzantine agreement (SMBA), a new variant of Byzantine agreement we introduce and construct, which ensures that the decided value was proposed by a correct process. To further advance resilience toward the optimal one-third bound, we then propose Reducer++, an MVBA protocol that tolerates up to $t < (\frac13 - \epsilon)n$ adaptive failures, for any fixed constant $\epsilon > 0$. Unlike Reducer, Reducer++ does not rely on SMBA. Instead, it employs a novel approach involving hash functions modeled as random oracles to ensure termination. Reducer++ maintains constant time complexity, quadratic message complexity, and quasi-quadratic bit complexity, with constants dependent on $\epsilon$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript introduces Reducer, an asynchronous MVBA protocol achieving O(n²) message complexity, near-optimal O(nℓ + n²λ log n) bit complexity, O(1) time complexity, and resilience t < n/4 using only collision-resistant hash functions. The key innovation is the internal use of a new SMBA primitive that forces the decided value to originate from a correct process. It further presents Reducer++ achieving t < (1/3 - ε)n for any fixed ε > 0 via random-oracle hash functions while preserving quadratic message complexity and constant time.

Significance. If the constructions and reductions hold, the work meaningfully advances hash-based asynchronous MVBA by closing the resilience gap between HMVBA (t < n/5) and optimally resilient but higher-bit-complexity protocols such as SQ, without sacrificing the optimal message and time bounds. The explicit separation of the collision-resistant Reducer from the random-oracle Reducer++ is a clear contribution.

major comments (1)
  1. [Abstract] Abstract (paragraph on Reducer design): the central claim that Reducer simultaneously achieves the stated complexity bounds and t < n/4 resilience rests on the new SMBA primitive being realizable with the claimed security properties under only collision-resistant hashes and composing correctly into the outer MVBA without hidden assumptions on adaptive scheduling; the provided description does not contain the security reduction or pseudocode needed to verify this composition step.
minor comments (1)
  1. [Abstract] The abstract states O(1) time complexity for both protocols but does not explicitly restate the bit-complexity expression for Reducer++.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and for acknowledging the potential significance of the work in advancing hash-based asynchronous MVBA. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph on Reducer design): the central claim that Reducer simultaneously achieves the stated complexity bounds and t < n/4 resilience rests on the new SMBA primitive being realizable with the claimed security properties under only collision-resistant hashes and composing correctly into the outer MVBA without hidden assumptions on adaptive scheduling; the provided description does not contain the security reduction or pseudocode needed to verify this composition step.

    Authors: The full manuscript contains the requested details beyond the abstract. Section 4 defines the SMBA primitive, gives its pseudocode construction based solely on collision-resistant hash functions, and provides the security reduction establishing that any decided value must originate from a correct process. Section 5 then shows the composition into Reducer, proving that the overall protocol achieves the claimed O(n²) message complexity, near-optimal bit complexity, O(1) time, and t < n/4 resilience in the standard asynchronous model with adaptive adversaries; the proof relies only on the usual scheduling assumptions of that model and introduces no hidden conditions. We are happy to add an explicit forward reference from the abstract to these sections if the referee finds that would improve readability. revision: partial

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper presents new protocol constructions (Reducer using SMBA, and Reducer++) rather than mathematical derivations or fitted parameters. Central claims rest on standard assumptions (collision-resistant hashes, random oracles) and explicit new primitives introduced in the work. No self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or described design. The argument is self-contained against external benchmarks with no reduction of results to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The protocols rest on standard cryptographic assumptions and introduce one new primitive; no free parameters or invented physical entities appear.

axioms (2)
  • domain assumption Collision-resistant hash functions exist and can be used to build secure protocols against adaptive adversaries
    Invoked for both Reducer and Reducer++ security; standard assumption in the field
  • domain assumption Random oracle model accurately models hash functions for termination arguments in Reducer++
    Explicitly used for Reducer++ termination guarantee
invented entities (1)
  • SMBA (strong multi-valued Byzantine agreement) no independent evidence
    purpose: Internal primitive ensuring the decided value was proposed by a correct process
    New variant introduced to enable Reducer's resilience improvement

pith-pipeline@v0.9.0 · 5904 in / 1452 out tokens · 21779 ms · 2026-05-23T18:58:19.763549+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

57 extracted references · 57 canonical work pages

  1. [1]

    In: TCC (4)

    Abraham, I., Asharov, G., Patra, A., Stern, G.: Asynchronous agreement on a core set in constant expected time and more efficient asynchronous VSS and MPC. In: TCC (4). Lecture Notes in Computer Science, vol. 15367, pp. 451–482. Springer (2024)

    work page 2024

  2. [2]

    In: PODC

    Abraham, I., Ben-David, N., Yandamuri, S.: Efficient and adaptively secure asynchronous binary agreement via binding crusader agreement. In: PODC. pp. 381–391. ACM (2022)

    work page 2022

  3. [3]

    In: PODC

    Abraham, I., Jovanovic, P., Maller, M., Meiklejohn, S., Stern, G., Tomescu, A.: Reaching consensus for asynchronous distributed key generation. In: PODC. pp. 363–373. ACM (2021)

    work page 2021

  4. [4]

    In: PODC

    Abraham, I., Malkhi, D., Spiegelman, A.: Asymptotically optimal validated asynchronous byzantine agreement. In: PODC. pp. 337–346. ACM (2019) 29

    work page 2019

  5. [5]

    Bacho, R., Lenzen, C., Loss, J., Ochsenreither, S., Papachristoudis, D.: Grandline: Adaptively secure DKG and randomness beacon with (log-)quadratic communication complexity. In: CCS. pp. 941–955. ACM (2024)

    work page 2024

  6. [6]

    Bandarupalli, A., Bhat, A., Bagchi, S., Kate, A., Reiter, M.K.: Random beacons in monte carlo: Efficient asynchronous random beacon without threshold cryptography. In: CCS. pp. 2621–2635. ACM (2024)

    work page 2024

  7. [7]

    In: PODC

    Ben-Or, M.: Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In: PODC. pp. 27–30. ACM (1983)

    work page 1983

  8. [8]

    Dis- tributed Comput.16(4), 249–262 (2003)

    Ben-Or, M., El-Yaniv, R.: Resilient-optimal interactive consistency in constant time. Dis- tributed Comput.16(4), 249–262 (2003)

    work page 2003

  9. [9]

    In: PODC

    Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience (extended abstract). In: PODC. pp. 183–192. ACM (1994)

    work page 1994

  10. [10]

    Bhat, A., Shrestha, N., Luo, Z., Kate, A., Nayak, K.: Randpiper - reconfiguration-friendly random beacons with quadratic communication. In: CCS. pp. 3502–3524. ACM (2021)

    work page 2021

  11. [11]

    Bracha, G.: Asynchronous byzantine agreement protocols. Inf. Comput.75(2), 130–143 (1987)

    work page 1987

  12. [12]

    The latest gossip on BFT consensus

    Buchman, E., Kwon, J., Milosevic, Z.: The latest gossip on BFT consensus. arXiv:1807.04938v3 [cs.DC] (2018), http://arxiv.org/abs/1807.04938v3

    work page arXiv 2018

  13. [13]

    Cachin, C., Guerraoui, R., Rodrigues, L.E.T.: Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer (2011)

    work page 2011

  14. [14]

    In: CRYPTO

    Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: CRYPTO. Lecture Notes in Computer Science, vol. 2139, pp. 524–541. Springer (2001)

    work page 2001

  15. [15]

    Cachin, C., Kursawe, K., Shoup, V.: Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. J. Cryptol.18(3), 219–246 (2005)

    work page 2005

  16. [16]

    In: SRDS

    Cachin, C., Tessaro, S.: Asynchronous verifiable information dispersal. In: SRDS. pp. 191–202. IEEE Computer Society (2005)

    work page 2005

  17. [17]

    In: STOC

    Canetti, R., Rabin, T.: Fast asynchronous byzantine agreement with optimal resilience. In: STOC. pp. 42–51. ACM (1993)

    work page 1993

  18. [18]

    ACM Trans

    Castro, M., Liskov, B.: Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst.20(4), 398–461 (2002)

    work page 2002

  19. [19]

    In: Public Key Cryptog- raphy

    Catalano, D., Fiore, D.: Vector commitments and their applications. In: Public Key Cryptog- raphy. Lecture Notes in Computer Science, vol. 7778, pp. 55–72. Springer (2013)

    work page 2013

  20. [20]

    arXiv:2501.00214v1 [cs.CR] (2024), http://arxiv.org/abs/2501.00214v1

    Chen, J.: Ociormvba: Near-optimal error-free asynchronous mvba. arXiv:2501.00214v1 [cs.CR] (2024), http://arxiv.org/abs/2501.00214v1

    work page arXiv 2024

  21. [21]

    In: SODA

    Civit, P., Dzulfikar, M.A., Gilbert, S., Guerraoui, R., Komatovic, J., Vidigueira, M., Zablotchi, I.: Partial synchrony for free: New upper bounds for byzantine agreement. In: SODA. pp. 4227–4291. SIAM (2025) 30

    work page 2025

  22. [22]

    arXiv:2002.08765v1 [cs.DC] (2020),http://arxiv.org/abs/2002.08765v1

    Crain, T.: Two more algorithms for randomized signature-free asynchronous binary byzan- tine consensus with t < n/ 3 and O(n2) messages and O(1) round expected termination. arXiv:2002.08765v1 [cs.DC] (2020),http://arxiv.org/abs/2002.08765v1

    work page arXiv 2002

  23. [23]

    Crain, T., Gramoli, V., Larrea, M., Raynal, M.: DBFT: efficient leaderless byzantine consensus and its application to blockchains. In: NCA. pp. 1–8. IEEE (2018)

    work page 2018

  24. [24]

    Das, S., Duan, S., Liu, S., Momose, A., Ren, L., Shoup, V.: Asynchronous consensus without trusted setup or public-key cryptography. In: CCS. pp. 3242–3256. ACM (2024)

    work page 2024

  25. [25]

    Das, S., Xiang, Z., Ren, L.: Asynchronous data dissemination and its applications. In: CCS. pp. 2705–2721. ACM (2021)

    work page 2021

  26. [26]

    Cryptology ePrint Archive, Paper 2023/1196 (2023),https://eprint.iacr.org/ 2023/1196

    Das, S., Xiang, Z., Tomescu, A., Spiegelman, A., Pinkas, B., Ren, L.: Verifiable secret sharing simplified. Cryptology ePrint Archive, Paper 2023/1196 (2023),https://eprint.iacr.org/ 2023/1196

    work page 2023

  27. [27]

    Das, S., Yurek, T., Xiang, Z., Miller, A., Kokoris-Kogias, L., Ren, L.: Practical asynchronous distributed key generation. In: SP. pp. 2518–2534. IEEE (2022)

    work page 2022

  28. [28]

    Duan, S., Wang, X., Zhang, H.: FIN: practical signature-free asynchronous common subset in constant time. In: CCS. pp. 815–829. ACM (2023)

    work page 2023

  29. [29]

    Cryptology ePrint Archive, Paper 2024/479 (2024),https://eprint.iacr.org/2024/479

    Feng, H., Lu, Z., Mai, T., Tang, Q.: Making hash-based MVBA great again. Cryptology ePrint Archive, Paper 2024/479 (2024),https://eprint.iacr.org/2024/479

    work page 2024

  30. [30]

    Cryptology ePrint Archive, Paper 2024/1710 (2024),https://eprint.iacr.org/2024/1710

    Feng, H., Lu, Z., Tang, Q.:eoptimal adaptively secure hash-based asynchronous common subset. Cryptology ePrint Archive, Paper 2024/1710 (2024),https://eprint.iacr.org/2024/1710

    work page 2024

  31. [31]

    Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM32(2), 374–382 (1985)

    work page 1985

  32. [32]

    In: PODC

    Fitzi, M., Garay, J.A.: Efficient player-optimal protocols for strong and differential consensus. In: PODC. pp. 211–220. ACM (2003)

    work page 2003

  33. [33]

    In: ICDCS

    Gao, Y., Lu, Y., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Efficient asynchronous byzantine agree- ment without private setups. In: ICDCS. pp. 246–257. IEEE (2022)

    work page 2022

  34. [34]

    In: NDSS

    Guo, B., Lu, Y., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Speeding Dumbo: Pushing asynchronous BFT closer to practice. In: NDSS. The Internet Society (2022)

    work page 2022

  35. [35]

    In: STOC

    Huang, S., Pettie, S., Zhu, L.: Byzantine agreement in polynomial time with near-optimal resilience. In: STOC. pp. 502–514. ACM (2022)

    work page 2022

  36. [36]

    In: SODA

    Huang, S., Pettie, S., Zhu, L.: Byzantine agreement with optimal resilience via statistical fraud detection. In: SODA. pp. 4335–4353. SIAM (2023)

    work page 2023

  37. [37]

    Chapman and Hall/CRC Press (2007)

    Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman and Hall/CRC Press (2007)

    work page 2007

  38. [38]

    Kimmett, B.: Improvement and partial simulation of King & Saia’s expected-polynomial-time Byzantine agreement algorithm. Ph.D. thesis, University of Victoria, Canada (2020) 31

    work page 2020

  39. [39]

    King, V., Saia, J.: Byzantine agreement in expected polynomial time. J. ACM63(2), 13:1– 13:21 (2016)

    work page 2016

  40. [40]

    arXiv:1812.10169v2 [cs.DC] (2018),http://arxiv.org/abs/1812.10169v2

    King, V., Saia, J.: Correction to byzantine agreement in expected polynomial time, jacm 2016. arXiv:1812.10169v2 [cs.DC] (2018),http://arxiv.org/abs/1812.10169v2

    work page arXiv 2016

  41. [41]

    ACM Trans

    Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.L.: Zyzzyva: Speculative byzantine fault tolerance. ACM Trans. Comput. Syst.27(4), 7:1–7:39 (2009)

    work page 2009

  42. [42]

    In: PODC

    Lu, Y., Lu, Z., Tang, Q., Wang, G.: Dumbo-MVBA: Optimal multi-valued validated asyn- chronous byzantine agreement, revisited. In: PODC. pp. 129–138. ACM (2020)

    work page 2020

  43. [43]

    Melnyk, D.: Byzantine Agreement on Representative Input Values Over Public Channels. Ph.D. thesis, ETH Zurich, Zürich, Switzerland (2020)

    work page 2020

  44. [44]

    In: CRYPTO

    Merkle, R.C.: A digital signature based on a conventional encryption function. In: CRYPTO. Lecture Notes in Computer Science, vol. 293, pp. 369–378. Springer (1987)

    work page 1987

  45. [45]

    Mostéfaoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous binary byzantine con- sensus with t < n/ 3, O(n2) messages, and O(1) expected time. J. ACM 62(4), 31:1–31:21 (2015)

    work page 2015

  46. [46]

    Acta Informatica54(5), 501–520 (2017)

    Mostéfaoui, A., Raynal, M.: Signature-free asynchronous byzantine systems: from multivalued to binary consensus witht < n/ 3, O(n2) messages, and constant time. Acta Informatica54(5), 501–520 (2017)

    work page 2017

  47. [47]

    In: DISC

    Nayak, K., Ren, L., Shi, E., Vaidya, N.H., Xiang, Z.: Improved extension protocols for byzan- tine broadcast and agreement. In: DISC. LIPIcs, vol. 179, pp. 28:1–28:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    work page 2020

  48. [48]

    In: FOCS

    Rabin, M.O.: Randomized byzantine generals. In: FOCS. pp. 403–409. IEEE Computer Society (1983)

    work page 1983

  49. [49]

    Journal of the Society for Industrial and Applied Mathematics8(2), 300–304 (1960)

    Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics8(2), 300–304 (1960). https://doi.org/10.1137/0108018

    work page doi:10.1137/0108018 1960

  50. [50]

    In: DISC

    de Souza, L.F., Kuznetsov, P., Tonkikh, A.: Distributed randomness from approximate agree- ment. In: DISC. LIPIcs, vol. 246, pp. 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

    work page 2022

  51. [51]

    Cryptology ePrint Archive, Paper 2023/1549 (2023),https://eprint

    Sui, X., Wang, X., Duan, S.: Signature-free atomic broadcast with optimalO(n2) messages and O(1) expected time. Cryptology ePrint Archive, Paper 2023/1549 (2023),https://eprint. iacr.org/2023/1549

    work page 2023

  52. [52]

    Zhang, H., Duan, S.: PACE: fully parallelizable BFT from reproposable byzantine agreement. In: CCS. pp. 3151–3164. ACM (2022) A MBAℓ: Pseudocode & Proof This section presentsMBAℓ, our adaptively-secure asynchronous MBA protocol employed by both Reducer and Reducer++. MBAℓ exchanges O(n2) messages and O(nℓ + n2λ log n) bits, and termi- nates in O(1) time. ...

    work page 2022

  53. [53]

    Each correct process broadcasts its proposal using theCRBλ algorithm

    work page

  54. [54]

    Due to the justification property of the CRBλ algorithm, v was proposed by a correct process toSMBAλ

    Each correct process delivers a valuev ∈ X from CRBλ. Due to the justification property of the CRBλ algorithm, v was proposed by a correct process toSMBAλ

    work page

  55. [55]

    (b) Decide some valuev′ ∈ X ∪ {⊥ MBA}

    For eachindex = 1, 2, ..., x − 1, execute the following logic: (a) Propose v to the index-th instance of the MBA primitive. (b) Decide some valuev′ ∈ X ∪ {⊥ MBA}. Now, we differentiate two cases: • If v′ ̸= ⊥MBA, then decidev′ and terminate. Importantly, the justification property of the MBA primitive ensures thatv′ was proposed by a correct process (toSM...

    work page

  56. [56]

    correct suggestions

    Decide the lexicographically smallest value from theX set. If this step is reached, it means that all values from theX set have been proposed by correct processes toSMBAλ; otherwise, correct processes would have decided in one of thex − 1 iterations. As |X | = x ∈ O(1), the modifiedSMBAλ algorithm exchanges O(xn2) messages and O(xn2ℓ) bits (where ℓ denote...

    work page

  57. [57]

    k, x ∈ {1, 2, 3}

    Therefore, quality is ensured as the probability that an adversarial value is decided is at most5 6 < 1. C.2 Proof of Complexity We now formally prove the complexity ofReducer (see Thm. 2). Message complexity.We start by proving thatReducer sends O(n2) messages in expectation. Lemma 13 (Reducer’s expected message complexity). Given n = 4 t + 1 and the exi...

    work page