精华内容
下载资源
问答
  • 文章目录一、状态树1.1 trie1.2 Patricia tree(trie)1.3 Merkle Patricia tree(trie)1.4 Modified Merkle Patricia tree(trie)1.5 账户状态值存储二、交易树收据树2.1 概述2.2 Modified Merkle Patricia tree(trie...
  • 每次发布的区块中,交易会组织成一棵交易树,也是一棵merkle tree,...对于状态树来说,查找账户状态所用的key是地址,对于交易树收据树来说,查找的键值就是交易在区块中的序号,交易的排列顺序由发布区块的节点决定
  • 以太坊中还有另外两棵树:交易树收据树。 每次发布一个区块的时候,这个区块里所包含的交易会组织成一个交易树,也是一颗Merkle tree。同时以太坊还增加了一个收据树,每个交易执行完之后会形成一个收据记录这个...

    以太坊中还有另外两棵树:交易树和收据树。

    每次发布一个区块的时候,这个区块里所包含的交易会组织成一个交易树,也是一颗Merkle tree。同时以太坊还增加了一个收据树,每个交易执行完之后会形成一个收据记录这个交易的相关信息。交易树与收据树上面的节点是一一对应的。增加这个收据树主要是考虑到了以太坊的智能合约比较复杂,所以通过收据树的结构有利于我们快速查询一些执行的结果。

    从数据结构上将,交易树与收据树都是MPT,与比特币中的交易树有所区别,比特币中的交易树就是普通的Merkle tree。

    MPT的一点好处是支持查找操作,通过键值从顶向下沿着树进行查找即可。对于状态树来说,查找的键值就是这个账户的地址,对于交易树和收据树的键值为交易在发布的区块中的序号,交易的排列顺序是由发布区块的节点决定的。

    三棵树的区别:
    交易树和收据树只将当前区块中的交易组织起来,而状态树将所有账户的状态都包含进去,无论这些账户是否与当前区块中交易有关系。
    多个区块状态树共享节点,而交易树和收据树是独立的,他们是不共享节点的。

    交易树和收据树的用途:

    1. 向轻节点提供Merkle Proof。证明某个交易被打包到某个区块里面了。
    2. 更加复杂的查找操作(例如:查找过去十天当中所有跟某个智能合约有关的交易;过去十天的众筹事件等)

    Bloom filter
    支持较为高效查找某个元素是否在某个大的集合中。例如某个很大的集合,要知道有没有我要想查找的元素。
    最笨:元素遍历,复杂度为线性的,O(n)——轻节点不能用
    方法:给一个大的集合,通过计算每个元素的哈希值,出一个紧凑的“摘要”,可以较为便捷的查找是否在集合中。

    例:给定一个数据集,其中含义元素a、b、c,通过一个哈希函数H()对每一个元素进行计算,将每一个元素取哈希之后映射到一个初始值全为0的向量中的某一个位置。然后映射到位置的向量的元素由0变为1。所有元素都处理完了,就可以得到一个向量,这就成了这个集合的digest(摘要)了。
    在这里插入图片描述

    假定想要查询一个元素d是否在集合中,假设H(d)映射到向量中的位置处为0,说明d一定不在集合中;假设H(d)映射到向量中的位置处为1,有可能集合中确实有d,也有可能因为哈希碰撞产生误报。

    Bloom filter特点:有可能出现误报,但不会出现漏报。
    bloom filter有各种变种,有的不是用一个哈希函数,有的使用一组哈希函数。每个哈希函数独立的把元素映射到向量中的某一个位置,用一组哈希函数的好处是,一般来说,当某一个哈希函数出现碰撞的时候,不会所有的哈希函数都出现哈希碰撞,这样就可以有效解决误报问题。

    如何集合中删除元素该怎么操作?
    无法操作。也就是说,简单的Bloom filter的局限性是不支持删除操作。如果想要支持删除操作,需要将记录数不能为简单的二进制0和1,需要修改为一个计数器,记录这个位置有多少个元素映射过来,而且还要需要考虑计数器是否会溢出。这样的设计复杂的太多了,与当初设计bloom filter初衷相违背的。所以一般来说,bloom filter不支持删除操作。

    以太坊中Bloom filter的作用
    每个交易完成后会产生一个收据,收据包含一个Bloom filter记录交易类型、地址等信息。在区块block header中也包含一个总的Bloom filter,其为该区块中所有交易的Bloom filter的一个并集。
    所以,查找时候先查找哪一个区块的块头中的Bloom filter中有我需要的类型,如果块头bloom filter里面没有我们想要的话,就可以确定这个区块不是我们想要的。如果块头bloom filter中包含,再查看区块中包含的交易所对应的那些收据树里面的Bloom filter,看看哪个有,也可能都没有,因为有可能是false positive,如果存在,将查看交易直接进行一下确认。
    好处是通过Bloom filter这样一个结构,快速大量过滤掉大量无关的区块,从而提高了查找效率。

    以太坊的运行过程,可以视为交易驱动的状态机(transaction-driven state machine)。这个状态机的状态就是所有账户的状态,即状态树中包含的那些内容,交易就是每次发布的区块里包含的那些交易,通过执行这些交易会驱动系统从当前状态转移到下一个状态。
    BTC我们也可以视为交易驱动的状态机,其状态为UTXO,没有被花掉的那些输出。
    以太坊与比特币状态有一个共同特点,状态转移是确定性的。对于给定的当前状态和给定一组交易,可以确定性的转移到下一状态(保证系统一致性)。

    问题1:A转账到B,有没有可能收款账户不包含再状态树中?
    可能。和比特币系统一样,因为以太坊中账户可以节点自己产生,只有在产生交易时才会被系统知道。
    问题2:可否将每个区块中状态树更改为只包含和区块中交易相关的账户状态?(大幅削减状态树大小,且和交易树、收据树保持一致)
    不能。首先,这样设计的话,每个区块没有一颗完整的状态树,只有当前区块所包含的交易涉及到的状态。这样会产生一个问题,要查找账户状态很不方便,因为不存在某个区块包含所有状态。
    其次,如果要向一个新创建账户转账,因为需要知道收款账户的状态,才能给其添加金额,但由于其是新创建的账户,需要一直找到创世纪块才能知道该账户为新建账户。

    具体代码讲解在视频后半段:https://www.bilibili.com/video/BV1Vt411X7JF?p=17

    展开全文
  • 1、定义: 交易树:每次发布区块时,区块中...2、交易树收据树状态树的区别: 交易树收据树都是只组织当前发布的区块的交易,所以每个区块的交易树收据树是独立的。 而状态树包含了系统中所有账户的状态,

    1、定义:

    • 交易树:每次发布区块时,区块中的交易会组织成一颗交易树。
    • 收据树:每个交易执行完后,会形成一个收据,该收据中包含一个bloom filter,用来记录交易的相关信息。所以交易树与收据树节点是一一对应的。增加收据树是因为以太坊的智能合约执行过程比较复杂,所以收据树有利于快速查询执行结果。从数据结构上来说,交易树和收据树都是MPT。

    2、交易树、收据树、状态树的区别:

    交易树、收据树都是只组织当前发布的区块的交易,所以每个区块的交易树、收据树是独立的。

    而状态树包含了系统中所有账户的状态,所以多个区块的状态树的共享节点的,每次新发布一个区块的时候,只有新发布的区块的交易改变了状态的节点需要新建一个分支,其他节点会沿用之前的节点。

    这三棵树的根哈希值都保存在块头(block header)中。

    3、交易树、收据树的作用:

    提供Merkle Proof,要证明某个交易的执行结果,需要在收据树中提供一个Merkle Proof。

    4、bloom filter

    可以高效查找某个特定元素是否在一个比较大的集合中。

    实现方法:

    把一个大的集合计算出一个紧凑的摘要(digest),比如一个128位的向量。该向量初始值为0,然后将集合中的元素取哈希映射到向量中的对应位置,该位置的值置为1。得到的这个向量就是摘要,它比集合要小很多。

    如果想要判断一个元素是否在集合中,则对该元素取哈希值,映射到集合中,如果集合中该位置为0,则元素不在这个集合中。如果集合中该位置为1,则无法判断该元素是否在集合中。因为存在哈希碰撞,集合中可能有另外一个元素也映射到这个位置。这也是简单的bloom filter不支持删除操作的原因。要想实现删除,需要计数器计算该位置有多少个元素映射,还要考虑到计数器会不会overflow,这种数据结构就会很复杂。

    所以,对于bloom filter而言,存在false positive,在集合中的元素一定会判断在里面,不在集合中的元素也有可能判断在里面。

    在以太坊中,发布的区块在块头中有一个总的bloom filter,是这个区块里所有交易的并集。

    所以,如果要查找过去10天和这个只能合约相关的所有的交易,则先查找各个区块的块头的bloom filter是否存在所需的交易内容。如果块头的bloom filter中有需要查找的交易内容,再去查找区块里面的交易所对应的数据库里的bloom filter。

    所以,通过bloom filter,可以快速过滤掉无关区块,提高查找效率。

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    以太坊的运行过程可以看作是交易驱动的状态机(transaction-driven state machine),通过执行交易,驱动系统从当前的状态转移到下一个状态。

    以太坊和比特币一样,创建账户的时候不需要通知其他人,只有账户第一次收到钱的时候,其他节点才会知道该账户的存在。此时在状态树中新插入一个节点。

    为什么状态树需要保存系统中所有账户的状态,可不可以只保存与当前交易相关的状态信息?

    这样设计的话,每个区块没有一颗完整的状态树,不便于查找某个账户的状态。

    比如A转给B10个以太币,则需要检查A中是否有10个以太币,那么A最近的区块可能没有A这个账户,则需要往前找,直到找到包含A这个账户的最近的区块,才能知道A账户的余额。所以如果A在很长时间没有进行交易,就需要找很多个区块才能找到A的区块状态。

    还存在一个问题,A在给B转账的时候也需要知道B账户的状态,才能在B的账户上加10个以太币。如果B是新建的账户,则需要查找每个区块,一直找到创世纪块才会发现B账户是新建的。

    展开全文
  • ETH-17交易树收据树

    2020-03-27 09:46:11
    内容整理自 北京大学肖臻老师《区块链技术与应用》公开课ETH-17交易树收据树 每次发布一个区块,区块中所包含的交易会组织成一棵交易树。每个交易执行完之后会形成一个收据,记录交易的相关信息,交易树收据树...

    内容整理自 北京大学肖臻老师《区块链技术与应用》公开课 ETH-17交易树和收据树

    每次发布一个区块,区块中所包含的交易会组织成一棵交易树。每个交易执行完之后会形成一个收据,记录交易的相关信息,交易树与收据树上的节点是一一对应的。增加收据树是考虑到以太坊的智能合约执行过程比较复杂,所以通过增加收据树的结构有利于快速查询一些执行结果。交易树和收据树都是MPT,比特币中的交易树是普通的merkle tree。 

    三棵树有一个重要的区别

    交易树和收据树都是只把当前发布的区块里的交易组织起来的。而状态树是把系统中所有账户的状态都要包含进去,不管这些账户和当前这些交易有没有关系。
    多个区块的状态树是共享节点的,每次新发布一个区块的时候,只有区块中的交易改变了状态的节点需要新建分支,其他节点沿用原状态树的节点。相比之下,每个区块的交易树和收据树都是独立的,不会共享节点。

    交易树和收据树的作用

    1.提供merkle proof,证明某个交易的执行结果
    2.支持更复杂的查询操作,比如想找到过去十天中和某个智能合约有关的交易,一种做法是把过去十天产生的所有区块都扫描一遍,看其中哪些交易是和智能合约相关。该方法复杂度高,而且对于轻节点来说,没有交易列表,没办法通过扫描所有交易列表的方法来找到符合条件的交易。还有就是查找过去十天符合某种类型的交易事件(如众筹事件,发行新币事件),这些需要高效的方法才能支持。
    以太坊中引用了bloom filter数据结构,该数据结构支持比较高效的查找某个元素是否在一个比较大的集合中。比如一个集合中有很多元素,想知道某个指定元素是否在集合中。bloom filter给包含很多元素的集合计算出一个紧凑的摘要,比如一个128bits的向量,向量初始的时候都是0,有一个哈希函数H,把每个元素映射到向量中的某个位置,该位置的元素就从0变成1。等到所有元素都处理完,得到的向量就是原集合的一个摘要,该摘要比集合小很多。
    如果要判断一个元素是否在集合中,集合本身可能不被保存,用哈希函数对元素取哈希值,如果取完之后发现映射到一个0的位置,说明该元素一定不在集合中,如果映射到一个1的位置,该元素可能在集合中,也可能不在集合中,出现了哈希碰撞。bloom filter可能会出现false positive,但不会出现false negative。可能会误报,但不会漏报。另外bloom filter不支持删除操作。
    每个交易执行完之后会形成一个收据,收据里面包含一个bloom filter,记录交易的类型,地址等信息,发布的区块在块头中有一个总的bloom filter,是区块里所有bloom filter的一个并集。所以如果要找到过去十天中和某个智能合约有关的交易,先查哪个区块的块头里的bloom filter有我要的交易的类型。如果块头里没有,那么这个区块就不是我们要找的。如果块头的bloom filter里有的话,再去查找区块里面包含的交易所对应的收据树里面的那些bloom filter,看看哪个有,也可能都没有,因为false positive,如果有再找到对应的交易确认。这样的好处是通过bloom filter的结构,能够快速过滤掉大量无关的区块。

    交易驱动的状态机

    以太坊的运行过程可以看作是一个交易驱动的状态机transaction-driven state machine,状态机的状态就是所有账户的状态(状态树包含的内容),交易是每次发布的区块里包含的交易,通过执行这些交易会驱动系统从当前的状态转移到下一个状态。

    比特币也可以认为是一个交易驱动的状态机,比特币中状态是UTXO,每次新发布一个区块,会从UTXO中用掉一些输出,又会增加一些新的输出,所以发布的区块会驱动状态机从当前状态转移到下一个状态。

    两个状态机一个共同点就是状态转移都必须是确定性的,对一个给定的当前状态,一组给定的交易,能够确定性的转移到下一个状态,因为所有的全节点、矿工都要执行同样的状态转移。

    展开全文
  • 交易树收据树状态树有一个比较大的区别,交易树收据树只把当前区块发布的交易组织起来,而状态树是要把系统中所有的账户状态都要包含进去,不管这些账户和当前区块的交易有无关系。 每个区块的交易树收据树...

    交易树和收据树

    交易树和收据树也是MPT。交易树和收据树与状态树有一个比较大的区别,交易树和收据树只把当前区块发布的交易组织起来,而状态树是要把系统中所有的账户状态都要包含进去,不管这些账户和当前区块的交易有无关系。

    每个区块的交易树和收据树都是独立的,它们是不会共享节点的。

    作用

    交易树: 提供Merkel Proof。向轻节点证明某个交易是打包在区块中的。
    收据树: 向轻节点证明某个交易的执行结果。

    如何高效的查询某个交易在哪个区块中?
    以太坊为了高效的查询某个区块中的某个交易,引入了bloom filter这种数据结构。
    bloom filter 可以参考 https://blog.csdn.net/jiaomeng/article/details/1495500
    通过bloom filter 这种数据结构,可以在区块头中快速查找某个交易是否被保存在该区块中。然后再向全节点请求具体的数据。

    以太坊的运行过程可以看作是交易驱动的状态机

    • 状态 以太坊中的状态树中包含的内容,交易 每次发布的区块中包含的交易。通过执行这些交易,会将状态树中的状态从当前状态转移到交易后的状态。
    展开全文
  • 目录账户类型ETH状态树ETH交易树收据树区块结构ETH GHOSTETH 挖矿算法 账户类型 Account-based ledger 以太坊,显式的体现账户余额 账户类型: 外部账户(普通账户)externally owned account,由公私钥控制,...
  • 增加这个收据树,主要是考虑到以太坊的智能合约执行过程比较复杂,所以通过增加收据树的结构有利于我们快速查询一些执行的结果,从数据结构上,交易树收据树都是MPT,这个跟比特币中有所区别,比特币的交易树就是...
  • 17.ETH 交易树收据树 以太坊中,每次发布一个区块的时候,区块里所包含的交易会组成一棵交易树, 也是一棵Merkle Tree,和BTC类似。每个交易执行完成之后会生成一个收据,记录交易的相关信息。交易树收据树上面...
  • 交易树收据树只把当前区块里的交易包含进去,状态数要把所有账户的状态包含进去 交易树收据树有什么用呢? 提供Merkle Proof 所有与某个智能合约有关的交易,所有众筹事件。需要高效的查询效率,怎么办呢? ...
  • 北京大学肖臻老师《区块链技术与应用》公开课笔记 以太坊数据结构篇3——交易树收据树,对应肖老师视频:...本打算将收据树交易树分开写两篇,但实际上分开内容太少,就此...
  • 17 交易树和数据树

    2020-02-18 10:55:45
    同时,以太坊增加了一棵收据树,每个交易完成之后会形成一个收据,记录这个交易的相关信息,就是交易树收据树上面的节点是一一对应的,增加这个收据树主要是考虑到以太坊的智能合约执行过程比较复杂,所以增加...
  • 以太坊黄皮书中的一些概念。通过本文,我们将学到以太坊中一些主要...能在脑海中勾勒出交易以及区块的结构。 默克尔 在讨论以太坊的主要数据对象之前,我想先向各位简要介绍一下默尔克到底是什么,以使得它...
  • 以太坊状态树

    千次阅读 2020-01-08 22:07:24
    我们要完成的是账户地址到账户状态的映射,addr→state,以太坊用的账户地址是160bits,一般表示成40个十六进制数,状态是外部账户的状态和合约账户的状态,包括余额,交易数,对于合约账户,还包括代码和存储。...
  • 在以太坊中,有三棵树的说法,分别是状态树收据树交易树。了解了这三棵树,就弄清楚了以太坊的基础数据结构设计。 而以太坊实现的是一个"平台性"的应用,其复杂性必然较高。因此,其内部数据结构设计...
  • 十五、以太坊中的状态树 以太坊采用基于账户的模式,系统中显式地维护每个账户上有多少余额,今天看一下用什么样的数据结构来实现account-based ledger。 完成的功能:从账户地址到账户状态的映射,addr->state。...
  • Merkle Tree(默克尔)算法解析

    万次阅读 多人点赞 2017-01-20 17:52:14
    Merkle Tree,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵。Merkle的叶子是数据块(例如,文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1]1、HashHash是一个把任意长度的...
  • txhash 交易树的根hash值:类似于比特币系统中的根hash值 receipthash 收据树的根hash值: difficulty:挖矿的难度 number: 智能合约要消耗汽油费,类似...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 649
精华内容 259
关键字:

交易树收据树状态树