区块链以太坊笔记part3

• 基于北大肖臻老师区块链公开课所做

以太坊状态树

以太坊中采用的是基于账户的模式，它是用什么样的数据结构来实现的呢？
我们要完成的功能是账户地址到账户状态的映射，addr->state，以太坊中用的地址是160位(20 bytes)的，也就是40个16进制的数。直观上，我们认为可以直接用一个哈希表来实现，系统中的全节点维护一个哈希表，每次有一个新的账户插入到哈希表，需要查询账户余额就直接在哈希表中查询，若不考虑哈希碰撞，基本上查询效率在常数时间内，更新也很容易在哈希表中更新。但是，如果用哈希表，怎么提供merkle proof？
比如，A要和B签合同，希望B证明一下自己有多少钱，如何提供证明？一种方法是，把哈希表中的元素组织成一个merkle tree，算出root hash，将根哈希值保存着block header里公布出去。只要root hash是正确的，就能够保证底下的树不被篡改。但是问题在于，如果有新区块发布，新区块中包含有新的交易，我们要执行这个交易就必然会使哈希表的内容发生变化。那么发布下一次内容需要重新将哈希表组织成树，太过复杂。实际上只有与那个区块发生交易的账户才有变化，大多数是不变的，重新组织数代价太大。
比特币系统中为什么没有这个问题？因为比特币中的merkle是把区块里包含的交易组织成merkle tree，每次发布一个新的区块又有一个新的交易，比特币中的merkle tree是immutable的。每次发布一个新的区块，对应一个merkle tree，这棵merkle tree构建完是不会再改的。下次再发布一个新的区块，构建一个新的merkle tree。而区块里交易数目最多4000个，所以每次发布一个区块，比特币里构建一个merkle tree是要把这几百几千个交易组织起来构成merkle tree。
以太坊中如果采用merkle tree，是要把所有的账户构建成merkle tree，这个数目要比每个区块里不到4000个交易的数量高出好几个数量级。也就是每发布一个区块，需要遍历所有账户。merkle tree除了提供merkle proof之外，还有一个重要作用是维护全节点之间状态一致性。如果没有root hash并发布出来，每个节点都是在本地维护一个数据结构，就不清楚自己的数据结构状态和别人的数据结构状态是否一致。
考虑第二种方案：不用哈希表，直接用merkle tree把所有账户放进去，要更改直接在merkle tree里改。这个方法问题在于merkle tree没有提供一个高效的查找和更新的方法。
而且这样构建merkle tree要不要排序？
比特币中要证明一个交易不再区块里需要用排序的方法，否则证明代价就变成了θ(n)。不排序还有另外一个问题，叶子结点是账户信息，如果不规定账户在叶节点中的出现顺序，构建出的merkle tree不唯一，那么算出的root hash也不一样。
为什么比特币中不排序没有问题？比特币中每个全节点收到交易的顺序也不一样，但是比特币是每个节点在本地组装一个候选区块，这个节点自己决定哪些交易要被打包到这个区块里，以什么样的顺序打包，然后去挖矿竞争记账权。只有抢到记账权的才说了算，也就是顺序是发布这个区块的节点确定的，所以这个顺序就变成唯一的了。如果以太坊中也要这么做，需要把账户的状态发布到区里。但是要发布的是所有账户的状态，不是一个区块的交易，相差好多数量级。
那以太坊使用sorted merkle tree就没问题吗？不。如果我们新增一个账户，账户地址是随机的，很可能是插在中间的，那么后面这些树的结构都得变化。代价还是太大。
注：区块链里删除是难度比较大的，其不可篡改性使得往里添东西容易，但删东西难。以太坊中没有显式地删账户的操作。

先讲一个数据结构trie（字典树/前缀树），trie是从retrieval(检索)来的，主要用于存储字符串。是一种key value的store，一般key是字符串比较多。例子：

Trie的结构特点：在trie当中，每个节点的分支数目取决于这个节点的key值里每个元素的取值范围。这个例子中，每个都是小写英文单词，所以每个节点的分叉数目(branching factor)最多是26个，加上一个结束标志位，表示到这个地方这个单词结束。
Trie的优点：
1.以太坊的地址是表示成40个16进制的数，所以分叉数目为17(0~f);（比特币与以太坊的地址是不通用的，两个地址的格式、长度都不一样，类似的一点是：以太坊中的地址也是公钥经过转换得来的 {其实是公钥取哈希，截掉前面一部分，只要后面一部分} ）
2.trie的查找效率取决于key的长度，键值越长，查找需要访问的次数就越多。在以太坊中，所有的key都是长度40，长度一致；
3.前面提过，如果用哈希表来存储，可能出现哈希碰撞，地址不同映射的值相同，即x≠y，但H(x)=H(y)。在trie中，不可能出现碰撞，地址不同，分支必然不同
4.Trie只要输入不变，不管输入的顺序如何，最后得到的字典树不变。
5.每发布一个区块，系统中绝大多数账户是不变的，只有少数受到影响的才会变。更新操作的局部性很重要。对trie来说，更新的局部性也很好。
Trie的缺点：存储有点浪费，图中某些节点只有一个子节点，如果能把这些节点进行合并，可以减少存储的开销，同时也提高了查找的效率。
引入：Patricia tree(trie) 压缩前缀树

压缩的好处：直观上，树的高度减少，这样使得访问内存的次数大大减少，效率提高。
对于patricia tree，如果加入一个路径，原来压缩的内容可能需要扩展开来。
路径压缩在树中插入的键值分布比较稀疏的情况下比较有用。

这样结构效率很低；

这样改进后就能够改善很多。

以太坊中是键值是地址(160位)，也就是2160，非常稀疏，越稀疏越不易碰撞。以太坊产生账户与比特币类似，在本地创建一个公私钥对即可，所以为了避免碰撞，要地址尽可能长。所以适合用Patricia tree(PT).
MPT：Merkle Patricia Tree.
MPT与PT的区别：把普通指针换成哈希指针。
所有的账户组织成一个Patricia tree，用路径压缩提高效率，然后把普通指针换成哈希指针，这样就能计算出一个根哈希值。这个root hash 也是写在block header里的，以太坊的块头有3个根哈希值，以太坊中也有一个由交易组成的交易树。
根哈希值作用：1.防止篡改 2.Merkle proof ，这个树可以证明你有多少钱。3.证明某个账户不存在
怎么证明自己账户上有多少余额？将自己的账户所在的分支自顶向上形成一个Merkle proof发给轻节点，轻节点就可以验证你账户上的余额。
A给B转账之前，A想验证全节点里有没有B这个账户信息，如何验证？（或者说，能不能证明MPT中某个键值是不存在的）：证明方法类似缩进Merkle tree，如果存在应该是什么样的分支，把这个分支作为Merkle proof发过去验证。
以太坊中用到的是modified MPT，是对MPT进行了一些修改得到的。

状态树例子：右上角有4个账户，为简单起见，这4个账户的地址都比较短，假设为7位地址。账户状态只显示了余额，其他未显示。
树种的节点分为3种：extension node（如果这个树这个部位出现了压缩，就会有一个extension node）。
观察4个地址，开始都是a7，所以根结点就是一个extension node。表格中的shared mibble(s)，mibble就是16进制数的意思，1 mibble = 4 bits。
从地址的第3位开始出现分叉，也就跟着一个branch node；然后再跟着一个leaf node等等。

这里面有extension node，branch node， leaf node，与MPT不太一样，就是modified MPT。注意，根结点取哈希得到的root hash要写在块头里。
每次更新，原来的状态是保留的，新的账户再进行新的创建。



这个例子里显示了两个区块，里面的state root就是根哈希值，右边是新的区块的状态树。可以看到，虽然每个区块有一个状态树，但这两棵树的大部分结点是共享的。右边的树大部分是指向左边的树的结点，只有那些发生改变的结点需要创建新的分支。
从图中可以看出有code、存储状态，故是合约账户。也就是合约账户的存储也是用MPT保存。存储是什么：其实也是一个key-value store，维护的是变量到变量取值的映射，在以太坊中也是用一棵MPT。所以以太坊中的这个结构，是一个大的MPT包含许多小的MPT,每一个合约账户的存储都是一个小的MPT。
回到例子，这个账户的nonce和balance都发生了变化，code不变，所以指向了原来树中的结点，存储变了，但存储树中大部分结点也没有改变。这个例子中，可以看到存储中一个整数变量从29变为45，所以新建了一个分支。
所以，系统中的每个全节点不止维护1个MPT,而是每出现一个区块，都要新建一个MPT,只不过这个状态树中大部分节点是共享的，只有少数发生变化的节点要新建分支。

为什么要保留历史状态？系统当中有时会出现分叉，临时性的分叉是很普遍的。假设有一个分叉，假设上面的节点胜出，下面的节点需要进行回滚(roll back)，也就是取消掉当前状态，退回到是一个状态，然后再沿着上面那条链继续。所以保留历史状态就是为了回滚。比特币的简单的转账交易要回滚比较容易推算，但在以太坊中，因为有智能合约，如果不保存以前的状态，想要推算以前的状态不可能。

状态树中保存的是(key,value)，这个账户的状态是怎么存储在状态树中的呢？实际上需要经过一个序列化的过程，利用RLP(Recursive Length Prefix)这种做序列化的方法（特点：简单，极简主义）。
Protocd buffer(protobuf)：一种常用的做序列化的库，与之相比RLP的理念就是越简单越好。RLP只支持一种类型:nested array of bytes,说白了就是字节数组，用一个个字节组成的数组，可以嵌套。
以太坊中的所有其他类型（如整数、哈希表）最后都要变成nested array of bytes。