Blockchain-2


Blockchain(2)

在本节中, 我们主要会针对 以太坊 这一另一个主要的加密货币进行说明.

仍然需要写在前面, 本文主要基于 《区块链技术与应用》(北京大学 肖臻教授) 的课程进行笔记整理与内容扩展, 文中除开视频内容外,也会涉及到一些博主自己的思考, 烦请读者理性看待. 在此也附上视频链接(https://www.bilibili.com/video/BV1Vt411X7JF?p=1&vd_source=4565edcb254cb6582d6382ac80011294), 有了他们的工作, 才能让区块链这一技术为更多人所知.

在此对 肖臻教授 以及 北京大学相应课程组 表达诚挚的敬意与感激!

Part.1 以太坊概述

以太坊(Ethereum) 对于比特币中出现的各种问题进行了更为针对性的改进, 包括但不限于 出块时间 / 谜题设计 / 共识协议 等等方面.

与此同时, 以太坊相对于比特币的最显著的该进, 在于 智能合约(Smart Contract) 的提出.


为什么要提出智能合约?

在BTC时代, BTC实现的最重要的成就是它达成了一个真正的 去中心化的货币政策(Decentralized Currency) , 比特币通过技术手段取代了一部分本该通过政府来保证的公信力; 人们看到了BTC的成功, 并希望将这种去中心化的思路推而广之(If we can decentralize currency, what else can we decentralize?), 以太坊在此基础上设计出了 去中心化的合约设计(Decentralized Contract) , 智能合约类似地通过技术手段, 取代了一部分原本应当由司法机关来保证的合约公信力.


Part.2 账户

2.1 以太坊中的账户模型

在比特币中, 账户仅仅是一个 <公钥, 私钥>对, 这意味着账户十分容易创建, 而且一个人可以很轻松地拥有多个账户. 同时一个账户中的余额需要通过查询 UTXO 才能真正得知(比特币是基于交易的账本: Transaction based ledger).

这种方法的好处在于隐私性的保护较强, 但同时也意味着交易过程中有了很多麻烦 (用户自己可能都说不清我有多少钱, 更别提别人了)

典型的麻烦在于, 当一个用户(我们后文称之为用户1)希望向另一个人转账时, 他必须将他此前参与交易的输出(相当于此前转到自己一个账户上的钱)全部花出去(这代表着假设交易金额与输出金额不等, 则用户1必须单独再创建一个账户来接受找零, 详情请见上一个章节的11.1). 显然, 这相当的别扭.

在以太坊中, 采用了传统的 基于账户的模型(Account Based Ledger) , 这代表着系统上必须显式记录每个账户上有几个ETH. 此时要检测交易是否合法, 则只需检查转账账户上是否有足够的金额即可, 无需像比特币一般说明金额的具体来源.

这种模型对 双花攻击(Double Spending Attack) 有天然的防御作用, 因为交易必定需要扣除余额.


重放攻击(Replay Attack)

重放攻击指的是 收款人 在收到付款人的交易请求后, 正常接收这个交易, 但在后续过程中再次向交易网络中重新转发这个交易, 达到让自己多次收款的目的.

以太坊采用的账户模型对于重放攻击是需要单独进行防护的, 以太坊对每个账户单独设置了一个域nonce, 表示 这个账户的总交易数 , 如果收款方重放该交易, 会由于总交易数nonce相同而被无恶意的节点拒绝.


2.2 账户的分类

以太坊中含有两类账户:

  • Externally owned Account: 也称外部账户(或普通账户), 这种账户很类似比特币中的账户, 利用公私钥控制. 这种账户的状态值包括:
    • Balance: 账户余额
    • nonce: 账户交易总数(类似计数器)
  • Smart contract Accound: 也称合约账户, 合约账户不是通过公私钥进行控制的, 同时合约账户也不能主动发起交易, 这代表着它涉及的所有交易都是由外部发起的, 同时每调用一次合约账户会导致其存储内的某些特定状态值发生变化. 其状态值包括:
    • Balance
    • nonce
    • code: 代码
    • storage: 存储(其他额外的状态值)

后续我们会进一步对上面的各种状态进行说明, 读者在这里不必过于纠结它们的用途.

2.3 为什么是 账户模型 ?

以太坊为什么要改用 账户模型 ?

当然, 交易更方便, 速度更快是理由之一. 但更本质的原因, 在于以太坊创建的系统是 智能合约系统 , 而合约的根本, 在于交易双方必须要 保持稳定 , 想比特币那样收一笔钱换一个地方的做法在合约中显然是行不通的.

Part.3 数据结构

3.1 状态树

谈完了模型, 我们来说说实现方式.

我们需要实现的, 是一个从账户地址(Address)到账户状态(State)的有效映射. 在以太坊中, 账户地址是一个160bit的二进制数, 我们一般将其表示为40个16进制数.


我们先来排除一个错误选项: Merkle Tree 能当此任吗?

答案是否定的. 有两个原因.

首先, 我们如果通过哈希的方式将 以太坊中所有的账户 组织在同一颗 Merkle Tree 中, 会导致任何账户信息更新的操作的开销都十分庞大. 因为 Merkle Tree 这玩意通过哈希指针连接双亲结点与孩子节点, 因此牵一发而动全身, 而所有账户一起组成的 Merkle Tree , 实在是太大了.

其次, 比特币中能够采用 Merkle Tree 的原因在于 Merkle Tree 仅存在于一个区块中, 它仅仅组织一个区块内的交易排列, 以及包含的交易信息. 这个过程有一个很明确的 共识源头 即获取到记账权的那个节点(挖到这个区块的矿工). 但如果以太坊的账户管理仍然套用 Merkle Tree , 这个共识源头就不好找了, 意味着让所有节点形成共识的难度也过高.

因此, 我们排除利用 Merkle Tree 来存储账户信息的想法.


3.1.1 Trie(字典树)

我们揭晓以太坊的数据结构之前, 先来说说这个简化的数据结构: Trie(字典树) .

In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set.

Trie

这种数据结构, 就是专门用于通过关键字来进行数据查找的. 通过例子也能够看出, 一般而言这种查找是通过字符串进行的.

提到字符串, 我们想一想能跟以太坊建立起什么联系?

前面提及到的, 以太坊的地址是160bit的二进制数, 而我们通常使用 40位16进制数 来表示. 这意味着, 如果使用Trie进行存储, 算上字符串结束符, 每个节点 最多 能够衍生出 17个分支 , 树的 深度 固定为 41.

Trie_complexity


Trie相比于Merkle Tree有什么好处?

上图中, 我们发现对于Trie, 搜索, 插入, 删除的时间复杂度都取决于字符长度, 而我们这里字符长必定是40. 显然, 相比于 Merkle Tree , Trie的各种操作效率可高太多了.

此外, 不论怎么打乱重排给入这颗 Trie, 最后构造出的Trie应当是一样的, 因为Trie是根据字符串本身进行插入操作的.

最后, 当这棵Trie需要更新时, 也不用访问其他分支, 不用遍历, 只需要根据给定地址访问指定分支即可, 即更新局部性控制的很好.


按理来说, Trie已经挺不错了, 但人们还是不满足, 人们觉得查找效率还是不够高.

对于上面的例子而言, 像 inn 这样的节点, 我还需要找三次才能找到它, 但它过程中没有什么分支, 那我能不能再度简化查找过程?

3.1.2 Patricia Tree(路径压缩前缀树 / 压缩前缀树)

Patricia Tree(Trie) , 也称路径压缩前缀树(字典树) , 是一种在传统字典树上对于单一路径进行进一步压缩的前缀树.

我们给出一个路径压缩的例子:

Patricia_trie

这样的好处在于: 树的深度显著减少了, 查找花费的时间更短了.

当然, 我们也需要明确, 路径压缩也意味着需要插入新单词的时候可能涉及到更复杂的 路径拆分操作 . 同时, 路径压缩只在数中插入键值分布比较分散的时候比较有效.(举例而言, 单词很长, 但总数并不多时), 当键值分布过于密集, 意味着可供压缩的路径较少, 则这种方法与传统字典树的效率差的并不多.

当然, 我们这里只需要考虑这160位地址, 即以太坊的地址总空间有 $ 2^{160} $ 次方这么大, 这是个天文数字, 我们的地址分布也因此及其稀疏. 因此采用路径压缩的方式的效果还是很不错的.

3.1.3 Merkle Patricia Tree(梅克尔路径压缩前缀树 / MPT)

我们继续向下, 现在我们成功的将这棵树压缩了一下, 理论上讲, 相比于此前的Trie, 采用Patricia Tree的树应该要精简许多, 那我们现在想想, 是否能将这棵树中的指针换成哈希指针呢?

当然可以, 这正是我们现在的主流做法. 我们最终可以将这棵树的根哈希值放入块头中, 用于保证整棵树没有被改变过, 同时, 要查找时, 我们可以利用Patricia Tree的特点, 通过前缀快速查找到一个节点是否存在.


读者读到这里可能会有疑问, 为什么之前Merkle Tree行不通, 现在就突然能成了?

我们思考我们上面这一系列流程干了些啥: 我们通过用户地址将每个账户进行了标识, 明确了要利用 字典树 的性质来进行查找, 这保证了状态树查找时的效率; 我们通过 路径压缩 , 在以太坊的用户地址分布及其分散的情况下, 极大程度上降低了树的深度和宽度, 这保证了树的大小不会太大; 我们利用 梅克尔树 的性质, 在指针上附加哈希值, 保证了树的不易篡改性.

因此, 事实上, Merkle Patricia Tree 是一种对 数据完整性 / 存储效率 / 查找效率 的平衡.


我们此前在以太坊的账户章节(2.2)中提及: 以太坊中存在两种账户, 普通账户合约账户 . 事实上, 这两种账户需要存储的内容不尽相同, 因此用于存储它们账户状态的 MPT 结构自然也不同.

那这两种账户是怎么同步在全球的以太坊树中的呢? 答案是, 通过我们前面提到的账户地址.

全球的以太坊树是一颗大的MPT, 它其中的每个叶子节点都是一个账户的地址, 这个地址指向一颗小的MPT. 至于指向的是哪种MPT, 则根据账户本身的类型来决定(普通账户MPT / 合约账户MPT).

因此, 以太坊的MPT存储方式是分级存储的.

这也代表着修改的便利性, 当一个新区块被添加到区块链中, 需要 根据全球MPT找到区块内所有涉及到的账户MPT -> 修改对应的账户MPT 即可完成操作, 其他不涉及到的内容可以原封不动的搬过来.

相对应的, 在修改账户MPT时, 也只需要寻找到需要修改的变量, 修改之, 即可. 不需要整体重新建立.

3.1.4 Roll Back

我们会发现, 以太坊中每个区块都要维护一个全局状态树和很多的个人账户状态树, 这看起来好像很浪费? 为什么要这么设计?

不同于比特币10分钟的出块时间, 以太坊的出块时间非常快, 接近15s. 这意味着很有可能产生临时性的分叉, 直到某一个分叉胜出后, 其余分叉才被判定为 Orphan Block 而被淘汰. 现在我们想一想, 当某一个节点所正在接受的分支被淘汰了, 它们应当怎样转到正确的分支上?

他们需要先进行 回滚操作(Roll Back) , 随后才能沿着新链条继续下去, 但这个回滚操作应当如何进行?

这就用到了此前区块中保存的状态树, 由于以太坊智能合约的存在, 以太坊的交易类型极大的复杂化, 因此必须要保存此前区块的全部状态树以保证 回滚的准确性 .

3.1.5 Key-Value Pair

我们倒腾了这么半天, 状态树这东西到底里面是什么?

说说白了, 就是一个个的键值对.

对于账户状态树而言, 其 键(Key) 就是账户地址的哈希(那个160位二进制数的哈希值, 采用Keccak-256加密算法), 值(Value) 就是该地址对应的账户对象(包括余额 / nonce / {代码哈希} / {存储根} , 利用RLP进行字符数组序列化操作)

RLP(Recursive Length Prefix) 是一种数据编码方法, 目的在于将任意结构的数据进行高效的序列化 / 反序列化操作, 具体序列化完成后体现为字节序列.


文章作者: MUG-chen
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 MUG-chen !
  目录
加载中...