Filecoin — An Upgrade Triggerd By Overflow Bug

Filecoin is having a compulsory upgrade on Novmber 24th, so I was curious about it and checked out the latest code. Poggers, good surprise there. An overflow bug triggers this upgrade. The overflow leads to SDR algorithm implemented in the program mismatches the contract. The performance was up around 50% with this overflow bug. This upgrade is closely knitted to SDR algorithm, and folks can review the SDR algorithm concept at this previous post.

https://starli.medium.com/filecoin-deep-into-sdr-algorithm-9c7dcc132875

1 Official Patch

There was an official patch submission on November 2nd:

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

This patch is pretty important. It fixes the current contract, and along with that the node relationship has also changed thoughout the SDR algorithm.

Let’s start with the simple one — drg: move predecessor to the first position. This change is rather straight forward:

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

A node Base’s dependency on its parent node has changed from the original first node of the LAST Base parent to the FIRST Base parent. That is to say, if the last Base parent node is dependent on the previous node, then the previous nodes of Base parent node can be calculated in advance, and the dependency on the previous node is removed. With the old algorithm, even though it doesn’t advance entire calculation for every node, it does improve a little bit. Coming to the latest contract, even this little bit cannot be calculated in advance anymore.

2 Overflow Bug

Highlight on this change:expander: divide before casting to u32:

The original logic is encapsulated in this class is_legacy:

transformed as u32 / self.expansion_degree as u32

transformed value we get from Feistel encryption algorithm. You can go to earlier posts to learn more about the specific logic. Anyway without opening the blackbox, we can still roughly calculate the range for the result. self.expansion_degree is fixed at 8. The max range for this expression is:

2^32/8 = 2^29

Note that, under 32G sector size, the total amount of nodes is 2³⁰. This expression, due to limiting trnasformed to 32-bit unsigned interger, leads to entire exp parents range down to 2²⁹ instead of 2³⁰. Alternatively, with the 32G sector size, nodes on a certain layer can only depend on the first half nodes of previous layer. And even less relative dependency on previous layer when it comes to the 64G sector size case.

The pre-upgrade exp parents dependency relationship can be summarized with this diagram:

That is also to say, the previous SDR contract logic is not exactly the Filecoin contract regulated SDR contract logic. Based on the the previous SDR contract logic, the SDR calculation process can be optimized as follows:

After half of the calculation is done on certain layer, kick off the next layer calculation, which accelarates the whole SDR calculation process by around 50%.

Oops.

3 Upgrade Time

The scheduled upgrade time for the next two versions is documented in build/params_mainnet.go:

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

Calico will upgrade at height 265200, which is November 25th CST. Persian will be done 2.5 days after Calico. In between two versions for the 2.5 days there will be a hybrid version, which supports both old and bew SDR contracts. Starting from Persian, only the upgraded SDR contract will be supported.

Summary:

Filecoin requires an official upgrade on November 25th. There exists overflow bug in the pre-upgrade SDR algorithm, and Exp parent dependency is only on the first half of previous layer data. SDR algorithm performance can improve by parallel calculating. Upgraded SDR algorithm fixes the bug, and reinforces the dependency relationship between parent and child Base nodes.