最近公司做共识机制改造，经过一番研究，决定采用gosig共识算法，过程虽然艰辛但是收获满满，这里记录一下。
感谢算法作者李沛伦先生的帮助。
Gosig共识算法论文 https://arxiv.org/abs/1802.01315
Gosig共识算法，它是一种可扩展的基于拜占庭的共识算法，这个算法经过数学逻辑验证，改进了BFT共识协议，可以使同时参与区块生产的节点达上万个。在带宽为 2Mbps-30Mbps 条件下进行测试，主网速度大于 4000tps，高于EOS测试1000tps，此共识算法由清华大学研究分布式系统关于区块链共识于2018年2月5日发表。
目前，已经有公链宣布其TPS理论值最高可以达到40万+。据介绍，其采用了Gosig共识算法，会使TPS随着带宽的增加而提高。至于安全性，Gosig共识算法下，区块链每轮出块会根据随机算法选出多个潜在出块者，计算出块需要私钥，别人不知道私钥，无法进行攻击。当潜在出块者完成出块计算，区块就完成了网络上传，这时候攻击也无济于事。
Gosig的优势
共识是分布式计算理论中的一个经典问题。一种解决方案是BFT协议，通常是PBFT。比特币共识采用POW，这是另一种方法。PBFT和POW都可以在不信任的分布式网络环境中达成共识。主要区别在于BFT协议是确定性共识算法，无需等待，但是无法有效地增加节点的参与。后者依赖于几个（6）块的确认耗时。
这两者在效率上有很大差异。 BFT协议有高效率和低延迟，但是POW在任何时候支持注册和退出节点。Gosig对传统的BFT算法进行了革命性的改进。基于PBFT，Gosig可以支持数万个节点，可以随时注册和退出。Gosig也具有从BFT继承而来的正确性，完整性，安全性。该算法利用了潜在出块者投票机制。它利用密码学原理来避免浪费算力。聚合签名的使用有效地减少了来自节点的投票签名的大小，从而减少了带宽的使用。在最后它使用2轮信息交换，类似于PBFT Prepare / Commit，并获得最后确认所有节点中的一个块。除了足够的安全性，它显著提高了BFT共识表现。
Gosig协议概述
Payers
玩家集合。每一个参与到协议中的玩家，都知道其他玩家的公钥。公钥是用于接收从客户端提交的交易和和所有玩家当中的Gossip交易。诚实的玩家负责验证交易的有效性和块的有效性。玩家会丢掉无效的交易和区块，并且把发送者列入黑名单。
Rounds and stages
Gosig是一个部分同步的协议。我们将Gosig的执行设定为一个固定时间长度的循环（默认30秒一轮）。每一轮包含选“选举领导”步骤（没有交流）和两个固定长度的后续阶段。
因此，所有玩家通过本地时钟可以知道当前的轮次号和场次（因为30秒一轮，那么时间是2分钟的话，则本轮轮次号为120/30-1 = 第3轮）。
P(B)表示准备消息prepare message（P message）
PR(B)表示提议消息propose message（PR message）
TC(B)表示意向消息tentatively-commit message (TC message)
Figure(图表)1，展示了一个典型的轮次的概括。首先，在每一轮的开始，一些玩家通过“密码学分类算法（The Cryptographic sortation algorithm）”隐秘地意识到自己是此轮的“潜在领导者”。因此，攻击者不可能够通过猜测的方式定位“领导者”。
在第I阶段，被选中的“潜在领导者”会打包一个没有冲突且没有被提交的交易到一个区块提议（a block proposal）中（注意，这只是一个提议区块），然后用gossip（翻译为流言蜚语，大概就是糊弄地传播的意思）来传播它，这个行为就像一个后续的正常节点一样。注意到，一个“潜在领导者”充分履行了他的领导者指责后，他的身份只能通过其他人（包括攻击者）。
在第II阶段，目标是对一些本轮投票得出的“提议区块”达成共识。如何投票呢？一个玩家的通过把他对某一个块的数字签名添加到一个准备消息（P message）中并发这个消息，来对这个块进行投票。一个诚实的玩家每一轮只对单个提议区块进行投票。至少接收到超过2f+1个来自于P消息的区块签名，玩家开始发送意向消息（TC message: tentatively-commit message）。他最终会在收到2f+1个tc消息后提交区块到他的区块链副本中。
以上过程仅仅描述了正常状态下的协议，下一章节中，我们介绍gosig如何处理故障的详细信息。
Gosig协议详解
我们正式的描述一下Gosig协议。整篇论文，我们采用下面符号：
使用下标来表示谁签署消息（这是一个可以被多个玩家集体签署的消息）
使用上标来表示该消息是在第几轮签发
例如：Prx 表示一个玩家集合里的x玩家，在第r轮签署的消息P
为了简略起见，我们使用Mri 来表示 Mr{i}
我们还使用一些简略的表达方式去描述一些行为：
pi在B区块中发送一个消息P(prepare message 准备消息)，我们记做：piPsB
pi在B区块中发送一个消息TC(tentatively-commit message 意向提交消息)，我们记做：piTCsB
注意：小写p表示玩家，大写P表是消息
1.玩家的本地状态
在Gosig算法中，我们将每一位玩家描述为一个有限状态机。每一个玩家维持一个本地状态，并根据他的状态和外部事件（接受某一消息或被选为leader）来决定他的下一个动作。
本地状态，使用s来表示，pi的状态则用si来表示
一个本地状态由4个元素组成，我们记做：
si = <Broot, hroot, Btc, F>
这些元素包含两种类别的信息，前面两个值是关于他在自己的区块链副本中最后一次提交的区块。Broot是区块本身，hroot是Broot的高度值。
Si的剩余两个值表示玩家打算在高度值为hroot+1时添加到他的区块链中的一个待处理区块，我们用Btc来表示。如果pi有TC消息的区块Btc，则Btc不为空。否则，Btc是一个空值ε。最后一个变量F是代表了区块Btc的时效性。
除了出现在状态机集合的元素外，pi还隐含地包含两个变量Croot和Ctc，Croot是证明Broot有效性的承诺书，Ctc是Btc的提议证明书，稍后我们再看他们的定义。为了简便起见，我们不明确地把Croot和Ctc放在Si的元素中。
当Gosig开始运行时，一个玩家的本地状态初始值为：Si=<Bε, 0, ε, 0>
2.第一步骤：领导选举
领导选举是每一轮的第一步骤。这一步的目的是秘密和随机地挑选出有资格提出下一个区块提议的“潜在领导者”。这其中最大的挑战是保持选举结果（就是潜在领导者是谁）的不可预见性，直到“潜在领导者”发出提议消息（PR message）。不然的话，攻击者事先攻击领导者，从而破坏系统的活性。
密码学分类算法，我们使用一个简化版的Algorand的密码学分类机制来选择一个“潜在领导者”集合。类似的，我们使用Qh来实施密码图分类，在Gosig中，Qh递归定义成：
Qh = H(SIGlh(Qh-1)) (h > 0)
h表示已提交区块的高度值。H表示hash函数，lh定义为提出了提议区块B的领导者（也就是B区块提议证书的签署人），SIGi(M)是用pi私钥签名的消息M的数字签名。
基于Qh，我们把pi在第r轮的领导积分记做Lr(i) = H(SIGi(r, Qh))。H表示在第r轮最后提交区块时的高度值。当h为0时，Q0表示所有玩家共享的随机数。
在每一轮的开始，每一个玩家pi计算的他的积分Lr(i)，如果积分小于领导能力参数q，则他便是这一轮的“潜在领导者”。潜在领导者可以用她的签名SIGi(r,Qh)向其他玩家证明他是领导者。我们把r轮的领导者证明用lCri来表示。以上过程，玩家之间是没有交流的。
密码学分类算法有两个很好的属性：
1） pi使用自己的私钥来生成的签名是无法被其他人伪造的
2） 如果H()哈希函数足够随机的话，那么潜在领导者的选举也是足够随机的
因此，攻击者没有办法去知道谁被选中，也无法剥夺任何节点成为领导者的机会。
选择出一个正确的q(领导能力参数)参数是非常重要的。
如果q太小，某一些轮次没法选举出领导者从而导致流程失败。
如果q太大，可能会有过多的人竞争当选“潜在领导者”，浪费资源去解决冲突。
类似Algorand，我们设置q = 7/N，N表示玩家的总数。这样的q值足够大，足以把“没有领导的轮次”可能性降到低于0.1%
当然了，一个异常的节点可能仍然成为“潜在领导者”，在这种情况下，可能造成的最大的伤害是在不影响正常性的情况下终止本轮次。
3.潜在领导者提议区块
当一个pi意识到自己是一个潜在领导者时，她需要决定提议哪个区块和产生一个提议消息（PR message）.
如果有pi的当前本地状态为 si = <Broot, hroot, Btc, F>(Btc可能为空值ε)，则他得先收集候选区块名单以便提出提议区块。如果pi发现他的Btc不为空，则这个Btc区块时一个不错的可以再次提议的候选区块，他的高度值与Btc相同。或者，她也可以在高度值为（hroot+1）构造一个新的区块来扩展她的链。
以下程序决定了她将提议哪个区块。
为了确保提议的有效性，潜在领导者需要在高度值为h时为已提议区块B提供一个有效的证明c。除了作为证明区块的有效性之外，证明c还决定了提案回合rp(B)的提议区块（更确切地说，提案回合是一个提议的属性，他是在下一段确定的，而不是一个区块，我们为了简便，使用rp(B)来表示）。
提案证明c是否有效，仅且仅有在匹配到以下两种情况的一种时有效：
我们还指出在每一种情况下怎样计算提议回合。
情况1：c = TCir’(Br’,h)(r’<r) ，当B和h是确切的提议区块和他的高度值，这种情况下，rp(B) = r’
情况2：c = TCr’x(B’r’, h-1)(r’<r)，当x包含至少2f+1不同的玩家，这种情况，rp(B)=r’+1
最后，潜在领导者pi以PRri (B∗, h, c, lc)的形式组装提议消息（PR message），其中包含：1) 提议的区块B ，2) B 的高度h，3) 提议证明 4) 领导证明。Pi使用它的私钥来签署消息，每个人可以通过检查它包含的区块，签名和证名，很轻松地验证出提议消息的有效性。
4.第一阶段：提议区块的传播
在领导选举步骤之后，Gosig进入阶段1：传播提议区块。
这一阶段的目标是尽可能多地向诚实的玩家传播所有潜在领导人发出的提议区块。
我们以同一组玩家的形式，在应用层上使用著名的gossip协议传播消息覆盖网络。在每一跳转中，一个玩家以m速随机地选出的玩家发送/转发消息。参数m为扇出和确定消息的传播速度。
潜在领导者初始化他的PR message的gossip。每一个诚实的玩家，当收到一个PR message首先要检查它的有效性，然后转发所有有效的PR message。需要注意的是，在同一轮次中，可能有超过一个有效提议区块，要么是因为有多个潜在领导者，要么就是有恶意的领导者提议了多个有效区块。玩家们在本轮次中，将转发所有有效区块并把解决冲突留在Stage II。
在Stage I的最后（一个固定的时间间隔T1之后），假设一起都顺利的话，在一个轮次中，我们期望大多数玩家能看到所有的提议区块。尽管如此，Stage II可以处理所有复杂的情况。
5.第二阶段：收集签名
Stage II的目标是传播得到玩家投票的建议区块的签名消息，希望诚实的玩家可以提交一个简单而有效的块。与Stage I一样，我们使用Gossip协议去传播所有消息。
Message Types 消息类型
在本阶段（Stage II）有两种复杂难懂的消息类型。玩家可以通过附加自己的签名来集体地对一个消息进行签名。我们说一个消息MrX，如果X包含至少k个不同的玩家签名，则这个消息是ksigned的。
P Message. 准备消息
一个准备消息(P message)对一个区块进行数字签名。特别是，Pri(Br,h)意为玩家pi把它的选票投给了他在第r轮高度为h时提议的投票区块，简单地，我们说pi 准备或者”P”sBr
TC Message. 意向消息（TC message）签署一个(2f+1)-signed P message的证明。特别是，TCri(Br, h)表示至少2f+1个玩家在r轮的h高度已经Ped了区块Br，简单地，我们说pi 意向提交或者”TC”sBr
Stage II protocol
算法1在Stage II阶段大概描述出诚实玩家pi的预期行为。我们通过算法1开始列出的本地状态，把每一轮的pi建模成一个限定的状态机。这种表现行为基于当前的本地状态和传入的信息。
第1行到第7行描述的是初始化程序，这其中，pi检查他所有在Stage I收到的提议区块（通过调用算法2函数DecideMsg得到）。如果pi在Stage I接收到一个有效的提议，她需要决定准备哪一个区块（算法2的DecidePMsg函数）。通常情况下，pi在提议回合更倾向于一个更大的区块，因为较大的区块表明是更近期提出的（2.14到2.20行）。最后，pi更确切为高度h选择一个区块B，和Ps（Ps就是发送一个P message的行为）它。
在初始化后，pi的状态机开始去处理来源消息。算法1的第8到第9行描述了三种不同的小型类型的处理程序。Pi只签名她已经Ped过的区块消息（第1.9行和1.21行），他可以在收到至少2f+1个来自于关于B区块的P message的签名后，只能TC一个区块B，而且他也可以在收到至少2f+1个来自于关于B区块的TC message的签名后(第1.13行和第1.25行)，只能提交一个区块B。这些规则都确保了Gosig的安全性
6.减少签名大小
Gosig协议要求签名来自于超过2/3的玩家。为了降低签名存储和传播的开销，我们采用技术【标注7，6】把那些签名（就是来自于2/3玩家的签名）整合成一种压缩的多签名的形式。
一个玩家pi的加密签名需要一个哈希函数H，一个制造者G，一个私钥Xi和一个公钥Vi = GXi。一个玩家持有私钥xi，可以通过公式：Si=H(M)Xi签名一个消息M，然后其他人可以验证这个签名，通过使用一个双线的map e，检查e(G,Si)是否等于e(Vi, H(M))。为了跟踪我们接收到哪个签名，我们在签名后面附加一个大小为N的整型数组n，并且通过签署消息M，玩家计算Si = H(M)xi，和递增数组nsi的第i位元素，这种组合是聚集签名，我们通过signi(M) = (Si, nsi)来表示这个过程。
聚合签名的一个很重要的特性是，我们可以吧一个新的签名放到一个任意的序列中，从而规避Byzcoin面临的自适应选择攻击玩家的风险。聚合签名只是简单地乘以BLS签名并加入到数组n中。因此聚合签名（aka 多重签名）是S = H(M) ∑i xi ·nS[i]。我们用aggregate(S1, S2, …) = (S, ns1)来表示这一个过程。让(S1, ns1)和(S2,ns2)为两个多重签名，我们可以通过计算aggregate(S1,S2) = (S1*S2, ns1+ns2)来组合他们。数组n用于跟踪消息是由谁签名的。每个人都可以通过检查是否e(G,S) = e(∏iVinS[i] ,H(M))来对多重签名进行验证。
【标注40, 6】指出，同一消息的聚合签名很容易遭受chosen-public-key攻击。如果参与者可以证明他们拥有已公布的公钥的私钥，这种攻击是可以规避的，要么强制信任第三方，要么通过一个零知识证明的自举过程【标注40】。我们选择这种方法是因为在PKI的驱使下是可以接受的。
【标注6】另一种方法是计算一个H(M+Vi)代替H(M)，每个玩家签署不同的消息。由于所有人都知道彼此的公钥，因而在不增加数据大小的情况下，结果仍然是可以进行验证的。这个方法没有涉及第三方信任机构或者在线引导过程，但是当对于同一个消息，它强制算法去计算双线映射N次，而不是一次。这样会造成校验时间慢100倍，因此，只能在整个系统的玩家数量小于200个时才被采用。
签名的聚合过程显著地减少了内存的使用。虽然多重签名确实具有O(N)渐进大小，大部分情况下，一个4字节的整型对于ns中任何一个元素都足够了。如果有 1,000 名玩家使 用 2048 位签名，那么则需要 256 KB 来存储这些签名，但是 通过聚合的方式，它只需要 4256 个字节，是原始大小的 1/60。 随着系统规模的扩大，优化效率也更高。 对于签名者数量较 少的情况，该阵列是松散的，因此容易压缩。