fx168财经网

Filecoin - 深入理解NSE算法

矿业前瞻 2021-07-27 19:4151www.jddiban.com未知

PoREP算法,从window SDR改成SDR,时间并不长。新的PoREP算法NSE已经在酝酿中。NSE算法的全名:Narrow Stacked Expander PoRep。在rust-fil-proofs的feat/nse分支,可以查询NSE算法的达成。

文章用的源码的最后一个提交信息如下:

commit af4bdcb6da4b371230eed441218c459e99d32068 
Merge: 7e7eab2 578d12c
Author: porcuquine <1746729+porcuquine@users.noreply.github.com>
Date:Wed May 20 12:11:43 2021 -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。

星想法

层数的配置,与Expander/Butterfly的一些参数配置都没确定。从测试代码的配置看:

let num_windows = 1;

let rng = &mut XorShiftRng::from_seed;
let replica_id = <PoseidonHasher as Hasher>::Domain::random;
let config = Config {
k: 8,
num_nodes_window: / 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);
// counter - 4 bytes
self.hash[4..8].copy_from_slice);
// padding 0 - 24 bytes
for i in 8..32 {
self.hash[i] = 0;
}

let mut hasher = Sha256::new;
hasher.input;
self.hash = hasher.finish;

容易的说,每一个node依靠的parent的个数是degree*k个。parents的确定通节日点编号与parents序号的hash结果来确定。

具体的hash计算逻辑,请查询storage-proofs/porep/src/nse/vanilla/batch_hasher.rs的batch_hash函数。

for  in .tuples {
let k = k as u32;

let = .fold, FrRepr::from),
|, l| {
let y1 = i + ;
let parent1 = parents[y1 as usize];
let current1 = read_at;
let y2 = j + ;
let parent2 = parents[y2 as usize];
let current2 = read_at;

add_assign;
add_assign;


},
);

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

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 -> 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.pos += 1;
Some
}

Butterfly Layer的一个节点,依靠degree个前一层的节点。每一个Parent序号的计算公式:

node + pos * factor

其中,node是节点编号,pos是Parents编号,factor是系数(和层的编号有关)。这种有固定间隔的依靠形状,有点像蝴蝶翅膀的条纹,所以称butterfly layer。

所有Parents的Hash计算,相对容易,就是所有Parent数据拼接后的Hash值。

// Compute hash of the parents.
for in graph.parents.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.. * NODE_SIZE];
let parent_b_value = &layer_in[parent_b * NODE_SIZE.. * NODE_SIZE];
hasher.input;
}

let hash = hasher.finish;
03
生成Replica


在多层处置结束后,最后一层的bufferfly layer和原始数据进行encode,生成最后的Replica layer。计算过程,就是在最后一层bufferfly layer的基础上,再做一次bufferfly计算,结果和原始数据进行大数加法计算。详细的计算过程,请查询storage-proofs/porep/src/nse/vanilla/labels.rs的butterfly_encode_decode_layer函数。

长按微信二维码关注我


概要:

PoREP的NSE算法,是SDR算法的另外一种尝试。尝试减少单个处置的数据大小,尝试不使用节点的前后依靠(layer的计算可以并行),加强单层的依靠,加强layer的层数。整个算法底层还是使用sha256算法。NSE算法可以理解为安全性和性能之间平衡的一种尝试。

技术改变世界

每一个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函数中。


此文出于传递更多信息之目的,并不意味着同意其看法或证实其描述。本网站所提供的信息,只供参考之用。

上一篇:报告:2021年Q2,ETH活跃用户翻番突破100万 下一篇:没有了

fx168财经网-虚拟货币|数字货币|区块链技术新闻资讯网站 Copyright © 2002-2021 fx168财经网 (http://www.inclusivedesignresearch.com) 网站地图 TAG标签 备案号