C01b-2 Merkle 树:几个哈希证明一条数据在里面
先补一块对数,再一步步搭出八叶子 Merkle 树,最后看证明 Data I 在树里为什么只要三个兄弟哈希。
一句话版
Merkle 树把数据两两哈希、一层层往上合并,顶上只剩一个根。要证明某条数据在里面,只需给出沿路每一层的兄弟哈希,数量是 log₂(n)。
上一页 C01b 的哈希链管块与块之间的顺序。这一页的 Merkle 树管一块之内的很多条数据。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| Merkle 树 | Merkle tree,读「默克尔树」 | 用哈希把节点连起来的二叉树 |
| 叶子节点 | leaf | 最底层,存一条数据的哈希 |
| 内部节点 | inner node / inode | 存两个孩子哈希拼起来再哈希的结果 |
| 根 RT | root | 最顶上那一个哈希,代表整棵树 |
| 兄弟节点 | sibling | 和你挂在同一个父节点下的另一个节点 |
| + 或 ‖ | 读「拼接」 | 把两段字节首尾接起来,不是算术加法 |
| log₂(n) | 读「以 2 为底 n 的对数」 | n 要对半分几次才剩 1 |
一个类比:淘汰赛对阵表
八支队伍打淘汰赛。第一轮两两对阵剩四支,第二轮剩两支,决赛剩一支冠军。对阵表画出来就是一棵倒过来的树。
想证明某支队伍参加过这次比赛,不用把八支队伍的名单全交出去。只要说出它每一轮的对手,一路推到决赛,对上公认的冠军就行。
八支队伍打三轮,对手只有三个。
类比在哪里失效:
- 比赛靠输赢往上走,Merkle 树靠把两个孩子拼起来哈希往上走,两边都要用上。
- 冠军是某一支队伍,根 RT 是全部数据合在一起的指纹,任何一条数据变了根就变。
从零讲起
1. 先补一块:对数 log₂(补充)
它解决什么问题
Merkle 证明的长度是 log₂(n)。这一节先把这个记号讲清楚,后面算证明大小时直接用。
直觉
log₂(n) 问的是:n 个东西对半分,分几次才剩 1 个。
也可以反过来想:2 乘自己几次能得到 n。
一步一步看
目标:把 2、4、8 个东西反复对半分,看出 log₂(n) 就是分几次到 1,数量翻一倍它只加 1。
- 2 个对半分 1 次剩 1 个,所以 log₂(2) = 1。
- 4 个分 2 次:4 → 2 → 1,所以 log₂(4) = 2。
- 8 个分 3 次:8 → 4 → 2 → 1,所以 log₂(8) = 3。
- 数量每翻一倍,对数只加 1。
| n | 对半分的过程 | log₂(n) |
|---|---|---|
| 2 | 2 → 1 | 1 |
| 4 | 4 → 2 → 1 | 2 |
| 8 | 8 → 4 → 2 → 1 | 3 |
| 16 | 16 → 8 → 4 → 2 → 1 | 4 |
怎么算
log₂(n) = k,等价于 2ᵏ = n。
意思是:知道叶子数 n,求树有几层,就是问 2 的几次方等于 n。八叶子满树,2³ = 8,所以有 3 层合并。
常见误解
以为 log₂(n) 和 n/2 差不多
差远了。n/2 随 n 线性增长,log₂(n) 每翻一倍才加 1。n 越大,两者差得越多。
以为 O(log n) 里的 log 一定是以 2 为底
大 O 记号里底数不重要,换底只差一个常数倍。但算 Merkle 二叉树的证明个数时,要用以 2 为底。
试一下
log₂(32) 是多少?
2⁵ = 32,所以是 5。
叶子数从 8 增加到 64,log₂ 增加了多少?
log₂(8) = 3,log₂(64) = 6,增加了 3。叶子数翻了 8 倍,对数只多 3。
2. 建一棵 Merkle 树
它解决什么问题
一个区块里有很多笔交易。要给它们一个总指纹,又要方便以后单独证明某一笔在里面,就把它们搭成一棵哈希树。
从哪来(补充)
Merkle 树以 Ralph Merkle 命名,他在 1979 年为它申请了专利。比特币、以太坊、BitTorrent、Git 都用到了哈希树。
直觉
规则只有一条,反复用:两个孩子的哈希拼起来,再哈希一次,就是父节点。
最底层的叶子是对数据本身取哈希。往上的每一层都不碰原始数据,只对下层的哈希再哈希。
一步一步看
目标:把八条数据逐层两两拼接再哈希,看一棵 Merkle 树怎样从叶子一路收成一个根。
-
八条数据 A B C D E F G I。刻意跳过 H,免得和哈希函数 H() 混。
-
每条数据各算一个哈希,得到 8 个叶子:h_A = H(A),……,h_I = H(I)。
-
相邻两个叶子拼起来再哈希,得到 4 个节点:h_AB = H(h_A + h_B),h_CD,h_EF,h_GI。
-
再两两拼接哈希,得到 2 个节点:h_ABCD = H(h_AB + h_CD),h_EFGI = H(h_EF + h_GI)。
-
最后拼成一个根:RT = H(h_ABCD + h_EFGI)。
怎么算
三条规则:
叶子 = H(数据),内部节点 = H(左标签 + 右标签),根 = RT
意思是:最底下对数据取哈希;往上每个节点都是把左右两个孩子的哈希按顺序拼起来再哈希;一直合并到只剩一个,就是根。
这里的 + 是字节拼接。左右顺序是结构的一部分,H(h_A + h_B) 和 H(h_B + h_A) 一般是两个不同的值。
常见误解
以为数据里漏了一个 H
课件刻意跳过 H。H() 已经是哈希函数的符号,再来一个 Data H,就会写出 h_H = H(H) 这种没法读的式子。
以为内部节点也要拿原始数据来算
内部节点只对下层两个哈希拼接后再哈希,不接触原始数据。这个「哈希的哈希」的递归就是 Merkle 树的全部。
试一下
把 Data E 改了一个字节,哪些节点会变?
h_E、h_EF、h_EFGI、RT 都变,正好是从 E 往上到根的那条路径。其余节点不变。
一棵四叶子树 W X Y Z,写出根的式子。
RT = H(H(h_W + h_X) + H(h_Y + h_Z)),其中 h_W = H(W),以此类推。
3. Merkle 证明
它解决什么问题
课件问:给定根 RT,怎么证明某条数据在树的叶子里?
还有一个反问:要是不建树,直接把所有数据拼起来哈希一次,会怎样?那样要证明一条数据在里面,就得把全部数据交出去。
直觉
课件的提示是:知道一个节点的两个孩子,就能算出这个节点。
验证方手上有自己那条数据,就能算出它的叶子。每往上一层,缺的只是旁边那个兄弟。证明方把每层的兄弟给他,他就能一路算到根。
课件的说法是只展开一部分哈希(some but not all)。
一步一步看
目标:拿三个兄弟哈希从 Data I 一路算回根,看证明一条数据在树里为什么只要 log₂(n) 个哈希。
要证 Data I 在树里,证明方给出三个兄弟哈希 {h_G, h_EF, h_ABCD}。验证方这样算:
-
手上有 Data I,自己算 h_I = H(I)。
-
h_GI = H(h_G + h_I)。G 在左,I 在右,顺序不能颠倒。
-
h_EFGI = H(h_EF + h_GI)。
-
RT’ = H(h_ABCD + h_EFGI),和已知的 RT 比。
-
相等,就证明 Data I 在树里。
-
数据翻一倍,证明只多一个哈希。
怎么判断
判断「证明里该给哪几个哈希」,从目标叶子往根走,每一层记下旁边那个兄弟。
意思是:证明里给的永远是兄弟节点的哈希,自己那条路径上的值由验证方自己算。正因为要自己算,篡改才无处藏。
| 直接把所有数据一起哈希 | Merkle 树 | |
|---|---|---|
| 证明一条数据在里面要给什么 | 全部 n 条数据 | log₂(n) 个哈希 |
| 8 条数据时 | 8 条全给 | 3 个哈希 |
| 验证方要不要拿到无关数据 | 要 | 不要 |
| 证明大小 | O(n) | O(log n) |
这对去中心化系统很关键。轻节点不用下载整条链,拿着区块头里的根就能验证一笔交易确实在某个块里。
常见误解
以为证明里要给自己那条路径上的 h_GI、h_EFGI
那几个由验证方自己算。证明方只给兄弟:h_G、h_EF、h_ABCD。要是路径上的值也由证明方给,验证方就没法确认它们真从 Data I 算出来。
以为拼接顺序无所谓
- 是字节拼接,H(h_G + h_I) 和 H(h_I + h_G) 一般不同。证明里要带上每个兄弟在左还是在右。
试一下
同一棵树要证 Data A,给哪三个哈希?
{h_B, h_CD, h_EFGI}。A 的兄弟是 B,h_AB 的兄弟是 h_CD,h_ABCD 的兄弟是 h_EFGI。
一棵 1024 个叶子的满树,证明要几个哈希?
2¹⁰ = 1024,所以要 10 个。
把它们串起来
log₂(n) 是对半分的次数,数量翻一倍它只加 1。Merkle 树就是把数据对半往上合并:叶子对数据取哈希,每个父节点把两个孩子的哈希拼起来再哈希,最后剩一个根 RT。
证明某条数据在里面,验证方从自己的数据算起,每层缺一个兄弟,证明方就给一个兄弟。八条数据三层,所以三个哈希,正好是 log₂(8)。
直接把所有数据一起哈希,证明一条就要交出全部。Merkle 树把这个代价从 O(n) 压到 O(log n)。哈希的应用到这里讲完,来源真实性那个洞还空着,下一页 C01b-3 用数字签名补上。
课件里的坑
- [记号提醒] p.33 的 h_GI 印成
H(h_G h_I),中间漏了+,同图另外七个内部节点全都写了,按体例应为 H(h_G + h_I)(p.33) - [题设区别] p.35 的文字问「怎么证明 Data G 在树里」,p.36 的图演示的却是 Data I,两页选的目标数据不一致,两个方向都要会算(p.35、p.36)
- [刻意跳字母] p.33 的数据是 A 到 G 再接 I,跳过 H 是刻意避开哈希函数的符号,不是漏印(p.33)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 Merkle 树的三条构造规则;再画出八叶子树,分别写出证 Data I 和证 Data G 要给的三个哈希;然后做一遍完整例题;最后回查两个最容易错的地方:给的是兄弟不是路径,拼接顺序不能换。
必背
- Merkle 树的构造规则:叶子 = H(数据),内部节点 = H(左标签 + 右标签),根 = RT
- 内部节点不接触原始数据,只对下层的哈希再哈希
- Merkle 证明给的是路径上每层的兄弟节点哈希,满树共 log₂(n) 个,8 叶子树是 3 个;拼接顺序不可交换
- 验证方从目标数据自底向上重算到根,再和可信的 RT 比对
- 相比把所有数据一起哈希,Merkle 树把证明大小从 O(n) 降到 O(log n)
- 证 Data I 给 {h_G, h_EF, h_ABCD},证 Data G 给 {h_I, h_EF, h_ABCD}
课件例题
例 1(课件 p.34):把所有数据直接拼起来哈希一次,不行吗
题面:课件在引出 Merkle 证明时反问:如果不建树,直接把所有数据拼在一起算一个哈希,会怎样?以 8 条数据为例。
提示
只有一个总哈希时,验证方要重算它,手上得有什么?
解答
- 只有一个总哈希时,要证明某条数据在里面,得把全部 8 条数据交给验证方,让他自己重算。
- 验证方被迫拿到无关数据,带宽和隐私两头吃亏。
- Merkle 树只需展开一部分哈希:8 条数据时给 3 个兄弟哈希就够,一般是 log₂(n) 个。
- 所以证明大小从 O(n) 降到 O(log n)。轻节点不用下载整条链,拿区块头里的根就能验证一笔交易在不在块里。
例 2(课件 p.35–36):给定根 RT,证明某条数据在 Merkle 树的叶子里
见下方完整例题。
完整例题
题面(课件 p.33 的八叶子树,数据依次为 A B C D E F G I):给定根哈希 RT,要向一个只知道 RT 的人证明 Data I 确实在这棵树的叶子里,需要给他哪几个哈希?他怎么验?再按 p.35 文字问的那版,证明 Data G。
约定:+ 表示字节拼接,左右顺序按树里的位置。
解法:
- 先定位 I:I 是最右边的叶子,兄弟是 G,父节点是 h_GI。h_GI 的兄弟是 h_EF,父节点是 h_EFGI。h_EFGI 的兄弟是 h_ABCD,父节点就是根。
- 证明要给三层的兄弟:{h_G, h_EF, h_ABCD},共 3 个,等于 log₂(8) = 3。
- 验证方第一步算 h_I = H(I)。
- 第二步 h_GI = H(h_G + h_I),G 在左、I 在右。
- 第三步 h_EFGI = H(h_EF + h_GI)。
- 第四步 RT’ = H(h_ABCD + h_EFGI)。
- 比对 RT’ 是否等于 RT,相等则 Data I 在树中。
- 证 Data G:给的是 {h_I, h_EF, h_ABCD}。步骤一样,只是第二步里 h_G 由自己算,h_I 由证明提供,算式仍是 H(h_G + h_I)。
- 对照直接把所有数据一起哈希:证明一条要交出 8 条,Merkle 树只要 3 个哈希。
要点:两版只差最底下那一层给谁;左右顺序跟着树的位置走,不跟着谁是目标走。
答题格式:先写证明集合,再按层写四步算式,最后一句「与 RT 比对,相等则成立」。
变式题(先自己做)
(1) 同一棵八叶子树,列出证明 Data C 在树里所需的兄弟哈希,并写出验证顺序。 (2) 一棵 16 个叶子的满树,证明要几个哈希? (3) 验证方算出的 RT’ 和 RT 不相等,能不能断定 Data C 不在树里?
提示
(1) 沿 C 往根走,每层记下兄弟,注意自己算出的那半边在左还是在右。(2) 2 的几次方是 16?(3) 不相等还可能是哪一步出了错?
判分点与答案(非官方评分标准)
判分点:① 第 (1) 问给出 {h_D, h_AB, h_EFGI} 且四步顺序正确;② 第 (2) 问答 4;③ 第 (3) 问指出不能直接断定。
(1) 证明 = {h_D, h_AB, h_EFGI},3 个。验证方:
- 算 h_C = H(C);
- h_CD = H(h_C + h_D),C 在左、D 在右;
- h_ABCD = H(h_AB + h_CD),这次自己算出来的那半边在右;
- RT’ = H(h_ABCD + h_EFGI),与 RT 比对。
(2) log₂(16) = 4,要 4 个哈希。每翻一倍叶子只多一个。
(3) 不能直接断定。也可能是证明方给错了兄弟哈希,或者拼接时左右顺序弄反了。验证失败只说明这份证明不成立。
闪卡自测
1. Merkle 树的叶子和内部节点分别存什么?
叶子存 H(数据);内部节点存 H(左孩子的标签 + 右孩子的标签),不接触原始数据;顶端是根 RT(p.32、p.33)。
2. 课件的八叶子树为什么没有 Data H?
刻意跳过,免得和哈希函数 H() 混,写出 h_H = H(H) 这种式子(p.33)。
3. 为什么不直接把所有数据一起哈希,非要建 Merkle 树?
一起哈希时,证明一条要把全部数据交出去,证明大小 O(n)。Merkle 树只要 log₂(n) 个兄弟哈希,证明大小 O(log n)(p.34)。
4. 证明 Data I 在八叶子树里,要给哪三个哈希?
{h_G, h_EF, h_ABCD}(p.36)。
5. 同一棵树改成证明 Data G,要给哪三个哈希?
{h_I, h_EF, h_ABCD}。和证 Data I 只差最底下一层:这次 h_I 由证明提供,h_G 由验证方自己算(p.35)。
6. Merkle 证明里的 + 是什么意思?左右能换吗?
字节拼接,不是算术加法。左右顺序是证明的一部分,换了一般会得到不同的根(p.33、p.36 补充)。
下一讲
C01b-3 数字签名:私钥签,公钥验:补上哈希证明不了的来源,看签名怎么做、为什么先哈希再签、签名为什么不保密。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。