Filecoin - 深入理解NSE算法

PoREP算法，從window SDR改成SDR，時間並不長。新的PoREP算法NSE已經在醞釀中。NSE算法的全稱：Narrow Stacked Expander PoRep。在rust-fil-proofs的feat/nse分支，可以查看NSE算法的實現。

文章使用的原始碼的最後一個提交信息如下：

commit af4bdcb6da4b371230eed441218c459e99d32068 (HEAD -> feat/nse, origin/feat/nse)
Merge: 7e7eab2 578d12c
Author: porcuquine <[e-mail]>
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

理解NSE算法，可以從storage-proofs/porep/src/nse/vanilla/porep.rs中NarrowStackedExpander結構的replicate函數看起。
NSE，之所以稱為NSE，因為N，Narrow。Narrow的意思是比之前的SDR算法，窄，每次處理的數據為一個Window。
每個Window經過層層的處理，都會生成對應的Replica。所有Window對應的每一層的數據一起構建成Merkle樹。所有Window對應的Replica的數據也一起構建成Merkle樹。這兩棵樹樹根的Poseidon Hash的結果作為comm_r。comm_d以及comm_r是需要上鏈的數據。
每個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, &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的名稱，來自於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();
在多層處理結束後，最後一層的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算法可以理解為安全性和性能之間平衡的一種嘗試。