The Ripple Protocol Consensus Algorithm
&
Stellar Consensus Protocol
分享者：Michael
Link to Ripple paper - by Ripple Labs Inc, 2014
Link to Stellar paper - by David Mazières, SDF 2015
瑞波共识算法 RPCA
解决的三个问题
- Correctness: 是否是有效的transaction。
- Agreement: 统一的global truth，防止双花。
- Utility: 高可用性，包括latency，电力消耗，易接入性。
构建步骤
- 每个server选一个UNL（unique node list）
- 每个节点建立candidate set
- 从UNL中，合并candidate set，并在本地进行验证。
- 上一轮pass的transaction，发给UNL节点。
- 拿到80% vote的transaction，放进最终的last-closed ledger中
2个前提
- 任何一个server都可以broadcast交易，但是只需要依赖UNL来做consensus
- 验证结果是time-bound & binary的。
达到共识的定义
- 所有正义节点都在finite时间内作出判决。
- 所有正义节点达成的判决是一致的。
- 最终的判决不论是0还是1，都是有效的共识。
这个算法的BFT是抵御 <20%的非正义节点。
RPCA 证明
证明correctness
如果一个节点非正义的概率是Pc，那么
这个这个公式可视化之后，节点数和Pc之间的关系就是：
当Pc = 15% N = 200时，p* = 97.8%
证明 agreement
系统存在fork的风险，也就是2个小系统，相互无法交换共识信息。
当UNL的size < 0.2*n时，fork是可能发生的。
看下面这两个 cliques（小帮派）的fork情况：
证明 utility
skip
恒星公式机制
Stellar Consensus Protocol 讲述了联邦拜占庭一致性（FBA）算法。我这里会粗略解释。
FBA于传统Byzantine Agreement的区别在于，无需所有节点都被验证，因为FBA中，每个节点自己选择quoram节点对象。
定义
Slice：Q（v）是一个node的slice。
Quoram：法定体。能满足达成一致协议的节点集合。
Tiered Quoram概念
Tiered Quoram就是分级的法定体。
在top tier不止一个qouram。
比如大商业银行是一个quoram，同时worker union和audit组织成为一个quoram。这样大大保证了top tier的可信度。
总结
联邦拜占庭一致性（FBA）无法挖矿，无验证奖励机制。高可用性，每5s出一个区块，同时耗费的算力极低。
这个算法是为分布式交易所，跨货币资产转移而存在的。