Filecoin — Deep into NSE algo

It didn’t take long for PoREP algorithm to change from window SDR to SDR. New PoREP algorithm NSE is developing in process. NSE stands for Narrow Stacked Expander PoRep. You can check out implementation of NSE algorithm at feat/nse branch of rust-fil-proofs.

See below for last submission of the source code mentioned in this article:

commit af4bdcb6da4b371230eed441218c459e99d32068 (HEAD -> feat/nse, origin/feat/nse)
Merge: 7e7eab2 578d12c
Author: porcuquine <1746729+porcuquine@users.noreply.github.com>
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 NSE algorithm, we can start from replicate function in NarrowStackedExpander from storage-proofs/porep/src/nse/vanilla/porep.rs.

Overall Process

NSE got its name from N for Narrow. Narrow as in narrower than previous SDR algorithms, that it only process one Window per data processing.

After layers of processing, each Window generates corresponding Replica. All layers of data corresponding to the Windows together build Merkle tree. All Replica data corresponding to Windows also builds Merkle tree. Take Poseidon Hash on roots of two trees, and the result is comm_r. comm_d and comm_r data needs to be stored on blockchain.

Multi-layer Processing

Each window needs to go through layers of processing. These layers include mask layer, expander layer, and butterfly layer. The code logic is located at encode_with_trees function in storage-proofs/porep/src/nse/vanilla/labels.rs的encode_with_trees.

Number of layers, and some parameters of Expander/Butterfly are not set. We can see from below 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,
        };

Number of window is 1; degree of expander layers is 384; degree of butterfly layers is 16. The total is 15 layers.

Mask Layer

Mask Layer is not related to specific data, but related to window Index/node index.

Expander Layer

Expander Layer is based on the values of ExpanderGraph generated dependent previous layer. These values and sha256 of some index information become value of the new node. For instance:

For calculation on parent node please check update_hash and next function in ExpanderGraphParentsIter from 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();

In short, number of parents of a node is degree*k. We can use hash result of node index and parents index to establish parents.

For details on hash function, please check 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)]);
    }

batch hash is named after batch. Before hashing, we need to perform modular addition on k parents. Then hash the result of modular addition.

Butterfly Layer

Butterfly Layer calculation is similar to the one in Expander Layer. The difference is method to get Parents and hash function of Parents. Parents calculation relies on ButterflyGraph Implementation:

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)
}

Any node in Butterfly Layer relies on number of degree nodes from previous layer. We can get Parent index by:

node + pos * factor

node is node index, pos is Parents index and factor is the coefficient related to index of the layer. The shape of this kind of fixed interval resembles pattern on butterfly wings, thus the name butterfly layer.

Hash calculation of Parents is pretty straight forward, which is the hash value of concatenation on all Parents values.

// 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();

Generate Replica

After finishing multi=layer processing, the last layer — bufferfly layer encode with original data, and generates the final Replica layer. This involves another bufferfly calculation based on the last layer, bufferfly layer. Then take large number addition on the result and original data. See butterfly_encode_decode_layer function in storage-proofs/porep/src/nse/vanilla/labels.rs for implementation details.

Summary:

PoREP NSE algorithm is yet another attempt of SDR algorithm. It reduces window size for data processing, does not depend on node sequentially (layer calculations work in parallel) , and increase the dependency on single layer and number of layers. However, the foundation is still sha256 algorithm. NSE is an attempt to reach for a balance in safety and performace.