In the midst of chaos

How do you find peace? ~Joyce DiDonato

如果Byzantine nodes的数量f >= n/3，Byzantine broadcast problem无解。

与Dolev-Strong Protocol的结论冲突，是因为二者assumptions不同。

Intuition

ref https://photos.app.goo.gl/UuBusKQtZoenB4xM8

《货币未来：从金本位到区块链》 赛费迪安·阿莫斯

增加供给难度很高的货币被称作硬通货，增加供给难度不那么高的货币被称为软通货。

如果人们选择使用低存量-增量比的商品储存财富，该商品的供给就会在这之后急剧增加，稀释储存者的财富。这样的商品若被选为价值存储的工具，不大可能实现保值的目的。一种商品的存量-增量比越高，就越可能穿越时间保持自身的价值，因此在时间上的适销性也就越好。

“软通货陷阱”：任何物品，一旦被用作价值存储的载体，都会带来供给的增加；任何供给可以轻易大量增加的物品，一旦被选择成为价值存储的载体，都会毁灭存储者的财富。从这一陷阱可以推知，任何成功承担货币角色的物品，必然会有一些自然或人为的限制，限制其流入市场的增量，以保证其保值能力。因此，某种物品要承担货币角色，它的生产成本必须很高，否则生产者赚快钱的诱惑将摧毁储蓄者的财富，人们在这种货币环境中，储蓄的动机也会被摧毁殆尽。

TL:DR: no assumption

但，only useful if f < n/2 in SMR context

ref https://youtu.be/ay023xOPXqE

Validity

由于签名不可被复制 (ideal signature assumption) 只有honest sender发出的消息在传播，被echo最终output

Agreement

如果convinced at f+1说明是最后一个被convinced，至少一个honest node在f+1之前签名且有充足时间通知其他honest nodes

一种Byzantine问题的通用解决方案，但实际不常用，因为依赖synchronous model以及慢

当honest non-senders识别出sender发送不一致的消息，就会认定这是个Byzantine sender并一致忽略

节点如何被convince？ref https://photos.app.goo.gl/6C9vRFcAQEDWuuq99

最后protocol be like https://photos.app.goo.gl/9G8wiXqVEv3e7xgw7

  • 每增加一个faulty节点，就增加一轮交叉验证，一共f+1轮
  • 如果一个节点被convince超过一个v，则认为是Byzantine sender

f = 2, counterexample

doesn't satisfy agreement

ref https://photos.app.goo.gl/95oDxCQgkoGpoW4N8

solution: dolve-strong protocol

f = 1 即只有一个Byzantine节点

  • t=0, sender发送v*并签名
  • t=1, 所有节点接收到v*并签名，同时echo至其他节点
  • t=2, 每个节点根据majority vote决定output

假设n>=4，honest non-sender接收到

  • v* from the honest sender
  • v* echo from n-3 other honest non-senders
  • in total n-2 votes for v*
  • n-2 > 1 byzantine node
  • 满足validity，即honest sender情况下可以正确输出

如果是byzantine sender，意味着non-sender都是honest，t-1同样echo，t-2获得相同votes，输出一致，满足agreement

ref https://www.youtube.com/watch?v=fJ5gCVWfCiQ

基于BB subroutine为SMR设计的protocol可同时满足consistency和liveness。

  1. rotating leaders, round-robin
  2. 运行BB protocol, sender = current leader, v* = 交易历史 ref https://write.as/xytang/byzantine-broadcast-problem-and-smr
  3. 每个节点将交易历史v1存入本地

Why correct, i.e. 同时满足consistency和liveness？

  • BB agreement –> consistency 每一步所有honest存入本地的交易历史都是相同的
  • BB validity –> liveness 所有honest nodes都会将交易历史存入本地

在存在Byzantine nodes的情况下，如何设计一个同时满足consistency和liveness的协议？ref https://write.as/xytang/byzantine-nodes-and-smr

A plugin to rotating leader idea

Idea

Stick with rotating leader approach.

Subroutine

  • 一个sender，known to all up front
  • 这个sender唯一知晓一个input v*

Goal

  • Termination: 每一个honest node最终都会对v*有一个猜测v1并停下
  • Agreement: 所有的honest nodes选择同一个v1
  • Validity: 如果sender是honest node，v1 = v*

Notes

  • 不对Byzantine node有任何假设
  • 三个要求，满足任意两个是容易的：1+2 = 永远使用同一个v；1+3 = just trust the sender is honest；2+3 =

ref https://www.youtube.com/watch?v=fJ5gCVWfCiQ

Honesty is not about intention but about behaviour. 对于一个节点，即便它没有任何不好的意图，仍然会因为外部因素，例如网络问题，产生deviation并成为一个faulty node。

Faulty类型

  1. Crash. 在rotating leader的情况下，如果crash的节点是leader节点，会丢失交易信息，满足consistency但不满足liveness
  2. Omission. 选择性的忽略消息，满足liveness但不满足consistency
  3. Byzantine. No assumption. Behave in inconsistent way.

更新SMR问题第四个假设 ref https://write.as/xytang/jie-jue-smrwen-ti-de-si-ge-jia-she

  • Old: all nodes are honest
  • New: some nodes are honest

引入一个新变量f，表示最大faulty nodes数量；一共n个节点，n-f个honest nodes。这里的tricky之处在于，哪f个节点faulty是不知道的。