← COMP5565 全部讲次
C01b · 第 2 周

C01b 哈希链:改一块,后面全要重算

从普通指针链表的漏洞讲起,看哈希链怎么把引用和内容绑在一起,改中间一块为什么要一路重算到链尾。

一句话版

哈希链让每一块都装着前一块的哈希。改了中间一块,后面每一块里存的值都对不上,只能一路重算到链尾,所以篡改藏不住。

前几页讲完了哈希本身,从 C01a 到 C01a-4。从这一页起,哈希被用来组织一堆数据,这就是区块链的骨架。

先认识这几个词

词 全称 / 读法 一句人话
链表 linked list 每个节点存数据和下一个节点的位置,串成一串
指针 pointer 一个内存地址,告诉你下一个节点在哪
块 block 链上的一个单元,装着数据和对前一块的引用
哈希链 hash chain 每一块都装着前一块哈希的链
确认数 confirmations 一笔交易所在的块上面又压了几块

一个类比:每页开头抄上一页的指纹

一本账簿按页装订。普通装订只在页脚写「下一页见第几页」,有人换掉中间一页的内容,页码照样对得上,谁也看不出来。

换一种装订法:每页开头,先抄一遍上一页的指纹。有人改了第 2 页,第 2 页的指纹就变了,第 3 页开头抄的那枚对不上。

要瞒住,他得重抄第 3 页;第 3 页一改,第 4 页又对不上,只能一直抄到最后一页。

类比在哪里失效:

  1. 抄指纹只能让篡改被发现。攻击者肯把后面每一页都重抄,册子本身拦不住他。
  2. 真账簿重抄要花力气,哈希重算本来很快。区块链另外加了工作量证明,才让重算变贵。

从零讲起

1. 先补一块:链表与指针(补充)

它解决什么问题

哈希链是从普通链表改出来的。课件先拿链表当反例,你得先知道链表长什么样、它漏在哪。

从哪来(补充)

链表在计算机里的第一个实现,由 Allen Newell、Cliff Shaw、Herbert A. Simon 在 1955–1956 年做出,是他们 IPL 语言的主要数据结构。

出处:Wikipedia: Linked list

直觉

链表像寻宝游戏的纸条:每张纸条写一段内容,再写「下一张在哪」。

下一张在哪,只是一个位置,和纸条上写了什么无关。有人偷偷改了纸条内容,位置没变,整条线索照样走得通。

一步一步看

目标:在普通链表里改掉一个节点的数据,看出指针只管地址,内容改了整条链照样看不出异样。

  1. 从 HEAD 出发,指向第一个节点。

  2. 每个节点存两样:数据 d 和指向下一个节点的 next。

  3. 四个节点 d1、d2、d3、d4 依次相连,最后一个的 next 指向 NULL,表示结束。

  4. 把第 2 个节点的数据从 d2 改成 d2’。

  5. next 只是地址,没有变。整条链表结构完好,从 HEAD 走到 NULL 毫无异样。

    指针链表改了数据照样完好:上面是改之前,HEAD 依次指向 d1、d2、d3、d4,最后指向 NULL;下面是把第 2 个节点改成 d2’ 之后,指针一根没动,链表依旧完整;底部说明 next 只是地址,和数据各管各的,结构看不出内容被动过

怎么判断

课件这一页要你抓住一个词:independent(独立)。

意思是:指针和它指向的数据相互独立,所以数据可以被改掉,而链表结构保持完整。结构本身反映不出内容有没有被动过。

答题时说到「链表的问题」,写出「指针与数据相互独立」这层意思才算答到点上。

常见误解

以为链表的问题是指针会被改错

课件说的问题在数据这边:改数据不需要动指针,所以改了也看不出来。指针本身好好的,正是问题所在。

以为加个校验位就等于哈希链

校验位只核对一个节点自己。哈希链的关键是把前一块的哈希放进后一块,让每一块都替前一块作证。

试一下

链表里把 d3 改成 d3',需要改几个指针?

0 个。指针只是地址,数据改了地址不变。这就是课件说的「独立」。

只看这条链表的结构,能不能发现 d3 被改过?

不能。从 HEAD 走到 NULL,每一步都通,结构看不出任何异常。

2. 哈希链

它解决什么问题

链表的漏洞在于引用和内容各管各的。把指针换成前一块的哈希,引用就和内容绑在一起了。

课件的定义是:用哈希函数把一串数据块链起来,形成一条抗篡改的链。

从哪来(补充)

Leslie Lamport 在 1981 年发表论文,用哈希链在不安全的网络上做一次性密码。维基百科的条目说哈希链和区块链相像,两者都用密码学哈希把节点连起来。

出处:Wikipedia: Hash chain

直觉

指针只说「下一块在哪」。哈希说的是「前一块长什么样」。

前一块的内容一变,它的哈希就变,后一块里存的那个值当场对不上。

一步一步看

目标:把链表的指针换成前一块的哈希,看每块的引用怎样和前一块的内容绑在一起。

  1. B1 是第一块,只装数据 d1。

  2. B2 装两样:H(B1) 和数据 d2。H(B1) 是对整块 B1 算的哈希。

  3. B3 装 H(B2) 和 d3。

  4. B4 装 H(B3) 和 d4。

    四块哈希链:Block B1 装 d1;Block B2 装 H(B1) 和 d2;Block B3 装 H(B2) 和 d3;Block B4 装 H(B3) 和 d4;箭头表示下一块装着这一块的哈希

  5. 对照上一个概念:链表的 next 换成了前一块的哈希,引用不再独立于内容。

怎么判断

拿链表和哈希链对照着判:

指针链表 哈希链
后一块存什么 前一块的地址 前一块的整块哈希
引用和内容的关系 相互独立 绑在一起
改中间一块的数据 结构照样完好 后一块存的值对不上

意思是:判断一个结构抗不抗篡改,看它的引用会不会随内容一起变。

常见误解

以为 B2 里存的是 d1 的哈希

存的是整块 B1 的哈希。从 B3 起,被哈希的那一块本身就装着更前一块的哈希,于是每一块都间接依赖它之前的全部内容。

以为哈希链能防止任何人改数据

它让修改可被检测。攻击者把后面每块都重算一遍,链本身是拦不住的,下一个概念讲。

试一下

B4 存的 H(B3) 依赖哪些数据?

依赖 B3 的全部内容,即 H(B2) 和 d3;H(B2) 又依赖 d2 和 H(B1),H(B1) 依赖 d1。所以它间接依赖 d1 到 d3 全部。

链表也想抗篡改,最少要改哪一处?

把每个节点的 next 换成「前一个节点的哈希」,或者在指针之外再存一份前一个节点的哈希。这就把链表改成了哈希链。

3. 改一块的连锁后果

它解决什么问题

课件把 d2 圈出来问:想改 d2,该怎么做?这是这一节最可能考的题,要能一步步推到链尾。

直觉

改一块,像推倒第一张多米诺骨牌。它的哈希一变,后面那块就站不稳,扶起后面那块,它的哈希又变,再后面那块又倒。

一步一步看

目标:把 B2 的数据改一下,一路推到链尾,看出改中间一块就得重算它之后的所有块。

  1. 把 B2 的数据 d2 改成 d2’。B2 的内容变了,H(B2) 跟着变。

    第 1 步:把 B2 的数据 d2 改成 d2’,用青绿标出,H(B2) 跟着变

  2. B3 里存的还是旧的 H(B2),和新算出来的对不上。只能重算并改写 B3。

    第 2 步:B3 里存的是旧 H(B2),用青绿标出并打叉,对不上,只能重算 B3

  3. B3 改了,H(B3) 又变。B4 里存的旧 H(B3) 也对不上,再重算 B4。

    第 3 步:B3 换成新 H(B2) 之后,H(B3) 又变,B4 里存的旧 H(B3) 用青绿标出并打叉,再重算 B4

  4. 一路传到链尾。B2、B3、B4 全部要重写。

    第 4 步:B2 装 d2’,B3 装新 H(B2),B4 装新 H(B3),底下青绿括号标出 B2、B3、B4 全部重写

  5. 结论:改中间任何一块,就必须重算它之后的所有块。

怎么算

一条 n 块的链,改第 k 块,要重写的块数是:

重写块数 = n − k + 1

意思是:第 k 块自己加上它后面的每一块,都要重写。本题 n = 4,k = 2,要重写 3 块。

在真实区块链里,每一块还绑着工作量证明或权益证明。重算就是把这些工作全部重做一遍,还要在诚实节点继续延长链的同时追上去。

所以块埋得越深,后面压的块越多,篡改越贵。比特币要等 6 个确认,就是让交易上面再压 6 块。

常见误解

以为改了 d2,只要改 B2 和 B3 两块

B3 一改,H(B3) 也变了,B4 跟着对不上。连锁一直传到链尾,一块都跳不过。

以为哈希重算很慢,所以哈希链本身就能挡住篡改

哈希本来算得很快,重算整条链不难。让重算变贵的是区块链另外加上的工作量证明或权益证明。

试一下

一条 10 块的链,改第 7 块,要重写几块?

10 − 7 + 1 = 4 块:第 7、8、9、10 块。

改最后一块要重写几块?为什么新出的块最不安全?

只重写 1 块,就是它自己。它上面没有压别的块,篡改成本最低,所以要等确认数涨上去。

把它们串起来

普通链表的指针只记位置,和数据各管各的,改了数据看不出来。哈希链把指针换成前一块的哈希,引用和内容绑死了。

于是改中间一块会一路传到链尾:它的哈希变了,后一块存的值对不上,重写后一块又带动再后一块。哈希链本身只负责让篡改暴露,让重写变贵的是区块链额外加的工作量证明或权益证明,块埋得越深越难改。

哈希链管的是顺序。一块之内有很多笔交易,怎么高效证明某一笔在里面,要靠下一页 C01b-2 的 Merkle 树。

课件里的坑

  • [边界提醒] p.31 底部只写「Hash chain is used in Blockchain」。哈希链只让修改可被检测,不会单凭自己阻止整链重算,答题时别写成「哈希链让数据无法修改」(p.31)
  • [整块哈希] p.30 的图里 B2 存的是 H(B1),对整块 B1 取哈希,不是只对 d1 取(p.30)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写四块哈希链每块装什么,再把「改 d2 要做什么」一步步推到链尾;然后做一遍完整例题;最后回查两个最容易错的地方:链表的问题在「独立」,哈希链只让篡改可被检测。

必背

  1. 指针链表的问题:指针和数据相互独立(independent),改了数据链表结构照样完好,结构反映不出内容被动过
  2. 哈希链每块装前一块的整块哈希,引用不再独立于内容
  3. 哈希链每块装前一块的哈希,改中间任何一块必须重算它之后的所有块
  4. 哈希链让修改可被检测,不会单凭自己阻止整链重算;真实区块链靠工作量证明或权益证明让重算变贵
  5. 块埋得越深,篡改成本越高;比特币等 6 个确认就是让交易上面再压 6 块

课件例题

例 1(课件 p.31):哈希链里想改 d2,要做什么

题面:一条四块的哈希链。B1 装数据 d1;B2 装 H(B1) 和数据 d2;B3 装 H(B2) 和 d3;B4 装 H(B3) 和 d4。课件把 d2 圈出来问:想改 d2,该怎么做?

提示

改了 d2 以后,B2 的哈希变不变?B3 里存的是哪个版本的 H(B2)?

解答
  1. 改了 d2,B2 的内容就变了,H(B2) 跟着变。
  2. B3 里存的 H(B2) 还是旧值,对不上,必须重算并改写 B3。
  3. B3 一改,H(B3) 又变,B4 里存的值对不上,必须改写 B4。
  4. 一路传到链尾。结论:改中间任何一块,就必须重算它之后的所有块。
  5. 真实区块链里每块还绑着工作量证明或权益证明,重算等于把这些工作全部重做一遍,还要追上诚实节点。所以块埋得越深,改起来越贵。

完整例题

题面(自编,依据课件 p.29–31):(1) 指针链表把第 2 个节点的数据改了,为什么看不出来?(2) 换成四块哈希链 B1–B4,攻击者想把 d2 改成 d2’ 又不被发现,他要做哪些事?(3) 这条链放进比特币,B2 上面已经压了 6 块,他还改得动吗?

约定:「被发现」指有人拿链上存的哈希逐块核对时对不上。

解法:

  1. (1) 链表的 next 只是地址,和数据相互独立。改数据不动地址,从 HEAD 走到 NULL 依然通,结构看不出异常。
  2. (2) 改 d2’ 后 H(B2) 变了,B3 存的旧 H(B2) 对不上,他得重写 B3。
  3. 重写 B3 后 H(B3) 变了,B4 存的值对不上,他得重写 B4。
  4. 一共要重写 B2、B3、B4 三块,按 n − k + 1 = 4 − 2 + 1 = 3。
  5. 哈希本身算得快,只看哈希链,这三块他重算得出来。所以哈希链让篡改可被检测,但单凭它挡不住整链重算。
  6. (3) 在比特币里,每块还要做工作量证明。他要把 B2 之后的每一块都重做一遍工作,还得追上一直往前延长链的诚实节点。
  7. B2 上面压了 6 块,代价高到不划算,这就是等 6 个确认的意义。

要点:链表输在「独立」,哈希链赢在「绑定」;让篡改变贵的是共识机制,不是哈希。

答题格式:三问分开答。第 (2) 问按块逐条写「谁的哈希变了 → 谁对不上 → 重写谁」。

变式题(先自己做)

(1) 一条 8 块的哈希链,攻击者改了第 3 块。他要重写哪几块? (2) 有人说:「既然改一块要重算后面所有块,哈希链就能保证历史不被篡改。」这句话哪里不准确? (3) 一条哈希链只公开发布了最后一块的哈希,其余块存在别人的服务器上。为什么光凭这一个哈希就能发现中间被改?

提示

(1) 用 n − k + 1。(2) 哈希链本身能让篡改「被发现」,还是能让篡改「做不到」?(3) 最后一块的哈希依赖哪些块?

判分点与答案(非官方评分标准)

判分点:① 第 (1) 问列出第 3 到第 8 块共 6 块;② 第 (2) 问区分「可检测」与「阻止」;③ 第 (3) 问指出最后一块的哈希间接依赖全部块。

(1) 8 − 3 + 1 = 6 块:第 3、4、5、6、7、8 块。

(2) 哈希链只保证改了会被发现。攻击者把后面的块全部重算,链本身拦不住;真实区块链靠工作量证明或权益证明让重算昂贵,才谈得上难以篡改。

(3) 最后一块的哈希依赖它自己的内容,其中装着前一块的哈希,前一块又装着更前一块的哈希,所以它间接依赖全部块。中间任何一块被改,重算出的最后一块哈希就和公开的那个不一样。

闪卡自测

1. 普通指针链表在防篡改上有什么问题?

指针和数据相互独立(independent),改了数据链表结构照样完好,结构反映不出内容被动过(p.29)。

2. 哈希链的每一块装什么?

自己的数据,加上前一块的整块哈希。B1 只装 d1,B2 装 H(B1) 和 d2,以此类推(p.30)。

3. 哈希链里改了中间一块会怎样?

那一块的哈希变了,下一块里存的旧值对不上,必须重算改写;改了下一块它的哈希又变,一路传到链尾。改中间任何一块必须重算它之后的所有块(p.31)。

4. 哈希链能不能单凭自己阻止篡改?

不能。它让修改可被检测,攻击者把后面的块全部重算,链本身拦不住。真实区块链靠工作量证明或权益证明让重算变贵(p.31 补充)。

5. 为什么比特币要等 6 个确认?

让交易所在的块上面再压 6 块。块埋得越深,篡改要重做的工作越多,代价高到不划算(p.31 补充)。

下一讲

C01b-2 Merkle 树:几个哈希证明一条数据在里面:把数据两两哈希、一层层往上合成一棵树,再看为什么证明一条数据只要 log₂(n) 个哈希。

下一讲 →
C01b-2 C01b-2 Merkle 树:几个哈希证明一条数据在里面

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。