北京大学肖震老师《区块链技术与应用》ETH_16

北京大学肖震老师《区块链技术与应用》ETH_16 比特币和以太坊有不同的模型

比特币：

BTC系统是一个基于交易的账本。 系统不显示账户中记录了多少钱。 只能通过UTXO来估算。 但在实际使用中，使用起来比较别扭。

A向B转账时，需要说明币种的来源。 实际操作中，只需要省钱说明出处，不需要花钱。 另外，账户里的钱花的时候，一定要一次性花完。

以太坊：

以太坊系统使用基于账户的模型，类似于现实中的银行账户。 系统显示并记录每个账户中的以太币数量。 转账是否合法只需要检查转账方账户中是否有足够的Ether，并不需要每次都转完所有的钱。 同时，也自然而然地防止了双花攻击。

当然，以太坊开发的这种模式也有缺点。 这种模式存在重放攻击的缺陷。 A转账给B，过了一段时间，B重新发布了A的交易，导致A的账户被扣了两次。

为了抵抗这种重放攻击，引入了一个nonce（实际上应该是一个数字）来记录交易次数

以太坊系统中存在两类账户：

外部账户：类似于BTC系统中的公私钥对。 有账户余额balance和counter nonce

合约账户：不受公私钥对控制。 （不能主动发起交易，只能在接到外部账户调用后发起交易或调用其他合约账户）除了balance和nonce，还有code（代码）、storage（相关state-storage）

创建合约时会返回一个地址，知道地址就可以调用合约。

ETH 状态树

前言：以太坊一共有三棵树，首先介绍一下状态树（与账户余额相关）

数据结构

首先，我们需要实现账户地址到账户状态的映射。 在以太坊中，账户地址为 160 个字节，用 40 个十六进制数表示。 状态包括余额（balance）、交易数量（nonce），合约账户还包括代码（code）和存储（stroge）。

思考：直观地来看，其本质上为Key-value键值对，所以直观想法便用哈希表实现。若不考虑哈希碰撞，查询直接为常数级别的查询效率。
但采用哈希表，难以提供Merkle proof(BTC数据结构篇中有对Merkle proof的介绍，还记得是什么吗？)。

那么如何组织数据结构呢？

我们能否像BTC中，将哈希表的内容组织为Merkle Tree？

但是当一个新的区块发布时，哈希表的内容会发生变化，重新组织成新的Merkle Tree？ 如果是这样的话，每产生一个新区块就必须重新组织Merkle Tree（ETH中一个新区块的产生时间大约是10s），显然这是不现实的。

需要注意的是，比特币系统中没有账户概念，交易由区块管理，区块包含的交易上限约为 4000 笔，因此 Merkle Tree 不会无限增长。 在ETH中，Merkle Tree是用来组织账户信息的，很明显它会越来越大。

实践中，只有一小部分数据发生变化，每次重建Merkle Tree的代价很大

那我们不要哈希表了，直接使用Merkle Tree，每次修改只需要修改其中一部分即可，这个可以吗？

实际上，Merkle Tree 并没有提供高效的搜索和更新解决方案。 此外，所有的账户都构建成一个大的Merkle Tree，必须对其进行排序，以保证所有节点的一致性和搜索速度。

那么经过排序，使用Sorted Merkle Tree可以吗？

新添加的账户，由于其地址是随机的，插入Merkle Tree时很可能处于树的中间，发现后必须重建。 因此，Sorted Merkle Tree 的插入和删除（实际上可能不删除）的成本太高了。

既然没有哈希表和Merkle Trees比特币的数据结构，那么我们来看看以太坊实际采用的数据结构：MPT

一个简单的数据结构——trie(字典树、前缀树)

下面是一个由5个词组成的trie数据结构（只画出key，不画出value）

如图所示：

特征：

trie中每个节点的分支数取决于Key值中每个元素的取值范围（图中最多26个英文字母分支+一个结束标志）。 Trie 查找效率取决于键的长度。 在实际应用中（以太坊地址长度为160byte）。 理论上hash会发生碰撞，但trie不会发生碰撞。 给定输入，无论插入顺序如何，构造的trie都是相同的。更新操作的局部性更好

缺点：

Trie 存储浪费。 很多节点只存储一个key，而他们的“儿子”却只有一个，太浪费了。 因此，为了解决这个问题，我们引入Patricia树/trie Patricia trie

Patricia trie 是具有路径压缩的 trie。 如上例所示，进行路径压缩后，如下图所示：

需要注意的是，如果插入了一个新词，可能需要对原来的压缩路径进行扩展。 那么，应该在什么情况下路径压缩效果比较好呢？ 当树中插入的键值分布比较稀疏时，可以看出路径压缩效果较好。

在以太坊系统中，有 2^160 种 160 位地址。 这个数字其实很大。 与账户数量相比，可以认为地址的键值非常稀疏。

因此，我们可以在以太坊账户管理中使用帕特里夏树数据结构！ 但实际上，以太坊中使用的并不是简单的PT（Patricia tree），而是MPT（Merkle Patricia tree）

MPT（改良帕特里夏树）

以太坊中针对MPT(Merkle Patricia tree)进行了修改，我们称其为MPT(Modified Patricia tree)

下图是以太坊中使用的 MPT 结构示意图。 右上角显示四个账户（为了直观，显示较少）及其状态（只显示账户余额）

每发布一个新的区块比特币的数据结构，状态树中某些节点的状态就会发生变化。 但是改变不是原地修改，而是创建一些分支，保持原来的状态。 如下图所示，只需要修改新变化的节点，其他未修改的节点直接指向上一个区块中对应的节点。

因此，系统中的全节点并不维护一个MPT，而是在每次发布新区块时创建一个新的MPT。 只是大多数节点共享。

为什么要保存原本状态？为何不直接修改？

为了方便回滚。 后面1发生fork，然后上层节点获胜，变成2中的状态，那么后面节点对状态的修改需要回滚。 因此，需要维护这些历史记录。

通过代码看以太坊中的数据结构

block header 中的数据结构

区块结构

区块在网上真正发布时的信息

这块我是真的没看懂（太难了，哭了），看了别人的笔记！ ！ ！