区块链技术与应用04 北大肖臻

ETH-以太坊概述

比特币(区块链1.0)与以太坊(区块链2.0) 之间的差别：

出块时间：BTC，10分钟；ETH：10几秒，为了适应新的出块时间，ETH设计了一套新的基于ghost的共识机制。
挖矿使用的 mining puzzle：BTC，是计算密集型的，比拼的是计算哈希值的算力，造成了挖矿设备的专业化；ETH，对内存要求高，memory hard mining puzzle，目的是一定程度上限制了ASIC芯片的使用(ASIC resistance)。
ETH，用权益证明替代工作量证明 (proof of work rightarrow proof of stake)。
ETH，对智能合约的支持(smart contact)。

比特币(Bitcoin)，去中心化货币(decentralized currency)，单位：1 Satoshi。

以太坊(Ethereum)，去中心化合同(decentralized contract) ，单位：1 wei。

ETH-账户

比特币。基于交易的账本，系统中并没有显式的记录账户有多少钱。假如A转10个比特币给B，需要查询A的10个比特币的来源。

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

以太坊。基于账户的模型(Account -based ledger),系统中记录了每个账户有多少钱。假如A转10个以太币给B，只要查询A的余额够不够就行，没必要说明币的来源。余额也可以留在自己的账户里。

以太坊的模式优缺点。优点：对双花攻击(double spending attack)具有天然的防御,花钱的人不诚实。缺点：重放攻击(replay attack)，收钱的人不诚实。防范：加一个nonce，交易次数，要成为交易内容的一部分。nonce一开始的值为0，每次收到账户的一个交易，nonce加1。

以太坊中的两类账户。

外部账户(externally owned account，也叫普通账户)。有余额(Balance)，有一个计数器(nonce)。
合约账户(smart contract account)。合约账户不能主动发起交易。有代码(Code)，存储(storage)。调用时代码不会变，存储会变。

以太坊智能合约需要保证账户的稳定性。利用智能合约产生一些金融衍生品(financialderivative)，都需要账户的稳定性。

ETH-状态树

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

以太坊中所用的账户地址是160位的，20个节，表示为40个16进制的数。

账户状态是指外部账户和合约账户的状态，包括余额，交易次数(nonce)，代码和存储。

实现什么数据结构完成这个映射？

假设方案：用哈希表来实现。系统中的全节点维护一个哈希表，每次有一个新的账户插入到哈希表里面，查询一个账户的余额直接在哈希表中查询，查询效率是常数级别的。

问题：需要提供merlel proof怎么办？如果签合同，需要证明账户余额怎么办？把这个哈希表的元素组织成一棵merkle tree，算出根哈希值，根哈希值保存在block header，公布出去。

问题：如果有一个新区块发布怎么办？哈希表内容发生变化，需要重新组建merkle tree,这样做代价太大。

问题：比特币系统中每发布一个新的区块也需要重新组织merkle tree，为什么比特币没有问题？比特币每出一个新的区块，也是要重新构建一棵关于自己发布区块中的交易的merkle tree，构建完后是不会再改的。区块里大概包含几百个至几千个交易。而在以太坊中，每发布一个区块，是要将以太坊中所有的账户遍历一遍，构建merkle tree。并且除了要证明账户中有多少钱外，还要维护各个全节点状态的一致性。代价太高。

假设方案：直接将账户构建成一个不排序的merkle tree,不用哈希表。

问题：merkle tree 没有提供一个快速查找和更新的方法。对于merkle tree，叶节点是账户信息，如果不规定叶节点在账户中的出现顺序，那么构建出的merkle tree 不是唯一的，算出的根哈希值也不一样。

问题：比特币中也不排序，为什么没有问题？比特币中merkle tree的顺序是发布这个区块的节点决定的。每个节点在本地组装一个候选区块，自己定顺序，但是最后只有获得记账权的节点说了算。以太坊中发布的是所有账户的状态，不是发布的区块的包含的交易，差好几个数量级。

假设方案：直接将账户构建成一个排序的merkle tree,不用哈希表。

问题：新增一个账户怎么办？插入代价太大，可能需要重新构建整棵merkle tree。输出的话，一般不删。

一个简单的数据结构字典树(trie)

trie 的结构。

单词有可能在这个trie结构的中间节点结束，如 Go。

trie的优缺点。

优点。

trie中每个节点的分支数目取决于这个key值里每个元素的取值范围。上面的例子，每个都是小写的英文单词，每个节点的分叉数目最多为26个，加上一个结束标志位。以太坊中地址被保存成40个16进制的数，分叉数目(branching factor)为17个，0-f加一个结束标识符。
trie的查找效率，取决于key的长度。键值越长，访问内存的次数越多。键值都为40。
哈希表存在哈希碰撞的可能性，trie只要地址不一样，不存在碰撞。
给定一组输入，顺序不影响trie的结构。
更新操作的局部性。

缺点。存储浪费。

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

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

Misunderstanding

Decentralization 去中心化

Disintermediation 去中间商（intermediaries中间商）

用trie结构，效率很低。

使用patricia tree时，效果很明显。键值分布比较稀疏的时候，路径压缩效果好，patricia tree效果好。

以太坊地址范围 2^{160} ,非常稀疏。以太坊中外部账户就是自己创建一个公私钥对，为了防止和别人碰撞，所有地址空间非常大。

MPT(merkle patricial tree)

MPT和patricia tree的区别，把普通指针换成了哈希指针，可以计算出一个根哈希值，保存在 block header 中。现在讲将账户状态组织起来构成一个MPT。

根哈希值的作用：1.防止篡改。2.可以证明账户余额是多少。账户所在分支自底向上作 merkle proof 发给轻节点。轻节点可以验证余额多少钱。3.证明一个账户不存在(证明MPT中某个键值不存在)。

modified MPT(以太坊中)

有extension node ，branch node，根节点取哈希值要写在块头里。

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

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

以太坊把出块时间降到10几秒后，临时分叉是常态。上面的胜出了，下面的回滚。靠这些历史记录。比特币中只是简单的转账交易，回滚很容易。但是以太坊中智能合约很强，要想回滚必须保持历史状态。

block header 的数据类型。

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

UncleHash：叔父区块的哈希值。uncle可能比parent大几个辈分。

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

Root：状态树的根哈希值。

TxHash：交易树的根哈希值。

ReceiptHash：收据树的根哈希值。

Bloom：提供一种高效的查询符合某种交易的执行结果。

Difficulty：挖矿难度。

GasLimit，GasUsed：智能合约要消耗汽油费。

MixDigest：Nonce经过一些计算算出的哈希值。

区块的结构。

header：指向上一个区块的指针。

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

transactions：区块中的交易列表。

真正发布出去的区块。

状态数中保存 (key,value),也就是 (账户地址，账户状态)。

账户状态经过序列化后再存储。RLP（Recursive lengthprefix）序列化，极简主义，越简单越好。

一个很有名的做序列化的库

RLP只支持一种类型，字节数组(Nestedarray of bytes)，实现RLP比实现Protocol buffer容易得多。

以太坊中的所有数据类型最后都要变成字节数组(Nested array of bytes)。

ETH-交易树和收据树

每次发布一个区块，区块中的交易构成一个交易树(MPT),和比特币中类似。

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

交易树和收据树只是把当前区块中的交易和收据组织起来，而状态树是要把系统中所有账户的状态都包含进去，不管账户和当前区块是否有关系。

bloom filter数据结构。查找某个元素是否在某个比较大的集合里面。

给大的集合，包含很多元素的集合，计算出一个很紧凑的摘要。

向量初始化为0。把每一个元素都取哈希，找到向量中的对应位置，改成1 。所有元素都处理完得到的向量就是原来集合的一个摘要。摘要比原来的集合小很多。有可能出现误报(false positive),哈希碰撞，但不会出现漏报(false negative)。可以用一组哈希替代一个哈希，哈希碰撞概率变低。

如果从这个集合中删除一个元素，该怎么操作？没法操作，不支持删除。把a删除，如果改为0的话，可能存在哈希碰撞，是别的元素哈希后也在这个位置。

每个交易执行完之后会形成一个收据，这个收据里面包含一个bloom filter，记录交易的类型，地址等相关信息。发布的区块在它的块头里也包含一个总的bloom filter，总的bloom filter是这个区块里所有交易的bloom filter的一个并集。

查找过去10天和这个智能合约相关的所有交易，怎么找？先查找每个区块的块头的bloom filter是否有我要的交易的类型，如果块头里没有，则知道这个区块不是我们想要的。如果存在，则查找这个区块里面包含的交易对应的收据的bloom filter，如果有，找到对应的交易。好处：快速过滤掉无关的区块。根据轻节点块头就能过滤到很多区块了，剩下的再去向全节点要详细信息。

交易驱动的状态机(Transaction-driven state machine)。

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

状态树可否设计成只包含这个区块涉及的交易的账户的状态而不是全部账户的状态？

A转账给B10个以太币，要检查A的账户里是否有10个以太币，如果A很久没转账了，得往前推很多次才能找到A最近一次的账户状态。如果B是新建的账户，你要查询B的账户，要从当前区块扫描到创世纪块发现没有这个账户。

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

在NewBlock函数里面创建了交易树和收据树。

交易树的代码，首先判断交易列表是否为空，为空的话，那么这个区块块头里交易树的根哈希值就是一个空的哈希值，否则的话，通过调用DeriveSha函数来获得交易树的根哈希值。然后创建区块的交易列表。

中间这段代码是收据树的创建代码，首先判断收据列表是否为空，为空的话，那么这个区块块头里收据树的根哈希值就是一个空的哈希值，否则的话，通过调用DeriveSha函数来获得收据树的根哈希值。然后创建区块块头的的bloom filter。交易列表的长度和收据列表的长度是一样的。

下面这段代码处理叔父区块，通过一个循环构建出区块里的叔父数组。

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

trie的数据结构是MPT。

CreateBloom函数的参数是这个区块的所有收据，for循环对每个收据调用LogsBloom函数生成这个收据的bloom filter，用Or操作合并起来得到整个区块的 bloom filter。

bloom9 是bloom filter中使用的哈希函数，这里把输入映射到digest中的三个位置，也就是把三个位置都置为1。首先使用crypto里面的函数生成256位的哈希值，b是一个32个字节的哈希值。r是我们要返回的bloom filter，这里把它初始化为0。前面生成的32个字节的哈希值，取前6个字节，每两个字节为一组，拼在一起，and 2047，得到一个0到2047之间的树，以太坊中bloom filter是2048位。把1左移b位，通过Or合并到上一轮得到的 bloom filter里。通过三轮循环，把三个位置设为1。

怎么查询bloom filter里是否包含了我们感兴趣的 topic呢？

ETH-GHOST

以太坊10几秒的出块时间，分叉情况会成为常态，分叉数目也会变多。没有成为最长合法链的区块就白挖了，叫做orphan block或者staleblock，在以太坊中，辛辛苦苦挖出的区块很大概率白挖了，对个体矿工不公平。

矿池(mining pool)挖出最长合法链可能性更大。也就是说矿池获得收益比比它所占的算力比要大。造成mining centralization。这种情况叫做 Centralization bias，中心化带来的不成比例的优势。

比如：出现一个三分叉，上下两个区块是个体矿工，中间是矿池，矿池会沿着自己的区块往后挖，挖出最长合法链可能性更大。并且大型矿池挖出的区块可能更早被其它节点知晓。

以太坊采用基于GHOST协议。

最初的GHOST协议。作废的区块叫做uncle block。挖到矿最后没有被认可，也能得到一定的好处，当前最长区块包含这个叔父区块，它可以得到7/8×3个奖励。现在出块奖励是3个。最长区块如果包含叔父区块，可以获得1/32×3额外的出块奖励,总共 1/32×3 3。一个区块最多可以包括两个叔父区块。八分之七的奖励实际上是很高的，这样做有利于出现分支后尽快合并。