以太坊数据结构MPT
链客，专为开发者而生，有问必答！
此文章来自区块链技术社区，未经允许拒绝转载。
MPT(Merkle Patricia Tries)是以太坊存储数据的核心数据结构，它是由Merkle Tree和Patricia Tree结合的一种树形结构，理解MPT有助于我们更好的理解以太坊的数据存储。在了解MPT数据结构之前，我们需要先来看看基本的Tree结构和Merkle Tree、Patricia Tree。
Trie字典树
Trie树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
上图是一棵Trie树，表示了字符串集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} ，从上图中我们可以看出Trie树的特点：
根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。
但是从上面的结构也可以看出一个问题：高度不可控，如下图所示。所以就有了Patricia树（压缩前缀树），后面会介绍到
Merkle Tree
Merkle Tree，也被称为Hash Tree，中文名称：默克尔树，主要用于数据集较大时的文件校验。其主要特点为：
叶节点存储着数据块的Hash（如：文件块、一段数据集）
非叶子节点（包括中间节点和根节点）存储着对应子节点Hash值串联字符串之后的Hash值。
解释：
1、在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应；
2、往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希再往上推，依然是一样的方式，可以得到数目更少的新一级哈希，
3、最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。
对于这种数据结构，在实际应用中会有哪些应用场景了，举个例子，我们知道现在从网上下载文件，很多都是P2P下载，文件会切分成很多小的数据块，每个数据块从不同的来源上下载，这些机器可以认为是不稳定或不可信的，文件下载完之后我们需要校验文件的完整性，这时我们总不能把文件再次切分然后分别计算它的Hash和下载前的Hash做对比吧，这时就需要用到Merkle Tree。
在下载前，先从可靠的源获得文件的Merkle Tree树根，下载后，在合并文件之前先对比小文件的Hash是否一样，如果一样就认为是可靠的，如果不一样，就判定文件被损坏，从新的来源重新下载，文件合并之后，计算小数据块的Hash并最终计算根Hash，也成为Merkle Root，然后对比根Hash是否一致。这样就避免了对整个文件进行Hash计算，因为当文件太大时，这种计算是很耗时。
Patricia Tree
Patricia树，或称Patricia trie，或crit bit tree，压缩前缀树，是一种更节省空间的Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。
MPT（Merkle Patricia Tree）
上面我们介绍了Merkle Tree和Patricia Tree，而MPT（Merkle Patricia Tree），顾名思义就是这两者的结合。MTP树种的节点包含空节点、叶子节点、扩展节点和分支节点。
Nibble：它是key的基本单元，是一个四元组（四个bit位的组合例如二进制表达的0010就是一个四元组）
空节点**：简单的表示空，在代码中是一个空串。
叶子节点（leaf）：只有两个元素，分别为key和value，表示为key,value的一个键值对，其中key是key的一种特殊十六进制编码，value是value的RLP编码。
扩展节点（extension）：也是key，value的一个键值对，但是这里的value是其他节点的hash值，这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。
分支节点（branch）：分支节点有17个元素，回到Nibble，四元组是key的基本单元，四元组最多有16个值。所以前16个必将落入到在其遍历中的键的十六个可能的半字节值中的每一个。第17个是存储那些在当前结点结束了的节点(例如， 有三个key,分别是 (abc ,abd, ab) 第17个字段储存了ab节点的值)
这里还有一些知识点需要了解的，为了将MPT树存储到数据库中，同时还可以把MPT树从数据库中恢复出来，对于Extension和Leaf的节点类型做了特殊的定义：如果是一个扩展节点，那么前缀为0，这个0加在key前面。如果是一个叶子节点，那么前缀就是1。同时对key的长度就奇偶类型也做了设定，如果是奇数长度则标示1，如果是偶数长度则标示0。
以太坊的每一个区块头，并非只包含一棵MPT树，而是包含了三棵MPT树，分别对应了四种对象：
State Trie 区块头中的状态树
key => sha3(以太坊账户地址address)
value => rlp(账号内容信息account)
Transactions Trie 区块头中的交易树
key => rlp(交易的偏移量 transaction index)
每个块都有各自的交易树，且不可更改
Receipts Trie 区块头中的收据树
key = rlp(交易的偏移量 transaction index)
每个块都有各自的交易树，且不可更改
Storage Trie 存储树
存储只能合约状态
每个账号有自己的Storage Trie
MPT树种还有一个重要的概念：特殊的十六进制前缀(hex-prefix, HP)编码来对key编码，我们先来了解一下编码定义规则：
RAW 原始编码，对输入不做任何变更
HEX 十六进制编码
- RAW编码输入的每个字符分解为高4位和低4位。比如key=>“bob”,b的ASCII十六进制编码为0x62，o的ASCII十六进制编码为0x6f，分解成高四位和第四位，16表示终结 0x10，最终编码结果为[6 2 6 15 6 2 16]，
- 如果是叶子节点，则在最后加上Hex值0x10表示结束
- 如果是分支节点不附加任何Hex值
HEX-Prefix 十六进制前缀编码
输入key结尾为0x10，则去掉这个终止符
key之前补一个四元组这个Byte第0位区分奇偶信息，第1位区分节点类型
如果输入key的长度是偶数，则再添加一个四元组0x0在flag四元组后
将原来的key内容压缩，将分离的两个byte以高四位低四位进行合并
十六进制前缀编码相当于一个逆向的过程，比如输入的是6 2 6 15 6 2 16，根据第一个规则去掉终止符16。根据第二个规则key前补一个四元组，从右往左第一位为1表示叶子节点，从右往左第0位如果后面key的长度为偶数设置为0，奇数长度设置为1，那么四元组0010就是2。根据第三个规则，添加一个全0的补在后面，那么就是20.根据第三个规则内容压缩合并，那么结果就是0x20 0x62 0x6f 0x62
相关文章：
lambda在python中的用法_在python中对lambda使用.assign（）方法
我在Python中运行以下代码：#Declaring these now for later use in the plotsTOP_CAP_TITLE Top 10 market capitalizationTOP_CAP_YLABEL % of total cap# Selecting the first 10 rows and setting the indexcap10 cap.loc[:10, :].set_index(id)# Calculating…
react 开发过程中的总结/归纳
1、点击元素，获取绑定该事件的父级元素，使用 e.currentTarget。e.target 获取的是，出发该事件的元素，该元素有可能是所绑定事件的元素的子元素。 2、使用 react router4 history 只能传递给儿子组件，不能传递给孙子组件…
kvm虚拟机--存储池配置梳理(转)
1.创建基于文件夹的存储池（目录） 2.定义存储池与其目录 1 # virsh pool-define-as vmdisk --type dir --target /data/vmfs 3.创建已定义的存储池 (1)创建已定义的存储池 1 # virsh pool-build vmdisk (2)查看已定义的存储池，存储池不激活无法…
区块链概况：什么是区块链
链客，专为开发者而生，有问必答！ 此文章来自区块链技术社区，未经允许拒绝转载。 区块链技术自身仍然在飞速发展中，目前还缺乏统一的规范和标准。 wikipedia 给出的定义为： A blockchain —originally, b…
drx功能开启后_简单实用！小米手机中这些新功能真香
小米手机作为国产机热销品牌之一，它除了有好看的外观，还有很多隐藏的实用功能，今天小编就来和大家分享5个小米手机里你不知道的功能。Al电话助理看到陌生号码时，很多人第一反应就是挂掉，不想接听，但又担心自…
Ubuntu 8.04嵌入式交叉编译环境arm-linux-gcc搭建过程图解
Linux版本：Ubuntu8.04 内核版本：Linux 2.6.24 交叉编译器版本：arm-linux-gcc-3.4.1 交叉编译器下载链接： https://share.weiyun.com/5oxlS6X （密码：36R7） 前言 1、搭建交叉编译环境 安装、配置交…
Installshield 2015 实现检测某安装文件是否存在并运行安装
最近在用installshiled 2015做安装包，用了很长时间研究明白了怎样实现在安装成功界面显示一个checkbox，选中该checkbox，就会安装选中的安装包。 首先我们要有一个installshield的工程。 其次是判断是否要显示这个checkbox。我的需求是根据某个…
区块链概况:从数字货币说起
链客，专为开发者而生，有问必答！ 此文章来自区块链技术社区，未经允许拒绝转载。 从数字货币说起 货币是人类文明发展过程中的一大发明，最重要的职能包括价值尺度、流通手段、贮藏手段。很难想象离开了货币，…
Android RecyclerView 基本使用
Android RecyclerView 基本使用 概述 RecyclerView出现已经有一段时间了，相信大家肯定不陌生了，大家可以通过导入support-v7对其进行使用。 据官方的介绍，该控件用于在有限的窗口中展示大量数据集，其实这样功能的控件我们并不陌生…
lisp语言cond和if套用_在'if'语句中设置多行条件的样式？
Harley Holco..679您不需要在第二个条件行上使用4个空格.也许用:if (cond1 val1 and cond2 val2 andcond3 val3 and cond4 val4):do_something另外,不要忘记空格比您想象的更灵活:if (cond1 val1 and cond2 val2 andcond3 val3 and cond4 val4):do_somethingif (cond1 …
jvm七种垃圾收集器
JVM_七种垃圾收集器介绍 本文中的垃圾收集器研究背景为：HotSpotJDK7一、垃圾收集器概述如上图所示，垃圾回收算法一共有7个，3个属于年轻代、三个属于年老代，G1属于横跨年轻代和年老代的算法。JVM会从年轻代和年老代各选出一个算法进…
新手怎么学以太坊区块链开发？
链客，专为开发者而生，有问必答！ 此文章来自区块链技术社区，未经允许拒绝转载。 在学习以太坊应用开发时，除了学习solidity开发智能合约，一个小白还应该补充 哪些知识？文本将给出相关的学习资源…
【题解】 bzoj1260: [CQOI2007]涂色paint （区间dp）
bzoj1260，懒得复制，戳我戳我 Solution: 这种题目我不会做qwq，太菜了区间打牌(dp) 用f[l][r]表示从l到r最少需要染几次色。状态转移方程： 1.\(f[l][r]min(f[l][i],f[i1][r]) (l<i<r)\) 这段染色等于俩段分别染色，…
[deviceone开发]-组件功能演示示例
一、简介 这个是官方比较早期对组件功能的展示集合，因为发布的比较早，只包含了部分组件，但是常用的组件和常用的功能都包含了。初学者推荐。二、效果图 三、相关下载 https://github.com/do-project/code4do/tree/master/demo四、相关讨论 ht…
联想g510升级换什么cpu好_老兵不死，十年前的联想 Y450 笔记本复活记
如果你是一个接触笔记本电脑比较早的用户，那么联想小Y的大名你一定不会陌生，作为联想旗下较为成功的产品线，彪悍的小Y在几年前就打出了名堂，而小Y系列笔记本里面又以 Y450 最为经典，Y450 引入 NVIDIA GT240M 中端移动显…
区块链和数据库
链客，专为开发者而生，有问必答！ 此文章来自区块链技术社区，未经允许拒绝转载。 区块链技术是一种不依赖第三方、通过自身分散式节点进行网路数据的存储、验证、传递和交流的一种技术方案。因此，有人从金融会计的角度…
普通粒子群算法和优化方法
粒子群优化(PSO, particle swarm optimization) 是由Kennedy和Eberhart在1995年提出的一 种群智能优化方法。 优点：好理解容易实现，适合解决极值问题 缺点：容易过早收敛，容易陷入局部最优解，（如果初始点选的…
古人怎么称呼年龄
来自为知笔记(Wiz)转载于:https://www.cnblogs.com/sanyuanempire/p/6154780.html
vue变量传值_vue组件与组件之间传值
目录一、父组件向子组件传值二、子组件向父组件传值三、兄弟组件之间的传值如上图所示，2是1的子组件，1是3的父组件，2和3是兄弟组件一、父组件向子组件传值：html代码:<div id"app"><v-app><!-- 用:xxxx&q…
区块链技术背后的运行逻辑
链客，专为开发者而生，有问必答！ 此文章来自区块链技术社区，未经允许拒绝转载。 区块链技术可能是自互联网技术以来最伟大的发明。区块链可以在不需要有中央权威机构的情况下或不需要双方信任的情况下交换价值或财富。想像一下你…
scp遇到路径中有空格
sudo scp root1.1.1.1:/test/soft/123/Microsoft SQL Server 2000.iso . 错误！ sudo scp root1.1.1.1:"/test/soft/123/Microsoft SQL Server 2000.iso" . 错误！ sudo scp root1.1.1.1:/test/soft/123/Microsoft\ SQL\ Server\ 2000.…
bzoj 3262 陌上花开
本质是一个三维偏序，一位排序后cdq分治，一维在子函数里排序，一维用树状数组维护。 把三维相等的合并到一个里面。 1 #include<iostream>2 #include<cstdio>3 #include<algorithm>4 #include<cstring>5 #define N 100…
jspstudy启动mysql失败_MySql启动数据库设置初始密码
这一小节介绍在Mac OS、Linux、Windows上启动关闭重启MySQL服务，以及部分图形化界面对服务的操控。安装完成后，可以使用 service 命令启动 mysql 服务，在Mac上service命令不存在。命令行启动关闭重启MySQL服务在命令行终端启动 MySQL 非常方便…
区块链技术产生数字货币时代
链客，专为开发者而生，有问必答！ 此文章来自区块链技术社区，未经允许拒绝转载。 比特币是一种革命性的数字货币，更是一种颠覆性的创新技术。比特币最大的贡献是创造了信用，解决了困扰互联网进一步发展的拜…
软件构造 第二章 第一节 软件生命周期和版本控制
软件构造第二章 第一节 软件生命周期和版本控制 基本内容 Software Development Lifecycle (SDLC) Traditional software process models (waterfall, incremental, V- model, prototyping, spiral) Agile development and eXtreme Programming (XP) Collaborative software de…
三极管在ad中的原理图库_555时基电路内部结构及其工作原理
555时基电路特点时基电路是一种常用的模数混合型集成电路。由它组成的振荡器、单稳态触发器、双稳态触发器和各类电子开关等都被十分广泛地应用在各类电路之中。它具有定时精度高、响应速度快、温漂小、输出驱动电流大、结构简单等优点。555时基电路型号命名555时基芯片由其内部…
Mac下导出chrome插件
Mac下导出chrome插件 chrome最强大的功能之一就是插件，有时候需要给小伙伴们共享一些插件，所以需要将自己chrome中的插件打包，在mac下打包插件还是挺费劲的，在此记录。 打开chrome的扩展程序，找到要导出的插件…
区块链技术的本质是分布式数据库
链客，专为开发者而生，有问必答！ 此文章来自区块链技术社区，未经允许拒绝转载。 区块链技术是基于比特币应用提出的一个概念，他是一个融合了多种技术的一个集成式创新。目前区块链的应用早已不仅仅局限在比特币上。人…
sql数据库系统表和mysql系统表
sql数据库系统表,常用的(sysobjects,sysindexes,sysindexkeys,SYSCOLUMNS,SYSTYPES 及更多解释说明): https://docs.microsoft.com/zh-tw/previous-versions/sql/sql-server-2012/ms177596(v%3dsql.110) 系统存储过程sp_spaceused: 执行sp_spaceused存储过程的时候可以不用带参…
交换机启用光口命令_如何在思科交换机上查询光模块状态？
本篇文章易天光通信（ETU-LINK）将为大家介绍下怎么在思科交换机上查询光模块的信息。 第一步，我们需要连接网络，然后登陆思科交换机的管理平台，用户名和密码默认是cisco/cisco。 第二步，在交换机的特权EXEC模式，通过输入以下使用显示光纤端口光纤收发器命令：show光纤端口…