pRipple Labs Inc, 2014The Ripple Protocol Consensus AlgorithmDavid SNoah Youngsnyoungsnyu.eduArthur BAbstractWhile several consensus algorithms exist for the Byzantine Generals Problem, specifically as itpertains to distributed payment systems, many suffer from high latency induced by the requirementthat all nodes within the network communicate synchronously. In this work, we present a novelconsensus algorithm that circumvents this requirement by utilizing collectively-trusted subnetworkswithin the larger network. We show that the “trust” required of these subnetworks is in fact minimaland can be further reduced with principled choice of the member nodes. In addition, we show thatminimal connectivity is required to maintain agreement throughout the whole network. The result is alow-latency consensus algorithm which still maintains robustness in the face of Byzantine failures. Wepresent this algorithm in its embodiment in the Ripple Protocol.Contents1 Introduction 12 Definitions, alization and Previous Work 22.1 Ripple Protocol Components . . . . . . . . . . . 22.2 alization . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Existing Consensus Algorithms . . . . . . . . . 32.4 al Consensus Goals . . . . . . . . . . . . . . 33 Ripple Consensus Algorithm 43.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . 43.3 Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 53.4 Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Convergence nbsp;Heuristics and Procedures4 Simulation Code 75 Discussion 76 Acknowledgments 8References 81. IntroductionInterest and research in distributed consensus systemshas increased markedly in recent years, with a centralfocus being on distributed payment networks. Such net-works allow for fast, low-cost transactions which are notcontrolled by a centralized source. While the economicbenefits and drawbacks of such a system are worthy ofmuch research in and of themselves, this work focuseson some of the technical challenges that all distributedpayment systems must face. While these problems arevaried, we group them into three main categories cor-rectness, agreement, and utility.By correctness, we mean that it is necessary for adistributed system to be able to discern the difference be-tween a correct and fraudulent transaction. In traditionalfiduciary settings, this is done through trust betweeninstitutions and cryptographic signatures that guaranteea transaction is indeed coming from the institution thatit claims to be coming from. In distributed systems,however, there is no such trust, as the identity of anyand all members in the network may not even be known.Therefore, alternative s for correctness must be1utilized.Agreement refers to the problem of maintaining asingle global truth in the face of a decentralized account-ing system. While similar to the correctness problem,the difference lies in the fact that while a malicioususer of the network may be unable to create a fraudu-lent transaction defying correctness, it may be able tocreate multiple correct transactions that are somehowunaware of each other, and thus combine to create afraudulent act. For example, a malicious user may maketwo simultaneous purchases, with only enough funds intheir account to cover each purchase individually, butnot both together. Thus each transaction by itself iscorrect, but if cuted simultaneously in such a waythat the distributed network as a whole is unaware ofboth, a clear problem arises, commonly referred to asthe “Double-Spend Problem” [1]. Thus the agreementproblem can be summarized as the requirement that onlyone set of globally recognized transactions exist in thenetwork.Utility is a slightly more abstract problem, which wedefine generally as the “usefulness” of a distributed pay-ment system, but which in practice most often simplifiesto the latency of the system. A distributed system thatis both correct and in agreement but which requires oneyear to process a transaction, for example, is obviouslyan inviable payment system. Additional aspects of util-ity may include the level of computing power requiredto participate in the correctness and agreement processesor the technical proficiency required of an end user toavoid being defrauded in the network.Many of these issues have been explored long beforethe advent of modern distributed computer systems, viaa problem known as the “Byzantine Generals Problem”[2]. In this problem, a group of generals each controla portion of an army and must coordinate an attack bysending messengers to each other. Because the gener-als are in unfamiliar and hostile territory, messengersmay fail to reach their destination just as nodes in adistributed network may fail, or send corrupted data in-stead of the intended message. An additional aspectof the problem is that some of the generals may betraitors, either individually, or conspiring together, andso messages may arrive which are intended to create afalse plan that is doomed to failure for the loyal gener-als just as malicious members of a distributed systemmay attempt to convince the system to accept fraudulenttransactions, or multiple versions of the same truthfultransaction that would result in a double-spend. Thusa distributed payment system must be robust both inthe face of standard failures, and so-called “Byzantine”failures, which may be coordinated and originate frommultiple sources in the network.In this work, we analyze one particular implemen-tation of a distributed payment system the Ripple Pro-tocol. We focus on the algorithms utilized to achievethe above goals of correctness, agreement, and utility,and show that all are met within necessary and predeter-mined tolerance thresholds, which are well-understood.In addition, we provide code that simulates the consen-sus process with parameterizable network size, numberof malicious users, and message-sending latencies.2. Definitions, alization andPrevious WorkWe begin by defining the components of the RippleProtocol. In order to prove correctness, agreement, andutility properties, we first alize those properties intoaxioms. These properties, when grouped together, the notion of consensus the state in which nodes in thenetwork reach correct agreement. We then highlightsome previous results relating to consensus algorithms,and finally state the goals of consensus for the RippleProtocol within our alization framework.2.1 Ripple Protocol ComponentsWe begin our description of the ripple network by defin-ing the following termsServer A server is any entity running the RippleServer software as opposed to the Ripple Clientsoftware which only lets a user send and receivefunds, which participates in the consensus pro-cess.Ledger The ledger is a record of the amountof currency in each user’s account and representsthe “ground truth” of the network. The ledger isrepeatedly updated with transactions that success-fully pass through the consensus process.Last-Closed Ledger The last-closed ledger isthe most recent ledger that has been ratified by theconsensus process and thus represents the currentstate of the network.Open Ledger The open ledger is the currentoperating status of a node each node maintainsits own open ledger. Transactions initiated byend users of a given server are applied to the open2ledger of that server, but transactions are not con-sidered final until they have passed through theconsensus process, at which point the open ledgerbecomes the last-closed ledger.Unique Node List UNL Each server, s, main-tains a unique node list, which is a set of otherservers that s queries when determining consen-sus. Only the votes of the other members of theUNL of s are considered when determining con-sensus as opposed to every node on the network.Thus the UNL represents a subset of the networkwhich when taken collectively, is “trusted” by sto not collude in an attempt to defraud the net-work. Note that this definition of “trust” does notrequire that each individual member of the UNLbe trusted see section 3.2.Proposer Any server can broadcast transactionsto be included in the consensus process, and everyserver attempts to include every valid transactionwhen a new consensus round starts. During theconsensus process, however, only proposals fromservers on the UNL of a server s are consideredby s.2.2 alizationWe use the term nonfaulty to refer to nodes in the net-work that behave honestly and without error. Conversely,a faulty node is one which experiences errors which maybe honest due to data corruption, implementation er-rors, etc., or malicious Byzantine errors. We reducethe notion of validating a transaction to a simple binarydecision problem each node must decide from the in-ation it has been given on the value 0 or 1.As in Attiya, Dolev, and Gill, 1984 [3], we defineconsensus according to the following three axioms1. C1 Every nonfaulty node makes a decision infinite time2. C2 All nonfaulty nodes reach the same deci-sion value3. C3 0 and 1 are both possible values for all non-faulty nodes. This removes the trivial solutionin which all nodes decide 0 or 1 regardless of theination they have been presented.2.3 Existing Consensus AlgorithmsThere has been much research done on algorithms thatachieve consensus in the face of Byzantine errors. Thisprevious work has included extensions to cases where allparticipants in the network are not known ahead of time,where the messages are sent asynchronously there isno bound on the amount of time an individual node willtake to reach a decision, and where there is a delineationbetween the notion of strong and weak consensus.One pertinent result of previous work on consen-sus algorithms is that of Fischer, Lynch, and Patterson,1985 [4], which proves that in the asynchronous case,non-termination is always a possibility for a consen-sus algorithm, even with just one faulty process. Thisintroduces the necessity for time-based heuristics, toensure convergence or at least repeated iterations ofnon-convergence. We shall describe these heuristics forthe Ripple Protocol in section 3.The strength of a consensus algorithm is usuallymeasured in terms of the fraction of faulty processesit can tolerate. It is provable that no solution to theByzantine Generals problem which already assumessynchronicity, and known participants can tolerate morethan n 13 byzantine faults, or 33 of the networkacting maliciously [2]. This solution does not, however,require verifiable authenticity of the messages deliveredbetween nodes digital signatures. If a guarantee on theunforgeability of messages is possible, algorithms ex-ist with much higher fault tolerance in the synchronouscase.Several algorithms with greater complexity havebeen proposed for Byzantine consensus in the asyn-chronous case. FaB Paxos [5] will tolerate n 15Byzantine failures in a network of n nodes, amountingto a tolerance of up to 20 of nodes in the networkcolluding maliciously. Attiya, Doyev, and Gill [3] in-troduce a phase algorithm for the asynchronous case,which can tolerate n 14 failures, or up to 25 ofthe network. Lastly, Alchieri et al., 2008 [6] presentBFT-CUP, which achieves Byzantine consensus in theasynchronous case even with unknown participants, withthe maximal bound of a tolerance of n 13 failures,but with additional restrictions on the connectivity ofthe underlying network.2.4 al Consensus GoalsOur goal in this work is to show that the consensusalgorithm utilized by the Ripple Protocol will achieveconsensus at each ledger-close even if consensus is thetrivial consensus of all transactions being rejected, andthat the trivial consensus will only be reached with aknown probability, even in the face of Byzantine failures.3Since each node in the network only votes on proposalsfrom a trusted set of nodes the other nodes in its UNL,and since each node may have differing UNLs, we alsoshow that only one consensus will be reached amongstall nodes, regardless of UNL membership. This goal isalso referred to as preventing a “fork” in the network asituation in which two disjoint sets of nodes each reachconsensus independently, and two different last-closedledgers are observed by nodes on each node-set.Lastly we will show that the Ripple Protocol canachieve these goals in the face of n 15 failures,which is not the strongest result in the literature, but wewill also show that the Ripple Protocol possesses severalother desirable features that greatly enhance its utility.3. Ripple Consensus AlgorithmThe Ripple Protocol consensus algorithm RPCA, isapplied every few seconds by all nodes, in order to main-tain the correctness and agreement of the network. Onceconsensus is reached, the current ledger is considered“closed” and becomes the last-closed ledger. Assum-ing that the consensus algorithm is successful, and thatthere is no fork in the network, the last-closed ledgermaintained by all nodes in the network will be identical.3.1 DefinitionThe RPCA proceeds in rounds. In each roundInitially, each server takes all valid transactions ithas seen prior to the beginning of the consensusround that have not already been applied thesemay include new transactions initiated by end-users of the server, transactions held over froma previous consensus process, etc., and makesthem public in the of a list known as the“candidate set”.Each server then amalgamates the candidate setsof all servers on its UNL, and votes on the veracityof all transactions.Transactions that receive more than a minimumpercentage of “yes” votes are passed on to the nextround, if there is one, while transactions that donot receive enough votes will either be discarded,or included in the candidate set for the beginningof the consensus process on the next ledger.The final round of consensus requires a minimumpercentage of 80 of a server’s UNL agreeingon a transaction. All transactions that meet thisrequirement are applied to the ledger, and thatledger is closed, becoming the new last-closedledger.3.2 CorrectnessIn order to achieve correctness, given a maximal amountof Byzantine failures, it must be shown that it is im-possible for a fraudulent transaction to be confirmedduring consensus, unless the number of faulty nodesexceeds that tolerance. The proof of the correctness ofthe RPCA then follows directly since a transaction isonly approved if 80 of the UNL of a server agreeswith it, as long as 80 of the UNL is honest, no fraud-ulent transactions will be approved. Thus for a UNLof n nodes in the network, the consensus protocol willmaintain correctness so long asf nbsp;n 15 1where f is the number Byzantine failures. In fact, evenin the face of n 151 Byzantine failures, correct-ness is still technically maintained. The consensus pro-cess will fail,/p