第二课:数据结构——《区块链技术与应用》一课学习笔记

作者:记录人陆凌燕  时间:2020-02-14  分类:区块链知识教程  

  一、重要概念:哈希指针,hash pointers

  指针不仅可以用来检验指针的位置,还可以用来检验指针有无被篡改,因为我们保持了它的哈希值(可参见第一课中哈希函数的不可逆性)。

  哈希指针只能用于无环的数据结构,在有环的结构会存在问题,会出现循环依赖:因为一个区块中的指针依赖于上一个区块中的指针。

  二、结构一:区块链

  比特币中一个最基本的数据结构,就是区块链,一个个区块组成的链表。与普通链表的区别,一个是用哈希指针替代了普通的指针,block chain as a linked list using hash pointers.

  (一)区块链的结构

  第一个区块是系统中产生的第一个区块,叫创世纪块,genesis block,最后的区块是最近产生的区块,most recent block.每个区块都包含指向前一个区块的哈希指针,即区块里有个小的HASH POINT,最后一个区块也有这么一个指针,保存在系统里。

  (二)取哈希以防止数据篡改

  取哈希时是把整个区块内容合在一起取哈希,哈希指针是把前面区块的内容(包括其中的哈希指针)合在一起取哈希值,我们称之位tamper-evident log。前面区块内容一旦改变,基于其的后面一区块的哈希指针也得改变,牵一发而动全身。

  因此只要记住最后一个哈希值,就可以检测对区块中任何部位的修改。这就是区块链与普通链表的区别。

  

  (三)轻节点节点无须保存全链内容

  基于此性质,比特币中的某个节点,就不一定要保持整条区块链中的内容,比如它只用保存最近的几千个区块,以前的就不用存。如果要用以前的区块,只须向系统中的其他区块请求。

  那如何验证别人返给你的区块是否正确?那这里就可以用到哈希指针进行验证(可参见第一课中哈希函数的不可逆性)。

  三、结构二:merkle tree

  另一个数据结构是merkle tree,其与binary tree的区别在于:merkle tree用哈希指针代替了普通指针。

  根哈希值,root hash。只要记住根哈希值,就能检测对树中任何结构的修改。

  (一)merkle tree与比特币关系

  比特币中各个区块用哈希指针连在一起,每个区块中包含的交易就组成了merkle tree,每个数据块实际是一个交易,transaction.

  每个区块分两部分,块头和块身。Block header和block body。根哈希值存在header里,header里没有交易具体内容,其中只有根哈希值。而block body里有交易列表。

  (二)Merkle tree证明交易已写入区块链的方式

  Merkle tree用途,其一是提供merkle proof

  比特币中有两类节点:全节点与轻节点。轻节点里只保存block header(只有根哈希值),如何向轻节点证明,某个交易已被写入区块链里?

  全节点就需要用merkle proof,找到交易所在的位置,从交易往上一直到根节点的路径,这条路径上的节点即我们所说的merkle proof。

  全节点只需要把树上的哈希值发给轻节点,轻节点再从下往上一层一层进行验证沿途的哈希值都是正确的。但轻节点只能计算自己所在条的哈希值,旁边的哈希值没有办法验证。且基于collision resistance,哈希值是无法被模拟出来。

  Merkle proof可以证明merkle tree里包含某个交易,这也叫proof of membership,也叫proof of inculsion。

  (三)Merkle tree证明交易未写入区块链的方式

  1、整树搜索

  能否证明merkel tree里没有某笔交易?proof of non-membership,有个简单的方法,把整棵树传给轻节点,轻节点对整个树的构造进行验证,发现整棵树是对的,每个哈希值都没问题,说明树里只有这些叶节点,没有别的了。而我所找的交易不在里面,从而证明了non-membership,这个复杂度是线性的,不是对数级别的。

  

  2、对叶节点进行排序

  更高效的办法来证明不存在,如果不对叶节点的排列顺序作假设的话,就没有什么更高效的做法。因为我们所找的交易可能存在于叶节点中的任何位置。但如果对叶节点的排列顺序作要求,如按照交易的哈希值排序,这里就有好的证明方法,先就拟找交易算个哈希值,然后进行验证。这种排好序的叫做sorted merkle tree,比特币中不存在这种排序,因为比特币中不需要证明不存在。

  

版权信息
作者:记录人陆凌燕
来源:鹿鸣于野UMU

关于我们

联系我们

作者进驻

公众号

Copyright © 2013 比特巴 www.btb8.com
只为您提供客观公正有用的比特币 区块链 加密数字货币新闻、技术教程、行情分析、行业人物资讯
手机版