Filecoin - 一个越界Bug引发升级

  • Star Li
  • 更新于 2020-11-21 22:50
  • 阅读 2435

Filecoin官方在11月25号强制升级。升级前的SDR算法实现在越界漏洞,Exp父亲节点的依赖只和上一层的前一半的数据有关。SDR算法可以通过多个并行计算提高性能。升级后的SDR算法修复了漏洞,并同时加强了Base父亲节点的依赖关系。

Filecoin在11月24号需要强制升级,好奇看了看最新的代码。不看不知道,一看吓一跳。一个越界的Bug引发了这次升级。这个越界的Bug使程序实现的SDR算法和协议不一致。利用这个越界的Bug可以提升SDR的性能50%左右。这次升级和SDR算法密切相关,对SDR算法不熟悉的小伙伴可以查看之前的文章:

Filecoin - 为什么SDR这么慢?

1 官方补丁

在11.02号官方提交一个补丁:

commit 0d17d7466f40e1228a4bab25f8b4861cb0d2da4d
Author: Friedel Ziegelmayer <me@dignifiedquire.com>
Date:   Mon Nov 2 12:06:36 2020 +0100

    fix(storage-proofs-porep): fix graph generation

    - expander: divide before casting to u32
    - drg: move predecessor to the first position

这个补丁比较重要,这个补丁“修正”了当前的协议。整个SDR算法中节点的连接关系也发生了改变。

先讲讲简单的 drg: move predecessor to the first position改动,比较简单:

-    parents[m_prime] = node - 1;
+    // Immediate predecessor must be the first parent, so hashing cannot begin early.
+    parents[predecessor_index] = node - 1;

一个节点的Base父亲节点的依赖,从原来的是最后一个Base父亲节点依赖上一个节点,变成了第一个Base父亲节点依赖上一个节点。简单的说,如果Base父亲节点的最后一个才依赖上一个节点,那Base父亲节点的前面一些节点可以先计算,无须依赖上一个节点的计算。使用老的算法,虽然不能完全提前算整个节点的结果,但是能提前一点好一点。改成最新的协议,这一点点也不能提前算了。

2 越界Bug

重点在于这个改动:expander: divide before casting to u32改动:

原始逻辑,就是在is_legacy包裹住的逻辑:

transformed as u32 / self.expansion_degree as u32

transformed的值是通过Feistel加密算法生成,具体的逻辑含义可以查看之前的文章。即使在不需要知道逻辑的情况下,可以估算出整个表达式的计算结果的范围。self.expansion_degree是固定值8。整个表达式的最大范围为:

2^32/8 = 2^29

注意的是,在32G扇区大小的情况下,节点个数是2^30次方。而这个表达式因为限制了transformed是32bit的无符号整数,导致了整个exp parents的范围在2^29次方范围内,并不是2^30次方。换个说法,在32G扇区大小的情况下,某一层的节点只依赖上一层的前一半节点。64G扇区大小的情况下,上一层依赖相对更少。

总结升级前的exp parents的依赖逻辑如下图:

也就是说,之前的SDR协议逻辑并不是Filecoin协议规定的SDR协议逻辑。在之前的SDR协议基础上,SDR的计算过程可以优化如下:

在某一层的一半计算完成后,可以立即开始下一层的计算,加速整个SDR的计算过程。整个计算可以加速50%左右。Oops。

3 升级时间

在build/params_mainnet.go定义了下两个版本的升级时间:

const UpgradeCalicoHeight = 265200
const UpgradePersianHeight = UpgradeCalicoHeight + (builtin2.EpochsInHour * 60)

Calico将在265200高度升级,也就是北京时间11月25号进行升级。Persian在Calico后2.5天完成。在两个版本中间的2.5天是个混合版本,新的和老的SDR协议都支持,从Persian开始,只支持升级后的SDR协议。

总结:

Filecoin官方在11月25号强制升级。升级前的SDR算法实现在越界漏洞,Exp父亲节点的依赖只和上一层的前一半的数据有关。SDR算法可以通过多个并行计算提高性能。升级后的SDR算法修复了漏洞,并同时加强了Base父亲节点的依赖关系。

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
Star Li
Star Li
Trapdoor Tech创始人,前猎豹移动技术总监,香港中文大学访问学者。