Concepts

asymptotically optimal,” we are saying that, in the limit as the problem size approaches infinity, no other algorithm can have a better worst-case (or sometimes average-case) performance.

• Asymptotic Analysis: This is a way of describing the behavior of an algorithm as the input size grows towards infinity. It provides a high-level understanding of the algorithm in terms of its efficiency. Common notations used in asymptotic analysis include O, o, Ω, ω, and Θ.

Introduction

Problem of Atomic Broadcast and Validated Asynchronous Byzantine Agreement (VABA).

Multi-valued Agreement

• Binary agreement problem.
  • Input are [0, 1], and the early algorithm time, resilience, word communication in the random oracle model.
  • withstands up to f < n/3 Byzantine failures,
  • runs in constant expected number of asynchronous views (rounds)
  • expected communication cost is O(n2) messages of the size of one or two RSA signature
• Furture work try to achieve optimality without any cryptographic assumptions with existence of common random coin.

Defination 1: weak validity: if all honest parties propose a value V, then every honest party that terminates decides V.

• Nothing about multiple parties propose various values. Where a stronger property is the algorithm can guarantee that value proposed by honest party or _ are allowd to be returned.
• Not clear how this can solve Atomic Broadcast

Later work is to reach agreement on a sequene of updates, to prevent updates from rogue parties, the model is extended with an external validity.

Defination2: if an honest party decides on a value V, then V is externally valid.

Signature-free deterministic reduction from their binary agreement protocol. Unfortunately, BA with Weak validity only does not solve Atomic Broadcast or State Machine Replication (SMR)

Binary agreement algorithm to VABA and showed how to use it in order to implement atomic broadcast. And VABA protocol provides external validity, has optimal resilience, asymptotically optimal time, and expected message complexity O(n3).

This paper propose a open problem the expected word communication from O(n3) to O(n2).

• This paper propose a protocol, which solves Asynchronous Byzantine agreement with external validity (VABA), has optimal resilience and asymptotically optimal time. Their expected word communication is also asymptotically optimal. In particular, honest parties send a total expected O(n2) messages, which is optimal and each message is roughly the size of one or two threshold signatures.
• Techniqually:
  • Solving byzantine agreement in async model using view-change based techniques, which is traditionally used in partially sync model.
  • view-change based techniques mostly based on timeput mechanism. To adpot this to full asynchronous models, and get optimal word communication, solutions:
    • Remove timeouts.
    • Provide safety and liveness against an an adaptive adversary.
    • Reduce communication to a minimum.

n parallel leader-based threads, random leader election primitive to decide which leader is elected in hindsight. While in async model, each leader-based thread is a seperated instance

Model

Assumes

1. async message passing, n partys, adaptive adversary, trusted dealer.
2. adversary control f < n/3 parties
3. computation: bound the computational basic steps allowed by the adversary by security parameter k.
4. communication: async link controlled by the adversary. We restrict the adversary to perform no more than k number of computation steps between a message m sent and delivered.
5. termination: liveness property in distributed system requres all correct

Defination3: a variable X is probabilitically uniformly bounded if there exist a fixed polynomial T(k) and a fixed negligible functions such that Pr…

• Efficiency: number of msg generated by honest party is probabilitically uniformly bounded
• Termination: if all msg sent by honest party delivered, all honest parties terminated.
• Weak Termination: if all msg sent by honest (before they are corrupted) party delivered, all honest parties terminated.
• Complexiry: measure the word communication of the protocl as maximum over all inputs and applicable adversaries of the total number of words sent by honest parties.

Defination4: validated byzantine agreement.

• validity: if an honest party decides an a value v, then EX-VABA-VAL (v) = True.
• quality: the probability of choosing a value that was proposed by honest party is ast least 50%
• agreement: all honest party terminate decide on the same value.
• termination: if all honest parties start with externally valid values and all message set among honest parties has been deliveded, then all honest parties decides.
• efficiency: number of msg generated by the honest parties is probabilistically uniformly bounded.

Protocol

It is for async byzantine agreeemnt, secure against adaptive adversary that controls up to f < n/3 parties, with expected word communication O(n2) and running time O(1). It consists of three sub protocols:

1. Provable Broadcast.
   1. Sender sends a message containing a value and a proof for external validity to all parties.
   2. Each party validates with external validation function that the message is valid.
      1. It delivers message
      2. Threshold signs it
      3. Sends the signed share back to the sender.
   3. Sender get n-f properly signed shares, it combines them into one threshold signature and returns it.
2. Proposal Promotions.
   1. Each view, every party acts as a leader and try to propose local value to others.
   2. The distribution includes 4 steps, each involves a provable broadcast.
      1. Each party have 3 local variables: key, lock, and commit. It is the message delivered from the 2nd step to fourth step.
3. Leader Election.

---

• ← Previous Post
• Next Post →