以太坊学习三: Merkle树和验证

这篇具有很好参考价值的文章主要介绍了以太坊学习三: Merkle树和验证。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Merkle tree简介

   Merkle树又称为哈希树,是一种二叉树,由一个根节点、若干中间节点和一组叶节点组成。最底层的叶节点存储数据,在它之上的一层节点为它们对应的Hash值,中间节点是它下面两个子节点的Hash值,根节点是最后顶层的Hash值,这个一般成为Merkle根。
以太坊学习三: Merkle树和验证
  Merkle树的层层Hash计算,任何底层叶节点或者说某个节点的数据变动都会传递到父亲节点,并直达树根。当叶子节点发生数据改变时,如果要比较两个集合的数据是否相同,则只需比较两次数据的树根即可,若底层叶节点数据相同,则树根相同;反之,树根便不相同。因此Merkle树的典型应用场景具体如下:

  • 快速比较大量数据:当两个Merkle树根相同时,则意味着所代表的数据必然相同
  • 快速定位变更:如果上图L1的数据被修改,则hi影响到Hash0-0,Hash0 和Root。因此沿着Root->Hash0->Hash0-0,可以快速定位到发生改变的L1。

MPT 状态树

  Trie树是一种有序的树形结构,也被称为前缀树或者字典树,一般用于保存关联数组,其中的键通常是字符串,键不保存在节点中,而是由节点在树中的位置决定,根节点对应空字符串,键对应的值标注在节点之下。

  Patricia树是一种节省空间的压缩前缀树。相当于Trie树存在的缺点,每个前置节点仅能表示一个字母,不管key和其它key有没有共享内容,key越长,树的深度也就越长。Patricia树的主要改进在于如果存在一个父节点只有一个子节点,那么这个父节点将与其子节点合并,这样可以减少Trie中树的深度,加快搜索节点速度,同时也减少了空间的消耗。

以太坊学习三: Merkle树和验证
  MPT是Merkle 和Patricia 结合后的产物,在以太坊中,MPT包含4种不同的节点: 空节点、叶子节点、扩展节点和分支节点。

  • 空节点:无实际内容节点,但占用一个元数据存储。
  • 叶子节点:是一个键值对,其中key是原始内容的一种特殊十六进制编码,value是内容的RLP编码.
  • 扩展节点: 也是一个键值对,但是value是其他节点的Hash值,即指向其他节点的链接
  • 分支节点:由于key被编码成一种特殊的十六进制的表示,还有最后的value,所以分支节点是一个长度为17的列表,前16个元素对应着key中的16个可能的十六进制字符,如果有一个(key,vlaue)键值对在这个分支节点终止,那么最后一个元素代表一个值,即分支节点既可以是所以搜路径的终止也可以是搜索路径的中间节点。分支节点的父节点基本上就是扩展节点。

   十六进制字母表中有16个字符(0…9 A…F),如果某个节点有16个子节点,那么每个子节点对应一个字符占用4位,半个字节,被称为nibble。一个nibble被加到key之前,用到对终止符的状态和奇偶性进行编码。其中,最低位表示奇偶性,**0表示偶数,1表示奇数;**倒数第二位表示终止符状态。如果key是偶数位,则需要加上另外一个nibble。

  MPT树实现图(图片来源:以太坊黄皮书)
以太坊学习三: Merkle树和验证
   首先,根节点ROOT实际上是一个扩展节点,该节点进行SHA-3Hash计算后的值就是所谓三个Merkle根之一的stateRoot。这个扩展节点的key为其它实际节点的共有前缀(a7,key)两位字符,需要在前面补充前缀半字节nibble;value指向第一个分支节点,这个分支节点key包含(1,7,f)字符。其中1指向叶子节点,这个叶子节点为1335,偶数位补充前缀,因为是终止节点,nibble是0010=2,value是balance 45.0 ETH。第一个分支节点key中的7指向第二个扩展节点,他的key是后续两个叶子节点的共有前缀d3,偶数位补字符0,value指向第二个分支节点。这个分支节点包含3和9,其中3指向叶子节点1.00WEI,9指向0.12ETH的叶子节点,这两个叶子节点key都只有1位,而且是终止节点,所以补充的nibble前缀0011 =3 。第一个分会节点key还包含f,他指向1.1 ETH的叶子节点,这个叶子节点的key为9365,偶数位而且是终止节点,所以在前面补充前缀nibble0010=2。
   叶子键值对

keys values
a711355 45.0ETH
a77d337 1.00WEI
a7f9365 1.1ETH
a77d397 0.12ETH

   综上所述,以太坊MPT树具有如下特点

  • 叶子节点和分支节点可以保存value,扩展节点保存key
  • 没有公共的key就成为2个叶子节点
  • 如有公共的key则应该提取为一个扩展节点
  • 如果公共的key也是一个完整的key,那么数据应该保存到下一级的分支节点中

以太坊的应用

   在区块结构中包含区块头header,header里面包含3种树根

状态树:stateRoot

   状态树是全局的树
   path = sha3(ethereumAddress): 以太坊账户地址
   value=rlp([nonce,balance,storageRoot,codeHash]):交易次数、账户余额、存储树、合约代码Hash
  其中storageRoot是另一个trie树,用于存储合约中的所有数据,每个账户都有一个独立的storageRoot树

交易树: transactionsRoot

  每个block都有一个交易树。
   path = rlp(transactionIndex): 该交易在block中的索引,顺序由矿工决定
   value=交易记录
  该树生成后永远不会被修改

收据树:receiptsRoot

  每个block都有一个收据树。
   path = rlp(receiptIndex): 该交易在block中生成receipt的索引,顺序由矿工决定
   value=receipt记录
  该树生成后永远不会被修改文章来源地址https://www.toymoban.com/news/detail-462966.html

到了这里,关于以太坊学习三: Merkle树和验证的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 北京大学肖臻老师《区块链技术与应用》公开课笔记:以太坊原理(一):以太坊概述、账户、状态树、交易树和收据树

    1、ETH-以太坊概述 比特币和以太坊是两种最主要的加密货币,比特币被称为区块链1.0,以太坊被称为区块链2.0 以太坊在系统设计上针对比特币运行过程中出现的问题进行了改进,比如: 出块时间 ,比特币的区块时间是10分钟,以太坊的出块时间大幅度降低到了十几秒,而且

    2024年01月18日
    浏览(55)
  • 区块链学习笔记(2)难度整定,区块形成,区块体,Merkle树,Merkle Proof默克尔证明

           是在每个完整节点中独立自动发生的。每2016个区块,所有节点都会按统的公式自动调整难度,这个公式是由最新2016个区块的花要时长与期望时长(期望时长为20160分钟,即两周,是按每10分钟一个区块的产生速率计算出的总时长 )比较得出的,根据实际时长与期望时

    2023年04月08日
    浏览(75)
  • 【云计算学习教程】云计算技术与应用学习教程_资源所在地称为云端(也称云基础设施),输入输出设备称为云终端,将两者连接在一

    先自我介绍一下,小编浙江大学毕业,去过华为、字节跳动等大厂,目前阿里P7 深知大多数程序员,想要提升技能,往往是自己摸索成长,但自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前! 因此收集整理了一份《2024年最新大数据全套学习资料》,

    2024年04月27日
    浏览(38)
  • 轻松通关以太坊--以太坊简介

    2008 区块链1.0 比特币 简单记账 2014 区块链2.0 智能合约 出现 以太坊 2017 区块链3.0 高性能 大吞吐量 开发者友好 用户友好 EOS ArcBlock IOTA … Frontier 前沿 Homestead 家园 Metropolis大都会 又分为两个分叉 Byzantium 和 Constantinople(POW/POS共识算法) Serenity 宁静 世界计算机 开源全球分布的

    2024年02月05日
    浏览(33)
  • FPGA实现以太网(一)——以太网简介

    以太网(Ethernet)是当今现有局域网采用的最通用的通信协议标准, 该标准定义了在局域网中采用的电缆类型和信号处理方法。 以太网凭借其成本低、通信速率高、抗干扰性强等优点被广泛应用在网络远程监控、 交换机、工业自动化等对通信速率要求较高的场合。 以太网是一

    2024年02月03日
    浏览(50)
  • 以太坊区块链网络部署及验证实验

    国科大2023秋季学期计算机网络实验,简单记录一下实验流程 在 Ubuntu 上安装 Go 1.19 版本可以通过以下步骤进行: 1.1 下载 Go 1.19 首先,打开终端。从 Go 语言的官方网站下载最新版本。使用 wget 或 curl 命令下载 Go 1.19 的 tarball。 确保下载链接是最新的,可以在 Go 语言官方下载

    2024年02月04日
    浏览(76)
  • 区块链技术以太坊简介

    区块链技术(也称之为分布式账本技术) ,是一种互联网数据库技术,其特点是去中心化,公开透明,让每一个人均可参与的数据库记录 ❤️💕💕关于区块链技术,可以关注我,共同学习更多的区块链技术。个人博客http://nsddd.top 我们通常说的区块链都是指的是 公链 ,私

    2024年01月16日
    浏览(39)
  • 以太坊私钥介绍及生成与验证

    1)私钥格式 Bitcoin私钥(或其他加密货币私钥)有32 bytes,(或256个bit),或者其他形式表示,Base64 string、a WIF key、助记词 2)为什么是32bytes 3)生成方法 3.1)原生方法 该方法不适合用于加密货币,因为该方法不安全;该方法基于随机数种子生成,如果知道生成时的时间,容

    2024年02月15日
    浏览(43)
  • 【以太网芯片验证】SR8201F调试记录

    SR8201F是100M以太网芯片(PHY)支持MII/RMII接口 立创上有购买链接和方案验证板 SR8201F是商业级 SR8201FI是工业级 SR8201F样品售价 2+RMB 电话问过和芯德润的业务经理 SR8201F-1.5+RMB SR8201FI-2.5+RMB 加上汉仁的以太网接口6+ RMB 有源晶振3+ 电容电阻忽略不计 整个方案的成本在12RMB左右(工业级

    2024年02月15日
    浏览(37)
  • STM32以太网通信-LWIP简介

    LwIP全名:Light weight IP,意思是轻量化的TCP/IP协议,是瑞典计算机科学院(SICS)的Adam Dunkels 开发的一个小型开源的TCP/IP协议栈。 LwIP的设计初衷是:用少量的资源消耗实现一个较为完整的TCP/IP协议栈,其中“完整”主要指的是TCP协议的完整性,实现的重点是在保持TCP协议主要功能

    2024年02月07日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包