NSE，之所以稱為NSE，因為N，Narrow。Narrow的意思是比之前的SDR演算法，窄，每次處理的資料為一個Window。
每個Window經過層層的處理，都會生成對應的Replica。所有Window對應的每一層的資料一起構建成Merkle樹。所有Window對應的Replica的資料也一起構建成Merkle樹。這兩棵樹樹根的Poseidon Hash的結果作為comm_r。comm_d以及comm_r是需要上鍊的資料。
2. 多層處理
每個window需要經過很多層的處理，這些層分為mask layer，expander layer, butterfly layer。核心邏輯在storage-proofs/porep/src/nse/vanilla/labels.rs的encode_with_trees函式中。
層數的配置，以及Expander/Butterfly的一些引數配置都沒有確定。從測試程式碼的配置看：
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設定為1，expander的依賴設定為384，butterfly的依賴為16。總共15層。
Mask Layer
Mask Layer和具體的資料沒有關係，和window編號/節點編號有關：
Expander Layer
Expander Layer基於ExpanderGraph生成依賴的上一層的節點的資料。這些資料和一些編號資訊的sha256的結果作為新的節點的資料。示意如下：
parent節點的計算請檢視storage-proofs/porep/src/nse/vanilla/expander_graph.rs中ExpanderGraphParentsIter結構的update_hash和next函式：
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();
簡單的說，每個node依賴的parent的個數是degree*k個。parents的確定透過節點編號以及parents序號的hash結果來確定。
具體的hash計算邏輯，請檢視storage-proofs/porep/src/nse/vanilla/batch_hasher.rs的batch_hash函式。
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, ¤t1, &modulus);
add_assign(&mut el2, ¤t2, &modulus);
(el1, el2)
},
);
// hash two 32 byte chunks at once
hasher.input(&[&fr_repr_as_bytes(&el1), &fr_repr_as_bytes(&el2)]);
}
batch hash的名稱，來自於batch，在做hash之前，需要將k個parents先做模加，模加的結果再做hash。
Butterfly Layer
Butterfly Layer的計算類似於Expander Layer，不同的是獲取Parents的方式以及Parents的hash計算方式。Parents的計算依賴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)
}
Butterfly Layer的一個節點，依賴degree個前一層的節點。每個Parent序號的計算公式：
node + pos * factor
其中，node是節點編號，pos是Parents編號，factor是係數（和層的編號有關）。這種有固定間隔的依賴形狀，有點像蝴蝶翅膀的條紋，所以稱butterfly layer。
所有Parents的Hash計算，相對簡單，就是所有Parent資料拼接後的Hash值。
// 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();
3. 生成Replica
在多層處理結束後，最後一層的bufferfly layer和原始資料進行encode，生成最後的Replica layer。計算過程，就是在最後一層bufferfly layer的基礎上，再做一次bufferfly計算，結果和原始資料進行大數加法計算。詳細的計算過程，請檢視storage-proofs/porep/src/nse/vanilla/labels.rs的butterfly_encode_decode_layer函式。
總結：
PoREP的NSE演算法，是SDR演算法的另外一種嘗試。嘗試降低單個處理的資料大小(window)，嘗試不採用節點的前後依賴（layer的計算可以並行），加大單層的依賴，加大layer的層數。整個演算法底層還是採用sha256演算法。NSE演算法可以理解為安全性和效能之間平衡的一種嘗試。
