区块、链和共识
区块链的基础数据结构
准备
Hash
Hash也称散列、哈希。基本原理就是把任意长度的输入,通过Hash算法变成固定长度的输出(更多解释见知乎)
特点是:相同的输入一定得到相同的输出,不同的输入大概率得到不同的输出
举例:用shell命令行下的
md5sum
来计算任意的字符的MD5哈希$ md5sum <<< haha7494ab07987ba112bd5c4f9857ccfb3f-$ md5sum <<< hehee4439267203fb5277d347e6cd6e440b5-$ md5sum <<< hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh6f2362c812dcfd693da2e3ae537cfb41-
常见的hash算法:
- 文件防篡改:MD5
- 比特币挖矿:SHA256
- 证明数据片段:Merkle root
- 文本去重:SimHash
区块
区块(block)由区块头(block header)和交易列表(transaction list,tx list)组成,block之间通过block header的hash连接成了一个链表结构。
block header
- 比特币的block header(Github)
int32_t nVersion;uint256 hashPrevBlock;uint256 hashMerkleRoot;uint32_t nTime;uint32_t nBits;uint32_t nNonce;
- 以太坊的block header(Github)
ParentHashcommon.Hash`json:"parentHash" gencodec:"required"`UncleHash common.Hash`json:"sha3Uncles" gencodec:"required"`Coinbasecommon.Address `json:"miner"gencodec:"required"`Rootcommon.Hash`json:"stateRoot"gencodec:"required"`TxHashcommon.Hash`json:"transactionsRoot" gencodec:"required"`ReceiptHash common.Hash`json:"receiptsRoot" gencodec:"required"`Bloom Bloom`json:"logsBloom"gencodec:"required"`Difficulty*big.Int `json:"difficulty" gencodec:"required"`Number*big.Int `json:"number" gencodec:"required"`GasLimituint64 `json:"gasLimit" gencodec:"required"`GasUsed uint64 `json:"gasUsed"gencodec:"required"`Timeuint64 `json:"timestamp"gencodec:"required"`Extra []byte `json:"extraData"gencodec:"required"`MixDigest common.Hash`json:"mixHash"`Nonce BlockNonce `json:"nonce"`// BaseFee was added by EIP-1559 and is ignored in legacy headers.BaseFee *big.Int `json:"baseFeePerGas" rlp:"optional"`
- 当前我们只需要关注其中两个字段(其他字段会在后续课程中解释)
hashPrevBlock
/ParentHash
,上一个block header的hashhashMerkleRoot
/TxHash
,tx list的hash
block body
block body
- block body就是tx list,block header通过
TxHash
指向唯一的tx list - 从tx hash list得到
TxHash
的hash算法叫做默克尔树(Merkle tree),相比其他的hash算法有特殊的性质(可以简洁地证明tx存在其中)
链
链
- block header通过
ParentHash
指向唯一的上个block header,并最终形成一条链高度为0的block称之为Genesis,即创世区块
写死在程序里(Github)
也可以在btc.com上看到比特币的创世区块,以及中本聪留下的那句话
比特币创世区块上记录的报纸头条文章标题
高度最高的block称之为Tip,即最新区块
可以在etherscan上观察以太坊链的情况
TxHash
和ParentHash
相结合,赋予了区块链不可篡改的特性
共识
只讲对数据结构有影响的知识点,不深入讲共识算法。
block reward
为什么:激励节点出块
对tx的有效性达成一致
比特币的双花攻击(double-spending attack)
对tx的顺序达成一致
以太坊的三明治攻击(sandwich attack)
怎么做:
Coinbase
在block里包含一笔特殊的交易或是记录在block header里
包含block reward和所有tx fee/gas
block reward一般设置为n年减半或是恒定
比特币挖矿奖励减半表格
Nakamoto consensus
为什么:对block的有效性达成一致
- 决定每个高度上使用哪个block
- tx list
- block reward
- 决定每个高度上使用哪个block
怎么做:PoW(Proof of Work)算法
- 调节block header:
Nonce
和TxHash
- 让block header的hash小于Target
- 可以看到比特币的block hash都是一堆0开头的(btc.com)
nBits
会随着nTime
调整,保持区块间隔时间为10分钟
- 多个block时的选择
谁的块先出用谁的
谁的链更长用谁的
Youtube上找到的说明最长链法则(longest chain rule)的视频
- 调节block header:
分析:这种争抢出块权的方式称作中本聪共识
- 去中心化、可用性、终局性的取舍
- 去中心化:节点多、permission-less、节点对等(都能出块)、网络差
- 可用性/liveness:链持续接受新数据写入、交易随时上链、网络不会停止出块
- 终局性/safety:所有节点对数据达成一致、写入的数据不可撤销、状态不可逆
- 保证去中心化、可用性,弱化终局性
- 用经济手段来强化终局性(比特币交易确认时间是6block)
- 中本聪共识的优点在于完全的去中心化、免信任
- 不阻止节点破坏共识而是让其付出经济代价
- 全网所有节点都是恶意但趋利的就能正常工作
- 中本聪共识的风险在于51%攻击/Selfish Mining
- 控制全网一半以上的算力,即可无视别人的block,构建只包含自己block的链,并在block选择中胜出
- 不断改变算法实现中所依赖的硬件来降低风险
- 去中心化、可用性、终局性的取舍
举例:中本聪共识的实现
- Bitcoin(ASIC)、Ethereum(GPU)、Monero(CPU)、Arweave(CPU+IO)
非中本聪共识(简述)
市场经济→计划经济:拜占庭共识
- 怎么做:
- 弱中心化:有限且固定数量的出块节点
- 指派:轮到某个节点出块
- 投票:超过2/3的出块节点同意
- 无难度,出块间隔固定
- 分析:保证终局性,弱化可用性、去中心化
- 举例:dPoS(delegated Proof of Stake)的算法大都属于拜占庭共识
Practical Byzantine Fault Tolerance(PBFT)共识
- 怎么做:
介于市场经济和计划经济之间:可验证随机数
怎么做:通过所有节点可验证的随机数生成器来不断指派一个或多个节点出块
- 随机数生成器
- 链上的随机数
- VDF(Verifiable Delay Function)、VRF(Verifiable Random Function)
- 第三方随机数服务
- 所有节点候选,按power为概率被选中,一个高度可能有0到多个被选中
- 有难度调整,出块间隔固定
- 随机数生成器
分析:和中本聪共识一样保证去中心化、可用性,弱化终局性
- 和中本聪共识的区别是在分叉上出块无需额外代价,需要打补丁来强化终局性
- 比如stake slashing、revert limit等,限制在分叉上出块
举例:
- Proof of Stake:Qtum、Algorand、Solana
- Proof of Storage:Filecoin、Chia
Filecoin最早期的共识算法
分叉
分叉的原因:去中心化、区块间隔、终局性的取舍
- 去中心化程度越高,网络环境越差
- block和tx的全网同步速度变慢
- 节点难以时刻保持同步
- 区块间隔时间越短,节点越容易在非最新高度上出块
- 去中心化程度越高,网络环境越差
分叉的结果:
- 孤块(orphant block)
比特币网络中的孤块
分叉的缓解(Etherscan):
- 一个block能包含最多2个(Github)叔块(uncle block)在
UncleHash
里 - 奖励
- 每包含一个叔块,能增加少量的block reward
- 被包含的叔块,能获得大部分的block reward
- 激励节点切换到被更多人所共识的链上
- 你出的块我已经给你算上了,赶紧切换到最长链吧
以太坊网络中的叔块
- 一个block能包含最多2个(Github)叔块(uncle block)在
总结
区块链是去中心化网络环境下,具有极高可用性、较高终局性的数据库设计
coin和block reward是保证区块链在去中心化环境下能够运行的前提
继完全去中心化的公有链之后又产生了几种弱中心化的链
减弱去中心化换来更高的终局性和更短的区块间隔
Hybrid:delegated PoS系列
继blockchain之后又产生了DAG(Directed Acyclic Graph)的数据结构
- 允许block/tx的并发,TPS提升
- 分叉加剧,终局性降低
- IOTA、Conflux、Avalanche