以太坊 RLP

admin 2019年08月15日

RLP(Recursive Length Prefix，递归的长度前缀)是一种编码规则，可用于编码任意嵌套的二进制数组数据。RLP 编码的结果也是二进制序列。RLP 主要用来序列化 / 反序列化数据。

一、RLP 数据定义

RLP 编码的定义只处理以下 2 类底层数据：

字符串（String）是指字节数组
列表（List）是指字节数组的数组
所有上层类型的数据需要转成以上的 2 类数据，才能进行 RLP 编码。转换的规则 RLP 编码不统一规定，可以自定义转换规则。从上面的数据类型定义中可以看出，RLP 编码的数据可看做 字节数组 和多维变长字节数组 。

二、编码规则

RLP 编码的重点是给原始数据前面添加若干字节的前缀，而且这个前缀是和数据的长度相关的，并且是递归的。

1. 针对单字节 b，b ∈ [0,127], Rc(b) = b

eg:Rc(a) = 97, Rc(w) = 119

**2. 针对字节数组 bytes，length(bytes) <= 55, Rc(bytes) =
128+length(bytes) ++ bytes(++ 符号表示拼接)**

eg:Rc(abc) = [131 97 98 99], 其中 131 = 128+length(abc), [97 98
99] 为[abc]本身编码

**3. 针对字节数组 bytes，length(bytes) > 55,
Rc(bytes) = 183+sizeof(sizeof(bytes)) ++ Rc(sizeof(bytes)) + bytes**

eg: str = "The length of this sentence is more than 55 bytes, I know
it because I pre-designed it"
Rc(str) = [184 86 84 104 101 32 108 101 110 103 116 104 32 111
102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32
109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32
73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32
112 114 101 45 100 101 115 105 103 110 101 100 32 105 116]
经计算该字符串占用字节数为 86，显然 184 = 183 + sizeof(86)，86 =
sizeof(str), 84 为“T”的编码，从 84 开始后面便是 str 本身的编码。

以上是针对字节数组，接下来看以字节数组为元素的数组，这里称之为列表的编码方式：

首先要明确几个概念，针对一个列表 list，lenL 是指 list 内每个 bytes 字节数的总和，lenDl 是指 list 每个 bytes 经过 Rc(x)编码后的总长度。

**lenL(list) =
$\sum\_{i=0}^Nsizeof(bytes\_i)$ )
lenDl(list) =
$\sum\_{i=0}^Nsizeof(Rc(bytes\_i))$ ))**
**4. 针对 list[bytes0, bytes1...bytesN]，lenL(list) \<= 55,\
Rc(list) = 192+lenDl(list) ++
Rc( $bytes\_i$ )**

eg: list = ["abc", "def"],\
Rc(list) = [200 131 97 98 99 131 100 101 102]\
首先，lenL(list) = 3+3 \<= 55,\
然后，根据 规则 3 可以得出：\
Rc[abc] = [131 97 98 99]，\
Rc[def] = 131 100 101 102\
现在就知道，lenDl(list) = 4 + 4 =
8，所以开始的 200 就是 192+ 8 的结构，后面跟的是 list 里每个 bytes 的 RLP 编码。

**5. 针对 list[bytes0, bytes1...bytesN]，lenL(list) \> 55,\
Rc(list) = 247+sizeof(lenDl(list)) ++ lenDl(list) ++
Rc( $bytes\_i$ )**

eg: list = ["The length of this sentence is more than 55 bytes,",\
"I know it because I pre-designed it"]\
Rc(list) = [248 88 179 84 104 101 32 108 101 110 103 116 104 32 111
102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32
109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32
163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32
73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116]\
首先，lenL(list) = 51+35 = 86 \> 55,\
然后，根据 规则 2 可以得出：\
Rc[The length of this sentence is more than 55 bytes,] = [179 84
104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115
101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97
110 32 53 53 32 98 121 116 101 115 44 32](179 = 128 + 51)，\
Rc[I know it because I pre-designed it]\
= [163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101
32 73 32 112 114 101 45 100 101 115 105 103 110 101 100 32 105 116](163
= 128 + 35)\
现在就知道，lenDl(list) = 52 + 36 =
88，88 只需占 1 个字节即可，所以开始的 248 就是 247+ 1 的结构，后面的 88 是 lenDl(list)本身的编码，再后面跟的是 list 里每个 bytes 的 RLP 编码。

RLP 解码

我们知道，有编码就有解码。编码是解码的一个逆过程，我们发现在编码的时候不同的情况都有一个不同的字节前缀，所以解码的时候也是从这个字节前缀入手。

设定 Dr(x)为解码函数，s 为 x 的第一个字节。\
subX[m,n]表示 x 的子串，从 x 的第 m 个开始取 n 个字节。\

bin2Int(bytes)表示将一个字节数组按 BigEndian 编码转换为整数，目的在于求出被编码字符串长度。

**1. s ∈ [0, 127], 对应编码规则 1 单字节解码，\
Dr(x) = x**
**2. s ∈ [128, 184), 对应编码规则 2，数组长度不超过 55\
Dr(x) = subX[2, s-128]**
**3. s ∈ [184, 192), 对应编码规则 3，数组长度超过 55\
bin2Int(subX[1, s-183])为被编码数组的长度 \
Dr(x) = subX[bin2Int(subX[1, s-183]+1, bin2Int(subX[1, s-183])]**
**4. s ∈ [192, 247), 对应编码规则 4，总长不超过 55 的列表列表总长 lenDl =
s-192，然后递归调用解码规则 1 - 3 即可 \
Dr(x) = ![\sum\_{i=0}^
NspliceOf(Dr(x\_i))](https://math.jianshu.com/math?formula=%5Csum_%7Bi%3D0%7D%5E%20NspliceOf(Dr(x_i)))**
**5. s ∈ [247, 256], 对应编码规则 5，总长超过 55 的列表, 列表总长 lenDl =
bin2Int(subX[1, s-247])，然后递归调用解码规则 1 - 3 即可 \
Dr(x) = ![\sum\_{i=0}^
NspliceOf(Dr(x\_i))](https://math.jianshu.com/math?formula=%5Csum_%7Bi%3D0%7D%5E%20NspliceOf(Dr(x_i)))**

RLP 源码

上面大概了解了 RLP 的编解码方式，下面我们就到 eth 源代码中去看看有关 RLP 的代码是怎么写的。

上篇文章主要介绍了 geth 源码结构，RLP 源码主要在 rlp 目录下。

RLP 源码结构

typeCache.go

该结构主要实现不同类型和对应编解码器的映射关系，通过它去获取对应的编解码器。

核心数据结构

// 核心数据结构
var (
typeCacheMutex sync.RWMutex    // 读写锁，用于在多线程时保护typeCache
typeCache      = make(map[typekey]*typeinfo)  // 保存类型 -> 编码器函数的数据结构
// Map的key是类型，value是对应的编码和解码器
)

type typeinfo struct {
decoder    // 解码器函数
writer     // 编码器函数
}

如何获取编码器和解码器的函数

// 获取编码器和解码器的函数
func cachedTypeInfo(typ reflect.Type, tags tags) (*typeinfo, error) {
typeCacheMutex.RLock()    // 加锁保护
info := typeCache[typekey{typ, tags}]    // 将传入的typ和tags封装为typekey类型
typeCacheMutex.RUnlock()  // 解锁
if info != nil {    // 成功获取到typ对应的编解码函数
return info, nil
}
// not in the cache, need to generate info for this type.
// 编解码不在typeCache中，需要创建该typ对应的编解码函数
typeCacheMutex.Lock()
defer typeCacheMutex.Unlock()
return cachedTypeInfo1(typ, tags)
}

// 新建typ对应的编解码函数
func cachedTypeInfo1(typ reflect.Type, tags tags) (*typeinfo, error) {
key := typekey{typ, tags}
info := typeCache[key]
if info != nil {
// another goroutine got the write lock first
/// 其他线程已经成功创建
return info, nil
}
// put a dummmy value into the cache before generating.
// if the generator tries to lookup itself, it will get
// the dummy value and won't call itself recursively.
// 这个地方首先创建了一个值来填充这个类型的位置，避免遇到一些递归定义的数据类型形成死循环
typeCache[key] = new(typeinfo)
info, err := genTypeInfo(typ, tags)    // 生成对应类型的编解码器函数
if err != nil {
// remove the dummy value if the generator fails
// 创建失败处理
delete(typeCache, key)
return nil, err
}
*typeCache[key] = *info
return typeCache[key], err
}

生成对应编解码器的函数

// 生成对应编解码器的函数
func genTypeInfo(typ reflect.Type, tags tags) (info *typeinfo, err error) {
info = new(typeinfo)
if info.decoder, err = makeDecoder(typ, tags); err != nil {
return nil, err
}
if info.writer, err = makeWriter(typ, tags); err != nil {
return nil, err
}
return info, nil
}

decode.go

typeCache 定义了类型与对应解编码器的映射关系，接下来就看看对应的编码和解码代码。

// 定义一些解码错误
var (
// EOL is returned when the end of the current list
// has been reached during streaming.
EOL = errors.New("rlp: end of list")

// Actual Errors
ErrExpectedString   = errors.New("rlp: expected String or Byte")
ErrExpectedList     = errors.New("rlp: expected List")
ErrCanonInt         = errors.New("rlp: non-canonical integer format")
ErrCanonSize        = errors.New("rlp: non-canonical size information")
ErrElemTooLarge     = errors.New("rlp: element is larger than containing list")
ErrValueTooLarge    = errors.New("rlp: value size exceeds available input length")
ErrMoreThanOneValue = errors.New("rlp: input contains more than one value")

// internal errors
errNotInList     = errors.New("rlp: call of ListEnd outside of any list")
errNotAtEOL      = errors.New("rlp: call of ListEnd not positioned at EOL")
errUintOverflow  = errors.New("rlp: uint overflow")
errNoPointer     = errors.New("rlp: interface given to Decode must be a pointer")
errDecodeIntoNil = errors.New("rlp: pointer given to Decode must not be nil")
)

// 解码器  根据不同的类型返回对应的解码器函数
func makeDecoder(typ reflect.Type, tags tags) (dec decoder, err error) {
kind := typ.Kind()
switch {
case typ == rawValueType:
return decodeRawValue, nil
case typ.Implements(decoderInterface):
return decodeDecoder, nil
case kind != reflect.Ptr && reflect.PtrTo(typ).Implements(decoderInterface):
return decodeDecoderNoPtr, nil
case typ.AssignableTo(reflect.PtrTo(bigInt)):
return decodeBigInt, nil
case typ.AssignableTo(bigInt):
return decodeBigIntNoPtr, nil
case isUint(kind):
return decodeUint, nil
case kind == reflect.Bool:
return decodeBool, nil
case kind == reflect.String:
return decodeString, nil
case kind == reflect.Slice || kind == reflect.Array:
return makeListDecoder(typ, tags)
case kind == reflect.Struct:
return makeStructDecoder(typ)
case kind == reflect.Ptr:
if tags.nilOK {
    return makeOptionalPtrDecoder(typ)
}
return makePtrDecoder(typ)
case kind == reflect.Interface:
return decodeInterface, nil
default:
return nil, fmt.Errorf("rlp: type %v is not RLP-serializable", typ)
}
}

根据以上 switch 方法可以调到各种解码函数。

encode.go

接下来来看看有关编码的代码解读。首先定义了两种特殊情况下的编码方式。

var (
// Common encoded values.
// These are useful when implementing EncodeRLP.
EmptyString = []byte{0x80}      // 针对空字符串的编码
EmptyList   = []byte{0xC0}      // 针对空列表的编码
)

接着定义了一个接口 EncodeRLP 供调用，但是很多情况下 EncodeRLP 会调用 Encode 方法。

type Encoder interface {
// EncodeRLP should write the RLP encoding of its receiver to w.
// If the implementation is a pointer method, it may also be
// called for nil pointers.
//
// Implementations should generate valid RLP. The data written is
// not verified at the moment, but a future version might. It is
// recommended to write only a single value but writing multiple
// values or no value at all is also permitted.
EncodeRLP(io.Writer) error
}

func Encode(w io.Writer, val interface{}) error {
if outer, ok := w.(*encbuf); ok {
// Encode was called by some type's EncodeRLP.
// Avoid copying by writing to the outer encbuf directly.
return outer.encode(val)
}
eb := encbufPool.Get().(*encbuf)    // 获取一个编码缓冲区encbuf
defer encbufPool.Put(eb)
eb.reset()
if err := eb.encode(val); err != nil {
return err
}
return eb.toWriter(w)
}

func (w *encbuf) encode(val interface{}) error {
rval := reflect.ValueOf(val)
ti, err := cachedTypeInfo(rval.Type(), tags{})
if err != nil {
return err
}
return ti.writer(rval, w)
}

makeWriter 作为一个 switch 形式的编码函数和上面的 makeDecoder 类似。

网站*

加入讨论吧...