哈希指针及数据结构——《区块链 技术驱动金融》笔记2

备注：本文所有图片来自Coursera课程《Bitcoin and Cryptocurrency Technologies》截屏。

1

在完成1.1小节的学习后，我觉得《区块链 技术驱动金融》这本书很难，因为我反复看反复查资料才终于弄懂了七七八八，并且还是书和网上课程结合着看的。

然后接下来的两个小节，1.2哈希指针与数据结构，以及1.3数字签名，我都是先看的书。书看完一遍勾出来几个问题，再看一遍英文版的Coursera课程《Bitcoin and Cryptocurrency Technologies》，再查了下资料。突然发现自己差不多都明白了。第一反应是：难道第一小节那么难懂，主要作用就是为了让大家打退堂鼓么？

好吧，如果是这样的话，感谢自己立的flag，以及感谢大家的存在，让我没好意思在觉得很难的时候立马就退缩。

跟第一小节相比，后面的几个小节简直就像天使一般可爱。

不过就算是天使，想要说到让人明白也不是那么容易的事情。最先设立这个公众号的时候，我以为能够维持一个高大上的专业形象，还特地在Ivy同学的建议（感谢Ivy同学的建议，让我反省了下自己的审美）下把头像改成了比较官方的样式。然而从我第一天开始自己写文章而不是翻译文章起，感觉自己就往往相反的方向越走越远——漂亮的头像也实在掩饰不住骨子里的逗逼与苦逼。

2

本周先来说说1.2哈希指针及数据结构。

哈希指针是一种数据结构，确切地说，是一个指向数据存储位置的指针，同时也是位置数据的哈希值。

跟普通的指针相比，哈希指针不但可以告诉你存储的位置，并且还可以验证数据没有被篡改过。通常我们用下图来表示哈希指针。

书中提到了两种带哈希指针的数据结构，一种是区块链，另一种是梅克尔树。

我们通过哈希指针建一个链表，这个数据结构就称为区块链。普通链表中有一系列区块，每个区块既有数据也有一个指向上一个区块的指针。而在区块链中，指向上一个区块的指针是哈希指针。所以，每个区块不仅能告诉我们上一个区块的值在哪里，还包含了其哈希值。我们可以用下图的样式表示哈希指针。

我们都知道区块链的一个应用就是“防篡改”，我们可以来看下，如果在区块链中篡改数据会发生什么样的后果。

假设有人改变了上图最左侧区块的数据，那么后面一个区块上方的哈希值就会不匹配。如果对方继续尝试，并篡改下一个区块的哈希值（上图中间）来掩盖这次篡改，那么再后面一个区块的哈希值（上图右侧）就会不匹配。对方可以一直篡改下去，直到到达链表最末端的H( )。只要最后的这个H( )存储在对方无法改动的地方，那么对方就无法在不被检测到的情况下篡改任何区块。

因此只要记住了最末端的哈希值，整个链表就是防篡改的。

另一个带哈希指针的有用的数据结构是二叉树，也称为梅克尔树(Merkle trees），以其发明者的名字命名。

如下图所示，最下方的数据区块为树的叶子，我们将区块两两分组，然后为每一组建立一个有两个哈希指针的数据结构，每个指针指向一个区块。这些指针区块就构成了树的下一层次，同样再将这些区块两两分组并建立指针，直到最后得到一个树根节点（下图最上方）。

看到上面结构的时候，我们很容易理解这个结构的防篡改特性，同区块链的结构一样，除非对方能够更改最上方根节点上的哈希值，否则，任何一个区块上的数据改动，都会导致和上一层的哈希指针不匹配，而被发现。

除了上面这点外，梅克尔树还有另外两个优点：

一是它可以实现简洁的隶属证明。假设某人想要证明某个区块属于梅克尔树，他只需要展示从这个区块通往根节点的路径上的区块，而忽略树的其它部分。也就是说，假设整棵树上有n个节点，只需要展示log(n)个项目便可以证明隶属关系——这代表验证所花的时间较短。

二是，如果我们将梅克尔树的底层的数据排序（按字母表、词典排序、数字化排序或其它约定的方式），我们就可以在log(n)复杂度的条件下验证某个数据区块不属于某梅克尔树。方法是通过展示被验证区块之前的区块路径，以及被验证区块之后的区块路径。如果之前、之后两个区块在树上是连续的，就说明了被验证区块并不属于该梅克尔树。

3

这一节的困惑：

1.这一节最大的疑问是，在区块链的部分看到“表头”及“头部数据”（这个并非翻译的问题，中文英文都是一样的意思）的时候，直觉的反应是这应该在区块链的最前端或者说应该是它的第一个数据，但事实上“头部数据”代表的却是区块链最末端的哈希指针——在看到梅克尔树中的描述时通常就明白了。而在1.3节中说到数字签名时，这点就更明白了。

2.这一节的另外一个疑惑是log(n)。我知道lg(n)代表底数是10，ln(n)代表底数是e，然后log(n)是什么东东？查了下，才知道log(n)没写底数，底数可以是10，可以是e，也可以是底数不重要时的任何底数——看具体用在什么情况下，但在计算机上一般代表底数是2。数学本来就不好的人深深体会到了与时俱进的压力。