乐趣区

关于区块链:事件驱动的HotStuff协议

jiezi

事件驱动 Hotstuff

    Basic HotStuff 
->  Chained HotStuff         // 流水线进步吞吐   
->  Event-driven HotStuff    // Safety 与 Liveness 解耦, 实现更简洁

事件驱动 hs 将实现分为了两局部, 其中负责 Liveness 性能 (如选举, 超时, 同步 view) 的称为 Pacemaker. 另一部分负责 Safety, 次要通过 Msg 来更新节点状态, 笔者将这部分称为 StateMachine。

Pacemaker

struct Pacemaker{
    qc_high // 所见过最高的、已投票的 QC
    b_leaf  // 叶子节点
}

Pacemaker 的动作:

  • update_qc_high()如果新 qc 比 pm 持有的 qc 更高，那么更新 qc_high 和 b_leaf.
  • on_beat(cmd)，如果本节点是新 leader，通过调用 sm.on_propose()来创立叶子并且将其播送给所有 replica。
  • on_next_sync_view(), 向 leader 发送 NewViewMSG 带上本人的 qc_high
  • on_recv_new_view(), 当 leader 收到 NewView 时, 如果附带的 qc 比本人持有的 qc 更高，就更新 qc_high 和 b_leaf.

StateMachine

sturct StateMachine{
    Vmapper     // node 到它的投票汇合的映射
    vheight     // 最新的, 本人已投票的节点的高度, 等同于 view number
    b_lock      // 锁定的节点
    b_exec      // 最初一个已执行的节点
}

StateMachine 的动作:

  • create_leaf()创立叶子节点
  • update(b*)更新节点 b * 及其父节点 b ”, b’, b. 并且更新 b_lock = b’, 执行 b
  • on_commit(b), 递归执行 b
  • on_recv_proposal(b_new), 如果 b_new.height 比本人的 vheight 要高，而且满足 SAFENODE()谓词, 就签名并且回复。随后更新 b_new 状态
  • on_recv_vote(), 计算门限签名和 qc, 并且调用 pacemaker.update_qc_height()
  • on_propose()，创立叶子并且将其播送，随后返回叶子。

一次无故障的提交流程

  1. 首先下层 app 把新的 cmd 交付给 hotstuff node。
  2. replica 依据某种自定义形式生成 proposal, 也就是 node b_new。
  3. 在 on_recv_new_view() 中, replica 把 node 发送给 leader。
  4. leader.pacemaker 挑选出最高的 node, 调用 on_beat() 将其播送给所有 replica。
  5. replica 受到 NewViewMSG 后会调用 on_recv_proposal(), 如果新 node 的高度更高而且满足SafeNode() 谓词, 那么会返回本人的签名。无论是否承受新 node, on_recv_proposal()都会调用update(b_new)。
  6. leader 通过 on_recv_vote() 来计算门限签名, 调用 pm.update_qc_high() 来更新 qc_high。
  7. replica 期待 b_new 提交。这须要间断三个节点b <- b'<- b'', 如果 b 被提交了, 那么之前的节点也会提交。
  8. b_new 被提交, 执行 cmds。
  9. replica 告知客户端 cmds 已执行。

其余

为何 SAFENODE(b_new)为假也调用 update(b_new)

update(b_new)并没有对 b_new 做任何动作。此时 b_new 处于 Prepare 阶段, 可能是个歹意的 proposal。

但收到到 b_new 节点时, replica 能够晓得, b_new的三个先人 b, b', b'' 的别离进入了 Decide, Commit, PreCommit 阶段, 因而它做如下动作:

  1. 如果 b ’ 比已锁定的 b_lock 要更高(等价于 viewNumebr 更大), 那么锁定 b ’
  2. 如果 b, b', b'' 三者间断, 那么递归提交b 及其之前的节点。

justify.node 与 parent 的区别

联合下面能够看到, 实际上 b, b', b'' 三者可能不间断:


 c1 <- b <- a1 <- a2 <- b'<- b1 <- b2 <- b''
      _________________      __________

// 所谓 ancesty gap, leader 超时导致进入下一个阶段

如上图: b''.justify.node == b', 而 b''.parent == b2.
当on_commit(b'')时, 会顺次提交b1 <- b2 <- b''。

从执行过程来看: 创立新节点时会将 pacemaker.qc_high 作为新节点的 justify, 那么 qc_high 何时更新? 通过以下路径调用 pacemaker.update_qc_high() 更新:

  • leader: on_recv_vote(), 计算出 qc 后得悉 b_new 曾经被承受了, 因而更新本人的。
  • replica: on_recv_proposal() -> update(b_new) -> update_qc_high(b_new.justify)。replica 投给 b_new 了, 天然也就确认了 b_new.justify。

pacemaker.qc_high 与 sm.vheight

这两个变量不是对应的。vheight在节点投票给 b_new 后更新为 b_new.height. 一般来说qc_high.node.height <= vheight

参考资料

  1. hotstuff paper
  2. event-driven hotstuff in go
  3. https://zhuanlan.zhihu.com/p/…
退出移动版