你好,我是币同学。这是我分享学习的第1天,每天学习进步一点点。
关键词:北大肖臻老师的公开课,关于以太坊的交易树和收据树。
1. 以太坊除了状态树外,还有交易树和收据树。
每次发布一个区块的时候,这个区块里所包含的交易会组织成一颗交易树,也是一颗Merkle tree,跟比特币中的情况是类似的。
同时以太坊还增加了收据树,每个交易执行完之后,会形成一个收据,记录交易的相关信息。
交易树和收据树上面的节点,是一一对应的。
增加收据树,主要是考虑到以太坊的智能合约执行过程比较复杂,所以通过增加收据树的结构,有利于快速查询一些执行的结果。
从数据结构上,交易树和收据树都是MPT(merkle patricia tree)。
这与比特币有所区别,比特币中的交易树就是用普通的Merkle tree(区块中的所有交易,组织成一颗普通的Merkle tree)。当然,MPT也是一种Merkle tree。
可能是为了方便,以太坊中的三颗树,都用同样的数据结构。这样代码比较统一,并且便于管理。
用MPT的一个好处是,它支持查找操作,即可以通过键值,从顶向下沿着这个树进行查找。
对于状态树来说,查找的键值就是该账户的地址。
对于交易树和收据树来说,查找的键值就是交易在发布的区块里面的序号(排序为第几)。交易的排列顺序,是由发布区块的节点决定的。
这三棵树,有一个重要的区别:交易树和收据树,都是只把当前发布的区块里的交易,组织起来的。而状态树,是把系统中所有账户的状态都要包含进去。不管这些账户,跟当前区块的交易有没有什么相关性。
从数据结构上讲,多个区块的状态树,是共享节点的。每次新发布一个区块的时候,只有这个区块中的交易改变了状态的那些节点,需要新建一个分支。其他的节点,都是沿用原来状态树上的节点即可。
相比之下,每个区块的交易树和收据树都是独立的,它们是不会共享节点的。一个区块和另外一个区块,发布交易的本身,我们也认为是独立的。
2. 交易树和收据树的用途?
一是提供Merkle Proof,就像比特币中交易树可以用来证明某个交易被打包到某个区块里,可以向轻节点提供Merkle Proof。
二是收据树也是类似的,要证明某个交易的执行结果,也可以在收据树里提供一个Merkle Proof。
除此之外,以太坊还支持一些更加复杂的查询操作:比如你想找到过去十天当中,所有跟某个智能合约有关的交易。
查询方法一:把过去十天产生的所有区块,都扫码一遍,看看其中有哪些交易是跟智能合约相关的。但这种方法的复杂度比较高,而且对于轻节点来说,实际上轻节点没有交易列表,它只有块头的信息。所以轻节点没有办法,通过扫描交易列表的方法,来找到符合查询条件的交易。
与之类似的查询,比如找到过去十天当中,符合某种类型的所有时间,比如说所有的众筹时间,或者是所有的发行新币的时间,这些都是需要比较高效的方法才能支持。
3. Bloom filter数据结构
可以支持比较高效的查找某个元素,是否在一个比较大的集合里面。
给大的包含很多元素的集合,计算出一个很紧凑的摘要。
比如说128位的向量:

如上图所示,abc元素各取哈希后,映射到向量中的各自位置,变成1。
所有的元素都处理完后,得到的向量,就是原来集合的一个摘要。这个摘要,比原来的集合要小很多。
这个摘要的用途?
比如有一个元素d,查询d元素是否在集合里,但集合本身不一定保存下来了。
用哈希函数,对d取哈希值后,映射到向量的其他位置,而且是0,说明元素d不在集合里。
假设d取完哈希值后,映射到a所映射的位置,而且也是1。说明d有可能就是集合里的元素d=a;有可能d不在集合里面,但是出现了哈希碰撞,恰好映射到了跟集合中某个元素一样的位置。
用Bloom filter,有可能出现假阳性(false positive),但不会出现假阴性(false negative)。
有可能出现误报,但不会出现漏报。(元素在里面,一定可以查询在里面;不在里面,也有可能查询在里面。)
简单的Bloom filter的局限性,不支持删除操作(比如例子中的a,不能删除,删除后取哈希的1,就有可能出现哈碰撞)。
4. 每个交易执行完后,在以太坊系统中,会形成一个收据。这个收据里面,就包含了一个Bloom filter,记录该交易的类型地址等信息。
发布的区块在块头里,有一个总的Bloom filter,总的Bloom filter是这个区块里,所有交易的Bloom filter的并集。
回到本文2点的例子,查询过去十天和智能合约的相关交易。
查询方法:先查一下哪个区块的块头里的Bloom filter,有要的交易的类型。
如果块头里的Bloom filter,没有的话,那这个区块不是我们想要的(过去十天和智能合约的相关交易并没有找到)。
如果块头的Bloom filter有的话,再查找区块里面包含的交易,所对应的收据树里面的那些Bloom filter(每个收据的Bloom filter)。
好处? 通过Bloom filter的结构,能够快速过滤掉大量无关的区块。(很多区块,看块头的Bloom filter,就知道肯定不会有我们要的交易。剩下的一些少数的候选区块,再进行仔细查看。)
比如说一个轻节点,轻节点只有块头信息,根据块头就可以过滤掉很多的区块。剩下有可能是你想要的那些区块,再去问全节点要一些进一步的信息。
5. 以太坊的三棵树的根哈希值,都是包括在块头里面的。
以太坊的运行过程,可以看做交易驱动的状态机。
状态机的状态就是所有账户的状态,状态数包括的那些内容。
交易是每次发布的区块里包括的那些交易,这些交易通过执行那些交易会驱动系统,从当前的状态转移到下一个状态。
比特币,也可以认为是由交易驱动的状态机。比特币中的状态是UTXO,没有被花掉的那些输出。每次新发布于一个区块,会从UTXO里用掉一些输出,增加一些新的输出。
所以发布这个区块,会驱动状态机从当前的状态,转移到下一个状态。UTXO,可以认为是比特币状态机中的状态。
而且这两个状态机,有一个共同的特点,即状态转移都得是确定性的。
对一个给定的当前状态,一组给定的交易(区块中包含了这组交易),能够确定性的转移到下一个区块。因为所有的全节点,所有的矿工,都要执行同样的状态转移。
今天就学习到这里,明天见。
201期【币圈人物】 计数员王纯|超级君【2019-11-29 1732】
“从童年起,我便独自一人照顾着,历代的星辰。” 这首短诗瞬间打动人心,将孤独写绝,远胜“独立寒江雪”和“念天地之悠悠”,揭示着浩瀚下的孤独,意象令人神往。翻看区块链朋友圈,若从中选一个人来当那个照顾历代星辰的孩子,王纯是不二人选。因为他也是一个孤独的大男孩,同时他对浩瀚的时空有着如痴如醉的爱好,计数是他照看的办法,数的递增,让他有着充实感和成就感。浩瀚无垠的星辰,是一个天文数字,数星星或许可以给他带来极致满足。 他从小就是一个计数员,远在他读初中的时候,第一天注册登陆QQ时,他就给自己的QQ名取名为1,第二天改为2,第三天改名为3.......光阴似箭,日月如梭,花开花落八年后,直到第2523天,他终于觉得这份计数过于无聊了,所以才放弃继续计数,其QQ名就停留在2523。2013年,在一个矿工群里,“2523”遇到了“七彩神仙鱼”。当时七彩神仙鱼是半个中国矿工的老师傅,从显卡时代到阿瓦隆矿机时代,从QQ群到论坛。说到这里,想起当年还有一个“传说哥“,50元教挖矿,风吹雨打,几年后,神鱼还是神鱼,传说哥早没了传说。总而言之,王纯和神鱼几经交流之后,决定联手打造一个比特币矿池,矿池名...
235期【基础知识】 北纬老师---比特币常见问题
本内容来自于北纬老师 前言: 这个帖子主要是为新手解惑,目前币圈因为在国内未被统一化,一如既往对新手很不友好,甚至连你开始下载的交易所app都有可能是假的,这个帖子主要是为了避免新手踏坑。 当你决定进入这个市场,一定要明白,这是一个无涨跌限制、24小时全球不间断交易、风险巨大的市场。的确,很多人在这个市场里面,赚取了无数财富,完成人生越级,这些故事每天都在被人津津乐道口口相传,但是,更多的是,无数人亏损黯然离场,只是他们一直保持沉默。 1.比特币是什么。 比特币是一个共识网络,促成了一个全新的支付系统和一种完全数字化的货币。可以把比特币理解为2个层面:1.这是一个去中心支付系统;2.数字互联网货币。 比特币总量为2100万枚,通过“挖矿”形式,每十分钟产生一个块,块里面包含50个比特币和手续费。块奖励是每四年减半一次,第一次减半后块奖励为25个比特币,第二次是12.5,目前块奖励为6.25个比特币。 2.新人对比特币的误解。 1)市面上显卡断货,涨价,却不是用来挖比特币的; 2)比特币在国内并不违法,公民可以合法持有,但,金融机构禁止进入,国内不允许开交易所,且国内比特币并不能称...
币圈人士必备工具(收藏)
币圈新闻、资讯金色财经网址:https://www.jinse.com/ 目前国内最大的区块链行业新闻媒体平台,资讯行情做的都还可以,特色:签约作者比较多,内容差异化做的不错。巴比特网址:https://www.8btc.com/ 巴比特创始人长侠,依靠论坛起家,里面有很多牛人,现在转型做新闻平台,旗下链节点论坛做的也不错。传统输出型媒体,资讯内容丰富且质量较高,特色:老牌资讯行情软件,综合实力最强。火星财经网址:https://www.huoxing24.com/ 火星是区块链行业新闻媒体平台,定位和金色差不多,优点是可以听新闻。区块链头条网址:http://blocktop.cn/Home/Index/index.html 区块链头条是新锐区块链媒体品牌,聚焦全球区块链行业资讯,专注于区块链产业的服务平台。集快讯、时讯、深研、行情、课堂等为一体。7*24 小时行业资讯追踪报道,秉承“客观、真实、深度”的理念,服务全球区块链领域生态。 行情软件Aicoin网址:https://www.aicoin.cn/ 炒币软件必备,圈子里用的人挺多的。Aicoin适合技术分析派,里面有很多...
同学区块链,同学数字货币。
你好,我是币同学。这是我分享学习的第1天,每天学习进步一点点。
关键词:北大肖臻老师的公开课,关于以太坊的交易树和收据树。
1. 以太坊除了状态树外,还有交易树和收据树。
每次发布一个区块的时候,这个区块里所包含的交易会组织成一颗交易树,也是一颗Merkle tree,跟比特币中的情况是类似的。
同时以太坊还增加了收据树,每个交易执行完之后,会形成一个收据,记录交易的相关信息。
交易树和收据树上面的节点,是一一对应的。
增加收据树,主要是考虑到以太坊的智能合约执行过程比较复杂,所以通过增加收据树的结构,有利于快速查询一些执行的结果。
从数据结构上,交易树和收据树都是MPT(merkle patricia tree)。
这与比特币有所区别,比特币中的交易树就是用普通的Merkle tree(区块中的所有交易,组织成一颗普通的Merkle tree)。当然,MPT也是一种Merkle tree。
可能是为了方便,以太坊中的三颗树,都用同样的数据结构。这样代码比较统一,并且便于管理。
用MPT的一个好处是,它支持查找操作,即可以通过键值,从顶向下沿着这个树进行查找。
对于状态树来说,查找的键值就是该账户的地址。
对于交易树和收据树来说,查找的键值就是交易在发布的区块里面的序号(排序为第几)。交易的排列顺序,是由发布区块的节点决定的。
这三棵树,有一个重要的区别:交易树和收据树,都是只把当前发布的区块里的交易,组织起来的。而状态树,是把系统中所有账户的状态都要包含进去。不管这些账户,跟当前区块的交易有没有什么相关性。
从数据结构上讲,多个区块的状态树,是共享节点的。每次新发布一个区块的时候,只有这个区块中的交易改变了状态的那些节点,需要新建一个分支。其他的节点,都是沿用原来状态树上的节点即可。
相比之下,每个区块的交易树和收据树都是独立的,它们是不会共享节点的。一个区块和另外一个区块,发布交易的本身,我们也认为是独立的。
2. 交易树和收据树的用途?
一是提供Merkle Proof,就像比特币中交易树可以用来证明某个交易被打包到某个区块里,可以向轻节点提供Merkle Proof。
二是收据树也是类似的,要证明某个交易的执行结果,也可以在收据树里提供一个Merkle Proof。
除此之外,以太坊还支持一些更加复杂的查询操作:比如你想找到过去十天当中,所有跟某个智能合约有关的交易。
查询方法一:把过去十天产生的所有区块,都扫码一遍,看看其中有哪些交易是跟智能合约相关的。但这种方法的复杂度比较高,而且对于轻节点来说,实际上轻节点没有交易列表,它只有块头的信息。所以轻节点没有办法,通过扫描交易列表的方法,来找到符合查询条件的交易。
与之类似的查询,比如找到过去十天当中,符合某种类型的所有时间,比如说所有的众筹时间,或者是所有的发行新币的时间,这些都是需要比较高效的方法才能支持。
3. Bloom filter数据结构
可以支持比较高效的查找某个元素,是否在一个比较大的集合里面。
给大的包含很多元素的集合,计算出一个很紧凑的摘要。
比如说128位的向量:

如上图所示,abc元素各取哈希后,映射到向量中的各自位置,变成1。
所有的元素都处理完后,得到的向量,就是原来集合的一个摘要。这个摘要,比原来的集合要小很多。
这个摘要的用途?
比如有一个元素d,查询d元素是否在集合里,但集合本身不一定保存下来了。
用哈希函数,对d取哈希值后,映射到向量的其他位置,而且是0,说明元素d不在集合里。
假设d取完哈希值后,映射到a所映射的位置,而且也是1。说明d有可能就是集合里的元素d=a;有可能d不在集合里面,但是出现了哈希碰撞,恰好映射到了跟集合中某个元素一样的位置。
用Bloom filter,有可能出现假阳性(false positive),但不会出现假阴性(false negative)。
有可能出现误报,但不会出现漏报。(元素在里面,一定可以查询在里面;不在里面,也有可能查询在里面。)
简单的Bloom filter的局限性,不支持删除操作(比如例子中的a,不能删除,删除后取哈希的1,就有可能出现哈碰撞)。
4. 每个交易执行完后,在以太坊系统中,会形成一个收据。这个收据里面,就包含了一个Bloom filter,记录该交易的类型地址等信息。
发布的区块在块头里,有一个总的Bloom filter,总的Bloom filter是这个区块里,所有交易的Bloom filter的并集。
回到本文2点的例子,查询过去十天和智能合约的相关交易。
查询方法:先查一下哪个区块的块头里的Bloom filter,有要的交易的类型。
如果块头里的Bloom filter,没有的话,那这个区块不是我们想要的(过去十天和智能合约的相关交易并没有找到)。
如果块头的Bloom filter有的话,再查找区块里面包含的交易,所对应的收据树里面的那些Bloom filter(每个收据的Bloom filter)。
好处? 通过Bloom filter的结构,能够快速过滤掉大量无关的区块。(很多区块,看块头的Bloom filter,就知道肯定不会有我们要的交易。剩下的一些少数的候选区块,再进行仔细查看。)
比如说一个轻节点,轻节点只有块头信息,根据块头就可以过滤掉很多的区块。剩下有可能是你想要的那些区块,再去问全节点要一些进一步的信息。
5. 以太坊的三棵树的根哈希值,都是包括在块头里面的。
以太坊的运行过程,可以看做交易驱动的状态机。
状态机的状态就是所有账户的状态,状态数包括的那些内容。
交易是每次发布的区块里包括的那些交易,这些交易通过执行那些交易会驱动系统,从当前的状态转移到下一个状态。
比特币,也可以认为是由交易驱动的状态机。比特币中的状态是UTXO,没有被花掉的那些输出。每次新发布于一个区块,会从UTXO里用掉一些输出,增加一些新的输出。
所以发布这个区块,会驱动状态机从当前的状态,转移到下一个状态。UTXO,可以认为是比特币状态机中的状态。
而且这两个状态机,有一个共同的特点,即状态转移都得是确定性的。
对一个给定的当前状态,一组给定的交易(区块中包含了这组交易),能够确定性的转移到下一个区块。因为所有的全节点,所有的矿工,都要执行同样的状态转移。
今天就学习到这里,明天见。
201期【币圈人物】 计数员王纯|超级君【2019-11-29 1732】
“从童年起,我便独自一人照顾着,历代的星辰。” 这首短诗瞬间打动人心,将孤独写绝,远胜“独立寒江雪”和“念天地之悠悠”,揭示着浩瀚下的孤独,意象令人神往。翻看区块链朋友圈,若从中选一个人来当那个照顾历代星辰的孩子,王纯是不二人选。因为他也是一个孤独的大男孩,同时他对浩瀚的时空有着如痴如醉的爱好,计数是他照看的办法,数的递增,让他有着充实感和成就感。浩瀚无垠的星辰,是一个天文数字,数星星或许可以给他带来极致满足。 他从小就是一个计数员,远在他读初中的时候,第一天注册登陆QQ时,他就给自己的QQ名取名为1,第二天改为2,第三天改名为3.......光阴似箭,日月如梭,花开花落八年后,直到第2523天,他终于觉得这份计数过于无聊了,所以才放弃继续计数,其QQ名就停留在2523。2013年,在一个矿工群里,“2523”遇到了“七彩神仙鱼”。当时七彩神仙鱼是半个中国矿工的老师傅,从显卡时代到阿瓦隆矿机时代,从QQ群到论坛。说到这里,想起当年还有一个“传说哥“,50元教挖矿,风吹雨打,几年后,神鱼还是神鱼,传说哥早没了传说。总而言之,王纯和神鱼几经交流之后,决定联手打造一个比特币矿池,矿池名...
235期【基础知识】 北纬老师---比特币常见问题
本内容来自于北纬老师 前言: 这个帖子主要是为新手解惑,目前币圈因为在国内未被统一化,一如既往对新手很不友好,甚至连你开始下载的交易所app都有可能是假的,这个帖子主要是为了避免新手踏坑。 当你决定进入这个市场,一定要明白,这是一个无涨跌限制、24小时全球不间断交易、风险巨大的市场。的确,很多人在这个市场里面,赚取了无数财富,完成人生越级,这些故事每天都在被人津津乐道口口相传,但是,更多的是,无数人亏损黯然离场,只是他们一直保持沉默。 1.比特币是什么。 比特币是一个共识网络,促成了一个全新的支付系统和一种完全数字化的货币。可以把比特币理解为2个层面:1.这是一个去中心支付系统;2.数字互联网货币。 比特币总量为2100万枚,通过“挖矿”形式,每十分钟产生一个块,块里面包含50个比特币和手续费。块奖励是每四年减半一次,第一次减半后块奖励为25个比特币,第二次是12.5,目前块奖励为6.25个比特币。 2.新人对比特币的误解。 1)市面上显卡断货,涨价,却不是用来挖比特币的; 2)比特币在国内并不违法,公民可以合法持有,但,金融机构禁止进入,国内不允许开交易所,且国内比特币并不能称...
币圈人士必备工具(收藏)
币圈新闻、资讯金色财经网址:https://www.jinse.com/ 目前国内最大的区块链行业新闻媒体平台,资讯行情做的都还可以,特色:签约作者比较多,内容差异化做的不错。巴比特网址:https://www.8btc.com/ 巴比特创始人长侠,依靠论坛起家,里面有很多牛人,现在转型做新闻平台,旗下链节点论坛做的也不错。传统输出型媒体,资讯内容丰富且质量较高,特色:老牌资讯行情软件,综合实力最强。火星财经网址:https://www.huoxing24.com/ 火星是区块链行业新闻媒体平台,定位和金色差不多,优点是可以听新闻。区块链头条网址:http://blocktop.cn/Home/Index/index.html 区块链头条是新锐区块链媒体品牌,聚焦全球区块链行业资讯,专注于区块链产业的服务平台。集快讯、时讯、深研、行情、课堂等为一体。7*24 小时行业资讯追踪报道,秉承“客观、真实、深度”的理念,服务全球区块链领域生态。 行情软件Aicoin网址:https://www.aicoin.cn/ 炒币软件必备,圈子里用的人挺多的。Aicoin适合技术分析派,里面有很多...
同学区块链,同学数字货币。

Subscribe to 币同学

Subscribe to 币同学
Share Dialog
Share Dialog
<100 subscribers
<100 subscribers
No activity yet