Filecoin - In-depth understanding of the NSE algorithm

The PoREP algorithm has changed from window SDR to SDR in a short time. The new PoREP algorithm NSE is already in the works. The full name of the NSE algorithm is: N arrow Straight E xpander PoRep. You can view the implementation of the NSE algorithm in the feat/nse branch of rust-fil-proofs .

The last commit information of the source code used in this article is as follows:

 commit af4bdcb6da4b371230eed441218c459e99d32068 (HEAD -> feat/nse, origin/feat/nse)
 Merge: 7e7eab2 578d12c
 Author: porcuquine <[email protected]>
 Date: Wed May 20 12:11:43 2020 -0700

    Merge pull request #1118 from filecoin-project/feat/nse-update-neptune-alt
    
    Feat/nse update neptune alt

To understand the NSE algorithm, you can start with the replicate function of the NarrowStackedExpander structure in storage-proofs/porep/src/nse/vanilla/porep.rs.

NSE is called NSE because N stands for Narrow. Narrow means that it is narrower than the previous SDR algorithm and each time the data is processed is a Window.

Each Window will generate a corresponding Replica after layers of processing. The data of each layer corresponding to all Windows are constructed into a Merkle tree together. The data of the Replica corresponding to all Windows are also constructed into a Merkle tree together. The result of the Poseidon Hash of the roots of these two trees is used as comm_r. comm_d and comm_r are data that need to be uploaded to the chain.

Each window needs to go through many layers of processing, which are divided into mask layer, expander layer, and butterfly layer. The core logic is in the encode_with_trees function in storage-proofs/porep/src/nse/vanilla/labels.rs.

The configuration of the number of layers and some parameter configurations of Expander/Butterfly have not been determined. From the configuration of the test code :

 let num_windows = 1;

        let rng = &mut XorShiftRng::from_seed(crate::TEST_SEED);
        let replica_id = <PoseidonHasher as Hasher>::Domain::random(rng);
 let config = Config {
 k: 8,
            num_nodes_window: (sector_size / num_windows) / NODE_SIZE,
            degree_expander: 384,
            degree_butterfly: 16,
            num_expander_layers: 8,
            num_butterfly_layers: 7,
 sector_size,
 };

Window is set to 1, expander's dependency is set to 384, and butterfly's dependency is 16. A total of 15 layers.

Mask Layer

Mask Layer has nothing to do with the specific data, but is related to the window number/node number:

Expander Layer

Expander Layer generates the data of the nodes in the upper layer based on ExpanderGraph. The sha256 result of these data and some numbering information is used as the data of the new node. The diagram is as follows:

For the calculation of the parent node, please refer to the update_hash and next functions of the ExpanderGraphParentsIter structure in storage-proofs/porep/src/nse/vanilla/expander_graph.rs:

 pub struct ExpanderGraph {
    /// The number of bits required to identify a single parent.
 pub bits: u32,
    /// Batching hashing factor.
 pub k: u32,
    /// The degree of the graph.
 pub degree: usize,
 }
        
        
 // node index - 4 bytes
 self.hash[..4].copy_from_slice(&self.node.to_be_bytes());
 // counter - 4 bytes
 self.hash[4..8].copy_from_slice(&self.counter.to_be_bytes());
 // padding 0 - 24 bytes
 for i in 8..32 {
 self.hash[i] = 0;
 }

 let mut hasher = Sha256::new();
 hasher.input(&[&self.hash[..], &[0u8; 32]]);
 self.hash = hasher.finish();

Simply put, the number of parents that each node depends on is degree*k. Parents are determined by the hash result of the node number and the parents sequence number.

For the specific hash calculation logic, please see the batch_hash function in storage-proofs/porep/src/nse/vanilla/batch_hasher.rs.

 for (i, j) in (0..degree).tuples() {
 let k = k as u32;

        let (el1, el2) = (0..k).fold(
            (FrRepr::from(0), FrRepr::from(0)),
            |(mut el1, mut el2), l| {
                let y1 = i + (l as usize * degree as usize);
                let parent1 = parents[y1 as usize];
                let current1 = read_at(data, parent1 as usize);
                let y2 = j + (l as usize * degree as usize);
                let parent2 = parents[y2 as usize];
                let current2 = read_at(data, parent2 as usize);

                add_assign(&mut el1, &current1, &modulus);
                add_assign(&mut el2, &current2, &modulus);

 (el1, el2)
 },
 );

        // hash two 32 byte chunks at once
        hasher.input(&[&fr_repr_as_bytes(&el1), &fr_repr_as_bytes(&el2)]);
 }

The name of batch hash comes from batch. Before hashing, k parents need to be added modularly, and then the result of the modular addition is hashed.

Butterfly Layer

The calculation of Butterfly Layer is similar to that of Expander Layer, the difference is the way to obtain Parents and the hash calculation method of Parents. The calculation of Parents depends on the implementation of ButterflyGraph:

 pub struct ButterflyGraph {
    /// The degree of the graph.
 pub degree: usize,
    /// The number of nodes in a window. Must be a power of 2.
    pub num_nodes_window: u32,
    /// Total number of layers.
 pub num_layers: u32,
    /// Number of butterfly layers.
    pub num_butterfly_layers: u32,
 }

 fn next(&mut self) -> Option<Self::Item> {
    if self.pos >= self.graph.degree as u32 {
 return None;
 }

    let parent_raw = self.node + self.pos * self.factor;
 // mod N
    let parent = parent_raw & (self.graph.num_nodes_window - 1);

 self.pos += 1;
 Some(parent)
 }

A node in the Butterfly Layer depends on the nodes in the previous layer by degree. The calculation formula for each Parent number is:

node + pos * factor

Among them, node is the node number, pos is the Parents number, and factor is the coefficient (related to the layer number). This kind of dependency shape with fixed intervals is a bit like the stripes on a butterfly's wings, so it is called a butterfly layer.

The hash calculation of all Parents is relatively simple, which is the hash value of all Parent data concatenated.

 // Compute hash of the parents.
 for (parent_a, parent_b) in graph.parents(node_index, layer_index).tuples() {
     let parent_a = parent_a as usize;
     let parent_b = parent_b as usize;
     let parent_a_value = &layer_in[parent_a * NODE_SIZE..(parent_a + 1) * NODE_SIZE];
     let parent_b_value = &layer_in[parent_b * NODE_SIZE..(parent_b + 1) * NODE_SIZE];
     hasher.input(&[parent_a_value, parent_b_value]);
 }

 let hash = hasher.finish();

After the multi-layer processing is completed, the last bufferfly layer is encoded with the original data to generate the final Replica layer. The calculation process is to perform another bufferfly calculation based on the last bufferfly layer, and perform large number addition calculation on the result and the original data. For the detailed calculation process, please refer to the butterfly_encode_decode_layer function in storage-proofs/porep/src/nse/vanilla/labels.rs.

Summarize:

PoREP's NSE algorithm is another attempt at the SDR algorithm. It attempts to reduce the size of data processed in a single process (window), tries not to use the front-end and back-end dependencies of nodes (layer calculations can be parallelized), increases the dependency of a single layer, and increases the number of layers. The underlying layer of the entire algorithm still uses the sha256 algorithm. The NSE algorithm can be understood as an attempt to balance security and performance.