# Erasure Coding 纠删码原理（ Near Protocol ）

By [Ethan - if(DAO)](https://paragraph.com/@ethan-if-dao) · 2022-01-13

---

Erasure Code 是什么
----------------

1、Erasure Code是一种编码技术，它可以将 n 份原始数据，增加 m 份数据，并能通过n+m份中的任意 n 份数据，还原为原始数据。即如果有任意小于等于 m 份的数据失效，仍然能通过剩下的数据还原出来。

2、纠删码技术在分布式存储系统中的应用主要有三类

（1）RS（ Reed-Solomon ）里德-所罗门纠删码

（2）AC（ Array Code: RAID5、RAID6等）阵列纠删码

（3）LDPC（ LowDensity Parity Check Code ）低密度奇偶校验纠删码（ LDPC 目前主要用于通信、视频和音频编码等领域 ）

Erasure Code 的优势
----------------

副本策略和纠删码是存储领域常见的两种数据冗余技术。相比于副本策略，纠删码具有更高的磁盘利用率：

![](https://storage.googleapis.com/papyrus_images/770ff7fefc77c3253d11016e746dea57bf019e5708290b43ea355ef8515ea4df.png)

RS码原理
-----

Reed-Solomon（RS）码是存储系统较为常用的一种纠删码，它有两个参数n和m，记为RS（n ，m）。n 代表原始数据块个数。m代表校验块个数。以n=5，m=3为例 ：

1、encoding 编码过程（D是原始数据块，得到的C为校验块，构建 Bi 有专门的数学方法，比如范德蒙矩阵，具体可参见大学的线性代数知识）

![](https://storage.googleapis.com/papyrus_images/9f76df4f2aa50bf85553bff61cfe8e4626090f5d5834dd8dc095594714114b8f.png)

即5个原始数据块，乘上一个 (n+m) \* n 的矩阵，然后得出一个 (n+m) \* 1 的矩阵。根据矩阵特点可以得知结果矩阵中前面5个值与原来的5个数据块的值相等（如图D），而最后3个则是计算出来的校验块（如图C）。

2、假设丢失了 m 块数据（D1、D4、C2丢失）

![](https://storage.googleapis.com/papyrus_images/8356b72ae6ac515bd4759f88bb2793fe7c4727aa3930f64566917da232ccd4e3.png)

我们如何从剩余的 n 个数据块（ 剩余的n块可能包含几个原始数据块+几个校验块 ）恢复出来原始的n个数据块呢，就需要通过下面的decoding（解码）过程来实现。

3、decoding 解码过程

（1）构建变形矩阵 B'

从编码矩阵中删去丢失数据块和丢失编码块对应行。 将删掉m个块的(n+m) \* 1个矩阵变形为n \* 1 矩阵，同时B矩阵也需要删掉对应的m个行得出一个 B' 的变形矩阵，这个 B' 就是 n \* n 矩阵，如下图所示

![](https://storage.googleapis.com/papyrus_images/0f3920eafec594f9e4eeb3ee6e1163806a05e14f38a526b86d8023f81b770be0.png)

（2）计算 B' 的逆矩阵（ 具体计算过程参见大学课程：线性代数 ）

![](https://storage.googleapis.com/papyrus_images/c125a62a4a26e22bd7663409e768d2dbf3af607a25c5d55da1d19691bbe74c36.png)

（3）等式两边分别乘上 B' 的逆矩阵

![](https://storage.googleapis.com/papyrus_images/1de781aedf0d34fcc36e77e0abed4c36b1d6c999e2d9a9b280c23db424536063.png)

（4） B' 和它的逆矩阵相乘得到单位矩阵 I

![](https://storage.googleapis.com/papyrus_images/6c1d984c75dbe7e27fdbd76df6ebd56c75a2b054e622516a53c112f10f0a4155.png)

（5）最后左边只剩下原始数据矩阵D，至此解码过程完成，即我们恢复出了全部数据D1-D5

![](https://storage.googleapis.com/papyrus_images/883ecb1734bc59c76e69105a7d5f05b58e8b7c5f1db9d09e06fa6919b967e852.png)

Erasure Code 在区块链中的应用
---------------------

Near Protocol 是 V神 点名表扬的区块链一层扩容协议，协议采用的是状态分片技术，其核心原理就是使用了纠删码技术使得跨分片的账户间的转账可以被容易的确定状态转化是否正确。

![](https://storage.googleapis.com/papyrus_images/b2cb98cc3ee6384e23f62f2a4fae8932163af74f734b8fd9edd604615915c35e.png)

即 Near 区块链的每个区块都被分割为很多个 Shard 分片，每个 Shard 分片通过 Erasure Code 进行编码分成很多个 Part ，不同的 Part 发送给 Near 区块链网络上的不同 Validators，这些 Validators 可以通过 Erasure Code 的解码过程还原每个 Shard 分片的状态，并确定状态转换的最终一致性。

想进行更深入的研究可以参见 Near Protocol 夜影分片协议的原文链接：

[https://near.org/downloads/Nightshade.pdf](https://near.org/downloads/Nightshade.pdf)

---

*Originally published on [Ethan - if(DAO)](https://paragraph.com/@ethan-if-dao/erasure-coding-near-protocol)*