Multi-Threshold Byzantine Fault Tolerance

Paper: Multi-Threshold Byzantine Fault Tolerance. Atsuki Momose, and Ling Ren. 2021

Overview

This is a Byzantine Fault Tolerant SMR Protocol where the standard \(t

  • \(\beta_a\): Number of safety faults in partial synchrony.
  • \(\gamma_a\): Number of liveness faults in partial synchrony.
  • \(\beta_s\): Number of safety faults in bounded synchrony.
  • \(\gamma_s\): Number of liveness faults in bounded synchrony.

Constraints Summary

The following constraints always hold since synchrony assumptions are stronger than asynchrony assumptions:

  • \(\beta_a \le \beta_s\)
  • \(\gamma_{a} \le \gamma_{s}\)

This work also focuses on the \(\gamma<\beta\) case, i.e., safety is more important than liveness.

Notes

  • It is an SMR protocol.
  • It works in both the synchronous and partially synchronous network model.
    • It uses the non-lock step network model.
  • It is adaptively secure.
  • It seems that the number of safety and liveness faults can intersect.
  • In this paper, it is not clear what the definition of "safety" fault is. Can it send blame messages when it is time to propose? Is safety + liveness fault = a Byzantine fault? If not, why is it a generalization of the \(t
  • I think the protocol assumes a clock synchronization protocol. It is unclear whether the clock synchronization protocol exists in this multi-threshold model?

RBC Definition

_20230308_232117SCR-20230308-wf3.png

Reliable Broadcast can be achieved if and only if \(2\gamma_s+\beta_a < n\)

Proof theorem

Proof by lower-bound in the sync-psync timing model for the RBC problem.

SCR-20230308-pbq.png

Proof

_20230308_181603SCR-20230308-pcj.png

_20230308_181656SCR-20230308-pdy.png

My understanding

_20230308_182918IMG_0835.jpeg

Optimal protocol with \(\beta_{a}+2\gamma_{s}\lt n\), \(\beta_{s}\lt n\), \(\gamma_{s} \lt n/2\) and \(\gamma_{a}<\min{\beta_{a},\gamma_{s}}\)

The protocol

_20230308_222656SCR-20230308-v5p.png

We need to use quorum size of \(|C|=n-\gamma_{s}\)

  • Since the protocol needs to be live in both synchrony and asynchrony, we need \(|C|<=n-\gamma_{a}\) and \(|C|<=n-\gamma_{s}\)
  • Since \(\gamma_{s} > \gamma_{a}\), we have the optimal quorum size of \(|C|=n-\gamma_{s}\)
  • We also need to ensure that a quorum certificate is unique for a value. So we get \(n-\gamma_s+n-\gamma_s > n\implies \gamma_{s} < n/2\)

The quorum size of \(|C|=n-\gamma_s\) ensures validity

  • All we need in the validity property is that some value is output by the protocol

Asynchronous quorum intersection needs \(\beta_{s}+2\gamma_{s} < n\)

  • Asynchronous quorum intersection needs to prevent existence of alternate certificates
  • \(n-\gamma_s + n-\gamma_{S} > n+\beta_{a}\implies n-2\gamma_{s}>\beta_{a}\) or \(\beta_{a}+2\gamma_{S} < n\)

Synchronous quorum intersection needs \(\gamma_{s} < n/2\) and \(n-\gamma_{s} > \beta_{s}\)

  • Since \(\gamma_s < n/2\), \(n-\gamma_s > \beta_{s}\) contains at least one honest node.
  • The protocol uses two equivocation checks. First on the proposal and second on the certificate. The second equivocation check works for any \(\beta_{s} < n\).
  • When \(\beta_{s} < \gamma_{s}\), no conflicting certificates exist.

Synchrony safety proof

_20230308_234144screenshot.png

Synchrony liveness proof (DID NOT UNDERSTAND)

_20230308_234315screenshot.png

_20230308_234359screenshot.png

Asynchrony safety proof

_20230308_235208screenshot.png

Asynchrony liveness proof

_20230308_235334screenshot.png

Metrics

  • Latency is \(2\Delta+2\delta\)
  • Communication complexity is \(O(n^{3})\) w/o threshold signatures

MT-BFT SMR with Public verifiability needs \(\beta_s+\gamma_s \lt n\) along with the RBC bound

  • Same bounds as RBC + a bound for public verifiability
  • Bound for public verifiability by showing bound for Publicly verifiable RBC (PVRBC)

Proof theorem

_20230309_055407screenshot.png

Proof

_20230309_055611screenshot.png

_20230309_055744screenshot.png

My understanding of the proof

_20230309_133034IMG_0837 Large.jpeg

A concrete protocol with \(\beta_s<\frac{2n}{3}\) and \(\beta_{a}=\gamma_{a} =\gamma_{s}=\frac{n}{3}\)

Protocol

_20230309_130003screenshot.png

_20230309_130103screenshot.png

A framework to upgrade to optimal synchronous safety

Typos

  • Page 4, "Synchronous equivocation-checking", repica
  • Section 4.1 use of \(\beta_{s}+f_{s} < n\) instead of \(\beta_{s}+\gamma_{s} < n\) in two locations

References

Atsuki Momose, and Ling Ren. 2021. “Multi-Threshold Byzantine Fault Tolerance.” https://doi.org/10.1145/3460120.3484554.