Blockchain Ethereum

Ethereum 中的 RLP 算法 (Recursive Length Prefix) 编码

Ethereum 学习笔记

Posted by Nicodechal on 2018-12-20

概述

在 Ethereum 中，RLP 算法被用于编码任意嵌套的字节数组，下面是一个任意嵌套字节数组的例子：

1
["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]

RLP 算法用来编码 ( 序列化 ) 其结构，使其变为字节序列 ( 二进制串 ) 。下面是一个简单的转化例子 ( 使用 < 和 > 表示序列和数组区分 ) ：

1
[ [], [[]], [ [], [[]] ] ] = < 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 >

上面例子中，RLP 算法将嵌套的数组转化为一个字节序列 ( 编码 )，可以方便的进行存储和传输，同时，该字节序列还记录了原始数据的结构及其中的数据，可以方便地将数据还原出来，这个过程称为解码。本文将对编码算法进行说明。

算法流程

字符串 ( 无嵌套的字节数组 ) 编码

  1. 对于字符串中的一个字节的值，如果其值在 [0x00, 0x7f] 之间 ( 即 [0, 127]，为 ASCII 表中的字符的取值范围 )，其 RLP 编码值为其本身。

例如，对于 "dog" 中的每个字符，则有：

1
2
3
RLP('d') = 'd'
RLP('o') = 'o'
RLP('g') = 'g'

ASCII 码表

完成上述步骤后再考虑字符串的长度：

  1. 如果一个字符串长度 str_len 在 0 到 55 字节，还需要在字符串每个字符编码结束后的结果前添加一个字节，这个字节的值为 0x80 + str_len ( 即 128 + str_len，128 为偏移值 )。
  2. 如果一个字符串长度 str_len 大于 55 ( 0x37 ) 字节，则需要：
    1. 首先得到字符串长度十六进制表示的字节数 len_of_str_len。
    2. 在每个字节编码结束后的结果前添加两个部分，一个是 0x80 + 0x37 + len_of_str_len, 另一个是 str_len 的字节编码形式结果。

例如，字符串 "dog"，长度为 3 ( 0x03 )，对于每个字符编码得到的结果为 ['d', 'o', 'g']，由于其长度为 3 个字节 小于 55 字节，在其结果前添加 0x80 + str_len = 0x80 + 0x03 = 0x83，所以有 ( len 函数用来输出输入的字节数 )：

1
2
3
len("dog") = 3 = 0x03
RLP("dog") = < 0x80 + len("dog"), 'd', 'o', 'g' >
           = < 0x83, 'd', 'o', 'g' >

另一个例子是字符串 "Lorem ipsum dolor sit amet, consectetur adipisicing elit"，其长度为 56 ( 0x38，一个字节 ) 大于 55，首先计算长度值 56 的字节数为 1:

1
2
3
4
5
str_len = len("Lorem ipsum dolor sit amet, consectetur adipisicing elit") 
        = 56 = 0x38
len_of_str_len 
    = len(len("Lorem ipsum dolor sit amet, consectetur adipisicing elit")) 
    = len(0x38) = 1 = 0x01

然后在每个字符编码结束后的结果前添加两部分，第一部分为 0x80 + 0x37 + 长度值的字节数 ( 占用一个字节 )，第二部分为 长度值 ( 占 长度值的字节数 个字节 )，所以有：

1
2
3
4
RLP("Lorem ipsum dolor sit amet, consectetur adipisicing elit") 
  = < 0x80 + 0x37 + len_of_str_len, str_len, 'L', 'o', ... , ' ', 'e', 'l', 'i', 't' >
  = < 0x80 + 0x37 + 0x01, 0x38, 'L', 'o', ... , ' ', 'e', 'l', 'i', 't' >
  = < 0xb8, 0x38, 'L', 'o', ... , ' ', 'e', 'l', 'i', 't' >

列表编码

对于列表使用下面规则进行编码：

  1. 首先需要对列表中的字符串和列表均进行编码 ( 字符串编码使用上一节的规则 ) 得到的列表是内部无嵌套的字节数组。
  2. 如果列表长度(字节数) list_len 在 0 到 55 字节，在列表中内容的 RLP 编码结果前添加一个字节，其值为 0xc0 + list_len。
  3. 如果列表长度 list_len 大于 55 字节，则需要：
    1. 首先得到列表长度十六进制表示的字节数 len_of_list_len。
    2. 在每个字节编码结束后的结果前添加两个部分，一个是 0xc0 + 0x37 + len_of_list_len, 另一个是 list_len 的字节编码形式结果。

以字符串数组 ["dog", "dog"] 举例，先对 dog 进行编码得到：

1
RLP("dog") = < 0x83, 'd', 'o', 'g' >

当前的字符串转化结果为：

1
2
["dog", "dog"] -> < 0x83, 'd', 'o', 'g', 0x83, 'd', 'o', 'g' >
len(< 0x83, 'd', 'o', 'g', 0x83, 'd', 'o', 'g' >) = 8

此时编码字节数为 8 ( 0x08 ) 个字节，小于 55 个字节，因此只需添加一个字节，其内容为 0xc0 + list_len，所以有：

1
2
3
4
RLP(["dog", "dog"]) = RLP([RLP("dog"), RLP("dog")])
                    = RLP([0x83, 'd', 'o', 'g', 0x83, 'd', 'o', 'g'])
                    = < 0xc0 + 0x08, 0x83, 'd', 'o', 'g', 0x83, 'd', 'o', 'g' >
                    = < 0xc8, 0x83, 'd', 'o', 'g', 0x83, 'd', 'o', 'g' >

对于较长的数组操作相似使用 3 中描述的方式添加前缀，不再赘述。

总结

对于字符串使用下面规则进行编码：

  1. 对于字符串中的一个字节的值，如果其值在 [0x00, 0x7f] 之间 ( 即 [0, 127]，为 ASCII 表中的字符的取值范围 )，其 RLP 编码值为其本身。
  2. 如果一个字符串长度 str_len 在 0 到 55 字节，还需要在字符串每个字符编码结束后的结果前添加一个字节，这个字节的值为 0x80 + str_len ( 即 128 + str_len，128 为偏移值 )。
  3. 如果一个字符串长度 str_len 大于 55 ( 0x37 ) 字节，则需要：
    1. 首先得到字符串长度十六进制表示的字节数 len_of_str_len。
    2. 在每个字节编码结束后的结果前添加两个部分，一个是 0x80 + 0x37 + len_of_str_len, 另一个是 str_len 的字节编码形式结果。

对于列表使用下面规则进行编码：

  1. 首先需要对列表中的字符串和列表均进行编码 ( 字符串编码使用上一节的规则 ) 得到的列表是内部无嵌套的字节数组。
  2. 如果列表长度(字节数) list_len 在 0 到 55 字节，在列表中内容的 RLP 编码结果前添加一个字节，其值为 0xc0 + list_len。
  3. 如果列表长度 list_len 大于 55 字节，则需要：
    1. 首先得到列表长度十六进制表示的字节数 len_of_list_len。
    2. 在每个字节编码结束后的结果前添加两个部分，一个是 0xc0 + 0x37 + len_of_list_len, 另一个是 list_len 的字节编码形式结果。

参考资料

RLP · ethereum/wiki Wiki

FEATURED TAGS
Blockchain Ethereum
FRIENDS