DATx系列之二 - 共识机制

DATx是针对当前广告行业的再一次创新运动，致力于建立一个以去中心化为基石，以人工智能为引擎的新型智能广告生态系统。

DATx提供了用户行为档案数据远程存储功能，其核心功能是用户将用户行为档案数据存储在去中心化的网络节点中，之后用户可以在任意地点获取和访问这些数据。用户行为档案主要包括了完整的链条式的用户行为记录，可以让我们模拟出完整的用户画像，知道用户在媒体上个各种浏览、点击、购买背后的商业真相。

把用户行为档案数据存储到一个去中心化的网络中，意味着其他的网络节点——存储节点，将保存用户的数据，而且负责在用户需要访问和广告平台进行大数据分析时，会归还这些数据。当用户成为存储节点后，会获得DATx激励。并且，如果有用户在该存储节点存储数据，该存储节点会获得额外的激励。

我们的DATx用户行为档案的存储技术，建立在区块链技术的基础之上。区块链是一个分布式账本，通过密码学方法让达成一致的双方直接交易，并由代码而不是人来保证交易的安全可靠。区块链中所有的规则事先都通过算法程序的形式表述出来，参与交易的双方不需要知道对方是君子或小人，更不需要第三方进行信任背书，只需要信任共同的算法就可以建立互信。

DTAx网络中，加入DATx生态的任何用户（包括但不限于广告主、渠道、广告受众）都可以成为网络存储节点。用户有权选择他们自己的存储节点，也有权利选择自己是否成为存储节点，但是加入DATx的存储节点必须遵循我们的共识算法。

FLP定理和CAP定理

区块链的伟大之处，就是它的共识机制在去中心化的思想上解决了节点间互相信任的问题。区块链能在众多节点达到一种较为平衡的状态也是因为共识机制。

区块链可以概括为去中心化分布式分类账，但是在账本中，如何对在几乎相同时间内的产生的事物前后排序，这就涉及到区块链网络的共识机制。在区块链中，所谓共识机制，就是在一个时间段内对事物的前后顺序达成共识的一种算法。在DATx生态中，两个存储节点几乎在相同的时间内竞争存储同一份文件，那么，怎么对竞争的存储节点排序，则需要我们的共识机制来解决。

当分布式的思想被提出来时，人们就开始根据FLP定理和CAP定理设计共识算法。

FLP定理

FLP定理即FLP不可能性，它证明了在分布式情景下，无论任何算法，即使是只有一个进程挂掉，对于其他非失败进程，都存在着无法达成一致的可能。

FLP基于如下几点假设：

仅可修改一次

每个进程初始时都记录一个值（0或1）。进程可以接收消息、改动该值、并发送消息，当进程进入decide state时，其值就不再变化。所有非失败进程都进入decided state时，协议成功结束。这里放宽到有一部分进程进入decided state就算协议成功。

异步通信

与同步通信的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序。

通信健壮

只要进程非失败，消息虽会被无限延迟，但最终会被送达；并且消息仅会被送达一次（无重复）。

Fail-Stop模型

进程失败如同宕机，不再处理任何消息。

失败进程数量

最多一个进程失败。

CAP定理

CAP是分布式系统、特别是分布式存储领域中被讨论最多的理论。CAP由Eric Brewer在2000年PODC会议上提出，是Eric Brewer在Inktomi期间研发搜索引擎、分布式web缓存时得出的关于数据一致性(consistency)、服务可用性(availability)、分区容错性(partition-tolerance)的猜想：

It is impossiblefor a web service to provide the three following guarantees: Consistency,Availability and Partition-tolerance.

该猜想在提出两年后被证明成立，成为我们熟知的CAP定理：

数据一致性(Consistency)

如果系统对一个写操作返回成功，那么之后的读请求都必须读到这个新数据；如果返回失败，那么所有读操作都不能读到这个数据，对调用者而言数据具有强一致性。

服务可用性(Availability)

所有读写请求在一定时间内得到响应，可终止、不会一直等待。

分区容错性(Partition-tolerance)

在网络分区的情况下，被分隔的节点仍能正常对外服务。

在某时刻如果满足AP，分隔的节点同时对外服务但不能相互通信，将导致状态不一致，即不能满足C；如果满足CP，网络分区的情况下为达成C，请求只能一直等待，即不满足A；如果要满足CA，在一定时间内要达到节点状态一致，要求不能出现网络分区，则不能满足P。

理想的分布式系统的一致性应该满足如下：

1）可终止性：一致性的结果可在有限时间内完成；

2）共识性：不同节点最终完成决策的结果应该相同；

3）合法性：决策的结果必须是其他进程提出的提案。

但是在实际情况中，可能会存在以下问题：

1）节点处理事务的能力不同，网络节点数据的吞吐量有差异；

2）节点间通讯的信道可能不安全；

3）可能会有作恶节点出现；

4）当异步处理能力达到高度一致时，系统的可扩展性就会变差（容不下新节点的加入）。

所以基于区块链设计的各种共识机制都可以看作牺牲某一部分代价来换取多适合的一致性。

DATx前期分别对几种主流的共识机制进行了探索。

POW共识机制

POW：Proof-Of-Work，工作量证明

在比特币等货币型区块链中，让各节点达成一致性的共识机制为工作量证明（Proof-Of-Work，POW），也是我们说的挖矿。通俗地讲，POW机理就是“通过工作以获得指定成果，用成果来证明曾经付出的努力”。

POW共识机制依赖机器进行数学运算来获取记账权，资源消耗相对较高、可监管性弱，同时每次达成共识需要全网共同参与运算，性能效率比较低，容错性方面允许全网50%节点出错。

POW的核心要义为：算力越大，挖到块的概率越大，维护区块链安全的权重越大。相对其他共识机制而言，POW逻辑简单，容易实现，容错达50%，其安全有严格的数学论证。

POW优点：完全去中心化，节点自由进出；

POW缺点：目前比特币已经吸引全球大部分的算力，其它再用Pow共识机制的区块链应用很难获得相同的算力来保障自身的安全；挖矿造成大量的资源浪费；共识达成的周期较长。因此，DATx决定不采用这种共识机制。

POS共识机制

POS：Proof of Stake，权益证明

Proof of Stake由QuantumMechanic在2011年首先提出。

POS算法具体流程为：存在一个持币人的集合，他们把手中的代币放入POS机制中，这样他们就变成验证者。假设在区块链最前面一个区块（区块链中最新的块），这时POS算法在这些验证者中随机选取一个（选择验证者的权重依据他们投入的代币多少，比如一个投入押金为10000代币的验证者被选择的概率是一个投入1000代币验证者的10倍），给他们权利产生下一个区块。如果在一定时间内，这个验证者没有产生一个区块，则选出第二个验证者来代替来产生新区块。与POW一样，以最长的链为准。

POS优点：不再需要为了安全产生区块而大量消耗电能。

由于不再需要大量能耗，通过发行新币以激励参与者继续参与网络的压力会下降。理论上负总发行量甚至成为可能，由于一部分交易费被烧掉，因此货币供应随着时间减少。随着规模经济的消失，中心化所带来的风险减小。

POS缺点：还是需要挖矿，本质上没有解决商业应用的痛点；所有的确认都只是一个概率上的表达，而不是一个确定性的事情，理论上有可能存在其他攻击影响。

并且在权益证明机制POS中，token的余额越多的人获得公示信息的概率越高，公示人会得到一定的token作为奖励，如此持有token多的人会越来越多，少的人越来越少。

瑞波共识机制

Ripple Consensus

瑞波共识算法，使一组节点能够基于特殊节点列表达成共识。要接纳一个新成员，必须由51%的初始特殊节点投票通过。共识遵循这核心成员的51%权力，外部人员则没有影响力。由于初始特殊节点由“中心化”开始，它将一直是“中心化的”，而如果它开始腐化，股东们什么也做不了。与比特币一样，瑞波系统将股东们与其投票权隔开，因此比其他系统更中心化。

Pool验证池

基于传统的分布式一致性技术，加上数据验证机制；是目前行业链大范围在使用的共识机制。

优点：不需要代币也可以工作，在成熟的分布式一致性算法（Pasox、Raft）基础上，实现秒级共识验证。

缺点：去中心化程度不如bictoin；更适合多方参与的多中心商业模式。

PoET共识机制

PoET：Proof of Elapsed Time，消逝时间量证明

它是由英特尔构建在可信执行环境的一种彩票协议。核心是用intel支持SGX技术的CPU硬件，在受控安全环境（TEE）下随机产生一些延时，同时CPU从硬件级别证明延时的可信性，类似于彩票算法，谁的延时最低，谁将获取记账权。这样，增加记账权的唯一方法就是多增加CPU的数量，具备了当初中本聪设想的一个CPU一票的可能，同时增加的CPU会提升整个系统的资源，变相实现了记账权与提供资源之间的正比例关系。

QV共识机制

QV：Quorum Voting，仲裁投票

它采用了瑞波和恒星的共识协议，用来解决需立即交易定局的需求。

DPOS共识机制

DPOS：Delegate Proof of Stake，股份授权证明

BitShares社区首先提出了DPOS机制。

与POS的主要区别在于节点选举若干代理人，由代理人验证和记账。其合规监管、性能、资源消耗和容错性与POS相似。类似于董事会投票，持币者投出一定数量的节点，代理他们进行验证和记账。

DPOS的工作原理为：

去中心化表示每个股东按其持股比例拥有影响力，51%股东投票的结果将是不可逆且有约束力的。其挑战是通过及时而高效的方法达到51%批准。为达到这个目标，每个股东可以将其投票权授予一名代表，获票数最多的前100位代表按既定时间表轮流产生区块。每名代表分配到一个时间段来生产区块。所有的代表将收到等同于一个平均水平的区块所含交易费的10%作为报酬。如果一个平均水平的区块含有100股作为交易费，一名代表将获得1股作为报酬。

网络延迟有可能使某些代表没能及时广播他们的区块，而这将导致区块链分叉。然而，这不太可能发生，因为制造区块的代表可以与制造前后区块的代表建立直接连接。建立这种与你之后的代表(也许也包括其后的那名代表)的直接连接是为了确保你能得到报酬。

该模式可以每30秒产生一个新区块，并且在正常的网络条件下区块链分叉的可能性极其小，即使发生也可以在几分钟内得到解决。

DATx共识机制

鉴于DATx需要高并发、低延迟处理交易的需求，我们采用股份授权证明共识机制，即DPOS共识机制。

DATx中，DPOS共识机制被分为了两部分，其一是选举一组区块生产者，其二是调度生产。选举流程要尽量保证，权益所有者最终能控制整个网络，因为一旦网络出现问题，权益所有者损失的将会最大。

1 选举区块生产者

1）成为代表

成为一名代表，用户必须在网络上注册属于他自己的公钥，然后其会被分配一个32位的特有标识符，该标识符会被每笔交易数据的“头部”引用。

2）授权选票

每个钱包有一个参数设置窗口，在该窗口里用户可以选择一个或更多的代表，并将其分级。一经设定，用户所做的每笔交易将把选票从“输入代表”转移至“输出代表”。一般情况下，用户不会创建以投票为目的的交易，因为那将耗费他们一笔交易费。但在紧急情况下，某些用户可能觉得通过支付费用这一更积极的方式来改变他们的投票是值得的。

3）保持代表诚实

每个钱包将显示一个状态指示器，让用户知道他们的代表表现如何。如果他们错过了太多的区块，那么系统将会推荐用户去换一个新的代表。如果任何代表被发现签发了一个无效的区块，那么所有标准钱包将在每个钱包进行更多交易前要求选出一个新代表。

4）抵抗攻击

在抵抗攻击上，因为前100名代表所获得的权力权重是相同的，每名代表都有一份相等的投票权。因此，无法通过获得超过1%的选票而将权力集中到一个单一代表上。因为只有100名代表，可以想象一个攻击者对每名轮到生产区块的代表依次进行拒绝服务攻击。幸运的是，由于事实上每名代表的标识是其公钥而非IP地址，这种特定攻击的威胁很容易被减轻。这将使确定DDOS攻击目标更为困难。而代表之间的潜在直接连接，将使妨碍他们生产区块变得更为困难。

2 调度生产

我们还需要重点知道的是，当区块生产者选好后，如何达成共识。为了说明DPOS共识机制，我们先假设只有三个区块生产者，A，B，C。当然在实际场景中，会有更多的区块生产者。

因为共识需要2/3 +1个成员来应对所有场景，所以在这里，我们假设区块生产者C是那个破局者。另外，如POW（工作量证明）共识一样，基本规则是我们总是应该选择最长的区块链。任何时候，一个诚实的节点看到另一个合法的且更长的区块链，它应该总是切换到那个更长的分支上。

1）正常情况

在正常情况下，区块生产者轮流每3秒产生一个区块。假设没有生产者错过自己顺序，那么他们生产的链条势必是最长的链条。另外，在区块生产者在非指定时间生产区块会被认为是无效的。

注意，实际情况中生产者的顺序是随机的。

在后面所有的例子中，我们展示的是一个轮流选择区块生产者的方案。但在实际中，生产者集合是随机的，每N个块就将随机一次，其中N是生产者的数量。这种随机保证区块生产者B不能总是忽略区块生产者A，打破多个同样的分支等待。

2）少数群体的分叉

可以允许最多1/3的节点是恶意节点或者是故障节点，从而导致出现分叉。这里我们假设A、B、C中C是恶意节点或者恶意节点。在这种情形下，少数分支（下图下方的链）将只能在9秒内生产1个块，而大多数分支（下图上方的链）由于数量多一倍，将预期能在9秒内生产2个块。所以，诚实的2/3的大多数可以比小的那一部分创建一个更长的链条。

3）隔离环境下的重复块生产

少数群体可能尝试创建一个无限数量的分叉，如下图中，节点C尝试创建了多个分叉（C0，C1，C2，C3）。但是即使节点C创建了很多分叉，分叉的链的长度比主链都要短，而且，分叉链的成长速度比主链要慢。

4）网络碎片

网络非常有可能碎片化，没有哪一个链上的区块生产者占到了所有区块生产者中的大多数。在此情景下，最长的那个链将变成最大的一个少数群体。当网络连接恢复正常后，相对较小的那些群体将自然的切换到最长的链，从而将恢复明确的共识。

还有一种非常可能的情况是，三个分支中，最大的两个分支一样大。此时，将由相对更小的第三个分支加入网络时来打破僵局。存在奇数个区块生产者，所以僵局一般不会持续很久。在区块生产者的清洗中，会将生产者随机生成顺序，以确保即使两个分支具有相同数量的生产者，分支也将以不同的长度爆发增长，导致一个分支最终接管另一个分支。

5）少数群体重复生产

在这种情景下，少数群体C在自己可以生产的时间节点，同时创建两条或多条的区块链。下一个执行的生产者A，将选择C创建的可选链中的任一条，A选中的这条链将成为最长的链。下图中，节点A选择了上一区块为C的节点。之后，即便节点C再次创建一个节点，下一个节点A也不会选择节点C1，而是选择长链。所以，无论少数恶意节点结点制造多少的链，他们在下一轮中，肯定不会是最长的那个链。

6）最后的不可逆区块

在网络碎片的情况下，多个分叉可能持续较长时间的隔离。长远来看，最长的链将最终受到认可。但观察者需要一种手段来确定某个块是否是在最长链条的一部分（确认共识）。这可以通过2/3 + 1个区块生产者是否对某个块有确认。

下图中，块B被A、C确认了，这意味着2/3 +1都已经确认了。由此我们可以为不可能存在更长的链了，因为2/3的区块链是诚实的。

需要注意的是这个规则与比特币的6个区块确认类似。一些聪明的人可以设计一系列事件，其中两个节点可能会在不同的最后不可逆块上结束。这种极端情况需要一个攻击者，精确控制通信延迟，并需要在几分钟内实施不止一次，而是二次攻击。如果发生这种情况，那么最长链条这一长期规则仍然适用。我们估计这种攻击的可能性足够接近0，经济后果也微不足道，不值得担心。

7）不足法定区块生产者

这种情况下，生产者没有明确达到法定人数，少数人可能继续生产块。在继续生产的区块中，利益相关者可以包含一些改变投票的交易。这些投票会选举一组新的区块生产者，并将区块生产参与度恢复到100%。一旦发生这种情况，少数人链最终会超过其它低于100%参与链。

当这个情况发生时，所有的观察者必须要明白整个网络处于不稳定的状态，直到多于67%参与者出现后才会稳定下来。哪些选择在这种情景下发起交易的，与那些在比特币中接受低于6块就确认交易成功那样，冒着类似的风险。他们必须明白，存在某些情况下，共识最终会以另一个链为准。在实践中，这种情形比在比特币中接受少于3个块就确认更加安全。

8）大多数的区块生产者的腐败

如果大多数区块生产者合谋变得腐败，他们制造无限数量的分支，每一个分支都有多于2/3的大多数的签名。如下图中节点B和节点C合谋，恶意创建无限数量的分支。

在这样的场景中，最后不可逆转块算法退化为最长链算法。此时最长的，获得了最大的群体认证的，将由少数的诚实节点的加入来确定。这样的情形不会持续很久，因为利益相关者会最终投票替换掉这些区块生产者。

交易即权益证明（TaPOS，Transactionsas Proof of Stake）

当用户对一个交易进行签名时，潜在假设是他们知道当前区块链的状态。如果关于最长链的共识发生了变化，那么对应当用户签发交易时所作的潜在假设也失去了基础。

TaPoS，是指所有的交易，包括最近区块的哈希。如果它不存在于区块历史中，那么他就被认为是无效的。任何人在一个孤立的节点上签名交易，交易本身将不会得到承认，而且也不能被移植到主网络上。

这个流程带来的一个副作用是，为网络带来安全，可以抵挡长程攻击，试图生成一个替代链。个人利益相关者每次交易就是对区块链的一个投票。随着时间的推移，所有的块都被所有利益相关者确认，这是一个不能在伪造链中复制的东西。

最后

DATx通过DPOS和并行链的方式解决延迟和数据吞吐量的问题。目前可观的情况下，DPOS（委托权益证明）都是强健的，甚至在面对相当数量区块生产者舞弊的情形时也是安全的。选择块生产者和验证节点质量的算法赋予了DPOS的安全性。运用赞成投票的过程可以确保一个人即使拥有50％的有效投票权也不能独自挑选哪怕一个生产者。DPOS大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。

程式化广告中，一直比较重要的是投放的实时决策、个性化投放需求和大量交易等问题。DATx采用的DPOS共识机制在我们的交易中占据了重要的地位，其在处理比任何其它区块链更多交易的同时持续达成共识，在DATx广告生态中展现出了非凡的一面。