← COMP5567 全部讲次
L04b-2 · 第 3 周

L04b-2 支撑比特币的三项技术:Merkle 树、矿池与 P2P 网络

Merkle 树怎么用一个根锁住整块交易、怎么剪枝、怎么给轻节点出证明;PoW 为什么难算易验,矿池为什么只降方差不改期望;交易和块怎么在没有中心的 P2P 网络里先验证再转发。

一句话版

区块头只有 80 字节,靠 Merkle 树的一个根锁住块里全部交易;挖块靠的 PoW 难算易验,单干矿工收入太不稳定,于是合伙进矿池;交易和块在一张没有中心的对等网络里,每个节点先验证、再转给邻居。

上一页 L04b 讲了链在冲突里怎么收拢。这一页补上前面一直默认存在的三块地基。

先认识这几个词

词 全称 / 读法 一句人话
Merkle 树 Merkle tree,哈希树 交易两两哈希、层层往上,最后得到一个根
Merkle Root 默克尔根 树顶那一个哈希,写进区块头
Merkle 证明 Merkle proof,包含证明 证明某笔交易在块里所需的几个兄弟哈希
PoW Proof-of-Work,工作量证明 用大量试错证明自己真花了算力
矿池 mining pool 很多矿工合伙挖,按贡献分钱
SPV Simplified Payment Verification,简化支付验证 只存区块头的轻节点
gossip 泛洪式转发 收到就验证,验证过就转给所有邻居

一个类比:封条、合伙买彩票、传话

Merkle 树像一叠文件的封条。每两份文件装一个信封封口,两个信封再装进大信封封口,最后只在最外层盖一个章。拆动任何一份文件,外层的章就对不上。

矿池像同事合伙买彩票。一个人买,可能好多年一次都中不了;十个人合买,中奖次数多了,每次分到的少了,长期看每人到手的钱和单干差不多。

P2P 网络像村里传话。没有广播站,谁听到消息先判断靠不靠谱,靠谱再告诉自己认识的人,消息就一圈圈传开。

类比在哪里失效:

  • 信封拆开能重新封上,哈希改了内容就一定变,没法伪造出同一个根。
  • 彩票的奖池固定,挖矿奖励按出块发,矿池还要从中抽手续费,合伙后的期望略低于单干。
  • 村里传话会走样,比特币节点转发的是原样数据,签名不对的直接丢掉。

从零讲起

1. Merkle 树:一个根锁住整块交易

它解决什么问题

区块头只有 80 字节,块里却可能有几千笔交易。区块头需要一个固定长度的字段,代表「这块里就是这些交易,一笔不多一笔不少」。

从哪来(补充)

Merkle 树由 Ralph Merkle 提出,他在 1979 年为这个结构申请了美国专利,1982 年公布。比特币白皮书用它把交易汇总进区块头。

出处:Wikipedia: Merkle tree

直觉

把交易两两配对,每对拼起来算一次哈希,得到上一层。上一层再两两配对,一直算到只剩一个,这个就是 Merkle Root。

任何一笔交易改了一个比特,它的哈希就变,沿途每一层都变,Root 跟着变。

一步一步看

目标:看四笔交易怎样两两哈希、一层层算到区块头里的那一个 Root。

  1. 四笔交易 Tx0 到 Tx3,各自算哈希,得到 Hash0 到 Hash3。

  2. Hash0 和 Hash1 拼起来再哈希,得到 Hash01;Hash2 和 Hash3 同样得到 Hash23。

  3. Hash01 和 Hash23 拼起来再哈希,得到 Root。

  4. Root 写进区块头,区块头再参与 PoW。

    四笔交易的 Merkle 树:最底层是 Tx0 到 Tx3 四笔交易,各自哈希得 Hash0 到 Hash3;Hash0 和 Hash1 拼起来哈希得 Hash01,Hash2 和 Hash3 拼起来哈希得 Hash23;Hash01 和 Hash23 拼起来哈希得 Root,Root 用青绿标出,区块头里只放它这一个

  5. 某一层个数为奇数时,比特币把最后一个复制一份凑成偶数,再往上算。

怎么算

父节点 = H(左子节点 ‖ 右子节点),‖ 表示把两段拼起来

意思是每个非叶节点都是它两个孩子拼接后的哈希,叶子是交易本身的哈希。

连锁反应按这条链走:改一笔交易 → 它的叶子变 → 沿途父节点变 → Root 变 → 区块头哈希变 → 原来的 PoW 作废。

常见误解

以为 Merkle Root 也要有前导零

只有区块头哈希要满足目标。Merkle Root 只是区块头里的一个字段,不需要满足任何条件。

以为对整张交易表做一次哈希效果一样

锁住交易这一点上一样,可整表哈希删掉任何一笔就无法再验证,也没法只证明其中一笔。Merkle 树能做到后面两件事,下一节讲。

试一下

有人把 Tx1 的金额改了一个数字,但不重新挖矿。哪些哈希会变?这个块还有效吗?

Hash1、Hash01、Root 依次变,区块头哈希也变。它大概率不再低于目标,节点验证时判块无效。

2. 剪枝与 Merkle 证明:只留几个哈希也能验证

它解决什么问题

花掉的旧交易一直存着很占磁盘,可删掉之后,区块头里的 Root 还要能算回来。另一方面,手机钱包不想下载整块交易,只想确认「付给我的那笔确实在块里」。

直觉

验证 Root 只需要每一层的哈希,不需要交易原文。所以删掉一批交易时,只要留下它们上方的那个哈希当「树桩」,Root 照样算得出来。

反过来,要证明某一笔在块里,只需递上它沿途每一层的兄弟哈希。对方从这笔交易往上算,算到顶和 Root 比一下就行。

一步一步看

目标:看删掉旧交易、或只递上几个兄弟哈希时,为什么照样能算回同一个 Root。

剪枝的例子:

  1. Tx0 到 Tx2 已经花掉,打算删,只留 Tx3。
  2. Tx0、Tx1 两笔都删,它们上方的 Hash01 留下当树桩。
  3. Tx2 删掉,它的 Hash2 留下。
  4. Tx3 和 Hash3 留着。用 Hash2、Hash3 算回 Hash23,再和 Hash01 算回 Root,和区块头里的值一致。
左右两张对比图。左图是完整的 Merkle 树:四笔交易 Tx0 到 Tx3 各自哈希成 Hash0 到 Hash3,两两合并成 Hash01 和 Hash23,再合并成区块头里的 Root Hash,区块头里还有 Prev Hash 和 Nonce。右图是剪掉 Tx0 到 Tx2 之后:这三笔交易和 Hash0、Hash1 都不再保留,只留下 Hash01、Hash2、Hash3 和 Tx3,仍然能一路算回同一个 Root Hash
图片来源:COMP5567 Lecture_4-Bitcoin.pdf, p.38

Merkle 证明,同一棵树:

  1. 对方手里只有区块头里的 Root,你要证明 Tx3 在块里。

  2. 你递上 Tx3,加上 Hash2 和 Hash01 两个兄弟哈希。

  3. 对方算 H(Tx3) 得 Hash3,再算 H(Hash2 ‖ Hash3) 得 Hash23。

  4. 再算 H(Hash01 ‖ Hash23),结果等于 Root,就证明了 Tx3 在块里。

    Merkle 证明 Tx3 在块里:同一棵四笔交易的 Merkle 树,要证明 Tx3 在块里只需提供 Hash2 和 Hash01 两个兄弟哈希,用青绿标出;Tx0、Tx1、Tx2、Hash0、Hash1 都用不上,画成虚线;对方先算 Tx3 的哈希得 Hash3,再和 Hash2 拼起来得 Hash23,再和 Hash01 拼起来得到根,和手里的 Root 比对

怎么判断

问「要留哪些哈希」或「证明要给哪些哈希」,从目标交易出发往上走,每一层把它的兄弟记下来。

剪枝时,一整棵子树都删掉,就只留这棵子树的根。证明时,沿途有几层就给几个兄弟哈希,所以证明大小按 log n 增长,交易翻一倍,证明只多一个哈希。

常见误解

以为剪枝要保留被删交易的全部叶子哈希

Tx0 和 Tx1 都删时,只留它们上方的 Hash01 就够了,Hash0、Hash1 也可以丢掉。

以为 Merkle 证明要把块里所有交易的哈希都给对方

只给沿途的兄弟哈希。四笔交易给两个,交易越多,这个数增长得越慢。

试一下

同一棵四笔交易的树,要证明 Tx0 在块里,要给哪两个哈希?

Hash1 和 Hash23。对方算 H(H(Tx0) ‖ Hash1) 得 Hash01,再算 H(Hash01 ‖ Hash23) 和 Root 比对。

3. PoW 与矿池:难算易验,合伙降波动

它解决什么问题

谁来出下一块,需要一个没法靠伪造身份抢到的规则。PoW 让出块权按算力分。可算力摊到一台矿机上,单干的人可能几年都挖不到一块,收入太不稳定,这就有了矿池。

从哪来(补充)

比特币用的 PoW 沿用 Hashcash。它由 Adam Back 在 1997 年提出,最初用来反垃圾邮件:发信人要先算出一个哈希谜题,证明自己花了算力。比特币把它搬到出块上。

出处:Wikipedia: Hashcash

直觉

PoW 有三个要素:难产生,要花大量时间和电;易验证,别人算一次哈希就知道;满足特定条件,比特币的条件是区块头哈希小于目标值。

挖矿是纯靠运气的试错,挖中的概率只和你的算力占比有关。矿池把很多人的算力合起来,谁挖中都按贡献分。中奖从几年一次变成天天都有,长期总数不变。

一步一步看

目标:看挖矿怎样试 nonce、挖中后怎样一算就验,以及进矿池后收入为什么变平稳。

  1. 矿工不停换区块头里 32 位的 nonce,算区块头哈希。

  2. nonce 试完还没挖中,就改 coinbase 里可自由填的一段字段,换出新的 Merkle Root,再试一轮。

  3. 挖中后,哈希开头有一长串 0,任何节点算一次就能验证。

  4. 单干:大多数时间颗粒无收,偶尔挖中一整块。

  5. 进矿池:池服务器下发任务,矿工提交难度低一些的份额证明自己在干活,按份额分钱。

    矿池降低方差、不改变期望:上下两条时间线,上面是单干,大部分时间没有收入,某一天挖中一整块,拿到一根很高的柱子;下面是矿池,每段时间都分到一小笔,用青绿标出,小柱子加起来和单干那根高柱面积相同,只是还要扣池子的手续费;图只示意期望相同、波动不同

矿池协议有两种:

协议 谁组装候选块 用得多不多
Stratum 池服务器 主流
GetBlockTemplate(BIP 22/23) 矿工自己,自己选交易 少,去中心化程度更高

怎么判断

问「加入矿池对收入有什么影响」,分开说期望和方差两件事。

期望只由算力占比决定,进不进池都一样,还要扣手续费。方差大幅下降,收入从几年一次的大奖变成每天一点小钱。

再问「矿池有什么风险」:算力集中。2018 年前后的饼图上前四大矿池合计已过半,理论上几家合谋就能发动 51% 攻击。比特币靠的是作恶会让矿池自己持有的币和设备贬值这一经济约束,技术上并不能阻止。

常见误解

以为加入矿池能多赚

期望不变,扣掉池子的手续费还略少一点,换来的只是收入稳定。

以为 PoW 的「难」是因为题目难解

哈希没有捷径可走,只能一个个试。难的是要试的次数多,每次试本身很简单,这也是验证容易的原因。

试一下

一个矿工占全网 0.01% 算力,进矿池后他一年的期望收入会变成多少倍?

不变,仍然约等于全年出块奖励的 0.01%,再扣掉手续费。变的只是到账的频率和波动。

4. P2P 网络:没有中心,先验证再转发

它解决什么问题

没有中央服务器,一笔交易、一个新块要怎么让全网几千个节点都收到?新节点又怎么找到网络?

直觉

比特币是叠在互联网上的对等网络,所有节点平等。新节点只要知道一个已在网里的节点,问它要更多地址就能接进来,这种引导节点叫 seed node。

消息靠泛洪传开:收到一笔新交易,先检查,合格就转给所有邻居。无效数据在第一跳就被丢掉,传不远。

一步一步看

目标:看一笔交易怎样在没有中心的网络里逐跳验证、转发,最后传遍全网。

  1. Alice 的节点 A 把交易发给所有邻居 B 和 C。

    gossip 传播第 1 步:七个节点 A 到 G 组成的网络,A 有这笔交易,把它发给邻居 B 和 C,B、C 用青绿标出为新收到,其余节点还没收到

  2. B、C 检查签名、引用的输出没花过、格式合法,通过了再转给自己的邻居 D、E、F。

    gossip 传播第 2 步:B 和 C 验证通过后转发,B 发给 D、E,C 发给 E、F;D、E、F 用青绿标出为新收到,其中 E 收到了两份

  3. D、E、F 都转给 G。G 收到三份副本,只处理第一份,重复的直接忽略。

    gossip 传播第 3 步:D、E、F 都转发给 G,G 用青绿标出为新收到;G 收到三份副本,只处理第一份,重复的直接忽略,不再转发

  4. 新块的传播一样:矿工广播给邻居,邻居验证这块合法再往外转。

网络里有三类节点:

节点类型 存什么 做什么
Full Node 整条区块链 独立验证每个块、每笔交易
Miner 是 full node 额外参与出块
SPV Node 只存区块头 需要时向 full node 要 Merkle 证明

怎么判断

问「某类节点能做什么、要信任谁」,看它存了什么。

full node 什么都自己验,谁也不用信。SPV 节点只存区块头,80 字节乘区块数,几十 MB 就能跟上链;它能验证一笔交易在某块里,却没法确认 full node 有没有瞒下别的交易,所以要信任对方不隐瞒。

gossip 和第三讲的可靠广播同源,都是第一次收到就转给所有邻居。不同在于比特币网络成员开放、不固定,只能做到高概率送达。

常见误解

以为 SPV 节点和 full node 一样安全

SPV 只能验证「这笔在块里」,要信任 full node 不隐瞒交易。换来的是存储从整条链降到几十 MB 的区块头。

以为节点收到什么就转什么

节点先验证再转发,签名不对、输出已花的交易在第一跳就被丢掉,这也是防垃圾数据泛滥的闸门。

试一下

攻击者控制了某个新节点的全部对等连接,会发生什么?怎么防?

这叫 eclipse 攻击,攻击者可以给它喂一条假链、扣住真交易。防法是连接多个随机对等节点、限制同一 IP 段的连接数、seed 节点多样化。

把它们串起来

前面几页一直默认「块里的交易改不了」「全网都能收到新块」,这一页把这两个默认补齐。

块里的交易改不了,靠的是 Merkle 树:一个根写进区块头,改任何一笔,根变,区块哈希变,PoW 作废。同一棵树还让旧交易可以剪掉,让轻节点用几个哈希验证一笔交易。

PoW 让出块权按算力分,难算易验。单干收入波动太大,矿工合伙进矿池,期望不变、方差变小,代价是算力集中,51% 攻击的约束于是落到经济代价上。

全网都能收到新块,靠的是对等网络里的 gossip:每个节点先验证再转发,SPV 节点再借 Merkle 证明,只存区块头也能用。

课件里的坑

  • [课件有误] 课件把 SPV 写成 Simple Payment Verification → 白皮书原文是 Simplified Payment Verification(p.52)
  • [补充] 课件 p.36 只给了 Merkle 树的定义 → 叶子数为奇数时要复制最后一个凑偶数,Merkle 证明大小按 log n 增长,这两点是 SPV 的依据,考试常问(p.36)
  • [读图提醒] p.47 截图里 Hash 一栏有一长串前导零 → Merkle Root 一栏没有,它不需要满足任何条件(p.47)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先画一棵四笔交易的 Merkle 树,标出剪掉前三笔后要留的哈希,再标出证明 Tx3 在块里要给的哈希;然后默写 PoW 三要素和矿池「降方差不改期望」;做课件例题;最后回查两个最容易错的地方:以为矿池能提高期望收益、以为 SPV 节点和 full node 一样安全。

必背

  1. Merkle 树让区块头只存一个根就锁定全部交易;改任何一笔交易,Root 变,区块哈希变,PoW 作废。
  2. 剪枝只需保留兄弟哈希:剪掉 Tx0 到 Tx2 后保留 Hash01 与 Hash2。
  3. Merkle 证明只需给沿途的兄弟哈希,大小按 log n 增长,这是 SPV 只存区块头也能验证交易的依据。
  4. PoW 三要素:难产生、易验证、满足特定条件;比特币沿用 Hashcash。
  5. 矿池降低收益方差、不改变期望;协议 Stratum / GetBlockTemplate。
  6. 三类节点:full node 存全链,miner 是出块的 full node,SPV 只存区块头。
  7. 块与交易的传播都是「先验证再转发」的泛洪,即 gossip,与可靠广播同源。

课件例题

例 1(课件 p.38):剪掉 Tx0 到 Tx2,要保留哪些哈希才能算回 Root

见下方完整例题。

例 2(课件 p.36):要向只有 Root 的人证明 Tx3 在块里,需要给什么

题面:四笔交易的 Merkle 树,对方只有区块头。你要证明 Tx3 在块里。

提示

从 Tx3 往上走,每一层记下它的兄弟。

解答
  1. 给 Tx3 和 Hash2、Hash01 两个兄弟哈希。
  2. 对方算 H(Tx3) = Hash3,H(Hash2 ‖ Hash3) = Hash23,H(Hash01 ‖ Hash23),和 Root 比对。
  3. 四笔交易给两个哈希,证明大小按 log n 增长。

例 3(课件 p.48):矿工为什么要加入矿池?加入后期望收益会变吗

题面:如题。

提示

分开说方差和期望。

解答
  1. 单干的收益方差极大,一台机器可能几年挖不到一块。
  2. 矿池合并算力、按贡献分,大幅降低方差。
  3. 期望不变,只由算力占比决定,还要扣池子的手续费。
  4. 协议有 Stratum 和 GetBlockTemplate 两种。

例 4(课件 p.52):比特币网络有哪三类节点?SPV 节点怎么验证交易

题面:如题。

提示

按「存什么、做什么」列表,再接上 Merkle 证明。

解答
  1. full node 存整条链并独立验证;miner 是额外参与出块的 full node;SPV 只存区块头。
  2. SPV 要验证某笔交易时,向 full node 要这笔交易的 Merkle 证明,自己算回 Root,和区块头里的比对。
  3. 代价是要信任 full node 不隐瞒交易。

完整例题

课件 p.38 的场景:一块里有四笔交易 Tx0 到 Tx3,Merkle 树如上。Tx0、Tx1、Tx2 已经花掉,节点想删掉它们省磁盘,只留 Tx3。问要保留哪些哈希,Root 才能算回来,以及为什么整表哈希做不到这一点。

第一步,确定能删什么。Tx0、Tx1 两笔都要删,它们整棵子树都不需要了,Hash0、Hash1 也可以丢,只留这棵子树的根 Hash01。

第二步,看 Tx2。Tx2 要删,可它的兄弟 Tx3 还在,算 Hash23 要用到 Hash2,所以 Hash2 留下。

第三步,列出保留清单。Hash01、Hash2,加上 Tx3 与 Hash3。

第四步,验算。Hash23 = H(Hash2 ‖ Hash3),Root = H(Hash01 ‖ Hash23),和区块头里的值一致,块仍可验证。

第五步,和整表哈希对比。整表哈希是把所有交易拼起来算一次,删掉任何一笔就再也算不回原值。Merkle 树能局部保留,剪掉三笔交易只多留两个哈希。

再多想一层:剪枝能成立,靠的是哈希的单向性和弱抗碰撞性。日后有人拿出 Tx2 的原文,你算一次哈希和留下的 Hash2 比,就能确认它确实是当年那笔。

变式题(先自己做)

变式|自编情境:一块里有 8 笔交易 Tx0 到 Tx7,Merkle 树完整。

(1) 要向 SPV 节点证明 Tx5 在块里,需要给哪几个哈希?(2) 如果这块有 1024 笔交易,证明要给几个哈希?(3) 如果这块只有 5 笔交易,树怎么建?

提示

先画出三层树,从 Tx5 往上每层记一个兄弟;交易数翻倍时树多一层。

判分点与答案

(1) 三个:Hash4(Tx5 的兄弟)、Hash67(Hash45 的兄弟)、Hash0123(Hash4567 的兄弟)。对方算 H(Hash4 ‖ H(Tx5)) = Hash45,H(Hash45 ‖ Hash67) = Hash4567,H(Hash0123 ‖ Hash4567) 比对 Root。

(2) 1024 = 2¹⁰,树有 10 层,给 10 个哈希。

(3) 叶子层 5 个,复制 Hash4 凑成 6 个,得到 3 个父节点;3 个再复制最后一个凑成 4 个,往上得 2 个,再得 Root。

判分点:兄弟哈希按层次给对;说出证明大小按 log n 增长;第 (3) 问说出复制最后一个凑偶数。

闪卡自测

1. 改动块里一笔交易的一个比特,会连锁影响什么?

该交易的哈希变,沿途父节点变,Merkle Root 变,区块头哈希变,原来的 PoW 作废(p.35)。

2. 剪掉 Tx0 到 Tx2 后要保留哪些哈希?

Hash01 和 Hash2,加上 Tx3 与 Hash3,就能算回 Root(p.38)。

3. 要向只有 Root 的人证明 Tx3 在块里,需要给什么?

Hash2 和 Hash01,证明大小随交易数按 log 增长(p.36 补充)。

4. 剪枝靠哈希函数的哪两个性质?

单向性和弱抗碰撞性:只存哈希,日后有人拿出原文也能验证它确实是当年那笔(p.37)。

5. PoW 的三要素是什么?

难产生、易验证、满足特定条件;比特币沿用 Hashcash(p.45)。

6. 区块头截图里,为什么 Hash 有一长串前导零而 Merkle Root 没有?

哈希小于目标在十六进制里表现为前导零,只有区块头哈希要满足这个条件(p.47)。

7. 加入矿池能提高期望收益吗?

不能。矿池降低收益的方差,期望只由算力占比决定,还要扣池子的手续费(p.48)。

8. 矿池算力集中,51% 攻击靠什么约束?

经济代价:矿池作恶会让自己持有的资产和设备贬值,技术上并不能阻止(p.49)。

9. 新节点怎么加入比特币网络?

联系一个已在网络里的 seed node,向它要更多节点地址;还有 DNS seed(p.51)。

10. 三类节点各存什么?

full node 存整条链;miner 是额外出块的 full node;SPV 只存区块头,需要时索取 Merkle 证明(p.52)。

11. 交易在网络里怎么传播?

简单泛洪,即 gossip:先验证再转发给所有邻居。和可靠广播「收到即转发」同源,只是开放网络成员不固定,可靠性是概率意义上的(p.53、p.54)。

下一讲

下一讲 L05a 从 PoW 往前走一步:不靠算力,改用押币来决定谁出块,会遇到什么新问题。

下一讲 →
T02 T02 HotStuff Part 1:三票成证书,三代成提交

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