C01b 哈希链:改一块,后面全要重算
从普通指针链表的漏洞讲起,看哈希链怎么把引用和内容绑在一起,改中间一块为什么要一路重算到链尾。
一句话版
哈希链让每一块都装着前一块的哈希。改了中间一块,后面每一块里存的值都对不上,只能一路重算到链尾,所以篡改藏不住。
前几页讲完了哈希本身,从 C01a 到 C01a-4。从这一页起,哈希被用来组织一堆数据,这就是区块链的骨架。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 链表 | linked list | 每个节点存数据和下一个节点的位置,串成一串 |
| 指针 | pointer | 一个内存地址,告诉你下一个节点在哪 |
| 块 | block | 链上的一个单元,装着数据和对前一块的引用 |
| 哈希链 | hash chain | 每一块都装着前一块哈希的链 |
| 确认数 | confirmations | 一笔交易所在的块上面又压了几块 |
一个类比:每页开头抄上一页的指纹
一本账簿按页装订。普通装订只在页脚写「下一页见第几页」,有人换掉中间一页的内容,页码照样对得上,谁也看不出来。
换一种装订法:每页开头,先抄一遍上一页的指纹。有人改了第 2 页,第 2 页的指纹就变了,第 3 页开头抄的那枚对不上。
要瞒住,他得重抄第 3 页;第 3 页一改,第 4 页又对不上,只能一直抄到最后一页。
类比在哪里失效:
- 抄指纹只能让篡改被发现。攻击者肯把后面每一页都重抄,册子本身拦不住他。
- 真账簿重抄要花力气,哈希重算本来很快。区块链另外加了工作量证明,才让重算变贵。
从零讲起
1. 先补一块:链表与指针(补充)
它解决什么问题
哈希链是从普通链表改出来的。课件先拿链表当反例,你得先知道链表长什么样、它漏在哪。
从哪来(补充)
链表在计算机里的第一个实现,由 Allen Newell、Cliff Shaw、Herbert A. Simon 在 1955–1956 年做出,是他们 IPL 语言的主要数据结构。
直觉
链表像寻宝游戏的纸条:每张纸条写一段内容,再写「下一张在哪」。
下一张在哪,只是一个位置,和纸条上写了什么无关。有人偷偷改了纸条内容,位置没变,整条线索照样走得通。
一步一步看
目标:在普通链表里改掉一个节点的数据,看出指针只管地址,内容改了整条链照样看不出异样。
-
从 HEAD 出发,指向第一个节点。
-
每个节点存两样:数据 d 和指向下一个节点的 next。
-
四个节点 d1、d2、d3、d4 依次相连,最后一个的 next 指向 NULL,表示结束。
-
把第 2 个节点的数据从 d2 改成 d2’。
-
next 只是地址,没有变。整条链表结构完好,从 HEAD 走到 NULL 毫无异样。
怎么判断
课件这一页要你抓住一个词:independent(独立)。
意思是:指针和它指向的数据相互独立,所以数据可以被改掉,而链表结构保持完整。结构本身反映不出内容有没有被动过。
答题时说到「链表的问题」,写出「指针与数据相互独立」这层意思才算答到点上。
常见误解
以为链表的问题是指针会被改错
课件说的问题在数据这边:改数据不需要动指针,所以改了也看不出来。指针本身好好的,正是问题所在。
以为加个校验位就等于哈希链
校验位只核对一个节点自己。哈希链的关键是把前一块的哈希放进后一块,让每一块都替前一块作证。
试一下
链表里把 d3 改成 d3',需要改几个指针?
0 个。指针只是地址,数据改了地址不变。这就是课件说的「独立」。
只看这条链表的结构,能不能发现 d3 被改过?
不能。从 HEAD 走到 NULL,每一步都通,结构看不出任何异常。
2. 哈希链
它解决什么问题
链表的漏洞在于引用和内容各管各的。把指针换成前一块的哈希,引用就和内容绑在一起了。
课件的定义是:用哈希函数把一串数据块链起来,形成一条抗篡改的链。
从哪来(补充)
Leslie Lamport 在 1981 年发表论文,用哈希链在不安全的网络上做一次性密码。维基百科的条目说哈希链和区块链相像,两者都用密码学哈希把节点连起来。
直觉
指针只说「下一块在哪」。哈希说的是「前一块长什么样」。
前一块的内容一变,它的哈希就变,后一块里存的那个值当场对不上。
一步一步看
目标:把链表的指针换成前一块的哈希,看每块的引用怎样和前一块的内容绑在一起。
-
B1 是第一块,只装数据 d1。
-
B2 装两样:H(B1) 和数据 d2。H(B1) 是对整块 B1 算的哈希。
-
B3 装 H(B2) 和 d3。
-
B4 装 H(B3) 和 d4。
-
对照上一个概念:链表的 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 的数据改一下,一路推到链尾,看出改中间一块就得重算它之后的所有块。
-
把 B2 的数据 d2 改成 d2’。B2 的内容变了,H(B2) 跟着变。
-
B3 里存的还是旧的 H(B2),和新算出来的对不上。只能重算并改写 B3。
-
B3 改了,H(B3) 又变。B4 里存的旧 H(B3) 也对不上,再重算 B4。
-
一路传到链尾。B2、B3、B4 全部要重写。
-
结论:改中间任何一块,就必须重算它之后的所有块。
怎么算
一条 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 要做什么」一步步推到链尾;然后做一遍完整例题;最后回查两个最容易错的地方:链表的问题在「独立」,哈希链只让篡改可被检测。
必背
- 指针链表的问题:指针和数据相互独立(independent),改了数据链表结构照样完好,结构反映不出内容被动过
- 哈希链每块装前一块的整块哈希,引用不再独立于内容
- 哈希链每块装前一块的哈希,改中间任何一块必须重算它之后的所有块
- 哈希链让修改可被检测,不会单凭自己阻止整链重算;真实区块链靠工作量证明或权益证明让重算变贵
- 块埋得越深,篡改成本越高;比特币等 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)?
解答
- 改了 d2,B2 的内容就变了,H(B2) 跟着变。
- B3 里存的 H(B2) 还是旧值,对不上,必须重算并改写 B3。
- B3 一改,H(B3) 又变,B4 里存的值对不上,必须改写 B4。
- 一路传到链尾。结论:改中间任何一块,就必须重算它之后的所有块。
- 真实区块链里每块还绑着工作量证明或权益证明,重算等于把这些工作全部重做一遍,还要追上诚实节点。所以块埋得越深,改起来越贵。
完整例题
题面(自编,依据课件 p.29–31):(1) 指针链表把第 2 个节点的数据改了,为什么看不出来?(2) 换成四块哈希链 B1–B4,攻击者想把 d2 改成 d2’ 又不被发现,他要做哪些事?(3) 这条链放进比特币,B2 上面已经压了 6 块,他还改得动吗?
约定:「被发现」指有人拿链上存的哈希逐块核对时对不上。
解法:
- (1) 链表的 next 只是地址,和数据相互独立。改数据不动地址,从 HEAD 走到 NULL 依然通,结构看不出异常。
- (2) 改 d2’ 后 H(B2) 变了,B3 存的旧 H(B2) 对不上,他得重写 B3。
- 重写 B3 后 H(B3) 变了,B4 存的值对不上,他得重写 B4。
- 一共要重写 B2、B3、B4 三块,按 n − k + 1 = 4 − 2 + 1 = 3。
- 哈希本身算得快,只看哈希链,这三块他重算得出来。所以哈希链让篡改可被检测,但单凭它挡不住整链重算。
- (3) 在比特币里,每块还要做工作量证明。他要把 B2 之后的每一块都重做一遍工作,还得追上一直往前延长链的诚实节点。
- 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) 个哈希。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。