PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication Complexity of Byzantine Agreement, Revisited

Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi

arXiv:1805.03391v4cs.DC

TL;DR

The paper asks whether subquadratic Byzantine Agreement can withstand strong adaptive corruption and develops protocols under standard cryptographic and PKI assumptions. It proves after-the-fact removal makes subquadratic communication impossible, while no-after-the-fact-removal protocols achieve near-optimal resilience and subquadratic communication in synchronous and partially synchronous settings.

  • Problem

    Existing BA protocols with subquadratic communication rely on restricted adaptive adversaries, motivating whether disallowing after-the-fact removal is necessary.

  • Method

    The paper proves a lower bound and constructs binary BA protocols using standard cryptography and PKI without after-the-fact removal.

  • Results

    The paper proves an Ω(f^2) communication lower bound against adversaries capable of after-the-fact removal and gives subquadratic protocols with near-optimal resilience and expected constant rounds.

  • Takeaways & Limitations

    Subquadratic multicast-based BA requires restricting after-the-fact removal and, for multicast protocols, some setup assumption.

  • Takeaways & Limitations

    The constructions assume no after-the-fact removal, while adaptive corruption can immediately exploit observed vote eligibility or corrupt a leader.

Abstract

from arXiv · show

As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an {\it adaptive} adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary {\it cannot erase the message that was already sent} --- henceforth we say that such an adversary cannot perform "after-the-fact removal". By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieves near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.

1 Introduction

The paper asks whether subquadratic Byzantine Agreement remains possible against adversaries that can erase messages after corrupting their senders, and answers that it does not. It then gives subquadratic protocols under weaker adaptivity and studies the necessity of setup assumptions.

  • Lower bound: Any randomized BA protocol requires expected Ω(f^2) communication against a strongly adaptive adversary capable of after-the-fact removal.This lower bound holds even with strong assumptions such as proof-of-work or random oracles.
  • Comparison: Existing subquadratic protocols rely on additional strong assumptions, including random oracles, proof-of-work, or secure erasure of secrets.The paper’s constructions require only the necessary no-after-the-fact-removal condition plus standard cryptographic and setup assumptions.
  • Communication model: Multicast complexity C implies pairwise communication complexity nC, so subquadratic communication requires only a sublinear number of players to multicast.The paper uses multicast because sending one message to everyone can be cheaper in large-scale peer-to-peer networks.

2 Model and Definition

The paper distinguishes synchronous and partially synchronous communication models and defines BA through agreement, termination, consistency, and validity. It measures communication by honest-node messages, with the protocols using multicast under an adaptive PKI adversary.

  • Communication model: In the synchronous model, every message from an honest node reaches every honest recipient at the beginning of the next round.The partially synchronous model instead assumes an unknown fixed message-delay bound Δ.
  • Adversary and complexity: Communication complexity is measured by messages sent by honest nodes, and multicast complexity counts honest multicasts to all nodes, including the sender itself.The adversary operates with a trusted PKI and may adaptively corrupt up to f nodes during execution.
  • Broadcast: In Byzantine broadcast, a designated sender supplies the input, and validity applies when that sender remains forever honest.Termination, consistency, and validity are required with the protocol’s stated success probability.
  • Agreement: BA agreement requires all forever-honest nodes to terminate and agree, with validity requiring output b when all forever-honest nodes receive input b.The agreement version has no designated sender and gives each node an input bit.

3 Communication Lower Bound Under a Strongly Adaptive Adversary

The paper proves that strongly adaptive adversaries capable of after-the-fact message removal impose a quadratic communication lower bound on Byzantine Agreement. The proof extends the Dolev-Reischuk indistinguishability strategy to randomized protocols by constructing adversaries that make honest executions indistinguishable while forcing inconsistency or nontermination.

  • Warmup: the Dolev-Reischuk lower bound: The proof adapts the Dolev-Reischuk strategy by partitioning nodes into a corrupt set V and remaining nodes U, then comparing two adversaries with indistinguishable views for U.Under one adversary, nodes in V ignore messages; under the other, after-the-fact removal blocks messages to a randomly selected honest node.
  • Any possibly randomized BA protocol requires at least Ω(f^2) expected communication against a strongly adaptive adversary capable of after-the-fact removal.The theorem states the lower bound for f corrupt nodes and establishes the impossibility of subquadratic communication in this model.
  • If fewer than (εf)^2 expected messages are sent, a randomly selected node in V is likely to receive few or no messages under the constructed executions.The argument uses Markov’s inequality and a random choice of the node to obtain the required low-message event.
  • The selected node is likely not to output the sender’s value, while nodes in U retain the same view and output the sender’s value.This creates either a consistency or termination violation under the adversary using after-the-fact removal.
  • The resulting error probability contradicts the assumed Byzantine Broadcast success probability, proving the quadratic lower bound.The contradiction follows from the combined event probability exceeding the permitted error threshold.

4 Subquadratic BA under Synchrony: f < (1/3 −ϵ)n

The section develops a warmup quadratic BA protocol and then reduces multicast communication using VRF-based, bit-specific eligibility while preserving consistency against adaptive corruption.

  • Warmup: A simple quadratic BA: The warmup protocol runs λ two-round iterations in which nodes follow a leader proposal or retain their previous bit, then vote and update a sticky flag.Nodes output the bit they last voted for after the final iteration.
  • Subquadratic communication through vote-specific eligibility: The protocol samples expected λ-sized vote committees through VRF eligibility, reducing the warmup protocol’s linear multicast participation per round.The section explicitly motivates improving the warmup protocol’s expected linear number of multicast messages.
  • Subquadratic communication through vote-specific eligibility: Bit-specific VRF eligibility prevents corrupting a voter after observing its message from making it eligible to vote for the opposite bit.Eligibility for voting on b is sampled independently from eligibility for voting on 1 −b, so corruption provides no extra leverage for producing conflicting votes.
  • Subquadratic communication through vote-specific eligibility: VRFs replace the idealized leader-election oracle by allowing nodes to prove eligibility for Propose messages using a separate difficulty parameter.A node attaches the VRF evaluation and proof so others can verify proposal eligibility.
  • Proof sketch: A good iteration requires a unique so-far-honest proposer and agreement between the leader’s random coin and the bit honest nodes would retain.If eligibility were not bit-specific, corrupting eligible voters could create opposite-bit votes or eliminate good iterations.

5 Subquadratic BA under Synchrony: f < (1/2 −ϵ)n

The synchronous protocol replaces quadratic all-node communication with conditional eligibility sampling, while preserving consistency and validity under adaptive corruption. It achieves expected constant rounds and subquadratic communication for f < (1/2 −ϵ)n.

  • 5 Subquadratic BA under Synchrony: f < (1/2 −ϵ)n: The warmup protocol uses four rounds per iteration—Status, Propose, Vote, and Commit—with random leaders and signed certificates.The first iteration skips Status and Propose; termination follows after receiving sufficient Commit messages.
  • 5 Subquadratic BA under Synchrony: f < (1/2 −ϵ)n: Conditional multicast and eligibility verification reduce the number of senders while replacing certificate thresholds with λ-sized samples.Status, Vote, Commit, and Terminate attempts use difficulty D, while proposals use D0; each has calibrated success probability.
  • 5 Subquadratic BA under Synchrony: f < (1/2 −ϵ)n: Consistency follows because an output certificate for b prevents any certificate for 1 −b in the same or later iterations.An honest commit sender would have observed a conflicting vote, and higher-certificate preference propagates the restriction across iterations.
  • 5 Subquadratic BA under Synchrony: f < (1/2 −ϵ)n: A good iteration occurs with constant probability before enough honest nodes terminate, and then remaining honest nodes terminate in the next round except with negligible probability.This stochastic progress argument supports the expected constant-round and O(λ)-message bounds.

6 Subquadratic BA under Partial Synchrony

The partially synchronous construction adapts the synchronous certificate protocol by doubling step lengths until they exceed the unknown delay bound. It achieves near-optimal resilience with expected O(λ∆) time and O(λ^2 log ∆) multicast complexity.

  • 6 Subquadratic BA under Partial Synchrony: Doubling the step length every λ iterations eventually reaches the unknown delay bound ∆, after which an honest leader leads to termination in expected constant iterations.The resulting expected termination time is O(λ∆) rounds.
  • 6 Subquadratic BA under Partial Synchrony: Conditional multicast replaces full multicast, and λ-sized eligibility thresholds replace 2f + 1 and weak-certificate thresholds.Eligibility is verified for Status, Propose, Vote, Commit, and Terminate messages.
  • 6 Subquadratic BA under Partial Synchrony: Consistency holds except with exp(−Ω(λ)) probability, while validity holds under the same failure probability.The consistency proof bounds the chance that enough mining attempts produce a conflicting certificate.

7 Necessity of Setup Assumptions for Sublinear Multicast Complexity

Without trusted setup, adaptive corruption enables an indistinguishability argument that rules out sublinear multicast-complexity Byzantine broadcast. The lower bound remains applicable even with random oracles or memory erasure.

  • 7 Necessity of Setup Assumptions for Sublinear Multicast Complexity: Without setup assumptions, no protocol can solve Byzantine broadcast with C multicast complexity and probability p > 5/6 under C adaptive corruptions.The result is stated for plain authenticated channels, where messages authenticate senders but no other setup is available.
  • 7 Necessity of Setup Assumptions for Sublinear Multicast Complexity: The lower bound also applies when at most C nodes send messages with probability p > 5/6, and it survives random-oracle or memory-erasure assumptions.Thus, these additional mechanisms do not remove the stated setup barrier.
  • 7 Necessity of Setup Assumptions for Sublinear Multicast Complexity: The proof structure is summarized by Figure 1 through relationships among the corrupted and honest worlds.The caption identifies the figure as describing these worlds in the sublinear multicast setting without setup assumptions.
  • 7 Necessity of Setup Assumptions for Sublinear Multicast Complexity: The proof compares four worlds in which a designated sender’s bit and a special node’s corruption status vary, using simulations and adaptive corruptions.Validity in corrupted worlds, indistinguishability for forever-honest nodes, and indistinguishability for the special node together yield a consistency violation.
  • 7 Necessity of Setup Assumptions for Sublinear Multicast Complexity: The special node’s indistinguishable views in the two honest worlds lead to a consistency violation, contradicting the assumed success probability.The argument combines the events that real and simulated executions each use at most C multicasts with the output guarantees in the corrupted worlds.

8 Additional Details on Modeling

The execution model formalizes adaptive corruption, probabilistic traces, and the secret mining functionality used by the protocols. Fmine supports probabilistic ticket mining and public verification while hiding unattempted eligibility from corrupt nodes.

  • Execution model: The model lets the adversary adaptively corrupt nodes, after which it controls their received and sent messages, while the environment supplies honest inputs and receives outputs.
  • Execution model: Security properties such as consistency and liveness are required to hold on all but a negligible fraction of probabilistic execution traces.Execution randomness comes from honest nodes, the adversary, and the environment.
  • Fmine ideal functionality: Fmine models mining attempts by flipping a message-type-specific random coin and allowing anyone to verify successful tickets.Eligibility probabilities are hard-wired through a mapping from message types to appropriate probabilities.
  • Fmine ideal functionality: The functionality remains secret because corrupt nodes cannot learn whether a so-far-honest node belongs to a message’s committee before that node attempts mining.

9 Instantiating Fmine in the Real World

The paper compiles Fmine-hybrid protocols into real-world protocols using cryptographic primitives and trusted PKI, preserving security while achieving subquadratic BA in synchronous and partially synchronous settings.

  • 9 Instantiating Fmine in the Real World: The instantiated proof and commitment schemes satisfy perfect completeness, non-erasure computational zero-knowledge, perfect knowledge extraction, perfect binding, and selective-opening hiding under standard bilinear group assumptions.These properties supply the cryptographic guarantees required by the compiler.
  • 9 Instantiating Fmine in the Real World: The compiler replaces Fmine with cryptographic components including PRFs, NIZKs, and perfectly binding, computationally hiding commitments.The construction realizes an adaptively secure VRF from adaptively secure PRFs and NIZKs.
  • 9 Instantiating Fmine in the Real World: Trusted PKI publishes CRS parameters and commitments to each node’s secret PRF key, enabling publicly verifiable mining eligibility.A node evaluates its PRF, proves correctness relative to its committed secret key, and succeeds when the output is below a difficulty threshold.
  • 9 Instantiating Fmine in the Real World: The synchronous protocol tolerates f < (1/2 − ϵ)n adaptive corruptions with expected constant rounds and χ · poly log(κ) multicast complexity.Its error probability is negligible in κ; χ is poly(κ) under standard assumptions and poly log(κ) under sub-exponential security.
  • 9 Instantiating Fmine in the Real World: The partially synchronous protocol tolerates f < (1/3 − ϵ)n adaptive corruptions with expected Δ · poly log(κ) rounds and χ · poly log(κ) · log Δ multicast complexity.The protocol also achieves consistency and validity except with negligible probability.

10 Real World is as Secure as the Fmine-Hybrid World

The paper proves that the real-world cryptographic protocol preserves the Fmine-hybrid protocol’s security through selective-opening PRF security and a sequence of hybrid arguments.

  • 10 Real World is as Secure as the Fmine-Hybrid World: Selective-opening security allows an adversary to create, evaluate, corrupt, and challenge PRF instances while preserving pseudorandomness for uncorrupted instances.Challenge outputs for an uncorrupted instance are indistinguishable from random values.
  • 10 Real World is as Secure as the Fmine-Hybrid World: Any secure PRF family provides pseudorandomness under selective opening with polynomial loss in the security reduction.The proof reduces the selective-opening guarantee to PRF security through adjacent indistinguishable hybrids.
  • 10 Real World is as Secure as the Fmine-Hybrid World: The hybrid proof transfers the Fmine-hybrid protocol’s security properties to the compiled protocol with only negligible loss.Lemma 5 establishes the intermediate hybrid bound, while later claims connect successive hybrids.
  • 10 Real World is as Secure as the Fmine-Hybrid World: Perfect binding and perfect knowledge extraction prevent the relevant bad events in Hybrid 3 except with negligible probability.These properties control commitment ambiguity and proof extraction in the cryptographic simulation.
  • 10 Real World is as Secure as the Fmine-Hybrid World: Consistency, validity, and termination are preserved in Hybrid 3 and therefore in the real-world execution except with negligible probability.The reduction shows that any real-world security violation would yield a corresponding violation in Hybrid 3.
Loading 1805.03391v4…