Filecoin – Introduction to Precommit2 Calculation

Filecoin – Introduction to Precommit2 CalculationNew

Abstract: Sector calculation is divided into two parts: Precommit1 and Precommit2. The two parts together are called the SDR algorithm. The relevant calculations of the entire SDR algorithm have been introduced in previous articles. This article focuses on the calculation logic of Precommit2.

The Sector calculation part is divided into two parts: Precommit1 and Precommit2. The two parts together are called the SDR algorithm. The relevant calculations of the entire SDR algorithm have been introduced in previous articles. This article focuses on the calculation logic of Precommit2. Precommit2 calculation is divided into two parts: 1/ Column Hash calculation and Merkle tree construction 2/ Replica calculation and Merkle tree construction. For related logic, please refer to the transform_and_replicate_layers function in rust-fil-proofs/storage-proofs/porep/src/stacked/vanilla/proof.rs.

1 Column Hash Calculation

Column Hash calculation is implemented in the generate_tree_c function. The specific implementation is divided into two versions: CPU version and GPU version.

 if settings::SETTINGS.lock().unwrap().use_gpu_column_builder {
       Self::generate_tree_c_gpu::(
layers,
nodes_count,
tree_count,
configs,
labels,
)
} else {
       Self::generate_tree_c_cpu::(
layers,
nodes_count,
tree_count,
configs,
labels,
)
}

The logic of the GPU version is relatively complicated. Let's talk about the logic of the GPU:

To perform column calculation, it is necessary to read 11 layers of layer data from the hard disk and integrate them into a column layout. The GPU version processes in batches, reads and sorts a part of the columns, and sends them to the GPU for processing (Column Hash and Merkle tree construction) through the channel. The code logic is generally two threads, one reads the layer data and sorts the columns, and the other is processed by the GPU. The default number of nodes for each batch is 400,000, which is about 135M. After the column calculation is completed, the GPU constructs the Merkle tree.

2 Replica Calculation

Replica is the result of encoding the data of the last layer and the original data. Each time a part of Replica is encoded, it is sent to the GPU through the channel (to construct a Merkle tree). The number of nodes in each batch is 700000 by default, which is about 22M. Note that batch is the result of encoding.

3 Merkle tree construction

The Merkle tree is constructed using the merkletree library. This library implements the structure and calculation of a general Merkle tree. A general Merkle tree means that Merkle is not just a binary tree as we usually understand it, but is divided into three layers: top, sub, and base.

As shown in the example above, top is a 1-way tree, sub is a 3-way tree, and base is a 4-way tree. In the Precommit2 calculation, both tree_c and tree_r_last are 8-way trees:

 type Tree = storage_proofs::merkle::OctMerkleTree;
pub type OctMerkleTree= DiskTree;

4 GPU Acceleration

In the Precommit2 calculation, the calculation of Column Hash and the construction of Merkle tree are accelerated by GPU. The relevant code is in the neptune code base. Interestingly, this part of the code is not implemented in cuda or opencl, but in a new higher-level language: Futhark.

5 Related macro definitions

FIL_PROOFS_USE_GPU_COLUMN_BUILDER – Use GPU to calculate column hash

FIL_PROOFS_MAX_GPU_COLUMN_BATCH_SIZE – The batch size of each column calculation, the default is 400000

FIL_PROOFS_COLUMN_WRITE_BATCH_SIZE – The batch size of each column data refresh, the default is 262144

FIL_PROOFS_USE_GPU_TREE_BUILDER – Use GPU to construct Merkle tree

FIL_PROOFS_MAX_GPU_TREE_BATCH_SIZE – The batch size for each encoding calculation, the default value is 700000

Summarize:

The Precommit2 phase mainly involves calculating Column Hash, generating Replicas, and constructing the corresponding Merkle tree. The calculation of Column Hash and the construction of Merkle tree can be accelerated by GPU. The GPU implementation uses a new high-level language: Futhark.

Source: Star Li