Verifiable Broadcast with 1-2-3-Phases

VPCBC: The Core Sub-Protocol of HotStuff

HotStuff, introduced by Yin, Malkhi et al. in [@Yin2019HotStuffBC], provides the first practical solution to the [SMR problem] with optimal communication complexity $O(n + t \cdot n)$, against $t$ actual cascading faults.

This post describes the key building block employed in HotStuff, a Verifiable, Provable Consistent Broadcast (“VPCBC”), depicted in Figure 1 below. The original HotStuff: Three-Chain Rules requires chaining three phases of VPCBC as a core sub-protocol operated by each leader.

---

Figure 1: 1-phase, 2-phase, 3-phase VPCBC’s (left), and a QC iconic representations (right).

---

A single phase of the VPCBC is a twist on a common building block, Consistent Broadcast (“CBC”)¹. Like the CBC primitive, VPCBC guarantees:

(i) Agreement.

All honest parties VPCBC-deliver the same message by a sender, if any.

(ii) Non-triviality.

If a sender is honest, then eventually all honest parties VPCBC-deliver a message from it.

Cachin et al. added in [@Cachin2001SecureAE] on top of CBC two additional properties (jointly referred to as Verifiability):

(iii) External Validity.

A broadcast message is accepted by parties if it satisfies a customizable application–specific validity condition, which they can verify at runtime.

(iv) Provability.

If an honest party VPCBC-delivers a broadcast message, it can prove to other parties that it correctly delivered it.

1-Phase VPCBC

A single phase of VPCBC revolves around a CBC protocol introduced by Reiter in [@Reiter1994SecureAP]. Borrowing Reiter’s method, we can solve 1-phase VPCBC as depicted in Figure 1 above at the top-left, and represented by a QC icon at the top-right. The protocol has linear Communication complexity, $O(n)$. A pseudo-code of VPCBC with an optional number of phases is listed below in Algorithm 1.

Specifically, in 1-phase , a sender invokes VPCBC-send($m$, $V$) by broadcasting $m$ and the validity condition $V()$ to all validators. Each validator verifies the validity of the message according to the customizable predicate $V()$. If $m$ passes the verification, the validator sends back to the sender a threshold-signed vote on $m$. The sender waits to collect a Byzantine quorum consisting of $2f+1$ votes, and then aggregates the signature shares into a single signature, referred to as a Quorum Certificate denoted $QC(m)$. Finally, the sender broadcasts the $QC(m)$ to all validators and they VPCBC-deliver it.

---

• For sender $s$ to VPCBC-send($m, V$), send($m, V$) to all nodes.

• Upon first message $(x, V)$ received by node $j$, if $V(x)$ send TE.Share-Sign($j, V, x$) to $s$.

• Upon $2f+1$ valid TE shares $\sigma_i(x)$ received by sender $s$, set $QC(x) \gets$ TE.Sign($x, \sigma_1, …, \sigma_{2f+1}$) and send $QC(x)$ to all nodes.

• Upon a valid $QC(y)$ received by node $j$,
  • in 1-phase protocol, VPCBC-deliver($y$).
  • in 2-phase protocol, set $lock \gets QC(y)$ and send TE.Share-Sign($j, QC(y)$) to $s$
  • in 3-phase protocol, set $key \gets QC(y)$ and send TE.Share-Sign($j, QC(y)$) to $s$

• Upon a valid $QC(QC(y))$ received by node $j$

  • in 2-phase protocol, VPCBC-deliver($y$)
  • in 3-phase protocol, $lock \gets QC(y)$ and send TE.Share-Sign($j, QC(QC(y))$) to $s$

• Upon a valid $QC(QC(QC(y)))$ received by node $j$

  • in 3-phase protocol, VPCBC-deliver($y$)

Algorithm 1. 1-phase, 2-phase, 3-phase VPCBC.

---

2-Phase VPCBC

In 2-phase VPCBC, another round of validator voting is added. Each validator sends back to the sender a threshold-signed vote on $QC(m)$. Note that the validity predicate is not reinstanted in this case (except for standard format and signature verification, which is omitted), because the QC from the first phase guarantees it is valid.

The sender collects and aggregates the votes and broadcasts $QC(QC(m))$. 2-phase is depicted in Figure 1 above (middle).

Importantly, the two phases are interpreted as lock and commit: We say that a validator commits $m$ if it VPCBC-delivers $m$, and locks on $m$ if it votes on $QC(m)$. 2-phase provides the following lock-commit guarantee:

Commit-Lock

if any validator commits $m$, then $2f+1$ validators are locked on $m$.

3-Phase VPCBC

3-Phase VPCBC adds another identical phase and provides a stronger guarantee than lock-commit, referred to as key-lock-commit. We now say that a validator locks on $m$ if it votes on $QC(QC(m))$, and holds a key on $m$ if it votes on $QC(m)$. 3-phase provides the following guarantees:

Commit-Lock

if any validator commits $m$, then $2f+1$ validators are locked on $m$.

Handover Responsiveness

if any validator is locked on $m$, then $2f+1$ validators hold a key on $m$.

3-phase VPCBC is depicted in Figure 1 (bottom left) and a QC iconic representation (bottom right)].

1. The literature also refers to CBC as secure broadcast. ↩