PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Composition of Byzantine Agreements under Reorder Attacks

Jing Chen, Jin Dong, Jichen Li, Xuanzhi Xia, Wentao Zhou

arXiv:2609.09623v1cs.CRcs.DS

TL;DR

Existing BA composition work leaves channel attacks alongside party corruption outside the adversary model, despite the security questions posed by multi-instance executions. This paper combines those threats and develops compilers for parallel and concurrent BA. It proves matching impossibility and possibility thresholds and reports communication refinements for long messages.

  • Problem

    BA security under multi-instance execution requires examining channel attacks alongside party corruption, a threat neglected by most existing adversary models.

    Source: §1 · p. 2

  • Method

    The paper combines party and channel corruption in an adversary model and builds black-box compilers, with refined long-message primitives using erasure-correcting codes.

    Source: §8 · p. 22

  • Results

    Authenticated BA is impossible under composition when n ≤ 3t or n ≤ 2c + 2t + 1, while unauthenticated BA protocols exist when n > max{3t, 2c+2t+1}.

    Source: §8 · p. 22

  • Takeaways & Limitations

    For sufficiently long messages, refined RB and RMT protocols achieve O(n|M|) and O(|M|) communication, respectively, modulo an additive term independent of |M|.

    Source: §8 · p. 22

    The protocols' complexity is not known to be optimal, and proving complexity lower bounds in this model remains open.

    Source: §2 · p. 5

Abstract

from arXiv · show

Byzantine agreement (BA) is a foundational building block in distributed systems, and the security analysis of BA protocols under multi-instance executions has attracted increasing attention. However, most existing adversary models focus solely on party corruption and neglect important threats posed by adversarial manipulations of communication channels in the network. Through channel attacks, messages can be reordered across multiple executions and lead to violations of the protocol's security guarantees, In this work, we present the first adversary model that combines party corruption and channel attacks. Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions, supported by complementary impossibility and possibility results that match each other to form a tight bound. For the impossibility result, we show that even authenticated Byzantine agreement protocols cannot be secure under parallel composition when $n \leq 3t$ or $n \leq 2c + 2t + 1$, where $t$ and $c$ denote the number of corrupted parties and communication channels, respectively, and $n$ is the number of parties. For the possibility result, we prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition, when $n > \max\{3t, 2c+2t+1\}$. We first provide general black-box compilers that transform any single-instance secure BA protocol into one that is secure under parallel and concurrent executions without additional security assumptions. To optimize performance, we further design refined compilers using erasure-correcting codes. These refined versions significantly reduce communication overhead, particularly for long messages, where they achieve a constant multiplicative overhead compared with the original protocol, thus achieving the same asymptotic communication complexity.

1 Introduction

The paper studies Byzantine agreement under multi-instance execution, where party corruption and channel reordering can jointly threaten security. It introduces a combined adversary model, establishes tight resilience thresholds, and gives compilers for parallel and concurrent composition.

1 Introduction

  • Compositional executions create security questions beyond single-instance BA, especially without common session identifiers and when messages can be reordered across instances.The paper considers parallel and concurrent execution, where adversarial channel manipulation can cause agreement or validity violations.Source: §1 · pp. 2–3

1.1 Adversary Model

  • The adversary may corrupt up to t parties and c channels, with channel attacks possible without the communicating parties' awareness.This model captures cross-instance interactions over shared network channels.Source: §1.1 · p. 3

1.2 Our Results

  • Authenticated BA is impossible under parallel composition if n ≤ 3t or n ≤ 2c + 2t + 1, while unauthenticated BA is achievable under composition when n > max{3t, 2c+2t+1}.The impossibility and possibility results establish a tight threshold for compositional executions.Source: §1.2 · p. 3
  • Black-box compilers transform single-instance secure BA protocols for parallel execution in synchronous networks and concurrent execution in asynchronous networks.The concurrent construction uses Reliable Broadcast and Reliable Message Transmission primitives.Source: §1.2 · p. 3
  • General compilers incur an O(n) or O(n log n) communication factor, while refined primitives use erasure-correcting codes and cryptographic proof schemes to reduce long-message costs.The refined constructions shift the adversary bound from unbounded to polynomial-time; the paper summarizes compiled protocol complexity in Table 2.Source: §1.2 · pp. 3–4

2 Related Work

Prior work addresses BA composition, single-execution complexity, and network attacks, but the paper focuses on channel attacks in composed BA executions and notes that its protocol complexity is not known to be optimal.

Composition of Byzantine Agreements

  • Earlier stateless composition work studied authenticated BA, while other concurrent BA constructions assumed unique common session identifiers.Prior work also considered classical-model concurrent BA and modular parallel composition.Source: §2 · p. 4

Computation and Communication Complexity

  • Single-execution BA research includes quadratic-message protocols, randomized approaches, and lower bounds of Ω(t^2) communication for deterministic agreement.The cited work also reports improved communication under enhanced cryptographic primitives.Source: §2 · p. 4

2 Related Work

  • This paper studies compositional BA and provides polynomial communication and computation, but its protocol complexity is not known to be optimal.Further complexity improvements and lower bounds in this model remain open problems.Source: §2 · p. 5

Network Attacks

  • Network-attack studies describe channel manipulation in security settings, but do not address channel attacks in composed Byzantine agreements.Related work also discusses transaction reordering and message-loss consensus within a single protocol.Source: §2 · p. 5

3 Our Model

The model studies Byzantine agreement across parallel or concurrent executions while accounting for both party corruption and channel reorder attacks. Composition security requires agreement and validity in each instance despite a single shared setup, adversarial scheduling, and messages reordered on attacked channels.

3.1 Byzantine Agreement

  • The network is synchronous and point-to-point in most of the paper, with communication proceeding in rounds; BA requires termination and agreement, and validity when honest parties share an input.The model treats each party-instance as an interactive machine with an input, output, random tape, and communication tapes for other parties.Source: §3.1 · pp. 5, 7
  • Parallel or concurrent executions run multiple protocol instances, whose indices are not accessible to parties in the stateless setting.Parallel instances start together with rounds synchronized across instances; in concurrent composition, the adversary controls each instance’s start time and round steps independently.Source: §3.1 · pp. 5–6
  • The adversary statically corrupts up to t parties, attacks up to c channels between honest parties, and may rush its decisions within a round.The model also specifies different computation bounds: polynomial time for impossibility results and refined compilers, and unbounded adversaries for the positive results in Sections 5 and 6.Source: §3.1 · p. 6
  • A channel reorder attack can redirect messages between protocol instances in either direction on a channel between honest parties.The channel comprises the parties’ input and output tapes across all instances; unattacked channels deliver messages to the corresponding instance.Source: §3.1 · pp. 5–6

3.2 Composition Security

  • Composition security requires BA to hold in every instance under parallel or concurrent execution, with one global setup, static party corruption, and adversarial reordering on attacked channels.For unauthenticated BA, the definition omits setup and cryptographic primitives when adversaries are unbounded.Source: §3.2 · p. 7

4 Impossibility Result

The result rules out stateless authenticated Byzantine agreement under parallel composition at specified party-corruption or channel-attack thresholds. The proof sketch derives a contradiction by making honest instances indistinguishable across systems that require different outputs.

4 Impossibility Result

  • In composed executions, a signature does not identify its specific execution, so an adversary can reuse signed messages across instances.This weakens the role of public-key authentication in distinguishing execution contexts.Source: §4 · p. 7
  • No stateless authenticated BA protocol remains secure under even two parallel executions when n ≤ 3t or n ≤ 2c + 2t + 1.The theorem assumes a synchronous network and an adversary that can corrupt parties and attack channels.Source: §4 · p. 7
  • The proof sketch cross-connects instances with conflicting inputs, making an honest instance indistinguishable across systems that require it to output different values.The contradiction follows from the protocol’s agreement and validity requirements.Source: §4 · p. 7

5 Black-box Compiler for Parallel Composable BA

The section builds a parallel-composition compiler by replacing point-to-point delivery with reliable message transmission. Under the stated threshold, the compiler preserves the base protocol’s security, with linear communication overhead per message and twice as many rounds.

5.1 RMT for Parallel Composition

  • RMT has Pi send (deliver, msg, Pi, Pj) to all parties except Pj in round 0, then forwarders send it to Pj in round 1, who accepts after strictly more than (n−1)/2 copies.For n > 2t + 2c + 1, the protocol ensures message delivery through a redundancy-based approach.Source: §5.1 · p. 8
  • Under n > 2c + 2t + 1, RMT guarantees correct delivery of sent messages and prevents acceptance of messages the sender did not transmit.The stated properties apply when both sender and recipient are honest.Source: §5.1 · p. 8

5.2 Black-box Compiler

  • The black-box compiler preserves the base protocol’s internal logic and computation while replacing its message-delivery operations with RMT.The proof simulates the compiled execution in the original protocol and establishes that honest parties retain agreement and validity.Source: §5.2 · pp. 9–10
  • Replacing each point-to-point operation with RMT yields parallel-composition security when n > 2t + 2c + 1.Applied to the stateless unauthenticated protocol of Garay and Moses, this gives security for any number of parallel executions when n > 3t and n > 2c + 2t + 1.Source: §5.2 · pp. 9–10
  • The compiled protocol doubles the round count and incurs O(n) communication overhead per message.The overhead is the stated trade-off for security against message reordering in parallel compositions.Source: §5.2 · p. 10

6 Black-box Compiler for Concurrent Composition under Asynchronous Network

This section develops black-box compilers for concurrent Byzantine agreement in asynchronous networks using reliable broadcast or reliable message transmission, and analyzes the RMT approach’s security threshold and communication costs.

6 Black-box Compiler for Concurrent Composition under Asynchronous Network

  • The compiler transforms any standard asynchronous BA protocol for concurrent composition, with secure constructions of the RB and RMT primitives as its main technical contribution.Source: §6 · p. 10

6.1 Reliable Broadcast Under Concurrent Composition

  • In each RB instance, if an honest party accepts a value, every other honest party eventually accepts it, and an honest sender's broadcast is eventually accepted by all honest parties.Source: §6.1 · p. 12
  • Protocol 2 realizes concurrent asynchronous RB when n > 3t and n > 2t + 2c + 1, with communication complexity O(n^3|M| + n^3 log n).The result applies against any adversary A(t, c).Source: §6.1 · pp. 12–13
  • RMT has the sender transmit to all parties, and the receiver accepts only after collecting more than (n−1)/2 matching messages from distinct parties.The messages must share the same sender, receiver, and payload.Source: §6.1 · p. 13
  • Replacing broadcast procedures with reliable broadcast adapts Π∗ from Figure 4 of for concurrent composition, and applies generally to BA protocols relying solely on broadcast.The constructed protocol is unauthenticated and secure in an asynchronous network.Source: §6.1 · p. 13

6.2 Reliable Message Transmission Under Concurrent Composition

  • n > 2c + 2t + 1 suffices for Protocol 3’s event-driven, redundancy-based RMT to provide eventual delivery and unforgeability under concurrent executions.Lemma 15 gives communication complexity O(n|M| + n log n) for message M.Source: §6.2 · pp. 13–14
  • RMT replacement makes any asynchronous BA protocol secure under concurrent composition when n > 2t + 2c + 1.The theorem applies to a protocol tolerating up to t Byzantine corruptions and replacing all point-to-point communication with RMT.Source: §6.2 · p. 14
  • The RMT compiler preserves the original protocol’s Agreement and Validity by simulating each compiled execution as an execution of the original protocol.The proof matches honest parties’ accepted messages and resulting states across the real and ideal executions.Source: §6.2 · p. 15
  • Bracha’s single-phase RB communication grows from O(n2|M|) to O(n3|M| + n3 log n) after compilation into a concurrently secure RB protocol.The comparison is for any message length |M|.Source: §6.2 · p. 15

7 Scalable RB and RMT for Long Messages

This section develops communication-efficient reliable broadcast and message transmission for long messages under concurrent composition, using erasure-correcting codes and sequential proofs. It presents Protocol 5 and analyzes communication costs across message-length regimes for representative binary BA and asynchronous common-subset protocols.

7.3 Reliable Broadcast for Very Long Messages

  • For |M| ∈ Ω(λn log n), concurrent RB further improves to O(n|M| + λn^3 log n) using ConcurrentRMT, ConcurrentRB, and ConcurrentADD.Protocol 5 applies when |M| ≥ n log n; if at least t + 1 honest parties input M and others input M or ⊥, ConcurrentADD ensures all honest parties eventually output M.Source: §7 · p. 16, §7.3 · pp. 19–20

7.1 Erasure-Correcting Codes and Proof Schemes

  • Sequential proofs verify each encoded symbol and its position, letting receivers discard corrupted symbols as erasures before ECC decoding reconstructs the message.A Merkle-tree instantiation uses O(λ log n)-size proofs per symbol and an O(λ)-size root; collision resistance assumes polynomial-time adversaries.Source: §7.1 · pp. 16–17, §7 · p. 16

7 Scalable RB and RMT for Long Messages

  • For |M| ∈ Ω(λ log n), concurrent RMT achieves O(|M| + λn log n) when n > 2c + 2t + 1, while long-message RB costs O(n^2|M| + λn^3 log n).The RMT protocol satisfies correctness and unforgeability under concurrent composition, assuming secure ECC and sequential proofs.Source: §7 · p. 16, §7.2 · p. 17, §7.3 · p. 19

7.2 Reliable Message Transmission for Long Messages

  • Concurrent RMT encodes the message into symbols, forwards them through parties, verifies proofs, and decodes once enough valid symbols arrive.Under n > 2c + 2t + 1, the protocol can reconstruct from at least d valid symbols and prevents acceptance of forged messages.Source: §7.2 · pp. 17–18

7.3 Reliable Broadcast for Very Long Messages

  • Protocol 5 realizes concurrent reliable broadcast with O(n|M| + λn^3 log n) communication for very long messages.It requires n > 2c+2t+1 and n > 3t when |M| ∈ Ω(λn log n); compiling ADD with ConcurrentRMT raises its cost from O(n|M| + λn^2) to O(n|M| + λn^3 log n).Source: §7.3 · p. 20
  • The selected reliable-broadcast construction depends on message length: Protocol 2 for short messages, compiled Bracha broadcast for long messages, and Protocol 5 for very long messages.The respective ranges and complexities are |M| ∈ O(λ log n): O(n^3|M| + n^3 log n); |M| ∈ Ω(λ log n) ∩ O(λn log n): O(n^2|M| + λn^3 log n); and |M| ∈ Ω(λn log n): O(n|M| + λn^3 log n).Source: §7.3 · p. 20

7.4 Complexity Analysis of Compiled Protocols

  • Compiled communication is upper-bounded by the sum of message-dependent costs across invocations plus cumulative message-independent costs.The message-dependent costs use the original protocol’s total message length; the message-independent costs scale with the number of messages and the primitive’s message-independent component.Source: §7.4 · p. 21
  • For Huang et al.’s binary BA, compilation gives ˜O(n^13) at n = 3t + 1, or ˜O(n^13|L|) for multi-bit inputs.The original single-bit protocol has ˜O(n^12) communication, with the extra log n factor absorbed by the ˜O notation.Source: §7.4 · p. 21
  • For Das et al. [2], compiled ACS costs O(λn^4), O(λn^4 log n), or O(n^2|L|) across increasing input-length regimes.The respective regimes are |L| ∈ O(λ log n), |L| ∈ O(λn log n), and |L| ∈ Ω(λn^2 log n); the first bound assumes λ > log n.Source: §7.4 · p. 21
  • For Guo et al. [3], compiled ACS costs O(λn^4 log n) for |L| ∈ O(λn log n) and O(n^2|L|) for |L| ∈ Ω(λn^2 log n).The compilation uses very-long-message reliable broadcast for PB and very-long-message RMT for recovery messages.Source: §7.4 · pp. 21–22

8 Conclusion and Future Directions

The paper introduces an adversary model combining party and channel corruption, then establishes security thresholds for composed Byzantine agreement. It also identifies communication-complexity lower bounds and weaker validity notions as directions for future work.

8 Conclusion and Future Directions

  • The adversary model combines corruption of parties and communication channels, and the reorder attack is presented as theoretically interesting and practically viable.Source: §8 · p. 22
  • Authenticated BA is insecure when n ≤ 3t or n ≤ 2c + 2t + 1, while unauthenticated BA protocols are secure under parallel and concurrent composition when n > max{3t, 2c + 2t + 1}.The paper describes these positive and negative conditions as tight.Source: §8 · p. 22
  • Black-box compilers support parallel and concurrent BA composition; for sufficiently long messages, optimized RB and RMT achieve O(n|M|) and O(|M|), respectively, modulo additive terms independent of |M|.Ignoring those additive terms, the complexities match standard non-compositional RB and RMT protocols.Source: §8 · p. 22
  • Tight lower bounds on communication complexity remain an open question, including the trade-offs imposed by security against reorder attacks.Source: §8 · p. 22
  • The work uses the standard BA validity notion; whether its conclusions extend to weaker notions such as weak validity remains unresolved.The paper notes that weaker validity conditions might allow the impossibility results to be circumvented.Source: §8 · p. 22

Consensus Protocol in Figure 4 of [74]

Bracha's unauthenticated BA protocol proceeds in phases, each with three reliable-broadcast steps. Parties update their values from validated messages and use coin tossing when the decision thresholds are not met.

Consensus Protocol in Figure 4 of [74]

Asynchronous Data Dissemination

Asynchronous Data Dissemination encodes long messages into Reed–Solomon shares for dissemination and later reconstruction. If at least t + 1 honest parties provide the same input message, all honest parties eventually reconstruct and output it.

Asynchronous Data Dissemination

Proof of Theorem 4

The proof assumes an authenticated BA protocol secure under two parallel executions when n ≤ 2c + 2t + 1, then constructs systems whose required outputs contradict. The contradiction rules out that security assumption.

Proof of Theorem 4

  • For c > 0 and n ≤ 2c + 2t + 1, the assumed protocol forces an honest party in System S to output both 0 and 1.The proof combines two output properties to derive the contradiction.Source: Proof of Theorem 4 · pp. 27, 29
  • The proof models two independent parallel executions of Π, with each party represented by copies in the two executions and an adversary controlling parties and reordering channels.The abstract system also includes party inputs and network topology.Source: Proof of Theorem 4 · p. 27
  • In the 2PBA comparison, equivalent views let validity transfer the 0-input parties’ output to corresponding parties in System S.The proof establishes the view equivalences across the executions and System S before applying validity.Source: Proof of Theorem 4 · pp. 29–30
  • The symmetric 2PBA comparison establishes that B1, eT, and the specified corrupted-party instances output 1 in System S.This supplies the opposing output used in the contradiction.Source: Proof of Theorem 4 · p. 30
  • For 2PBA’, the proof uses BA agreement, rather than validity, after establishing view equivalence to infer equal outputs in System S.This is the distinct output argument in the second system construction.Source: Proof of Theorem 4 · pp. 30–31
Loading 2609.09623v1…