内容简介:比特币中使用哈希指针保存前一个区块头的哈希值,将多个区块连接成一条链,保证了区块链的不可篡改特性。比特币还使用梅克尔树保存区块体中的交易数据,从最底层的交易数据通过哈希指针层层传递到根哈希,浓缩了所有的交易数据,提高了篡改交易的难度。梅克尔树还提供交易数据隶属证明和非隶属证明的高效方法,时间复杂度均为O(log N)。本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。
比特币中使用哈希指针保存前一个区块头的哈希值,将多个区块连接成一条链,保证了区块链的不可篡改特性。比特币还使用梅克尔树保存区块体中的交易数据,从最底层的交易数据通过哈希指针层层传递到根哈希,浓缩了所有的交易数据,提高了篡改交易的难度。梅克尔树还提供交易数据隶属证明和非隶属证明的高效方法,时间复杂度均为O(log N)。
哈希指针H( )
比特币中通过哈希指针将多个区块连接成一条链。在本质上,区块链也是一个链表,只不过用哈希指针代替了普通指针。
为了说明哈希指针的优点,我们先了解一下 单向链表(singly-linked list)和普通指针 。
以C++为例,单向链表中的节点通常是结构体数据类型,包含节点的值val和指向下一个节点的指针next。
//单向链表节点 结构体,包含节点的值val和指向下一个节点的指针next struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };
Node 0又称为根节点(root node),根节点是链表的初始节点,没有指向任何节点,因此根节点的next指针为空(Node 0.next = NULL)。Node 1中的next指针存储了Node 0的地址(Node 1. next = Node 0_address),指向Node 0。同理,Node 2指向Node1, Node 3指向Node 2... 如果要往链表中加入新节点,只需要新建一个节点,并将新节点的next指针指向链表的末尾节点。链表相比于数组的优势是什么?链表的可扩展性更强,一个数组中的元素在磁盘上是先申请一块空间然后连续存储的,而链表中的节点元素可以存储在不同的磁盘位置,通过指针存储下一个节点的地址,然后去磁盘上寻址找到下一个节点。如果要修改链表中的某个节点的值,我们可以寻址找到该节点,并修改节点的值val即可。
在使用普通指针的单向链表中,我们可以随意修改任意节点的值val,而不会破坏链表的完整性。如果比特币也采用普通指针连接成一个普通链表,那我们就可以任意修改区块中的交易信息,这就破坏了区块链的不可篡改特性(严格来说,是难以篡改)。 相比于普通指针,哈希指针不仅能把区块连接成一条链,还能保证区块不可篡改。 一个区块(Block)的结构,包含区块头(Block Header)和区块体(Block Body) ,下图简单列举了Block Header和Block Body中包含的数据信息,区块结构的具体内容我将在系列博客3-比特币协议中详细讲解。
哈希指针H( )是对上一个区块的Block Header取哈希值,Block Header中的Merkle Tree哈希值已经包含了Block Body的信息,这也是为什么只需要对Block Header 取哈希的原因,减少了哈希函数的输入数据大小从而提高哈希运算的速度。Block 0又称为创世区块(genesis block),Block 1中的H()为Block 0 header的哈希值,Block 2中的H()为Block 1 header的哈希值······ 如果有新区块要加进来,只需把最末尾区块的header哈希值计算出来,放在新区块的header中即可,这样就连接成了一条区块链。
哈希指针提高了篡改的难度,防止篡改区块中的数据。假设我修改了Block 1中的数据,那么根据哈希函数的碰撞阻力特性,Block 1 header的哈希值发生变化,那么我就要修改Block 2 header中的哈希指针,Block 2 header发生变化,同理我也需要修改Block 3 header······ 相当于一个连锁反映,篡改区块链中的某个区块,就需要篡改该区块之后的所有区块,大大提高了篡改区块的难度 。
Merkle Tree(梅克尔树)
Block body中存储交易信息的数据结构就是Merkle Tree。Merkle Tree根哈希反映了所有的交易信息,修改任意一个交易数据都会造成根哈希的变化,防止篡改交易数据,并且能够快速验证某笔交易属于这个区块(隶属证明)或者不属于这个区块(非隶属证明)。
相比于普通的二叉树,Merkle Tree采用了哈希指针代替普通指针,提高了篡改交易的难度。 Merkle Tree的最底层叶子节点存的是交易信息 ,对每一笔交易取哈希值得到H( ),两个相邻的H()拼接在一起作为两个相邻哈希指针节点的父节点,依次迭代,最终得到Merkle Tree的根节点。根节点也是由两个子节点的哈希值拼接在一起的, 根节点相当于包含了所有的交易信息,假设任意一笔交易信息变化,都会层层传递导致根节点的变化 。最终,对Merkle Tree的根节点取哈希值,存在区块头的Merkle Tree Hash字段中,从而保证区块头包含了所有的交易信息, 任意一笔交易信息变化层层传递导致区块头的变化,该区块头的变化又会导致区块头取哈希值的变化,块块传递导致该区块之后每一个区块发生变化 ,提高了篡改交易信息的难度。
查找一笔交易是否属于Merkle Tree,验证一笔交易属于Merkle Tree称为隶属证明,反之成为非隶属证明。
隶属证明
下图中, 假设我们需要验证一笔待证交易存在Merkle Tree中,只需要提供部分节点信息(下图中红圈部分),经过自底向上的哈希运算后,最终算出Merkle Tree hash 。我们将哈希运算结果与该区块头中的Merkle Tree hash作比较,如果相等则证明了待证交易确实存在这个Merkle Tree中。
使用Merkle Tree做交易的隶属证明,假设包含N笔交易,Merkle Tree的高度为O(log N)+1,则 验证一笔交易的时间复杂度为O(log N) 。
非隶属证明
如何证明一笔交易不属于Merkle Tree?方法是使用 排序梅克尔树(sorted Merkle Tree) ,相比于Merkle Tree, sorted Merkle Tree中最底层的交易数据是有序排列的 。先假设待证交易X在Tree中,根据有序排列的交易数据可以推算出排在待证交易之前的交易A和排在待证交易之后的交易B,如果我们使用隶属证明中的方法证明了交易A和B都隶属于sorted Merkle Tree且交易A和B是相邻紧挨着的(时间复杂度为O(log N)),那么意味着在树中A和B之间是没有空间放下待证交易X的,从而证明了待证交易X不隶属于Merkle Tree。
小结
比特币中使用哈希指针保存前一个区块头的哈希值,将多个区块连接成一条链,保证了区块链的不可篡改特性。比特币还使用梅克尔树保存区块体中的交易数据,从最底层的交易数据通过哈希指针层层传递到根哈希,浓缩了所有的交易数据,提高了篡改交易的难度。梅克尔树还提供交易数据隶属证明和非隶属证明的高效方法,时间复杂度均为O(log N)。
参考文献:
- 北京大学肖臻老师《区块链技术与应用》公开课
- 《区块链 技术驱动金融:数字货币与智能合约技术》[美] 阿尔文德·纳拉亚南(Arvind Narayanan),约什·贝努 等 著,林华,王勇,帅初 等 译
哈希指针H( )
比特币中通过哈希指针将多个区块连接成一条链。在本质上,区块链也是一个链表,只不过用哈希指针代替了普通指针。
为了说明哈希指针的优点,我们先了解一下 单向链表(singly-linked list)和普通指针 。
以C++为例,单向链表中的节点通常是结构体数据类型,包含节点的值val和指向下一个节点的指针next。
//单向链表节点 结构体,包含节点的值val和指向下一个节点的指针next struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };
Node 0又称为根节点(root node),根节点是链表的初始节点,没有指向任何节点,因此根节点的next指针为空(Node 0.next = NULL)。Node 1中的next指针存储了Node 0的地址(Node 1. next = Node 0_address),指向Node 0。同理,Node 2指向Node1, Node 3指向Node 2... 如果要往链表中加入新节点,只需要新建一个节点,并将新节点的next指针指向链表的末尾节点。链表相比于数组的优势是什么?链表的可扩展性更强,一个数组中的元素在磁盘上是先申请一块空间然后连续存储的,而链表中的节点元素可以存储在不同的磁盘位置,通过指针存储下一个节点的地址,然后去磁盘上寻址找到下一个节点。如果要修改链表中的某个节点的值,我们可以寻址找到该节点,并修改节点的值val即可。
在使用普通指针的单向链表中,我们可以随意修改任意节点的值val,而不会破坏链表的完整性。如果比特币也采用普通指针连接成一个普通链表,那我们就可以任意修改区块中的交易信息,这就破坏了区块链的不可篡改特性(严格来说,是难以篡改)。 相比于普通指针,哈希指针不仅能把区块连接成一条链,还能保证区块不可篡改。 一个区块(Block)的结构,包含区块头(Block Header)和区块体(Block Body) ,下图简单列举了Block Header和Block Body中包含的数据信息,区块结构的具体内容我将在系列博客3-比特币协议中详细讲解。
哈希指针H( )是对上一个区块的Block Header取哈希值,Block Header中的Merkle Tree哈希值已经包含了Block Body的信息,这也是为什么只需要对Block Header 取哈希的原因,减少了哈希函数的输入数据大小从而提高哈希运算的速度。Block 0又称为创世区块(genesis block),Block 1中的H()为Block 0 header的哈希值,Block 2中的H()为Block 1 header的哈希值······ 如果有新区块要加进来,只需把最末尾区块的header哈希值计算出来,放在新区块的header中即可,这样就连接成了一条区块链。
哈希指针提高了篡改的难度,防止篡改区块中的数据。假设我修改了Block 1中的数据,那么根据哈希函数的碰撞阻力特性,Block 1 header的哈希值发生变化,那么我就要修改Block 2 header中的哈希指针,Block 2 header发生变化,同理我也需要修改Block 3 header······ 相当于一个连锁反映,篡改区块链中的某个区块,就需要篡改该区块之后的所有区块,大大提高了篡改区块的难度 。
Merkle Tree(梅克尔树)
Block body中存储交易信息的数据结构就是Merkle Tree。Merkle Tree根哈希反映了所有的交易信息,修改任意一个交易数据都会造成根哈希的变化,防止篡改交易数据,并且能够快速验证某笔交易属于这个区块(隶属证明)或者不属于这个区块(非隶属证明)。
相比于普通的二叉树,Merkle Tree采用了哈希指针代替普通指针,提高了篡改交易的难度。 Merkle Tree的最底层叶子节点存的是交易信息 ,对每一笔交易取哈希值得到H( ),两个相邻的H()拼接在一起作为两个相邻哈希指针节点的父节点,依次迭代,最终得到Merkle Tree的根节点。根节点也是由两个子节点的哈希值拼接在一起的, 根节点相当于包含了所有的交易信息,假设任意一笔交易信息变化,都会层层传递导致根节点的变化 。最终,对Merkle Tree的根节点取哈希值,存在区块头的Merkle Tree Hash字段中,从而保证区块头包含了所有的交易信息, 任意一笔交易信息变化层层传递导致区块头的变化,该区块头的变化又会导致区块头取哈希值的变化,块块传递导致该区块之后每一个区块发生变化 ,提高了篡改交易信息的难度。
查找一笔交易是否属于Merkle Tree,验证一笔交易属于Merkle Tree称为隶属证明,反之成为非隶属证明。
隶属证明
下图中, 假设我们需要验证一笔待证交易存在Merkle Tree中,只需要提供部分节点信息(下图中红圈部分),经过自底向上的哈希运算后,最终算出Merkle Tree hash 。我们将哈希运算结果与该区块头中的Merkle Tree hash作比较,如果相等则证明了待证交易确实存在这个Merkle Tree中。
使用Merkle Tree做交易的隶属证明,假设包含N笔交易,Merkle Tree的高度为O(log N)+1,则 验证一笔交易的时间复杂度为O(log N) 。
非隶属证明
如何证明一笔交易不属于Merkle Tree?方法是使用 排序梅克尔树(sorted Merkle Tree) ,相比于Merkle Tree, sorted Merkle Tree中最底层的交易数据是有序排列的 。先假设待证交易X在Tree中,根据有序排列的交易数据可以推算出排在待证交易之前的交易A和排在待证交易之后的交易B,如果我们使用隶属证明中的方法证明了交易A和B都隶属于sorted Merkle Tree且交易A和B是相邻紧挨着的(时间复杂度为O(log N)),那么意味着在树中A和B之间是没有空间放下待证交易X的,从而证明了待证交易X不隶属于Merkle Tree。
小结
比特币中使用哈希指针保存前一个区块头的哈希值,将多个区块连接成一条链,保证了区块链的不可篡改特性。比特币还使用梅克尔树保存区块体中的交易数据,从最底层的交易数据通过哈希指针层层传递到根哈希,浓缩了所有的交易数据,提高了篡改交易的难度。梅克尔树还提供交易数据隶属证明和非隶属证明的高效方法,时间复杂度均为O(log N)。
参考文献:
- 北京大学肖臻老师《区块链技术与应用》公开课
- 《区块链 技术驱动金融:数字货币与智能合约技术》[美] 阿尔文德·纳拉亚南(Arvind Narayanan),约什·贝努 等 著,林华,王勇,帅初 等 译
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。
- 发表于 25分钟前
- 阅读 ( 9 )
- 学分 ( 0 )
- 分类:比特币
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- MySQL索引背后的数据结构及算法原理
- MySQL索引背后的数据结构及算法原理
- 浅谈Redis五种数据结构的底层原理
- 从 PHP 数组实现原理看线性表数据结构
- 从PHP数组实现原理看线性表数据结构
- Lucene学习笔记之-核心数据结构PriorityQueue的实现原理
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Web2.0策略指南
艾米 / 2009-3 / 39.00元
《Web2.0策略指南》是有关战略的。书中的示例关注的是Web 2.0的效率,而不是聚焦于技术。你将了解到这样一个事实:创建Web 210业务或将Web 2.0战略整合到现在业务中,意味着创建一个吸引人们前来访问的在线站点,让人们愿意到这里来共享他们的思想、见闻和行动。当人们通过Web走到一起时,结果可能远远大于各部分的和。随着传统的“口碑传诵”助推站点高速成长,客户本身就能够帮助建立站点。 ......一起来看看 《Web2.0策略指南》 这本书的介绍吧!