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

L02b-2 RANDAO 与委员会:谁出块、谁投票,抽签怎么防作弊

先补异或,再看 RANDAO 怎么把每个提议者的一份随机性累加起来、为什么要隔两个 epoch 才用;然后看洗牌怎么分委员会,投票的 2/3 为什么按押金算,BLS 聚合解决了什么。

一句话版

每个 slot 由谁出块、谁投票,靠一个大家一起凑出来的随机数决定。凑的办法是异或,所以只要有一个人老实,结果就没人能控制。投票按押金算票数,过 2/3 才算通过。

上一页 L02b-1 讲了验证者怎么上岗,这一页讲上岗之后怎么排班。

先认识这几个词

词 全称 / 读法 一句人话
XOR / ⊕ 异或,读「异或」 两位相同得 0,不同得 1
RANDAO RANDom number DAO 链上逐块累加出来的公共随机数
randao_reveal 随机贡献 提议者在区块里交的那一份随机性
committee 委员会 被派到某个 slot 去投票的一组验证者
shuffle 洗牌 用随机数把验证者打乱、分组
attestation 证明 / 见证 验证者投的一票
BLS 三位作者姓氏缩写 一种能把很多签名合成一个的签名方案

一个类比:一群人一起摇骰子

公司要抽签排班,谁都不信任谁。办法是每人往一个黑箱里扔一枚自己的骰子结果,箱子把所有结果混在一起,得出最终签号。只要有一个人扔的是真骰子,最终结果就没人能预先算出来。

排班表定下来后,大家被分成若干小组,每组负责审一个时段。审的时候按每个人交的押金算票,押金多的人一票更重。

类比在哪里失效:

  1. 现实里的人可以扔假骰子;RANDAO 的「骰子」是对 epoch 号的签名,每人每个 epoch 只有一个合法值,没法换着扔。
  2. 现实里最后一个扔的人只能扔一次;在 RANDAO 里,最后一个人还可以选择干脆不扔,在两个结果里挑一个。
  3. 排班表不是马上生效,要等两个 epoch 之后才用。

从零讲起

1. 先补一块:异或 XOR(补充)

它解决什么问题

RANDAO 把很多人的随机数合成一个,用的就是异或。异或有一个关键性质:拿一个真随机的数去异或任何数,结果还是真随机。看懂这一点,才能理解「一个诚实的人就够了」。

直觉

异或像一排开关。另一个数里是 1 的位置,就把这一位的开关拨一下;是 0 的位置,就不动。你不知道别人会拨哪几个,就猜不出最后的开关状态。

一步一步看

目标:按位算一遍 1010 ⊕ 0110,看异或的规则,以及再异或一次变回原值、先算哪两个都一样这两条性质。

  1. 把两个数写成二进制,按位对齐。
  2. 每一位单独比:两位相同得 0,不同得 1。
  3. 例子:1010 ⊕ 0110 = 1100。
  4. 再异或一次同一个数,会变回原来的值:1100 ⊕ 0110 = 1010。
  5. 顺序无所谓:A ⊕ B ⊕ C 不管先算哪两个,结果都一样。

异或按位计算示意:上下两行二进制 1010 与 0110 逐位对齐,相同的位得 0,不同的位用青绿高亮得 1,最下一行结果是 1100

A B A ⊕ B
0 0 0
0 1 1
1 0 1
1 1 0

怎么判断

判断一串异或的结果能不能被人控制:只要其中有一项是别人事先不知道、也没法挑的随机数,整串结果就没人能控制。所有项都被同一个人掌握时,才能控制。

常见误解

以为异或和加法一样会进位

异或逐位独立计算,没有进位。一位的结果只看这一位上的两个数。

试一下

计算 0011 ⊕ 0101。

逐位比:0 和 0 得 0,0 和 1 得 1,1 和 0 得 1,1 和 1 得 0。结果 0011 ⊕ 0101 = 0110。

2. RANDAO:一块一块累加的随机数

它解决什么问题

选提议者和分委员会都要随机数。这个数如果由某个人生成,他就能给自己挑一个好位置。RANDAO 让每个出块的人都往里混一份,没有任何一方能单独决定结果。

直觉

像一锅大家轮流加料的汤。每个人加一勺自己的调料,最后的味道由所有人共同决定。只要有一个人加的东西别人事先不知道,最后的味道就没人能提前调好。

一步一步看

目标:看每个提议者的 reveal 怎样逐块哈希后异或进 RANDAO,为什么没有谁能单独定下结果。

  1. 链上维护一个 RANDAO 值。每个区块里,提议者交一个 randao_reveal。

  2. randao_reveal 是提议者用签名密钥对当前 epoch 号做的 BLS 签名。epoch 号是确定的,BLS 签名也是确定的,所以每人每个 epoch 只有一个合法值。

    RANDAO 累加第 1 步:初始值 R₀ 与第一个提议者的 reveal 哈希异或,青绿高亮得到新值 R₁

  3. 混入时先对 reveal 取哈希,再和旧值异或:R_n = Hash(reveal_n) ⊕ R_{n−1}。

    RANDAO 累加第 2 步:R₁ 再与下一个提议者的 reveal 哈希异或,青绿高亮得到 R₂,前一步的结果保留在左侧

  4. 一个 epoch 的 32 个 slot 依次混完,得到这个 epoch 的 RANDAO 值。

  5. 这个值不马上用,留到两个 epoch 之后,用来选那时的提议者和委员会。

    RANDAO 累加第 3 步:R₂ 再异或一次得到 R₃,青绿箭头指向右侧标注,说明 epoch N 累积的结果在 epoch N+2 才被用来选提议者和委员会

怎么算

R_n = r_n ⊕ R_{n−1},其中 r_n = Hash(对 epoch 号的签名)。

意思是:新随机数 = 这个区块的贡献 异或 上一个随机数。签 epoch 号保证贡献没法挑,取哈希把签名摊平成均匀随机,异或保证一个诚实贡献者就能让结果随机。

常见误解

以为 RANDAO 完全无法操纵

还剩一个口子:轮到出块的人可以选择不出块,少混一项,在「混」和「不混」两个结果之间挑一个。代价是丢掉这次的出块奖励。

以为这个 epoch 算出的随机数当场就用

要等到 epoch N+2 才用。当场就用的话,最后一个贡献者能先算出结果对自己有没有利,再决定出不出块。

试一下

当前 RANDAO 值是 1001,下一个提议者 reveal 的哈希是 0110,新值是多少?

1001 ⊕ 0110 = 1111。

3. 洗牌与委员会:把验证者分组

它解决什么问题

让全网每个验证者每 12 秒都投一次票,网络扛不住。协议把一个 epoch 里的验证者切成若干小组,每组只管一个 slot,每人每个 epoch 只投一次。

直觉

像考场分配座位。考生名单先用一个公开的随机数打乱,再按顺序切成若干考场,每人只进一个考场。谁进哪个考场,事先谁也挑不了。

一步一步看

目标:看 RANDAO 值怎样把验证者名单洗牌、切成每个 slot 一个委员会,选提议者时又多了哪个输入。

  1. 拿到 RANDAO 值和活跃验证者名单。
  2. 用洗牌算法把名单打乱。
  3. 打乱后切成若干组,每个 slot 分到一个委员会,每个委员会至少 128 人。
  4. 一个 epoch 内,每个活跃验证者恰好属于一个委员会,各委员会互不相交。
  5. 选提议者时还要再加一个输入:余额。押得多,当选概率高。

洗牌分组示意:一排验证者经过洗牌被打乱,再切成若干委员会,每个委员会对应一个 slot,青绿标注写着每组至少 128 人、组与组互不相交

用途 输入
选提议者 RANDAO 值 + 活跃验证者 + Balance + 洗牌算法
分配委员会 RANDAO 值 + 活跃验证者 + 洗牌算法

怎么判断

问「stake 体现在哪一步」,答选提议者:这一步看 Balance。分委员会不看余额,因为委员会只是投票分组,不该有偏向。

常见误解

以为一个验证者在一个 epoch 里可以进好几个委员会

每人每个 epoch 只在一个委员会里,委员会之间不重叠。这保证了每人每个 epoch 只投一次票。

试一下

一个 epoch 有 32 个 slot,每个 slot 一个 128 人的委员会,这个 epoch 至少要多少个验证者?

32 × 128 = 4,096 个。

4. 投票:按押金算的 2/3 与 BLS 聚合

它解决什么问题

提议者出了块,要有人确认它。委员会成员投票,票按押金加权,凑够 2/3 区块才被接受。几十万个验证者各签一票,签名数据会多得没法处理,所以还要能把票合并起来验证。

从哪来(补充)

BLS 签名以三位作者命名:Dan Boneh、Ben Lynn、Hovav Shacham,方案 2004 年发表在 Journal of Cryptology 上。它的特点是多个签名可以聚合成一个短签名,一次验证。

出处:Wikipedia: BLS digital signature

直觉

股东大会表决按股份算票,一个大股东可以抵好多个小股东。统计时不用一张张核对签名,只要核对一张汇总表,这张表能证明所有投同样意见的人都签过字。

一步一步看

目标:跟着一个区块从打包到被接受,看委员会投票怎样按押金加权凑够 2/3,聚合者又怎样把票合并。

  1. 提议者从 mempool 里挑交易打包成块。
  2. 委员会成员各自签一票 attestation。一票里同时表态三件事:当前区块、本 epoch 首块(target)、上个 epoch 首块(source)。
  3. 委员会里选出一部分人当聚合者,把内容相同的票合成一张聚合票,再广播出去。
  4. 计票时按存款额加权。赞成方的押金总额达到全体押金的 2/3,区块才被接受。

按押金计票示意:A、B、C 三人各押 32 ETH 投赞成,D 押 160 ETH 投反对;按人数赞成占 75%,按押金赞成只占 37.5%,后者用青绿高亮,区块没有通过

怎么判断

问「多少人赞成算通过」,先把每个人的押金加起来,再看赞成方押金占全体押金是否达到 2/3。人数过 2/3 不等于通过。

常见误解

以为不同内容的票也能聚合成一张

BLS 聚合要求签的是同一条消息。委员会内部意见不一时,会出现几张内容不同的聚合票。

试一下

委员会四人押金分别是 32、32、32、64 ETH,前三人赞成,够 2/3 吗?

总押金 32 + 32 + 32 + 64 = 160 ETH,赞成方 96 ETH,96 ÷ 160 = 60%,不到 2/3,不通过。

把它们串起来

这一页回答的是「谁上场」。

每个提议者交一份对 epoch 号的签名,取哈希后异或进 RANDAO。一个 epoch 混完的值,两个 epoch 之后拿来洗牌:带上余额选提议者,不带余额分委员会。委员会成员对区块投票,票按押金加权,过 2/3 才算数;BLS 把内容相同的票压成一张,几十万人投票才跑得动。安全靠抽样:委员会是随机抽的,攻击者在全局只占三分之一时,很难在某个小组里凑到三分之二。

投票不花钱,验证者为什么不两边都投?下一页讲罚没。

课件里的坑

  • [课件有误] p.94 图上 slot 标签写成 “Slot0, Slot1, Slot3, …”,第三个应为 Slot2(p.94)
  • [补充核验] p.93 写 randao_reveal = Hash(Signature)。按协议,randao_reveal 本身是对 epoch 签名根的 BLS 签名,更新 RANDAO 时才对它取哈希并异或。两种写法算出的结果一样,只是「reveal」指的东西不同(p.93)
  • [补充核验] p.91 说每个委员会「至少 128 人」。128 是委员会的目标规模,能不能达到取决于活跃验证者够不够多(p.91)
  • [读图提醒] p.103 把 source 写成上个 epoch 的首块,这是简化说法。协议里 source 是最近一次被 justify 的检查点,可能往回指好几个 epoch,下一页的 surround vote 会用到这一点(p.103)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先写出 RANDAO 的累加公式,用 4 位二进制自己走两步;再说清楚为什么要等到 N+2;最后用一个押金不均的委员会算一次 2/3,确认自己不会按人数算。

必背

  1. R_n = r_n ⊕ R_{n−1};randao_reveal 是对 epoch number 的 BLS 签名,混入时先取哈希再异或
  2. 异或累加:只要有一个诚实贡献者,结果就随机;残余攻击是提议者拒绝出块(二选一)
  3. epoch N 累积的 RANDAO 用于 epoch N+2,两个 epoch 的延迟是防操纵设计
  4. 每个 slot 的委员会至少 128 人(目标规模);一个 epoch 内每个验证者恰好属于一个委员会,委员会互不相交
  5. 洗牌两用途:选提议者要看 Balance,分配委员会不看 Balance
  6. attestation 按存款额加权,需 2/3 多数,按存款总额算不按人数算;BLS 聚合让几十万验证者的票能合并验证
  7. 安全论证:全网至少 16,384 个验证者、委员会 128 人,攻击者占全局 1/3 也极难在随机委员会里拿到 2/3

课件例题

例 1(课件 p.94):走一遍一个 epoch 的 RANDAO 累加:见下方完整例题。

例 2(课件 p.102):为什么全网至少要 16,384 个验证者

题面:课件说即使攻击者控制全部 16,384 个验证者中的三分之一,也极不可能在随机选出的 128 人委员会里控制超过三分之二。把这个论证的支点说清楚。

提示

从三个方面想:委员会是怎么选出来的;攻击者全局占比和小组内占比差多少;128 这个样本量起什么作用。

解答
  1. 委员会是随机抽样的,靠 RANDAO 加洗牌,攻击者不能挑组。
  2. 攻击者在全局只占 1/3,要在某个具体小组里凑到 2/3,属于极端的抽样偏差。
  3. 样本量 128 足够大,这种偏差的概率低到可以忽略。
  4. 三个数要一起记:16,384(全网下限)、128(委员会规模)、1/3 对 2/3。

例 3(课件 p.101):一个委员会多数人赞成,区块一定被接受吗

题面:一个委员会有 150 人,105 人投了赞成。区块一定被接受吗?

提示

先确定 2/3 是按什么算的:人数,还是押金。

解答
  1. 105 ÷ 150 = 70%,按人数超过了 2/3。
  2. 课件规定 2/3 按存款总额算:赞成者的押金总额要达到全体押金的 2/3。
  3. 题目没给押金,所以不一定。这是 PoS 和「一人一票」的根本区别。

完整例题

题面(改编自课件 p.93–94,数字自编,用 4 位二进制代替真实的 32 字节):epoch N 开始时 RANDAO 值为 1100。前三个 slot 的提议者 reveal 取哈希后分别是 1010、0111、0001。(1) 依次累加,写出每一步的值。(2) 如果第三个提议者拒绝出块,结果变成什么?(3) 累加出来的值用在哪个 epoch?

  1. 写公式:R_n = Hash(reveal_n) ⊕ R_{n−1},逐位异或,相同得 0,不同得 1。
  2. 第一步:1100 ⊕ 1010 = 0110。
  3. 第二步:0110 ⊕ 0111 = 0001。
  4. 第三步:0001 ⊕ 0001 = 0000。
  5. 第三个提议者不出块,就少异或这一项,结果停在 0001。他可以在 0000 和 0001 之间挑一个,这是 RANDAO 唯一的残余操纵空间,代价是丢掉出块奖励。
  6. 真实情况下一个 epoch 要混满 32 个 slot,混完的值用于 epoch N+2 的提议者和委员会选择。
  7. 检查:任何一项是真随机的,最终值就随机。三个人里只要有一个老实,其他两人联手也没法预先定出结果。

变式题(先自己做)

自编情境:一个 5 人委员会,押金分别是 A 32 ETH、B 32 ETH、C 32 ETH、D 32 ETH、E 192 ETH。(1) A、B、C、D 投赞成,E 反对,区块通过吗?(2) 只有 E 和 A 投赞成呢?(3) 两种情况按人数算分别是多少?

提示

先算全体押金总额,再算赞成方押金,看比例是否达到 2/3。人数比例单独算,只用来对照。

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

判分点:① 写出全体押金总额;② 每种情况算出赞成方押金占比并判断是否过 2/3;③ 指出按人数和按押金结论不同。

全体押金:32 × 4 + 192 = 320 ETH,2/3 约为 213.3 ETH。

(1) 赞成方 32 × 4 = 128 ETH,128 ÷ 320 = 40%,不通过。

(2) 赞成方 192 + 32 = 224 ETH,224 ÷ 320 = 70%,通过。

(3) 按人数,第一种 4/5 = 80%,第二种 2/5 = 40%,结论正好和按押金相反。

闪卡自测

1. randao_reveal 为什么要对 epoch number 签名?允许自选签名内容会怎样?

epoch 号是确定的,BLS 签名又是确定性的,同一个 epoch 里一个验证者只能产生唯一一个合法签名。允许自选内容,他就能试很多个签名,挑一个对自己有利的随机数(p.93)。

2. epoch N 收集的随机数为什么要等到 epoch N+2 才用?

给网络留出同步时间,同时让最后一个贡献者也无法即时看到这个随机数会给自己带来什么。当场就用,最后一个贡献者就能算准结果再决定出不出块(p.94)。

3. 洗牌在「选提议者」和「分配委员会」两个用途下,输入有什么不同?

唯一的差别是 Balance:选提议者要看余额,押得多当选概率高;分配委员会不看余额,纯随机均分(p.95、p.96)。

4. 一次 attestation 要表态哪几件事?

当前区块、本 epoch 首块(target)、上个 epoch 首块(source),外加验证者签名。source 和 target 这一对是后面罚没规则的基础(p.103)。

5. 为什么验证者公钥用 BLS,不用 EOA 那套 ECDSA?

BLS 的多个签名能合并成一个,验证一次就能确认所有人都签过。这让信标链能扩展到几十万个验证者(p.82、p.104)。

6. 作恶由谁来发现?

由其他验证者举报。验证者互相监督,举报冲突投票或重复出块的人有奖励(p.90)。

下一讲

下一页 L02b-3 讲投票不花钱带来的问题 Nothing at Stake,三种会被罚没的行为怎么认,罚多少、罚多久,以及区块什么时候算真正定下来。

下一讲 →
L02b-3 L02b-3 罚没与最终性:投票不花钱,验证者为什么不敢两边下注

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