代码编织梦想

普通指针与哈希指针

普通指针存储的是某个结构体在内存中的地址。假如P是指向一结构体的指针,那么P里面存放的就是该结构体在内存中的起始位置。

哈希指针除了要存地址之外,还要保存该结构体的哈希值H()。好处是:存了哈希值和地址的哈希指针,不仅可以找到该结构体的位置,同时还能够检测出该结构体的内容有没有被篡改,因为我们保存了它的哈希值。

普通链表和区块链

比特币中最基本的数据结构就是区块链,区块链就是一个一个区块组成的链表。他和普通链表有着如下的区别:

1.用哈希指针代替了普通指针(B block chain is a linked list using hash pointers)区块链第一个区块叫作创世纪块(genesis block) 最后一个区块叫最近产生的区块(most recent block) 。每一个区块都包含指向前一个区块的哈希指针,最后一个区块也有一个哈希指针保存在系统里。

这样做的好处是通过这种结构,可以实现tamper-evident log。如果有人改变了一个区块的内容,后面一个区块的哈希指针就对不上,因为后一个区块哈希指针是根据前一个区块的内容算出来的,所以后一个哈希指针也得改,以此类推,我们保留的是最后一个哈希值也会变化。

因此我们甚至只要记住最后一个哈希值,就可以检测出对去区块链中任何一个部位的是否有修改。 

2.由此引出第二个区别,普通链表可以改变任意一个元素,对链表中其他元素是没有影响的。而区块链是牵一发而动全身,因为只需要保存最后一个哈希值,就可以判断区块链有没有改变,在哪里改变了。

因此比特币没有要保存所有区块的内容,可以只保留最近的几千个区块。如果要用到以前的区块,可以向系统中其他节点要这个区块。

有些节点是有恶意的,怎么判断?这里要用到哈希值一个性质,其他节点给你一个区块,如何判断它是正确的?算出它的哈希值,与相邻保存上一个节点的区块的哈希值对比,看他们是否相同即可。

二叉树和默克尔树(哈希树)

Merkle Tree 是什么?

答:比特币中的另外一个结构是:Merkle Tree。其中最下面一层是数据块(data blocks),上面几层的内部节点都是哈希指针(hash pointers),第一层是根节点,根节点的区块也可以取个哈希,叫根哈希(root hash)

这种结构的好处:只要记住根哈希值,就能检测出对树中任何部位的修改。

比特币当中各区块之间用哈希指针连接在一起,每个区块所包含的交易组织成一个merkle tree的形式,最下面一行data blocks每个区块实际上是一个交易。

每个区块分为两部分,分别是块头和块身(block header ,block body)。

块头里面有根哈希值,每个区块所包含的所有交易组成的merkle tree的根哈希值存在于区块的块头里面,但是,块头里没有交易的具体内容,只有一个根哈希值。

块身里面是有交易的列表的。 

Merkle Tree 的主要作用

提供merkle proof

比特币中的节点分为两类:

全节点:保存整个区块的内容,即block header ,block body都有。

轻节点:例如手机上的比特币钱包,只有block header。

这时存在一个问题:如何向一个轻节点证明某个交易是写入区块链的?

答:这时需要用到merkle proof :找到交易所在的位置(最底行的其中一个区块),这时该区块一直往上到根节点的路径就叫merkle proof。

假设某个轻节点想知道图中黄色的交易,是否包含在了merkle tree里面(轻节点没有包含交易列表,没有这颗merkle tree的具体内容,只有一个根哈希值)。这时轻节点向一个全节点发出请求,请求证明黄色的交易被包含在这颗merkle tree里面的merkle proof。全节点收到这个请求之后,只需要将图中标为红色的这三个哈希值发给轻节点即可。有了这些哈希值之后,轻节点可以在本地计算出图中标为绿色三个哈希值。首先算出黄色交易的哈希值,即它正上方的那个绿的哈希值,然后跟旁边红色的哈希值拼接起来,可以算出上层节点绿色的哈希值。然后再拼接,再算出上层绿色哈希值,再拼接,就可以算出整棵树的根哈希值。轻节点把这个根哈希值和block header里的根哈希值比较一下是否相等,就能知道黄色的交易是否在这颗merkle tree里。

由于merkle proof可以证明merkle tree里面包含了某个交易,所以这种证明又叫proof of membership或者 proof of inclusion。

对于一个轻节点来说,验证一个merkle proof 复杂度是多少?

答:假设最底层有n个交易,则merkle proof 复杂程度是θ(log(n))。

如何证明merkle tree里面没有包含某个交易(proof of non-membership)?

答:可以把整棵树传给轻节点,轻节点收到后验证树的构造都是对的,每一层用到的哈希值都是正确的,说明树里只有这些叶节点,要找的交易不在里面,就证明了proof of non-membership。问题在于,它的复杂度是线性的θ(n),是比较笨的方法。

查找效率高一点的办法是如果对叶节点的排列顺序做一些要求,比如按照交易的哈希值排序。每一个叶节点都是一次交易,对交易的内容取一次哈希,按照哈希值从小到大排列。要查的交易先算出一个哈希值,看看如果它在里面该是哪个位置。比如说在第三个第四个之间,这时提供的proof是第三个第四个叶节点都要往上到根节点。如果其中哈希值都是正确的,最后根节点算出的哈希值也是没有被改过的,说明第三、四个节点在原来的merkle tree里面,确实是相邻的点。要找的交易如果存在的话,应该在这两个节点中间。但是它没有出现,所以就不存在。其复杂度也是log形式,代价是要排序。排好序的叫作sorted merkle tree。比特币中没有用到这种排好序的merkle tree,因为比特币中不需要做不存在证明。

总结

这节讲了比特币中两种最基本的结构:区块链和merkle tree,都是用哈希指针来构造的。除了这两种之外,哈希指针还能用另一个方面。只要一个数据结构是无环的(非循环链表),都能用哈希指针代替普通指针。有环的话存在一个问题,他们的哈希值没法计算,没法确定一个哈希值固定的区块,会出现循环依赖。

参考资料

1.北京大学肖臻老师《区块链技术与应用》公开课

2.某位同学的区块链笔记

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/LDDlove_java/article/details/127151058

最全 比特币区块链结构+代码_区小升的博客-爱代码爱编程_比特币区块链代码

1. 区块链书籍和有用链接 首先,本人也是一周后在学习区块链的路上,学习中将自己看过的有用的信息就放在自己的GitHub上,方便自己复习好找 本人首页:www.github.com/cancerts/study-blockchain-referrence 【点击】 里面有我25本(写博客时)区块链领域比较热门的书籍,有PDF、mobi三种格式的,懂区块链

05.比特币区块链的数据结构-爱代码爱编程

我们回到两个人转账交易的过程中,去理解比特币区块链的数据结构。 我发起一笔交易,即我向整个区块链网络广播,我和你两个人想进行这笔交易:我向你的地址中转入一笔比特币,无须你的许可。 但只有当这笔交易被打包进最新的比特币区块中时,这笔交易才真正完成。通常来说,当在一笔交易所在的区块之后又增加 5 个区块,即包括它自己在内一共经过 6 次确认时,这笔交易可认

比特币中重要的数据结构-爱代码爱编程

文章目录 一、哈希指针(hash pointer)二、区块链(Blockchain)三、默克尔树(Merkle tree) 一、哈希指针(hash pointer) 我们通常所说的指针中保存的是对应数据的内存地址,哈希指针套用了这个概念,保存对应数据的哈希值就形成了哈希指针。如下图所示: 二、区块链(Blockchain) Block c

比特币系统数据结构 Merkle tree-爱代码爱编程

疫情期间,看了区块链相关,北京大学 肖臻研究员 的《区块链技术与应用》课程,课程传送门,方便复习做下笔记啦 什么是Merkle tree 哈希树(hash tree;Merkle tree),在密码学及计算机科学中是一种树形数据结构,每个叶节点均以数据块的哈希作为标签,而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效

[学习笔记] 比特币交易的数据结构-爱代码爱编程

https://aaron67.cc/2018/12/27/bitcoin-transaction-data-structure/ 比特币的交易,由一个或多个输出和一个或多个输入(Coinbase 交易是一种特殊情况)构成。 交易的每个输出上,都会附上一个加密难题,定义将来在花费这笔 UTXO 时需要满足的条件。 交易的每个输入上,都要提供

区块链:2、比特币 核心数据结构-爱代码爱编程

区块链:2、比特币 核心数据结构 区块、地址和交易是比特币的三种基本数据结构。 之所以需要这些特定的数据结构,是因为比特币被设计成一种分布式数字货币。 所有基于比特币的加密货币,无论是它的直系货币(例如 Namecoin、Litecoin、Zcash)还是仅仅以它为基础的货币(例如 Ethereum),都是有一些小修改的核心数据结构的变体。 一、区块

比特币的密码学原理和数据结构-爱代码爱编程

比特币 一、比特币         比特币:一种点对点的电子现金系统,一个完全的点对点版本的电子现金将允许一方不通过金融机构直接在线支付给另一方。 二、比特币的密码学原理 1、哈希算法         哈希算法就是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,

区块链】2:比特币中的数据结构_qq_40270404的博客-爱代码爱编程

来自:【区块链学习笔记】2:比特币中的数据结构_LauZyHou的博客-CSDN博客 1. 哈希指针:普通的指针存储的是某个数据在内存中的首地址。哈希指针不仅要保存地址,还要保存数据的哈希值。通过哈希指针不仅能找到数据的位置,还能检测出数据有没有被篡改(因为保存了哈希值)。 2. 区块链和普通链表的区别 普通链表:数据域储存数据,指针域储存链表指向的

比特币区块结构_ucasers的博客-爱代码爱编程

摘要:本文主要介绍比特币区块的相关概念 文章目录 前言哈希指针区块链Merkle tree防篡改验证身份比特币区块链比特币区块获取区块数据coinbase交易总结参考文献 前言 比特币账本是以区块链的形式组织起来的,每个区块以merkle tree的形式记录着多条交易的具体信息, 而区块与区块间则通过哈希指针链接起来,从而实现了对

02-btc-数据结构_preys的博客-爱代码爱编程

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 二、区块链 三、Merkel tree 总结 前言     今天看了北大肖臻老师《区块链技术与应用》公开课,有很大收获,在此写博客以做笔记,加深印象,若有不当之处,欢迎斧正。 一、比特币中的数据结构是什么?     比特币中

二、区块链技术与应用-比特币的数据结构_山姆哥up的博客-爱代码爱编程

哈希指针(hash pointer):         传统指针:传统指针存着一个内存位置的地址         而哈希指针不仅保存着位置的地址 也保存着这个内存内容的哈希值 从而检测这个内容有没有被篡改 Question: 我们都知道c++ stl中也有链表 是一个个结点链起来形成了一个链式结构 那么区块链和链表有什么区别呢? 区块链里用哈希指针