文件名称:
ripple_consensus_whitepaper.pdf
开发工具:
文件大小: 417kb
下载次数: 0
上传时间: 2019-08-24
详细说明：瑞波共识协议白皮书，官方原版，需要的朋友快快下载吧ledger of that server, but transactions are not con- previous work has included extensions to cases where all
sidered final until they have passed through the participants in the network are not known ahead of time,
consensus process, at which point the open ledger where the messages are sent asynchronously(there is
becomes the last-closed ledger
no bound on the amount of time an individual node will
take to reach a decision) and where there is a delineation
Unique Node List (UNL): Each server, S, main- between the notion of strong and weak consensus
tains a unique node list, which is a set of other
One pertinent result of previous work on consen
servers that s queries when determining consen- sus algorithms is that of Fischer, Lynch, and Patterson
sus. Only the votes of the other members of the
1985[4 which proves that in the asynchronous case
UNL of s are considered when determining con
non-termination is always a possibility for a consen
sensus(as opposed to every node on the network)
sus algorithm, even with just one faulty process. This
Thus the unl represents a subset of the network
ntroduces the necessity for time-based heuristics, to
which when taken collectively, is"trusted by s ensure convergence (or at least repeated iterations of
to not collude in an attempt to defraud the net- non-convergence). We shall describe these heuristics for
work.Note that this definition of "trust does not the ripple protocol in section 3
require that each individual member of the UNL
The strength of a consensus algorithm is usually
be trusted(see section 3.2)
measured in terms of the fraction of faulty processes
Proposer: Any server can broadcast transactions
it can tolerate. It is provable that no solution to the
to be included in the consensus process, and every
Byzantine Generals problem(which already assumes
server attempts to include every valid transaction
synchronicity, and known participants) can tolerate more
when a new consensus round starts. During the
than(n-1/3 byzantine faults, or 33 of the network
consensus process, however, only proposals from
acting maliciously [2]. This solution does not, however
require verifiable authenticity of the messages delivered
servers on the unl of a server s are considered
between nodes(digital signatures ). If a guarantee on the
unforgeability of messages is possible, algorithms ex
2.2 Formalization
ist with much higher fault tolerance in the synchronous
We use the term nonfaulty to refer to nodes in the net-
ase.
work that behave honestly and without error. Conversely,
Several algorithms with greater complexity have
been proposed for Byzantine consensus in the asyn
a faulty node is one which experiences errors which may
be honest(due to data corruption, implementation er
chronous case. FaB Paxos [5] will tolerate(n-1)/5
rors, etc.), or malicious ( Byzantine errors ). We reduce
Byzantine failures in a network of n nodes, amounting
to a tolerance of up to 20% of nodes in the network
the notion of validating a transaction to a simple binary
decision problem: each node must decide from the in
colluding maliciously. Attiya, Doyev, and Gill [3] in
troduce a phase algorithm for the asynchronous case
ormation it has been given on the value O or l
As in Attiya, Dolev, and Gill, 1984 33], we define
which can tolerate(n-1)/4 failures, or up to 25 of
consensus according to the following three axioms
the network. Lastly, Alchieri et al., 2008 [6] present
BFT-CUP, which achieves Byzantine consensus in the
(C1): Every nonfaulty node makes a decision in asynchronous case even with unknown participants, with
finite time
the maximal bound of a tolerance of(n-1)/3 failures,
2.(C2): All nonfaulty nodes reach the same deci-
but with additional restrictions on the connectivity of
sion value
the underlying network
3.(C3):0 and 1 are both possible values for all non-
faulty nodes. (This removes the trivial solution 2.4 Formal Consensus Goals
in which all nodes decide o or l regardless of the Our goal in this work is to show that the consensus
information they have been presented)
algorithm utilized by the ripple protocol will achieve
consensus at each ledger-close(even if consensus is the
2.3 Existing Consensus Algorithms
trivial consensus of all transactions being rejected), and
There has been much research done on algorithms that that the trivial consensus will only be reached with a
achieve consensus in the face of Byzantine errors. This known probability, even in the face of Byzantine failures
Since each node in the network only votes on proposals
on a transaction. All transactions that meet this
from a trusted set of nodes(the other nodes in its UNL),
requirement are applied to the ledger, and that
and since each node may have differing UNLS, we also
ledger is closed. becoming the new last -closed
show that only one consensus will be reached amongst
ledger
all nodes, regardless of uNL membership This goal is
also referred to as preventing a"fork in the network
3.2 Correctness
situation in which two disjoint sets of nodes each reach In order to achieve correctness, given a maximal amount
consensus independently, and two different last-closed of Byzantine failures, it must be shown that it is im
ledgers are observed by nodes on each node-set
possible for a fraudulent transaction to be confirmed
Lastly we will show that the Ripple protocol can during consensus, unless the number of faulty nodes
achieve these goals in the face of(n-1)/5 failures, exceeds that tolerance. The proof of the correctness of
which is not the strongest result in the literature. but we the rPCa then follows directly: since a transaction is
will also show that the Ripple protocol possesses several only approved if 80% of the UNl of a server agrees
other desirable features that greatly enhance its utility. with it, as long as 80%o of the UNl is honest, no fraud
ulent transactions will be approved. Thus for a UNL
3. Ripple Consensus Algorithm
of n nodes in the network, the consensus protocol will
maintain correctness so long as
The Ripple Protocol consensus algorithm(RPCA), is
applied every few seconds by all nodes, in order to main
f≤(n-1)/5
tain the correctness and agreement of the network. Once
consensus is reached, the current ledger is considered where f is the number Byzantine failures. In fact, even
closed and becomes the last-closed ledger. Assum- in the face of(n-1)/ 5+1 Byzantine failures, correct-
ing that the consensus algorithm Is successful, and that ness is still technically maintained. The consensus pro
there is no fork in the network. the last-closed ledger cess will fail, but it will still not be possible to confirm a
maintained by all nodes in the network will be identical. fraudulent transaction. Indeed it would take(4n+1)/5
Byzantine failures for an incorrect transaction to be con-
3.1 Definition
firmed. We call this second bound the bound for weak
The RPCa proceeds in rounds. In each round
correctness, and the former the bound for strong correct
ness
Initially, each server takes all valid transactions it
It should also be noted that not all fraudulent trans
has seen prior to the beginning of the consensus actions pose a threat, even if confirmed during consen
round that have not already been applied(these
sus. Should a user attempt to double-spend funds in
may include new transactions initiated by end- two transactions, for example, even if both transactions
users of the server transactions held over from
are confirmed during the consensus process, after the
a previous consensus process, etc. ) and makes first transaction is applied, the second will fail, as the
them public in the form of a list known as the
funds are no longer available. This robustness is due to
candidate set
the fact that transactions are applied deterministically,
Each server then amalgamates the candidate sets
and that consensus ensures that all nodes in the network
of all servers on its UNL, and votes on the veracity
are applying the deterministic rules to the same set of
transactions
of all transactions
For a slightly different analysis, let us assume that
Transactions that receive more than a minimum the probability that any node will decide to collude and
percentage of"yes"votes are passed on to the next join a nefarious cartel is Pc. Then the probability of
round. if there is one, while transactions that do correctness is given by p, where
not receive enough votes will either be discarded
or included in the candidate set for the beginning
of the consensus process on the next ledger
P
e The final round of consensus requires a minimum This probability represents the likelihood that the size
percentage of 80% of a server's UNL agreeing of the nefarious cartel will remain below the maximal
threshold of Byzantine failures, given Pe. Since this
likelihood is a binomial distribution, values of pc greater
than 20%o will result in expected cartels of size greater
than 20% of the network, thwarting the consensus pro
cess. In practice a uNl is not chosen randomly, but
rather with the intent to minimize pc. Since nodes are
not anonymous but rather cryptographically identifiable,
selecting a unl of nodes from a mixture of continents
nations, industries, ideologies, etc. will produce values
of pc much lower than 20%. As an example, the proba
bility of the anti-Defamation League and the westboro
Baptist church colluding to defraud the network, is cer
tainly much, much smaller than 20%o. Even if the UNL
has a relatively large pc, say 15%, the probability of
correctness is extremely high even with only 200 nodes
in the UNL: 97.890
a graphical representation of how the probability of Figure 2. An example of the connectivity required to
incorrectness scales as a function of UNL Size for differ- prevent a fork between two UNL cliques
ing values of pc is depicted in Figure 1. Note that here
the vertical axis represents the probability of a nefarious
prove agreement is given by
cartel thwarting consensus, and thus lower values indi-
cate greater probability of consensus success. As can be
seen in the figure, even with a Pc as high as 10%, the
UNL∩UNL≥:max(UML,UNL1)v,(3)
probability of consensus being thwarted very quickly This upper bound assumes a clique-like structure of
becomes negligible as the unl grows past 100 nodes
UNLS. ie, nodes form sets whose UNls contain other
nodes in those sets. This upper bound guarantees that
3.3 Agreement
no two cliques can reach consensus on conflicting trans
To satisfy the agreement requirement, it must be shown actions, since it becomes impossible to reach the 80%
that all nonfaulty nodes reach consensus on the same threshold required for consensus. A tighter bound is
set of transactions, regardless of their UNLs. Since possible when indirect edges between UNLs are taken
the unls for each server can be different, agreement into account as well. For example. if the structure of the
is not inherently guaranteed by the correctness proof. network is not clique-like a fork becomes much more
For example, if there are no restrictions on the member- difficult to achieve. due to the greater entanglement of
ship of the UNL, and the size of the unl is not larger the uNls of all nodes
than 0.2*ntotal where ntotal is the number of nodes in
It is interesting to note that no assumptions are made
the entire network, then a fork is possible. This is 1l- about the nature of the intersecting nodes. The intersec-
lustrated by a simple example ( depicted in figure 2): tion of two uNls may include faulty nodes. but so long
imagine two cliques within the UNL graph, each larger as the size of the intersection is larger than the bound
than 0.2+ n,otal. By cliques, we mean a set of nodes required to guarantee agreement, and the total number
where each node's UNL is the selfsame set of nodes. of faulty nodes is less than the bound required to satisfy
Because these two cliques do not share any members, strong correctness, then both correctness and agreement
it is possible for each to achieve a correct consensus will be achieved. That is to say, agreement is dependent
independently of each other, violating agreement. If solely on the size of the intersection of nodes, not on the
the connectivity of the two cliques surpasses 0.2+ ntotal, size of the intersection of nonfaulty nodes
then a fork is no longer possible, as disagreement be
tween the cliques would prevent consensus from being 3.4 Utility
reached at the 80%agreement threshold that is required. While many components of utility are subjective, one
that is indeed provable is convergence: that the consen-
An upper bound on the connectivity required to sus process will terminate in finite time
■p。=0.
0.15
p=0.10
p=0.05
0.1
10
170
IL Size
Figure 1. Probability of a nefarious cartel being able to thwart consensus as a function of the size of the UNL, for
different values of pc, the probability that any member of the UNL will decide to collude with others. Here, lower
values indicate a higher probability of consensus success
3.4.1 Convergence
Since the consensus algorithm itself is deterministic
We define convergence as the point in which the rPCa
nd has a preset number of rounds, t, before consensus
is terminated. and the current set of transactions are de
reaches consensus with strong correctness on the ledger
and that ledger then becomes the last-closed ledger. note
clared approved or not-approved(even if at this point
that while technically weak correctness still represents
no transactions have more than the 80%o required agree
ment, and the consensus is only the trivial consensus)
convergence of the algorithm, it is only convergence in
the limiting factor for the termination of the algorithm
the trivial case, as proposition C3 is violated, and no
transactions will ever be confirmed. from the results
is the communication latency between nodes. In order
to bound this quantity, the response-time of nodes is
above, we know that strong correctness is always achiev
monitored, and nodes who's latency grows larger than
able in the face of up to(n-1)/ 5 Byzantine failures,
and that only one consensus will be achieved in the
a preset bound b are removed from all UNLs. While
entire network so long as the uNl-connectedness con
this guarantees that consensus will terminate with an
dition is met equation 3). All that remains is to show
upper bound of tb, it is important to note that the bounds
that when both of these conditions are met consensus is
described for correctness and agreement above must
reached in finite time
be met by the final UNL, after all nodes that will be
dropped have been dropped. If the conditions hold for
validation,, in which they do not process or vote
the initial uNls for all nodes but then some nodes are
on transactions, but declare that are still partic
dropped from the network due to latency the correctness
ipating in the consensus process, as opposed to
and agreement guarantees do not automatically hold but
a different consensus process on a disconnected
must be satisfied by the new set of uNls
subnetwork
3. 4.2 Heuristics and Procedures
While it would be possible to apply the rpca in
As mentioned above, a latency bound heuristic is en
just one round of consensus, utility can be gained
forced on all nodes in the ripple network to guarantee
through multiple rounds, each with an increas-
that the consensus algorithm will converge. In addi-
ing minimum-required percentage of agreement
tion, there are a few other heuristics and procedures that
before the final round with an 80 %o requirement
provide utility to the rPca
These rounds allow for detection of latent nodes
e There is a mandatory 2 second window for all
in the case that a few such nodes are creating a
nodes to propose their initial candidate sets in
bottleneck in the transaction rate of the network
each round of consensus. While this does intro
These nodes will be able to initiall
ep u
ur-
duce a lower bound of 2 seconds to each consen-
ing the lower-requirement rounds but fall behind
sus round it also guarantees that all nodes with
and be identified as the threshold increases. In the
reasonable latency will have the ability to partici
case of one round of consensus, it may be the case
pate in the consensus process
that so few transactions pass the 80% threshold
that even slow nodes can keep up, lowering the
As the votes are recorded in the ledger for each
transaction rate of the entire network
round of consensus, nodes can be flagged and
removed from the network for some common
4. Simulation Code
easily-identifiable malicious behaviors. These in-
clude nodes that vote No on every transaction
The provided simulation code demonstrates a round of
and nodes that consistently propose transactions
RPCA, with parameterizable features(the number of
which are not validated by consensus
nodes in the network, the number of malicious nodes, la-
tency of messages, etc. The simulator begins in perfect
e A curated default UNL is provided to all users, disagreement (half of the nodes in the network initially
which is chosen to minimize pc, described in sec- propose"yes,, while the other half propose"no"), then
tion 3. 2. While users can and should select their proceeds with the consensus process, showing at each
own UNLS. this default list of nodes guarantees stage the number of yes/no votes in the network as nodes
that even naive users will participate in a consen- adjust their proposals based upon the proposals of their
sus process that achieves correctness and agree- UNL members. Once the 80% threshold is reached,
ment with extremely high probability
consensus is achieved. We encourage the reader to ex
periment with different values of the constants defined at
A network split detection algorithm is also em-
the beginning of"Sim. cpp, in order to become familiar
ployed to avoid a fork in the network. While
with the consensus process under different conditions
the consensus algorithm certifies that the transad
tions on the last-closed ledger are correct, it does
not prohibit the possibility of more than one last
5. Discussion
closed ledger existing on different subsections of We have described the rPCa, which satisfies the con-
the network with poor connectivity. To try and ditions of correctness, agreement, and utility which we
identify if such a split has occurred, each node have outlined above. The result is that the ripple pro
monitors the size of the active members of its tocol is able to process secure and reliable transactions
UNL. If this size suddenly drops below a preset in a matter of seconds: the length of time required for
threshold, it is possible that a split has occurred. one round of consensus to complete. These transactions
In order to prevent a false positive in the case are provably secure up to the bounds outlined in sec
where a large section of a UNL has temporary tion 3, which, while not the strongest available in the
latency, nodes are allowed to publish a "partial literature for Asynchronous Byzantine consensus, do
allow for rapid convergence and flexibility in network 4 Fischer, Michael J, Nancy A. Lynch, and Michael
membership When taken together, these qualities allow
S Paterson. " Impossibility of distributed consensus
the Ripple network to function as a fast and low-cost
with one faulty process Journal of the ACm (jacm
global payment network with well-understood security 32.2(1985): 374-382
and reliability properties
5I Martin, J-P, and Lorenzo Alvisi. "Fast byzan
While we have shown that the ripple protocol is
tine consensus. Dependable and Secure Computing
provably secure so long as the bounds described in equa
IEEE Transactions on 3.3(2006): 202-215
tions I and 3 are met, it is worth noting that these are [61 Alchieri, Eduardo aP, et al. "byzantine consensus
maximal bounds, and in practice the network may be
secure under significantly less stringent conditions. It
with unknown participants "Principles of Distributed
is also important to recognize, however, that satisfying
ystems. Springer Berlin Heidelberg, 2008. 22-40
these bounds is not inherent to the rpca itself. but
rather requires management of the UNLs of all users
The default uNL provided to all users is already suffi
cient, but should a user make changes to the uNL, it
must be done with knowledge of the above bounds. In
addition, some monitoring of the global network struc
ture is required in order to ensure that the bound in
equation 3 is met, and that agreement will always be
satisfied
We believe the RPCa represents a significant step
forward for distributed payment systems, as the le
latency allows for many types of financial transactions
previously made diffic
cult or even impossible with other
higher latency consensus methods
6. Acknowledgments
Ripple labs would like to acknowledge all of the peo
ple involved in the development of the Ripple Protocol
consensus algorithm. Specifically, Arthur Britto, for his
work on transaction sets Jed Mccaleb, for the original
Ripple protocol consensus concept, and David Schwartz
for his work on the "failure to agree is agreement to de
fer aspect of consensus Ripple labs would also like to
acknowledge Noah Youngs for his efforts in preparin
and reviewing this paper
References
Nakamoto, Satoshi.Bitcoin: A peer-to-peer elec-
tronic cash system Consulted 1. 2012(2008): 28
Lamport leslie. Robert shostak, and marshall
Pease.“ The Byzantine generals problem”ACM
Transactions on Programming Languages and Sys-
tems( TOPLAS)4.3(1982):382-401.
31 Attiya, C, D. Dolev, and J. Gill. "Asynchronous
Byzantine Agreement. Proc. 3rd. Annual ACM
Symposium on principles of distributed computing
1984
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
