技术小白的区块链技术手册-BTC02-区块链的数据结构基础

在计算机编程领域,若要理解一种算法是如何工作的,那么必须从其最基础的单位开始学习,即数据结构。不同的数据结构所具有的不同特性,能够发展出不同的算法。对于纯纯的小白来说,算法可以被理解为一种

在计算机编程领域,若要理解一种算法是如何工作的,那么必须从其最基础的单位开始学习,即数据结构。不同的数据结构所具有的不同特性,能够发展出不同的算法。对于纯纯的小白来说,算法可以被理解为一种解决问题的办法,而数据结构则是该办法所用到的工具。比如说锤子是用来敲的,斧子是用来砍的。工具和方法之间相辅相成。

比特币的数据结构

哈希指针

理解哈希指针,首先需要理解什么是指针。

  • 指针

    可以将指针形象的理解为一个有两个格子的麻袋,其中一个格子装的是某些值,比如说可以是一个数值,也可以是一串字符;而另一个格子装的则是内存中的某个位置的地址,如下图所示。这个被指向的位置存储着其他的东西,一般是另一个指针。

  • 哈希指针

    哈希指针是在指针的基础上,不仅储存了下一个位置的地址,同时还储存了下一个位置的哈希值,这就使得我们可以通过指向某个“麻袋”的哈希指针来验证这个麻袋里的内容是否有被篡改。

  • 链表

    多个指针连在一起就是链表。

区块链

区块链是一个个区块组成的链表。区块链和普通的指针链表的一个区别就是用哈希指针代替了普通指针,如图所示:

这种数据结构的好处就是,只要有人篡改了某一个位置的数据,那么整个区块链都需要更改(因为保存的哈希值对不上了),是真正的牵一发而动全身。因此只要知道其中一个头,就能验证整条链是否有被篡改。比如说我只保存最近产生的区块(图里最右边的),可以问其他人要保存在他们那里的哈希值,就可以验证我保存的区块对不对。

Merkle Tree

理解Merkle Tree,需要先理解Binary Tree(二叉树)

  • 二叉树

    二叉树是一种特殊的链表。和一般链表内的指针不同,二叉树里的每一个节点是存储着两个位置地址的指针。也就是说一个节点有两个指针指着两个地址,如下图所示

  •  

  • 这种数据结构的优点是可以对所存储的数据进行快速的查找,因此许多数据库的底层都是用二叉树实现的。

Merkle Tree和二叉树的区别便是用哈希指针代替了普通指针,每个节点除了储存下两个节点的位置同时还储存了其哈希值。

这种数据结构的好处是,只要我拥有根哈希值(Top Hash),由于哈希指针对篡改的检测和二叉树可以快速查找的特性,便能很快的检测出树中任何位置发生了修改。

比特币中的区块是通过哈希指针链接在一起的,而区块当中发生的交易则是以Merkle Tree的形式组织在一起的(图里最底层的数据块就代表区块内的交易内容)

简单来说,当一笔比特币从别人账户转到我的账户里时,我可以要求对方发给我一个哈希值,这个哈希值是这个交易的哈希值。此时我可以通过这个哈希值,在交易发生的Merkle Tree里一路向上验证,看最后的根哈希值是否对得上,对得上的话说明对方没有骗我,确实产生了这笔交易。这个验证的过程叫做Merkle Proof

技术小白的区块链技术手册-BTC02-区块链的数据结构基础

收藏我們

搜索