← COMP5567 全部讲次
L05a · 第 4 周

L05a PoW 与 PoS:出块权从烧电换成押币

从零讲 PoW 的合法条件,再讲 PoS 为什么要换资源、只按余额选人为什么富者恒富,以及币龄选择的三条规则和那条公式。

一句话版

区块链要决定下一个块由谁来出。PoW 让大家拼算力,谁先算出一个足够小的哈希谁出块;PoS 改成按押在协议里的币来分配机会,省掉了电费,但得重新设计「怎么挑人」,否则富人会越挑越富。

这一页讲三件事:PoW 到底要算出什么,PoS 为什么换资源,以及币龄选择怎样挑出块人。下一页 L05a-2 讲换资源之后冒出的第二个漏洞。

先认识这几个词

词 全称 / 读法 一句人话
PoW Proof of Work,工作量证明 拼算力出块,算出合格哈希的人赢
PoS Proof of Stake,权益证明 按押上的币分配出块机会
Target 目标阈值 哈希要小于等于它才算合格,随难度调整
nonce 读「农斯」,随机数字段 区块头里专门拿来反复改、反复试的那个数
质押 stake 把币锁进协议当押金
forger / validator 锻造者 / 验证者 PoS 里出块的人,对应 PoW 的矿工
币龄 coin age 币数乘以持有天数,一种挑人的权重

一个类比:两种抽签办法

一个班要轮流选值日组长。第一种办法是比赛摇骰子:谁先摇出一个够小的点数谁当,摇得越多越容易中,于是有人雇了一屋子人帮他摇。这就是 PoW,骰子是哈希,雇人摇是买矿机、付电费。

第二种办法是按押金抽签:每人往班费里押一笔钱,押得多的签就多。不用雇人,也不费力气。这就是 PoS。

按押金抽签有个毛病。当组长有工钱,工钱又加进押金,下次签更多,越当越当。于是班里补了几条规矩:押金放满 30 天才算数,当过一次的那笔押金清零重攒,放得再久也只算到 90 天。这就是币龄选择。

类比在哪里失效:

  • 骰子点数人人看得见,哈希是先算才知道,没有捷径,只能一个个试。
  • 押金在班费里可以退,真实协议里押上的币作恶会被没收,这一条下一页才讲。
  • 30 天、90 天是课件举的历史方案参数,不是所有 PoS 都这么定。

从零讲起

1. PoW 的合法条件

它解决什么问题

谁都能往网络里广播一个块,大家要有一条人人能验证的规则,判定这个块算不算数。PoW 的规则是:块头的哈希要足够小。算出这样的哈希很难,验证它只要算一次。难,就让出块有了门槛;好验证,就让所有人都能当裁判。

从哪来(补充)

用「算一道难题」当门槛的想法比比特币早得多。1993 年 Cynthia Dwork 和 Moni Naor 提出,让发邮件的人先付出一点计算代价,用来挡垃圾邮件和拒绝服务攻击。1997 年 Adam Back 提出 Hashcash,用的就是「找一个哈希够小的输入」这种题。「proof of work」这个名字是 Markus Jakobsson 和 Ari Juels 在 1999 年的论文里正式提出的。

出处:Wikipedia: Proof of work

直觉

哈希函数的输出可以看成一个很大的随机数。输入改一点,输出就跳到完全不同的地方,没法预判。想要一个落在很小区间里的输出,只能一个个试。

Target 就是那个区间的上沿。Target 越小,合格的区间越窄,平均要试的次数越多,这就是「难度」。

一步一步看

目标:跟着矿工试一遍 Nonce,看出块为什么要反复算,而别人验证只要算一次。

  1. 矿工把区块头的六个字段摆好:Version、Target、Prev Hash、Merkle Root、Timestamp、Nonce。除了 Nonce,其余五个先固定。

    PoW 出块循环示意图:左边一列六个区块头字段 Version、Target、Prev Hash、Merkle Root、Timestamp、Nonce,其中 Nonce 1559164 用青绿框标出是唯一在变的字段;字段送进 SHA-256 做两次,再判断是否小于等于 Target,是就广播,否就让 nonce 加一再算一遍

  2. 把整个区块头送进 SHA-256,算两次,得到一个 256 位的数 H。

  3. 拿 H 和 Target 比。H ≤ Target 就挖到了,把块广播出去。

  4. 不合格,就把 Nonce 加一,回到第 2 步再算。

    一条从 0 到 2 的 256 次方减 1 的数轴,左端阴影是 0 到 Target 的合法区间;第 1 次和第 2 次算出的哈希落在右边太大的地方,换 nonce 重试,第 3 次落进合法区间,用青绿圈标出

  5. 别人收到块,只要把区块头哈希一次,和 Target 比一下,就能确认它合格。

怎么算

比特币的条件写成:

SHA256(SHA256(header)) ≤ Target

意思是:把区块头连做两次 SHA-256,得到的数不超过当前的目标阈值,这个块就合法。Target 由难度调整算法定期改,所以「要几个前导零」不是一个固定数。

如果非要用前导零来说,前 N 个字节全为 0,等价于 H ≤ 2^(256−8N) − 1。推导是这样的:256 位里最高的 8N 位都是 0,剩下 256−8N 位随便取,最大就是这些位全为 1,也就是 2^(256−8N) − 1。只有 Target 恰好等于这种值时,两种写法才一致;平时 Target 落在两个这种边界之间,只能写成和 Target 比。

还有一个细节:nonce 只有 4 字节,试完了怎么办?矿工可以改 coinbase 交易里的 extraNonce,Merkle Root 就跟着变,整个区块头换了一批新的可试空间。

常见误解

以为合法条件就是「前若干个字节全是 0」

前导零只是 H 很小的一个表现。协议比的是 H 和 Target 的大小,Target 随难度变。把零的个数写死,难度一调就错了。

以为挖矿只能改 nonce

nonce 是直接拿来试的字段,但它只有 4 字节,很快会试穿。改 coinbase 里的 extraNonce 会换掉 Merkle Root,等于又多出一整批可以试的区块头。

试一下

前 4 个字节全为 0 的哈希,对应 H 不超过多少?用 2 的幂写出来。

4 个字节是 32 位,剩下 256 − 32 = 224 位可以随便取,最大是这 224 位全为 1,所以 H ≤ 2^224 − 1。

流程图里 Prev Hash 开头有一串 0,Merkle Root 没有。为什么?

Prev Hash 是前一个块的区块头哈希,前一个块自己也得过 PoW,所以它很小,开头是一串 0。Merkle Root 是交易列表的哈希,协议不要求它满足任何条件,所以长什么样都行。

2. 换成押币:PoS 怎么挑出块人

它解决什么问题

PoW 的门槛靠电费撑着,能耗巨大。PoS 想换一种稀缺资源:押在协议里的币。押得越多,被选中出块的机会越大。这样不用烧电,一台普通电脑加稳定网络就能参与。

但换完资源立刻冒出一个问题:拿什么规则从押币的人里挑下一个出块人?最简单的「按余额挑」会让富人越来越富。

直觉

PoW 里算力最大的矿工也只是更常出块,他的算力不会因为出块自动变多,想变多得再买机器。

纯按余额挑就不一样了。出块的奖励直接加到余额上,余额多了,下一轮被选中的概率更高,再拿奖励,再变多。这个圈会自己转起来。

一步一步看

目标:看只按余额挑出块人怎样转成富者越富的圈,再看课件给的两种打断办法。

  1. 设想只按余额挑人,余额越多,被选中的概率越高。

  2. 某人被选中出块,拿到出块奖励。

  3. 奖励加进余额,他的余额变得更多。

  4. 下一轮他被选中的概率更高,回到第 2 步。

    只按余额选出块人的正反馈环:余额多到被选中的概率高,到出块拿到奖励,到余额更多,再回到余额多;回到起点那一段虚线用青绿叉号标出,写着币龄方案切在这一环

  5. 课件给了两种打断这个圈的办法,下面的表并排对比:

办法 怎么挑 留下的问题
随机数选择 算一个哈希当随机数,再按质押规模加权,挑最低的那个 质押是公开的,大家都能提前算出下一个出块人
币龄选择 按「币数 × 天数」加权,再加三条限制 参数是课件的教学版,不是所有 PoS 通用

怎么判断

拿到一种挑人规则,问两件事。

第一,出块之后,这个人下一轮的机会会不会因此变大?会,就有富者恒富的正反馈。

第二,下一个出块人能不能被提前算出来?能,攻击者就可以定向攻击那个人,让他那一轮出不了块。随机数选择正好卡在这一条上,所以以太坊后来用 RANDAO 把能提前知道的时间压得很短。

术语也顺带分清:PoS 里的块是 forged(锻造)或 minted(铸造)出来的,出块人叫 forger 或 validator;mine 和 miner 是 PoW 的说法。

常见误解

以为 PoS 只是省电,别的都和 PoW 一样

能耗对 PoW 是安全的来源:攻击要付真实的物理成本。PoS 把这份成本换成了链内的质押资产。换完之后挑人规则、分叉时的激励都得重新设计,所以 PoS 多出了富者恒富和下一页的 Nothing at Stake 两个问题。

以为「出块人能被提前预测」是好事

能预测意味着攻击者知道下一个是谁,可以集中去打他,让那一轮空掉。连着这么干,链就被拖慢了。

试一下

甲、乙两人质押一样多,规则是纯按余额挑。甲先被选中三次。之后两人被选中的概率还一样吗?

不一样了。甲出块三次拿了三份奖励,余额比乙多,下一轮被选中的概率比乙高。差距只会越拉越大,这就是正反馈。

3. 币龄选择

它解决什么问题

币龄选择是课件给的第二种修正。它让「币少但放得久」的人也能和「币多但刚到手」的人比,并且让刚出过块的那笔币暂时退场,把富者恒富那个圈剪断。

从哪来(补充)

币龄这一套来自 Peercoin。它由 Sunny King(化名)和 Scott Nadal 设计,白皮书 2012 年发布,同年 8 月 12 日首次上线,是第一个用 PoS 的加密货币。

出处:Wikipedia: Peercoin

直觉

币龄 = 币数 × 持有天数,单位是「币·天」。等待也能攒权重,小户靠时间追大户。

再加三条限制。刚到手的币不算,免得流水大的账户占便宜;出过块的币清零,免得同一笔币连着赢;放太久也封顶,免得巨鲸放几年攒出谁也撼不动的权重。

一步一步看

目标:用 A、B、C 三人算一轮币龄,看三条限制怎样让刚出块的赢家暂时退场。

三个人:A 质押 50 枚、放了 40 天;B 质押 100 枚、放了 20 天;C 质押 20 枚、放了 120 天。

  1. 先看天数。B 未满 30 天,直接出局;A、C 可以参选。

    币龄第 1 步:三条灰色长条表示持有天数,A 50 枚 40 天、B 100 枚 20 天、C 20 枚 120 天;30 天那条竖线用青绿标出,B 的虚线长条没过线,写着未满 30 天不参选

  2. 再算币龄。A 是 50 × 40 = 2000 币·天。C 放了 120 天,超过 90 天的部分不再加权,按 90 天算,20 × 90 = 1800 币·天。

    币龄第 2 步:90 天封顶那条竖线用青绿标出,C 超过 90 天的部分画成虚线不算;右侧写 A 50 乘 40 等于 2000 币·天,C 20 乘 90 等于 1800 币·天,B 仍未满 30 天

  3. 假设这一轮 A 出了块。A 用来出块的那笔币,币龄归零,要从头攒。

    币龄第 3 步:A 的长条变成青绿虚线框,旁边写着归零、币龄 0 要重新攒;C 仍是 20 乘 90 等于 1800 币·天,B 仍未满 30 天不参选

  4. 下一轮 A 那笔币已经没有币龄,C 的权重排到了前面。赢家赢完就被清零,圈剪断了。

怎么算

PoW 的条件是 Hash(block_header) < Target。币龄选择把右边乘上币龄:

Hash(block_header) < Target × CoinAge

意思是:每个人的「合格线」被自己的币龄放大了。币龄翻倍,合格线翻倍,能落进合格区间的哈希也翻倍,命中概率就跟着翻倍。所以命中概率正比于币龄。

为什么这里不用拼算力?候选输入和可用的时间戳都被协议限住了,没有一个 nonce 能让人随便枚举。一个人可以有好几笔合资格的质押,但不能靠多买机器多试。

还有一处要知道:公式里写 block_header 是为了和 PoW 那行对仗。Peercoin 实际哈希的是 kernel,里面不含交易列表,免得出块人反复重排交易来多试几次。

常见误解

以为币龄只要算乘积比大小就行

先过 30 天门槛,再算乘积,再看 90 天封顶。一个人币很多、乘积很大,只要没满 30 天就不能参选,乘积再大也不参与比较。

以为出块后这个人所有的质押都清零

清零的只是刚用来出块的那笔币。他另外几笔合资格的质押照样有币龄。

试一下

D 质押 30 枚、放了 100 天;E 质押 40 枚、放了 70 天。谁能参选?各自币龄多少?

两人都满 30 天,都能参选。D 超过 90 天,按 90 天算,30 × 90 = 2700 币·天。E 没到封顶,40 × 70 = 2800 币·天。E 的合格线略宽。

把它们串起来

出块权总要靠一种稀缺资源来分。PoW 用的是链外的算力:块头哈希要不超过 Target,只能一个个试 nonce,验证却只要算一次。安全建立在物理成本上,代价是能耗。

PoS 把资源换成链内的质押。省下了电,却要重新回答「挑谁」。只按余额挑,奖励会回流成更大的机会,形成富者恒富的正反馈。

课件给了两种修补。随机数选择按质押加权抽一个随机数,但质押公开,出块人能被提前算出来。币龄选择用币数乘天数加权,再加 30 天起算、出块归零、90 天封顶三条限制;条件写成 Hash(block_header) < Target × CoinAge,命中概率正比于币龄。

挑人的问题到这里补上了。换资源还留下第二个更大的洞:分叉时,同一笔币可以在两条链上各签一次。下一页从这里接着讲。

课件里的坑

  • [课件有误] p.7 固定写「最高 20 字节全 0」;这等价于 H ≤ 2⁹⁶ − 1,不能替代随难度变化的 Target,也不能另背一个固定零数量(p.7)
  • [适用条件] p.6 从奖励递减推出攻击风险降低,缺少条件;也不能反向断言攻击必然更便宜,币价、手续费和算力供给都会影响结果(p.6)
  • [适用条件] p.9 的「PoS 更去中心化」缺少指标;需比较实际控制分布,不能凭机制名字判断(p.9)
  • [适用条件] p.7 的 66.7% 未说明安全模型,不能直接归因于自私挖矿论文;经济收益门槛与多数算力安全分析并非同一问题(p.7)
  • [读图提醒] p.8 流程图只画了一次 SHA 256,真实比特币对区块头做两次;图上的 Nonce 1,559,164 是示意值(p.8)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写 PoW 条件和币龄公式两行;再在纸上画一次富者恒富的环,标出币龄方案剪在哪;然后做课件例题和变式题;最后回查一个易错点:币龄先看 30 天门槛,再算乘积。

必背

  1. 比特币 PoW 条件是 SHA256(SHA256(header)) ≤ Target;Target 随难度调整,不固定前导零字节数
  2. PoS 的动机是 PoW 的能耗;更准确的说法是安全成本从外部的电力换成了链内的质押资产
  3. PoS 术语:块是 forged / minted,出块人叫 forger / validator;mine / miner 是 PoW 的说法
  4. 只按余额选出块人会富者恒富:出块奖励加到余额上,下一轮更容易再中,形成正反馈;课件给的修正是随机数选择和币龄选择
  5. 课件简化币龄模型:币数 × 天数,满 30 天起参与、用来出块的币龄归零、90 天封顶;不是所有 PoS 的通用参数
  6. 币龄选择条件 Hash(block_header) < Target × CoinAge:币龄越大有效阈值越大,命中概率正比于币龄

课件例题

例 1(课件 p.8):读 PoW 出块流程图

图里区块头含 Version、Target、Prev Hash 0000008bb8…、Merkle Root、Timestamp 1507292970、Nonce 1559164,经 SHA256 后分成「合法哈希」和「不合法,Nonce 加一再算」两路。问:哪个字段在循环里变?循环何时停?

PoW 出块流程图:左边一列六个区块头字段,Version 和 Target 各 4 bytes,Prev Hash 0000008bb8…,Merkle Root 06c056519733,Timestamp 1507292970,Nonce 1559164,只有 Nonce 一格是蓝色、其余是红色;字段经黄色箭头送进 SHA 256,绿色箭头通向 A Valid Hash,红色回路箭头指回 Nonce,旁边红框写 Invalid Hash, Increment the Nonce, Repeat SHA 256
图片来源:COMP5567 Lecture_5-PoW-PoS.pdf, p.8
提示

看图上哪一格的颜色和其他格不一样,再看红色回路的箭头指回哪里。

解答

只有 Nonce 在变,其余字段固定。哈希值 ≤ Target 时停下,得到合法块;否则 Nonce 加一重算。

例 2(课件 p.13–14):币龄选择的公式

PoW 的条件是 Hash(header) < Target,课件给的币龄版本是什么?币龄怎么算,有哪几条附加规则?

提示

币龄是一个乘数,想想它乘在不等式的哪一边。附加规则有三条,分别管起点、出块后和上限。

解答

条件变为 Hash(header) < Target × CoinAge,币龄 = 币数 × 持有天数,币龄越大通过区间越宽。附加规则:满 30 天才参选,出块后用到的币龄归零,概率在 90 天封顶。

例 5(课件 p.34,Take-home Exercise-1):PoW 与 PoS 各自的优缺点

提示

先定一个比较轴:两者都在决定用哪种稀缺资源分配出块权。再从安全来源、能耗、集中化、最终性四个方面各写一句。

解答

先给统一比较轴:两者都在决定用哪种稀缺资源分配出块权,PoW 用链外的算力和电,PoS 用链内的质押。PoW 优点是安全靠物理成本、选链可独立验证;缺点是能耗大、算力集中到矿池、最终性只是概率性的。PoS 优点是能耗低、作恶可被罚没、有经济最终性;缺点是要靠罚没修 Nothing at Stake、新节点需信任近期检查点、质押容易集中。阅卷看三点:比较轴、Nothing at Stake 及其解法、两种最终性的区别。

课件例 3、例 4(p.17–21,分叉与期望收益)见下一页 L05a-2。

完整例题

题面:按课件的简化币龄模型,四个质押者:P 有 60 枚、放了 50 天;Q 有 300 枚、放了 25 天;R 有 25 枚、放了 150 天;S 有 40 枚、放了 90 天。问:谁能参选?各自币龄是多少?如果 P 这一轮出了块,下一轮的排序怎么变?

约定:币龄 = 币数 × 天数;满 30 天才参选;超过 90 天按 90 天算;出块后用到的那笔币币龄归零。

解法:

  1. 先过门槛。Q 只放了 25 天,未满 30 天,出局。P、R、S 都满 30 天。
  2. 算 P:60 × 50 = 3000 币·天。
  3. 算 R:150 天超过 90 天,按 90 算,25 × 90 = 2250 币·天。
  4. 算 S:正好 90 天,不超过封顶,40 × 90 = 3600 币·天。
  5. 排序:S 3600 > P 3000 > R 2250。按公式 Hash < Target × CoinAge,S 的合格线最宽,命中概率最高,但不保证一定是 S。
  6. P 出块后,那笔 60 枚的币龄归零。下一轮 P 掉到最后,S、R 排在前面。

要点:顺序是门槛、乘积、封顶、出块后归零。Q 的币最多,乘积 300 × 25 = 7500 也最大,但没过门槛,乘积不参与比较。

答题格式:写一张四列表「质押者 / 是否满 30 天 / 计入天数 / 币龄」,最后一句说明出块后哪一笔清零。

变式题(先自己做)

(1) 改编自课件 p.13–14:甲质押 100 枚、持有 60 天,乙质押 200 枚、持有 30 天,丙质押 400 枚、持有 10 天。谁能参选?能参选的人里谁的通过区间更宽?甲出块之后会怎样? (2) 改编自课件 p.7:前 3 个字节全为 0 的哈希,对应 H 不超过多少?这种写法什么时候和「H ≤ Target」等价? (3) 自编情境:一种 PoS 方案按「余额 × 一个公开的随机数」挑人,这个随机数在一个月前就公布。指出它的安全问题。

提示

(1) 先看 30 天门槛筛掉谁,再对剩下的人算币数 × 天数,最后想三条规则里哪一条在出块后生效。(2) 3 个字节是多少位?剩下几位随便取?(3) 想想攻击者提前知道下一个出块人能干什么。

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

判分点:① (1) 先写门槛再写乘积,不能拿丙的乘积去比;② (2) 推导要写出剩余位数;③ (3) 要点名「可预测」和「定向攻击」。

(1) 丙只持有 10 天,未满 30 天,不能参选,不能拿乘积 4000 去比。甲、乙都是 6000 币·天,通过区间一样宽。甲出块后,用来出块的那部分币龄归零,这条规则掐断富者恒富的正反馈。

(2) 3 个字节是 24 位,剩下 256 − 24 = 232 位,所以 H ≤ 2^232 − 1。只有 Target 恰好等于 2^232 − 1 时两种写法才等价,平时 Target 不在这种边界上。

(3) 随机数早就公开,加上余额也公开,任何人都能提前一个月算出每一轮的出块人。攻击者可以定向攻击即将出块的人,让那一轮空掉;连续这么做能拖慢整条链。这正是以太坊改用 RANDAO、压短可预测窗口的原因。

闪卡自测

1. True or False: Bitcoin always requires the first 20 hash bytes to be zero.
中文:比特币总要求前 20 字节为零。

False. A valid header hash must be at most the current target. 条件是 SHA256(SHA256(header)) ≤ Target,前导零数量不固定。20 字节全零对应 H ≤ 2⁹⁶ − 1;at most 表示 ≤(p.7、p.8)。

2. 币龄选择的三条规则是什么?哪一条专门掐断富者恒富?

满 30 天的币才参与竞争、签完一个块币龄归零、概率在 90 天封顶。归零那条掐断正反馈:赢家赢完就被清零,没法用刚拿到的优势接着赢(p.13)。

3. 如果 PoS 只按账户余额选出块人,会出现什么问题?

最富的人选择多押,就会获得永久优势。出块拿到奖励,余额更多,下一轮被选中的概率更高,形成正反馈。课件给的两种修正是随机数选择和币龄选择(p.11–12)。

4. 写出币龄选择的哈希条件。它为什么不需要大量算力?

Hash(block_header) < Target × CoinAge,币龄越大通过区间越宽。该方案限制候选输入和时间戳,不能像 PoW 那样任意枚举 nonce,所以拼算力没用。实际被哈希的是不含交易列表的 kernel(p.13–14)。

5. PoS 里出块叫什么?出块人叫什么?

块是 forged(锻造)或 minted(铸造)出来的,出块人叫 forger 或 validator。mine、miner 是 PoW 的说法(p.10)。

6. 随机数选择留下了什么安全问题?以太坊怎么应对?

质押是公开的,下一个出块人能被提前算出来,攻击者可以定向攻击他。以太坊用 RANDAO 让出块人只在很短的提前量内可知(p.12、p.25)。

7. 「PoS 解决了 PoW 的能耗问题」这句话哪里需要补一句?

能耗是 PoW 安全的来源,攻击要付真实的物理成本。PoS 把安全成本从外部的电力换成了内部的质押资产,各有代价(p.10、p.15)。

下一讲

挑人的规则补好了,分叉时又出问题:同一笔币在两条链上各签一次不花钱。见 L05a-2。

下一讲 →
L05a-2 L05a-2 Nothing at Stake 与罚没:分叉时为什么要两边都押

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