PKU - Blockchain - Lecture 6

以太坊的新特点（相比于 Bitcoin）

以太坊（Ethereum）加密货币的存在机制是 memory hard mining puzzle。

共识机制演进：从早期的 PoW（工作量证明）转向更环保的 PoS（权益证明），通过质押 ETH 参与验证，能耗降低99%以上。

智能合约（smart contract）的出现：Bitcoin 的初衷是 decentralized currency ，Ethereum 加入了 decentralized contract 的功能。
智能合约是以太坊的核心创新，它是一种存储在区块链上的可编程代码，能够自动执行预设条件（如自动转账、资产交割等）。例如，租赁合约可自动扣除租金并释放数字钥匙。

Bitcoin 通过密码学、PoW 代替政府（发币机关）实现了对于货币应用体系功能的保障，Ethereum 的智能合约也是类似：想办法用技术手段用编程语言实现合约内容，量化合约里的条款，代替司法手段对合约的保障（部署在区块链上，通过区块链的不可篡改性来保证代码的运行）。

在跨国业务（转账、合约）问题上，现有世界的流程很麻烦。去中心化的、不可篡改的代码很方便，且不会说谎，这也是 Bitcoin 和 智能合约的意义。

以太坊的账户

在 Bitcoin 中，用户比特币的数量是通过对 UTXO 的计算得到的（transaction base）。对隐私性起到了很好的保护，但是与日常使用习惯不同（不能显式的看到余额，花钱的时候还要说明清楚来源，以及下图中提到的一笔钱要“一次性花完”，剩余需转给自己的另一个账户）。
Bitcoin 中没有显示的维护基于账户的一些功能，它是每一个交易单独处理的。

以太坊采用的是和现实生活中相似的“银行账户”（count base） 。这种模式可以防范 double spending attack，但也引入了 replay attack（重放攻击）。防止重放攻击的方式也很简单，只需要将交易内容加入一个 nonce（该账户从古至今已经发起过多少个交易了），并且对整个交易内容附上交易发起人的签名保护即可。

以太坊中的账户分为外部账户（externally owned account）和合约账户（smart contact account）两类。
外部账户记录 balance 和 nonce。
合约账户记录 code 和 storage。
所有交易只能由外部账户发起。合约账户可以调用另外一条合约。

以太坊采用的新模式，主要是为了契合智能合约（合约需要签订的双方的身份确定且稳定）。

以太坊的数据结构 - 状态树

以太坊中账户的地址是一个 160 bits 的数字，通常用 20 个 16 进制数字表示。现在想要一个结构能够保存所有用户的 账户地址-状态 键值对。
经过对以太坊各个部分性质的分析，发现 Hash Table 和 Merkle Tree 都不能很好的被使用。
引入 Trie 树的结构，发现该结构很适用于以太坊的情形（修改只修改局部性的问题、建树唯一性的问题、不会重复的问题、且分支数固定）。
但是容易消耗一些空间（在一些选择很少的地方需要考虑所有的可能性），在此基础上优化数据结构，提出 Patricia Tree（Trie），是一个经过路径压缩的前缀树（大大减少树的高度，减少内存访问次数）。

键值分布稀疏的时候，路径压缩的效果更好。

Merkle Patricia Tree（MPT）：所有的账户组成一个 Patricia Tree，用路径压缩提高效率，把普通指针换成哈希指针。
以太坊使用的是 Modified MPT。

系统中每次新出现一个区块，就需要新建一颗 MPT。但不同区块之间的树大部分是共享的，只有部分有改变的地方需要新建一部分树。
新建而不直接修改的目的是，以太坊中出块时间很快，可能会出现区块回滚（roll back）的操作，所以需要记录历史状态。

以太坊区块链中 block header 在程序层面上的结构：

区块的结构：

账户的状态需要经过序列化（RLP：Recursive Length Prefix）后再存储。

以太坊的数据结构 - 交易树与收据树

与 Bitcoin 相似，每次发布一个新区块时，该区块中的交易都会形成一颗 MPT，即交易树。
每个交易完成之后，都会形成一个收据，同理构成一颗收据树。引入收据树的原因是加快智能合约中查询执行结果的速度。
对于状态树来说，MPT 的键是账户的地址；对于交易树与收据树来说，MPT 的键是该交易在区块中的序号。

交易树与收据树最简单的应用就是为某笔交易提供 Merkle Proof。
以太坊中引入了 Bloom Filter 这个数据结构，用来支持快速查找某个元素是否在一个规模很大的集合里。

Bloom Filter 的本质是将集合中的元素通过哈希函数，映射到一个向量的某个位中（将哈希结果对应的某一位设置成1）。不难发现该结构对于 nonmembership 的正确性是 100% 的，但对 membership 的正确性不是（因为可能会出现哈希碰撞）。
且该结构不支持删除操作。

在以太坊中，每个交易完成后会生成一个收据，收据中包含一个 Bloom Filter，记录交易的类型、地址等其他信息。
发布的块的块头中也存储了一个 Bloom Filter，是这个区块所有包含交易的 Bloom Filter 的并集。
这样在想要查找智能合约所涉及到某些性质的交易时，可以先去找块中 Bloom Filter 符合性质的块，然后再去块中进行具体的确认。
这样通过 Bloom Filter 能快速过滤大量的无关区块及其包含的交易（轻节点只有块头信息，通过初筛之后再问全节点进行进一步的信息查询）。

每个全节点都在本地保存自己的这三颗树，智能合约过程中任何对账户的修改都是在改本地的数据结构，只有在合约执行完了，发布到区块链上后，这个更改才是可见的，才能变成区块链上的共识。