We explore a family of broadcast protocols in the authenticated setting in which a designated *sender* wants to create a *delivery-certificate* of its input value. After describing the base protocol we call **Provable Broadcast** ($PB$), we explore the surprising power of simply running $PB$ two times in a row, then three times, and finally four times in a row.

These protocols are secure against a malicious adversary controlling $f<n/3$ parties in the asynchronous model.

Provable Broadcast based protocols are the backbone of many authenticated consensus protocols. When used as part of a consensus protocol, the *delivery-certificate* of $PB$ is often called a *commit-certificate*. In this post, we focus just on the $PB$ primitive and hence use the term *delivery-certificate*. We will refer to it as a *commit-certificate* in the follow-up posts that explain consensus protocols that use $PB$.

**Provable Broadcast**: is a simple one round-trip building block going back to Reiter 94’s **Echo Broadcast**. Echo Broadcast produces a *delivery-certificate* proving that $n-2f$ honest parties delivered the sender’s value. This is the *Weak-Availability* property. Moreover, even if the sender is Byzantine, the *Uniqueness* property guarantees that there is at most one such value.
Echo Broadcast can be slightly extended to *Validated Echo Broadcast* which we call Provable Broadcast that also provides an *External-Validity* property (see below). This allows sequencing provable broadcast instances to achieve stronger properties:

**Locked Broadcast**: by running*two*consecutive $PB$s, we get a two round-trip protocol. This protocol additionally provides a*Unique-Lock-Availability*pretty: a*delivery-certificate*is a proof that $n-2f$ honest parties received a*lock-certificate*for this value, and no other value can have a*lock-certificate*. Locked Broadcast is the main sub-loop of Tendermint, Casper FFG, linear PBFT, two-chain-HotStuff.**Keyed Broadcast**: by running*three*consecutive $PB$s, we get a three round-trip protocol. As before, a*delivery-certificate*is a proof that $n-2f$ honest parties received a*lock-certificate*. In addition, this protocol provides a*Unique-Key-Availability*property: if a*lock-certificate*exists, then $n-2f$ honest parties hold a*key-certificate*and there can only be one value with a*key-certificate*. Keyed Broadcast is the main loop of three-chain-HotStuff and overcomes the*hidden lock problem*.**Robust Keyed Broadcast**: by running*four*consecutive $PB$s, we get a four round-trip protocol. This protocol additionally provides a*Robust-Delivery*property: there is proof that at least $n-2f$ honest parties have a*Delivery-Certificate*. Robust Keyed Broadcast is the main sub-loop of Asynchronous protocols: VABA, ACE, AllYouNeedIsDag.

*Note:* Some recent consensus protocols opt for *three* consecutive $PB$s for obtaining **Robust Locked Broadcast** that provides *Robust-Delivery* with *Unique-Lock-Availability* (but without *Unique-Key-Availability*), see Tusk.

#### On External Validity

We assume there is some *External Validity* ($EV$) Boolean predicate that is provided to each party. $EV$ takes as input a value $v$ and a $proof$. If $EV(v,proof)=1$ we say that $v$ is *externally valid*. A simple example of external validity is a check that the value is signed by the sender and/or is signed by the client that controls the asset etc. External validity is based on the framework of Cachin, Kursawe, Petzold, and Shoup, 2001. In later posts, we will extend $EV$ to also take the internal state of the party as input.

#### Properties of the Broadcast protocols

All four protocols above have the following properties:

**Termination**: If the sender is honest and has an*externally valid*input $v$, then after a constant number of rounds the sender will obtain a*delivery-certificate*of $v$. Note that the Termination property requires just the sender to hold the certificate.**Uniqueness**: There can be at most one value that obtains a*delivery-certificate*. So there cannot be two*delivery-certificates*with different values.**External Validity**: If there is a*delivery-certificate*with value $v$ and $proof$ then $v$ is*externally valid*. So $EV(v,proof)=1$.

The four protocols differ by providing additional properties:

*Echo Broadcast*obtains**Weak-Availability**: If a*delivery-certificate*exists for $v$ then at least $n-2f$ honest parties hold the value $v$.*Locked Broadcast*obtains**Unique-Lock-Availability**: If a*delivery-certificate*exists for $v$ then there can only exist a*lock-certificate*for $v$ and there are at least $n-2f$ honest parties that hold this*lock-certificate*.*Keyed Broadcast*obtains**Unique-Key-Availability**: If a*lock-certificate*exists for $v$ then there can only exist a*key-certificate*for $v$ and there are at least $n-2f$ honest parties that hold this*key-certificate*.*Robust Keyed Broadcast*obtains**Robust-Delivery**: If a*robust-certificate*exists then there are at least $n-2f$ honest parties that hold a*delivery-certificate*.

## Provable Broadcast (Validated Echo Broadcast) and Weak-Availability

Provable Broadcast calls a Boolean external validity function $EV(v,proof)$ as a subroutine. For now, consider the case where $EV$ just checks that $proof$ is a valid signature on $v$ relative to the designated sender’s public key.

$PB$ is a super simple protocol: the Sender sends a value, parties check the *first* value they see is *valid*, and if it is, *sign* it back to the sender. The sender accumulates signatures until a *delivery-certificate* is formed.

```
Sender s:
input v
input proof = <v>_s //signature by s on v
send <v, proof>_s to all
Party i:
For the first <v, proof> received from s:
If EV(v, proof) then send <v, proof>_i to s
Delivery-Certificate for v:
n-f distinct signers on <v, proof>
```

** Proof**:

*External Validity*: since honest parties check $EV$ and at least $n-2f$ honest parties need to sign for a *delivery-certificate* to form.

*Uniqueness* follows from quorum intersection - seeking a contradiction assume there are two values $v \neq v’$ with a *delivery-certificate*. Hence there are two sets of size $n-f$, and they must intersect in at least $n-2f$ parties. Since $n>3f$, this implies that at least $f+1$ parties signed both certificates, but we assume the adversary can corrupt up to $f$ parties. Hence contradiction.

*Termination* follows from the sender needing to wait for only $n-f$ signatures for a *delivery-certificate* to form.

*Weak-availability* from counting: at least $n-f$ parties signed for the *delivery-certificate* to form, so at least $n-2f \geq f+1$ of them are honest.

Make sure you go over the proof once in detail. Now, let’s start composing :-)

## Locked Broadcast and Unique-Lock-Availability

The sender runs **two** $PB$ consecutively: $PB_1,PB_2$. For $PB_1$ the external validity function $EV_1$ for now just checks the sender signature (in later posts, we will use Locked Broadcast as part of a consensus protocol, and add a PBFT style view change check to $EV_1$). For $PB_2$ we define $EV_2(v,p)$ to check that $p$ is a *delivery-certificate* on $v$ from $PB_1$ (so $EV_2$ checks that $p$ contains $n-f$ distinct valid signatures on $<v,proof>$). That’s it!

```
Sender s:
input v
input proof = <v>_s //signature by s on v
send <v, proof>_s to all
send <v, cert_1(v)>_s to all when you obtain cert_1(v)
Party i:
For the first <v, proof> you receive from s:
If EV_1(v,proof) then send <v, proof>_i to s
For the first <v, cert_1(v)> you receive from s:
If EV_2(v, cert_1(v)) then send <v, cert_1(v)>_i to s
Cert_1(v), "lock-certificate for v":
n-f distinct signers on <v, proof>
Cert_2(v), "delivery-certifiacte for v":
n-f distinct signers on <v, cert_1(v)>
```

** Proof**: We get

*External Validity*and

*Uniqueness*from $PB_1$.

*Termination*follows from needing just $n-f$.

*Unique-Lock-Availability*follows from the Uniqueness of $PB_1$ and the Weak-availability of $PB_2$. Directly: if there is a $cert_2(v)$ then from $PB_1$ there can be at most one $cert_1(v)$ and due to $PB_2$ at least $n-2f$ honest hold $cert_1(v)$.

*Note 1*: Unique-Lock-Availability is the core of what allows a safe view-change in all authenticated PBFT style protocols.

**More on PBFT style view change**:

It means that if a party committed to $v$ in view $k$ due to seeing a Certificate $cert_2(v,k)$ then any leader of any view $>k$, by querying $n-f$ parties, must intersect with one of the $n-2f$ honest holding $cert_1(v,k)$ hence this query must contain $cert_1(v,k)$, and no other $cert_1(v',k)$ can exist (here we use the Unique-Lock-Availability property). Moreover, the new leader, by sending all the $n-f$ certificates it queried as the proof, and proposing value $v$ from $cert_1(v,k)$ of the highest view $k$ in this set, can prove its proposal is safe. $EV_1$ checks that the proposal is indeed of the highest view, using this proof.

*Note 2*: In some protocols, Unique-Lock-Availability is not enough. When using Tendermint style view change, if not using a timeout, the new leader may not be aware of all the Lock-Certificates held by honest parties. This is called the **hidden lock problem**. HotStuff is a Tendermint style protocol that has the property that if any honest party has a Lock-Certificate then the new leader will not miss this lock, even if the new leader just waits for the first $n-f$ responses. HotStuff obtains this property by using *Keyed Broadcast*.

**More on Tendermint style view change**:

In the Tendermint view change protocol, the new leader only sends $cert_1(v,k)$, but does not prove this is the certificate with the highest view. Instead, $EV_1$ checks that the proposed value $v$ has a $cert_1(v,k)$ from a view $k$ that is at least as high as the highest $cert_1(v',k’)$ that the validator has ever seen. In a later post we will cover this in detail. For now, it's sufficient to grasp at a high level a problem with this protocol: a new honest leader, that does not use a timeout, may query $n-f$ parties and observe the highest $cert_1(v,k)$ is from view $k$, but due to it only waiting for the first $n-f$, may miss a $cert_1(v',k’)$ held by an honest party with $k<k’$. This may cause the new leader to fail Termination of its $PB$, and is called the *hidden lock problem*.

## Keyed Broadcast and Unique-Key-Availability

Solving the hidden lock problem is critical for *efficient* solutions in asynchrony and *efficient* solutions obtaining responsiveness in partial synchrony.

In Keyed Broadcast the sender runs **three** $PB$s consecutively: $PB_1,PB_2, PB_3$. As before, for $PB_1$ we assume for now $EV_1$ just checks the sender signature (in later posts, we will use Keyed Broadcast as part of a consensus protocol, and add a Tendermint style lock check condition to $EV_1$). As before, $EV_2(v,proof)$ checks that $proof$ is a delivery-certificate on $v$ from $PB_1$. As you can imagine, $EV_3(v,proof)$ just checks that $proof$ is a *delivery-certificate* on $v$ from $PB_2$. That’s it!

```
Sender s:
input v
input proof = <v>_s //signature by s on v
send <v, proof>_s to all
send <v, cert_1(v)>_s to all when you obtain cert_1(v)
send <v, cert_2(v)>_s to all when you obtain cert_2(v)
Party i:
For first <v, proof> received from s:
If EV_1(v,proof) then send <v, proof>_i to s
For first <v, cert_1(v)> received from s:
If EV_2(v, cert_1(v)) then send <v, cert_1(v)>_i to s
For first <v, cert_2(v)> received from s:
If EV_3(v, cert_2(v)) then send <v, cert_2(v)>_i to s
Cert_1(v), "key-certificate for v":
n-f distinct signers on <v, proof>
Cert_2(v), "lock-certificate for v":
n-f distinct signers on <v, cert_1(v)>
Cert_3(v), "delivery-certificate for v":
n-f distinct signers on <v, cert_2(v)>
```

** Proof**:

*External Validity*and

*Uniqueness*follows from $PB_1$,

*Unique-Lock-Availability*from $PB_2 + PB_3$,

*Unique-Key-Availability*follows from $PB_1 + PB_2$, and

*Termination*follows from needing just $n-f$ in each of the three $PB$s.

To guarantee that there is no hidden lock: if an honest party has a *lock-certificate* $cert_2(v)$ then at least $n-2f$ honest have a *key-certificate* $cert_1(v)$ and there cannot be *key-certificates* on other values (due to $PB_1$). Hence during view change, even in asynchrony, a new honest leader is guaranteed to see at least one *key-certificate* for any *lock-certificate* held by any honest party. So the new honest leader can propose the value that has the *key-certificate* with the highest view.

In partial synchrony, this three round-trip protocol is the core of how HotStuff obtains **responsiveness**.

Finally, for termination in asynchrony, we want to know that many parties have a *delivery-certificate*. Simply add one more $PB$!

## Robust Keyed Broadcast and Robust-Delivery

Run **four** consecutive $PB$s, where the fourth $PB$’s goal is to output a robust-certificate that indicates that at least $n-2f$ honest parties hold a delivery-certificate. A `Deliver v`

event is explicitly added when a valid *delivery-certificate*, $cert_3(v)$, is received.

For completeness here is the protocol:

```
Sender s:
input v
input proof = <v>_s
send <v, proof> to all
send <v, cert_1(v)> to all when you obtain cert_1(v)
send <v, cert_2(v)> to all when you obtain cert_2(v)
send <v, cert_3(v)> to all when you obtain cert_3(v)
Party i:
For first <v, proof> received from s:
If EV_1(v,proof) then send <v, proof>_i to s
For first <v, cert_1(v)> received from s:
If EV_2(v, cert_1(v)) then send <v, cert_1(v)>_i to s
For first <v, cert_2(v)> received from s:
If EV_3(v, cert_2(v)) then send <v, cert_2(v)>_i to s
For first <v, cert_3(v)> received from s:
If EV_4(v, cert_3(v)) then
Deliver v; and
send <v, cert_3(v)>_i to s
Cert_1(v), "key-certificate for v":
n-f distinct signers on <v, proof>
Cert_2(v), "lock-certificate for v":
n-f distinct signers on <v, cert_1(v)>
Cert_3(v), "delivery-certifiacte for v":
n-f distinct signers on <v, cert_2(v)>
Cert_4(v), "robust-certificate for v":
n-f distinct signers on <v, cert_3(v)>
```

** Proof**:

*Termination*is again obtained since we just need $n-f$ valid responses.

*Robust-Delivery*follows from weak-availability of $PB_4$ and the uniqueness of $PB_1$.

## Linearity

All $PB$ protocols have a linear message complexity. When using threshold signatures they require a total of just $O(n)$ words of communication. When using multi signatures they require just $O(n)$ authenticators (where each authenticator includes $n$ bits and a single signature whose length depends on the security parameter).

## Next Posts and Notes

In the next posts, we will see how:

- Locked Broadcast is the core building block of two-round-Hotstuff, 2018.
- Keyed Broadcast is the core building block of Hotstuff, 2018.
- Robust Keyed Broadcast is the core building block for obtaining a VABA, 2018. The exposition in this post is based on the
*$f+1$-Provable-Broadcast*and*$4$-stage-$f+1$-Provable-Broadcast*of VABA, 2018.

Your thoughts and comments on Twitter.