一种拜占庭共识协议-Byzantine Agreement,Made Trivial

前言

周六看了几遍Silvio Micali的论文Byzantine Agreement,Made Trivial, 理解上比以前深刻了一些。今天准备把论文叙述一遍,不会一字一句翻译,基本是自己的理解。文字记录下来理解会更深一点, 也做为接下来和守敬老师讨论的基础。

介绍

拜占庭共识在几十年间已经吸引了众多前辈投入研究, 本论文提供了一种简单可操作的拜占庭共识协议, 容错率大概在33%(1/3), 在可预期的9轮(round)之内全网节点可以达成共识。

  • 容错率: 作恶节点最大所占比例。
  • 作恶节点: 可以装死/发送错误消息的节点。

n>=3t+1>=3

  • n: 全网节点总数。
  • t: 网络中坏节点总数。

后续文中拜占庭共识用 BA代替。


一些定义

论文描述的BA会使用两个工具:

  • 数字签名: 保证点对点消息传递的可靠。
  • 哈希函数: 生成随机位 c(r)。(BBA*中着重解释)

接下来我们要对弈的是这样一个对手(adversary):

  • 对手的能力:

    • 控制全网t个作恶节点(malicious)收集(receive)和发送(send)消息的内容。
    • 在每一轮(round)开始的时候, 可以在全网任意指定t个作恶节点(malicious)。
    • 无法影响诚实节点(honest)。
ps: 如果不太了解BA,可能对receive和send的具体含义不太理解,下面协议描述中会有说明。

BA描述

  • 定义若干变量:

    • 全网节点总数: n
    • 作恶节点总数: t
    • 节点i向其他节点广播的消息: out(i)
    • 节点i初始化值: v(i)
    • v(i),out(i)是V的元素。 V={0,1}
    • n>=3t+1>=3

    我的以为: 原论文中的soundness应该不是概率,是?

  • 定义两条规则:

    • 如果节点i和节点j都是诚实节点, out(i)=out(j)
    • 如果诚实节点i初始化值v(i)=v, 则诚实节点j的out(j)=v

  • 定义几个标示符号:

    • 节点i对字符串x的签名: sig(x)
    • 节点i在第r轮(round)收到来自节点j的消息: m(j)
    • 节点i在第r轮收到值v的个数: #(v)

一种二进制拜占庭共识协议: BBA*

Dolev and Strong[4]第一次提出了容错50%的BA 协议; Katz and Koo[10]接下来也提出了容错50%,且在有限轮数内全网可以到达共识的BA协议。他们的协议很完善但是太过复杂,可操作性比较低。
基于本论文的BBA*, Vinod Vaikuntanathan 和作者一起发现了容错在50%的协议方法, 后续会写出来, 本论文描述的还是容错33%的协议。


本论文基于二进制数值达成共识(0 或 1), 定义b(i)为节点i的初始化二进制数值。

下面是三个演化过程:

1.理想化(借助天空)

  • 节点i广播b(i)到所有节点,包括自己。
  • 一个随机独立的二进制变量 c(r)出现在天空,所有节点可见。
  • 节点i更新自己的b(i)按照如下规则:

    • 如果: #(0)>=2t+1, 节点i将b(i)设置为0.
    • 如果: #(1)>=2t+1, 节点i将b(i)设置为1.
    • 否则设置b(i)为c(r).

    Ps: 诚实节点个数>=2t+1; 诚实节点出现的概率: 2/3.

    下面快速分析三点:

  • 如果在协议执行之前诚实节点对 b 已经达成共识,则执行之后还是共识状态。
  • 如果在协议执行之前诚实节点对 b 没有达成共识,则执行之后共识概率是1/2。
  • 如果所有诚实节点的初始值都是 b, 则他们后续动作仍然会在b上共识。

上述三点不难理解, 对于第二点概率1/2的原因, 我个人认为因为共识数值集合是{0,1}, 所以概率是50%.


2.改进版

//TODO: 未完全领会,稍后补充


3.确定版

接下来抛开天空给我们的帮助,通过规则构造具体的c(r):

确定的随机值(0 或 1)的构造方式:

  • 节点i向外广播 v(i), v(i)是节点i在r轮对随机字符串R的数字签名。
  • 所有节点收到来自其他节点的v(?), 通过哈希函数计算出最小的值, 对所有节点j: H(v(m))<=H(v(j))。 则m是最小的那个节点。
  • 对于节点i, H(v(m))的最低有效位(0 或 1)就是 c(r)了。
  • 问题: 每轮协议执行之后,全网达到共识的概率是 1/3.

    • 概率1/3的原因: 上一节有描述。//TODO
  • 解决办法:

    • 方法1: 执行次数足够多,次数提高总概率。(太浪费,很笨拙)
    • 方法2: 规则改进,拆分为3步循环:

      • 第一步: 强制c(r)为0.
      • 第二步: 强制c(r)为1.
      • 第三步: 正常产生c(r)=lsb(H(v(m))).

详细描述和证明过程如下:


分析和证明过程

过程描述:

  • Step1:

    • 1.1 如果 #(0)>=2t+1,节点i设置: b(i)=0, out(i)=0, 向其他节点广播0*, 退出循环.
    • 1.2 如果 #(1)>=2t+1,节点i设置: b(i)=1.
    • 1.3 否则: 节点i设置: b(i)=0.
  • Step2:

    • 2.1 如果 #(1)>=2t+1,节点i设置: b(i)=1, out(i)=1, 向其他节点广播1*, 退出循环.
    • 3.2 如果 #(0)>=2t+1,节点i设置: b(i)=0.
    • 2.3 否则: 节点i设置: b(i)=1.
  • Step3:

    • 3.1 如果 #(0)>=2t+1,节点i设置: b(i)=0.
    • 3.2 如果 #(1)>=2t+1,节点i设置: b(i)=1.
    • 3.3 否则: 产生c(r)=lsb(H(vm)), 节点i设置: b(i)=c(r), r(i)自增1, 返回Step1循环.

三点证明:

  • A: 如果在Step3执行的开始,没有节点退出循环,全网也没有达成共识;则在Step3结束时有1/3概率全网达成共识.

假设最小节点(lsb(H(v(m))))节点m是诚实节点, 全网通过节点m的签名消息可以唯一确定c(r).
最小节点是诚实节点的概率是: 2/3(这个比较明显,因为n>=3t+1,所以诚实节点数>=2t+1).

对于Step3的三个小步: 3.1, 3.2, 3.3会出现5种情况:

  • 可能情景1: 所有节点满足了3.1.
  • 可能情景2: 所有节点满足了3.2.
  • 可能情景3: 所有节点满足了3.3.
  • 可能情景4: 部分节点满足3.1,其余满足3.3.
  • 可能情景5: 部分节点满足3.2,其余满足3.3.

很显然,不可能出现 部分节点满足3.1,其余满足3.2的情况。

对于情景1~3, 节点在Step3结束时达成共识的概率都为1.
对于情景4和情景5, 着重说明一下:

  • 情景4: 3.3中c(r)=0的概率是1/2(因为只有1或0的可能).
  • 情景5: 3.3中c(r)=1的概率是1/2.

综上, 5种场景在Step3结束时达成共识的概率最小为1/2, 而节点m是诚实节点的概率是2/3,所以Step3结束时有(1/2*2/3=1/3)的概率达成共识。

我的疑问: 和m是否为诚实节点有什么关系呢? lsb(H(v(m)))为0或1对于m是否为诚实节点无关吧? 所以A的概率应该为1/2 ?

----

  • B: 如果在某一步,在b上达成共识,则共识的b在接下来的执行中不会被改变。

假设在某个Step的开始对b达成了共识, 则所有诚实节点(>=2t+1)都会广播这个b, 所以#(b)>=2t+1对所有诚实节点都是成立的, 后续协议执行并不会改变b。

这个比较好理解,不用过多说明。

----

  • C: 如果在某一步,有一个诚实的节点退出循环,则共识会在这步结束时达成。

诚实节点数>=2t+1, 作恶节点数<=t

以Step0为例, 如果某节点满足#(0)>=2t+1而退出了循环则说明至少有 t+1个诚实节点在Step0开始前全网广播了0。
对于其余节点j有两种情况:

  • #<j,1>(0)>=2t+1 (满足了退出循环条件且达成共识)
  • t+1<=#<j,1>(0)<2t+1

//TODO: 未完全领会,后续补充...


二进制BA向任意值BA的转化

参见附录[5]的论文.


最后

论文中两部分没有完全吃透,后续找时间更新:

  • Frequently magic coins的具体用意。
  • If at some step, a honest player i halts, then agreement will hold at the end of the step. 后半段的证明过程。

2017-01-07

上一篇:JS:字符串常用方法整理


下一篇:ASP.NET MVC WEB API必知必会知识点总结