
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 <[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
理解NSE算法,可以从storage-proofs/porep/src/nse/vanilla/porep.rs中NarrowStackedExpander结构的replicate函数看起。
01 整体流程
NSE,之所以称为NSE,因为N,Narrow。Narrow的意思是比之前的SDR算法,窄,每次处理的数据为一个Window。
每个Window经过层层的处理,都会生成对应的Replica。所有Window对应的每一层的数据一起构建成Merkle树。所有Window对应的Replica的数据也一起构建成Merkle树。这两棵树树根的Poseidon Hash的结果作为comm_r。comm_d以及comm_r是需要上链的数据。
02 多层处理
每个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();
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算法的另外一种尝试。尝试降低单个处理的数据大小(window),尝试不采用节点的前后依赖(layer的计算可以并行),加大单层的依赖,加大layer的层数。整个算法底层还是采用sha256算法。NSE算法可以理解为安全性和性能之间平衡的一种尝试。
作者:Star Li
比推快讯
更多 >>- 白宫数字资产政策顾问:稳定币立法或推动数字资产市值增至 15 至 20 万亿美元
- 分析师:10 年期美国国债将维持区间交易
- 慢雾余弦:Sui 地址对应的私钥无法派生出同地址的 Aptos 地址,互相之间无法转换
- 山寨币季节指数升至 24,90 天表现居前代币为 SYRUP、PENGU、HYPE、VIRTUAL、FARTCOIN
- 币安:CROSS 交易将于 7 月 4 日 16:00 开启,持有至少 140 个 Alpha 积分的用户可参与空投
- Jupiter Studio:反狙击保护支持用户自主设置“狙击税”
- 欧洲央行行长:需要改善经济以提升欧元全球地位
- Solana 链上 Meme 币 NOBODY 市值现报 3700 万美元,24 小时涨幅 18.75%
- 分析师:比特币牛市或将于 10 月结束
- Bitget 链上交易(Onchain)本周涨幅榜 Top 3:UNICORN、LuckyCoin、H
- Sonic Labs 联创 AC:即将上线支持 Gas 补贴的新版客户端
- 过去 24 小时 CEX 净流入 421.07 枚 BTC
- 股票代币化平台 xStocks 昨日交易额达 381 万美元,标普 500 成交额居首
- Upbit 暂停 Polygon Ecosystem(POL)及 Stephan(GMT)充提业务
- 数据:“此前转出 1 万枚 BTC 的巨鲸”的另一钱包转出 1 万枚 BTC,价值约 10.9 亿美元
- 特朗普计划对部分国家征收最高 70%关税,8 月 1 日起执行
- CoinW 币赢携手东亚杯足球赛,借国家级电视台曝光强化信任背书
- 特朗普:在接下来的 24 小时内,我们将会知道哈马斯是否同意停火协议
- AEX(安银)交易平台创始人黄天威昨日于泰国被保释
- BNSOL Super Stake 上线 PIXEL(PIXEL)
- 以太坊现货 ETF 昨日净流入 1.49 亿美元,仅灰度 ETHE 净流出 535.48 万美元
- 某包含 10000 枚 BTC 的地址在休眠 14.3 年后被激活
- 受德州电力限制与天气影响,多家比特币矿企 6 月产量下降
- Galaxy Digital 从 Coinbase 提现 400 枚 cbBTC,约合 4379 万美元
- 英国与新加坡在伦敦会谈中达成新的人工智能和代币化协议
- 数据:巨鲸 qwatio 被清算 10 次后再次做空 21 枚 BTC,价值约 230 万美元
- Polymarket 上预测马斯克今年年底前创建新政党的概率报 42%
- RootData:BMT 将于一周后解锁价值约 351 万美元的代币
- Project Hunt:大型多人在线角色扮演游戏 Treeverse 为过去 7 天被 Top 人物取关最多的项目
- A 股港股数字货币稳定币概念股涨幅居前,国泰君安国际涨超 19%
- 高盛下调美债收益率预期,因美联储提前降息可能性增加
- 市场消息:京东和蚂蚁集团建议央行批准基于人民币的稳定币
- PLUME 短时涨幅扩张至 8.9%, Gate 交易占比居首
- 华尔街日报:Meta Platforms 提出收购风投公司 NFDG 的少数股权
- 数据:质押型 SOL ETF SSK 上市首日吸引 1200 万美元资金流入
- FTX 债权人代表:FTX 向法院申请在 49 个司法管辖区实施“受限处理程序”,其所属债权人将丧失分配权益
- 日本 Minna Bank 正与 Fireblocks、Solana Japan 和 TIS 试行稳定币和钱包用例
- Bitmine 自宣布以太坊储备战略以来股价上涨超 30 倍
- FTX 债权人代表:中国用户或有可能失去索赔权
- 某巨鲸/机构过去 3 周累计将 8.1 万枚 ETH 转入 CEX
- 6 月以太坊链上 NFT 销售额仅约 1 亿美元,创 2021 年 2 月以来最低记录
- Binance Alpha 昨日交易量报 4.6 亿美元,BR、KOGE、BULLA 分列前三
- Bybit 首席法务官 Robert MacDonald 入选《亚洲法律杂志》2025 年度亚洲合规官 15 强
- 内幕交易员@qwatio 于今日凌晨再次加仓做空
- 汇丰银行与阿布扎比银行、交易所合作推出中东北亚首个代币化固定收益产品
- iM Bank 抢注 12 项商标,布局韩元稳定币市场
- 富达 FBTC 昨日净流入 2.37 亿美元,ARKB 昨日净流入 1.14 亿美元
- Eclipse 官方 ES 空投查询上线,ASC 系列 NFT 持有者将获得空投
- 数据:Circle 约 8 小时前在 Solana 上铸造了 2.5 亿 USDC
- 民调:73% 加密货币投资者支持特朗普数字资产政策
比推专栏
更多 >>观点
比推热门文章
- 白宫数字资产政策顾问:稳定币立法或推动数字资产市值增至 15 至 20 万亿美元
- Tether推出黄金代币,泰国出台数字资产监管新政
- 分析师:10 年期美国国债将维持区间交易
- 慢雾余弦:Sui 地址对应的私钥无法派生出同地址的 Aptos 地址,互相之间无法转换
- 山寨币季节指数升至 24,90 天表现居前代币为 SYRUP、PENGU、HYPE、VIRTUAL、FARTCOIN
- 马斯克”乌托邦”梦碎:科技狂想与现实的碰撞
- 币安:CROSS 交易将于 7 月 4 日 16:00 开启,持有至少 140 个 Alpha 积分的用户可参与空投
- Jupiter Studio:反狙击保护支持用户自主设置“狙击税”
- 欧洲央行行长:需要改善经济以提升欧元全球地位
- Solana 链上 Meme 币 NOBODY 市值现报 3700 万美元,24 小时涨幅 18.75%