← COMP5565 全部讲次
C01b-2 · 第 2 周

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

一个类比:淘汰赛对阵表

八支队伍打淘汰赛。第一轮两两对阵剩四支,第二轮剩两支,决赛剩一支冠军。对阵表画出来就是一棵倒过来的树。

想证明某支队伍参加过这次比赛,不用把八支队伍的名单全交出去。只要说出它每一轮的对手,一路推到决赛,对上公认的冠军就行。

八支队伍打三轮,对手只有三个。

类比在哪里失效:

  1. 比赛靠输赢往上走,Merkle 树靠把两个孩子拼起来哈希往上走,两边都要用上。
  2. 冠军是某一支队伍,根 RT 是全部数据合在一起的指纹,任何一条数据变了根就变。

从零讲起

1. 先补一块:对数 log₂(补充)

它解决什么问题

Merkle 证明的长度是 log₂(n)。这一节先把这个记号讲清楚,后面算证明大小时直接用。

直觉

log₂(n) 问的是:n 个东西对半分,分几次才剩 1 个。

也可以反过来想:2 乘自己几次能得到 n。

一步一步看

目标:把 2、4、8 个东西反复对半分,看出 log₂(n) 就是分几次到 1,数量翻一倍它只加 1。

  1. 2 个对半分 1 次剩 1 个,所以 log₂(2) = 1。
  2. 4 个分 2 次:4 → 2 → 1,所以 log₂(4) = 2。
  3. 8 个分 3 次:8 → 4 → 2 → 1,所以 log₂(8) = 3。
  4. 数量每翻一倍,对数只加 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 都用到了哈希树。

出处:Wikipedia: Merkle tree

直觉

规则只有一条,反复用:两个孩子的哈希拼起来,再哈希一次,就是父节点。

最底层的叶子是对数据本身取哈希。往上的每一层都不碰原始数据,只对下层的哈希再哈希。

一步一步看

目标:把八条数据逐层两两拼接再哈希,看一棵 Merkle 树怎样从叶子一路收成一个根。

  1. 八条数据 A B C D E F G I。刻意跳过 H,免得和哈希函数 H() 混。

    第 0 步:八条数据 Data A 到 Data I 排成一行,刻意跳过 H,免得和哈希函数 H() 混

  2. 每条数据各算一个哈希,得到 8 个叶子:h_A = H(A),……,h_I = H(I)。

    第 1 步:每条数据各算一个哈希,得到 h_A 到 h_I 共 8 个叶子,用青绿标出

  3. 相邻两个叶子拼起来再哈希,得到 4 个节点:h_AB = H(h_A + h_B),h_CD,h_EF,h_GI。

    第 2 步:相邻两个叶子拼起来再哈希,得到 h_AB、h_CD、h_EF、h_GI 四个节点,用青绿标出

  4. 再两两拼接哈希,得到 2 个节点:h_ABCD = H(h_AB + h_CD),h_EFGI = H(h_EF + h_GI)。

    第 3 步:再两两拼接哈希,得到 h_ABCD 和 h_EFGI 两个节点,用青绿标出

  5. 最后拼成一个根:RT = H(h_ABCD + h_EFGI)。

    第 4 步:h_ABCD 和 h_EFGI 拼起来再哈希,得到顶上的根 RT,用青绿标出

怎么算

三条规则:

叶子 = 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}。验证方这样算:

  1. 手上有 Data I,自己算 h_I = H(I)。

    第 1 步:验证方手上有 Data I,自己算 h_I = H(I),用青绿标出;h_G、h_EF、h_ABCD 三个兄弟哈希用虚线框标出,是证明方给的

  2. h_GI = H(h_G + h_I)。G 在左,I 在右,顺序不能颠倒。

    第 2 步:用给的 h_G 和自己算的 h_I 拼成 h_GI = H(h_G + h_I),h_GI 用青绿标出

  3. h_EFGI = H(h_EF + h_GI)。

    第 3 步:用给的 h_EF 和刚算出的 h_GI 拼成 h_EFGI,用青绿标出

  4. RT’ = H(h_ABCD + h_EFGI),和已知的 RT 比。

    第 4 步:用给的 h_ABCD 和算出的 h_EFGI 拼成 RT’,和已知的 RT 比,相等就证明 Data I 在树里

  5. 相等,就证明 Data I 在树里。

  6. 数据翻一倍,证明只多一个哈希。

    证明一条数据在里面要交多少东西:n 等于 2、4、8、16 时,全部哈希一起要交 2、4、8、16 条数据,Merkle 只要交 1、2、3、4 个哈希;数据翻一倍,Merkle 证明只多 1 个哈希,从 O(n) 降到 O(log n)

怎么判断

判断「证明里该给哪几个哈希」,从目标叶子往根走,每一层记下旁边那个兄弟。

意思是:证明里给的永远是兄弟节点的哈希,自己那条路径上的值由验证方自己算。正因为要自己算,篡改才无处藏。

直接把所有数据一起哈希 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 要给的三个哈希;然后做一遍完整例题;最后回查两个最容易错的地方:给的是兄弟不是路径,拼接顺序不能换。

必背

  1. Merkle 树的构造规则:叶子 = H(数据),内部节点 = H(左标签 + 右标签),根 = RT
  2. 内部节点不接触原始数据,只对下层的哈希再哈希
  3. Merkle 证明给的是路径上每层的兄弟节点哈希,满树共 log₂(n) 个,8 叶子树是 3 个;拼接顺序不可交换
  4. 验证方从目标数据自底向上重算到根,再和可信的 RT 比对
  5. 相比把所有数据一起哈希,Merkle 树把证明大小从 O(n) 降到 O(log n)
  6. 证 Data I 给 {h_G, h_EF, h_ABCD},证 Data G 给 {h_I, h_EF, h_ABCD}

课件例题

例 1(课件 p.34):把所有数据直接拼起来哈希一次,不行吗

题面:课件在引出 Merkle 证明时反问:如果不建树,直接把所有数据拼在一起算一个哈希,会怎样?以 8 条数据为例。

提示

只有一个总哈希时,验证方要重算它,手上得有什么?

解答
  1. 只有一个总哈希时,要证明某条数据在里面,得把全部 8 条数据交给验证方,让他自己重算。
  2. 验证方被迫拿到无关数据,带宽和隐私两头吃亏。
  3. Merkle 树只需展开一部分哈希:8 条数据时给 3 个兄弟哈希就够,一般是 log₂(n) 个。
  4. 所以证明大小从 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。

八叶子默克尔树:底层 Data A、B、C、D、E、F、G、I 各自哈希成 hA 到 hI;上一层两两拼接得到 hAB、hCD、hEF、hGI;再上一层得到 hABCD 和 hEFGI;顶端根 RT 等于 H(hABCD + hEFGI)
图片来源:COMP5565 Lecture crypto foundation.pdf, p.33

约定:+ 表示字节拼接,左右顺序按树里的位置。

解法:

  1. 先定位 I:I 是最右边的叶子,兄弟是 G,父节点是 h_GI。h_GI 的兄弟是 h_EF,父节点是 h_EFGI。h_EFGI 的兄弟是 h_ABCD,父节点就是根。
  2. 证明要给三层的兄弟:{h_G, h_EF, h_ABCD},共 3 个,等于 log₂(8) = 3。
  3. 验证方第一步算 h_I = H(I)。
  4. 第二步 h_GI = H(h_G + h_I),G 在左、I 在右。
  5. 第三步 h_EFGI = H(h_EF + h_GI)。
  6. 第四步 RT’ = H(h_ABCD + h_EFGI)。
  7. 比对 RT’ 是否等于 RT,相等则 Data I 在树中。
  8. 证 Data G:给的是 {h_I, h_EF, h_ABCD}。步骤一样,只是第二步里 h_G 由自己算,h_I 由证明提供,算式仍是 H(h_G + h_I)。
  9. 对照直接把所有数据一起哈希:证明一条要交出 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 个。验证方:

  1. 算 h_C = H(C);
  2. h_CD = H(h_C + h_D),C 在左、D 在右;
  3. h_ABCD = H(h_AB + h_CD),这次自己算出来的那半边在右;
  4. 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 数字签名:私钥签,公钥验:补上哈希证明不了的来源,看签名怎么做、为什么先哈希再签、签名为什么不保密。

下一讲 →
C01b-3 C01b-3 数字签名:私钥签,公钥验

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