# Mixed Fault Tolerance Protocols with
Trusted Execution Environment

Mingyuan Gao<EMAIL_ADDRESS>0000-0002-9579-1890 National University
of SingaporeSingapore ,  Hung Dang<EMAIL_ADDRESS>FPT Blockchain
LabVietnam ,  Ee-Chien Chang<EMAIL_ADDRESS>0000-0003-4613-0866
National University of SingaporeSingapore and  Jialin Li<EMAIL_ADDRESS>National University of SingaporeSingapore

###### Abstract.

Blockchain systems, or distributed ledgers, are designed, built and operated
in the presence of failures. There are two dominant failure models, namely
crash fault and Byzantine fault. Byzantine fault tolerance (BFT) protocols
offer stronger security guarantees, and thus are widely used in blockchain
systems. However, their security guarantees come at a dear cost to their
performance and scalability. Several works have improved BFT protocols, and
Trusted Execution Environment (TEE) has been shown to be an effective
solution. However, existing such works typically assume that each
participating node is equipped with TEE. For blockchain systems wherein
participants typically have different hardware configurations, i.e., some
nodes feature TEE while others do not, existing TEE-based BFT protocols are
not applicable.

This work studies the setting wherein not all participating nodes feature TEE,
under which we propose a new fault model called mixed fault, which is a
combination of crash and Byzantine faults. We explore a new approach to
designing efficient distributed fault-tolerant protocols under the mixed fault
model. In general, mixed fault tolerance (MFT) protocols assume a network of
$n$ nodes, among which up to $f=\frac{n-2}{3}$ can be subject to mixed faults.
Among these failures, some nodes may exhibit Byzantine behaviours, especially
equivocating, while other nodes fail only by crashing. We identify two key
principles for designing efficient MFT protocols, namely, (i) prioritizing
non-equivocating nodes in leading the protocol, and (ii) advocating the use of
public-key cryptographic primitives that allow authenticated messages to be
aggregated. We showcase these design principles by prescribing an MFT
protocol, namely MRaft, which is based on the Raft (Ongaro and Ousterhout,
2014) consensus protocol.

We implemented a prototype of MRaft using Intel SGX, integrated it into the
CCF (Russinovich et al., 2019) blockchain framework, and conducted experiments
on Microsoft Azure using nodes spanning across different geographical regions.
Experimental results showed that MFT protocols can obtain the same security
guarantees as their BFT counterparts while still providing better performance
(both transaction throughput and latency) and scalability.

consensus protocol, trusted execution environment, TEE, Intel SGX, blockchain,
distributed ledger, Byzantine fault tolerance, BFT, crash fault tolerance,
CFT, distributed system

††copyright: none††ccs: Security and privacy Distributed systems
security††ccs: Security and privacy Hardware-based security protocols††ccs:
Computer systems organization Reliability††ccs: Computer systems organization
Availability

##  1\. Introduction

Blockchain systems, or distributed ledgers, have received tremendous interest
from both academia and industry communities over the last few years. They
offer data integrity and immutability in the presence of service disruption or
adversarial attempts. These systems achieve such security guarantees by
building on distributed fault-tolerant consensus protocols (Ongaro and
Ousterhout, 2014; Castro et al., 1999; Dang et al., 2019). These protocols can
achieve both safety and liveness in the presence of failures. Safety means
that honest participants (aka nodes or replicas) agree on the same value,
whereas liveness means that these nodes eventually agree on a value.

A fault-tolerant distributed system is designed, built and operated with
respect to a particular threat model, which comprises assumptions made on the
nodes involved in upkeeping the system. Crash fault tolerance (CFT) protocols
assume faulty nodes fail only by crashing, whereas Byzantine fault tolerance
(BFT) protocols deal with faulty nodes that deviate arbitrarily from their
protocol description. Byzantine faults cover not only adversarial behaviour,
but also account for hostile environment wherein errors may arise from
hardware malfunctions, software bugs, or errant system administrators causing
data loss or state corruptions. There are clear trade-offs among choices of
the threat model. BFT protocols offer stronger security guarantees in
comparison to their CFT counterparts, for they are designed to tolerate a more
powerful adversary who is able to equivocate at will. It has been shown that
equivocation - the act of a faulty node sending conflicting messages to other
nodes without being detected - is the chief cause of the complications and
overheads underlying BFT protocols (Chun et al., 2007). Ensuring both safety
and liveness despite equivocation comes at a dear cost to the performance
(i.e., transaction throughput and latency) and scalability of BFT protocols
(Dinh et al., 2017).

Consequently, a number of works have attempted to lessen this gap via the use
of hybrid fault model (Behl et al., 2017; Dang et al., 2019; Chun et al.,
2007). In such model, it is assumed that each node is equipped with a small
trusted subsystem that fails only by crashing, i.e., stop processing and
responding to any message from other nodes, whereas other untrusted components
in a node may fail or misbehave arbitrarily. Protocols following this hybrid
fault model have been shown to require only $n=2f+1$ nodes to tolerate $f$
Byzantine faults, as opposed to $n=3f+1$ in conventional BFT protocols (e.g.,
PBFT (Castro et al., 1999)). This leads to lower computational and
communication costs. Alternatively, there exist attempts that deploy CFT
protocols such as Raft (Ongaro and Ousterhout, 2014) in a Byzantine setting
(Russinovich et al., 2019) via the use of Trusted Execution Environment (TEE)
(Subramanyan et al., 2017). In particular, one may run the entire CFT
consensus protocol inside a TEE with attested execution (McKeen et al., 2013)
so as to curb adversarial capability of the faulty nodes. It is worth noting
that this line of protocols assume that each node in the system is equipped
with TEE, which may not be applicable to systems wherein participants have
different hardware configurations, i.e., some nodes feature TEE while others
do not.

The motivations behind our work are twofold. On one hand, participants of a
fault-tolerant distributed system are likely to feature heterogenous machines,
which are also subject to different maintainance or administration.
Consequently, it is rarely the case that an adversary can coordinate a large
number of Byzantine faults simultaneously as assumed in BFT threat models. On
the other hand, it is more likely the case that among the faulty nodes, only a
few of them feature Byzantine behaviours, while others are simply crash
faults. The latter claim can be justified in practice via the use of TEE
(Russinovich et al., 2019), which is widely available nowadays in commodity
processors. This is so because running code inside TEE can significantly
restrict the malicious capability of a compromised node. That is, when
deploying procotol code inside TEE, the TEE-powered node only fails by
crashing.

Given that BFT protocols are not efficient for such replicated systems, these
two observations motivate us to design a new fault model, namely mixed fault,
which is a combination of crash and Byzantine faults. In this fault model, a
portion of these nodes may exhibit Byzantine behaviours, deviating arbitrarily
from the protocol description in an attempt to break safety and liveness,
whereas the remaining nodes fail only by crashing.

In this work, we explore a new approach to designing efficient distributed
fault-tolerant protocols under the mixed fault model, and we refer to such
protocols as Mixed Fault Tolerance (MFT) protocols. In general, MFT protocols
assume a network of $n$ nodes, among which up to $f=\frac{n-2}{3}$ can be
subject to mixed faults. Among the $n$ nodes, some are equipped with TEE,
while others do not. We identify two key principles for designing efficient
MFT protocols. Both principles are drawn from an insight that communication
overhead is a major hurdle that exacerbates protocols’ scalability. Various
works have demonstrated that communication overhead is the main performance
bottleneck of these protocols (Dinh et al., 2017).

The first principle advocates _prioritizing non-equivocating nodes in leading
the protocol_. This is built upon an observation that the complications
underlying BFT protocols primarily arise from equivocation. In MFT protocols,
only a few faulty nodes exhibit equivocation, as opposed to each faulty node
in BFT protocols. Consequently, as long as the protocol is led by a non-
equivocating node, it may be designed in such a way that a majority of
messages are routed through and verified by the leader, thereby reducing the
overall communication and computation overheads in the system.

The second principle advocates _incorporating public-key cryptographic
primitives that allow authenticated messages to be aggregated_. Early
proposals for consensus protocols favour symmetric-key Message Authentication
Code (MAC) to authenticate all-to-all communication in hostile environments,
e.g., PBFT (Castro et al., 1999). This choice was made so as to avoid public-
key operations, whose implementations and executions used to be prohibitive.
Fortunately, there exist various well-optimized asymmetric or hardware-based
cryptosystems (Szerwinski and Güneysu, 2008; Bernstein et al., 2012; int, [n.
d.]) that render these costs far more affordable. Furthermore, by aggregating
authenticated messages such that receiving and verifying an aggregated message
is equivalent to receiving and verifying a set of individual messages, one can
improve the communication complexity of the system (Kogias et al., 2016; Dang
et al., 2019).

To showcase these two principles, we prescribe an MFT protocol, namely, MRaft,
which is based on a CFT consensus protocol called Raft (Ongaro and Ousterhout,
2014). It is worthy to mention that MRaft features communication complexity
that is linear to the network size $n$, i.e., $O(n)$. Similar to Raft, MRaft
is driven by a leader. However, the leader election in MRaft favours nodes
that are equipped with TEE. The TEE-powered leader leverages TEE to verify and
aggregate messages from other nodes, generating a certificate attesting the
fact that a statement has been agreed by a quorum of the nodes. Alternatively,
in the very rare case that the leader is not equipped with TEE, the protocol
leverages Collective Signing (CoSi) (Syta et al., 2016) to generate such
certificates.

We implemented a prototype of MRaft using Intel SGX, integrated it into the
CCF (Russinovich et al., 2019) blockchain framework, and conducted experiments
on Microsoft Azure using nodes spanning across different geographical regions.
Experimental results showed that MFT protocols can obtain the same security
gurantees as their BFT counterparts while still providing better performance
(both transcation throughput and latency) and scalability.

In summary, we make the following contributions in this work.

  1. (1)

Leveraging TEE, we propose a new approach to designing efficient distributed
fault-tolerant protocols that tolerate a combination of crash and Byzantine
faults. That is, a new fault model named mixed fault is proposed.

  2. (2)

We identify two key principles for designing efficient MFT protocols. That is,
(i) prioritizing non-equivocating nodes in leading the protocol, and (ii)
advocating the use of public-key cryptographic primitives that allow
authenticated messages to be aggregated.

  3. (3)

We showcase the above two design principles by prescribing an MFT protocol,
namely, MRaft.

  4. (4)

We implemented a prototype of MRaft uisng Intel SGX, integrited it into the
CCF blockchain framework (Russinovich et al., 2019), conducted experiments in
realistic deployment settings, and demontrated the efficiency of MFT
protocols.

##  2\. Preliminaries

This section provides prerequisite knowledge that is relevant for this work.
We first discuss key features of distributed consensus protocols, focusing on
Raft (Ongaro and Ousterhout, 2014) and PBFT (Castro et al., 1999).
Subsequently, we give a brief overview of TEE, in particular, Intel SGX.
Finally, we review the collective signing technique (Syta et al., 2016).

###  2.1. Consensus Protocols

Consensus protocols aim to achieve both safety and liveness in a distributed
environment, which is potentially hostile. Safety necessitates non-faulty
nodes to reach an agreement and never return conflicting results for the same
query, whereas liveness requires that these nodes eventually agree on a value.
There are two types of node failures, namely crash fault and Byzantine fault.
Crash fault-tolerant (CFT) protocols assume faulty nodes fail only by
crashing, whereas Byzantine fault-tolerant (BFT) protocols deal with faulty
nodes that deviate arbitrarily from their expected behaviours. For instance, a
Byzantine node can equivocate, or delay its activity for arbitrary duration
(Castro et al., 1999).

#### Raft Consensus Protocol.

Raft is arguably the most notable CFT consensus protocol. A Raft system
comprises $n$ deterministic nodes, and could tolerate up to
$f=\lfloor\frac{n-1}{2}\rfloor$ crash-failures. Each node maintains a log that
contains a series of commands (or ledger). Raft ensures that logs of non-
faulty nodes converge, achieving safety regardless of synchrony assumption.
However, it necessarily relies on timing to offer liveness (Fischer et al.,
1982) (e.g., network is partially synchronous such that messages are delivered
within an unknown but finite bound).

The protocol is driven by a leader. All remaining nodes are referred to as
followers. Each leader is associated with a unique term. The leader exchanges
heartbeats with the followers in order to maintain its leadership. If a leader
crashes, the protocol goes into the leader election phase and safely replaces
the faulty leader with a non-faulty one. We refer readers to the Raft paper
(Ongaro and Ousterhout, 2014) for details on the leader election.

The leader collects commands (e.g., requests from the clients), records them
in its log, and replicates them on the followers as follows. First, it
broadcasts the command to all followers. Each command is identified by the
leader’s term and an index in its log. When a follower receives a command from
the leader, it appends the command to its own log, and responds to the leader
with an acknowledgement. The leader commits (i.e., execute) the command once
it has received a quorum of $f+1$ or more acknowledgements. The leader
announces such commit to the followers, who then also commit the command in
their own local state.

#### Practical Byzantine Fault Tolerance (PBFT)

PBFT is driven by a leader, whose leadership is associated with a view. The
protocol comprises three phases, namely Pre-Prepare, Prepare and Commit. In
the first phase, the leader collects requests from clients and broadcasts them
to other nodes in the network as pre-prepare messages. Upon receiving a pre-
prepare message from the leader, each node verifies the validity of the
request, before broadcasting its responses in prepare messages. These messages
constitute the second phase, which ensures nodes agree on the ordering of the
requests. Upon receiving a quorum of valid and matching prepare messages,
nodes move to the third phase, broadcasting their commit messages. They
execute the requests once they receive a quorum of commit messages. When the
leader fails, the view change protocol is triggered to replace the leader.

PBFT requires a network of $n=3f+1$ nodes and a quorum size of $2f+1$ to
tolerate up to $f$ Byzantine failures. The protocol observes a communication
complexity of $O(n^{2})$. It attains safety regardless of timing assumptions,
whereas liveness is achieved in partially synchronous networks.

###  2.2. Trusted Execution Environment

#### Enclave Execution.

Trusted Execution Environment (TEE) offers an isolated region that safeguards
the integrity of the code running inside. In other words, an adversary is
unable to tamper with the execution of the protected components, or deviate
them from their expected behaviours. There are various hardware primitives
that provision TEEs, e.g., Intel SGX (McKeen et al., 2013), KeyStone (Lee et
al., 2019) and Sanctum (Costan et al., 2016). This work adopts Intel SGX due
to its wide availability.

Intel SGX (McKeen et al., 2013) is capable of provisioning hardware-protected
TEE (or enclave) for general computation. Each enclave is associated with an
address space (or enclave memory) which is guarded by the CPU, and
inaccessible by foreign (non-enclave) processes. In particular, each enclave
is segregated from the Operating System (OS), user processes and other
enclaves running on the same physical host. The enclave code, on the other
hand, is able to invoke OS services such as paging and I/O. It is worth noting
that data residing in the enclave memory are encrypted under the processor’s
key prior to leaving the enclave.

#### Attestation.

Enclaves are instantiated by the OS. A remote user can verify the correct
instantiation of an enclave based on a remote attestation protocol (sgx, [n.
d.]). The CPU produces a measurement of the enclave right after it is
instantiated, and signs the measurement with its private key. Such measurement
consists of the hash of the enclave’s initial state. The user can validate the
signature using Attestation Services (sgx, [n. d.]), and check the correctness
of the measurement.

#### Data Sealing.

An enclave may persist its private state on non-volatile storage via data
sealing mechanisms. Data sealing begins with the enclave obtaining a unique
key bound to its measurement from the CPU. The enclave then encrypts its
private state under the enclave-specific key before passing the encrypted data
to the non-volatile storage. It is guaranteed that the sealed data is
retrievable only by its owner (i.e., the enclave that sealed it). Nonetheless,
previous works have shown that data sealing may be susceptible to rollback
attacks in which a malicious OS attempts to provide the enclave with properly
sealed but stale data (Brandenburger et al., 2017). Defences against such
attack have been proposed in the literature (Matetic et al., 2017).

###  2.3. Collective Signing

Collective Signing, or CoSi for short, allows a group of independent nodes to
validate and co-sign a statement (Syta et al., 2016). The protocol produces a
collective signature attesting the fact that all nodes in the group have
endorsed the message. Such collective signature has size and verification cost
equivalent to those of an individual signature.

CoSi builds upon Schnorr multi-signatures (Schnorr, 1991). The protocol takes
advantage of communication trees (Castro et al., 2003; Venkataraman et al.,
2006) to optimize its communication cost, thereby achieving scalability. The
protocol assumes that each node in the group has a unique public key, and that
these keys are combined to generate an aggregate public key. One node in the
group is designated as a leader, who drives the protocol through the following
four phases to generate the collective signature for a message $M$:

  * •

Announcement: The leader triggers the new round by multicast an announcement
along the communication tree. $M$ may be embedded in the announcement.
Alternatively, it can be sent in the Challenge phase.

  * •

Commitment: Upon receiving the announcement from the leader, nodes pick a
secret uniformly at random, and compute a Schnorr commitment of their chosen
secret. From the bottom of the communication tree up, each node sends its
aggregated Schnorr commitment to its parent. The node computes its aggregated
commitment by combining its own Schnorr commitment with those it collects from
its children.

  * •

Challenge: After receiving the aggregated Schnorr commitment, the leader
produces a collective Schnorr challenge. It then sends the challenge along the
communication tree. If $M$ has not been sent in the Announcement phase, the
leader embeds $M$ in the challenge.

  * •

Response: Given the collective challenge, nodes assemble the aggregate
responses in a manner similar to that of the Commitment phase.

In case some nodes fail to respond to messages from the leader, the protocol
can still produce the collective signature. However, this signature will
include metadata that indicates which node did or did not participate in the
collective signing. Readers are referred to the CoSi paper (Syta et al., 2016)
for further details.

##  3\. Overview of MFT Systems

In this section, we give an overview of the MFT systems. First, we present
some example distributed systems that motivate the design of the MFT model in
Subsection 3.1. Then, we describe the MFT model in detail in Subsection 3.2.
Lastly, we elaborate on the threat model of an MFT system in Subsection 3.3
and its system goals in Subsection 3.4.

###  3.1. Motivating Examples

Before presenting the MFT model that this work studies, let’s first look at
some example distributed systems that motiviate the design of this model.

  1. (E1)

Consortium Blockchain: In a deployment of the consortium blockchain, the
distributed ledger is shared and maintained by a group of independent parties.
Typically, these parties rely on a BFT protocol like PBFT (Castro et al.,
1999) to provide safety and liveness for the distributed ledger. It is highly
likely that these parties have different hardware configurations, e.g., some
systems feature TEE while others do not.

  2. (E2)

Backward-Compatible Distributed Systems: Consider a large-sized corporate
whose operations span across multiple regions, business activities at each
region is administered by a separate branch. These branches need to stay in
synchronization. Needless to say, the corporate can use a BFT protocol to
enable such synchronization. However, these branches are highly likely to have
different hardware configurations. Some branches may have already upgraded
their systems which feature TEE while other branches do not.

  3. (E3)

Confidentiality-Preserving Replicated Systems: Confidential Computing (CC)
(ccc, [n. d.]) protects data in use by performing computation involving
sensitive data in TEE, thus providing confidentiality protection for the
sensitive data. Since CC can increase the security assurances for sensitive
and regulated data, various initiatives have been actively focusing on
defining and accelerating its adoption. When deployed in a replicated system,
current CC platforms like CCF (Russinovich et al., 2019) typically assume each
node in the system is equipped with TEE. In circumstances where such
assumption is too strong, i.e., not every node in the system feature TEE, one
may still wish to attain the same security gurantee as the system
configuration wherein all nodes feature TEE. In such cases, the goal can be
achieved by using the network only for reaching consensus on the order of
execution, while the actual execution of the confidential computation is
carried out on the TEE-powered nodes. The computation results are then
replicated to other nodes.

The above distributed systems all aim to provision a replicated service using
a BFT protocol. One one hand, nodes in these systems are likely to feature
heterogenous machines, which are also subject to different maintainance or
administration. Consequently, it is rarely the case that an adversary can
coordinate a large number of Byzantine faults simultaneously as assumed in BFT
threat models. On the other hand, it is more likely the case that among the
faulty machines, only a few of them feature Byzantine behaviours, while others
are simply crash-faults. This claim can be justified in practice via the use
of TEE (Russinovich et al., 2019), which is widely available in recent
commodity processors. This is so because running code inside a TEE can
significantly restrict the malicious capability of a compromised node. That
is, when deploying procotol code inside a TEE, the TEE-powered node only fails
by crashing.

Given that BFT protocols are not efficient for such replicated systems, the
above two observations motivate us to design a new fault model for such
distributed systems.

###  3.2. System Model

We now present the system model that this work studies, with a focus on the
fault model.

We study a distributed system that comprises of $n$ deterministic and
independent nodes. The system provisions a replicated service that receives
requests from individual clients, and executes those requests in a totally
ordered sequence. In other words, the replicated service appears to the
clients as if it runs on a single non-faulty machine.

Most distributed systems make an assumption that nodes in the network are
homogeneous. That is, the nodes are presumed to share the same set of
capabilities, and admit similar vulnerabilities. Nonetheless, this is not
always necessarily the case. As can be seen from the above example systems,
nodes are likely to have heterogeneous machines. In view of this and the wide
availability of TEE in commodity processors, we study a heterogeneous system
wherein some nodes feature hardware-based TEE, while others are powered by
legacy systems which place trust on their OSs or hypervisors.

Each pair of nodes in the network communicate through a reliable,
authenticated point-to-point communication channel. In order to sidestep the
FLP impossibility (Fischer et al., 1982), we assume that the communication
channels are partially synchronous, i.e., messages that are sent repeatedly
with a finite timeout will be eventually delivered at its destination. This
assumption is commonly observed in existing distributed and replicated systems
(Dang et al., 2019; Kogias et al., 2016). Besides, there is no global clock.
Nodes process messages and execute requests at their own speed.

#### Mixed Fault Model:

It has been shown that the complexity of BFT protocols typically arises from
the ability of a Byzantine node to equivocate (i.e., issue conflicting
statements to different nodes without being detected) (Chun et al., 2007; Dang
et al., 2019). Given that code executed inside a TEE is integrity protected,
the malicious behaviours of a compromised node that is powered by TEE can be
significantly restricted. That is, when deploying protocol code inside the
TEE, a TEE-powered node, even compromised, is not able to equivocate. In other
words, a TEE-powered node only exibits crash failures. Thus, the use of TEE
can significantly reduce the communication complexity of BFT protocols.

In heterogeneous distributed systems wherein some nodes feature TEE while
others do not, different nodes can exibit different types of failures. In
particular, TEE-powered nodes only exhibit crash failures, while non-TEE nodes
feature Byzantine behaviours. We refer to this fault model as the mixed fault,
which is eleborated in Section 4.

###  3.3. Threat Model

Our threat model assumes that the Byzantine nodes are under adversarial
control. They may access (i.e., read and write) to other processes’ memory,
including that of the OS. They can also tamper with data persisted on
persistent storage, intercept and alter system calls.

The adversary is also able to initialize, stop and invoke the TEE enclaves of
the TEE-powered nodes. Nevertheless, its control over the TEE is limited, for
we make an assumption that the TEE’s attested execution mechanism is secure.
In contrast to Intel SGX’s threat model, we make no assumption on the
confidentiality protection of the enclaves, except for a few critical
cryptographic primitives such as key generation, random number generation or
attestation. That is, the TEE-powered nodes run in the seal-glassed proof
model that is able to attest to the correct execution of the codebase loaded
inside, but its execution is transparent (Tramer et al., 2017). This threat
model is particularly relevant in view of recent side-channel attacks against
Intel SGX (e.g., (Brasser et al., 2017)). While we leave attacks that
compromise confidentiality of attestation and other cryptographic keys (Van
Bulck et al., 2018) out of scope, we remark that techniques, both software and
hardware-based, hardening critical cryptographic operations against these
attacks are available (Kiriansky et al., 2018).

Finally, we assume the adversary is computationally bounded. It is not able to
break standard cryptographic assumptions. Besides, we exclude denial-of-
service attacks against the system in this study.

###  3.4. System Goals

Our system goal is efficient state machine replication (Schneider, 1990) under
the MFT model. It is desired that the system provides both safety and
liveness. That is, any two clients interact with the system receive consistent
responses, and valid requests from the clients are eventually executed.

In particular, we study a network of $n$ nodes, among which up to
$f=\frac{n-2}{3}$ can be subject to mixed faults. The argument for this is
provided in Section 5.2. Here, $f=f_{c}+f_{b}$, wherein $f_{c}$ denotes the
number of crash-faulty nodes, and $f_{b}$ that of Byzantine nodes. In
addition, we require that the number of TEE-powered nodes $n_{tee}\geq f+1$.
We refer to protocols that enable such replication as MFT protocols, which are
elaborated in Section 4.

##  4\. Mixed Fault Tolerance

In this section, we first elaborate on our MFT model by contrasting it against
related conventional and non-conventional fault tolerance models, thereby
highlighting MFT’s key characteristics. For clarity, we shall review those
models as we visit them. Then, we present two design principles that allow MFT
protocols to scale.

###  4.1. MFT vs. CFT/BFT

Recall that our system model presented in Section 3.2 does not assume any
global clock or known bounds of network latency. This assumption is also
observed by asynchronous CFT/BFT protocols. The difference between MFT and
asynchronous CFT/BFT arises from our treatment of node faults.

(a) Hybrid Fault Replicas.

(b) TEE-Powered Consensus.

(c) MFT Replicas.

Figure 1. Comparison between MFT and other hybrid fault models.

CFT protocols, such as Raft (Ongaro and Ousterhout, 2014), provide safety
regardless of network condition, and require partial synchrony to ensure
liveness. They tolerate up to $f=\frac{n-1}{2}$ crash failures. However, as
soon as there exists a single Byzantine node in the network, CFT’s threat
model is violated, and all security guarantees are voided. In contrast to CFT,
our MFT model affords some Byzantine nodes, and retains safety and liveness as
long as the number of faulty nodes does not exceed a predefined threshold.

BFT protocols assume a powerful adversary who wields absolute control over all
faulty nodes, causing them to deviate arbitrarily from their expected
behaviours. The most prominent BFT protocol is arguable PBFT (Castro et al.,
1999), which tolerates up to $f=\frac{n-1}{3}$ faults but incurs quadratic
communication complexity in term of the network size. Such communication
complexity hinders PBFT’s scalability (Dang et al., 2019; Dinh et al., 2017).
In opposition to BFT, MFT assumes that only a portion of the faulty nodes
exhibit Byzantine behaviours, whereas other faulty nodes only crash and do not
misbehave. This assumption allows MFT to trim down the communication overhead,
thereby improving the performance and scalability of the system.

###  4.2. MFT vs. Hybrid BFT

The complexity of BFT protocols typically arises from the ability of a
Byzantine node to equivocate (Chun et al., 2007; Dang et al., 2019). It has
been shown that without equivocation, it is possible to tolerate $f$ Byzantine
failures with only $n=2f+1$ nodes using the quorum size $f+1$. The smaller
network and quorum sizes result in lower computational and communicational
cost incurred in tolerating the same number of failures.

Building on this observation, a number of approaches have studied the hybrid
fault model. In such models, each node in the network is assumed to be
equipped with a trusted subsystem that only fails by crashing, whereas its
other components are untrusted and may fail arbitrarily. Figure 1(a) depicts
this threat model. The trusted subsystem is utilized to combat against
undetected equivocation. A common technique is to bind each message a node
broadcasts with a record in a log (which can be as simple as a monotonic
counter) maintained by the trusted subsystem. Since operations carried out by
the trusted subsystem cannot be equivocated, malicious nodes cannot send
conflicting messages without being convicted by others.

Alternatively, one can also eliminate equivocation by running the entire
codebase of a consensus protocol inside a TEE (Figure 1(b)). This approach,
adopted by CCF (Russinovich et al., 2019), effectively reduces a node’s fault
model from BFT to CFT. Consequently, any non-Byzantine consensus protocols,
such as Raft (Ongaro and Ousterhout, 2014) or Paxos (Lamport et al., 2001),
can be applied. CFT consensus protocols could then tolerate $f$ Byzantine
failures with only $n=2f+1$ nodes using the quorum size of $f+1$, resulting in
lower communication and computational overhead. While this approach is similar
to the hybrid fault model described earlier in their assumptions on the
availability of TEE at each node, it incurs a large trusted code base (TCB)
which is undesirable for security (McCune et al., 2007). A large TCB makes
security analysis of the implementation bewildering, which likely exposes the
system to potential vulnerabilities.

In contrast to the above two hybrid fault models, MFT does not require each
node in the network to be equipped with TEE. Our MFT model allows for a
portion of the nodes to behave arbitrarily (i.e., Byzantine nodes), whereas
hybrid fault models collapse as soon as there exists a single Byzantine node
in the network. Figure 1(c) shows the heterogeneity of nodes in an MFT system.

###  4.3. MFT vs. Flexible BFT

Malkhi et al. (Malkhi et al., 2019) introduced Flexible BFT, which tolerates
alive-but-corrupt faults. Flexible BFT assumes that these alive-but-corrupt
nodes may exhibit Byzantine behaviours. However, they do so strictly for the
purpose of breaking the protocol’s safety. In case they are unable to
compromise safety, they will not hinder the protocol’s liveness. Furthermore,
Flexible BFT allows clients interacting with the replicated service to hold
different assumptions or beliefs about the system, based on which they
interpret the protocol transcript and make commit decisions. Flexible BFT
guarantees both safety and liveness for all clients with correct beliefs.

Flexible BFT justifies the alive-but-corrupt faults based on an observation
that the adversary may benefit if safety is broken, for instance in double-
spending attacks, while it is unlikely to gain anything from broken liveness.
The authors (Malkhi et al., 2019) further argue that alive-but-corrupt nodes
are incentivised to keep the liveness as they could collect service fee. These
assumptions are in line with rational protocol design treatment wherein the
adversary is assumed to misbehave only if such action yields (economic) gain
(Badertscher et al., 2018).

On the contrary, MFT does not make any assumption on the rationale of the
corrupted nodes. Our threat model pays more attention to the capability that
the adversary wields and the constraints that it adheres to. For instance, if
a TEE’s attested execution protection is intact, the adversary may attempt to
disconnect it from the network, but it cannot compromise TEE’s execution
integrity. In such a case, the adversary cannot cause the TEE-powered nodes to
violate safety, yet it can tamper with their I/O and network connections in an
attempt to prevent liveness.

###  4.4. MFT vs. XFT

Cross Fault Tolerance, or XFT for short (Liu et al., 2016), studies a system
model which admits both crash and Byzantine faults. Beyond crash and Byzantine
faults, XFT explicitly defines network fault as an event wherein some non-
faulty nodes could not communicate synchronously with each other (i.e., a
message exchanged between two nodes is delivered and processed within a known
latency $\Delta$). A node is considered partitioned if it does not belong to a
largest synchronous subset. In a network of $n$ nodes, XFT protocols are able
to tolerate up to $n$ crash faults without compromising safety, and tolerate
some Byzantine faults together with network faults, so long as there exist a
majority of nodes that are not faulty and communicate synchronously.

The key difference between XFT and our MFT model is XFT’s separation of node
and network faults. Similar to CFT and BFT, our MFT model considers only
machine faults, and relies on partial synchrony to sidestep the FLP
impossibility (Fischer et al., 1982). By separating network from node faults,
XFT can guarantees safety in two modes: (i) there is no Byzantine faults,
regardless of the number of crash-faulty and partitioned replicas; (ii) there
exist some Byzantine faults, but a majority of nodes remain correct and not
partitioned, i.e., the total number of crash, Byzantine and network faults
combined does not exceed $\frac{n-1}{2}$. MFT, on the other hand, offers
safety when $f\leq\frac{n-2}{3}$ ($f$ is the total number of crash and
Byzantine nodes) in partially synchronous network.

###  4.5. Design Principles for MFT Protocols

So far we have contrasted MFT against CFT, BFT, and other non-conventional
fault tolerance models. We now draw observations from the discussion and
comparison presented above, and codify them into two design principles.

Our first observation, which is applicable not only to MFT but also to other
distributed systems in general, is that communication complexity is typically
a bottleneck to the performance and efficiency of the system. Various works
have shown that this is indeed the case for many different fault tolerance
models and protocol designs (Dinh et al., 2017). Consequently, reducing the
communication complexity contributes to the improvement of the system’s
performance.

MFT protocols essentially implement a replicated state machine system that is
driven by a designated node in the network, which is typically called leader.
That is, the leader processes requests sequentially and the remaining nodes in
the network merely follow. When the leader becomes faulty, it is replaced by
another node via a subprotocol, during which the performance of the system
suffers significantly (Dang et al., 2019). Our second observation is that in
heterogeneous settings such as those studied under the MFT model, the choice
of the leader plays a crucial role in tuning the performance of the system.

These two observations motivate the following two design principles for MFT
protocols:

  1. (P1)

Leadership favours non-equivocating nodes. Recall that MFT assumes both types
of failures, namely crash and Byzantine faults. It is well established that
most complications underlying BFT protocols are due to equivocation. In MFT,
only Byzantine nodes may equivocate, whereas such behaviour is never conducted
by crash faulty nodes. Consequently, as long as a protocol is led by a non-
equivocating node, a majority of consensus messages can be routed through and
verified by the leader on behalf of other nodes. This communication pattern
poses much less overhead on the network. Furthermore, computation cost
incurred in verifying authenticated messages can also be saved. We remark that
this principle advocates giving higher priority to non-equivocating node in
attaining the leadership, but it does not impose strict restriction on
potentially Byzantine node never becoming the leader.

  2. (P2)

Aggragation of Consensus Messages. In case the leadership is taken by a node
that may feature equivocation, it is important to ensure that its
misbehaviour, if any, does not compromise safety. Such node should not be
trusted with collecting and verifying consensus messages on others’ behalf.
Instead, the protocol should incorporate cryptographic primitives that allow
consensus messages to be efficiently aggregated in such a way that receiving
and verifying an aggregated message is equivalent to receiving and verifying a
quorum of individual messages (e.g., CoSi (Syta et al., 2016)), without
relying on any trusted third party. This clearly improves the communication
complexity of the system.

Based on these two principals, we retrofitted the Raft procotol for the MFT
model, and refer to the resulting protocol as MRaft, which is elaborated in
Section 5.

##  5\. MRaft

In this section, we present MRaft, which is a distributed consensus protocol
designed to operate under the MFT model. MRaft is built upon Raft (Ongaro and
Ousterhout, 2014). However, instead of tolerating up to $f$ crash-faults using
a network of $n=2f+1$ nodes as Raft does, MRaft employs a network of $n=3f+2$
nodes to tolerate up to $f$ mixed faults. Some nodes in the network are
assumed to be equipped with TEE with intact integrity protection, and thus
never equivocate or deviate from the protocol description.

We require that the number of TEE-powered nodes $n_{tee}\geq f+1$. This
assumption is not strictly required, but it significantly increases the chance
that a TEE-powered node is elelected as the leader. We further assume that
each node should know TEE-capability of other nodes in the network, i.e.,
whether the other node is equipped with and running the consensus codebase
inside a TEE, which can be achieved via TEE’s remote attestation mechanism
(Anati et al., 2013).

Each node in the network implements a state machine, and maintains a
replicated log which records a sequence of commands or requests the network
has served. The goal of MRaft is to ensure logs of different nodes in the
network converge, and each node commits (or executes) exactly the same
sequence of commands.

Similar to Raft, nodes in MRaft can be in one of the three roles, namely
leader, follower and candidate. Our protocol proceeds in terms. In each term,
a node is selected to serve as a leader, while all other nodes are followers.
Leader election in MRaft favours TEE-powered nodes, which are assumed to be
non-equivocating thanks to TEE’s execution integrity protection. In the common
case where a TEE-powered node attains leadership, the message pattern and
communication complexity of MRaft is similar to those of Raft. The leader
processes most of the messages, while the followers passively receive and
respond to messages from the leader.

In a very rare case where all TEE-powered nodes fail to attain leadership, the
protocol is led by a non-TEE node. In such case, the leader cannot be trusted
to verify followers’ messages on behalf of the network. The first approach to
sidestep this issue is to employ an all-to-all communication pattern wherein a
node broadcasts its messages to the network (similar to the message pattern of
PBFT (Castro et al., 1999)). However, this will results in a communication
complexity of $O(n^{2})$, which is detrimental to the scalability of the
protocol (Dang et al., 2019). Alternatively, one can tasks the leader to
collect messages containing digital signatures from all followers. Once it has
collected a quorum of signatures, it broadcasts such quorum to the network,
incurring a communication complexity of $O(n)$ instead of $O(n^{2})$.
Nonetheless, the need of each node to independently verify quorum of
signatures may poses a hindrance on the performance of the protocol. In view
of these encumbrances, we follow Byzcoin (Kogias et al., 2016) in using CoSi
(Syta et al., 2016) to implement collective signing. This implementation
enables a potentially equivocating leader to collect and aggregate messages
from the followers. It suffices for a follower to receive and verify an
aggregated message before proceeding, as opposed to verify a quorum of
messages as in the two naive approaches mentioned earlier.

We detail below the concrete prescription of MRaft in a common case wherein
the protocol is led by a TEE-powered node (Section 5.1) and in a very rare
case wherein the non-TEE node attains leadership (Section 5.3). For clarity of
exposition, we shall denote the leader by $L$, and a follower $i$ by $p_{i}$.
Each leader $L$ is associated with a term $t$, and indexes a request $r$ it
receives from the client in its log with a counter $j$. Both the term number
$t$ and the index $j$ are increased monotonically. That is, each request $r$
is uniquely identified by a 3-tuple $\langle t,j,r\rangle$. In addition to the
replicated log, each node keeps track of a LastCommitIndex which is the index
of the latest entry in its own replicated log that is known to be committed,
which also increases monotonically over time. With each $p_{i}$, $L$
establishes an authenticated communication channel, and a timeout $T_{i}$
which is a window of time during which $p_{i}$ expects to receive a message
from $L$. Should there be no request from the client during the timeout window
$T_{i}$, $L$ sends a HeartBeat message containing $L$’s term number and
LastCommitIndex to $p_{i}$ so as to maintain its leadership. If $p_{i}$ fails
to hear from $L$ once its timeout $T_{i}$ has passed, it assumes $L$ is faulty
and requests for a new leader. We defer the leader election mechanism to
Section 5.2.

###  5.1. TEE-Powered Leader

#### Protocol.

If the leader $L$ is equipped with TEE and running the protocol inside the
TEE, it is assumed that $L$ never deviates from its expected behaviour (i.e.,
execution integrity is preserved). It may fail only by crashing. In such case,
the protocol proceeds as follows:

  1. (1)

Upon receiving a request $r$ from a client, the leader $L$ whose term is $t$
assigns $r$ an index $j$, and puts $\langle t,j,r\rangle$ onto its log.

  2. (2)

$L$ broadcasts $\langle t,j,r\rangle$ to the network.

  3. (3)

Upon receiving $\langle t,j,r\rangle$, a follower $p_{i}$ checks if it was
from the node it believes to be the leader, and if $r$ is valid (i.e.,
committing $r$ does not compromise safety). If so, it puts $\langle
t,j,r\rangle$ to its log and responds $L$ with an acknowledgement
$\langle\texttt{ack}_{i},t,j,r\rangle$.

  4. (4)

Upon receiving a quorum of $q=2f+1$ acknowledgements for $r$, the leader
commits $r$ (i.e., executes $r$ and applies the result to its state machine)
and all uncommitted requests in its log whose index is smaller than that of
$r$, if any. It produces a certificate $\texttt{Cert}_{r}$, which attests a
fact that $r$ has been replicated on a quorum of nodes. Subsequently, $L$
broadcasts $\texttt{Cert}_{r}$ to the network.

  5. (5)

Upon receiving $\texttt{Cert}_{r}$ from $L$, a follower $p_{i}$ commits $r$
and all uncommitted requests in its log whose index is smaller than that of
$r$, if any.

#### Remarks.

Our protocol requires the leader $L$ to broadcast $\texttt{Cert}_{r}$ in its
announcement of request $r$’s commit (Step 4). This enables every node in the
network to independently verify that $r$ has been replicated on a quorum of
nodes, and that the quorum agrees on the total order of requests. Since quorum
size in our protocol is $q=2f+1$, quorums must be intersected at at least one
honest node. Consequently, while a Byzantine node could equivocate, or tamper
with term and index value in its messages, it is unable to cause the entire
network to violate safety.

###  5.2. Leader Election

As mentioned earlier, during normal operation, $L$ periodically sends
HeartBeat message containing its term number and LastCommitIndex to followers
so as to maintain its leadership. Communication during the consensus round can
also be deemed as HeartBeat messages, for it conveys $L$’s term number and
LastCommitIndex, as well as the fact that $L$ is fully functional. When a
follower $p_{i}$ receives such messages, it acknowledges with a corresponding
ack via an authenticated channel. $p_{i}$ may rely on $L$’s LastCommitIndex to
assure that its replicated log and state are in sync with $L$’s. Should
$p_{i}$ finds its log and state outdated, it retrieves the missing requests
(i.e., log entries) and commits them, thereby updating its own state to match
that of $L$.

For each follower $p_{i}$, $L$ institutes a unique and randomised timeout
$T_{i}$ chosen from a fixed interval. Since MRaft favors TEE-powered node in
obtaining leadership, the timeout interval (i.e., a fixed interval from which
$T_{i}$ is drawn) between $L$ and a TEE-powered node, say $[T_{a},T_{b}]$ is
configured to be smaller than that between $L$ and a non-TEE follower, say
$[T_{c},T_{d}]$. That is, $T_{a}<T_{c}\wedge T_{b}<T_{d}$.

Should a follower $p_{i}$ fail to receive any message from $L$ after its
$T_{i}$ has elapsed, it switches its role to candidate and increases its term
number. Subsequently, $p_{i}$ broadcasts a $\texttt{RequestVote}=\langle
p_{i},newTerm,lastLogIndex\rangle$ to the network in an attempt to assume
leadership, in which $newTerm$ is its current term number, and $lastLogIndex$
is the index of the latest entry in its replicated log. A leader election in
MRaft is closely related to that of Raft, with some adjustments in how a
recipient handles a RequestVote message.

Upon receiving a RequestVote from $p_{i}$, a node $p_{j}$ grants its vote if
all following conditions are met:

  * •

$p_{i}$ is indeed a node within the network, and RequestVote is properly
signed by $p_{i}$

  * •

$p_{j}$’s own timeout $T_{j}$ has elapsed and it has not received any message
from its current leader.

  * •

$newTerm$ in the RequestVote is larger than its own current term.

  * •

$p_{j}$ has not granted its vote to any other candidate.

  * •

$p_{i}$’s replicated log is more up-to-date than that of $p_{j}$, as
determined by the indice of the last entries.

In case $p_{j}$ receives a RequestVote from $p_{i}$ before its timeout $T_{j}$
with its current leader has not elapsed, it queues $p_{i}$’s RequestVote, if
it has not queued any other candidate’s RequestVote, and $p_{i}$’s log is more
up-to-date than its own replicated log. When there is a competing RequestVote,
$p_{j}$ keeps that of a node which is more up-to-date, and discards the other.
If $p_{j}$ receives a valid message from its current leader, it discards any
RequestVote that it has queued. When $T_{j}$ has elapsed, $p_{j}$ grants its
vote to $p_{i}$.

A vote is essentially an authenticated message from $p_{j}$ that is publicly
verifiable. A node wins an election once it has collected votes from a quorum
of $q=2f+2$ nodes. If the leader is equipped with TEE, it can leverage the TEE
to produce a compact proof of leadership by aggregating the votes, as in step
(4) of the protocol described in Section 5.1. On the other hand, if a non-TEE
candidate wins the election, the proof of its leadership is a collection of
the votes it has thus received. The new leader announces its authority by
broadcasting a HeartBeat message containing its proof of leadership along with
the new term number to the network. Upon receiving such message, a follower
verifies if the proof of leadership is valid before switching to the new
leader and updating its term number accordingly.

#### Remarks.

We remark that the quorum size necessitated for leader election is $q=2f+2$.
Hence, the network needs $n=3f+2$ nodes to be correctly operational. This is
so because there exists a possibility that an honest node is disconnected from
the network during the leader election. In such a scenario, it may happen that
there are $f$ Byzantine followers, $f$ honest and up-to-date followers, $f$
honest followers that hold stale view of the replicated log, and a candidate
that may have a stale view. If the quorum size for leader election is
$q=2f+1$, it may happen that the log of elected leader miss some entries
committed by the previous leader, and his leadership in the new term may
accidentally undo the requests that had been committed earlier. To avoid this,
the candidate must obtain $q=2f+2$ votes. Therefore, the network needs
$n=3f+2$ nodes to tolerate $f$ failures.

###  5.3. Non-TEE Leader

Note that MRaft employs a network of $n=3f+2$ to tolerate up to $f$ mixed
faults, among which up to $f$ can be Byzantine faults. Since we require that
the number of TEE-powered nodes $n_{tee}\geq f+1$, thus, it is high likely
that a TEE node becomes leader during the leader election process. In a very
rare case that the leader election fails to elect a TEE-powered node, we can
repeat the leader election process until a TEE-powered node is elected as the
leader. However, this approach would sacrifice the system’s liveness during
the leader election process. Alternatively, we can set a timeout value for the
period that the system is electing a TEE-powered node as leader. When this
timeout is reached, we can temporarily fall back to a safe BFT protocol until
a TEE node is available and elected as leader. That is, we use the fallback
BFT protocol to ensure that the system’s liveness is lost only during the
timeout period.

Below is the fallback protocol we prescribed for the circumstance when a TEE-
powered node is temporarily not eleteced as the leader.

#### Protocol

When the leader is not equipped with TEE, it cannot be trusted to aggregate
responses from the followers as in the previous case. Consequently, MRaft
employs CoSi to save on the communication complexity. The protocol proceeds as
follows:

  1. (1)

Upon receiving a request $r$ from a client, the leader $L$ whose term is $t$
assigns $r$ an index $j$, and puts $\langle t,j,r\rangle$ onto its log.

  2. (2)

$L$ initiates a CoSi round to drive the network to generate the collective
signature for a message $\langle t,j,r\rangle$. A successful CoSi round
effectively replicates $\langle t,j,r\rangle$ on the followers’ logs.

  3. (3)

Upon receiving $\langle t,j,r\rangle$, during the execution of the CoSi
protocol (described in Section 2.3), a follower $p_{i}$ checks if it was from
the node it believes to be the leader, if $r$ is valid, and if the term $t$
and index $j$ match its log ($j$ should immediately follow the latest
committed entry in its log). If so, it puts $\langle t,j,r\rangle$ to its log
and completes the final phase of the CoSi protocol.

  4. (4)

Once the network has completed the CoSi rounds, $L$ should have obtained the
collective signature $\texttt{CoSig}_{r}$ for $\langle t,j,r\rangle$. It
checks if a quorum of $q=2f+1$ has partaken in the collective signing using
the metadata contained in the collective signature. If this is the case, it is
assured that the $\langle t,j,r\rangle$ has been replicated on a quorum of
nodes, and it is safe for $L$ to commit $r$ and all uncommitted requests in
its log whose index is smaller than that of $r$, if any. Subsequently, $L$
broadcasts $\texttt{CoSig}_{r}$ to the network.

  5. (5)

Upon receiving $\texttt{CoSig}_{r}$, a follower checks if a quorum of $q=2f+1$
nodes have co-signed $\texttt{CoSig}_{r}$. If so, $p_{i}$ commits $r$ and all
uncommitted requests in its log whose index is smaller than that of $r$, if
any.

#### Remarks

In case the leader $L$ is equipped with a TEE, MRaft relies on the trusted
execution to produce a certificate $\texttt{Cert}_{r}$ which attests a fact
that a request $r$ has been replicated on a quorum of nodes. In case $L$ does
not feature TEE, MRaft resorts to the CoSi protocol (and relies on its
security) to produce $\texttt{CoSig}_{r}$, which conveys the same significance
that $\texttt{Cert}_{r}$ does.

##  6\. Implementation

In this section, we describe the implementation details of our prototype
MRaft. Our prototype is based on the codebase of CCF (Russinovich et al.,
2019), which is an open-source framework for building confidential replicated
services.

A CCF network (ccf, [n. d.]) consists of several nodes, each running on top of
a TEE, such as Intel SGX. Each node runs the same application, which can
mutate or read the in-enclave-memory _key-value store_ that is replicated
across all nodes in the network. The key-value store is a collection of maps
(associating a key to a value) that are defined by the application. Changes to
the key-value store must be _agreed_ by a _quorum_ number of nodes before
being applied, wherein the quorum value depends on the _consensus_ algorithm
selected.

CCF supports two consensus protocols, i.e., CFT and BFT. CFT is the default
consensus protocol and its implementation is based on Raft (Ongaro and
Ousterhout, 2014). The BFT implementation is a derivative from PBFT-PK (PBFT
using signatures) (Castro et al., 1999), with additional features specific to
CCF (Shamis et al., 2021).

Each CCF network has a network identity public-key certificate (aka, _service
certificate_), used for TLS server authentication, and the corresponding
_private key_ always resides in enclave memory. This key pair is generated
when the first node starts. Each CCF node is identified by a fresh _public-key
certificate_ endorsed by the enclave quote. This _node-identity certificate_
is used to authenticate the node when it joins the network, and to sign
entries committed by the node to the ledger during its time as primary.

#### Modifications to CCF’s Codebase

A CCF network only allows TEE nodes with a valid enclave quote to join the
network, which is achieved by verifying a joining node’s enclave quote through
remote attestation. For non-TEE nodes, we similary identify them using a
public-key certificate issued by the _service certificate_ , i.e., the service
certificate acts as the root CA for these node-identity certificates. We
retrofitted CCF’s codebase to allow non-TEE nodes with a valid _node-identify
certificate_ to join the network.

In CCF, each node to node pair establish a symmetric traffic key, using an
authenticated Diffie-Hellman key exchange. This key is used to authenticate
messages sent between nodes. For messages sent from non-TEE nodes, we
retrofitted CCF’s codebase to append a signature to such messages; the
signatures are generated using the private key corresponding to the _node-
identity public key_. Thus, TEE nodes can verify the authenticity of such
messages using the contained signature.

#### Changes to CCF’s Raft Implementation

To implement MRaft, we retrofitted the Raft implementation in _ccf-1.0.0_ ,
and changed its _quorum_ size to $2f+2$, wherein $f=\frac{n-2}{3}$.
Specifically, we modified the code so that the TEE-powered leader institutes
smaller leader-election timeout values for TEE nodes than for non-TEE nodes,
which makes leader election favors TEE nodes. We also modified the code so
that, during normal operation, whenever a TEE-powered leader commits entries,
it generates a commit certificate for these entries. Followers will update
their commit_idx according to the correponding comit certificates.

#### Remarks.

We remark that we did not implement the rare case when a non-TEE node becomes
leader. In such a scenario, the CoSi scheme (Syta et al., 2016) is used to
aggregate authenticated messages, and the performance is expected to be worse
than the case when a TEE node leads the protocol. In our current
implementation, when a non-TEE node becomes leader, we make the protocol
“idle-waiting” until a TEE node is available in the network.

In addition, transactions in CCF are committed in batch, rather than one by
one. The maximal batch size for transcations defaults to 20,000 bytes (20
KiB). However, when the request timeout reaches, it triggers the comitting for
transcations since last commit. Therefore, the batch size for transactions
varies, with a maximal size of 20 KiB.

##  7\. Evaluation

This section presents our experimental study of MRaft, focusing on its
performance (i.e., transaction throughput and latency) and scalability.

We conducted experiments on Microsoft Azure cloud platform using SGX-enabled
virtual machines (VMs) backed by Intel Xeon E-2288G processor, i.e.,
DCsv2-series Confidential Computing VMs (azu, [n. d.]). We chose size
“Standard_DC4s_v2” for all VMs, each configured with 4 vCPUs, 112 MiB EPC
memory, 16 GiB memory, and 30 GiB SSD.

For all experiments, we run each MRaft node in a separate VM, running Ubuntu
18.04.5. We deploy these VMs evenly across five Azure datacenters, i.e., “East
US”, “Canada Central”, “UK South”, “West Europe”, and “Southeast Asia”. We
issue client requests to the MRaft backed service using a “Standard D8as_v4”
VM located at the “East US” datacenter; this VM is configured with 8 vCPUs, 32
GiB RAM and 30 GiB SSD, running Ubuntu 20.04.2. We report the average
communication latency between these nodes in Table 1.

Table 1. Network latency (ms) between nodes on Azure

Datacenter | East US | Canada Central | UK South | West Europe | Southeast Asia
---|---|---|---|---|---
East US | 1.71 | 27.89 | 75.34 | 82.82 | 219.86
Canada Central | 27.89 | 3.50 | 90.0 | 93.94 | 218.11
UK South | 75.34 | 90.0 | 1.27 | 8.95 | 156.12
West Europe | 82.82 | 93.94 | 8.95 | 2.35 | 160.39
Southeast Asia | 219.86 | 218.11 | 156.12 | 160.39 | 2.12

#### Benchmarks

We use two benchmarks in the experiments. The first benchmark runs a Logging
application, which supports storing a message with id and retriving the stored
message with a given id. This benchmark invovles 100,000 transcations of
storing messages of the form $\langle\texttt{id},\texttt{msg}\rangle$, wherein
id is a unique integer and msg is the SHA256 checksum of id. Since this
benchmark only involves transactions on a single table, for the second one, we
use the more complicated TPC-C benchmark (tpc, [n. d.]). The TPC-C database is
composed of nine types of tables with a wide range of row sizes and
cardinalities. TPC-C involves a mix of five concurrent transactions of
different types and complexity. Therefore, there is greater diversity in the
data manipulated by the five types of transactions and thus greater database
contention. In the second benchmark, we also issue 100,000 transcations.

In all experiments, transaction throughput is measured at the leader replica
and latency at the clients. Latency is averaged over all transactions in an
experiment and counts the time from sending a command on the client to
receiving a global commit confirmation. Unless otherwise stated, the results
presented in this section are averaged over $10$ independent runs. We focus on
normal operation, and do not report performance of the system in case that the
leader crashes or during the leader election process (Ongaro and Ousterhout,
2014).

#### Baselines

We compare MRaft against two baselines: (i) PBFT, wherein each node runs PBFT
without any TEE hardening; and (ii) Raft-TEE, wherein each node runs Raft
within a TEE. Note that MRaft, PBFT and Raft-TEE all aim to achieve the same
goal, i.e., state machine replication in a network wherein all nodes are
running within adversarial environments. A brief comparison of them is shown
in Table 2. For all experiments, we configure the number of TEE nodes in MRaft
to be $\lfloor\frac{n}{2}\rfloor$, wherein $n$ is the network (i.e., cluster)
size.

Table 2. Comparison of MRaft with PBFT and Raft-TEE

| MRaft | PBFT | Raft-TEE
---|---|---|---
TEE Availability | Some nodes | None | All nodes
| Fault-Tolerance
---
Threshold
$f=\frac{n-2}{3}$ | $f=\frac{n-1}{3}$ | $f=\frac{n-1}{2}$

511203247$0$$0.5$$1$$1.5$$2$$\cdot 10^{4}$$n$Transactions per
secondMRaftPBFTRaft-TEE (a) Logging

511203247$0$$0.5$$1$$1.5$$2$$\cdot 10^{4}$$n$Transactions per second (b) TPC-C

Figure 2. Throughput of MRaft, PBFT and Raft-TEE with respect to different
cluster sizes ($n$) on Azure. Here, Raft-TEE is the case wherein each node
runs Raft within a TEE.

#### Experimental Results.

Now we present our evaluation results. We remark that in all comparisons, we
have normalized Raft-TEE’s values to settings such that it has the same fault
threashold $f$ with MRaft and PBFT.

Figure 2 presents the throughput of MRaft, PBFT, and Raft-TEE with respect to
different cluster sizes ($n$) on Azure. As can be seen, MRaft’s throughput
outperform both PBFT and Raft-TEE in both benchmarks, regardless of the
cluster size.

511203247$0$$5$$10$$15$$n$Latency (ms)MRaftPBFTRaft-TEE (a) Logging

511203247$0$$5$$10$$15$$n$Latency (ms) (b) TPC-C

Figure 3. Latency of MRaft, PBFT and Raft-TEE with respect to different
cluster sizes ($n$) on Azure. Here, Raft-TEE is the case wherein each node
runs Raft within a TEE.

Figure 3 depicts the latency of MRaft, PBFT, and Raft-TEE with respect to
different cluster sizes ($n$) on Azure. Interestingly, MRaft’s latency is
smaller than both PBFT and Raft-TEE in both benchmarks, regardless of the
cluster size. That is, in terms of performance (i.e., transaction throughput
and latency), MRaft outperforms both PBFT and Raft-TEE.

Next, we compare the scalability of MRaft with that of PBFT and Raft-TEE. As
shown in Figure 2, as the cluster size increases, the throughput of PBFT and
Raft-TEE drops much faster than MRaft. Similarly, as can be seen in Figure 3,
the latency of PBFT and Raft-TEE increases much faster than MRaft when the
cluster size increases. Even when the cluster size increases to $n=47$,
MRaft’s throughput still does not drop that much, and its latency also does
not increase that much, as compared with PBFT and Raft-TEE. These results
demonstrated MRaft’s excellent scalability.

In summary, MRaft’s performance (i.e., transaction throughput and latency)
outperforms both PBFT and Raft-TEE. At the same time, MRaft also provides
better scalability than PBFT and Raft-TEE. That is, MFT protocols achieve the
same security gurantees as their BFT counterparts, but also provide better
performance and scalability.

##  8\. Related Work

The bottleneck of performance (i.e., transaction throughput and latency) and
scalability in blockchain systems or distributed ledger systems is typically
the underlying consensus protocol. Consensus protocols are used by replicas to
agree on an order for transactions. A majority of current ledger systems
(Androulaki et al., 2018; goq, [n. d.]) rely on BFT consensus protocols.

#### Improving BFT Protocols.

Several recent works have improved the scalability of BFT protocols. Using
threshold cryptograph, SBFT (Golan-Gueta et al., 2019) proposes a variant of
PBFT that scales to larger consensus groups. Byzcoin (Kogias et al., 2016)
also builds on PBFT and dynamically forms consensus groups. HotStuff (Yin et
al., 2019) can also scale to hundreds of replicas using threshold
cryptography.

#### Improving Consensus Protocols using TEE

Several works have proposed to improve the efficiency of BFT protocols using
TEE (Behl et al., 2017; Chun et al., 2007; Russinovich et al., 2019). These
systems typically assume that each node is equipped with a small trusted
subsystem that fails only by crashing, whereas other untrusted components in a
node may fail or misbehave arbitarily. The use of such trusted subsystems
reduces the number of requried nodes to tolerate $f$ failures. However, this
line of protocols impose a trust assumption on each and every node
participating in the system, which may not be applicable to settings wherein
participants have different hardware configurations. Unlike existing works, we
explore a new approach to designing efficient distributed fault-tolerant
systems that tolerate a combination of crash and Byzantine faults, which we
refer to as mixed fault tolerance (MFT).

##  9\. Conclusion

We proposed a new approach, which leverages TEE, to designing efficient
distributed fault-tolerant protocols (i.e., MFT protocols) that tolerate a
combination of crash and Byzantine faults. We identified two key principles
for designing efficient MFT protocols, and showcased these two principles by
prescribing an MFT protocol, namely, MRaft. We implemented a prototype of
MRaft, integrated it into the CCF (Russinovich et al., 2019) blockchain
framework, conducted experiments in realistic deployment settting, and
demonstrated the efficiency of our approach.

## References

  * (1)
  * sgx ([n. d.]) [n. d.].  Attestation Services for Intel SGX.  https://software.intel.com/content/www/us/en/develop/topics/software-guard-extensions/attestation-services.html.
  * ccf ([n. d.]) [n. d.].  CCF Documentation.  https://microsoft.github.io/CCF/main/index.html.
  * ccc ([n. d.]) [n. d.].  Confidential Computing Consortium.  https://confidentialcomputing.io/.
  * int ([n. d.]) [n. d.].  Intel 64 and IA-32 Architectures Software Developer’s Manual .  https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf/.
  * azu ([n. d.]) [n. d.].  Microsoft Azure Confidential Computing.  https://azure.microsoft.com/en-us/solutions/confidential-compute/.
  * goq ([n. d.]) [n. d.].  Quorum.  https://github.com/ConsenSys/quorum.
  * tpc ([n. d.]) [n. d.].  TPC-C.  http://www.tpc.org/tpcc.
  * Anati et al. (2013) Ittai Anati, Shay Gueron, Simon Johnson, and Vincent Scarlata. 2013\.  Innovative technology for CPU based attestation and sealing. In _Proceedings of the 2nd international workshop on hardware and architectural support for security and privacy_ , Vol. 13. ACM New York, NY, USA.
  * Androulaki et al. (2018) Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolic, Sharon Weed Cocco, and Jason Yellick. 2018\.  Hyperledger fabric: a distributed operating system for permissioned blockchains. In _EuroSys_. ACM, 30:1–30:15.
  * Badertscher et al. (2018) Christian Badertscher, Juan Garay, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. 2018\.  But why does it work? A rational protocol design treatment of bitcoin. In _Annual international conference on the theory and applications of cryptographic techniques_. Springer, 34–65.
  * Behl et al. (2017) Johannes Behl, Tobias Distler, and Rüdiger Kapitza. 2017\.  Hybrids on steroids: SGX-based high performance BFT. In _Proceedings of the Twelfth European Conference on Computer Systems_. 222–237.
  * Bernstein et al. (2012) Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. 2012.  High-speed high-security signatures.  _Journal of cryptographic engineering_ 2, 2 (2012), 77–89.
  * Brandenburger et al. (2017) Marcus Brandenburger, Christian Cachin, Matthias Lorenz, and Rüdiger Kapitza. 2017.  Rollback and forking detection for trusted execution environments using lightweight collective memory. In _DSN_.
  * Brasser et al. (2017) Ferdinand Brasser, Urs Müller, Alexandra Dmitrienko, Kari Kostiainen, Srdjan Capkun, and Ahmad-Reza Sadeghi. 2017.  Software grand exposure:$\\{$SGX$\\}$ cache attacks are practical. In _11th $\\{$USENIX$\\}$ Workshop on Offensive Technologies ($\\{$WOOT$\\}$ 17)_.
  * Castro et al. (2003) Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, Animesh Nandi, Antony Rowstron, and Atul Singh. 2003.  SplitStream: high-bandwidth multicast in cooperative environments.  _ACM SIGOPS Operating Systems Review_ 37, 5 (2003), 298–313.
  * Castro et al. (1999) Miguel Castro, Barbara Liskov, et al. 1999\.  Practical Byzantine fault tolerance. In _OSDI_ , Vol. 99. 173–186.
  * Chun et al. (2007) Byung-Gon Chun, Petros Maniatis, Scott Shenker, and John Kubiatowicz. 2007.  Attested append-only memory: Making adversaries stick to their word.  _ACM SIGOPS Operating Systems Review_ 41, 6 (2007), 189–204.
  * Costan et al. (2016) Victor Costan, Ilia Lebedev, and Srinivas Devadas. 2016\.  Sanctum: Minimal hardware extensions for strong software isolation. In _25th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 16)_.
  * Dang et al. (2019) Hung Dang, Tien Tuan Anh Dinh, Dumitrel Loghin, Ee-Chien Chang, Qian Lin, and Beng Chin Ooi. 2019\.  Towards scaling blockchain systems via sharding. In _Proceedings of the 2019 International Conference on Management of Data_.
  * Dinh et al. (2017) Tien Tuan Anh Dinh, Ji Wang, Gang Chen, Rui Liu, Beng Chin Ooi, and Kian-Lee Tan. 2017\.  Blockbench: A framework for analyzing private blockchains. In _Proceedings of the 2017 ACM International Conference on Management of Data_. 1085–1100.
  * Fischer et al. (1982) Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1982\.  _Impossibility of distributed consensus with one faulty process._ Technical Report. Massachusetts Inst of Tech Cambridge lab for Computer Science.
  * Golan-Gueta et al. (2019) Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019.  SBFT: A Scalable and Decentralized Trust Infrastructure. In _DSN_. IEEE, 568–580.
  * Kiriansky et al. (2018) Vladimir Kiriansky, Ilia Lebedev, Saman Amarasinghe, Srinivas Devadas, and Joel Emer. 2018\.  DAWG: A defense against cache timing attacks in speculative execution processors. In _2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 974–987.
  * Kogias et al. (2016) Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. 2016.  Enhancing bitcoin security and performance with strong consistency via collective signing. In _25th $\\{$usenix$\\}$ security symposium ($\\{$usenix$\\}$ security 16)_. 279–296.
  * Lamport et al. (2001) Leslie Lamport et al. 2001\.  Paxos made simple.  _ACM Sigact News_ 32, 4 (2001), 18–25.
  * Lee et al. (2019) Dayeol Lee, David Kohlbrenner, Shweta Shinde, Dawn Song, and Krste Asanovic. 2019.  Keystone: An Open Framework for Architecting TEEs.  arXiv:1907.10119
  * Liu et al. (2016) Shengyun Liu, Paolo Viotti, Christian Cachin, Vivien Quéma, and Marko Vukolic. 2016\.  XFT: Practical Fault Tolerance beyond Crashes. In _OSDI_.
  * Malkhi et al. (2019) Dahlia Malkhi, Kartik Nayak, and Ling Ren. 2019.  Flexible byzantine fault tolerance. In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_. 1041–1053.
  * Matetic et al. (2017) Sinisa Matetic, Mansoor Ahmed, Kari Kostiainen, Aritra Dhar, David Sommer, Arthur Gervais, Ari Juels, and Srdjan Capkun. 2017\.  ROTE: Rollback Protection for Trusted Execution.  _IACR Cryptology ePrint Archive_ (2017).
  * McCune et al. (2007) Jonathan M McCune, Bryan Parno, Adrian Perrig, Michael K Reiter, and Arvind Seshadri. 2007.  Minimal TCB code execution. In _2007 IEEE Symposium on Security and Privacy (SP’07)_. IEEE, 267–272.
  * McKeen et al. (2013) Frank McKeen, Ilya Alexandrovich, Alex Berenzon, Carlos V Rozas, Hisham Shafi, Vedvyas Shanbhogue, and Uday R Savagaonkar. 2013.  Innovative instructions and software model for isolated execution.  _HASP@ ISCA_ 10 (2013).
  * Ongaro and Ousterhout (2014) Diego Ongaro and John K Ousterhout. 2014.  In search of an understandable consensus algorithm.. In _USENIX Annual Technical Conference_. 305–319.
  * Russinovich et al. (2019) Mark Russinovich, Edward Ashton, Christine Avanessians, Miguel Castro, Amaury Chamayou, Sylvan Clebsch, Manuel Costa, Cédric Fournet, Matthew Kerner, Sid Krishna, et al. 2019\.  CCF: A framework for building confidential verifiable replicated services.  _Technical Report MSR-TR-201916_ (2019).
  * Schneider (1990) Fred B. Schneider. 1990\.  Implementing Fault-Tolerant Services using the State Machine Approach: A Tutorial.  _ACM Comput. Surv._ 22, 4 (Dec. 1990), 299–319.
  * Schnorr (1991) Claus-Peter Schnorr. 1991\.  Efficient signature generation by smart cards.  _Journal of cryptology_ 4, 3 (1991), 161–174.
  * Shamis et al. (2021) Alex Shamis, Peter Pietzuch, Miguel Castro, Edward Ashton, Amaury Chamayou, Sylvan Clebsch, Antoine Delignat-Lavaud, Cedric Fournet, Matthew Kerner, Julien Maffre, Manuel Costa, and Mark Russinovich. 2021\.  PAC: Practical Accountability for CCF.  arXiv:2105.13116 [cs.DC]
  * Subramanyan et al. (2017) Pramod Subramanyan, Rohit Sinha, Ilia Lebedev, Srinivas Devadas, and Sanjit A Seshia. 2017.  A formal foundation for secure remote execution of enclaves. In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2435–2450.
  * Syta et al. (2016) Ewa Syta, Iulia Tamas, Dylan Visher, David Isaac Wolinsky, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ismail Khoffi, and Bryan Ford. 2016.  Keeping authorities" honest or bust" with decentralized witness cosigning. In _2016 IEEE Symposium on Security and Privacy (SP)_. Ieee, 526–545.
  * Szerwinski and Güneysu (2008) Robert Szerwinski and Tim Güneysu. 2008.  Exploiting the power of GPUs for asymmetric cryptography. In _International Workshop on Cryptographic hardware and embedded systems_. Springer, 79–99.
  * Tramer et al. (2017) Florian Tramer, Fan Zhang, Huang Lin, Jean-Pierre Hubaux, Ari Juels, and Elaine Shi. 2017\.  Sealed-glass proofs: Using transparent enclaves to prove and sell knowledge. In _2017 IEEE European Symposium on Security and Privacy (EuroS &P)_. IEEE, 19–34.
  * Van Bulck et al. (2018) Jo Van Bulck, Marina Minkin, Ofir Weisse, Daniel Genkin, Baris Kasikci, Frank Piessens, Mark Silberstein, Thomas F Wenisch, Yuval Yarom, and Raoul Strackx. 2018\.  Foreshadow: Extracting the keys to the intel $\\{$SGX$\\}$ kingdom with transient out-of-order execution. In _27th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 18)_. 991–1008.
  * Venkataraman et al. (2006) Vidhyashankar Venkataraman, Kaouru Yoshida, and Paul Francis. 2006\.  Chunkyspread: Heterogeneous unstructured tree-based peer-to-peer multicast. In _Proceedings of the 2006 IEEE International Conference on Network Protocols_. IEEE, 2–11.
  * Yin et al. (2019) Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019\.  HotStuff: BFT Consensus with Linearity and Responsiveness. In _PODC_. ACM, 347–356.