Ripple Protocol 瑞波币

,

我们通过定义以下术语来开始对纹波网络的描述:

  • Server: 服务器是运行Ripple Server软件的任何实体（与仅允许用户发送和接收资金的Ripple Client软件相对），它参与共识过程。
  • Ledger: 分类帐是每个用户帐户中货币金额的记录，代表网络的“基本事实”。总账将使用成功完成共识流程的交易重复进行更新。
  • Last-Closed Ledger: 最后关闭的分类帐是经共识过程批准的最新分类帐，因此代表网络的当前状态。
  • Open Ledger: 开放分类账是一个节点的当前运行状态（每个节点都维护其自己的开放分类账），由给定服务器的最终用户发起的交易将应用于该服务器的开放分类账，但在交易通过之前，交易不会被视为最终交易共识过程，此时打开的分类帐成为最后关闭的分类帐。
  • Unique Node List (UNL): 每个服务器维护一个唯一的节点列表，该列表是确定共识时要查询的一组其他服务器。在确定共识时（与网络中的每个节点相对），仅考虑联合国语言联盟其他成员的选票。因此，联合国语言联盟表示网络的一个子集，当集体考虑时，将被“信任”，因此不会相互勾结欺骗网络。请注意，这种“信任”的定义并不要求UNL be的每个成员都是受信任的（请参阅第3.2节）。
  • Proposer: 任何服务器都可以广播要包含在共识过程中的交易，并且每个服务器都尝试在新的共识回合开始时包括每个有效交易。但是，在共识过程中，S仅考虑来自服务器S的UNL上服务器的提议。

特点：异步网络，可以容忍 $(1+n)/5$ 的failures

==同步异步网络的BFT算法的区别==

Ripple Consensus Algorithm

所有节点每隔几秒钟应用一次Ripple协议共识算法（RPCA），以保持网络的正确性和一致性。一旦达成共识，当前分类帐就被视为“封闭”，并成为最后封闭的分类帐（==区别PoW，这里解决了双花问题==）。假设共识算法是成功的，并且网络中没有分叉，则网络中所有节点维护的最后关闭的分类帐将是相同的。

Definition

RPCA分几轮进行。在每个round中：

  • 最初，每个服务器处理在共识轮开始之前看到的所有尚未应用的有效事务（这些事务可能包括服务器最终用户发起的新事务，从先前共识过程中保留的事务等），以及将其以称为“候选集”的列表形式公开。
  • 然后，每台服务器将其UNL上所有服务器的候选集合并，并对所有事务的准确性进行投票。
  • 得票数超过“yes”的最小百分比的交易将传递到下一个round（如果有的话），而得不到足够票数的交易将被丢弃，或被包括在候选者集中，以开始对下一个分类帐。
  • 最终一轮共识需要服务器的UNL达成交易的最低百分比为80％。所有满足此要求的交易都将应用到分类帐，并且分类帐已关闭，成为新的最后关闭分类帐。

Correctness 正确性

为了获得正确性，在给定最大数量的拜占庭式故障的情况下，必须证明，在协商一致的情况下不可能确认欺诈性交易，除非故障节点的数量超过该容忍度。然后直接得出RPCA正确性的证明：由于仅当服务器的UNL的80％同意该交易时，才批准该交易，因此，只要80％的UNL是诚实的，就不会批准任何欺诈性交易。因此，对于网络中的UNL of n nodes，只要以下条件，共识协议将保持正确性：

还应注意的是，即使在共识中得到确认，并非所有“欺诈性”交易都构成威胁。例如，如果用户尝试两次将资金用于两次交易，即使在共识过程中都确认了这两项交易，则在应用第一笔交易后，第二笔交易将失败，因为资金不再可用。这种鲁棒性是由于以下事实：确定性地应用事务，并且共识确保网络中的所有节点都将确定性规则应用于同一组事务。

对于稍微不同的分析，让我们假设任何节点将决定勾结和加入邪恶的卡特尔 $p_c$ 的概率。然后正确性的概率由$p^∗$给出，其中：

image-20201203192025316

该概率表示给定pc时有害卡特尔的大小将保持在拜占庭式故障最大阈值以下的可能性。由于这种可能性是二项式分布，因此pcgreaterer值大于20％将导致预期卡特尔的大小大于网络的20％，从而阻碍了共识过程。在实践中，UNL不是随机选择的，而是出于最小化目的。由于节点不是匿名的而是密码可识别的，因此需要从各大洲，国家，行业，意识形态等的混合中选择节点的UNL。例如，反诽谤联盟和Westboro Baptist教会合谋欺骗网络的概率肯定要比20％小得多，甚至远远小于20％。 largepc，例如15％，即使在UNL中只有200个节点，正确的可能性也非常高：97.8％。

图1中描绘了pcis的不同值，不正确概率如何根据UNL大小变化的图形表示。请注意，此处的垂直轴表示有害的卡特尔挫败共识的概率，因此，较低的值表示较大的概率共识成功。从图中可以看出，即使apcas高达10％，随着UNL超过100个节点，共识被迅速挫败的可能性也可以忽略不计。

Agreement

为了满足协议要求，必须证明所有无故障节点都在同一事务集上达成共识，无论其UNL如何。由于每个服务器的UNL可能不同，因此正确性证明并不能固有地保证协议的准确性，例如，如果对UNL的会员资格没有任何限制，并且UNL的大小不大于0.2 n整个网络中的节点数量，则可以进行分叉。这由一个简单的例子（图2中所示）来说明：想象一下UNL图中的两个集团，每个集团总计大于0.2 ntotal。 “集团”是指一组节点，其中每个节点的UNL是相同的节点集。由于这两个集团不共享任何成员，因此彼此之间有可能彼此独立地达成正确的共识，从而违反协议。如果两个集团的连通性总计超过0.2 * n，则将不再可能使用分叉，因为集团之间的分歧将阻止达成要求的80％协议阈值达成共识。

Convergence

我们将收敛定义为RPCA在分类账上具有高度正确性的共识，然后该分类账成为最后关闭的分类账。请注意，尽管技术上较弱的正确性仍表示算法的收敛性，但仅在琐碎的情况下才是收敛性，因为违反了命题C3，并且永远不会确认任何交易。从上面的结果可以看出，面对多达 $(n-1)/5$ 个拜占庭式失败，总是可以实现很强的正确性，并且只要有UNL连通性条件，整个网络就只能达成一个共识。满足（等式3）。剩下的一切只是表明，当同时满足这两个条件时，就会在有限的时间内达成共识。

由于共识算法本身是确定性的，并且在共识终止之前具有预设的回合数t，并且声明了当前交易集为已批准或未批准（即使在这一点上，没有交易超过80％需要达成共识，并且共识只是琐碎的共识），算法终止的限制因素是节点之间的通信延迟。为了限制该数量，需要监视节点的响应时间，并且延迟的节点会变大虽然这保证从所有UNL中删除了一个预设边界，但是这保证了共识将以最大边界tb终止，但重要的是要注意，在将要删除的所有节点都删除之后，finalUNL必须满足上述正确性和一致性描述的边界。条件适用于所有节点的初始UNL，但随后由于延迟而将某些节点从网络中删除，正确性和协议保证不会自动新的UNL必须满足您的需要。

Heuristics and Procedures

如上所述，在Ripple网络中的所有节点上强制执行延迟绑定启发式算法，以确保共识算法将收敛。此外，还有其他一些启发式方法和过程可为RPCA提供实用程序。

  • 所有节点都有强制性的2秒窗口，可以在每一轮共识中提出其初始候选集。尽管这确实为每个共识回合引入了2秒的下限，但它也保证了所有具有合理延迟的节点都将有能力参与共识过程。
  • 当投票被记录在分类帐中以达成共识后，就可以针对某些常见的，易于识别的恶意行为对节点进行标记并从网络中删除。这些在每个交易中都投票否决的隐含节点，以及始终如一地提出未经共识验证的交易的节点。
  • 已为所有用户提供了预定的默认UNL，选择它以最小化 $p_c$，如3.2节所述。尽管用户可以并且应该选择自己的UNL，但此默认节点列表可确保即使是天真的用户也将以极高的概率参加达成正确性和共识性的共识过程。
  • 还采用了网络拆分检测算法来避免在网络中分叉。虽然共识算法可以证明最后关闭的分类账上的交易是正确的，但它并不排除存在多个以上最后关闭的分类账的可能性为了尝试确定是否发生了这种拆分，每个节点会监视其UNL的活动成员的大小。如果该大小突然降至预设阈值以下，则可能发生了拆分。为了防止在UNL的很大一部分具有临时延迟的情况下出现误报，允许节点发布”部分验证’’，其中节点不处理或投票交易，但声明仍在参与共识过程，而不是针对断开的子网的不同共识过程。
  • 虽然可能仅在一轮共识中应用RPCA，但可以通过多轮获取效用，每轮以最小的协议百分比递增，在最后一轮需求达到80％之前。如果几个这样的节点正在网络的交易速率中造成瓶颈，这些节点将能够在较低的需求回合中最初保持跟上，但是会落在后面并随着阈值的增加而被识别。在达成一轮共识的情况下，可能只有极少数交易通过80％阈值，甚至慢的节点也能跟上，从而降低了整个网络的交易速率。

Simulation Code

他提供的仿真代码演示了一轮RPCA，具有可参数化的功能（网络中的节点数，恶意节点数，消息的延迟等）。模拟器始于完全不同的意见（网络中一半的节点最初建议“是”，而另一半则建议“否”），然后进行共识过程，并在每个阶段显示网络中的“是/否”投票数，以作为节点调整其投票的依据。提案以其UNL成员的提案为基础。一旦达到80％阈值，就可以达成共识。我们鼓励读者使用“ Sim.cpp”开头定义的常数的不同值进行实验，以熟悉不同条件下的共识过程。

Discussion

我们已经描述了RPCA，它满足了我们上面概述的正确性，协议和实用性条件，结果是Ripple协议能够在几秒钟内处理安全可靠的交易：时间长度这些交易在第3节中已被证明是安全的，尽管这在文献中不是异步拜占庭共识中最强大的，但可以实现网络成员资格的快速融合和灵活性。这些品质使Ripple Network可以充当快速且低成本的全球支付网络，并具有众所周知的安全性和可靠性。

虽然我们已经证明，只要满足方程式1和3中所述的界限，Ripple协议就可以证明是安全的，但值得注意的是，这些界限是最大的，实际上，在不太严格的条件下，网络可能是安全的。但是，同样重要的是要认识到，满足这些限制并不是RPCA本身固有的，而是需要管理所有用户的UNL。提供给所有用户的默认UNL已经足够了，但是用户应该对它进行更改吗？ UNL，必须在了解上述限制的情况下完成。另外，需要对全局网络结构进行某种监视，以确保满足边界不等式3，并且始终会满足协议。

我们认为RPCA对于分布式支付系统而言是重要的一步，因为低延迟允许许多其他类型的金融交易，而这些交易以前是用其他更高延迟的共识方法很难实现甚至无法实现的。