1. Home
  2. Docs
  3. 超块链共识数据结构和算法简析
  4. Buddy算法分析

Buddy算法分析

安全性 Safety

1.算法只能根据输入选出一个唯一的结果,不存在同时选出多个结果的可能。(无加密的情
况下)
Buddy 共识要求结对双方达成一致来选出结果,不允许结对成功后各自保留不同结果。
迭代结对扩展时遵循一致性原则,不能推翻结对双方已选定过的结果。
2.只有在结果被选出后节点才能直到结果被确认。
只有在 buddy 共识双方代表节点都接受的情况下结果才被选定。其他节点只能被动接受结
果,不能对结果的选择产生影响。

生命力 Liveness

1.提案结果最终能够被选出。
2.选出的结果最终能被节点收到并信任。
Buddy 共识要求两个代表节点对选择结果达成一致,其他节点被动接收选择的结果。不会
出现通信延迟或丢失产生 live lock 导致选择摆动。
网络连接不失效的情况下,迭代结对过程能保证每次结对选出的结果能够可信的送达所有
节点。

Buddy 共识在经典失效模型中的表现

拜占庭失效 Byzantine Failure

拜占庭失效是指未采用密钥技术的情况下,2M+1 个节点相互通信,出现恶意节点导致信
息不一致而无法监测出的问题。
Buddy 共识结对过程中只有两个节点参与,不存在拜占庭失效问题。
迭代结对过程中代表节点和其他节点的数据同步存在拜占庭失效问题。
Buddy 共识容错率
参与 Buddy 共识的所有节点间保持全连接的情况下,随着节点的增多,最差情况下 33%的
节点为恶意节点 buddy 共识仍能继续运行,最好情况下 49%节点为恶意节点仍可继续运行。
在局部共识阶段,由于 buddy 共识规则可扩展。共识总体容错率会受应用扩展共识规则限
制。比如,扩展共识为 BFT,则最好情况下,共识总体容错率为 33%允许存在恶意节点。
若为 POW, 则最坏情况下,共识总体容错率为允许 49%的恶意节点。
应对拜占庭失效
在共识脚本中加入非对称加密的数据验证机制。

失效宕机 Fail-Stop

节点失效 Node Failure
共识节点发生失效,结对将不能运行,迭代结对的效率会降低。
网络失效 Network Failure
网络失效一般为消息延迟、丢失或网络分隔(Network Partition),效果类似节点失效。
Buddy 共识结对时只有两个参与节点,现通信延迟/丢失会造成共识效率降低或超时失败,
但不会产生 live lock 导致的选择摆动。
失效如何恢复 Failover
节点通过心跳探测判定邻居节点是否可响应。
结对过程中发生节点无响应超时则结对中止。节点未失效一方寻求其他可结对的节点。
结对迭代过程中代表节点无响应超时则需要重新选举代表节点,选出后结对可继续,其他
节点无响应对结对进程无影响。失效节点恢复后,需要向其他节点索取共识数据副本维护
数据一致性。
特别的,出现网络分隔的情况下,迭代结对进程中如果出现一方所有节点不能连接另一方
任意节点的情况,超时之后共识不能继续,双方代表节点将需要寻找新的 buddy 共识合作
方。

消息通信复杂度

Buddy 结对时需要向所有邻居发送结对请求,并等待响应,2 个节点发送 2n 条结对请求,,
各自获得 1 条对方的确认即可结束结对准备,之后数据传输和接受结对都是常数数量级的
消息交换,所以 Buddy 结对的消息复杂度为 O(n)。
迭代结对时中结对各方选出己方 leader 节点,若双方共有 n 个节点则最少需要发送 n-2 条
消息来选出 leader,在使用 Basic Buddy 相互结对,然后将共识结果通过至少 n-2 条消息
同步到所有节点。这样的过程最多会经历 log2n 次结对后停止。所以迭代结对的消息复杂
度为 O(n·logn)

Buddy 共识的优势

共识效能

共识收敛迅速,n 个节点共识可以在 log2n 次结对后快速对 n 个输入选出 1 个最终结果。
没有 livelock 的选择摆动问题。
Buddy 共识参与的节点越多,共识可处理数据吞吐量越大。

共识规则可扩展

共识规则可随应用发送的请求定制,每次结对都可使用不同规则。数据一致性规则是最低
要求,让结对扩展具备最大可能的算法兼容性。比如可以在结对规则中定制使用 POW,先
满足 POW 规则的多个数据块才能结对。

分片扩容

Buddy 共识本身是天然的分布式系统网络分片算法。
结合可状态分片的数据块结构,比如 UTXO, Buddy 共识可以实现状态分片和交易分片的计
算。
Buddy 共识结合超块链创新的超块和局部链区块可分离的复合结构(也称并行区块链数据结
构),可以提供超块链独有的动态分片能力。

Buddy 共识的局限

单一节点在线无法使用 Buddy 共识。
Buddy 共识中并行计算能力发挥需要靠应用客户端能将数据输入提前划分为可满足并行计
算的数据子集并高效的分发到可参与 Buddy 共识的节点。区块中的应用数据负载也需要满
足并行计算规则的读取和验证。
举例:
以太坊区块结构中多个 trie 数据之间的纠缠的逻辑依赖导致了无法实现并行计算。
比特币 UXTO 的数据结构允许对交易划分为互补子集输入并行计算。
参与共识的节点增多,数据通信量会快速增大,网络带宽会成为限制条件。所幸的是,数
据通信容易优化。长期来看,网络带宽限制也会随着通信技术的升级而消除。

Was this article helpful to you? Yes No