赞
踩
balance
)nonce
)code
) 和 存储(stroge
)现在要实现从账户地址到账户状态的映射,咋一看,容易想到Key-value
键值对,所以直观想法便用哈希表实现。若不考虑哈希碰撞,查询直接为常数级别的查询效率。
但采用哈希表,难以提供Merkle proof
(需要回顾请看这里)
Merkle Tree
思考
- 比特币为什么可以构建
Merkle Tree
,而以太坊不行 ?
- 因为构建的内容不是一个量级的
- 在比特币系统中,仅对一个区块中的交易(最多包含4000左右) 构造,前面构建好的是不发生变化的
- 在以太坊系统中,基于账户的模式下,每发布一个区块,要将所有的账户都遍历一遍来构建,开销太大。
- 构建出的
Merkle Tree
不唯一
- 在比特币系统中,没有排序不影响,因为是一人(拥有记账权的矿工 POW)说的算,其他都都是复制,所以大家得到的Merkle Tree是唯一的
- 在以太坊系统中,因为没有排序,没办法保证新账户出现在叶子节点的顺序(因为每个人接受新节点的顺序是不一样的),算出的根哈希值不同,所以构建的
Merkle Tree
不唯一
思考
- 那么经过排序,使用
Sorted Merkle Tree
可以吗?
- 还是开销太大,新增账户,由于其地址随机,插入
Merkle Tree
时候很大可能在树中间,发现其必须进行重构。(牵一发而动全身)
所以,简单的Merkle Tree
和哈希表数据结构是不满足的
那么我们看一下实际中以太坊采取的数据结构:MPT
(第四小节)
取自单词retrieval
n. 检索
下图是使用trie
数据结构对单词进行存储
trie
特点:
trie
上面不会发生碰撞。trie
缺点:
trie
的存储浪费,很多节点只存储一个key(叶子节点)。因此,要是能合并一些就好了,为此,引入了Patricia tree/trie
需要注意的是,如果新插入单词,原本压缩的路径可能需要扩展开来。
问题
- 那么,需要考虑什么情况下路径压缩效果较好?
- 树中插入的键值分布较为稀疏的情况下,可见路径压缩效果较好(如下图)。
Disintermediation
去中间商
在以太坊系统中,160位的地址存在
2
160
2^{160}
2160 种,和账户数目相比,可以认为地址这一键值非常稀疏。因此,我们可以在以太坊账户管理种使用Patricia trie
这一数据结构
但实际上,在以太坊种使用的并非简单的PT(Patricia trie
),而是MPT(Merkle Patricia trie
)
Merkle tree
与 Binary tree
区别
Merkle tree
相比 Binary tree
,也是普通指针换成了哈希指针block heade
r中的根哈希值
block header
只有一个根哈希值:
Merkle tree
的根哈希值block header
中有三个根哈希值:
Merkle Tree
根哈希值的用处:
Merkle proof
给轻节点可以验证账户余额Merkle Patricia trie
不同在哪?
Prefixes
有分奇数哥和偶数个nibble
发布新区块的时候,状态树中有一些节点的值会发生变化,这些改变是在保留原来状态基础上新建分支来修改
在这里插入图片描述
状态树中保存Key-value
对,key
是地址,value
是状态通过RLP(Recursive Length Prefix
,一种进行序列化的方法)编码序列号之后再进行存储。
以太坊的所有类型最后都要经过RLP变成字符数组(
nested array of bytes
)
以太坊中三棵树都是Merkle Patricia trie
,MPT的优点是支持查找操作,通过键值
比特币只有一颗交易树,采用普通的MT(Merkle Tree
)
Merkle Proof
以太坊中是如何实现这复杂的查找操作呢? 答:Bloom filter
(布隆过滤器)
布隆过滤器可以判断某个数据一定不存在,但是无法判断一定存在(可能发生互相碰撞,
false positive
)
- 例子
每个交易完成后会产生一个收据,收据中包含一个Bloom filter,用于记录交易类型、地址等信息
发布的区块中块头里有一个总Bloom filter,其为该区块中所有交易的Bloom filter的一个并集
查找时候先查找哪个区块块头中包含需要的Bloom filter
,(如果不包含,则一定不存在)如果块头中包含,再查找区块中包含的交易所对应的收据树中的Bloom filter
,也就是每个收据的Bloom filter
,看看哪个有,再查看交易进行确认;也可能都没有,因为可能是false positive
Bloom filter
结构的优点:
以太坊的运行过程,可以视为交易驱动的状态机(transaction-driven state machine
),通过执行当前区块中包含的交易,驱动系统从当前状态转移到下一状态。当然,BTC我们也可以视为交易驱动的状态机,其状态为UTXO(用掉一些输出,又会增加一些新的输出,所以发布的区块会驱动状态机从当前的状态转移到下一个状态)。
问题1:
- 有没有可能收款账户不包含再状态树中?
- 可能
- 因为在以太坊和比特币系统中,新建的账户是不会被知道的,只有产生交易时才会被系统知道,对应在以太坊的操作是在状态树中新插入一个节点
问题2:
- 能否将每个区块中状态树改成只包含和区块中交易相关的账户状态?(这样就和交易树、收据树保持一致,可以大幅削减状态树大小)
- 不能
- 这样的设计账户状态查找不方便,因为不存在某个区块包含所有状态
- 例如,查询新建账户的状态,则需要一直找到创世纪块才能知道这个账户不存在是个新建的账户声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/833206
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。