Optimally Resilient Asynchronous Multi-Valued Byzantine Agreement

"Exploring the challenges and solutions in achieving optimally resilient asynchronous multi-valued Byzantine agreement protocols. This work presents a novel construction meeting key requirements and delves into round-preserving parallel composition of agreements, shedding light on probabilistic termination and composability in distributed systems."

• Byzantine Agreement
• Cryptographic Protocols
• Resilient Protocols
• Asynchronous Networks
• Multi-Valued Consensus

melai Follow

Uploaded on Oct 09, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited Ran Cohen Pouyan Forghani Juan Garay Rutvik Patel Vassilis Zikas

2. Byzantine Agreement (BA) [PSL80,LSP82] Each ??has input ?? Agreement: honest parties output same value Validity: if all honest parties start with ??= ?, common output is ? Without trusted setup, possible only if ? < ?/3 (even with crypto and randomization) [FLM85,Bor96] Building block for cryptographic protocols 2

3. Asynchronous Networks Eventual delivery channels Adversary can delay messages for arbitrary finite amount of time Can t distinguish between silent corrupted party & slow honest party! Honest party can t wait to receive messages from > ? ? parties Deterministic asynchronous BA (A-BA) is impossible [FLP83] Randomization is necessary! 3

4. Oblivious Common Coin (OCC) With constant probability, all honest parties output the same random value ? ? ?(1) rounds ? < ?/4 [Fel89] Expected ?(1) rounds ? < ?/10 [Rab83] Expected ?(1) rounds ? < ?/3 [Fel89] Binary OCC Secure channels A-BA ?(1) rounds ? < ?/3 [CR93] Multi-valued OCC generally useful for consensus tasks Enables oblivious leader election (OLE) 4

5. Asynchronous OLE Doesnt Exist! Major hole in the literature for decades! [BE03] [FG03] Binary OCC only! [CR93]/[Fel89] Point to Not immediately clear how to extend to larger domains Running log? executions in parallel agreement w.p. 1/poly(?) 5

6. This Work No existing OCC protocol is simultaneously optimally resilient asynchronous multi-valued information-theoretic We provide the first construction satisfying all 4 requirements We also investigate round-preserving parallel composition of A-BA 6

7. Probabilistic Termination and Composability How many flips expected until coin comes up heads? ?(1) How many (parallel) flips expected until ? coins all come up heads? (log?) Running PT protocols concurrently doesn t preserve expected round complexity! Motivation: composing multiple BA instances in MPC without blowing up rounds [BE03] solved concurrent BA and A-BA in expected ?(1) rounds for ? < ?/3 7

8. Ben-Or and El-Yanivs Concurrent A-BA Idea: run batch of executions per instance, for (strict) constant rounds Reduces to problem of electing a leader to coordinate Very complicated protocol, with some issues Missing building blocks: asynchronous OLE, multi-valued A-BA We address this via a new protocol that is simple and modular 8

9. Expected ?(1) round asynchronous MPC The Asynchronous Landscape, ? < ?/3 [Coh16] Expected ?(1) round concurrent A-BA [BE03] This work [BE03] Expected ?(1) round multi-valued A-BA [CR93+MR15] ?(1) round ?(1) round asynchronous OLE asynchronous binary OCC This work [CR93] P2P channels 9

10. The Multi-valued OCC Construction 10

11. Starting Point: Binary OCC [Fel89,CR93] Each party secret-shares ? random field elements Intersection of size (at least) ?/3 among all honest parties ? ? elements visible to party ?? Random field elements ?1 ?? ??1 ??1 ?2 ??2 ??2 ??? ? ??? ? ?? 11

12. A Combinatorial Lemma Random value from ? Lemma: If ? = (?2), then with constant probability: 1. At least one repeat in ? 2. All repeats lie inside ? ? = ? When ? = O(?2), at least one repeat in any constant fraction of ? w.p. (1) When ? = (?2), no repeats in ? w.p. (1) ? = ?? Birthday paradox 12

13. Applying the Lemma When ? < ?/3, common subset of indices: ? ?/3 Work over field ? of size ?2 Parties output the repeat with minimum index in local view of ? We get an ??-valued asynchronous OCC! Can generalize to arbitrary domains ? (even exponential-sized!) In particular, ? = ? asynchronous oblivious leader election 13

14. Simplified Concurrent A-BA (in expected-constant rounds) 14

15. Dispersion Issues in Asynchrony ?1 ?2 ?3 ?4 ?1 ?2 ?3 ?4 ?1 ?2 ?3 ?4 ?? ?? ?? ?1 ?2 ?3 ?3 ?4 ?1 ?2 ?2 ?1 But all honest parties will eventually receive each other s messages! (? ? parties should have an overlap of size ? ?) [BE03]: A-cast A-cast+ Spread Select concurrent A-BA Layered structure with non-black-box calls to lower-level primitives Error-prone and difficult to analyze (in fact, there are some issues with part of their analysis) 15

16. Our Solution More message exchanges and a counting argument Messages from at least ?/3 parties are received by all honest parties Is it enough? No, we also need to add a layer of validation to make sure even corrupted parties provided the right message! Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA A-BA on continuation Distribute/validate representative outputs Distribute/validate representative outputs Asynchronous oblivious leader election A-BA on leader s output A-BA on leader s output 16

17. Comparison with Synchronous Solution Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc A-BA Trunc BA Trunc BA Trunc BA Trunc BA Trunc BA Trunc BA Trunc BA Trunc BA Trunc BA A-BA on continuation Distribute/validate representative outputs Distribute representative outputs Asynchronous oblivious leader election Oblivious leader election A-BA on leader s output BA on leader s output BA on termination Concurrent BA in [BE03] Our concurrent A-BA 17

18. Summary Optimally resilient, asynchronous, multi-valued, information-theoretic OCC This feasibility result is novel and yet has been assumed in the literature First simple and sound expected ?(1) round concurrent A-BA for ? < ?/3 Composable treatment in UC 18

19. Thank you! https://eprint.iacr.org/2023/1003