WIXLIB

Algorithm 2: OM (0) (The base case for OM (f ))12345Commander sends its value to every lieutenant;for i 1 : N-1 doLieutenant i stores the value received from Commander as vi ;vi DEFAULT if no value received;Lieutenant i uses vi ;endwhich the recursion ends at OM (0), it requires f 1 rounds of executions.Essentially, as long as N 3f 1, the f 1 rounds of recursive executionsguarantee that at the end of algorithm every general has exactly the same setof votes, from which the majority function then produces the same result —the consensus is achieved. Due to its recursive fashion, OM (f ) algorithm hasO(N f 1 ) message complexity, which is impractical when N is large.Optional: The Phase King Algorithm1.1.4Practical Consensus Protocols in Distributed ComputingNow we have discussed single-value consensus in a synchronous network. In atypically distributed computing system, the clients spontaneously issue computing requests while the distributed processors work as a consortium to provide correct and reliable computing service in response to these requests. Thecorrectness requirement means not only every single request should be processed correctly, but also the sequence of requests from a client (or a groupof clients) should be processed in the correct order, which is called the totalordering requirement. The combination of the two requirements makes distributed computing a significantly harder task than the single-value consensusproblem we have seen previously. Moreover, the asynchronous nature of realworld networks further complicates the problem. In practice, we assume thereal-world distributed computing network is asynchronous but with boundedcommunication delay between two non-faulty servers.Replication In actual distributed computing systems, replication is the defacto choice for ensuring the availability of the system and the integrity ofthe service in face of faulty servers. A replication-based distributed systemmaintains a number of redundant servers in case the primary server crashes ormalfunctions. The redundant servers are also called backups or replicas. Thereare two major types of replication schemes: primary-backup and state-machinereplication.7

Primary Backup (PB) PB is also known as passive replication. It wasfirst proposed in [AD76]. In a PB based system of n replicas, one replicais designated as the primary and the others are backups. The primaryinteracts with clients and processes clients’ computation requests. Afterthe primary finishes one task, it sends to the backups what it has done.If the primary crashes, a replica will be selected to assume the role ofthe primary. PB only tolerates crash failures; it does not tolerate anynumber of Byzantine failures. State-Machine Replication (SMR) SMR is also known as activereplication. It was proposed in [Sch90]. In a SMR based system, theconsensus protocol is instantiated at each server which runs a deterministic state machine that receives inputs, changes states and producesoutputs in an “organized” manner. This enables the distributed networkto provide fault-tolerant service by replicating the state machine acrossserver replicas and processing client service request in a coordinated way.A good SMR protocol should guarantee two basic service requirements:safety - all processors execute the same sequence of requests, and liveness- all valid requests are executed.Next we introduce two well-known SMR based consensus protocols for distributed computing: Viewstamped Replication and Practical ByzantineFault Tolerance.Viewstamped Replication (VSR)VSR is an early protocol developed for distributed replication systems. Here wepresent an updated version of VSR proposed by Liskov and Cowling in 2012[LC12]. Interested reader may refer to [OL88] for Oki and Liskov’s originaldesign. In a VSR system with N replicas, there is one primary and N 1backups. Each replica operates a local state machine with state variables listedin Table 1.1. The “viewstamp” refers to the hv, ni pair, which essentiallyenables the replication network to process clients’ operation requests in thecorrect order.VSR consists of three sub-protocols; each is designed specially for one ofthe three status cases. We will leave out the message details and focus on thehigh-level work flow of these protocols.1) Normal operation protocol The normal operation runs from sessionto session when all functioning replicas hold the same view and the primaryis in good condition. A session includes the client sending request and thereplicas processing this request. A diagram of the normal operation protocol8

Table 1.1: State variables at replica i in riptionself indexlist of all replicas in the networkoperation status: either normal, view-change, or recoveringcurrent view numberthe most recent request message from a clientsequence number of m execute(m), the execution result of msequence number of the most recently committed client requestrecord of operation requests received so farrecord of most recent operation for all clientsTable 1.2: Messages in esponseFromclientprimaryreplica iprimaryprimaryreplica ireplica iprimaryreplica ireplica iToprimaryall backupsprimaryclientall backupsall replicasnew primaryall replicasall replicasthe recoverer9Formathrequest, mihprepare, m, v, n, cihprepareok, v, iihreply, v, eihcommit, v, cihstartviewchange, v 1, iihdotheviewchange, v 1, iihstartview, v 1, logihrecovery, iihrecoveryresponse, v, n, c, ii

Figure 1.2: The normal operation protocol of VSR for a three-replica system.for a three-replica system is shown in Figure 1.2. At the beginning of a session,the client sends to the primary a Request message indicating a new operationrequest.1. Prepare Upon receiving a request message, the primary updates its n,log, client-table and then passes this request to all backups using Preparemessages which also include its n and c which was updated in the previoussession. Each backup executes the primary-committed operations if thereis any and updates its state accordingly.2. PrepareOK Each backup sends a PrepareOK message to the primaryshowing its state is up to date. After receiving f PrepareOK messages,the primary executes the requested operation and then updates c, log,client-table.The primary then sends a Reply message to the client. Specifically if theprimary hasn’t received a client request for a long time, it sends a Commitmessage to the backups indicating the updated c, as an alternative to thePrepare message.2) View change protocol A view change is needed in the event of primaryfailure, which can be detected by a backup replica if no Prepare or Commitmessage has been received for a long time. After detecting the need for aview change, a replica updates its status to view-change and advances theview number to v 1. It then sends a StartViewChange message includingthe new view number v 1 to other replicas. When a replica receives atleast f StartViewChange messages with the new view number v 1, it sendsa DoTheViewChange message to the backup that will become the primary.10

When the new primary receives at least f 1 DoTheViewChange messages,it updates its state accordingly, sends to other replicas a StartView messagewith the updated log and the new view number v 1, and starts processingoperation requests from clients. In the meantime, backup replicas receive theStartView message and update their state according to the log in the message,and finally change status to normal.3) Recovering protocol When a replica recovers from a crash, it has togo through the recovering protocol before participating in normal operationand view change. It first sends a Recovery message to all other replicas. Eachreplica responds with a RecoveryResponse message indicating the current v.The primary needs to respond with additional state information including log,n, and c. The recovering replica waits until it has received at lease f 1RecoveryResponse messages, and then updates its state accordingly.Fault Tolerance Note VSR can tolerate f crash failures if the total numberof replicas (including the primary) N 2f 1. However, it has zero toleranceof Byzantine failures. For example if the primary is Byzantine faulty due tothe adversarial manipulation, it can simply deny all client operation requestswhile pretending to work normally with the backups. If a backup is Byzantineon the other hand, it may maliciously initiate a view change session to oustthe current primary without suspicion.Complexity analysis We analyze the message complexity of the normaloperation. The communication overhead is primarily contributed by the twophases: Ii the Prepare phase the primary broadcasts a Prepare message to allreplicas; in the PrepareOK phase all replicas send a PrepareOK message tothe primary. Therefore the message complexity for VSR’s normal operation isO(N ).Practical Byzantine Fault Tolerance (PBFT)In the practical scenario where the distributed computing system may be compromised by malicious actors, both the primary and the backups are proneadversary manipulation, which falls into the realm of Byzantine failures. Proposed by Castro and Liskov in 1999 [CL 99], PBFT advances VSR for tolerating Byzantine failures.PBFT consists of three sub-protocols: normal operation, checkpoint, andview-change. The messages involved are listed in Table 1.4. As an additionalsecurity measure, each message is signed by the sender and verified by thereceiver. In the following part we assume there are at most f faulty replicas11

Table 1.3: State variables at replica i in criptionself index (0 for primary)list of all replicas in the networkreplica i’s key for signing messagesoperation status: normal or view-changecurrent view numberthe most recent request message from a clientsequence number of m digest(m), the digest of m execute(m), the execution result of mThe latest checkpointlow-water mark, ie. sequence number of shigh-water mark; h and H form a sliding windowset of all valid Checkpoint messages proving the correctness of sset of a valid Pre-prepare message and all matching Preparemessages for a request with sequence number tset of the Pt for every request t that is higher than nset of all valid View-Change and View-Change messagesset of a specially chosen Pre-Prepare messagesrecord of operation requests received so farTable 1.4: Messages in w-ChangeNew-ViewCheckpointFromclientprimaryreplica ireplica ireplica ireplica iprimaryreplica iToprimaryall backupsall replicasall replicasclientall replicasall replicasall replicas12Format (signed)hrequest, miσchpre-prepare, v, n, diσ0hprepare, v, n, d, iiσihcommit, v, n, d, iiσihreply, e, iiσihview-change, v 1, n, C, P, iiσihnew-view, v 1, V, Oiσ0hcheckpoint, n, d, iiσi

and the network size N 3f 1. Later we will show N 3f 1 guaranteesthe protocol’s Byzantine fault tolerance.1) Normal operation protocol Similar to VSR, PBFT runs its normaloperation from session to session. A session starts with a client operationrequest and goes through three sequential phases of replica interaction, namelyPre-Prepare, Prepare, and Commit, before replying to the client.1. Pre-Prepare When the primary receives an operation request messagem, it assigns a sequence number n to the request and sends a Pre-Preparemessage along with the message m to all backups. After receiving aPre-Prepare message, a backup checks the associated signatures and thevalidity of v, n, d. If everything is valid and n is within the water markedrange hh, Hi, the backup accepts this message, updates its state accordingly, and proceeds to the Prepare phase.2. Prepare Each backup sends a Prepare message to all other replicas. Areplica that has received at least 2f 1 Prepare messages with the samev, n, d values updates its state accordingly and proceeds to the Commitphase.3. Commit Each replica sends a Commit message to all other replicas.When a replica receives at least 2f 1 Commit messages with the samev, n, d values, it first finishes executing the old requests with sequencenumbers lower than n, then executes the current request m to producethe result e, and finally updates its state accordingly.When a replica finishes the Commit phase, it sends the execution result ein a Reply message to the client. The client accepts an execution result onlyafter it receives at least 2f 1 Reply messages containing the same result e.2) Checkpoint protocol The checkpoint protocol is used by the replicas tosafely discard old items in log and agree on a stable checkpoint which providesessential service state info for the view-change process. Each replica periodically marks a executed client request as a checkpoint in log and records itssequence number as h, which is called the low water mark. It multicasts thecheckpoint to other replicas in the form of a Checkpoint message. When areplica collects at least 2f 1 Checkpoint messages with the same n and d, itmarks this checkpoint stable by assigning n to the variable h, and saves theseCheckpoint messages as the proof form the stable checkpoint. After that thereplica can safely discard from its log all Pre-Prepare, Prepare, and Commitmessages with sequence numbers prior to h. In addition to h, each replica alsoupdates the high water mark H.13

Figure 1.3: The normal operation protocol of PBFT for a four-replica system.3) View-change protocol Since a view is binded to a known primary, whenthe primary is suspected faulty, the backups carry out the view-change protocol to choose a new primary. When a backup received a request but has notexecuted it for a certain timeout (for example it stays in Phase2 of normal operation for too long), it stops receiving further messages related to the currentview v and updates status to view-change before sending a View-Changemessage for view v 1 to all replicas. When the new primary receives at least2f View-Change messages for view v 1, it multicasts a New-View messageto all backups, updates its log and hh, Hi pair, and proceeds into normal operation. A replicas validates the received New-View message, updates it state,and proceeds to normal operation as well.Fault tolerance In the normal operation, the separation of pre-preparephase and prepare phase is essential to the correct ordering of request execution and faulty primary detection. When a primary sends a Pre-Preparemessahe with out-of-order request or stays silent for a long time, the backupswill consider the primary faulty and initiate the view change protocol for anew primary, as long as the majority of backups are non-faulty. Now we discuss the condition for PBFT to tolerate f Byzantine replicas. In the normaloperation, a replica needs to receive 2f 1 Prepare messages with the samestate to proceed to the Commit phase; it then needs to receive 2f 1 Commit messages with the same state to proceed to request execution. This isequivalent to the scenario we discussed in the Oral Messaging algorithm forthe Byzantine generals problem: in a fully connected network the consensuscan be reached if the super-majority of components are non-faulty. The same14

Table 1.5: A Comparison between VSR and PBFT for partially asynchronousdistributed computing systemsYear proposedCFT conditionBFT conditionMessage ComplexityVSR1988N 2f 1NoneO(N )PBFT1999N 2f 1N 3f 1O(N 2 )consensus routine is applied in the checkpoint protocol and view-change protocol as well to guarantee the safety of the new primary election. As we haveassumed N 3f 1 in the beginning, messages from 2f 1 non-faulty replicas are enough for a super-majority consensus. In the general case where f isunknown (but N 3f 1 is assumed), the super-majority number should beupdated to b 2N3 c 1 from 2f 1 in the protocol.Complexity analysis We analyze the message complexity of the normaloperation. The communication overhead is primary contributed by the threephases: in the Pre-Prepare phase the primary broadcasts a message to all backups (O(N )); in the Prepare phase every backup broadcasts a message to allother replicas (O(N 2 )); in the Commit phase every replica broadcasts a message to all other replicas (O(N 2 )). Therefore the overall message complexityof PBFT’s normal operation is O(N 2 ). This is acceptable for a network thatis fully or near-fully connected.Optional: Paxos [Lam98, L 01]Comparison between VSR and PBFTVSR and PBFT are compared in Table 1.5. In a short summary, PBFTachieves Byzantine fault tolerance with a more complex protocol scheme andhigher communication overhead. To date PBFT has gained considerable interest in the blockchain community for its application in blockchains with smallnetwork size and permissioned access. We will introduce it in Section 1.3.1.2The Nakamoto ConsensusSince its inception in 2008, Bitcoin has become the leading figure in the cryptocurrency plethora. As of the first quarter of 2018, the Bitcoin network hasabout 10,000 mining nodes and market capitalization of more than 200 billion dollars. The popularity of Bitcoin and other cryptocurrencies has brought15

huge academic and industrial interest to blockchain, the enabling technologybehind the cryptocurrencies and many emerging distributed ledger systems.Out of various aspects of Bitcoin, the celebrated Nakamoto consensus [Nak08]is the key innovation to its security and performance. Similar to distributedcomputing systems, the consensus target for blockchain is the network’s entire transaction history - not only the transactions’ content, but also the theirchronological order. In a practical blockchain system such as Bitcoin andEthereum, the consensus protocol also needs to consider various physical factors such as network connectivity, network size, and adversarial influence. Inthis section we introduce the

From security’s perspective, the strength of a consensus protocol is usually measured by the number faulty components it can tolerate. Specially, if a consensus protocol can tolerate at least one crash failure, we call it crash-fault tolerant (CFT). Similarly, if a