区块链之共识算法
本文主要说明常用的几种共识算法
1. 拜占庭容错技术
区块链的架构是一种分布式架构,其中公有链
、联盟链
、私有链
,分别对应去中心化分布式系统
、部分去中心化分布式系统
和弱中心化分布式系统
。
在分布式系统中,可能存在故障主机、网络拥塞等问题导致错误信息在系统中传播,因此需要在默认不可靠的异步网络中定义容错协议来保证各主机达到安全可靠的状态共识。其中拜占庭容错技术是一类分布式系统中的容错技术。
1.1. 拜占庭将军问题
问题描述:拜占庭将军问题就是寻找一个方法使得在有叛徒的非信任环境中建立对战斗计划的共识。
2. PoW机制
PoW(Proof of Work)
,即工作量证明
,可理解为当你达到某个水平,表明了你付出了对应的工作量
。例如你获得了毕业证,表明你已经完成了大学所有课程的工作量。在比特币系统中,当你找到了某个满足当前难度的Nonce值
(即挖矿),表明了你付出了相应计算量。
- 工作量证明函数:表示计算方法
- 区块:表示输入数据
- 难度值:表示所需计算量
2.1. 工作量证明函数
比特币系统中使用的工作量证明函数是SHA256
,其输出值为256位的哈希算法。
2.2. 区块
比特币的区块由区块头
和该区块所包含的交易列表
组成。区块头的大小为80字节,作为比特币工作量证明函数的输入字符串,为了体现包含区块的所有交易,区块头中包含一个所有交易的生成的Merkle根的哈希值
。同时区块头还包含了父区块的哈希值,从而将记录不同交易的区块关联起来,形成区块链。
2.3. 难度值
难度值决定了节点大概多久产生一个合法的区块,即根据算力的不同,适当地调整难度值使得新区块的产生速度稳定在一个固定的速率(例如10分钟产生一个新区块)。其中难度值的调整是在每个完整节点中按照统一的公式自动发生的。
公式如下:
新难度值=旧难度值*(过去2016个区块花费时长/20160分钟)
目标值:即挖矿产生的区块哈希值必须小于目标值。
目标值=最大目标值/难度值
其中最大目标值是一个恒定值,即目标值与难度值成反比
。
2.4. PoW的过程
PoW的过程可以简化为以下数学问题:
找出一个 $x$ 使得满足 $f(x,x_0) < y_0$,其中 $x $ 为Nonce值,$x_0$ 为其他已知的常量值,$y_0$为目标值(target值)。
由于$f(x,x_0)$ 是一个单向哈希函数,即无法通过 $y_0$ 反向求出 $x$,所以需要不断地尝试 $x$ 从而得出 $f(x,x_0)$与目标值 $y_0$ 比较来判断该 $x_0$ 是否为所要找的Nonce值。
具体过程:
- 生成coinbase交易,并和其他需要打包进块的交易组成交易列表,将交易列表通过Merkle算法生成Merkle根哈希值。
- 把Merkle根哈希值和其他必要字段(例如父区块哈希值等)组成区块头,将区块头的80字节数据作为工作量证明函数的输入。
- 不断改变区块头中的Nonce值,对改变后的区块头进行
双重SHA256
运算(即SHA256(SHA256(Block_Header)))
,如果结果值小于当前的目标值则计算成功,即挖矿成功。
2.5. 基于PoW的共识记账
以下以比特币为例说明基于PoW的共识记账过程。
- 客户端产生新的
交易
,向全网广播要求对交易进行记账。 - 每个记账节点一收到请求就将该交易信息纳入一个
区块
中。 - 每个节点通过PoW的过程,找到符合难度的
Nonce值
,即挖矿。 - 当某个节点找到该Nonce值(即工作量证明),就向
全网广播
。 - 当且仅当该区块的所有交易有效且之前未存在过,才认证该区块有效。
- 其他节点认可了该区块则将区块加在自己区块链的末尾,并进行下一个区块的挖矿过程。
2.6. PoW与拜占庭问题
待完成
3. PoS机制
PoS(Proof of Stake)
,即权益证明
。PoS指的是一种对货币所有权的证明。一笔交易所消耗的币龄可被视为PoS的一种形式。
待完成
4. DPoS机制
DPoS(Delegated Proof of Stake)
,即股份授权证明
。
待完成