[논문 리뷰] Signature-Free Asynchronous Byzantine Consensus with t<n/3 and O(n^2) Messages

Authors : Mostéfaoui, A., Moumen, H., & Raynal, M

Journal/Conference: 2014 ACM symposium on Principles of distributed computing

source: https://dl.acm.org/doi/abs/10.1145/2611462.2611468 

 

---

[Abstract]

This paper presents a new round-based asynchronous consensus algorithm that copes with up to t<n/3 Byzantine processes, where n is the total number of processes. In addition of not using signature, not assuming a computationally-limited adversary, while being optimal with respect to the value of t, this algorithm has several noteworthy properties: the expected number of rounds to decide is four, each round is composed of two or three communication steps and involves O(n2) messages, and a message is composed of a round number plus a single bit. To attain this goal, the consensus algorithm relies on a common coin as defined by Rabin, and a new extremely simple and powerful broadcast abstraction suited to binary values. The main target when designing this algorithm was to obtain a cheap and simple algorithm. This was motivated by the fact that, among the first-class properties, simplicity --albeit sometimes under-estimated or even ignored-- is a major one.

---

[Contributions]

• BV-broadcast
    : focus on values not on process, which not considering that "this" value has been broadcast by "this" process.
    : reduce the power of consensus in such a way that a value broadcast only Byzantine processes is never delivered to the correct processes.
• $t<n/3$ optimal with repect to $t$.
• expected number of rounds to decide is 4, per which 2~3 communication steps are required only. 
• If there are n parallel BA processes, expected number of rounds is $O(logn)$
• Message complexity is $O(n^2)$ messages per round. Each message consist of ($type$, #$round$, 1-$bit$)

---

[Computation Model]

• Network
     (Asynchronous : no bound for message delivery delay)
    + (Reliable : no loss, duplicated, modified, and created)
    + (Point-to-point : bi-directional channels which are able to identify sender)
    + (Unreliable broadcast : best-effort broadcast)   
• Failure
    : Byzantine process can send specific messages to others selectively. But no byzantine process can impersonate another process since they are connected by channels. Also cannot affect network reliability.
• Step
    : A (communication) step consists of receiving a message from another process, executing a local computation, and sending a message to some process.
  

---

[BV-broadcast]

• the method makes the consensus progress when at least $t+1$ correct processes call "$BV$-$broadcast$"[BV-Obligation]. (but if there are at least $n-t$ correct processes, eventually $BV$-$broadcast$ terminate. [BV-Termination])
• Best case: all the process $broadcast$ a same value. $broadcast$ occur only once per a process. (1 step)
• Worst case: there are two values $broadcasted$ by at least $t+1$ processes. Then $broadcast$ occur twice per a process. (2 steps) In this case, the local variable $bin$-$value{s}_i$ has all the binary value {0, 1}.
• 1~2 steps are needed.

security properties of Binary Value Broadcast

---

[Randomized Byzantine Consensus Algorithm]

There are n replicas in the network, and each replica has n parallel BA(asynchronous binary Byzantine Agreement) instances which communicate with corresponding replica.

  A process $B{A}_1$ is executed, which means that all $B{A}_1$ of $Replic{a}_k(k\in [1...n])$ conduct "asynchronous binary Byzantine Agreement (look below codes)" to decide whether include $Replic{a}_1$ in the final result or not.

 

• After disperse phase($BV$-$broadcast$), $broadcast$ the first value of $bin$-$value{s}_i$ and wait $n-f$ response values (AUX).
• Since each process choice only the "first-arrived" value, it is not guaranteed that each replica has a same value at this point. Therefore each process exchane the first value by $broadcast$ing AUX messages, and then check whether there is only one value. Otherwise all replicas repeat additional rounds with initial value($es{t}_i$) set by common coin. In this case, expected the number of rounds is 4. (2 rounds as mentioned, and coin probability 50%).
• Common coin play a role to guarantee that all the replicas have the same value. This role can be replaced by additional broadcast(Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. 2015. SignatureFree Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time. J. ACM 62, 4 (2015), 31:1–31:21.), and etc.