Neohope的网络笔记

一、概述
将区块链的共识算法放到这里，其实只是做个简单的补充。
想了解更多内容，可以参考:
区块链资料汇总
区块链白皮书

二、常见区块链共识机制说明
1、PoW: Proof of Work，工作量证明
工作量证明中，所有参与的节点一起计算区块的Hash值，通过调整区块的一个随机数nonce，得到不同的Hash值。
最终第一个计算出前N位为0的Hash值，获得记账资格，并获取区块的奖励。
其余节点可以快速验证Hash结果，从而快速达成一致（算出这个Hash工作量很大，验证工作量很小）。
此类区块链，采用长链高于短链的原则，也就是如果产生了分区，短链必须遵从于长链的结果，达到最终一致性。

如果要攻破PoW，需要在该网络中，破坏者算力超过全网络算力一半，才有可能破坏最终一致性。

但PoW计算量太大，能耗太高，而且达成一致性的速度太慢，吞吐量就很难提高。

2、PoS: Proof of Stack，权益证明
权益证明网络中，所有参与节点都知道彼此节点的权益（比如，每个Token*该Token持有时间，然后求和）
在达成一致性的时候，权益越大（Token越多，持有时间越久）的节点，越容易被选择为记账节点

如果要攻破PoS，就需要较长时间持有大量的Token，增加了攻击者的攻击成本。

但PoS会导致，强者恒强，造成垄断。与区块链区中心化的目标，背道而驰。

3、DPoS: Delegated Proof of Stake，委托式权益证明
在委托式权益证明网络中，每个节点都知道彼此节点的权益（比如，持有的Token数）
想参与记账的节点，被叫做受托节点，受托节点会进行竞选，要求普通节点投票给他
普通节点不参与记账，而是根据自己的利益，投票给自己选中的受托节点，节点权益越高，投票权重越高
最终，获得最多投票的受托节点进行记账

三、部分区块链项目的共识机制

一、两阶段提交2PC（Two-Phase Commit）
1、概述
顾名思义，两阶段提交，就是分布式数据库系统，把事务的提交过程，分为两个阶段进行操作，从而保持数据的一致性。

2、流程
a、准备阶段（Prepare Phase）
协调者（Coordinator）收到事务请求。
协调者向所有参与者（Participants）发送准备事务提交的请求。
参与者收到准备请求后，会检查本地事务的状态，判断能否完成此事务请求，并将检查结果反馈给协调者。
如果可以完成请求，参与者需要确保所有操作都已完成，事务处于可以提交、可以回滚的状态。

b、提交阶段（Commit Phase）：
协调者根据所有参与者的反馈结果，决定是否提交事务。
如果任何一个参与者不同意提交，则协调者向所有参与者发送回滚请求，全部参与者进行事务回滚，事务失败。
如果所有参与者都同意提交，则协调者向所有参与者发送提交请求，全部参与者进行事务提交，事务成功。

3、示例
假设我们有一个分布式数据库系统，包含两个数据库实例A和B，以及一个协调者C。

a、准备阶段：
客户端向协调者C发送事务请求。
协调者C向数据库A和B发送准备提交的请求。
数据库A和B检查本地事务状态，判断事务可以提交，确认所有操作已完成，并将结果反馈给协调者C。

b、提交阶段：
数据库A和B都反馈可以提交，协调者C向数据库A和B发送提交请求。
数据库A和B执行提交操作，更新数据并持久化。

二、三阶段提交3PC（Three-Phase Commit）
1、概述
顾名思义，三阶段提交就是分布式数据库系统，把事务的提交过程，分为三个阶段进行操作，可以解决两阶段提交协议2PC的阻塞问题。

2、流程
a、CanCommit阶段
协调者（Coordinator）收到事务请求。
协调者向所有参与者发送一个“CanCommit”请求。
参与者收到请求后，会根据本地状态，判断是否可以完成此事务，并将判断结果反馈给协调者。
如果参与者判断可以支持事务，则返回“就绪”（Ready）；否则，则返回“中止”（Abort）。

b、PreCommit阶段
协调者收到所有参与者的确认消息后。
如果所有参与者都返回“就绪”（Ready），则协调者会向所有参与者发送“PreCommit”请求。
参与者收到请求后，会锁定其资源以防止其他事务干扰，需要确保所有操作都已完成，事务处于可以提交、可以回滚的状态，并返回确认消息给协调者。

如果任何一个参与者不同意提交，则协调者向所有参与者发送取消请求，事务失败。

c、DoCommit阶段
协调者收到所有参与者的确认消息后，如果所有参与者都表示准备好提交事务，则协调者会向所有参与者发送“DoCommit”请求。
参与者收到请求后，会真正提交事务，并返回确认消息给协调者。
协调者收到所有参与者的确认消息后，事务成功。

如果任何一个参与者不同意提交，则协调者向所有参与者发送回滚请求，全部参与者进行事务回滚，事务失败。

3、示例
假设我们有一个分布式数据库系统，包含两个数据库实例A和B，以及一个协调者C。

a、CanCommit阶段
协调者C收到事务请求。
协调者C向所有参与者发送一个“CanCommit”请求。
A判断可以支持事务，返回“就绪”（Ready）。
B判断可以支持事务，返回“就绪”（Ready）。

b、PreCommit阶段
参与者A和B都向协调者C反馈“就绪”，协调者C判断可以进行下一阶段。
C向A和B发送“PreCommit”请求。
A和B收到消息后，锁定资源，让事务处于可以提交、可以回滚的状态，并返回确认消息给协调者。

c、DoCommit阶段
协调者C收到所有参与者的确认消息。
C向参与者A和B发送“DoCommit”请求。
参与者A，提交事务，向C返回提交成功。
参与者B，提交事务，向C返回提交成功。
C收到所有参与者的提交成功消息后，事务完成。

三、事务补偿TCC（Try Confirm Cancel）
1、概述
在高并发场景下，2PC和3PC的效率根本无法满足要求，于是大家就考虑如何在应用层进行优化，而不要把压力都给到数据库呢，于是TCC应运而生。
TCC可以跨数据库类型、跨系统类型操作，而且灵活性强，效率高。
但TCC需要大量业务代码的改造，各服务需要实现Try、Confirm和Cancel接口，而且要求接口必须支持幂等操作，是一种入侵性比较强的一致性实现方式。

2、流程
TCC通常会将一个大的事务，拆分为多个子事务，并将事务的提交拆分为三个阶段：Try、Confirm 和 Cancel。
这里要注意，对于非严格一致的场景，可以通过MQ等方法异步解决问题，不要加入TCC。TCC应该只涉及到强一致性的各个服务。

a、Try阶段
在Try阶段，系统会进行业务检查，并预留资源。
比如：检查用户余额、检查库存，并暂时冻结资源。

b、Confirm阶段
确认所有业务服务的操作。
比如：扣余额，扣库存。

c、Cancel阶段
如果在Try或Confirm阶段有任何问题导致事务需要回滚，系统会执行Cancel阶段，释放之前预留的所有资源。
比如：释放余额、释放库存等。

3、示例
有一个电商平台，用户想要购买一个商品，这笔交易涉及到以下几个子业务：
用户账户扣款：需要确保账户余额足够，并能正确扣款。
库存服务扣减库存：确保商品库存足够，并能正确扣库存。
订单服务创建订单：记录交易的详细信息，并能设置为正确的状态。

a、Try阶段
客户下单，事务协调器（Transaction Coordinator）指示每个服务进行Try操作：
账户服务尝试扣款，但只是冻结资金，不会实际扣除。
库存服务标记商品库存为预留状态，不会实际减少库存。
订单服务准备创建订单，但不会实际创建。

b、Confirm阶段
如果事务协调器（Transaction Coordinator）收到所有Try操作都成功的消息，确认它们的操作：
账户服务将冻结的资金实际扣减。
库存服务将预留的库存实际扣减。
订单服务实际创建订单，并标记为已完成支付。
事务协调器（Transaction Coordinator）收到全部操作成功消息，此时可判断事务成功。

c、Cancel阶段
如果Try或Confirm的任意操作失败，事务协调器将指示每个服务撤销它们的操作：
账户服务将冻结的资金解冻。
库存服务将预留的库存重新释放。
订单服务放弃创建订单。
事务协调器（Transaction Coordinator）同时会判断，事务失败，并监督完成全部业务补偿操作。

一、概述
上一节说了OM算法，但OM算法效率太低了，在实际工程上几乎无法使用。
1999年，Miguel Castro和Barbara Liskov提出了PBFT（Practical Byzantine Fault Tolerance）算法，大幅提高拜占庭容错算法的效率和实用性。
PBFT算法更好的平衡了效率和容错能力，在n个节点的网络中，同样可以允许的故障的节点数可以达到f =（n-1）/3个。

二、PBFT算法的工作原理
PBFT算法主要包括三个阶段：预准备（Pre-Prepare）、准备（Prepare）和提交（Commit）。
PBFT算法的复杂度为O(n^2)，虽然消息数量还是很多，所以不适合大规模的网络，但比OM算法已经有大幅提升。

1、发起请求
客户端向主节点发起请求。

2、预准备阶段（Pre-Prepare）
主节点（Primary Node）收到消息后，为其分配一个视图消息编号vid，并广播预准备消息给所有副本节点。
广播消息格式为（Pre-Prepare，视图编号v，视图消息编号vid，请求内容msg，请求内容摘要msg-hash，时间有效区间T，主节点签名sign）

3、准备阶段（Prepare）
副本节点接收到Pre-Prepare预准备消息后，进行验证：
a、消息签名不正确，不通过
b、通过v和vid判断是否有相同编号消息，但不同内容的消息，不通过
c、超出时间有效期间T，不通过
d、msg与msg-hash不一致，不通过
e、通过
消息验证通过后，副本节点进入准备阶段，并进行消息广播
广播消息格式为（Prepare，视图编号v，视图消息编号vid，请求内容msg，请求内容摘要msg-hash，时间有效区间T，副本消息签名sign）

4、提交阶段（Commit）
每个节点在收到Prepare准备消息后，进行验证：
a、消息签名不正确，不通过
b、通过v和vid判断是否有相同编号消息，但不同内容的消息，不通过
c、超出时间有效期间T，不通过
d、msg与msg-hash与之前Pre-Prepare不一致，不通过
e、通过
每个节点在接收到足够数量的提交消息（通常是2f+1个）后，进入Commit阶段，并进行消息广播
广播消息格式为（Commit，视图编号v，视图消息编号vid，请求内容msg，请求内容摘要msg-hash，时间有效区间T，节点消息签名sign）

5、回复阶段
每个节点在收到Commit提交消息后，进行验证：
a、消息签名不正确，不通过
b、通过v和vid判断是否有相同编号消息，但不同内容的消息，不通过
c、超出时间有效期间T，不通过
d、msg与msg-hash与之前Prepare不一致，不通过
e、通过
节点收到（2f+1）条相同结果的Commit消息后，确认请求已成功执行，返回给客户端。

客户端收到（f+1）条相同结果的消息后，得到最终结果。
这里设置为f+1，因为节点最多收到f条一样的错误消息，不可能收到f+1条错误的消息。

三、主节点选举
如果主节点出现了异常，或则主节点故意作恶，PBFT是无法达成一致的。
此时，就要通过视图变更（View Change，类似于主节点任期的概念），选择新的主节点。

1、故障检测
当遇到以下情况时，备份节点会触发视图变更：
主节点，在约定时间内不响应客户端及备份节点请求
备份节点发送了准备消息后，在约定的时间内未接收到来自其他节点的2f个相同的准备消息。
备份节点发送了提交消息后，在约定的时间内未接收到来自其他节点的2f个相同的提交消息。
备份节点接收到异常消息，比如视图值、序号和已接受的消息相同，但内容摘要不同。

2、发起变更消息
触发视图变更的节点会向其他节点广播视图变更消息（View-Change消息）
这个消息包含了当前视图号v+1、序列号n（最后一个稳定的检查点的序列号）、以及已经准备好的消息集合P。

3、收集变更消息
其他节点在收到视图变更消息后，会检查消息的有效性。
如果消息有效，节点会记录该消息到本地日志中，并启动一个定时器，等待接收2f+1个视图变更消息来确认视图变更的成功。

4、选举主节点
当一个节点接收到2f+1个视图变更消息后，它会确认视图变更成功，并通过预定规则开始选举新的主节点：
(v + 1) mod |R|，其中v为当前视图的值，|R|为节点数选出下一个视图的主节点
节点启用新的视图号v+1，并将选举结果，广播通知其他节点。

5、广播NEW-VIEW消息
新的主节点接收到2f个其他节点的视图变更消息后，会广播一个NEW-VIEW消息，这个消息包含了上一个视图中所有未确认的请求信息。

6、处理未确认的请求
在新的视图中，副本节点需要处理在旧视图中未能达成一致的那些请求。
一旦新主节点广播了新视图消息，副本节点将执行这些请求，并进入提交阶段。

7、变更完毕，恢复正常

一、概述
前面讲的几种一致性算法，比较适合封闭式网络，各节点都是可信的，也就是没有节点故意作恶。
但对于开放式网络，可以允许任意节点加入的时候，我们无法判定这些节点是否有恶意，也就是无法判定这些节点是否可信。
此时，我们就需要一种新的思路了：
当存在少数节点作恶（ 消息可能被伪造） 场景下，其余节点如何达成一致性呢？
对于此种场景，最出名的就是拜占庭算法，而为了更快的理解拜占庭算法，我们要先解释一下拜占庭问题。

二、拜占庭将军问题（The Byzantine Generals Problem）
拜占庭问题又叫拜占庭将军问题，是Leslie Lamport在1982年提出用来解释一致性问题的一个虚构模型。
拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统节点） 需要通过信使来传递消息，达成某些一致的决定。
但由于将军中可能存在叛徒（恶意节点），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。
拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。
（其实，还有一个隐含的限定，就是节点无法伪装为其他节点，实际中可以通过签名算法来达到这个目的）。

这样说可能有些抽象，我们举个例子：
比如一共有3个将军G1~G3，3个将军约定，少数服从多数。
G1、G2为忠诚的将军，G3是个叛徒
此时，G3有多种破坏方案，让G1和G2无法取得共识：

1、破坏方案A、否认提案内容，消息重放
比如：G1发起提案，G1要求明天进攻A城市，要把消息发给G2~G3

但G3先收到了消息，然后通过小道（比如更快的路由）向G2发送了“撤退”的提案
G2先收到了撤退的消息，后收到进攻的消息
G3向G1反馈进攻

结果：（G1被欺骗，G2被劫持）
由于只有G1发起了进攻，兵力不足，吃了败仗。
G3一口咬定，收到了G1要撤退的消息。

2、破坏方案B、故意发起错误提案
比如：G3发起提案，要把消息发给G1~G2。
但G3给G1的提案是进攻，给G2的提案时撤退

结果：（G1和G2不一致，但G1和G2认为彼此一致）
由于只有G1发起了进攻，兵力不足，吃了败仗。
G3一口咬定，发送了撤退的消息。

3、破坏方案C、故意传播相反的消息，操纵投票结果
比如：G1发起提案，G1要求明天进攻A城市，要把消息发给G2~G3。

此时：
G1希望进攻
G2希望撤退（比如节点有问题，无法接收事务提交）
G3是个叛徒，他给G1答复“进攻”，给G2答复“撤退”

结果：（G1和G2不一致，但G1和G2认为彼此一致）
G1收到了2票进攻，1票撤退，于是进攻
G2收到了1票进攻，2票撤退，于是撤退
G3是个叛徒，撤退
由于只有G1发起了进攻，兵力不足，吃了败仗。

三、Byzantine Fault Tolerant (BFT) 算法
对于上述问题，作者提出了一种BFT算法（OM算法），并证明了：
当叛变者为m，将军总人数不小于3m+1时，存在有效的算法，不论叛变者如何折腾，忠诚的将军们总能达成一致的结果。
或者，当将军总人数为n，当叛变者不大于(n-1)/3时（向下取整），存在有效的算法，不论叛变者如何折腾，忠诚的将军们总能达成一致的结果。

当恶意节点为m，节点总数必须不小于3m+1，可以这样证明：
在极端情况下：
a、m个正常节点下线。
b、m个恶意节点给出同一的恶意结论F。
c、此时必须至少有m+1个正常节点，给出正确结论T，才能保证系统得到结论T
因此节点总数，必须不小于3m+1

可见，能确保达成一致的拜占庭系统节点数至少为 4，允许出现1个坏的节点。如果叛变者过多，则无法保证能达到一致性。

四、OM算法过程
OM算法（Oral Message Algorithm）的核心思想是通过递归的方式，将命令从指挥官传递给下属，确保所有忠诚的下属最终都能接收到相同的命令。
OM算法复杂度为O(n^(m+1))，就是当有m个叛变者时，进行m+1轮递归通讯。
算法复杂度太大，在实际工程中无法应用。

1、初始化：
指挥官（通常是忠诚的将军）发送其命令给所有其他将军。
如果某个将军没有收到命令，则默认执行撤退命令。

2、递归传递：
每个将军在接收到命令后，会将该命令传递给其他未收到命令的将军。
如果某个将军接收到多个不同的命令，它会选择一个多数命令作为最终命令。

3、递归终止：
当所有将军都接收到相同的命令时，递归终止。
最终，所有忠诚的将军都会执行相同的命令。

具体步骤如下：
1、OM(0)：（递归终止条件）
指挥官发送其命令给所有其他将军。
每个将军使用接收到的命令来做出决策。如果没有接收到命令，则使用默认命令（撤退）。

2、OM(x)：（递归步骤：x=m、m-1、…、2、1）：
指挥官发送其命令给所有其他n位将军。
对于每个将军i，如果它接收到命令，则将军i作为新的指挥官，执行OM(x-1)，并将其收到的多数命令，传递给其他n-2位将军。

3、重复上述过程，所有忠诚的将军都会执行相同的命令。