← COMP5567 全部讲次
L11c · 第 11 周

L11c PoH:用一条哈希链当时钟

从零讲 Solana 的 Proof of History:哈希为什么只能一个接一个算,交易怎样混进哈希链变成 entry,区块怎样由 entry 组成,验证者怎样拆开并行验算,Turbine 怎样把区块切片传播。

一句话版

PoH 让 leader 不停地对上一个哈希结果再求哈希,排成一条长链。哈希只能一个接一个算,所以链上第几个哈希,就代表过了多少时间。

交易被混进这条链的某一步,它在链上的位置就是它的时间戳。别人拿到链的片段,可以拆开同时验算,比生成快得多。

先认识这几个词

词 全称 / 读法 一句人话
哈希 hash,H(·) 把任意数据压成固定长度指纹的函数
哈希链 hash chain 每一步都对上一步的结果再求一次哈希
PoH Proof of History 用哈希链证明「这件事发生在那件事之后」
entry 条目 PoH 的一条记录:算了几次、混了哪些交易、结果是多少
Turbine Solana 的广播协议 把区块切成小片,分层转发
并行验证 parallel verification 把链拆成几段,多核同时验算

一个类比:只能一页一页翻的日记本

有一本特殊的日记本,每一页都要抄写上一页最后一行的「指纹」才能开始写,指纹要现场算,算一页大约要一分钟。写到第 100 页,就证明至少过了 100 分钟,谁也没法跳着写。

有事发生时,把它记在当页,事情就被钉在了这一页的位置上:它比前一页的事晚,比后一页的事早。

检查的人不必从头翻。可以请 10 个人各拿 10 页,同时核对每页的指纹对不对,10 分钟就能查完 100 页。

类比在哪里失效:

  • 日记的「指纹」可以照抄;哈希必须真算,抄不来。
  • 写日记的速度因人而异;哈希的速度由硬件决定,PoH 按「算了多少次」计时,不按真实分钟。
  • 日记本可以撕页重写;哈希链改动一处,后面所有哈希都要重算。

从零讲起

1. 先补一块:哈希链(补充)

它解决什么问题

PoH 整个建立在「哈希链」上。要看懂后面的 H12499 = H(H12498 || …),先得知道哈希函数有什么性质、把它一环扣一环会得到什么。哈希函数本身在 L01a-2 区块头与挖矿 用过,这里只补「链」的部分。

直觉

哈希函数 H 把任意输入变成一串固定长度的指纹。输入改一点,指纹就面目全非;只给指纹,倒推不出输入。

把输出再喂回去:H1 = H(H0),H2 = H(H1),……这就成了一条链。想知道 H3,只能老老实实先算出 H1、H2,没有捷径。

一步一步看

目标:一环一环算哈希链,看后一个为什么必须等前一个,以及改动一个值会牵连多少。

  1. 从一个起点 H0 出发(课件里叫 genesis)。

  2. 算 H1 = H(H0)。

  3. 算 H2 = H(H1)。这一步必须等 H1 出来。

  4. 算 H3 = H(H2),以此类推。

    五个方框 H0 到 H4 依次用箭头相连,每一步都是对上一个结果再求一次哈希;青绿标出 H2 到 H3 这一步,说明后一个必须等前一个算完,所以哈希个数可以当作时间

  5. 改动链上任何一个值,它后面所有哈希都会变,要从那里重算到底。

怎么算

H(k) = H(H(k−1)),H0 为起点

意思是:第 k 个哈希只能由第 k−1 个算出来。算到第 k 个,至少要花「算 k 次哈希」的时间。

常见误解

以为有了 H0,可以直接跳着算出 H100

不行。哈希没有「快进」公式,只能从 H0 一步步算 100 次。

以为多台机器分工就能更快算出一条哈希链

每一步依赖上一步,别的机器拿不到输入,没法分工。生成只能单线程。

试一下

改了 H2 之后,H1 会变吗?H4 会变吗?

H1 不变,它在 H2 之前;H3、H4 都会变,要重算。

算一次哈希要 1 微秒,算到 H5000 至少要多久?

5000 × 1 微秒 = 5 毫秒。

2. PoH:顺序生成、并行验证的时钟

它解决什么问题

分布式系统里每台机器的时钟都不准,节点之间要对时就得来回发消息。PoH 给 Solana 提供一个不依赖外部时间源的时钟:每个验证者都在跑同一条哈希链,看算到第几个哈希,就知道现在是第几个 slot、第几个 tick。

从哪来(补充)

PoH 来自 Anatoly Yakovenko 的白皮书「Solana: A new architecture for a high performance blockchain」。白皮书把 PoH 定义为「a proof for verifying order and passage of time between events」,并说它和 PoW、PoS 一起用,能减少 BFT 复制状态机的消息开销。

出处:Solana 白皮书 PDF

直觉

课件的一句话概括得很准:PoH 把「时间」本身变成了可以在本地验证的数据(哈希)。

生成的时候只能一个接一个算,所以算够多少个哈希,就证明过了多少时间。验证的时候,因为每一段的起点和终点都公开了,可以把整条链切成很多段,交给多核同时验算。

这一快一慢的差距,正是它能当时钟又不拖慢网络的原因。

一步一步看

目标:看验证者怎样靠数哈希知道现在是第几个 slot、第几个 tick,三条性质又为什么防得住作弊。

  1. 验证者持续运行 PoH 哈希函数,让本地时钟和网络同步,随时知道当前 slot 号、tick 号。

  2. 每算完一个 tick 的哈希,产出一个 entry,1 tick ≈ 6.25 ms。

  3. 一个 slot 最多 64 个 tick,即最多 64 个 entry,打包成一个区块,约 400 ms。

  4. 对照三条防作弊性质:

    性质 为什么成立
    不能并行 每个哈希依赖上一个输出,只能单线程算
    可验证的延迟 知道起始种子和哈希个数,任何消息都能在毫秒级验证
    改历史代价高 插队或回滚交易要重算整条哈希链,成本和真实时间成正比
  5. 不需要外部时间源:没有谁去问网络时间服务器,时间就是哈希个数。

怎么判断

判断一个说法是否符合 PoH,抓住两件事:

  • 生成是不是只能顺序做?是,所以能证明时间流逝。
  • 验证是不是可以并行做?是,所以验证比生成快。

意思是:PoH 只证明「先后」和「至少过了多久」,它不负责决定哪条链有效,那是 Tower BFT 的事。

常见误解

以为 PoH 是一种像 PoW 那样的出块竞赛

PoH 没有竞赛。出块者由 PoS 轮值表定好,PoH 只是 leader 手里的时钟。

以为 PoH 能告诉你现在是北京时间几点

它只给出相对顺序和经过的哈希个数,不对应墙上的钟点;6.25 ms、400 ms 都是在正常硬件上的大约值。

以为验证 PoH 也要从头单线程算一遍

验证可以把链切段,多核同时算,每段核对起点和终点即可。

试一下

攻击者想把一笔交易挪到 1 秒前,要付出什么?

要从那个位置起重算后面的整条哈希链,至少再花上原来那段的真实时间,追不上一直在往前算的网络。

一条链有 64 个 tick,用 8 个核验证,理想情况下比生成快几倍?

每个核验 64 ÷ 8 = 8 个 tick,大约快 8 倍。

3. entry 和区块:交易怎样插进哈希链

它解决什么问题

一条只有哈希的链只是时钟,还要把交易钉上去。leader 把收到的交易打包,在某一步把交易摘要混进哈希,这一步之后的所有哈希都依赖这些交易。交易的先后,就由它在链上的位置决定。

直觉

平时 leader 只算 H(上一个)。有交易时,这一步改成 H(上一个 || 交易摘要),交易就被「焊」进链里了。

每个 tick 结束时,leader 写下一条 entry:这一段算了几次哈希、混进了哪些交易、最后的结果是多少。区块就是一个 slot 里所有 entry 的集合,再加上前一块的哈希和 leader 签名。

一步一步看

目标:看交易摘要怎样混进哈希链、写成 entry、再装进区块,弄清交易先后由什么决定。

课件的例子:初始状态 H0,leader 从 RPC 节点收到交易 T1、T2、……

  1. H1 = H(H0),H2 = H(H1),……一路算到 H12498,都是普通的哈希。

  2. 最后一步把交易混进来:H12499 = H(H12498 || H(T1||T2||…))。

  3. 这个 tick 约 12500 个哈希,写成一条 entry:Num_hashes 12500,TX 为 Tx1、Tx2、……,Hash 为 H12499。

    上方哈希链从 H0 算到 H12498,最后一步把交易摘要 H(T1||T2||…) 混进去得到 H12499,青绿标出这一步;下方 Entry 卡片记 Num_hashes 12500、交易列表和结果哈希 H12499

  4. 把一个 slot 的 entry 装进区块。课件假设每个 slot 两个 tick,即两个 entry。

  5. 每个区块含:前一个区块的哈希(Block1 为空)、全部 entry、leader 签名。Block2 的 entry 接在 Block1 的 entry 2 之后。

    三个区块并排,每块由前一块哈希、两个 entry 和 leader 签名组成;Block1 的前一块哈希为空,青绿曲线表示 Block2、Block3 的前一块哈希接在上一块最后一个 entry 之后

怎么算

普通一步:H(k) = H(H(k−1))

混交易的一步:H(k) = H(H(k−1) || H(交易们))

entry = {这一段的哈希个数, 交易列表, 最后的哈希}

意思是:交易只影响它混进去的那一步及之后的哈希。知道前一个哈希、交易和次数,任何人都能重算出 entry 里的结果哈希。

常见误解

以为 Num_hashes 12500 表示这个 entry 装了 12500 笔交易

12500 是这一段算了多少次哈希,交易列表单独写在 TX 里。

以为交易的时间戳是 leader 自己填的一个数字

时间戳就是交易在哈希链上的位置,没法随便填;改位置就要重算后面的链。

试一下

如果 leader 在 H500 这一步混入交易 Tx,H501 依赖 Tx 吗?H499 呢?

H501 依赖,它由 H500 算出;H499 不依赖,它在 Tx 之前。

一个 slot 有 3 个 tick,区块里有几个 entry(按课件口径)?

3 个,每个 tick 一个。

4. 并行验证和 Turbine 传播

它解决什么问题

leader 出了块,要尽快送到所有验证者手里,验证者也要尽快验完。整块一次性发给每个人会堵网络;从头单线程验又太慢。Solana 用 Turbine 把块切片分层传,再利用 entry 的结构并行验。

从哪来(补充)

Anza 的验证者文档把 Turbine 描述为多层区块传播机制,每个节点只向下一层的一小组节点转发。数据切成 shred,按组加上纠删码(FEC),丢了几片也能恢复。

出处:Anza Docs: Turbine Block Propagation

直觉

传播像传话树:leader 只告诉几个人,每个人再告诉下一层的几个人,很快全网都知道了,leader 自己不用挨个发。

验证像分组批改:每个 entry 都写明了起点、次数和结果,验证者把几个 entry 分给几个核同时重算,最后对一遍结果。PoH 已经给出了交易的先后,所以不冲突的交易也可以并行执行。

一步一步看

目标:用一个只有两个 entry 的小区块,看验证者怎样把它拆成两路同时验。

课件的验证例子:1 tick = 2 个哈希,1 slot = 2 tick,leader 只插入 1 笔交易 Tx。

  1. leader 顺序算:H1 → H2 = H(H1||Tx) → H3 = H(H2) → H4 = H(H3)。

  2. 产出两个 entry:Entry1 = {num_hashes 2,结果 H2,Tx};Entry2 = {num_hashes 2,结果 H4,无交易}。

  3. Turbine 把区块切成小片(例如一个 entry 一片)分层广播,验证者凭收到的片知道是哪个 slot、哪个 tick。

  4. 验证者同时开两路:一路从 H1 和 Tx 算出 H2′,看是否等于 H2;另一路从 H2 连算两次得 H4′,看是否等于 H4。

    上方是 leader 的顺序链 H1、H2、H3、H4,H2 混入交易 Tx,产出两个 entry;下方两个青绿框是验证者的两个线程,同时检查 H2′ 是否等于 H2、H4′ 是否等于 H4

  5. 两路都对上,这两个 entry 就通过。如果某个 leader 没收到上一个 slot 的块,它会把自己的块接在最近的一个块后面。

怎么判断

拿到一个 entry 能不能单独验?看它和前一个 entry 的结果哈希:

  • 有前一个结果哈希(起点)、本段次数和交易,就能单独重算。
  • 所以多个 entry 之间互不等待,可以并行。

意思是:生成时 Entry2 必须等 Entry1 算完;验证时 Entry2 只需要 Entry1 公开的结果 H2 当起点,两路可以同时开工。

常见误解

以为验证者必须等收到整个区块才能开始验

Turbine 按片传,验证者收到 entry 就能验对应的那一段。

以为并行执行交易会打乱顺序

PoH 已经定好先后,只有互不冲突的交易才并行执行,冲突的仍按顺序来。

试一下

验证者算出 H4′ ≠ H4,说明什么?

Entry2 的结果对不上,可能 leader 少算或篡改了,这个 entry 验证失败。

把例子改成 1 slot = 4 tick,验证者最多可以同时开几路?

4 路,每个 entry 一路。

把它们串起来

哈希链每一步依赖上一步,只能顺序算,所以哈希的个数可以当时间用。PoH 就是 leader 手里一直在跑的这条链,验证者也跟着跑,靠它知道当前的 slot 和 tick。

交易被混进链的某一步,它的位置就是它的时间戳。每个 tick 结束写一条 entry,记下次数、交易和结果哈希;一个 slot 的 entry 加上前一块哈希和签名就是一个区块。

生成慢、验证快:Turbine 把区块切片分层传出去,验证者拿到 entry 就分几路同时重算,对上就通过。

PoH 只回答「先后」和「过了多久」。分叉了选哪条、什么时候算定了,要靠下一页的 Tower BFT 投票。

课件里的坑

  • [读图提醒] p.18 的 H0 到 H12499 正好是 12500 个哈希值,课件把 Num_hashes 记为 12500,按「这一个 tick 内算的哈希个数」理解。
  • [读图提醒] p.17 说「每个 tick 一个 entry、一个 slot 最多 64 个 entry」,是课件的简化口径,按它作答即可。
  • [读图提醒] p.20 的「1 tick = 2 个哈希」是为了好画;p.18 的口径是一个 tick 约 12500 个哈希。
  • [读图提醒] p.15 说 PoH 不需要外部时间源;p.16 的 6.25 ms、400 ms 只是正常硬件上的大约时长,不是用墙钟测出来定的。

课后 10 分钟:考点复习

这 10 分钟怎么用:先默写 PoH 的三条防作弊性质,再写出 H12499 的式子和 entry 的三个字段,最后把 p.20 的验证例子在纸上画一遍。

必背

  1. PoH 是内置在验证者里的密码学时钟:用 SHA-256 链式哈希证明时间流逝,顺序生成、并行验证,不需要外部时间源
  2. 防作弊:每个哈希依赖上一个输出,不能并行;知道起始种子和哈希个数就能验证;插队或回滚要重算整条链,成本和真实时间成正比
  3. 交易混进哈希链:H12499 = H(H12498 || H(T1||T2||…));一个 tick 约 12500 个哈希;entry 记 Num_hashes、交易和结果哈希
  4. 区块 = 前一个区块的哈希 + 本 slot 的全部 entry + leader 签名;Block1 的前一块哈希为空
  5. 验证例子:1 tick = 2 个哈希,Entry1 {2, H2, Tx},Entry2 {2, H4, 空};验证者并行检查 H2′ = H2 和 H4′ = H4

课件例题

例 1(课件 p.14):区块由什么组成

假设每个 slot 两个 tick,画出 Block1、Block2 的结构,并说明两者怎样连起来。

提示

每块三部分;两个 tick 对应两个 entry。

解答

每块含前一个区块的哈希、两个 entry、leader 签名。Block1 的前一块哈希为空;Block2 的前一块哈希指向 Block1,Block2 的 entry 1 接在 Block1 的 entry 2 之后,由 PoH 的 SHA-256 链连成一条线。

例 2(课件 p.18):写出含交易的那一步和 entry

初始状态 H0,一个 tick 约 12500 个哈希,leader 收到交易 T1、T2、……。写出混入交易的哈希式和这条 entry。

提示

交易在 tick 的最后一步混进去。

解答

H1 = H(H0),H2 = H(H1),……,H12499 = H(H12498 || H(T1||T2||…))。Entry:Num_hashes 12500;TX:Tx1、Tx2、……;Hash:H12499。

例 3(课件 p.20):PoH 验证

1 tick = 2 个哈希,1 slot = 2 tick,leader 只插入 1 笔交易 Tx。写出 leader 的 entry 和验证者的检查。

提示

Tx 混在 Tick 1 的第二个哈希里。

解答

leader:H2 = H(H1||Tx),H3 = H(H2),H4 = H(H3)。Entry1 = {num_hashes 2,H2,Tx};Entry2 = {num_hashes 2,H4,空}。验证者收到两个 entry 后并行验证:从 H1 和 Tx 算 H2′,检查 H2′ = H2;从 H2 算 H3 再算 H4′,检查 H4′ = H4。

完整例题

题目:设 1 tick = 3 个哈希,1 slot = 2 tick。leader 从 H0 开始,在第一个 tick 的第二步混入交易 Tx,第二个 tick 没有交易。(1) 写出 H1 到 H6;(2) 写出两条 entry;(3) 验证者怎样并行验?

解法:

第一步,写哈希链。H1 = H(H0),H2 = H(H1||Tx),H3 = H(H2);H4 = H(H3),H5 = H(H4),H6 = H(H5)。

第二步,写 entry。Entry1 = {num_hashes 3,结果 H3,Tx};Entry2 = {num_hashes 3,结果 H6,无交易}。

第三步,并行验证。线程 A:从 H0 出发,算 H1,混 Tx 得 H2,再算 H3′,检查 H3′ = H3。线程 B:从 Entry1 公开的 H3 出发,连算 3 次得 H6′,检查 H6′ = H6。两路同时进行。

要点:每个 entry 的起点是上一个 entry 的结果哈希;交易混在哪一步就从哪一步起改变后面的哈希。

答题格式:先列链,再写 entry 三字段,最后写每一路的起点、次数和要比对的结果。

变式题(先自己做)

1. 沿用 p.20 的设定,但 leader 在 Tick 2 的第一步混入第二笔交易 Tx2。写出新的 H3、H4 和 Entry2。(改编自课件 p.20)

提示

Tick 2 的第一步就是 H3。

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

H3 = H(H2||Tx2),H4 = H(H3)。Entry2 = {num_hashes 2,H4,Tx2}。判分点:H3 混入 Tx2;H4 由新 H3 算出;Entry2 的交易字段写 Tx2。

2. 自编情境:有人声称「我用 100 台机器一起算,能比 leader 更快地造出一条更长的 PoH 链」。这个说法对吗?

提示

想想生成时每一步的输入从哪来。

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

不对。每个哈希依赖上一个输出,生成只能单线程,100 台机器没法分工。判分点:指出顺序依赖;说出多机只能加速验证、不能加速生成。

闪卡自测

1. PoH 用什么哈希函数?

SHA-256 链式哈希(p.15)。

2. PoH 的生成和验证分别是什么方式?

顺序生成,并行验证(p.15)。

3. PoH 需要外部时间源吗?

不需要(p.15)。

4. 为什么改历史代价高?

要重算整条哈希链,成本和真实时间成正比(p.16)。

5. 一个 tick 约多少个哈希(p.18 口径)?

约 12500 个(p.18)。

6. entry 有哪三个字段?

Num_hashes、交易列表、结果哈希(p.18)。

7. 区块由哪三部分组成?

前一个区块的哈希、全部 entry、leader 签名(p.14)。

8. Turbine 做什么?

把区块切成小片广播,减少网络拥塞(p.19)。

下一讲

下一页是 L11d Tower BFT 投票:出了块还可能分叉,验证者怎样按质押投票选出最重的分叉,并经过 processed、confirmed、finalized 三级确认。

下一讲 →
L11d L11d Tower BFT 投票:最重分叉和三级确认

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