区块链技术与应用04 肖震，北京大学

ETH-以太坊概述

比特币（区块链 1.0）和以太坊（区块链 2.0）的区别：

出块时间：BTC，10分钟； ETH：10秒，为了适应新的区块生成时间，ETH设计了基于ghost的新共识机制。 用于挖矿的挖矿难题：BTC是计算密集型的，竞争的是计算哈希值的算力，导致挖矿设备专业化； ETH对内存的要求很高，内存硬挖难题的目的是为了保证在一定程度上限制ASIC芯片的使用（ASIC resistance）。 ETH，用权益证明代替工作量证明（proof of work \rightarrow proof of stake）。 ETH，支持智能合约（smart contact）。

比特币（Bitcoin），去中心化货币（decentralized currency），单位：1聪。

以太坊（Ethereum），去中心化合约（decentralized contract），单位：1 wei。

ETH-账户

比特币。 基于交易账本，系统不会明确记录账户中有多少钱。 如果A给B转了10个比特币，就要查A的10个比特币的来源。

钱必须一次性转出，余额转入自己的另一个账户。 这有利于隐私保护。

以太坊。 基于账户的分类账（Account-based ledger），系统记录每个账户有多少钱。 如果A转10个ETH给B，只看A的余额是否够用，无需说明币种来源。 余额也可以留在您自己的帐户中。

以太坊模型的优缺点。 优点：对双花攻击有天然的防御能力，花钱的人都是不诚实的。 缺点：重放攻击（replay attack）以太坊私钥碰撞软件，收钱的人不诚实。 预防：添加一个nonce，交易次数，成为交易内容的一部分。 nonce 的初始值为 0，每从账户收到一笔交易，nonce 就加 1。

以太坊中的两种类型的账户。

外部账户（external owned account，也叫普通账户）。 有余额（Balance），也有计数器（nonce）。 合约账户（智能合约账户）。 合约账户不能主动发起交易。 有代码（Code）、存储（storage）。 调用时代码不会更改，存储会更改。

以太坊智能合约需要保证账户的稳定性。 使用智能合约生成一些金融衍生品（financial derivatives）需要账户稳定。

ETH-状态树

完成账户地址到账户状态的映射。

以太坊使用的账户地址为 160 位，20 段，用 40 个十六进制数表示。

账户状态是指外部账户和合约账户的状态，包括余额、交易次数（nonce）、编码和存储。

实现这种映射的数据结构是什么？

假设的解决方案：用哈希表实现。 系统中的所有节点都维护一个哈希表。 每次向哈希表中插入一个新账户时，直接在哈希表中查询一个账户的余额，查询效率处于恒定水平。

问：需要提供merlel证明怎么办？ 签约时需要证明账户余额怎么办？ 将这个哈希表的元素组织成一个merkle树，计算根哈希值，将根哈希值保存在区块头中，并发布。

问题：如果发布了一个新区块怎么办？ 哈希表内容发生变化，需要重新构建merkle树，代价太大。

问：比特币系统每发布一个新区块，都需要重新组织默克尔树。 为什么比特币没有问题？ 比特币每发布一个新区块，还需要重新构建一棵关于其发布的区块中的交易的默克尔树，构建完成后不再更改。 一个区块可能包含数百到数千笔交易。 在以太坊中，每发布一个区块，都需要遍历以太坊中的所有账户以太坊私钥碰撞软件，构建一棵merkle树。 而且除了要证明账户里有多少钱，还要保持每个全节点状态的一致性。 价格太高了。

假设方案：直接将账户构造成无哈希表的未排序默克尔树。

问题：默克尔树没有提供快速查找和更新的方法。 对于默克尔树，叶子节点是账户信息。 如果不指定叶子节点在账户中的出现顺序，则构造的merkle树不唯一，计算出的根哈希值也不同。

问：比特币没有排序，为什么没有问题？ 比特币中默克尔树的顺序是由发出区块的节点决定的。 每个节点在本地组装一个候选区块并自行决定顺序，但最终只有拥有记账权的节点说了算。 以太坊中公布的是所有账户的状态，而不是公布的区块中包含的交易，两者相差几个数量级。

假设的解决方案：直接将账户构建成排序的 merkle 树，无需哈希表。

问：如何添加新账号？ 插入成本太高，可能需要重建整棵merkle树。 如果是输出，一般不会删除。

一个简单的数据结构字典树（trie）

特里的结构。

单词有可能在这个 trie 的中间节点结束，就像在围棋中一样。

trie的优点和缺点。

优势。

树中每个节点的分支数取决于键值中每个元素的取值范围。 上面的例子中，each是一个小写的英文单词，每个节点的分叉数最多为26个，加上一个结束标志。 以太坊中的地址保存为40个十六进制数，分叉数（分支因子）为17，0-f加上一个结束标识。 trie的搜索效率取决于key的长度。 键值越长，内存被访问的次数越多。 key值为40。哈希表有哈希冲突的可能，但只要trie的地址不同，就不会发生冲突。 给定一组输入，顺序不会影响 trie 的结构。 更新操作的位置。

缺点。 存储废物。

压缩前缀树 (patricia tree/trie)。

注意：新插入的值，原来的压缩路径可能会再次展开。

误解

权力下放 权力下放

去中介化中间人（intermediaries middlemen）

使用trie结构是非常低效的。

使用帕特里夏树时，效果很明显。 当key-value分布比较稀疏时，路径压缩效果好，patricia tree效果好。

以太坊的地址范围是2^{160}，非常稀疏。 以太坊中的外部账户是自己创建公私钥对。 为了防止与他人发生冲突，所有地址空间都非常大。

MPT（merkle patricial tree）

MPT和patricia tree的区别在于普通指针被hash指针代替，可以计算出一个根hash值存储在区块头中。 现在让我们将帐户状态组织起来形成一个MPT。

根哈希值的作用： 1.防止篡改。 2.可以证明账户余额是多少。 账户所在的分支作为默克尔证明自下而上发送到轻节点。 轻节点可以验证余额是多少。 3.证明一个账户不存在（证明MPT中的一个键值不存在）。

修改后的 MPT（在以太坊中）

有扩展节点，分支节点，根节点的哈希值要写在区块头中。

显示相邻的两个块，State Root 状态树的根哈希。 系统中每个全节点需要维护的不是MPT，而是每出现一个区块就创建一个新的MPT，但这些状态树中的大部分节点是共享的。 只有少数变化的节点需要创建新的分支。

问题：为什么要保留历史状态？

以太坊将区块生成时间缩短至 10 秒后，临时分叉成为常态。 上胜，下退。 靠这些历史记载。 它只是一个简单的比特币转账交易，很容易回滚。 但是，以太坊中的智能合约非常强大，必须保持历史状态才能回滚。

区块头的数据类型。

ParentHash：上一个区块头的哈希值。

UncleHash：叔块的哈希值。 叔叔可能比父母大几代人。

Coinbase：挖出这个区块的矿工地址。

Root：状态树的根哈希。

TxHash：交易树的根哈希。

ReceiptHash：收据树的根哈希。

Bloom：提供高效查询匹配某笔交易的执行结果。

难度：挖矿难度。

GasLimit、GasUsed：智能合约消耗gas费用。

MixDigest：Nonce经过一些计算后计算出的hash值。

块的结构。

header：指向前一个块的指针。

uncles：指向叔叔级块的指针，一个数组，可能有很多个。

交易：区块中的交易列表。

实际释放的块。

(key, value)保存的是状态号，即(账户地址，账户状态)。

帐户状态在存储之前被序列化。 RLP（Recursive length prefix）序列化，极简主义，越简单越好。

一个著名的序列化库

RLP只支持一种类型，Nested array of bytes，实现RLP比实现Protocol buffer容易得多。

以太坊中的所有数据类型最终都会成为 Nested array of bytes。

ETH - 交易树和收据树

每发布一个区块，区块中的交易就形成一棵交易树（transaction tree，MPT），类似于比特币。

每笔交易执行后，都会形成一张收据，记录交易的相关信息。 交易和收据之间存在一对一的对应关系。 智能合约比较复杂，使用收据树方便我们快速查询结果。

交易树和回执树只是组织了当前区块中的交易和回执，而状态树则是包含了系统中所有账户的状态，不管账户是否与当前区块相关。

布隆过滤器数据结构。 找出一个元素是否在更大的集合中。

计算包含许多元素的大型集合的紧凑摘要。

向量初始化为0。对每个元素进行哈希处理，找到向量中的对应位置，并将其更改为1。处理完所有元素后得到的向量是原始集合的摘要。 摘要比原始集合小得多。 可能存在误报和哈希冲突，但不会出现漏报。 一个哈希可以被一组哈希代替，哈希冲突的概率变低。

如果我从这个集合中删除一个元素怎么办？ 无法操作，不支持删除。 删除一个。 如果改为0，可能会发生哈希冲突，其他元素哈希后也在这个位置。

每笔交易执行后，都会形成一张收据，收据中包含一个布隆过滤器，用于记录交易的类型、地址等相关信息。 发布的区块在其区块头中也包含了一个total bloom filter，total bloom filter是该区块中所有交易的bloom filter的并集。

如何查找过去 10 天内与此智能合约相关的所有交易？ 首先检查每个区块的区块头的布隆过滤器是否有我想要的交易类型。 如果没有区块头，我们就知道这个区块不是我们想要的。 如果存在，则查找该区块包含的交易对应的收据布隆过滤器，如果存在，则查找对应的交易。 好处：快速过滤掉不相关的块。 根据轻节点的区块头，可以过滤掉很多区块，剩下的会去全节点查询详细信息。

事务驱动状态机（Transaction-driven state machine）。

状态转换必须是确定性的。

状态树能不能设计成只包含这个区块涉及的交易的账户状态，而不是所有账户的状态？

A转给B 10个以太币，查看A账户中是否还有10个以太币。 如果A长时间没有转账，需要多次向前推送才能找到A的最新账户状态。如果B是新创建的账户，需要查询B的账户，从当前区块扫描到创世区块，发现没有这个账户。

代码。 创建交易树和收据树的过程。

交易树和收据树是在 NewBlock 函数中创建的。

交易树的代码首先判断交易列表是否为空，如果为空，则区块头中交易树的根哈希值为空哈希值，否则，通过调用DeriveSha获取交易树函数根哈希。 然后为该块创建一个交易列表。

中间的代码是创建收据树的代码。 首先判断收货单是否为空。 如果为空，则区块头中收据树的根哈希值为空哈希值。 否则，调用 DeriveSha Function 获取收据树的根哈希。 然后为区块头创建布隆过滤器。 交易清单的长度与收货清单的长度相同。

下面这段代码是对叔块进行处理，通过循环构造块中的叔块数组。

DeriveSha 函数。 创建的数据结构是一个 trie。

trie的数据结构是MPT。

CreateBloom函数的参数是本区块的所有回执，for循环为每一个回执调用LogsBloom函数生成本回执的bloom filter，并通过Or运算合并得到整个区块的bloom filter .

Bloom9 是布隆过滤器中使用的哈希函数。 这里将输入映射到摘要中的三​​个位置，即三个位置都设置为1。首先使用crypto中的函数生成一个256位的哈希值，b为32字节的哈希值。 r是我们要返回的bloom filter，这里初始化为0。对于前面生成的32字节hash值，取前6个字节，每两个字节分组，放在一起，和2047，得到一棵树0 和 2047，以太坊中的布隆过滤器是 2048 位。 将1左移b位，通过Or合并到上一轮得到的bloom filter中。 通过三个循环，将三个位置设置为1。

如何查看我们感兴趣的主题是否包含在布隆过滤器中？

ETH-幽灵

随着以太坊的出块时间在几秒之内，分叉将成为常态，分叉的数量也会增加。 没有成为最长合法链的块被白挖，称为孤儿块或陈旧块。 在以太坊中，来之不易的区块有很大概率被白挖，这对个体矿工来说是不公平的。

矿池更有可能挖出最长的合法链。 也就是说，矿池的盈利比例大于其占用的算力比例。 造成挖矿中心化。 这种情况称为 Centralization bias，即中心化带来的不成比例的优势。

比如：出现一个三叉，上下区块是个体矿工，中间是矿池。 矿池会沿着自己的区块回挖，更有可能挖出最长的合法链。 而大型矿池挖出的区块可能更早被其他节点知道。

以太坊使用 GHOST 协议。

原始的 GHOST 协议。 无效块称为叔块。 如果最后矿山不被认可，也可以获得一定的利益。 当前最长的区块包含这个叔块，它可以获得7/8×3的奖励。 现在区块奖励为3，如果最长的区块包含叔块，则可以获得1/32×3的额外区块奖励，共计1/32×3+3。 一个块最多可以包含两个叔块。 八进七的奖励其实很高，有利于分支出现后尽快融合。

缺点。 有矿池故意不包含叔叔。

改变。 叔叔的定义扩大了。 祖父母或曾祖父母。 . . 也可以认孙子，曾孙可以当叔块，可以隔代隔代。 如果您不包括其他人。 你可能不是挖下一个街区的人。

缺点：有些人总是挖叔块，期望被包括在内。

变化：现任叔叔7/8奖励，每两代6/8奖励。 . . . . . 1/32 是固定的。 2/8 之前不会再有叔叔了。 只有 6 个叔块（7 代以内），并且没有更多。

如果不限制叔块的数量，全节点维护的状态就太多了。 另一个问题是，该设计最多被 7 代叔块隔开，鼓励分叉尽快合并。

上述协议是为了解决临时分叉。 如果分叉是其他原因造成的（比如协议变更），那么以上方法都无法解决。

两个奖励。

汽油费称为动态奖励，区块奖励称为静态奖励。

叔块不收取汽油费。 以太坊没有规定区块奖励的定期减半机制。

包括叔块，块中的交易是否应该执行？ 无法执行，因为主链中的区块可能包含叔块中的交易。 如果区块检查叔块是否满足挖矿难度要求，则认为是合法的叔块，不检查交易是否合法，因为叔块中的交易没有执行。

如果分叉后还有字符串怎么办？ 分叉攻击变得太便宜了，如果在长链中得到奖励，分叉攻击的风险太小。 分叉攻击失败也有奖励。 不好。

因此，以太坊规定只有分叉后的第一个区块才能获得叔叔奖励（uncle reward）。

叔块奖励的几种形式。

两个block的具体内容。