在进行以太坊相关学习或者开发的时候，一个trie还有一个rlp都是绕不开的数据结构。这次我们先来讨论讨论rlp。

数据结构我们也了解过很多了，比如树、链表、图等；如果说数据的序列化方式，像json、xml、protobuf、klv等都是一些很成熟的序列化方式，可是以太坊为什么要用rlp呢？

定义

在以太坊黄皮书的定义中，对RLP的定义是

Recursive Length Prefix

This is a serialisation method for encoding arbitrarily structured binary data (byte arrays).

是递归长度前缀，是一种任意结构的二进制数据(数组)的序列化方式。

我认为，这个binary data是需要注意的一个内容。

在黄皮书中，为了说明rlp能够处理的数据类型，用了一个数学形式的定义：

$\mathbb{T} \equiv \mathbb{L} \uplus \mathbb{B}$

$\mathbb{L} \equiv { \mathbf{t}: \mathbf{t} = ( \mathbf{t}[0], \mathbf{t}[1], ... ) \; \wedge \; \forall n < \lVert \mathbf{t} \rVert : \mathbf{t}[n] \in \mathbb{T} }$

$\mathbb{B} \equiv { \mathbf{b}: \mathbf{b} = ( \mathbf{b}[0], \mathbf{b}[1], ... ) \; \wedge \; \forall n < \lVert \mathbf{b} \rVert : \mathbf{b}[n] \in \mathbb{O} }$

定义的很复杂，不是很理解。但是我们只需要关注两个最基本的集合

  1. $\mathbb{O}$是字节（8位bytes）的集合，所以我们就可以知道，实际上$\mathbb{B}$就是字节数组
  2. $\mathbb{T}$是字节数组（或类似的结构）的集合，所以$\mathbb{L}$就是一个集合。集合的元素可以是字节数组，也可以是集合。

处理方式

对于这两种数据结构，有两种处理办法。

字节数组

$\mathbb{B}$好理解，就是一个字节数组，按照每数组中的每一位进行处理，可以获取结果，更详细的定义是这样子的。

  1. 如果$\mathbb{B}$的长度是1，然后数值大小小于128，编码的结果就是自身。

    可能有些人好奇，如果数值大小大于128呢？该怎么编码？

    实际是这个原因，每一个字符的ascii编码都是0~127，所以是不可能大于128的

  2. 如果$\mathbb{B}$的长度小于56，假设是L，那么编码结果就是(128+L)~原始数组

    我们举一个例子:

    假设数组是[1,2,3,4],那么结果就应当是[128+4,1,2,3,4]

  3. 如果长度大于56的话，并且长度小于$2^{64}$的话，编码结果就是(183+BE(L))~BE(L)~原始内容

    BE是什么呢？我们不妨这么解释下，就是长度L的大端显示占据的长度

    我们依然举一个例子：

    假设原始数组是[1,2,3,...,58]，那么长度就是58，大端编码占据内存一位，编码成十六进制数组就是0x3a，我们又知道，两个是一位，所以BE(L)就是[183+1,58,1,2,3,...,58]

  4. 如果长度大于$2^{64}$呢？以太坊就弄了个很不负责的方法，直接不支持这个类型的数据。

    这个地方以太坊的处理方式很不厚道，万一有人就写的超出了呢！

    为什么要做这个限制？是因为以太坊规定如果第一位的长度超出了192就是数组的数组。假设一个长度是$2^{64}$，也就是说这个长度在内存中占用的是64bits，换成bytes就是64/8=8;183+8=181<192;所以如果超出这个长度就会跟后面混淆了。

数组的数组

$\mathbb{T}$是数组的数组,比如一个例子[[1,2,3],[1,3,5],[]]。这个地方的处理就体现出rlp中的r的概念啦。

  1. 我们还是以[[1,2,3],[1,3,5],[]]举例。为了方便理解，我们以自底向上的方式来解读。

    数组的第一个元素是[1,2,3]，对这个元素的编码是[128+3,1,2,3]

    数组的第二个元素是[1,3,5],对这个的编码是[128+3,1,3,5]

    数组的第三个元素是[],也就是说对这个的编码是[128]

    这三个编码合起来的结果是[131,1,2,3,131,1,3,5,128]，总长度是9，小于56，那么最终的编码结果就是

    [192+9,131,1,2,3,131,1,3,5,130,2,4]

    也就是说，是递归的处理子结果，直到处理的类型是最基本的字节数组类型数据，然后一层一层的网上套，算出来结果

  2. 如果嵌套的数组长度大于56呢？我们再举一个例子[[1,2,3,...,58],[1,2,3],[2,4]]

    数组的第一个元素是[1,2,3,...,58]，对这个元素的编码是[183+1,58,1,2,3,...,58]

    数组的第二个元素是[1,2,3]，对这个元素的编码是[128+3,1,2,3]

    数组的第三个元素是[2，4],对这个的编码是[128+2,2,4]

    三个编码合起来的结果是[191,58,1,2,3,...,58,131,1,2,3,130,2,4]，总长度是67，大端编码占据内存还是1位，结果就是

    [247+1,247,191,58,1,2,3,...,58,131,1,2,3,130,2,4]

    而且，以太坊也是要求这个合并起来的list长度不能大于$2^{64}$。这个原因就好理解了，根据刚刚我们的分析我们知道最大的字节长度是8位，247+8=255，也就是在内存中一字节能够表示的最大大小了，如果超出就无法表示了。

到了此处，似乎有一些好奇，这里面存储的数据全是在[0,127]之间的整数，如果是负数或者小数呢？

在黄皮书上是这么写的

There is no specific canonical encoding format for signed or floating-point values.

但是肯定会有需求的，所以我们需要看看源码是怎么实现的了。