Introduction

The paper studies Byzantine reliable broadcast under async networks, and imporve existing work from those aspects:

• Near-optimal communication cost: It proposes two new BRB protocols for n nodes and input M that has comm cost O(nM + n^2logn)

  • 1st uses threshold signature

  • 2nd uses error-free

• Improved Computation:

  • avoid the online error correction on the input msg

• Balanced communication: balanced multicast which balance the comm cost for BRB

  • broadcaster needs to multicast the message M while other needs to multicast coded fragments of size O(M/n + logn)

Background

• Reliable Broadcast: The goal of reliable broadcast is to have a designated broadcaster send its input message and to have all nodes output the same message.
• Byzantine Relable Broadcast: Byzantine faults that may deviate arbitrarily from the protocols
  • Imporvement History: Bracha -> Cachin and Tessaro -> Patra
  • Balanced comm cost: In all of these BRB protocols, every node, including the broadcaster, incurs the same asymptotic communication cost. Here on, we say such a BRB protocol has a balanced communication cost.
• Limitation of the SOTA RBR protocols
  • SOTA cannot reduce the comm cost to the lower bound
  • Unbalanced communicatin cost:
    • Bracha and Cachin/Tessare achieve balanced commmunication cost
    • SOTA RBR have unbalanced comm cost, broadcaster is around n times higher than other nodes => bottlenect at the broadcaster. (broadcaster sends M to all others, while each other node only communicate O(M/n + logn)) messages.
    • Thus, it requires to design a balanced and neral optimal communication for each node.
  • Inefficiency in computation
    • online error correction (OEC) algorithm introduce the extra computation (such as Reed Solomon codes)
    • whether we can improve the computation cost of Das, Xiang, and Ren [21] while preserving the same communication cost?

Contributions

• Balanced multicast: balance the communication cost of any BRB protocols.

  • All the nodes incur the same cost of O(

    M

    + nlogn)

  • Main techniques: use an additional round of interaction between nodes to help them reconstruct the input message of the broadcaster without having the broadcaster to directly send the input to all nodes.
  • With this, existing unbalanced comm BRB can be made balanced by replacing the multicast of M with our balanced multicast in a black-box manner.
• Improved computations
  • replace error correcting codes with erasure codes as much as possible.
• Near optimal communication
  • ?

System Model

Assumption

• Malicious corrupt up to t nodes.
• Arbitrarily delay any message but must eventually deliver all messages sent between honest nodes.

• S	size of set S

• Async rounds: protocol runs in 푅 asynchronous rounds if its running time is at most R times the maximum message delay between honest parties during the execution
• Phase: consists of a fixed number of rounds.

Problem Formulation

Reliable Broadcast:

• Agreement: If an honest node outputs M’ and another node outputs M’’, then M’ == M’’
• Validity: If the broadcaster is honest, all honest nodes eventually output the message M.
• Totality: if an honest node outputs a message, then every honest node eventaully outputs a message.

Metrics

Communication

• Communication Cost: Total communication cost measures the total number of bits sent by all honest nodes during the execution of the protocol.
• Per-node Communication Cost: It measures the number of bits sent by P. We say the protocol has per-node communication cost of C, if every honest node has communication cost at most C.
• We say a protocol has balanced communication, if the per-node communication cost is O(C/n) where C is the total communication cost of the protocol; otherwise, the protocol is unbalanced.

---

• ← Previous Post
• Next Post →