part 1 共识算法综述文章
1 文章一：《区块链共识算法综述》
1.1 文章来源
地址：知网
引用：[1]谭朋柳,王润庶,曾文豪等.区块链共识算法综述[J].计算机科学,2023,50(S1):691-702.
期刊：计算机科学(北大核心CSCD)
作者：谭朋柳 王润庶 曾文豪 王诗堃 邹雯诗 南昌航空大学软件学院
日期：2023年
1.2 文章概述
本文从服务对象节点的种类出发，将共识算法归类为公有链、联盟链以及私有链这3个大类，在这三个大类的基础上阐述了当前主流的区块链共识算法的基本原理，并从去中心化、安全性、可扩容性这3个方面进行算法性能评估。并对算法进行了优缺点的分析总结，给出了优化区块链共识算法的相关方向。
1.3 文章研读
提出当前区块链共识算法问题：
需解决区块链中存储大小以及共识算法中高吞吐量、高容错性、高安全性和低资源消耗等问题。
从区块链中节点参与网络方式的不同的分类中引出问题：
- 公有链中的共识算法需要更完善的安全机制来保证公有链正常运行，而不是会因此而崩溃，在提高安全性的同时，公有链牺牲的是共识速度和共识吞吐量。
- 联盟链相对于公有链来说去中心化程度较低，联盟链中的共识算法需要提高共识的吞吐量，减少系统资源的消耗。
- 私有链对交易效率、安全性能等多个方面有更高要求，故私有链相对于联盟链来说又更加中心化。其次，相对于联盟链共识算法来说，私有链共识算法所需吞吐量应得到进一步的提升，交易效率需更高。
公有链、联盟链和私有链之间的主要区别：
共识过程：
- 加入共识阶段
- 出块阶段(核心阶段)
- 进行验证投票阶段(核心阶段)
- 推出共识阶段
公有链、联盟链、私有链需要什么样的共识算法：
- 公有链所需的共识算法需要安全性高和允许出现拜占庭节点这两种特性来保证公有链的正常运作。
- 联盟链所需的共识算法需要在性能消耗尽可能少和允许一定数量拜占庭节点的情况下保证有多个实体来共同管理链。（研究重心放在联盟链~~~）
- 私有链所需的共识算法需要在节点不出现拜占庭节点的情况下，有运行性能高、能耗小等特点，优先考虑系统的速度，在中心化高的情况下管理链。
公有链共识算法：
①PoW( Proof Of Work ) 共识算法
公式具体如下：
$$ SHA256( $$
$$ SHA256(父区块哈希值(32byte)+版本号(4byte)+时间戳(4byte) $$
$$ +Nonce值(4byte)+nBits(4byte)+Merkel根(32byte))) $$
$$ <Target $$
- 父区块哈希值大小为32字节，即上一个区块的哈希值，指向前面一个区块的哈希指针；
- 版本大小为4字节，即当前版本的版本号；
- 时间戳大小为4字节，即生成这个区块的时间信息，精确到秒的UNIX时间戳；
- Nonce值大小为4字节，初始值为0,Nonce值可以不断增加，是工作量证明的关键；
- nBits大小为4字节，存储的是压缩格式的当前目标Hash值，即本区块的难度值；
- Merkel根大小为32字节。在区块所收集的交易中，对每个交易进行哈希，再对两两交易的哈希值进行哈希，一直重复第二个步骤，直至哈希值为一个，这个哈希值称为Merkel根。这个计算过程称为Merkel树，树的叶子节点必须为偶数，若叶子节点为奇数则需将最后一个交易复制一份，再进行上面的步骤。
- Target: 大小为4字节。Target即目标阈值。当前区块的哈希值必须小于这个阈值，寻找Nonce值的难度与Target成反比。
Python代码实现如下：
import hashlib
import time
def calculate_merkle_root(transactions):
if len(transactions) == 0:
return None
while len(transactions) > 1:
if len(transactions) % 2 != 0:
transactions.append(transactions[-1]) # 复制最后一个交易
new_transactions = []
for i in range(0, len(transactions), 2):
data = (transactions[i] + transactions[i+1]).encode() # 对两个交易哈希值进行哈希
hash_result = hashlib.sha256(hashlib.sha256(data).digest()).hexdigest()
new_transactions.append(hash_result)
transactions = new_transactions
return transactions[0]
def proof_of_work(previous_block_hash, version, timestamp, nBits, transactions, target):
merkle_root = calculate_merkle_root(transactions) # 计算Merkle根
if merkle_root is None:
return None, None
max_nonce = 2 ** 32 # 最大Nonce值
for nonce in range(max_nonce):
data = (
previous_block_hash.encode() +
version.to_bytes(4, 'big') +
int(timestamp).to_bytes(4, 'big') +
nonce.to_bytes(4, 'big') +
nBits.to_bytes(4, 'big') +
merkle_root.encode()
)
hash_result = hashlib.sha256(hashlib.sha256(data).digest()).hexdigest()
if int(hash_result, 16) < target: # 满足目标条件
return nonce, hash_result
return None, None
# 示例调用
previous_block_hash = "00000000000000000000000000000000"
version = 1
timestamp = time.time()
nBits = 12345
transactions = [
"transaction1",
"transaction2",
"transaction3",
"transaction4"
]
target = int("000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 16)
nonce, hash_result = proof_of_work(previous_block_hash, version, timestamp, nBits, transactions, target)
if nonce is not None:
print(f"Nonce: {nonce}")
print(f"Hash Result: {hash_result}")
else:
print("Proof of work failed.")
②PoS(Proof of Stake)共识算法
2012年点点币PoS公式如下
币龄公式：
$$ CoinAge=CoinNum×CoinDay $$
- CoinAge为币龄；
- CoinNum为该节点所拥有的币数；
- CoinDay为持有币的天数。
目标公式如下：
$$ Hash(n StakeModifier $$
$$ +tx Prev.block.n Time+tx Prev.offset $$
$$ +tx Prev.n Time+tx Prev.vout.n+n Time) $$
$$ <bn Target×bn CoinDayWeight $$
- Hash为哈希函数中的哈希算法。
- n StakeModifier为权重修正因子。
- tx Prev.block.n Time,tx Prev.offset,tx Prev.nTime,tx Prev.vout.n为点点币中区块头中的部分信息属性。
- n Time为当前区块的时间戳。
- bn Target为目标阈值。
- bn CoinDayWeight为节点所拥有的币龄。
从上面的公式可以看出，bn CoinDayWeight越大，节点就越容易达到目标不等式的要求，越容易获得记账权。
但PoS协议存在一些潜在的安全问题：币龄会被恶意的节点滥用以获得更高的网络权重并成功实施双花攻击。值得注意的是，由于币龄的问题，创世的节点可以通过定期开启钱包进行权益累积而滥用这一系统。
PoS2.0协议，发布黑币
黑币中前5 000个块是使用PoW算法产出的，目的是为了解决黑币分配不公平的问题。第5 001个块到第10 000个块是PoW算法和PoS算法共同产生的。从第10 001个块开始就是采用纯PoS算法。
PoS算法证明公式为：
$$ Hash(n StakeModifier+tx Prev.block.n Time $$
$$ +tx Prev.n Time+tx Prev.vout.hash $$
$$ +tx Prev.vout.n+nT ime)<bn Target×n Weight $$
- n StakeModifier为权重修正因子，在PoS2.0中用于预防计算攻击每次都会变化。
- tx Prev.block.n Time,tx Prev.nTime,tx Prev.vout.hash,tx Prev.vout.n为黑币中区块头的信息属性。
- n Time为当前区块的时间戳信息。
- bn Target为目标阈值。
- n Weight为节点拥有的币数。
注意：PoS2.0中的合格区块已与币龄无关，但和币数有关联。
PoS代码实现
import hashlib
def proof_of_stake(stake_modifier, prev_block_n_time, prev_n_time, prev_vout_hash, prev_vout_n, n_time, target, weight):
# 将所有参数转换为字符串并拼接在一起作为数据
data = (
str(stake_modifier) +
str(prev_block_n_time) +
str(prev_n_time) +
str(prev_vout_hash) +
str(prev_vout_n) +
str(n_time)
)
# 计算数据的哈希值
hash_result = hashlib.sha256(data.encode()).hexdigest()
if int(hash_result, 16) < (target * weight): # 满足目标条件
return hash_result
return None
# 示例调用
stake_modifier = "stake_modifier"
prev_block_n_time = 1234567890
prev_n_time = 9876543210
prev_vout_hash = "prev_vout_hash"
prev_vout_n = 1
n_time = 1543210987
target = int("000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 16)
weight = 2
hash_result = proof_of_stake(stake_modifier, prev_block_n_time, prev_n_time, prev_vout_hash, prev_vout_n, n_time, target, weight)
if hash_result is not None:
print(f"Hash Result: {hash_result}")
else:
print("Proof of stake failed.")
③DPoS( Delegated proof of Stake ) 共识算法
DPoS算法中的节点分为两大角色，分别为普通节点和委托人。委托人必须由持币节点进行投票，被选中的委托人负责管理区块链项目。某种程度上类似于“人民代表”制度。任何的持币节点都可以参与到投票和竞选委托人的环节中，在这些环节中节点可以随时进行投票、撤票等操作，且节点的持币量与投票的权重成正比。普通持币节点可以投票选出n个委托人。
n个委托人之间没有什么差别，各自的权益都是相等的。之后系统会把委托人之间的顺序打乱排列，从而在重新排列的顺序上依次进行出块任务。委托人的职责主要是在自己的出块时间内收集各个节点间的交易并且验证交易的有效性，从而把交易打包进区块，同时把区块广播出去。委托人若在不是自己的出块时间出块，则所产生的区块会被其他节点视为无效块。
在完成一轮的委托人出块后，系统会把没有履行好职责的委托人剔除，之后重新对各个节点统计票数，再选出n个委托人，再一次地打乱委托人之间的顺序。从已有的结果表明，打乱顺序而不按照原有的顺序进行出块任务是为了防止相邻委托人因长时间顺序不变而结识，从而相互串通进行分叉攻击；其次，各个委托人会按照排好的顺序依次出块，在成功出块后委托人会获得一定的奖励。
联盟链共识算法：
①PBFT( Practical Byzantine Fault Tolerance ) 共识算法
PBFT算法中允许容忍的异常节点最大个数为f,那么一个节点可以收到的消息量为N-f条消息，消息中又会有作恶的节点发送错误的信息，最多为f条，诚实的节点个数又要大于所容忍的节点个数，故PBFT算法中总节点的个数要满足N-f-f>f这个不等式，即N≥3f+1。公式表明若出现1个异常的节点，要想确保其余节点消息的传达能达到一致性需求需要总节点的个数至少为4个，且其余3个节点必须为诚实可靠的节点。
PBFT算法的共识流程主要是客户端发送请求给主节点，之后主节点广播给其他节点开始三阶段的共识流程，各个节点收到的信息达到一定数量后回传给客户端，客户端收到回复确认共识完成。
其中Cline为客户端；Primary Node为主节点；Node1,Node2,Node3为节点1,2,3。
PBFT的一次共识
<1>首先在Request阶段，客户端发消息给主节点。主节点验证请求消息并负责签名加密，之后封装Pre-prepare消息〈〈Pre_prepare,v,n,d〉s,m〉,该消息中
- v为视图编号，一轮共识一般都是在同一个视图下进行；
- n代表序号；
- d为消息摘要；
- s为主节点对消息的签名；
- m为原始消息数据。
<2>此时系统进入Pre-prepare阶段，主节点把Pre-prepare消息广播给其他节点，其他节点收到主节点发送过来的Pre-prepare消息后进行以下操作：
- 首先对m验证签名的合法性；
- 验证节点中的视图编号v是否与消息中的视图编号v相同；
- 验证节点在当前视图上没有收到额外的Pre-prepare消息，即不存在另一个d′=hash(m′);
- Pre-prepare消息中的n满足不等式h≤n≤H,h和H代表序号n的高低阈值。
<3>若验证通过，节点会封装对应的Prepare消息〈Prepare,v,n,d,i,s〉,其中i表示节点的身份。之后系统进入到Prepare阶段，节点在Prepare阶段把Prepare消息广播给其余的节点。其余的节点在收到Prepare消息后会对其中的v,n,d进行验证。等节点收到Prepare消息数量为2f+1(包括本身消息)且验证通过时，该节点开始封装Commit消息〈Commit,v,n,d,i〉。
<4>系统进入到Commit阶段，节点开始广播Commit消息给其余的节点。其余的节点在收到Commit消息后，验证其中的v,n,d是否与本身的v,n,d无差别。
<5>若验证通过且通过数量为2f+1(包括本身消息)时，系统会进入到Reply阶段，各个节点会将Commit消息回传给客户端。当客户端收到f+1个相同的Commit消息时，这表明各个节点达成了共识，之后客户端会把消息存入本地状态数据库中。以上就是一次共识的完成过程。
PBFT算法中有视图切换机制，当节点发现主节点在一定的时间里没有完成共识，发生了宕机或主节点作恶，则启动视图切换机制。视图切换的公式为：P=v mod |N|,P为主节点编号。每完成一轮共识，也会触发视图切换机制。其中需要注意的是，已经达成的共识不会在新的视图中进行回滚。
②SBFT
SBFT算法在PBFT算法的基础上添加了C-Collector和E-Collector两个角色，它们都由副本节点担任(一个角色可由多个副本节点担任),这两个角色的作用都是收集并组合阈值签名并且转发相关结果给其他的节点，从而降低消息复杂度。
SBFT算法中有两条路径在不同的情况下促使节点达成共识，分别为快速路径(Fast path protocol)和线性PBFT路径(Linear-PBFT)。默认情况下，SBFT算法执行快速路径。当快速路径无法达成共识，SBFT算法就会运行线性PBFT路径。
SBFT算法的共识过程分为5个阶段：Pre-prepare(预准备阶段)、Sign-share(签名分享阶段)、Commit-Proof(提交证明阶段)、Sign-state(签名状态阶段)、Execute-Proof(执行证明阶段)
客户端发送〈“request”,o,t,k〉消息给主节点，主节点再转发消息给其他副本节点。那么主节点进入到Pre-prepare预准备阶段，主节点收到客户端发来的Request请求，随后创建一个〈“pre-prepare”,s,v,r〉消息决策块并将该块作为预准备消息广播给其他副本节点。其中s是当前序号，v是视图编号，r是request请求集合。Sing-share签名分享阶段，副本节点收到预准备消息后，对决策块进行校验，校验通过的条件为：
(1)决策块中的视图编号与本节点的视图编号相同；
(2)视图v之前没有接受序列s的“pre-prepare”;
(3)序号s应满足公式：
$$ ls<s<win $$
其中ls为最后的稳定序列号，win为一个常量用来限制未完成的块数；
(4)r是通过认证和访问控制要求的一系列有效操作。
校验通过后副本节点会对相关信息进行哈希加密，公式为：
$$ h=H(s‖v‖r) $$
其中，H是加密哈希函数(SHA256)。接着对h进行阈值签名操作从而得到σi(h),并向C-Collector节点的C-collectors(s,v)集合发送〈“sign -share”,s,v,σi(h)〉签名消息。在commit-Proof阶段，每个C-Collector收到消息后，进行校验，校验条件为：
(1)C-Collector节点的视图编号v与消息中的视图编号v相同；
(2)在同一个视图中，C-Collector节点先前没有接收相同序列s的“sign -share”;
(3)阈值签名σi(h)通过C-Collector节点的验证。
当C-Collector节点接受到3f+c+1条不同的签名消息且通过时，C-Collector节点会组合签名σi(h),并且广播〈“full-commit-proof”,s,v,σi(h)〉消息给所有节点。Sign-state阶段，副本节点收到“full-commit-proof”消息后依旧对相关的参数进行校验，校验通过后提交r(r为序号为s的请求)。当序号s之前的所有请求都被执行，并且r是序列s的提交请求块时，副本节点通过执行请求r使状态DS-1更新为DS。随后副本节点更新状态摘要为d=digest(DS),签名为πi(d),并向E-Collector节点的E-collectors(s)集合发送〈“sign -state”,s,πi(d)〉签名消息。Execute-proof阶段，E-Collector节点收到sign-state消息并验证签名，当收到sign-state消息数达到f+1条时，E-Collector节点会将消息组成一个单一的签名π(d),并且发送〈“full-execute-proof”,s,π(d)〉消息给所有节点表明决策块状态是持久的。E-Collector节点会给客户端发送〈“execute-ack”,s,l,val,o,π(d),proof(o,l,s,D,val)〉消息，其中o为请求(o∈r),l为请求o的位置，val为请求o的状态响应值，proof(o,l,s,D,val)为请求o是否被执行的证明。客户端在接收到execute-ack消息后会校验π(d)是否有效和proof(o,l,s,D,val)是否为真，校验通过后客户端标记请求o为已执行和设置val作为其返回值。SBFT共识过程中客户端只需要接收确认一条消息就可以完成共识。
线性PBFT路径的触发条件是在规定的时间内客户端没有接收到Execute-act消息(即快速路径无法达成共识)。则客户端会把Request请求发送给所有的节点，并请求一个新的线性PBFT路径。线性PBFT路径中的Sign-state阶段包含两个签名，分别为速路径所需要的σi(h)和线性PBFT路径所需要的τi(h)。当一定的时间内，C-Collector节点只收集到足够创建签名τi(h)的消息，而没有收集到足够创建签名σi(h)的消息，则C-Collector节点发送〈“prepare”,s,v,τ(h)〉消息给其他节点，从而进入到Prepare阶段。在该阶段中副本节点收到prepare消息后进行验证，通过后发送〈“commit”,s,v,τi(τ(h))〉给全部的Collector节点。随后在PBFT commit-proof阶段，C-Collector节点(包含主节点)收集到一定数量的签名后发送〈“full-commit-proof-slow”s,v,τ(τ(h))〉消息给所有节点。如果节点已收到过pre-prepare消息和full-commit-proof-slow消息，并且通过h=H(s‖v‖r)验证，随后节点就提交r(序列为s的决策块),其他节点接收到r进而触发快速路径中Sign-state阶段和Execute-proof阶段，从而使节点达成共识。
③T-PBFT
T-PBFT共识算法（EigenTrust-Based Practical Byzantine Fault Tolerance ) 是一种基于特征信任模型的优化实用拜占庭容错共识算法，也是一种多阶段共识算法，通过节点间的交易来评估节点信任，从而选择网络中质量较高的节点来构建共识群。
T-PBFT算法引入EigenTrust信任模型,根据计算的全局信任值，把信任值高的节点挑选出来组成一个共识组，以此作为节点达成共识的基础。全局信任值的公式为：
$$ Ti=C1iT1+…+CniTn $$
Ti是node的全局信任值，Cij是nodei对nodej的局部信任值(通过nodei对nodej两个节点的交易满意数量来计算)。局部信任值分为两种，分别为直接信任值(两个节点有直接交易)和推荐信任值(两个节点没有直接交易)。由于共识组的存在，参与共识的节点数量减少，从而使得共识在大规模的网络环境下的共识过程更加高效。随着区块上链，节点间会产生新的交易，全局信任值随之改变，共识组的节点也因全局信任值而动态改变。
最后，T-PBFT可以开始新的一轮共识。T-PBFT共识算法达成共识需要满足两个前提条件，分别为：
1)行为一致性，即在本算法中，那些全局信任值高的节点值得信任，并以高概率诚实行事；
2)有限的交易时间，以在一定时间内的交易量为基础，计算节点的全局信任值。
T-PBFT算法的共识过程分为4个阶段：Group Process阶段(共识组阶段)、Pre-Prepare阶段(预准备阶段)、Prepare阶段(准备阶段)、Reply阶段(回复阶段)。
Group Process阶段，主组中的相关节点收到客户端发来的消息后，将消息打包且放到预生成的块中，随后广播给主组中的其他成员。其他主组成员收到预生成块后进行验证，验证通过后每个主组成员节点将用相同的视图临时记录预生成块。其中，若主组中的一个节点发生故障，也可以立即替换他，并不会触发视图更改过程。同时进入到Pre-Prepare阶段，主组将预生成块和组签名的预准备消息广播给共识组的副本节点进行审核和验证。其中节点可以验证主组签名的有效性，但无法发现是哪个主组成员签了该名。在Prepare阶段，副本节点验证预生成块的有效性，每个副本节点在预生成块中使用预先安排的交易顺序模拟打包事务执行，同时计算块哈希，如果块哈希值与当前块哈希值一致，则通过有效性检查。随后副本节点向其他节点广播带有它们签名的准备信息。一旦有节点收到的消息数量超过2f(其中f是共识组中的拜占庭数量),则该节点会发送一条回复给客户端。之后共识到达Reply阶段，客户端在收到相同应答消息数为f+1时，确认预生成块，并将块添加到区块链的尾部。随后每个节点更新它们的日志记录，从而达成共识。
继续加油