以太坊数据结构

以太坊数据结构介绍，底层原理

整体架构

区块Block

所谓的区块，其实可以定义为记录一段时间内发生的交易和状态结果的数据结构，是对当前账本状态的一次共识。

区块主要由区块头、交易列表和叔区块头三部分组成：

区块头

区块头包含：父块的散列值（ Prev Hash ）、叔区块的散列值（ Uncles Hash ）、状态树根散列值（ stateRoot ） 、交易树根散列值（
Transaction Root ） 、收据树根散列值（ Receipt Root ）、时间戳（ Times tamp ）、随机数（ Nonce ）等

以太坊区块链上区块数据结构相对比特币的一个重大改变就是保存了三棵Merkle树根，分别是状态树、交易树和收据树。

• 状态树(RootHash)：整个系统状态的hash，也就是所有账户状态树的根hash。

• 交易树(TxHash):本区块中所有的交易默克尔树的根hash。

• 收据树(ReceiptHash):收据默克尔树的根hash。每个区块都有自己的收据树，收据树不需要更新，收据树代表每笔交易相应的收据。

交易列表

交易列表是由矿工从交易池中选择收入区块中的一系列交易。

叔区块

不在主链上的且被主链上的区块通过Uncles 字段收留进区块链的孤块叫做“叔区块” 。

账户体系

账户以地址为索引，地址由公钥衍生而来，取公钥的最后20 字节

在以太坊系统中存在两种类型的账户，分别是外部账户和合约账户。外部账户存储以太币余额状态，而合约账户除了余额还有智能合约及其变量的状态。

外部账户

外部账户（ Externally Owned Account, EOA ）是用户实际控制的账户。由公私钥来控制，其中私钥掌握账户的控制权。

状态：

balance（账户余额）

nonce（计数器）

合约账户

在以太坊中，每个账户都有一个唯一的地址，由20个字节组成，通常表示为40个十六进制字符。这个地址是由账户的公钥通过Keccak-256哈希算法计算出来的。

账户的公钥是由该账户的私钥通过椭圆曲线加密算法（ECDSA）推导而来的。公钥是一个512位的二进制数，通常表示为64个十六进制字符。在以太坊中，公钥不是直接使用的，而是通过Keccak-256哈希算法计算出一个唯一的地址。

账户的私钥是一个256位的二进制数，通常表示为64个十六进制字符。私钥是用于签署交易和发送以太币的关键，因此必须妥善保管。使用私钥可以生成与该私钥对应的公钥和地址。

因此，以太坊账户地址、公钥和私钥之间的关系可以总结为：

• 以太坊账户地址是由账户的公钥通过Keccak-256哈希算法计算得出的。

• 以太坊账户的公钥是由账户的私钥通过ECDSA算法计算得出的。

• 以太坊账户的私钥是用于签署交易和发送以太币的关键，可以生成与该私钥对应的公钥和地址。

以太坊中每个外部账户都由一对密匙定义，即一个私钥和一个公钥。

合约账户是一个包含合约代码的账户。合约账户不是由私钥文件直接控制，而是由合约代码控制。合约账户的地址是由合约创建时合约创建者的地址，以及该地址发出的交易共同计算得出的。

balance（账户余额）

nonce（计数器）//一个合约可以调用另外一个合约，所以要通过nonce值记录一下调用的次数。

code（代码）

storage（相关状态-存储，包括每个变量的取值）

与外部账户相比，合约账户除了余额还有智能合约及其变量的状态。合约账户不能主动发起一个交易，以太坊中的一个规定，*
*所有的交易只能由外部账户发起**，外部账户发起一个交易如果调用了一个合约账户，这个合约账户可以发送一个message调用另外一个合约，但是他不能自己品平白发起一个交易。

合约账户的调用

创建一个合约会返回一个地址，知道这个合约的地址，就可以调用这个合约，调用的过程当中状态会发生变化，代码（code）不会变，*
*存储（storage）会变**。

私钥和公钥

目前常见的私钥有三种形态：

Private key

Private key 就是一份随机生成的256 位二进制数字。用户甚至可以用纸笔来随机地生成一个私钥，即随机写下一串256 位的仅包含“0”或“
1”的字符串。该256 位二进制数字就是私钥最初始的状态。

Keystore & Password

而在以太坊官方钱包中，私钥和公钥将会以加密的方式保存一份JSON 文件，存储在key store 子目录下。这份JSON 文件就是Keys tore
，所以用户需要同时备份Keys tore和对应的Password （创建钱包时设置的密码） 。

Memonic code

Memonic code 是由BIP 39 方案提出的，目的是随机生成12 ～ 24 个比较容易记住的单词，该单词序列通过PBKDF2 与HMAC-SHA512
函数创建出随机种子，该种子通过BIP-0032 提案的方式生成确定性钱包

数据结构与存储

区块、交易等数据最终都是存储在Level DB数据库中。Level DB数据库是一个键值对（ key-value ）数据库，
key一般与散列相关，value则是存储内容的RLP编码。

数据组织形式

以太坊使用了MPT树（Merkle Patricia
Trie），作为数据组织形式，用来组织管理用户的账户状态、交易信息等重要数据。MPT是一种加密认证的数据结构，它融合了Merkle树和Trie树（前缀树）两种数据类型的优点。

Merkle树

Merkle树是一种树形数据结构，可以是二叉树，也可以是多叉树。它由一组叶节点、一组中间节点和一个根节点构成。最下面的叶节点包含基础数据，每个中间节点是它的子节点的散列，根节点是它的子节点的散列，代表了Merkle树的根部。

创建Merkle树的目的是允许区块的数据可以零散地传送；节点可以从一个节点下载区块头，从另外的源下载与其相关的树的其他部分，而依然能够确认所有的数据都是正确的。

Merkle树可以用来存储所有键值对

Merkle树特性

1.每个数据集对应一个唯一合法的根散列值。

2.很容易更新、添加或者删除树节点，以及生成新的根散列值。

3.不改变根散列值的话就没有办法修改树的任何部分，所以如果根散列值被包括在签名的文档或有效区块中，就可以保证这棵树的正确性。

4.任何人可以只提供一个到特定节点的分支，并通过密码学方法证明拥有对应内容的节点确实在树里。

Trie树

key代表的是从树根到对应value的一条路径。即从根节点开始， key 中的每个字符（从前到后）都代表着从根节点出发寻找相应value
所要经过的子节点。value 存储在叶节点中，是每条路径的最终节点。

MPT树

结合merkle和Trie,并做了以下改进：

1.为了保证树的加密安全，每个节点通过它的散列值被引用

2.对于存储在Leve IDB 数据库中的非叶节点，key代表着节点的RLP编码的SHA3散列值， value是节点的RLP编码。

3.引入了很多节点类型来提高效率：

3.1空节点：简单的表示空，在代码中就是一个空串

3.2叶节点：键值对的一个列表，其中key是一种特殊的十六进制编码， value是RLP编码。

3.3扩展节点：键值对的列表，但是这里的value 是其他节点的散列值，通过这个散列值可以链接到其他节点。

3.4分支节点：一个长度为17 的列表。MPT 中的key 被编码成一种特殊的十六进制的表示，再加上最后的value ，前16 个元素对应key 中的16
个可能的十六进制字符，如果有一个键值对在这个分支节点终止，则最后一个元素代表一个值，即分支节点既可以是搜索路径的终止，也可以是路径的中间节点。

4.用于对key 进行编码的特殊十六进制前缀编码（ HP ）

区块头中的三颗树

状态树(RootHash)

整个系统状态的hash，也就是所有账户状态树的根hash。状态树包含一个键值映射，其中键是账户地址，值是账户内容，主要是｛ nonce,
balance,codeHash, storageRoot ｝ 。nonce 是账户交易的序数， balance 是账户余额， codeHash 是代码的散列值， storageRoot
是另一棵树的根节点。状态树代表访问区块后的整个状态。

状态树不存在于链上，而存在于节点的levelDB中。只有他的根hash存在于区块中，每一个区块头里的Root都是区块被挖出确认时的快照。

交易树(TxHash)

本区块中所有的交易默克尔树的根hash。

每个区块都有一棵独立的交易树。区块中交易的顺序主要由“矿工”决定，在这个块被挖出前这些数据都是未知的。不过“矿工”
一般会根据交易的GasPrice 和nonce 对交易进行排序。首先会将交易列表中的交易划分到各个发送账户，每个账户的交易根据这些交易的nonce
来排序。每个账户的交易排序完成后，再通过比较每个账户的第一条交易，选出最高价格的交易，这些是通过一个堆（heap）来实现的。

在交易树包含的键值对中，其中每个键是交易的编号，值是交易内容

收据树(ReceiptHash)

收据默克尔树的根hash。

每个区块都有自己的收据树，收据树不需要更新，收据树代表每笔交易相应的收据。

交易的收据是一个RLP 编码的数据结构：［medstate, Gas_ used, logbloom,logs ］ 。其中， medstate 是交易处理后树根的状态；
Gas_used 是交易处理后Gas 的使用量；logs 是表格［ address, [topicl, topic2 ,…], data ］元素的列表，表格由交易执行期间调用的操作码LOGO
…LOG4 生成（包含主调用和子调用）， address 是生成日志的合约地址， topicn是最多4 个32 字节的值， data 是任意字节大小的数组；*
logbloom 是交易中所有logs 的address 和topic 组成的布隆过滤器。*

数据库支持一一Level DB

LeveI DB 是Goog le 实现的一个非常高效的键值对数据库，其中键值都是二进制的，目前能够支持十亿级别的数据量，在这个数据量下还有着非常高的性能。

以太坊中共有三个Leve IDB 数据库，分别是BlockDB 、StateDB 和ExtrasDB。

BlockDB保存了块的主体内容，包括块头和交易；StateDB保存了账户的状态数据；ExtrasDB保存了收据信息和其他辅助信息。

共识机制

共识机制是区块链事务达成分布式共识的算法。由于点对点网络下存在着或高或低的网络延迟，所以各个节点接收到的事务的先后顺序可能不一样，因此区块链系统需要设计一种机制让节点对在差不多时间内发生的事务的先后顺序实现共识，这就是共识机制。

Pow

PoW 即通过工作结果来证明你完成了相应的工作

哈希函数的特征：

1.免碰撞，即不存在输入值不同，经过散列变换，而散列值相同的情况。

2.隐匿性，即给定一个散列值，想要反向逆推出输入值，在计算上是不可行的。

3.不存在比穷举更好的方法，以使得散列值落在特定的范围。

POW算法原理：节点通过不断地更换随机数来探寻合适的哈希值，当节点最先计算出合适的哈希值，它所打包的块如果通过其他共识节点的验证，则会被加入到区块链中。

Ethash （以太坊专门的POW算法 ）

为了解决挖矿中心化问题,专门设计了一个能抵制ASIC、轻客户端可快速验证的PoW 算法

算法流程：

1.对于每一个区块，都能通过扫描区块头的方式计算出一个种子（ seed ），该种子只与当前区块有关。

2.使用种子能产生一个16MB 的伪随机缓存，轻客户端会存储缓存。

3.基于缓存再生成一个1GB 的数据集，称其为DAG 。数据集中的每一个元素都只依赖于缓存中的某几个元素，也就是说，只要有缓存，就可以快速地计算出DAG
中指定位置的元素。挖矿者存储数据集，数据集随时间线性增长。

4.挖矿可以概括为“矿工”从DAG 中随机选择元素并对其进行散列的过程， DAG 也可以理解为一个完整的搜索空间，挖矿的过程就是从DAG
中随机选择元素（类似比特币挖矿中试探合适nonce 的过程）进行散列运算。

5.验证者只需要花费少量的内存存储缓存就可以了，因为验证者能够基于缓存计算得到DAG
中自己需要的指定位置的元素，然后验证这些指定元素的散列是不是小于某个散列值，也就是验证“矿工”的工作是否符合要求。

Ethash 算法的特点是挖矿的效率基本与CPU 无关，而与内存大小、带宽正相关，目的是去除专用硬件的优势，抵抗ASIC 。

POS

PoS 即基于网络参与者目前所持有的数字货币的数量和时间进行利益分配，是一种对货币所有权的证明

共识算法类型：

基于链的PoS 和BFT (Byzantine Fault Tolerant ，拜占庭容错）风格的PoS 。

在基于链的PoS 中，该算法在每个时隙内伪随机地从验证者集合中选择一个验证者（比如，设置每l0s
一个周期，每个周期都是一个时隙），给予验证者创建新区块的权利，但是验证者要确保该块指向最多的块（指向的上一个块通常是最长链的最后一个块）
。因此，随着时间的推移，大多数的块都收敛到一条链上。

在BFT 风格的PoS
中，分配给验证者相对的权利，让他们有权提出块并且给被提出的块投票，从而决定哪个块是新块，并在每一轮选出一个新块加入区块链。在每一轮中，每一个验证者都为某一特定的块进行“投票”，最后所有在线和诚实的验证者都将“商量”被给定的块是否可以添加到区块链中，并且意见不能改变。

交易

以太坊的交易主要是指一条外部账户发送到区块链上另一账户的消息的签名数据包，其主要包含发送者的签名、接收者的地址以及发送者转移给接收者的以太币数量等内容。

交易是以太坊整体架构中的重要部分，它将以太坊的账户连接起来，起到价值的传递作用。

交易内容

from ：交易发送者的地址，必填；

to ：交易接收者的地址，如果为空则意味这是一个创建智能合约的交易；

value ：发送者要转移给接收者的以太币数量；

data （也写作input）：存在的数据字段，如果存在，则是表明该交易是一个创建或者调用智能合约交易；

Gas Limit （也写作Gas, StartGas ）：表示这个交易允许消耗的最大Gas 数量；

GasPrice ：表示发送者愿意支付给矿工的Gas 价格；

nonce ：用来区别同一用户发出的不同交易的标记；

hash ：由以上信息生成的散列值（哈希值），作为交易的ID;

r 、s 、v ：交易签名的三个部分，由发送者的私钥对交易hash 进行签名生成。

交易费用

为了防止用户在区块链公有链中发送太多的无意义交易，浪费矿工的计算资源，要求交易的发送方为每笔交易付出一定的代价，便是交易费用。

由于比特币中只存在转账交易，每笔交易所需的计算开销大体一致，因此每笔交易的发送者会以比特币的形式，付出相对固定的手续费。而以太坊中引入了智能合约，涉及智能合约创建和调用的交易所消耗的计算差别巨大，因此引入了相对复杂的Gas
、Gas Price 对交易所需的手续费进行定价。

Gas

Gas （汽油）是用来衡量一笔交易所消耗的计算资源的基本单位。当以太坊节点执行一笔交易所需的计算步骤越多、越复杂，那么就会说这笔交易消耗的Gas
越多。

Gas Price

Gas Price ( Gas 价格）是一单位Gas 所需的手续费（以太币，即Ether ）。矿工会对接受到的交易按照Gas Price 或者按照Gas * Gas Price
从大到小进行排序，以便决定哪个交易会先纳入到区块中。当以太坊公有链上某个时段交易量激增的情况下，为了尽早让矿工接受一笔交易，交易发送者可以提高这笔交易的Gas
Price ，以激励矿工

Gas Limit

有两种：

对于单个交易， Gas Limit （有时也会称作StartGas ）表示交易发送者愿意为这笔交易执行所支付的最大Gas
数量，需要发送者在发送交易时设置。可以保护用户免受错误代码影响以致消耗过多的交易费。GasPrice * Gas Limit
表示用户愿意为一笔交易支付的最高金额。

而对于区块来说， Gas Limit 是单个区块所允许包含的最大Gas 总量，由矿工决定它的大小。防止矿工的资源消耗过大，造成挖出的区块无法形成最长的交易链。不过矿工也不能任意地更改区块的Gas
Limit ，根据以太坊协议，当前区块的Gas Limit 只能基于上一个区块的Gas Limit 上下波动1/1024。

交易类型

• 转账交易

web3.eth.sendTransaction({
from :"Oxb60e8dd6lc5d32be8058bb8eb970870f07233155",
to:"Oxd46e8dd67c5d32be8058bb8eb970870f07244567",
value: 10000000000000000
});

• 创建智能合约

web3.eth.sendTransaction({
from:"Oxb60e8dd6lc5d32be8058bb8eb970870f07233155",
data :"contract binary code"
});

• 执行智能合约

web3.eth.sendTransaction({
from:"Oxb60e8dd6lc5d32be8058bb8eb970870f07233155",
to:"Oxb4259e5d9bc67a0f2ce3ed372ffc5lbe46c33c4d",
data :"hash of the invoked method signature and encoded parameters"
});

交易执行流程

以太坊交易分为：发起、广播、打包与执行、验证与执行

1. 用户从Dapp或者钱包初始化一笔交易，比如发送资金或者调用合约。这个类似弹出了MetaMask交易界面。
2. 用户使用它们的钱包（私钥）签名这个交易。这个例如我们在第一步弹出的交易界面点击确定按钮（签名交易）。
3. 钱包将签名后的交易发送到连接到以太坊网络的一个节点，通常叫着网关节点。比如我们常用的Infura节点。
4. 网关节点验证该交易有效并将它放入自己的内存池（交易池/交易队列）中。此时，该交易为Pending状态，所有人都可以读取（前提是提供该项服务）。具体的对象名称在Geth和Parity客户并不相同。进入pending状态的交易代表着将要被交易，具体交易区块由打包矿工决定。很多套利机器人和攻击者就是读取pending中的交易，然后获取交易详情（包括交易发送对象，接收者，交易参数等），然后决定下一步的行动。
5. 网关节点将该交易向其它节点（邻近节点）扩散（广播）。这是个Pending交易传播过程。
6. 它节点接收到该交易后也验证有效性，然后放入自己的内存池中。然后再向其它节点扩散。这是其它节点将pending放入自己的内存池中。
7. 重复上述步骤，直到该交易扩散到整个网络。
8. 矿工是一种特殊节点，它们除了接收交易和验证它以外，还试图把它加入一个区块。矿工特权，具有打包交易的权利。
9. 最终，会有一个矿工将该交易打包到区块中（这里假定交易成功并且会被打包）并添加到区块链上（产生一个新区块）。这就是通常所说的挖矿（出块）。
10. 新产生的区块向全网广播。（以太坊大概13秒左右出一个块，基本上能够全网广播）。
11. 所有节点接收到该区块，查看其中包含的交易并将其从自己的内存池中移除。

数据编码与压缩(RLP)

RLP ( Recursive Length Prefix ）递归长度前缀是一种编码算法，用于编码任意的具有嵌套结构的二进制数据，是以太坊数据序列化的主要方法。。

补充：RLP编码解析 大端与小端

RLP编码

Byte单子节

规则1：对于值在[0, 127]之间的单个字节，其编码是其本身。

a的编码是97

Byte数组编码

规则2：如果byte数组长度小于55，编码的结果是数组本身，再加上128+l作为前缀。

空字符串编码是128，即128 = 128 + 0

abc编码结果是131 97 98 99，其中131=128+len(“abc”)，97 98 99依次是a b c。

规则3：如果数组长度大于55， 编码结果第一个是183加数组长度的编码的长度，然后是数组长度的本身的编码，最后是*
*byte数组的编码**。

The length of this sentence is more than 55 bytes, I know it because I pre-designed it

这段字符串共86个字节，而86的编码只需要一个字节，那就是它自己，因此，编码的结果如下：

184 86 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115
32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 73 32 107 110 111 119 32 105 116 32 98 101 99
97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

其中前三个字节的计算方式如下：

184 = 183 + 1，因为数组长度86编码后仅占用一个字节

86即数组长度86

84是T的编码

编码一个重复1024次”a”的字符串. aaaaa….aaaaa

结果为 185 4 0 97 97 97 97 97 97 …

1024按 big endian编码为0 0 4 0，省略掉前面的零，长度为2，因此185 = 183 + 2

补充:1024的大端表示 0x 00 00 04 00，去掉前面的0后，长度是2(04,00). ..0x400=1024

Bytes列表

定义：列表长度为 子列表编码后的长度之和

规则4：如果列表长度小于55，编码结果第一位是192加列表长度的编码，然后依次连接各子列表的编码。

[“abc”, “def”]的编码结果是200 131 97 98 99 131 100 101 102。

“abc” 的编码结果为：131 97 98 99,

“def” 的编码结果为：131 100 101 102，

列表长度为4+4 = 8 . 8<55.

因此编码结果第一位计算得出：192 + 8 = 200

规则5：如果列表长度超过55，编码结果第一位是247加列表长度的编码长度，然后是列表长度本身的编码，最后依次连接各子列表的编码。

[“The length of this sentence is more than 55 bytes, “, “I know it because I pre-designed it”]

编码结果为:248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99
101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110 111 119 32
105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

248 = 247 +1.

88 = 86 + 2，在规则3的示例中，长度为86，而在此例中，由于有两个子字符串，每个子字符串本身的长度的编码各占1字节，因此总共占2字节。

第3个字节179依据规则2得出179 = 128 + 51.

[“abc”,[“The length of this sentence is more than 55 bytes, “, “I know it because I pre-designed it”]]

248 94 131 97 98 99 248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116
101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 163 73 32 107 110
111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116

列表第一项字符串abc根据规则2，编码结果为131 97 98 99,长度为4。

列表第二项也是一个列表项：上一个demo，长度为90，

因此，整个列表的编码结果第二位是90 + 4 = 94, 占用1个字节，第一位247 + 1 = 248

RLP解码

解码时，首先根据编码结果第一个字节f的大小，执行以下的规则判断：

1. 如果f∈ [0,128), 那么它是一个字节本身。

2. 如果f∈[128,184)，那么它是一个长度不超过55的byte数组，数组的长度为l=f-128

3. 如果f∈[184,192)，那么它是一个长度超过55的数组，长度本身的编码长度ll=f-183,然后从第二个字节开始读取长度为ll的bytes，按照BigEndian编码成整数l，l即为数组的长度。

4. 如果f∈(192,247]，那么它是一个编码后总长度不超过55的列表，列表长度为l=f-192。递归使用规则1~4进行解码。

5. 如果f∈(247,256]，那么它是编码后长度大于55的列表，其长度本身的编码长度ll=f-247,然后从第二个字节读取长度为ll的bytes,按BigEndian编码成整数l，l即为子列表长度。然后递归根据解码规则进行解码。