ezBFT: Decentralizing Byzantine Fault-Tolerant State Machine Replication

We present ezBFT, a novel leaderless, distributed consensus protocol capable of tolerating byzantine faults. ezBFT's main goal is to minimize the client-side latency in WAN deployments. It achieves this by (i) having no designated primary replica, and instead, enabling every replica to order the requests that it receives from clients; (ii) using only three communication steps to order requests in the common case; and (iii) involving clients actively in the consensus process. In addition, ezBFT minimizes the potentially negative effect of a byzantine replica on the overall system performance. We developed ezBFT's formal specification in TLA+, show that it provides the classic properties of BFT protocols including consistency, stability, and liveness, and developed an implementation. Our experimental evaluation reveals that ezBFT improves client-side latency by as much as 40% over state-of-the-art byzantine fault-tolerant protocols including PBFT, FaB, and Zyzzyva.

I. INTRODUCTION
State Machine Replication (SMR) is a common technique employed in today's distributed applications to tolerate server failures and maintain high availability [1], [2]. The replication servers, or replicas, employ consensus protocols (e.g., Raft [3], Paxos [4], Zab [5]) to replicate the application state and ensure that the same sequence of client commands is executed on the shared state in the same order (i.e., a total order), ensuring consistency of the replicated state.
Consensus solutions can be broadly classified as Crash Fault-Tolerant (CFT) and Byzantine Fault-Tolerant (BFT), with the former being a subset of the latter. While CFT protocols have found their niche in datacenter applications [6], [7], [8] of a single enterprise-class organization, BFT protocols are increasingly used in applications involving multiple independent organizations. For example, for distributed ledger or blockchain-based applications in the permissioned setting, consensus need to be reached among a set of known participants (e.g., independent organizations), despite no complete trust among them. In such cases, BFT protocols can ensure replica state consistency while withstanding malicious actors and other non-crash related faults. An example of a permissioned blockchain system that uses a BFT protocol is the Hyperledger Fabric [9], [10].
The use of permissioned blockchain applications is growing in many domains (e.g., supply chain [19], real-estate [20], finance [21]) and many such systems are increasingly deployed in geographically distributed settings to cater to different application needs. Geographical-scale (or "geo-scale") deployments of BFT systems have an additional challenge: achieving low client-side latencies and high server-side throughput under the high communication latencies of a WAN. Since replicas need to communicate with each other and the clients to reach consensus, the number of communication steps incurred directly impacts the latency, as each step involves sending messages to potentially distant nodes. Thus, protocols such as Zyzzyva [14], Q/U [13], and HQ [15] use various techniques to reduce communication steps. These techniques, however, do not reduce client-side latencies in a geo-scale setting, where, the latency per communication step is as important as the number of communication steps. In other words, a protocol can achieve significant cost savings if the latency incurred during a communication step can be reduced.
The downside of such lack of locality is most manifest for primary-based BFT protocols such as PBFT and Zyzzyva: a replica is bestowed the primary status and is responsible for proposing the total-order for all client requests. While the clients that are geographically nearest to the primary may observe optimal client-side latency, the same is not true for distant clients. A distant client will incur higher latency for the first communication step (of sending the request to the primary). Additionally, the primary-based design limits throughput as the primary carries significantly higher load.
To validate these hypotheses, we deployed Zyzzyva [14] in a 4-replica geo-scale setting with nodes located in the US (Virginia), Japan, India, and Australia, using Amazon's EC2 infrastructure [22]. We deployed clients alongside each replica to inject requests, and measured the client-side latencies by changing the primary's location. Table I shows the results. We observe that the lowest latencies are when the primary is colocated within the same region.
Past work suggests that it is important to perform regular view changes (i.e., elect a new primary) to reduce the negative impacts of a byzantine replica [23]. This makes it difficult to  [14] latencies (in ms) in a geo-scale deployment with primary at different locations. Columns indicate the primary's location. Rows indicate average client-side latency for commands issued from that region. For example, the entry at the 4th row and the 3rd column shows the clientside latency for commands issued from India to the primary in Japan. Lowest latency per primary location is highlighted.

II. SYSTEM MODEL
We consider a set of nodes (replicas and clients), in an asynchronous system, that communicate via message passing. The replica nodes have identifiers in the set {R 0 , ..., R N −1 }. We assume the byzantine fault model in which nodes can behave arbitrarily. We also assume a strong adversary model in which faulty nodes can coordinate to take down the entire system. Every node, however, is capable of producing cryptographic signatures [29] that faulty nodes cannot break. A message m signed using R i 's private key is denoted as m Ri . The network is fully connected and quasi-reliable: if nodes R 1 and R 2 are correct, then p 2 receives a message from R 1 exactly as many times R 1 sends it.
To preserve safety and liveness, EZBFT requires at least N = 3f + 1 replica nodes in order to tolerate f Byzantine faults. EZBFT uses two kinds of quorums: a fast quorum with 3f +1 replicas, and a slow quorum with 2f +1 replicas. Safety is guaranteed as long as only up to f replicas fail. Liveness is guaranteed during periods of synchronous communication.

III. PROTOCOL OVERVIEW
We now overview EZBFT and highlight the novelties that enable it to tolerate byzantine failures and provide optimal wide-area latency.
EZBFT can deliver decisions in three communication steps from the client's point-of-view, if there is no contention, no byzantine failures, and synchronous communication between replicas. The three communication steps include: (i) a client sending a request to any one of the replicas (closest preferably); (ii) a replica forwarding the request to other replicas with a proposed order; and (iii) other replicas (speculatively) executing the request as per the proposed order and replying back to the client. These three steps constitute EZBFT's core novelty. To realize these steps, EZBFT incorporates a set of techniques that we summarize below and explain in detail in the next section.
First, the EZBFT replicas perform speculative execution of the commands after receiving the proposal messages from their respective command-leaders (see below). With only one replica-to-replica communication, there is no way to guarantee the final commit order for client commands. Thus, the replica receiving the proposal assumes that other replicas received the same proposal (i.e., the command-leader is not byzantine) and that they have agreed to the proposal. With this assumption, replicas speculatively execute the commands on their local state and return a reply back to the client.
Second, in EZBFT, the client is actively involved in the consensus process. It is responsible for collecting messages from the replicas and ensuring that they have committed to a single order before delivering the reply. The client also enforces a final order, if the replicas are found to deviate.
Third, and most importantly, there are no designated primary replicas. Every replica can receive client requests and propose an order for them. To clearly distinguish the replica proposing an order for a command from other replicas, we use the term command-leader. A command-leader is a replica that proposes an order for the commands received from its clients. For clarity, all replica can be command-leaders. To ensure that client commands are consistently executed across all correct replicas, EZBFT exploits the following concepts.
EZBFT uses the concept of command interference to empower replicas to make independent commit decisions. If replicas concurrently propose commands that do not interfere, they can be committed and executed independently, in parallel, in any order, and without the knowledge of other non-interfering commands. However, when concurrent commands do interfere, replicas must settle on a common sequential execution.
Command Interference: A command encapsulates an operation that must be executed on the shared state. We say that two commands L 0 and L 1 are interfering if the execution of these commands in different orders on a given state will result in two final states. That is, if there exists a sequence of commands Σ such that the serial execution of Σ, L 0 , L 1 is not equivalent to Σ, L 1 , L 0 , then L 0 and L 1 are interfering.
Instance Space: An instance space can be visualized as a sequence of numbered slots to which client-commands can be associated with. The sequence defines the execution order of requests, and the role of a consensus protocol is to reach agreement among a set of replicas on a common order. However, to accommodate our requirement that every replica can be a command-leader for their received requests, each replica has its own instance space. Thus, EZBFT's role is not only to reach consensus on the mapping of client-commands to the slots within an instance space, but also among the slots in different instance spaces.
Instance Number: An instance number, denoted I, is a tuple of the instance space (or replica) identifier and a slot identifier.
Instance Owners: An owner number, O, is a monotonically increasing number that is used to identify the owner of an instance space. Thus, there are as many owner numbers as there are instance spaces (or replicas). This number becomes useful when a replica is faulty, and its commands must be recovered by other replicas. When replicas fail, another correct replica steps up to take ownership of the faulty replica's instance space. The owner of a replica R 0 's instance space can be identified from its owner number using the formula O R0 mod N , where N is the number of replicas. Initially, the owner number of each instance space is set to the owner replica's identifier (e.g., O R0 = 0, O R1 = 1, and so on).
Dependencies: Due to the use of per-replica instance spaces, the protocol must agree on the relationship between the slots of different instances spaces. EZBFT does this via dependency collection, which uses the command interference relation. The dependency set D for command L is every other command L that interferes with L.
Sequence Number (S): is a globally shared number that is used to break cycles in dependencies. It starts from one and is always set to be larger than all the sequence numbers of the interfering commands. Due to concurrency, it is possible that interfering commands originating from different commandleaders are assigned the same sequence number. In such cases, the replica identifiers are used to break ties.
Protocol Properties: EZBFT has the following properties: 1) Nontriviality. Any request committed and executed by a replica must have been proposed by a client. 2) Stability. For any replica, the set of committed requests at any time is a subset of the committed requests at any later time. If at time t 1 , a replica R i has a request L committed at some instance I L , then R i will have L committed in I L at any later time t 2 > t 1 . 3) Consistency. Two replicas can never have different requests committed for the same instance. 4) Liveness. Requests will eventually be committed by every non-faulty replica, as long as at least 2f +1 replicas are correct.

IV. PROTOCOL DESIGN
In this section, we present EZBFT in detail, along with an informal proof of its properties. We have also developed a TLA+ specification of EZBFT and model-checked the protocol correctness; this can be found in the technical report [28].
A client command may either take a fast path or a slow path. The fast path consists of three communication steps, and is taken under no contention, no byzantine failures, and during synchronous communication periods. The slow path is taken otherwise to guarantee the final commit order for commands, and incurs two additional steps.

A. The Fast Path Protocol
The fast path consists of three communication steps in the critical path and one communication step in the non-critical path of the protocol. Only the communication steps in the critical path contribute to the client-side latency. The fast path works as follows.
1. Client sends a request to a replica.
The client c requests a command L to be executed on the replicated state by sending a message REQUEST, L, t, c σc to a EZBFT replica. The closest replica may be chosen to achieve the optimal latency. The client includes a timestamp t to ensure exactly-once execution.
2. Replica receives a request, assigns an instance number, collects dependencies and assigns a sequence number, and forwards the request to other replicas.
When a replica R i receives the message m = REQUEST, L, t, c σc , it becomes the command-leader for L. It assigns c to the lowest available instance number I L in its instance space and collects a dependency set D using the command interference relation that was previously described. A sequence number S assigned for c is calculated as the maximum of sequence numbers of all commands in the dependency set. This information is relayed to all other replicas in a message SPECORDER, O Ri , I L , D, S, h, d σ Ri , m , where d = H(m), h is the digest of R i 's instance space, and O Ri is its owner number.
Nitpick. Before taking the above actions, R i ensures that the timestamp t > t c , where t c is the highest time-stamped request seen by R i thus far. If not, the message is dropped.
3. Other replicas receive the SPECORDER message, speculatively executes the command according to its local snapshot of dependencies and sequence number, and replies back to the client with the result and an updated set of dependencies and sequence number, as necessary.
When replica R j receives a message SPECORDER, O Ri , I L , D, S, h, d σ Ri , m from replica R i , it ensures that m is a valid REQUEST message and that I L = maxI Ri + 1, where maxI Ri is the largest occupied slot number in R i 's instance space. Upon successful validation, R j updates the dependencies and sequence number according to its log, speculatively executes the command, and replies back to the client.  The receipt of 3f + 1 matching responses from the replicas constitutes a fast path decision for command L. This happens in the absence of faults, network partitions, and contention. The client returns reply rep to the application and then asynchronously sends a message COMMITFAST, c, I L , CC , where CC is the commit certificate consisting of 3f + 1 matching SPECREPLY responses, and returns. 5. The replicas receive either a COMMITFAST or a COM-MIT message. Upon receipt of a COMMITFAST, c, I L , CC message, the replica R i marks the state of L as committed in its local log and enqueues the command for final execution. The replica does not reply back to the client.
Example. Figure 1 shows an example case. The client sends a signed REQUEST message to replica R 0 to execute a command L 0 on the replicated service. Replica R 0 assigns the lowest available instance number in its instance space to L 0 . Assuming that no instance number was used previously, the instance number assigned to L 0 is I L0 = r 0 , 0 . Then, R 0 collects dependencies and assigns a sequence number to L 0 . As the first command, there exists no dependencies, so the dependency set D = {}. Thus, the sequence number is S = 1.
A signed SPECORDER message is sent to other replicas in the system with the command and compiled metadata. Other replicas -R 1 through R 3 -receive this message, add the command to their log, and start amassing dependencies from their log that are not present in D. No other replica received any other command, thus they produce an empty dependency set as well, and the sequence number remains the same. Since there are no dependencies, all replicas immediately execute the command, speculatively, on their copy of the application state. The result of execution, unchanged dependency set, sequence number, and the digest of log are sent in a SPECREPLY message to the client. The client checks for identical replies and returns the result to the application. The replies are identical in this case because no other command conflicts with L 0 in any of the replicas and the replicas are benign.

B. Execution Protocol
EZBFT uses speculative execution as a means to reply to the client quickly. However, the protocol must ensure that every correct replica has identical copies of the state. This means that, when necessary (as described in Section IV-C), the speculative state must be rolled back and the command must be re-executed correctly; this is called final execution.
Moreover, differently from existing BFT solutions, EZBFT collects command dependencies that form a directed graph with potential cycles. The graph must be processed to remove cycles and obtain the execution order for a command.
Each replica takes the following steps: 1) Waits for the command to be enqueued for execution. For final execution, wait for the dependencies to be committed and enqueued for final execution as well. 2) A dependency graph is constructed by including R and all its dependencies in D as nodes and adding edges between nodes indicating the dependencies. The procedure is repeated recursively for each dependency. 3) Strongly connected components are identified and sorted topologically. 4) Starting from the inverse topological order, every strongly connected component is identified, and all the requests within the component are sorted in the sequence number order. The requests are then executed in the sequence number order, breaking ties using replica identifiers. During speculative execution, the execution is marked speculative on the shared state. During final execution, the speculative results are invalidated, command re-executed, and marked final. Note that speculative execution can happen in either the speculative state or in the final version of the state, which ever is the latest. However, for final execution, commands are executed only on the previous final version.

C. The Slow Path Protocol
The slow path is triggered whenever a client receives either unequal and/or insufficient SPECREPLY messages that is necessary to guarantee a fast path. The client will receive unequal replies if the replicas have different perspectives of the command dependencies, possibly due to contention or due to the presence of byzantine replicas. The case of insufficient replies happen due to network partitions or byzantine replicas.
The steps to commit a command in the slow path are as follows.

4.2
The client receives at least 2f + 1 possibly unequal responses.
The client c sets a timer as soon as a REQUEST is issued. When the timer expires, if c has received at least 2f + 1 SPECREPLY, O Ri , I L , D, S, d, c, t σ Ri , R j , rep, SO messages, it produces the final dependency set and sequence number for L. The dependency sets from a known set of 2f +1 replicas are combined to form D . A new sequence number S is generated if the individual dependency sets were not equal. c sends a COMMIT, c, I L , D , S , CC σc message to all the replicas, where CC is the commit certificate containing 2f +1 SPECREPLY messages that are used to produce the final dependency set.
Nitpick. Each command-leader specifies a known set of 2f + 1 replicas that will form the slow path quorum, which is used by the client to combine dependencies when more than 2f + 1 reply messages are received. This information is relayed to the clients by the respective command-leaders and is cached at the clients.

5.2
The replicas receive a COMMIT message. The client returns rep to the application upon receipt of 2f + 1 COMMITREPLY, L, rep messages. At this point, execution of command L is guaranteed to be safe in the system, while tolerating upto f byzantine failures. Moreover, even after recovering from failures, all correct replicas will always execute L at this same point in their history to produce the same result.
Example: Figure 2 shows an example of a slow path. Two clients c 0 and c 1 send signed REQUEST messages to replicas R 0 and R 3 , respectively, to execute commands L 1 and L 2 , respectively, on the replicated service. Assume that L 1 and L 2 conflict. Replica R 0 assigns the lowest available instance number of R 0 , 0 to L 1 . Thus, R 0 collects a dependency set D L1 = {} and assigns a sequence number S L1 = 1 to L 1 . Meanwhile, R 3 assigns the instance number R 3 , 0 to L 1 ; the dependency set is D L2 = {}, and sequence number is S L2 = 1. Replicas R 0 and R 3 send SPECORDER messages with their respective commands and their metadata to other replicas. Let's assume that R 0 and R 1 receive L 1 before L 2 , while R 2 and R 3 receive L 2 before L 1 . The dependency set and sequence number will remain unchanged for L 1 at R 0 and R 1 , because the dependency set in the SPECORDER message received is the latest. However, the dependency set and sequence number for L 2 will update to D L2 = {L 1 } and S L2 = 2, respectively. Similarly, the dependency set and sequence number will remain unchanged for L 2 at R 0 and R 1 , but for L 1 , D L1 = {L 2 } and S L1 = 2, respectively. The SPECREPLY messages for both L 1 and L 2 with the new metadata are sent to the respective clients c 0 and c 1 by the replicas.
Let's assume that the slow quorum replicas are R 0 , R 1 , and R 2 for R 0 , and R 1 , R 2 , and R 3 for R 3 . Since client c 0 observes unequal responses, it combines the dependencies for L 1 from the slow quorum and selects the highest sequence number to produce the final dependency set D L1 = {L 2 } and sequence number S L1 = 2. This metadata is sent to the replicas in a COMMIT message. Similarly, c 1 produces the final dependency set D L2 = {L 1 } and sequence number S L2 = 2 for L 2 , and sends a COMMIT message to the replicas. The replicas update the dependency set and sequence number of the commands upon receipt of the respective COMMIT messages, and the commands are queued for execution. The replicas wait for the receipt of the COMMIT messages of all commands in the dependency set before processing them.
After the construction of the graph and the inverse topological sorting, there will exist commands L 1 and L 2 with a cyclic dependency between them. Since the sequence numbers for both the commands are the same and thus cannot break the dependency, the replica IDs are used in this case. Thus, L 1 gets precedence over L 2 . L 1 is executed first, followed by L 2 . The result of the executions are sent back to the clients. The clients collect 2f + 1 reply messages and return the result to the application.
Example with a faulty replica: Figure 3 shows an example of the slow path that is very similar to that of Figure 2, but with a faulty replica R 2 that misbehaves. Notice that the REQUEST and SPECORDER steps (first four rows) remain the same. Upon receipt of the SPECORDER message from R 0 and R 3 for L 1 and L 2 , respectively, the replicas collect the dependency set and update the sequence number, and send back SPECREPLY messages to the client. For L 1 , R 0 and R 1 send D L1 = {} and S L1 = 1; however, R 2 misbehaves and sends D L1 = {} and S L1 = 1, even though it received L 2 before L 1 . For L 2 , R 2 and R 3 send D L2 = {} and S L2 = 1; R 1 sends D L2 = {L 1 } and S L2 = 2. c 0 receives a quorum of 2f + 1 SPECREPLY messages, and sends a COMMIT message with an empty dependency set and a sequence number 1. On the other hand, R 1 that participated in command L 1 's quorum sends back a correct dependency set and sequence number. Therefore, the final commit message for L 2 will have L 1 in its dependency set. Thus, even though replicas immediately execute L 1 since L 1 's final dependency set is empty, they cannot do so for L 2 . Correct replicas must wait until L 1 is committed before constructing the graph, at which point L 1 will be executed first because of the smallest sequence number, followed by L 2 .

D. Triggering Owner Changes
EZBFT employs a mechanism at the clients to monitor the replicas and take actions to restore the service when progress is not being made. Although the slow path helps overcome the effects of a participant byzantine replica, it does ensure progress of a command when its command-leader, the replica that proposed that command, is byzantine. From the clientside, two events can be observed to identify misbehaving command-leaders.

4.3
The client times-out waiting for reply from the replicas.
After the client sends a request with command L, it starts another timer, in addition to the one for slow-path, waiting for responses. If the client receives zero or fewer than 2f + 1 responses within the timeout, it sends the REQUEST, L, t, c, R i σc message to all the replicas, where R i is the original recipient of the message.
When replica R j receives the message, it takes one of the following two actions. If the request matches or has a lower timestamp t than the currently cached timestamp for c, then the cached response is returned to c. Otherwise, the replica sends a RESENDREQ, m, R j message where m = REQUEST, L, t, c, R i σc to R i and starts a timer. If the timer expires before the receipt of a SPECORDER message, R j initiates an ownership change.

4.4
The client receives responses indicating inconsistent ordering by the command-leader and sends a proof of misbehavior to the replicas to initiate an ownership change for the command-leader's instance space.
Even though a client may receive prompt replies from the replicas, it must check for inconsistencies leading to a proof of misbehavior against the command-leader. The SPECREPLY, O Ri , I L , D , S , d, c, t σ Ri , R k , rep, SO messages from different replicas are said to match if they have identical O Ri , I, D, S, c, t, and rep fields, but the contention may affect the equality of the dependency set and sequence number fields. Thus, the command-leader is said to misbehave if it sends SPECORDER messages with different instance numbers to different replicas (i.e., if the I field varies between the replicas). The client c can identify by inspecting SPECORDER SO message embedded in the SPECREPLY message received from the replicas. In this case, the client collects a pair of such messages to construct a POM, O Ri , P OM message, where P OM is a pair of SPECREPLY messages, proving misbehavior by the command-leader R i of L.

E. The Owner Change Protocol
An ownership change is triggered for an instance space if its original owner is faulty. However, to initiate an ownership change, there must exist either a proof of misbehavior against the owner, or enough replicas must have timed out waiting for a reply from the owner.
A replica R j commits to an ownership change by sending a STARTOWNERCHANGE, R i , O Ri message to other replicas, where R i is the suspected replica and O Ri is its owner number. When another replica R k receives at least f +1 STARTOWN-ERCHANGE messages for R i , it commits to an ownership change. From this point forward, R k will not participate in R i 's instance space. The new owner number is calculated as O Ri = O Ri + 1, and the new command-leader is identified using O Ri mod N (henceforth R l ). Replicas that have committed to an owner-change send OWNERCHANGE messages to the new leader. Once the new command-leader R l receives f + 1 OWNERCHANGE messages, it becomes the new owner of R i 's instance space and finalizes its history.
Each replica sends an OWNERCHANGE message containing its view of R i 's instance space, i.e., the instances (speculative) executed or committed since the last checkpoint, and the commit-certificate with the highest owner number that it had previously responded to with a commit message, if any. The new owner collects a set P of OWNERCHANGE messages and selects only the one that satisfies one of the following conditions. For clarity, we label the sequence of instances in each OWNERCHANGE message as P i , P j , and so on.
There exists a sequence P i that is the longest and satisfies one of the following conditions. Condition 1 P i has COMMIT messages with the highest owner number to prove its entries. Condition 2 P i has at least f +1 SPECORDER messages with the highest owner number to prove its entries. If there exists a sequence P j that extends a P i satisfying any of the above conditions, then P j is a valid extension of P i if one of the following conditions hold: 1) P i satisfies Condition 1, and for every command L in P j not in P i , L has at least f + 1 SPECORDER messages with the same highest order number as P i . 2) P i satisfies Condition 2, and for every command L in P j not in P i , L has a signed COMMIT message with the same highest order number as P i . The new owner sends a NEWOWNER message to all the replicas. The message includes the new owner number O R0 , the set P of OWNERCHANGE messages that the owner collected as a proof, and the set of safe instances G produced using Condition 1 and Condition 2. A replica accepts a NEWOWNER message if it is valid, and applies the instances from G in R i 's instance space. If necessary, it rolls-back the speculatively executed requests and re-executes them again.
At this point, R i 's instance space is frozen. No new commands are ordered in the instance space, because each replica has its own instance space that it can use to propose its command. The owner change is used to ensure the safety of commands proposed by the faulty replicas.

F. Correctness
We formally specified EZBFT in TLA+ and model-checked using the TLC model checker. The TLA+ specification is provided in a technical report [28]. In this section, we provide an intuition of how EZBFT achieves its properties.
Nontriviality. Since clients must sign the requests they send, a malicious primary replica cannot modify them without being suspected. Thus, replicas only execute requests proposed by clients.
Consistency. To prove consistency, we need to show that if a replica R j commits L at instance I, then for any replica R k that commits L at I, L and L must be the same command.
To prove this, consider the following. If R j commits L at I = R i , − , then an order change should have been executed for replica R i 's instance space. If R j is correct, then it would have determined that L was executed at I using the commit certificate in the form of SPECORDER or COMMIT messages embedded within the CHANGEOWNER messages. Thus, L and L must be the same. If R j is malicious, then the correct replicas will detect it using the invalid progress-certificate received. This will cause an ownership change.
In addition, we need to also show that conflicting requests L and L are committed and executed in the same order across all correct replicas. Assume that L commits with D and S, while L commits with D and S . If L and L conflict, then at least one correct replica must have responded to each other in the dependency set among a quorum of 2f + 1 replies received by the client. Thus, L will be in L 's dependency set and/or viceversa. The execution algorithm is deterministic, and it uses the sequence number to break ties. Thus, conflicting requests will be executed in the same order across all correct replicas.
Stability. Since only f replicas can be byzantine, there must exist at least 2f + 1 replicas with the correct history. During an ownership change, 2f +1 replicas should send their history to the new owner which then validates it. Thus, if a request is committed at some instance, it will be extracted from history after any subsequent owner changes and committed at same instance at all correct replicas.
Liveness. Liveness is guaranteed as long as fewer than f replicas crash. Each primary replica attempts to take the fast path with a quorum of 3f + 1 replicas. When faults occur and a quorum of 3f + 1 replicas is not possible, the client pursues the slow path with 2f + 1 replicas and terminates in two additional communication steps.

V. EVALUATION
We implemented EZBFT, and its state-of-the-art competitors PBFT, FaB, and Zyzzyva in Go, version 1.10. In order to evaluate all systems in a common framework, we used gRPC [30] for communication and protobuf [31] for message serialization. We used the HMAC [32] and ECDSA [29] algorithms in Go's crypto package to authenticate the messages exchanged by the clients and the replicas. The systems were deployed in different Amazon Web Service (AWS) regions using the EC2 infrastructure [22]. The VM instance used was m4.2xlarge with 8 vCPUs and 32GB of memory, running Ubuntu 16.04. We implemented a replicated key-value store to evaluate the protocols. Note that, for Zyzzyva and EZBFT, the client process implements the logic for the client portion of the respective protocols.
Among the protocols evaluated, only EZBFT is affected by contention. Contention, in the context of a replicated key-value store, is defined as the percentage of requests that concurrently access the same key. Prior work [24] has shown that, in practice, contention is usually between 0% and 2%. Thus, a 2% contention means that roughly 2% of the requests issued by clients target the same key, and the remaining requests target clients' own (non-overlapping) set of keys. However, we evaluate EZBFT at higher contention levels for completeness.

A. Client-side Latency
To understand EZBFT's effectiveness in achieving optimal latency at each geographical region, we devised two experiments to measure the average latency experienced by clients located at each region for each of the protocols. Experiment 1: We deployed the protocols with four replica nodes in the AWS regions: US-East-1 (Virginia), India, Australia, and Japan. At each node, we also co-located a client that sends requests to the replicas. For single primary-based protocols (PBFT, FaB, Zyzzyva), the primary was set to US-East replica; thus, clients in other replicas send their requests to the primary. For EZBFT, the client sends its requests to the nearest replica (which is in the same region). The clients send requests in closed-loop, meaning that a client will wait for a reply to its previous request before sending another one.  Figure 4 shows the average latency (in milliseconds) observed by the clients located in their respective regions (shown on x-axis) for each of the four protocols. For EZBFT, the latency was measured at different contention levels: 0%, 2%, 50%, and 100%; the suffix in the legend indicates the contention. Among primary-based protocols, PBFT suffers the highest latency, because it takes five communication steps to deliver a request. FaB performs better than PBFT with four communication steps, but Zyzzyva performs the best among primary-based protocols using only three communication steps. Overall, EZBFT performs as good as or better than Zyzzyva, for up to 50% contention. In the US-East-1 region, both Zyzzyva and EZBFT have about the same latency because they have the same number of communication steps and their primaries are located in the same region. However, for the remaining regions, Zyzzva clients must forward their requests to US-East-1, while EZBFT clients simply send their requests to their local replica, which orders them. At 100% contention, five communication steps required for total-order increases EZBFT's latency close to that of PBFT's. Experiment 2: To better understand Zyzzyva's best and worst-case performances and how they fare against EZBFT, we identified another set of AWS regions: US-East-2 (Ohio), Ireland, Frankfurt, and India. This experiment was run similar to that of Figure 4. The primary was placed in Ireland. The results are shown in Figure 5. Figure 5a shows the average latencies as observed by the clients in each deployed region for each of the four protocols. The choice of Ireland as the primary region represents the best case for Zyzzyva. Hence, EZBFT performs very similar to Zyzzyva.
In Experiment 1, the regions mostly had non-overlapping paths between them, and thus the first communication step of sending the request to the leader can be seen clearly (notice Mumbai in Figure 4. On the other hand, in Experiment 2, connections between the regions have overlapping paths. For example, sending a request from Ohio to Mumbai for EZBFT will take about the same time as sending a request from Ohio to Mumbai via the primary at Ireland for Zyzzyva. Figure 5b shows the effect of moving the primary to different regions. We disregard PBFT and FaB in this case, as their performance do not improve. For Zyzzyva, moving the primary to US-East-2 or India substantially increases its overall latency. In such cases, EZBFT's latency is up to 45% lower than Zyzzyva's. This data-point is particularly important as it reveals how the primary's placement affects the latency. To curb the negative effects of byzantine primary replicas, in [33], the authors propose to frequently move the primary (this strategy is adopted by other protocols including Zyzzyva). From Figure 5b, we can extrapolate that such frequent movements can negatively impact latencies over time. Given these challenges, we argue that EZBFT's leaderless nature is a better fit for geo-scale deployments.

B. Client Scalability
Another important aspect of EZBFT is its ability to maintain low client-side latency even as the number of connected clients  increases. For this experiment, we deployed the protocols in Virginia, Japan, Mumbai, and Australia, and measured clientside latency per region by varying the number of connected clients. Figure 6 shows the results. Notice that as Zyzzyva approaches 100 connected clients per region, it suffers from an exponential increase in latency. However, EZBFT, even at 50% contention, is able to scale better with the number of clients. Particularly, in Mumbai, EZBFT maintains a stable latency even at 100 clients per region, while Zyzzyva's latency shoots up.

C. Server-side Throughput
We also measured the peak throughput of the protocols. For this experiment, we deployed the protocols in five AWS regions: US-East-1 (Virginia), India, Australia, and Japan. We co-located ten clients with the primary replica in US-East-1. Unlike the experiments so far, here the clients send requests in an open-loop, meaning that they continuously and asynchronously send requests before receiving replies. The requests consists of an 8-byte key and a 16-byte value. Figure 7 shows the results. For EZBFT, we carried out two experiments: i) clients are placed only at US-East-1 (labelled EZBFT in the figure); and ii) clients are placed at every region (labelled "EZBFT (All Regions)" in the figure). Due to the leaderless characteristic, each of the replicas can feed requests into the system, increasing the overall throughput. The contention was set to 0%, and no batching was done. Observe that when clients are placed only at US-East-1, EZBFT performs at par or slightly better than others. On the other hand, when clients are placed in all the other regions, which does not yield any benefit for other protocols, EZBFT's throughput increases by as much as four times, as all EZBFT replicas are able to process and deliver requests concurrently.
VI. RELATED WORK BFT consensus was first introduced in [34]. However, PBFT [11], [33] was the first protocol to provide a practical implementation of BFT consensus in the context of state machine replication. PBFT solved consensus in three communication steps (excluding two steps for client communication) using 3f +1 nodes and requiring responses from at least 2f +1 nodes. f is the maximum number of byzantine faulty nodes that the system can tolerate and make progress.
FaB [13] reduced the number of communication steps required to reach agreement in the common case to two steps, called two-step consensus (excluding two steps for client communication). However, node and quorum requirements are substantially larger with 5f +1 and 4f +1 nodes, respectively, to tolerate f faults and still achieve two-step consensus. FaB falls back to a slower path when 4f + 1 responses cannot be acquired, and requires an extra communication step and at least 3f + 1 nodes to reach agreement.
FaB was the first BFT protocol to not require any digital signatures in the common case. Parameterized-FaB [13] requires 3f + 2t + 1 nodes, where f is the number of tolerated faults and preserve safety and t is the number of tolerated faults and solve two-step consensus. This minimized the node requirements in the common case to 3f + 1 (by setting t = 0), but the quorum requirement is still more than that of PBFT.
The Q/U [12] protocol was the first to achieve consensus in two communications steps when there are no faults and update requests do not concurrently access the same object. Q/U defines a simplified version of conflicts. Requests are classified as either reads or writes. Reads do not conflict with reads, while write conflicts with reads and writes. This is more restrictive than the commutative property used by EZBFT. In EZBFT, for instance, mutative operations (such as incrementing a variable) are commutative.
HQ [15] is similar to PBFT with a special optimization to execute read-only requests in two communication steps and update requests in four communication steps under no conflicts. HQ's definition of conflict is the same as Q/U's.
Zyzzyva [14], [35] uses 3f + 1 nodes to solve consensus in three steps (including client communication), requiring a quorum of 3f +1 responses. The protocol tolerates f faults, so it takes an additional two steps when nodes are faulty. Zyzzyva uses the minimum number of nodes, communication steps, and one-to-one messages to achieve fast consensus. It is cheaper than the aforementioned protocols, but also more complex. Zyzzyva's performance boost is due to speculative execution, active participation of the clients in the agreement process, and tolerating temporary inconsistencies among replicas.
EZBFT has the same node and quorum requirements as well as the number of communication steps as Zyzzyva. However, by minimizing the latency of the first communication step and alleviating the specialized role of the primary, EZBFT reduces the request processing latency.
Aliph [18] builds a BFT protocol by composing three different sub-protocols, each handling a specific system factor such as contention, slow links, and byzantine faults. Under zero contention, the sub-protocol Quorum can deliver agreement in two steps with 3f + 1 nodes by allowing clients to send the requests directly to the nodes. However, as contention or link latency increases, or as faults occur, Aliph switches to the subprotocol Chain whose additional steps is equal to the number of nodes in the system, or to the sub-protocol Backup which takes at least three steps. Although the idea of composing simpler protocols is appealing in terms of reduced design and implementation complexities, the performance penalty is simply too high, especially in geo-scale settings.
In contrast, EZBFT exploits the trade-off between the slow and fast path steps. EZBFT uses three steps compared to Aliph's two steps in the common case, and in return, provides slow path in only two extra communication steps unlike Aliph. Moreover, EZBFT's leaderless approach reduces the latency of the first communication step to near zero, yielding client-side latency comparable to Aliph's.
EBAWA [36] uses the spinning primary approach [23] to minimize the client-side latency in geo-scale deployments. However, a byzantine replica can delay its commands without detection reducing the overall server-side throughput. EZBFT's dependency collection mechanism enables correct replicas to only depend on commands that arrive in time, and execute without waiting otherwise. Table II summarizes the comparison of existing work with EZBFT. Note that EZBFT and Zyzzyva have the same bestcase communication steps. However, for EZBFT, the latency for the first-step communication is minuscule (tending towards zero) when compared to Zyzzyva's first-step latency.
Leaderless and multi-leader protocols [25], [26], [24], [2] have been proposed for the CFT model. Among these, EPaxos [24] and Caesar [25] collect dependencies and find a total order among all the dependent requests. Both protocols work in two phases: a fast phase that is reached under no contention and an additional slow phase that is required under contention. In EPaxos, the collected dependencies form a graph, which is linearized before executed.
Caesar can deliver fast phase consensus even under nontrivial contention by having a replica wait until some conditions are satisfied before replying to the primary. Such wait conditions are harmful in BFT protocols, because a malicious replica can use this as an opportunity to cease progress.
In M 2 Paxos [26], a replica can order a request if it owns the object that the request accesses. Otherwise, it forwards the request to the right owner or acquires ownership. Acquiring ownership means becoming the primary for some subset of objects, and in CFT-based protocols, any replica can propose to be a owner of any subset of objects at any point in time. However, in BFT-based protocols, electing a primary is a more involved process requiring consent from other replicas. In addition, view numbers are pre-assigned to replicas; therefore, randomly choosing primaries is not a trivial process.

VII. CONCLUSIONS
State-of-the-art BFT protocols are not able to provide optimal request processing latencies in geo-scale deployments -an increasingly ubiquitous scenario for many distributed applications, particularly blockchain-based applications.
We presented EZBFT, a leaderless BFT protocol that provides three-step consensus in the common case, while essentially nullifying the latency of the first communication step. EZBFT provides the classic properties of BFT protocols including nontriviality, consistency, stability, and liveness. Our experimental evaluation reveals that EZBFT reduces latency by up to 40% compared to Zyzzyva. Status ∆ = {"not-seen", "spec-ordered", "committed"} Variables: cmdLog = the commands log at each replica proposed = command that have been proposed executed = the log of executed commands at each replica sentMsg = sent (but not yet received) messages crtInst = the next instance available for a command leader leaderOfInst = the set of instances each replica has started but not yet finalized committed = maps commands to set of commit attributs tuples owners = largest ballot number used by any replica variables cmdLog, proposed , executed , sentMsg, crtInst, leaderOfInst, committed , ownerLog, owners


SecureSurgiNET: A framework for ensuring security in telesurgery

The notion of surgical robotics is actively being extended to enable telesurgery, where both the surgeon and patient are remotely located and connected via a public network, which leads to many security risks. Being a safety-critical application, it is highly important to make telesurgery robust and secure against active and passive attacks. In this article, we propose the first complete framework, called SecureSurgiNET, for ensuring security in telesurgery environments. SecureSurgiNET is primarily based on a set of well-established protocols to provide a fool-proof telesurgical robotic system. For increasing the efficiency of secured telesurgery environments, the idea of a telesurgical authority is introduced that ensures the integrity, identity management, authentication policy implementation, and postoperative data security. An analysis is provided describing the security and throughput of Advanced Encryption Standard during the intraoperative phase of SecureSurgiNET. Moreover, we have tabulated the possible attacks on SecureSurgiNET along with the devised defensive measures. Finally, we also present a time complexity analysis of the SecureSurgiNET through simulations.

Introduction
Robotic surgery is an emerging surgical trend that is leading to the birth of telesurgery. 1 In robotics, surgeons perform surgeries while sitting in close proximity to the patient console. On the contrary, telesurgery enables a surgeon to operate on a patient remotely via a surgical robot and a communication network between them. Telesurgical robotic systems (TRSs) 1 allow a master (surgeon console) to operate on a slave (called surgical robot) situated at a remote geographical location. The surgeon visualizes the robotic arms' response and movement through video feedback on his console and controls the robotic arms accordingly.
Operation Lindbergh was the first major breakthrough in the telesurgery domain. 2 During this operation, carried out in 2001, Marescaux and his team, based in the United States, performed robotic surgery on a patient in France using the ZEUS surgical robot. The successful accomplishment of this and many preceding telesurgical procedures paved the success of remote robotic surgery. 1,3 The success of these operations has provided the evidence that contemporary TRSs are now capable of tackling mission-critical operations in extreme environments. 1 Telesurgery provides numerous offerings and benefits, such as quality care to the people of underdeveloped countries, access to immediate surgical care for wounded soldiers, cost-effective solutions across geographical locations, and active intervention of remote experts in sophisticated surgeries. 4 Moreover, this technology enables expert surgeons to remotely train young surgeons all across the globe. Similarly, telesurgery can bridge the gap and inconsistencies between the healthcare systems of developing and developed countries and regions. However, all the aforementioned benefits are reliant on a secure system and its ability to support security in adversarial, uncontrolled, and hostile environments. 5 Patients' safety, security, and data privacy are some of the major obstacles and concerns in these types of procedures. 6 To the best of our knowledge, one of the main obstacles behind the widespread usage of telesurgery is the almost nonavailability of secure dedicated mechanisms for telesurgeries. To our knowledge, the Interoperable Telesurgical Protocol (ITP) 5 is the only available protocol to specifically address the security requirements of telesurgery. Although this protocol addresses the issues of authentication and confidentiality, it lacks in addressing the development and implementation of security policies in national and international environments.
The accuracy of robotic manipulations and the video feedback to the surgeon is vital for patients' safety. This accuracy is in turn mainly dependent on data integrity, which is an extremely desirable characteristic of a telesurgical system. Integrity helps in achieving the desired safety and accuracy objectives of safety-critical applications, such as telesurgery. In case of any intentional or unintentional data modification, the system must provide nonrefutable evidence to establish the chain of accountability. 7 Similarly, nonrepudiation is a key feature that provides evidence against the deniability of participating entities. Such characteristics would help in raising patients' confidence levels and thus would provide the basis for the success and widespread adoption of this telesurgical technology. [8][9][10] In this article, we proposed a security framework (SecureSurgiNET) that provides a foundation for developing secure telesurgical systems. We adopt a useful classification, inspired by Dowler and Hall's 11 classification, of telesurgery for our security architecture that breaks the telesurgical procedures into three distinct phases referred to as the preoperative, intraoperative, and postoperative phases. In the preoperative phase, platform integrity is ensured. Furthermore, a secure connection between the master and slave is established based on the X.509 digital certificates and patients' biometric identities. A dummy identity is managed against a patient's real identity and is never revealed to any unauthorized entities. The authentication and authorization processes are controlled by the implementation of formal policies. Secret parameters are shared only after a successful authentication session. Similarly, SecureSurgiNET ensures encryption and authentication of communication data in both intraoperative and postoperative phases.
In the intraoperative phase, the proposed framework provides multiple Transmission Control Protocol (TCP) and User Datagram Protocol (UDP) connections for communication. The TCP is used for reliable communication, while UDP provides throughput advantages. Moreover, Advanced Encryption Standard (AES) is used to encrypt the intraoperative phase communication, that is, video feedback from the patient to surgeon console and control commands from the surgeon to patient consoles. The proposed architecture enforces confidentiality and integrity of the data in the intraoperative phase while considering the real-time requirements. In contrast, during the postoperative phase, the postsurgical data are collected and stored securely and anonymously at the central telesurgical authority (TSA) database server (DBS) for future reference and legal requirements, if any.
In general, secure identification of doctors and patients in a telemedicine or telesurgical system is of prime importance. The key features of secure telemedicine systems include confidentiality of patient information, mutual authentication, patient anonymity, data integrity, freshness of communication, and mobility. 12 The proposed SecureSurgiNET handles the identity challenges through the use of a TSA including a strong authentication server (SAS) and an identity management server (IDMS). The TSA maintains a complete record of participating entities, including doctors and patients via the security administrator (SA) IDMS. Further details are given in section ''SecureSurgiNET: the proposed framework.'' The organization of this article is as follows: first, background and related work are presented. Then possible attacks and challenges to telesurgical systems are discussed, followed by details on the proposed architecture of our framework along with the design and flow of different protocols. In the following section, we discuss some results of video encryption as well as their analysis. In the end, we conclude this article and discuss potential future work.

Background and related work
Telesurgery mainly relies upon surgical robotics and communication networks, that is, Internet. After years of research in surgical robotics, ZEUS and da Vinci surgical robots are now commercially available. 3 ZEUS was also used in the first ever transatlantic surgery, known as Operation Lindbergh 13 in 2001. In this surgical procedure, Dr Marescaux and his team performed laparoscopic cholecystectomy that is, removal of gallbladder using a minimally invasive procedure, on a 68-year-old woman at a hospital in Strasbourg, France. The doctor and his team were operating from New York, USA. The underlying network facilities were provided by France Telecommunications, which was a high-bandwidth, reliable, secure, and low-latency asynchronous transfer mode (ATM) network. 2 The ZEUS surgical robotic system was replaced by the da Vinci system, which is another teleoperated surgical robotic system and has a comparable efficiency. 14 Regardless of the recent research advances in robotic surgery, very little progress has been made in the area of security of telesurgery. To date, there does not exist any complete security framework, specifically for designing and developing security aspects of telesurgical systems. There is a dire need for a security framework that takes into account the safety as well as legal and technical requirements of telesurgeries. 15,16 The most significant work in telesurgery so far is the development of ITP, which is designed for interoperability between the telesurgical robots and controllers. 17 But it ignores the security requirements of telesurgery.
Secure ITP is an enhancement of ITP 5 that uses the open software tools and Federal Information Processing Standards (FIPS) guidelines to develop a prototype to address the stringent telesurgery security requirements. Secure ITP addresses the four security requirements including authorization, authentication, communication, and policy development and enforcement. Secure ITP specifies two channels between the master and slave, that is, the Transport Layer Security (TLS) and Datagram Transport Layer Security (DTLS). TLS is used to provide security to TCP-based communication and DTLS is used for UDP communication. Secure ITP uses AES to encrypt the communication between the master and slave consoles. 5 Secure ITP is a reasonable design but fails in addressing some important issues such as patient identity theft, as well as some other administrative and legal issues.
Dowler and Hall 11 have highlighted the safety issues in telesurgery and divided the telesurgical procedures into three phases, namely preoperative, intraoperative, and postoperative phases. In another research, 18 the authors have pointed out security, availability, cost, and surgeon's legal responsibility as the major barriers in the success of remote robotic surgeries. Coble et al. 19 proposed a mechanism that allows the verifier to remotely attest the integrity of the software on a telesurgical robotic system. Tozal et al. 1 proposed a new method that integrates light-weight privacy and adaptive reliability in a single protocol, and it matches the performance of the AES cryptosystem. Bonaci et al. 20 analyzed the cybersecurity attacks against an advanced teleoperated robotic surgery system and focused on the denial-of-service (DoS) attacks. They used Fitts' law to quantify the impact and to analyze the tasks' difficulty under DoS attacks. Dong et al. 21 investigated the content modification attacks on a bilateral teleoperation system. They also proposed a safety mechanism to safeguard against a static malignant content modification attack. El Kalam et al. 22 presented a bilateral generalized predictive controller coupled to a quality of service (QoS)-friendly IP security protocol for telerobotic systems. P Fekri et al. 23 make use of machine learning algorithms to identify manipulated or incorrect commands, transmitted by any console, during a particular telesurgery. However, all of these works fail in providing a comprehensive solution to the problems related to secure telesurgery.
Besides, several remote health monitoring systems have been proposed in the literature to secure data of patients in a public network. R Amin et al. 24 proposed a multi-medical framework to ensure the anonymity and untraceability of patients during remote monitoring through sensor data. The framework also ensures confidentiality and integrity of the patient's data; however, it does not enforce security policies. V Sureshkumar et al. 25 proposed a robust communication protocol for ensuring the security of body sensor data for a smart healthcare system. The proposed system offers confidentiality, integrity, and anonymity; however, it lacks enforcement of security policies and is not fault tolerant. SD Suganthi et al. 26 proposed a lightweight authentication scheme for the IoT-enabled healthcare environments. The proposed scheme offers confidentiality and integrity; however, it overlooks anonymity and does not enforce security policies.
On the contrary, numerous generic security protocols exist which can be tailored to fulfill security requirements of telesurgery. These standardized generic protocols have well-tested security features and can be easily integrated in a variety of applications. 27 We have chosen the best security protocols and adopted the best design practices and guidelines to design a complete security framework called SecureSurgiNET. The protocols in the proposed framework provide authentication, authorization, confidentiality, integrity, anonymity, and nonrepudiation services. We argue that our proposed framework, that is, SecureSurgiNET, is the first complete setup that covers all the security requirements of the preoperative, intraoperative, and postoperative phases of any telesurgical system.

Attacks and defensive measures
Telesurgery is prone to different types of active and passive attacks. We have highlighted these attacks and countermeasures in Table 1.

SecureSurgiNET: the proposed framework
SecureSurgiNET is an assimilated framework and its architecture is shown in Figure 1. Security requirements of the proposed schemes are as follows: (a) security must be ensured during the preoperative, intraoperative, and postoperative phases of remote robotic surgery; (b) the scheme is designed to provide robust and time-efficient security to participating entities and assets of the telesurgical systems; (c) the postoperative phase ensures the secure recordkeeping of the entire intervention with log details. The proposed SecureSurgiNET comprises a patient console (the telesurgical robot along with a computer system), a TSA with comprehensive security infrastructure, and a surgeon console (a combination of surgical robot, its control and monitoring system). The TSA security infrastructure includes an SAS, a local certification authority (LCA), an IDMS and a key distribution server (KDS), an authorization and policy server (APS), a telesurgical server (TSS), and a DBS.
The SecureSurgiNET platform uses well-established security protocols and practices for authentication, platform integrity, identity management, authorization, secure communication, and secure data storage. The following subsections discuss the proposed SecureSurgiNET architecture.

TSA
TSA is a centralized authority that acts as a trusted third-party regulatory body. All framework components must be approved and registered with the TSA. The TSA is responsible for keeping and maintaining the complete record of participating entities via the SA IDMS. The telesurgical administrator, after registration and identity management, defines the authorization policy and the level of authorization for every entity to perform various functions as per the requirement, qualification, expertise, and permissions. The following dedicated servers and components help the TSA to perform the abovementioned tasks.
The LCA server. LCA issues, verifies, revokes, and updates the X.509 standard-based digital certificates for different entities. LCA establishes a hierarchy with the higher level certification authority (CA) for further verification.
SAS. SAS ensures the authentication of participating entities, such as surgeon console, patient console, patient, and surgeons, in the preoperative phase of telesurgery. The SAS verifies certificates from the LCA and identities from IDMS for an authentication process. The authentication protocol proposed for our architecture is an extension of the strong authentication protocol described in FIPS-196. 28 IDMS and KDS. IDMS is responsible for the storage and management of identities. It registers, updates, and distributes the identities for the participating entities. Furthermore, IDMS is responsible for issuing anonymous identities (AIDs) to patients against their biometric identity. These AIDs are used for protecting the patient's privacy. The KDS is liable to generate, manage, and securely distribute all the session security keys to entities.
APS. The policy server is responsible for managing the access and authorization policies. It is responsible for granting authorization to surgeons in order to conduct remote surgeries through the TSS. The TSS enforces the policies via a policy enforcement point (PEP) in coordination with its policy decision point (PDP). On successful validation of the user request, the authorization server securely issues the tokens authorizing access to the requested resources.
DBS. DBS is responsible for the secure storage of patients' medical data during the postoperative phase. An anonymous patient identity (APID) is used for data storage to protect the privacy of patients in case of any breach. Furthermore, it is ensured that access to data can only be permitted to authorized entities. The stored data are properly encrypted to ensure confidentiality and privacy of patients.
Patient console. Patient console, also known as the slave console, is appropriately equipped with the telesurgical robot, associated control, hardware/software, and the feedback devices. The feedback devices are used for providing the visual and audio feedback to the remote surgeon. This feedback is very important to judge the exact position and status of the patient and the surgical robot. All the feedback and controlling devices are registered, evaluated, and recommended by the TSA, prior to the commencement of telesurgery. Each console is embedded with a trusted platform module (TPM) chip for remote verification.
Surgeon console. Surgeon or the master console is equipped with the controlling and interacting devices to aid the surgeon to remotely control the surgical robot. The surgeon can remotely manipulate telesurgical robot on the patient console through the hardware devices and can perceive the reaction through video display. All the hardware control commands are transparently translated into communicable format and are managed by the underlying robust and secure software. The surgeon console has the TPM chip for platform integrity verification and secret key storage.
TSS. TSS interacts with different servers having TSA on behalf of authenticated users. It verifies the authenticity of users and forwards their requests to the internal resources of the TSA. It acts as a bridge between the internal and external entities. It coordinates with the TSA and sends the responses back to the users.

Design and flow of protocols
The registration phase The TSA SA, with its administrative privileges, registers the master and slave consoles and maintains the identities in the IDMS database. The profiles of surgeons with information such as qualification, expertise, and capabilities are maintained in the IDMS. Policies are formulated and enforced by the SA, which also requests the LCA for the issuance of digital certificates to different entities. After the digital certificate issuance, the SA securely manages the public keys and identities in the IDMS database. All of these tasks are performed prior to the commencement of the intraoperative phase. The flow and sequence of different protocols are shown in Figure 2. In the preoperative phase, our framework ensures platform integrity and participants' authentication, and subsequently grants authorization. In the end, the session keys are securely distributed to valid users in the preoperative phase. An AID is also issued to the patient against biometric identity in the preoperative phase. We propose to use the FIPS-196based authentication with extended features in our framework. Digital certificates are verified by the LCA and identities are verified by the IDMS. 27 After the successful authentication, the policy server validates and delegates authorization to perform the telesurgical procedure. During the intraoperative phase, a secure and reliable real-time protocol ensures the confidentiality and integrity of the data. TCP and UDP connections are established for reliability and throughput, respectively. AES encryption is used for confidentiality and privacy purposes. Finally, during the postoperative phase, the complete data of the session are securely stored within the DBS against the patient's AID. This information may be used in future for postoperative follow-up.

The preoperative phase
In the preoperative phase, the platform integrity, authentication, and authorization are ensured. Patient's AID against biometric identity is also issued and maintained during this phase. Furthermore, session parameters are also negotiated in the preoperative phase. These tasks are briefly described below.
Platform integrity verification. In response to the TSA challenge, both patient and surgeon consoles calculate the platform configuration register (PCR) values and digitally sign them with the secret key embedded in the TPM chip. The PCR values are sent to the TSA for verification against the PCR values that are already stored in the TSA. If the PCR values match against the already stored values, the system is considered healthy.
Authentication process. Authentication starts with a message exchange between the slave console and the SAS. The details and format of the challenge and response messages are described in Figure 2. The TSA authenticates the patient and surgeon console on the basis of X.509 digital certificates. These certificates are verified and validated by the LCA from the issuing authority. After authentication, the TSA issues a token to get authorization.
Patient AID. After the completion of platform integrity and authentication, the next step is to generate and maintain an AID against patient's biometric identity. The TSA, after receiving the patient's biometric identity, securely issues an AID against the biometric identity. The AID adds an extra layer of protection against identity theft and enhances privacy.
Authorization process. The patient console sends an authorization request along with authentication tokens to the TSS. The TSS, after verifying the token, forwards it to the IDMS and KDS. The IDMS checks the policy against APID and sends back the response back to the TSS. After receiving the response from the IDMS, the TSS forwards the request for authorization and session key to the authorization and key distribution server. The APS, after coordinating with the policy server, permits or denies the request.
Key distribution process. If permitted, the APS requests the KDS for the session keys. The KDS generates the key for the current session and updates the IDMS database accordingly and sends the encrypted keys back to the TSS. Session keys are encrypted with the public keys of the patient and surgeon consoles. It also concatenates the session ID, random numbers, surgery type, and participants' identities with the authorization token. The KDS sends this message to authorization severs, which then in turn forward it to the TSS. The TSS passes on this message to the requesting parties, that is, patient and surgeon consoles. Patient and surgeon consoles extract the session keys and other parameters and store them securely. Now, after having the session key, they are capable of generating other keys and able to establish a secure connection based on symmetric key cryptography. This secure session ensures confidentiality and integrity of data during the intraoperative phase.

The intraoperative phase
After the completion of the preoperative phase, the intraoperative phase starts, which is very crucial for patients' safety and privacy. In this phase, patients' video data and robotic commands travel over the Internet and thus could be compromised if not properly protected. Thus, our proposed framework specifies a standard track protocol AES-GCM Authenticated Encryption in Secure Real-Time Transport Protocol (SRTP). With SRTP being a profile of a standard protocol, Real-Time Transport Protocol (RTP) is suitable for real-time audio, video, and control commands and data communication between patient and surgeon consoles. SRTP provides confidentiality, integrity, and protection against the replay attacks.
SRTP with AES-GCM can encounter computational overhead by adopting a light-weight noncryptographic hash function, called GHASH. The GHASH is a keyed hash, especially adopted for the Galois/Counter Mode (GCM) standard and adds a little overhead. Similarly, the AES provides data confidentiality in our framework. It is a standard block cipher and, as per the National Security Agency (NSA)-defined policy, it is suitable for the protection of classified and SECRET information with the key widths of 128 bits or more. 29 Moreover, it is further recommended with the key sizes of 192 and 256 bits for top SECRET communication. In the literature, 5,7 different protocols have been analyzed and AES is considered more suitable for lifecritical applications.
GCM is adopted by the National Institute of Standards and Technology (NIST) as a standard for authenticated encryption and has been published in Special Publication SP-800-38D November, 2007. 30 The NIST standard provides specific implementation details for authenticated encryption. It is highlighted that GCM is efficient and accelerates the process of authenticated encryption by providing parallel implementation in hardware as well as in software. The Intel architecture provides a specific instruction, that is, PCLMULQDQ (Carry-Less Multiplication Quadword), to accelerate performance. 31 The postoperative phase The postoperative phase commences once the surgical procedure is successfully completed. In this phase, both the master and slave consoles reconcile and create data backup in the DBS. The backup is stored in an encrypted form against the APID. The TSA timestamps and digitally signs the data before storing at the DBS. However, the data can be made available for different research and analysis purposes, with the permission of the patient. Furthermore, the stored data can be used for audit, in case of postsurgical complications, and to ascertain that all the responsibilities have been fulfilled. Moreover, the data can be shared with different users, such as patients, doctors, and surgeons. But, before handing over these data, these are properly formatted so that the privacy of the patients can be preserved. For this purpose, a trusted framework for health information exchange 32 is needed that makes the patient data fully unidentifiable using the l-diversity algorithm before sharing.

Results and discussion
The intraoperative phase is very crucial in terms of timely availability of patients' video data to the surgeon and transfer of control commands from the surgeon to patient console. As data encryption is a computationally intensive process, we simulate the AES for different sizes of videos to judge the performance throughput.
For simulation purposes, a system having a 2.40 GHz CPU, 8 GB RAM, and a Core i5 processor running Windows 8 (32 bits) and NetBeans IDE 7.4 is used. The Java cryptography classes are used to perform encryption and decryption of videos.

Results
The encryption and decryption throughputs for video files of different sizes against 128-, 192-, and 256-bit key sizes are depicted in Figure 3. The overall time delay of the SecureSurgiNET framework for different qualities of video and AES key lengths is presented in Table 2. It provides figures for the overall AES encryption time, network delay, and AES decryption time. An increase in time delay with comparatively larger key lengths can be observed from Figure 4.

Discussion
AES performance. It is evident from Figure 3 that, by increasing the key size, the throughput decreases but the level of security rises exponentially. The presented data signify that AES is quite efficient in terms of performance and higher key sizes with very minor trade-   offs in the throughput. The size of the TCP and UDP packets is in bytes and AES encryption adds overhead of only a few milliseconds. A very high quality video, which requires 0.15 MB/s, can easily be encrypted and decrypted without any noticeable visual impact and additional delays. This minor overhead, on the contrary, provides a high level of security and privacy to the patient's medical records. Furthermore, it can be examined from Figure 4 that, by increasing the key size, the time delay increases as well. The same can be examined with increasing the video quality. From the data presented in Table 2 and Figure 4, we can observe that the 128-bit encrypted transmission is approximately 50% faster than the 256bit encryption and approximately 30% faster compared with the 192-bit encryption. It can also be observed that the performance of encryption increases with the increase in video quality.
The time complexity and throughput analysis presented above clarifies that the proposed algorithm provides good performance even with a low-end computing machine. Using a state-of-the-art computing machine, one can perform these computations very fast and with very minimal overhead. Furthermore, the preoperative and postoperative phases are flexible and the time overhead will not affect the procedure significantly.
AES security. We propose to use the AES encryption to encrypt the video and command data during the intraoperative phase. The AES is the state-of-the-art encryption algorithm with three key bit lengths, that is, 128, 192, and 256 bits. The security of AES is very high compared to DES (Data Encryption Standard), 3DES, Blowfish, RC4, and IDEA (International Data Encryption Algorithm). European Union (EU) consortium recommends AES with 128 bits as the minimum for security purposes, but it is expected that 192 or 256 bits would be a more feasible choice in the next 15-20 years. There is no known successful attack against AES but DES is susceptible to linear 33 and differential cryptanalysis. 29 Blowfish has a 64-bit block size and is not suitable for most applications. Also, there are many reported attacks 34-36 against reducedround Blowfish. Security of the ciphers is quantified with the key length and 128-bit AES is suitable for SECRET applications, while 192-and 256-bit AES for TOP SECRET purposes. There are a number of attacks reported against RC4 such as the state recovery attack, 37 secret key recovery attack, 38 and various other attacks. 39 Thus, it is concluded that AES security is suitable for telesurgical purposes due to its strong algebraic properties and the fact that there are no reported successful attacks against it. These findings are supported from the reported analysis of different encryption algorithms such as RC4, DES, 3DES, and IDEA and it was concluded that AES is a secure, fast, and reliable algorithm in terms of security and performance. 40 Furthermore, its key lengths make brute force attack impractical with the current state-of-the-art computing machines. For hash functions, we have proposed the use of GCM, which is provably secure, 41 is very efficient as well as fast due to its hardware implementation, and is fully parallelizable. 42

Analysis
Comparison of our proposed framework with existing approaches is presented in Table 3. We can analyze that the SecureSurgiNET is more comprehensive and complete than the existing approaches in this realm. A brief description of some features is given in the following.

Security strength
The implementation of the proposed framework is based on well-established and standardized protocols to provide a robust and secure system for telesurgery. Furthermore, using digital certificates and cryptographic nonce ensures strong authentication and guards against masquerading and replay attacks. R Amin et al. 24 3 ü ü ü ü 3 ü 3 P Fekri et al. 23 3 Implementation of appropriate policies, authorization rules, and identity management reinforces our system against session hijacking. A strong cipher like AES has the potential to thwart spying and criminal privacy violations. Moreover, the dedicated servers are used for each task and, if any server is compromised, its effects will be limited only to that single resource and the attacker cannot threaten the security of other servers. A centralized TSA makes it possible to enforce strong security policies and access rules in an international environment. Thus, standardized surgical practices can be enforced effectively in the proposed architecture. Moreover, SRTP with AES-GCM ensures the implementation of security services in real time for the underlying system. Additional chaining of patient data with AID adds an extra layer of privacy.

Scalability
The design concept of the central TSA and public key infrastructure (PKI) makes the proposed framework more scalable. Moreover, it can be extended to multiple geographic locations with tighter policies to connect patients with their desired surgeons around the globe.

Adaptability
The modular design of SecureSurgiNET provides easy integration with new protocols without any significant change. If technological advances introduce more efficient and robust security protocols, our system can adapt and integrate with them quickly and without any significant update requirements.

Fault tolerance
The modular design of SecureSurgiNET enables decentralized access to different components of the system, that is, if a server/component fails (due to any reason), then it does not stop other components from working. With load balancing between different parallel servers offering the same functionality, the system continues to work in the event of failure.

Nonrepudiation
With the security policies enforcement along with the comprehensive authentication and authorization mechanisms, the system guarantees the authenticity and effectiveness of operations between different entities.

Computation and communication overhead
Although SecureSurgiNET has some overhead in terms of communication and computation, it is comparable to the alternatives such as TLS and DTLS. Adaptation of AES-GCM makes fast authentication encryption possible and thus outshines other security algorithms. Its efficient hardware and software implementation and parallelization capability makes it more proficient. The proposed SecureSurgiNET adds more value in terms of security and safety to the telesurgical systems. However, the adaptation of AES with the parallelized version of GCM can make it further valuable.

Conclusion
The proposed SecureSurgiNET framework is designed to meet the stringent safety and security requirements of telesurgical systems in all phases. The contribution of this article is multifold. To our knowledge, it is the first complete framework for the security of telesurgical systems. In the preoperative phase, the TSA forms a special purpose PKI that provides numerous benefits such as platform integrity and participant authentication and authorization. Patients' AID adds an extra layer of privacy and guards against identity theft. During the intraoperative phase, our framework provides an efficient and secure encryption and authentication scheme. This scheme is based on standardized and well-established security protocols, which offer a high level of security and throughput. The security, along with its modularity, makes our design flexible and adaptable. It can integrate newly available protocols quite easily and with greater flexibility, without affecting much of the underlying architecture. All policies and credentials are securely and centrally managed, thus providing the capability to enforce everchanging policies and rules. Access to the data can only be granted after proper authentication and authorization that guards against illegal data deletions and modifications. This framework provides a foundation for developing secure and robust telesurgical systems.
In future, this framework will be formally evaluated in terms of adequacy in providing security to telesurgery. For this purpose, a complete prototype or simulation setup needs to be developed.

Declaration of conflicting interests
The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.