The Hermes BFT for Blockchains

To discourage malicious primary as well as impetus committee nodes from equivocation, Hermes nodes will have to provide a fixed amount of stake while joining the network as done in Proof-of-Stake (PoS) protocols [23, 19]. But this amount will be equal for every participant in the network. Since every participant has equal stake therefore the probability of being selected as primary node or member of the impetus committee is same for every node. Alternatively, any node involved in equivocation can be blacklisted in the network.

Consider a set of $n$ nodes and let $\mathcal{N}=\left\{i|~{}1\leq i\leq n\right\}$ be their unique node ids, which for simplicity are assumed to be taken between $1$ and $n$. Since all nodes are regular, $\mathcal{N}$ also denotes the set of regular nodes. Suppose that out of the $n$ nodes at most $f$ are faulty such that $f<n/3$; actually, we will assume the worst case $n=3f+1$.

Let $\mathcal{C}\subset\mathcal{N}$ denote the set of nodes in the impetus committee, such that $|\mathcal{C}|=c$, where $c\ll n$ is a predetermined number that specifies the size of the impetus committee (from now on $\mathcal{C}$ and impetus committee will be used interchangeably in the paper). The impetus committee $\mathcal{C}$ is formed by randomly and uniformly picking a set of $c$ nodes out of $n$. In addition to the impetus committee members, there is a primary node picked randomly and uniformly out of the remaining $n-c$ nodes.

Since $f<n/3$, therefore on expectation, the impetus committee will have less than $c/3$ faulty nodes. Hence, $\mathcal{C}$ will likely have less than $c/2$ faulty nodes as well. Nevertheless, as the members of $\mathcal{C}$ are randomly picked, having $c/2$ or more faulty nodes in $\mathcal{C}$ are at long odds.

Moreover, the primary might be faulty as well. However, a view change can address primary as well as impetus committee failure. We carry on with analysis to precisely determine the likelihood of different scenarios for picking the members in $\mathcal{C}$. In the formation of $\mathcal{C}$ the number of possible ways to pick any specific set of $c$ nodes out of $n$ is $\binom{n}{c}$. The probability to pick exactly $a$ correct nodes and $b$ faulty nodes in $\mathcal{C}$, such that $a+b=c$, is $\frac{{\binom{n-f}{a}}{\binom{f}{b}}}{\binom{n}{c}}.$ Therefore, the probability $P_{f}$ of having at least $c/2$ faulty nodes ($b\geq c/2$) in $\mathcal{C}$ will be:

If $\mathcal{C}$ is unable to generate a block by the end of timeout period, then $\mathcal{C}$ is replaced by another randomly chosen committee and a new primary through view change.

View Change Probability.

View change can be triggered either by the failure of impetus committee $\mathcal{C}$ or failure of a primary. More specifically the two cases that can ultimately result in a view change are: (i) $b\geq c/2$, where $b$ is the number of faulty nodes in $\mathcal{C}$ (this comes with probability $P_{f}$), or (ii) when $b<c/2$ and the primary node is faulty. For the latter case ii, since we choose the primary randomly from $n-c$ nodes if the total number of faulty nodes is $f<n/3$, then the probability of primary being faulty is at most $(f-b)/(n-c)<n/(3(n-c))$; hence, the probability that case ii occurs is less than $n(1-P_{f})/(3(n-c))$. Therefore, the probability $P_{v}$ of having view change due to case i or ii is bounded by $P_{v}<n(1-P_{f})/(3(n-c))+P_{f}.$ Since $P_{f}$ is approaching $0$ and $n\gg c$, the upper bound of probability $P_{v}$ can be approximated by $1/3$ asymptotically to the limit of $n$.

Probability of At Least One Correct Node in $\mathcal{C}$. For a view change to be initiated, it requires at least one correct node in $\mathcal{C}$. In the worse case, all the nodes in $\mathcal{C}$ are faulty, namely, $b=c$; this is the total failure scenario that does not allow view changes.

We observe that the probability of not having any correct node in $\mathcal{C}$ for different values of $n$ and $c$ in our experiments is at most $3.8\times 10^{-22}$. Consequently, the probability of avoiding total failure is extremely high.

The currently designated primary node $p$ proposes a block by broadcasting a $Pre\mbox{-}Prepare$ message to $\mathcal{C}$ (Algorithm 1, lines 1-9). A $Pre\mbox{-}Prepare$ message from primary $p$ sends a newly created block $B=(\langle``Pre\mbox{-}Prepare",v,s,h,d,o\rangle_{p},m)$ which contains the view number $v$, block sequence number $s$, transaction list $m$, its hash $h$, the previous blockhash $d$ and optional field $o$ which can be used by the primary to send the proof $2f+1$ of negative responses ($F$) during first epoch of its view (new primary in its first epoch might request the latest $Proposal$ from the previous view. If replicas do not have the $Proposal$ they will send negative response $F$). More details about this can be found in the subsection 4.3. Let $\rho=\langle``Pre\mbox{-}Prepare",v,s,h,d\rangle_{p}$.

A node $i$ in $\mathcal{C}$ begins $Pre\mbox{-}Proposal$ phase of the algorithm after receipt of a $Pre\mbox{-}Prepare$ message. Then, node $i$ broadcasts a $Pre\mbox{-}Proposal$ message $\langle``Pre\mbox{-}Proposal",v,s,h,i\rangle_{i}$ if it finds the $Pre\mbox{-}Prepare$ message to be valid. The validity check of the $Pre\mbox{-}Prepare$ message includes checking the validity of $s$, $v$, $d$, $h$ and transactions inside $m$ (Algorithm 2, lines 1-3). If node $i$ receives $\lfloor c/2\rfloor+1$ $Pre\mbox{-}Proposal$ messages from other members of $\mathcal{C}$ for block $B$ then the node $i$ will successfully create a proposal block $(\langle``Proposal",v,s,h,d\rangle_{\sigma_{r}},B)$. This proposal block can be compressed into $(\langle``Proposal",\rho\rangle_{\sigma_{r}},m)$ and then node $i$ will broadcast it to the regular committee members; $\sigma_{r}$ aggregates the signatures of the $\lfloor c/2\rfloor+1$ members of $\mathcal{C}$ that contributed to the $Proposal$. Let $\beta=\langle``Proposal",\rho\rangle_{\sigma_{r}}$ since the primary already has the payload $m$ (from block $B$ it already proposed), the impetus committee member $i$ will only forward $\beta$ to the primary instead of sending the whole $Proposal$ (Algorithm 2 lines $4-8$).

Upon receipt of a $Proposal$ message from $\mathcal{C}$, the regular nodes check if it is signed by at least $\lfloor c/2\rfloor+1$ members of $\mathcal{C}$. Regular nodes also verify the block by performing format checks and verification of each transaction against their history. If verification is successful, a regular node $j$ sends back a signed $Confirm$ message $\langle``Confirm",v,s,h,j\rangle_{j}$ to $\mathcal{C}$ (4, lines 1-4). The confirmation of a block $B$ at height $s$ by a node $j$ is denoted by $\eta_{j}(B,s)\leftarrow true$.

Each member $i$ of $\mathcal{C}$ aggregates $2f+1$ signatures $\sigma$ for $Confirm$ messages and then commits the block locally ($\psi_{i}(B,s)$ is used to show commit of a block $B$ by a node $i$ at the height $s$). The node $i$ then broadcasts $Approval$ message $\langle``Approval",v,s,h\rangle_{\sigma}$ to regular nodes. Each member $i$ of $\mathcal{C}$ will also send the $Response$ message ($\langle Response,s,v,r,t,i\rangle_{i}$) to each client confirming the execution of the respective transaction (with the timestamp $t$ that the client submitted the transaction and its result $r$) that it contributed to the block $B$ (Algorithms 1, lines 21-25 and Algorithm 2 lines $19-23$). Upon receipt of a valid $Approval$ message from $\mathcal{C}$ (for the current block in the sequence), the regular member $k$ also commits the block ($\psi_{k}(B,s)\leftarrow true$) as shown in Algorithm 4, lines 12-21. Each node $k$ (after committing the block) also sends a $Response$ message as shown in Algorithm 4 line 22.

The impetus committee $\mathcal{C}$ might be faulty, when it has $c/2$ or more faulty nodes (shown in red in Figures 4, 4, 4). In such a case, the faulty members of $\mathcal{C}$ might attempt to not update $\zeta\leq f$ regular nodes without triggering view change; namely, not sending $Proposal$ and other messages to the $\zeta$ nodes. (In the upper bound of $\zeta$, $f$ may include at most $\lceil c/2\rceil-1$ failed members of $\mathcal{C}$.) These $\zeta$ nodes (shown in yellow in Figure 4) may not be participating in the consensus process as they have not received messages from members of $\mathcal{C}$ (as majority of $\mathcal{C}$ have failed). Therefore, they will need to sync their history (download messages) with other nodes.

Suppose that node $j$ is a regular node that needs to be synchronized ($j\in\zeta$) (download missing blocks).

Let $i$ be a member of $\mathcal{C}$ such that $i$ has received a timeout complaint $\Gamma_{j}=\langle``Timeout",v,s^{\prime},h^{\prime},s^{\prime\prime},h^{\prime\prime},\tau,j,\rangle_{j}$ mentioning that $j$ has not received blocks between the sequences $s^{\prime}$ and $s^{\prime\prime}$ with respective hashes $h^{\prime}$ and $h^{\prime\prime}$. The fields $s^{\prime\prime}$ and $h^{\prime\prime}$ are optional and if node $j$ has not received any block after the block at sequence $s^{\prime}$ then $\Gamma_{j}=\langle``Timeout",v,s^{\prime},h^{\prime},\tau,j,\rangle_{j}$. The message type $\tau$ shows which type of message is missing, e.g. a block, an aggregated view change message $\mathcal{Q}$ (will be discussed along with other message types in subsection 4.3). The view number $v$ identifies the primary. If node $i$ has not sent a block $B^{\star}$ to the same node $j$ earlier such that its sequence $s^{\star}\geq s^{\prime}$or $s^{\star}\geq s^{\prime\prime}$ (validity condition for $\Gamma_{j}$), then the node $i$ will forward missing messages for missing blocks as shown in Figure 4.

If node $i$ times-out without receiving a valid expected message during the consensus process (as shown in the Figure 4) it will broadcast a complaint $\Gamma_{i}$ to regular nodes. Consequently, a node $i$ in $\mathcal{C}$ can recover a block by receiving it from regular nodes (as shown in the Figure 4). Thus, members of $\mathcal{C}$ and regular nodes synchronize their history (download missing blocks from each other) while keeping message complexity low (avoid quadratic message complexity).

When a new primary is elected it has to make sure that if a block is committed by at least a single correct node then it should be committed by at least $2f+1$ nodes before proposing new blocks. $\Gamma_{p}=\langle``Timeout",v^{\prime},\beta\rangle_{p}$ is a specific type of timeout complaint by the new primary to request the latest uncommitted $Proposal$ (actually the payload $m$ for $\beta$) from previous view. $v^{\prime}$ denotes the view of the current primary. A negative response from $2f+1$ nodes for $\Gamma_{p}$ request will prove that this $Proposal$ has not been committed by any node. If the primary receives a response for $\Gamma_{p}$ it will re-propose the block. Thus, this additional recovery step after view change makes sure that safety is held after the view change. More details about the $\Gamma_{p}$ will be discussed in the subsection 4.3.

Algorithm 3 is about synchronization sub-protocol. Lines 1-14 are executed if the node is a member of the impetus committee. In lines 1-10 node $e$ responds to the $\Gamma_{p}$ request from primary node. After sending the negative response to the primary, node $e$ forwards $\Gamma_{p}$ to regular nodes (Algorithm 3 line 8). In lines 11-13, the impetus committee member $e$ responds to the request of a regular node $j$ by sending the missing blocks to the node $j$. Lines 15-27 are executed if node $e$ is not a member of the impetus committee. In lines 16-18, node $e$ responds to an impetus member request/complaint $\Gamma_{i}$. In lines 19-26, node $e$ responds to request $\Gamma_{p}$ from the primary node.

The primary node might be malicious which can cause the impetus committee $\mathcal{C}$ to fail by not proposing a block. Another possible cause of failure can be the presence of majority of malicious nodes in $\mathcal{C}$. As a result, impetus committee nodes cannot collect at least $c/2+1$ signatures for proposed block. In a rare case, it is also possible that both the primary and the impetus committee $\mathcal{C}$ fail; in such a case the primary can collude with the $\mathcal{C}$ to perform block equivocation. The failure can be detected if $f+1$ nodes send timeout complaint or a single node sends a complaint for equivocation by the primary and $2f+1$ nodes receive it. Upon detecting failure, Hermes will switch to view change mode to select new primary and impetus committee.

The view change sub protocol in Hermes is different from conventional BFT-based protocols as it has additional recovery phase to make sure if a block is committed by a single node just before view change, then it will be committed eventually by all other correct nodes. A view change can be triggered if there is sufficient proof of maliciousness of the primary or the impetus committee. The two types of complaint by a node $i$ that can form a proof against the Byzantine primary are the $\Gamma$ complaints (as discussed in subsection 4.2) as well as $E=\langle``Explicit\mbox{-}complaint",v,\epsilon,i\rangle_{i}$ complaint, where $\epsilon$ determines the reason for the complaint which can be either an invalid block $Proposal$ or multiple $Proposal$s by the primary and/or $\mathcal{C}$ with the same sequence number. A $Proof$ is simply formed by $f+1$ valid $\Gamma$ complaints or a single valid $E$ complaint. A single valid $Proof$ is required to trigger a view change.

During each epoch, a regular node waits to receive a proposed block from $\mathcal{C}$. If a regular node $i$ does not receive the block after a timeout then it considers that $\mathcal{C}$ has failed and reports this to $\mathcal{C}$ (Algorithm 4, lines 5-6). If $f+1$ nodes report a timeout, then there is at least one correct $\mathcal{C}$ member $j$ that will broadcast the aggregated $f+1$ timeout complaints $(\Gamma)$ to all regular nodes (as $Proof$ in Algorithm 2, lines 27-29). Upon receipt of $f+1$ $\Gamma$ complaints the regular nodes send back confirm view change $(\langle``ConfV",\langle v,j\rangle_{j},\langle Proof\rangle_{\sigma_{v}}\rangle)$ message to $\mathcal{C}$, where $\sigma_{v}$ is the aggregated signature from at least $f+1$ complaints from $\Gamma$ messages (Algorithm 4, line 23-25). If complaint is of type $E$ then the confirm view will be of the form $(\langle``ConfV",\langle v,j\rangle_{j},\langle Proof\rangle_{i}\rangle)$, where the node $i$ will be the node that has complained. If an impetus committee member receives a $ConfV$ message and was not aware of the $Proof$ (therefore did not broadcast it to the regular nodes), it will also broadcast the $ConfV$ to the regular nodes (Algorithm 2 line 24-25). This step is added to prevent a Byzantine member in $\mathcal{C}$ from triggering the view change in a subset of regular nodes by sending the $Proof$ messages to few regular nodes.

Once a member $i$ in $\mathcal{C}$ receives $2f+1$ $ConfV$ messages, then $i$ triggers view change by broadcasting message $(\langle``ApproveV",\langle v\rangle_{\sigma},\langle Proof\rangle_{\sigma_{v}},\langle i\rangle_{i},\rangle)$ to all regular nodes (Algorithm 2, lines 30-34). Where $\langle v\rangle_{\sigma}$ is the aggregate signature for $2f+1$ $\langle v,j\rangle_{j}$ from $ConfV$ messages sent by a regular node $j$. Upon receipt of the $ApproveV$ message each regular node will begin the view change process (Algorithm 4, lines 26-33). In the view change, members of new impetus committee $\mathcal{C}$ along with a new primary is selected by each node using a pre-specified common seed for pseudo-random number generation [24], which guarantees that every node selects the identical $\mathcal{C}$ and primary. In pseudo-random generator algorithms, a random result can be reproduced using the same seed. For example the count for the epoch trial can be considered as input seed. Count for epoch trial is the total number of successful epochs that generated blocks plus total number of failed epochs that resulted in view change. In Hermes the main requirements for random generator include liveness, bias-resistance and public verifiability or determinism. By using the count for epoch trials as a seed for the the Pseudo-random generator we can satisfy the above mentioned requirements. There are other options like Verifiable Random Functions [25, 26] which can also be used in order to provide stronger guarantees like unpredictability.

After randomly choosing the new primary as well as the new impetus committee $\mathcal{C}$, each node sends a $ViewChange$ message $V_{k}=(\langle``ViewChange",v+1,s^{\prime},h,k\rangle_{k},\sigma,\beta)$ to the new primary (Algorithm 5 line 1). The $ViewChange$ message has information about the latest block in the local history of the node $k$ ($Approve$ message can be built from $V_{k}$). It includes the latest committed block sequence number $s^{\prime}$, block hash $h$, incremented view number $v+1$, and signature evidence of at least $2f+1$ ($\sigma$) nodes that have confirmed the block (through $Confirm$ message). The $\beta$ part of this message includes the latest $Proposal$ and its respective $Pre\mbox{-}Prepare$ message from the last primary (without its payload $m$) which was received by the node $k$ from $\mathcal{C}$ (through block $Proposal$ message). The inclusion of $\beta$ in the view change message is used to recover the block (transactions) if less than $f+1$ correct nodes have committed the block. We will discuss more about this at the end of the current section. The information in $V_{k}$ is used to determine whether nodes have different local histories, which in turn can allow them to synchronize their histories by getting the possible missing blocks from the new members of $\mathcal{C}$. Upon receipt of $V_{k}$ from node $k$, the new primary extracts the parts $h$ (hash of the latest committed block), $s^{\prime}$, and $k$ and also checks the validity of $\sigma$ and $\beta$. Out of the $2f+1$ nodes that contribute to $\sigma$, it is guaranteed that at least $f+1$ are correct nodes and at least one out of these $f+1$ correct nodes has the latest block.

This guarantee is sufficient to generate next blocks in the new epoch on the top of the latest block.

The new primary, once it receives $2f+1$ $V_{k}$ messages it aggregates them into $\mathcal{Q}$ which it broadcasts to members of $\mathcal{C}$ (Algorithm 7, lines 1-6) and then $\mathcal{C}$ will broadcast the message $\mathcal{Q}$ to all nodes (Algorithm 6). Upon receipt of $\mathcal{Q}$, node $k$ makes sure that its history matches with the history in $\mathcal{Q}$ (agreed by at least $f+1$ nodes) and if it does, node $k$ sends back a $Ready$ message $R_{k}=\langle``Ready",v+1,s^{\prime},h,k\rangle_{k}$ to the new primary (Algorithm 5, lines 2-8). The primary will aggregate $2f+1$ $Ready$ responses into a single $P$ message and broadcast it to $\mathcal{C}$ (Algorithm 7, lines 11-16) which will be forwarded to all the nodes (Algorithm 6). Upon receipt of $P$, node $k$ is now ready to take part in new view (Algorithm 5, lines 9-12). If node $k$’s history does not match that of $\mathcal{Q}$ it will synchronize its history (Algorithm 5, lines 4-6).

Recovery During View Change.

Recall that we add a recovery phase to the view change in order to significantly reduce the latency. During this recovery phase, Hermes protocol makes sure that if there is any block that has been committed by at least one node, it will be committed by all correct nodes eventually. If there is $\beta$ in $V_{k}\in\mathcal{Q}$, then the new primary has to propose the respective block $B$ for the $\beta$. If the new primary has already received the $Proposal$ or the block $B$ for $\beta$ it will re-propose it in the first epoch of its view. On the other hand, if the new primary does not have the complete $Proposal$ (including its payload $m$) for $\beta$ it will request it from $\mathcal{C}$ using a $\Gamma_{p}$ complaint. If an impetus committee member $e$ has the $Proposal$ (payload $m$) it will send it back to the primary. If not, it will forward the $\Gamma_{p}$ complaint to the regular nodes as well as sending a negative response $F=\langle\beta,false\rangle_{e}$ to the primary (Algorithm 3, lines 1-10). Regular nodes will also send back the $Proposal$ message for $\beta$ if they have it to the impetus committee (which will forward it to the primary) or a negative response $F$ to the primary. If the primary receives back the $Proposal$ it will re-propose the block else it will have to propose another block with $2f+1$ aggregated signatures for negative response $F$ being attached to it in order to prove that $Proposal$ for $\beta$ was not committed by any correct node (Algorithm 1, lines 1-15). Therefore, if there is a $\beta$ in $V_{k}\in\mathcal{Q}$ during recent view change, then in the first epoch after the view change the new primary either has to propose the relative block for $\beta$ or include $2f+1$ negative responses in the first block $B$ that it proposes in the new view. If the primary fails to do so, a view change will occur (through $E$ complaint).

Hermes has relaxed the agreement (safety) condition. In Hermes a block is committed if at least $f+1$ correct nodes commit the block. If $2f+1$ nodes commit a block it is guaranteed that at least $f+1$ of these nodes are correct. Due to this relaxation in the agreement condition the client also needs to wait for at least $2f+1$ $Response$ messages for its transaction to consider it committed (to make sure at least $f+1$ correct nodes have committed the block). For further client and network interaction including addressing, client request de-duplication, censorship etc., we would defer to standard literature.

But it is also highly likely that Hermes holds stronger agreement condition where if a single correct node commits a block all other correct nodes will eventually commit the same block at the same height (due to low probability of the primary as well as the majority of nodes in $\mathcal{C}$ are Byzantine). For simplicity we use $\mathcal{H}$ as the set of all correct nodes such that $\mathcal{H}\subseteq\mathcal{N}$ and $|\mathcal{H}|\geq 2f+1$ in the proof of correctness.

Therefore, we get the following theorem: