RLP(Recursive Length Prefix),递归长度前缀编码,它是以太坊序列化所采用的序列化和反序列化的主要方式。区块、交易等数据结构在 网络传输和持久化时会先经过 RLP 编码后再存储到数据库中。rlp 适用于任意的二进制数据数组的编码,在以太坊中,rpl 接受的数据分为两类:1.字节数组 2.类 list 数据结构。

以太坊中 rlp 的具体定义和规则我们可以在黄皮书中找到(Appendix B. Recursive Length Prefix):

  • 序列化定义 1532341583673

    * **O** 所有byte的集合
    * **B** 所有可能字节数组
    * **L** 不只单一节点的树形结构(比如结构体或者树节点分支节点,非叶子节点)
    * **T** 所有字节数组的树形结构组合
    
  • 序列化处理 1532341606589 通过两个子函数定义 RLP 分别处理上面说的两种数据类型

  • Rb(x)字节数组序列化处理规则 1532341627515

    • 如果字节数组只包含一个字节(对于 [0x00, 0x7f] 范围内的单个字节),而且这个字节的大小小于 128,那么不对数据进行处理,处理结果就是原数据,比如:a 的编码是 97
    • 如果字节数组的长度小于 56,那么处理结果就等于在原始数据前面加上(128+字节数据的长度)的前缀,比如 abc 编码结果是 131 97 98 99,其中 131=128+len(“abc”),97 98 99 依次是 a b c
    • 如果不是上面两种情况,那么处理结果就等于在原始数据前面加上原始数据长度的大端表示,然后在前面加上(183 + 原始数据大端表示的长度),比如编码下面这段字符串The length of this sentence is more than 55 bytes, I know it because I pre-designed it编码结果如下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,其中前三个字节的计算方式如下:1. 184 = 183 + 1,因为数组长度 86 编码后仅占用一个字节; 2. 86 即数组长度 86

    关于大端小端的理解可以参考《理解字节序》比较浅显易懂。关于公式中的一些数学符号的解释:

    • ||x|| 代表了求 x 的长度
    • (a).(b,c).(d,e) = (a,b,c,d,e) 代表了 concat 的操作,也就是字符串的相加操作。 “hello “+“world” = “hello world”
    • BE(x)函数表示去掉了前导 0 的大端模式。 比如 4 个字节的整形 0x1234 用大端模式来表示是 00 00 12 34 那么用 BE 函数处理之后返回的其实是 12 34. 开头的多余的 00 被去掉了。
    • ^ 符号代表并且的含义。
    • ≡ ,恒等于
  • Rl(x) 其他类型(树型结构)数据序列化处理规则 1532341641762 _ 如果连接后的字节长度小于 56, 那么在连接后的结果前面加上(192 + 连接后的长度),组成最终的结果。比如:[“abc”, “def”]的编码结果是 200 131 97 98 99 131 100 101 102。其中 abc 的编码为 131 97 98 99,def 的编码为 131 100 101 102。两个子字符串的编码后总长度是 8,因此编码结果第一位计算得出:192 + 8 = 200。 _ 如果连接后的字节长度大于等于 56, 那么就在连接后的结果前面先加上连接后的长度的大端模式,然后在前面加上(247 + 连接后长度的大端模式的长度)比如:["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]的编码结果是: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,其中前两个字节的计算方式如下:1. 248 = 247 +1; 2. 88 = 86 + 2,在Rb(x)3示例中,长度为 86,而在此例中,由于有两个子字符串,每个子字符串本身的长度的编码各占 1 字节,因此总共占 2 字节。第 3 个字节 179 依据Rb(x)规则2得出 179 = 128 + 51 第 55 个字节 163 同样Rb(x)2得出 163 = 128 + 35

    上面是一个递归的定义, 在求取s(x)的过程中又调用了RLP方法,这样使得RLP能够处理递归的数据结构。通过一个复杂的例子来理解一下递归长度前缀:
    `["abc",["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]]`
    编码后的结果:
    `248 94 131 97 98 99 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`
    列表第一项字符串abc依据`Rb(x)规则2`,编码结果为131 97 98 99,长度为4。
    列表第二项也是一个列表项:
    `["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]`
    根据`Rl(x)规则2`,结果为
    `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`
    长度为90,因此,整个列表的编码结果第二位是90 + 4 = 94, 占用1个字节,第一位247 + 1 = 248
    
  • 标量数据处理 1532341655523 使用 RLP 处理标量数据,也就是基本的数据,RLP 只能够用来处理正整数。 RLP 只能处理大端模式处理后的整数。 也就是说如果是一个整数 x,那么先使用 BE(x)函数来把 x 转换成最简大端模式(去掉了开头的 00),然后把 BE(x)的结果当成是字节数组来进行编码。

上面就是 RLP 的编码定义,下面开始我们来看一下以太坊中的实现源码。 ###代码文件结构

rlp
├── decode.go               // 解码器
├── decode_tail_test.go     // 解码示例
├── decode_test.go          // 解码器测试用例
├── doc.go                  // 文档代码
├── encode.go               // 编码器
├── encode_test.go          // 编码器测试用例
├── encoder_example_test.go // 编码器示例
├── raw.go                  // 处理编码后rlp数据,比如计算长度、分离、值计数等
├── raw_test.go             // raw测试用例
└── typecache.go            // 类型缓存,记录数据类型->编码器|解码器的映射

可以直接从示例 encoder_example_test.go 中来看,这个示例中实现了一个如何通过 rlp 编码 struct 的调用:

type MyCoolType struct {
	Name string
	a, b uint
}

func (x *MyCoolType) EncodeRLP(w io.Writer) (err error) {
	if x == nil {
	// 结构体为空指针,编码{0, 0}
		err = Encode(w, []uint{0, 0})
	} else {
	// 编码指定的值
		err = Encode(w, []uint{x.a, x.b})
	}
	return err
}

func ExampleEncoder() {
	var t *MyCoolType
	bytes, _ := EncodeToBytes(t)   // t MyCoolType为nil编码为字节数组
	fmt.Printf("%v → %X\n", t, bytes)

	t = &MyCoolType{Name: "foobar", a: 5, b: 6}
	bytes, _ = EncodeToBytes(t)    // t 为struct
	fmt.Printf("%v → %X\n", t, bytes)

	// Output:
	// <nil> → C28080
	// &{foobar 5 6} → C20506
}

通过上面的测试用例代码,可以看到EncodeToBytes就是编码的函数,往下走,看一下编码器具体实现 encode.go

var (
	EmptyString = []byte{0x80}
	EmptyList   = []byte{0xC0}
)

// Encoder is implemented by types that require custom
// encoding rules or want to encode private fields.
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
}

首先定义了空字符串和空列表的值,定义了Encoder接口,我们可以看到上面的 MyCoolType 就实现了该接口的 EncodeRLP 方法,继续往下看 EncodeToBytes 的具体实现:

// EncodeToBytes 返回RLP编码后的值.
func EncodeToBytes(val interface{}) ([]byte, error) {
	eb := encbufPool.Get().(*encbuf)   // 从encbufPool池中获取encbuf实例
	defer encbufPool.Put(eb)           // 调用结束以后重新放入池中
	eb.reset()                         // 初始化encbuf
	if err := eb.encode(val); err != nil { // 对数据编码
		return nil, err
	}
	return eb.toBytes(), nil   //将编码后的数据和头部拼接成byte[]后返回
}

encbufPool 是一个 sync.Pool,可以通过一个资源池来提高编码效率,减少资源浪费。来看下 encbuf 的结构定义:

type encbuf struct {
	str     []byte      // 包含了除了列表的头部的所有的编码的内容
	lheads  []*listhead // 所有的列表头
	lhsize  int         // lheads的长度
	sizebuf []byte      // 9个字节大小的辅助buffer,用来处理uint的编码
}

type listhead struct {
	offset int // 记录了列表数据在str字段的起始位置
	size   int // 编码数据的总长度 (包括列表头)
}

encbuf 看起来是在编码过程的一个 buffer 的作用,其定义了一些 encode 过程中的操作方法,具体每个函数的实现不做代码分析了,这里大略说一下每个函数的作用:

  • encode(val interface{}) error 编码函数
  • (w *encbuf) encodeString(b []byte) 将编码后的原始数据连接到已编码内容之后
  • encodeStringHeader(size int) 将头部结构体中新编码后的元素和之前已经编码的内容连接
  • list() *listhead 保存每个元素编码后的头部 lheads 信息
  • listEnd(lh *listhead) 编码连接后的长度 lhsize 统计
  • reset() encbuf 初始化
  • size() int 计算编码后内容和头部长度之和
  • toBytes() []byte 将每个头部 lheads 连接到对应的编码数据后
  • toWriter(out io.Writer) (err error) 通过 io 流将编码后头部写到编码后,
  • Write(b []byte) (int, error) 实现 io.Writer 接口,以便于可以传入 EncodeRLP

继续上面的 EncodeToBytes 函数,我来看一下eb.encode(val)编码函数具体做了什么:

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)
}

首先通过 reflect 反射机制获取编码值的类型,后和 tags 一起传入cachedTypeInfo,往下看 cachedTypeInfo 做了什么typecache.go

var (
	typeCacheMutex sync.RWMutex    // 读写锁
	typeCache      = make(map[typekey]*typeinfo)// 类型->编码|解码函数的映射,不同的数据类型对应不同的编码和解码方法
)

type typeinfo struct {
	decoder    // 解码
	writer     // 编码
}

type tags struct {
	nilOK bool     // 是否为空值
	tail bool      // 该字段是否含其他列表元素。它只能设置为最后一个字段,该字段必须是切片类型。
	ignored bool   // 是否忽略
}

type typekey struct {
	reflect.Type   // 数据类型
	tags   // 根据tags可能会生成不同的解码器。
}

type decoder func(*Stream, reflect.Value) error

type writer func(reflect.Value, *encbuf) error

func cachedTypeInfo(typ reflect.Type, tags tags) (*typeinfo, error) {
	typeCacheMutex.RLock() // 加读锁
	info := typeCache[typekey{typ, tags}]  // 从缓存中获取编码解码器
	typeCacheMutex.RUnlock()
	if info != nil {
		return info, nil
	}
	// 缓存中没有时通过type和tags生成编码解码器
	typeCacheMutex.Lock()
	defer typeCacheMutex.Unlock()
	return cachedTypeInfo1(typ, tags)
}

cachedTypeInfo 函数主要是从缓存中来根据数据类型来获取编码解码器,如果不存在时就通过cachedTypeInfo1 来创建一个对应类型的编码解码器,这里需要注意的 typeCacheMutex 进程锁来避免多线程资源保护和互斥,下面继续看下cachedTypeInfo1如何根据 typekey 来创建 typeinfo 的:

func cachedTypeInfo1(typ reflect.Type, tags tags) (*typeinfo, error) {
	key := typekey{typ, tags}
	info := typeCache[key]
	if info != nil {
		// 另外一个协程首先获得锁,再次验证避免多进程并发请求
		return info, nil
	}

	typeCache[key] = new(typeinfo)
	info, err := genTypeInfo(typ, tags)
	if err != nil {
		// 生成失败清除空间
		delete(typeCache, key)
		return nil, err
	}
	*typeCache[key] = *info
	return typeCache[key], err
}

该函数并不是实际创建缓存的函数,其中调用了genTypeInfo函数,顺着往下看:

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
}

显而易见,这里分别调用makeDecodermakeWriter来创建解码和编码,我们来看下编码器的实现encode.go:

// 通过类型和tags创建对应的具体编码函数
func makeWriter(typ reflect.Type, ts tags) (writer, error) {
	kind := typ.Kind()
	switch {
	case typ == rawValueType:
		return writeRawValue, nil
	case typ.Implements(encoderInterface):
		return writeEncoder, nil
	case kind != reflect.Ptr && reflect.PtrTo(typ).Implements(encoderInterface):
		return writeEncoderNoPtr, nil
	case kind == reflect.Interface:
		return writeInterface, nil
	case typ.AssignableTo(reflect.PtrTo(bigInt)):
		return writeBigIntPtr, nil
	case typ.AssignableTo(bigInt):
		return writeBigIntNoPtr, nil
	case isUint(kind):
		return writeUint, nil
	case kind == reflect.Bool:
		return writeBool, nil
	case kind == reflect.String:
		return writeString, nil
	case kind == reflect.Slice && isByte(typ.Elem()):
		return writeBytes, nil
	case kind == reflect.Array && isByte(typ.Elem()):
		return writeByteArray, nil
	case kind == reflect.Slice || kind == reflect.Array:
		return makeSliceWriter(typ, ts)
	case kind == reflect.Struct:
		return makeStructWriter(typ)
	case kind == reflect.Ptr:
		return makePtrWriter(typ)
	default:
		return nil, fmt.Errorf("rlp: type %v is not RLP-serializable", typ)
	}
}

这个函数很简单,通过 type 来设置对应的具体编码器,注意一下 ts 也就是 tags 参数,只有类型为 slice 和 array 时候才会用到,具体每个类型对应的编码器实现就不一一分析了,很值得每一个源码看一下,加深一下对上面黄皮书定义的规则的理解。对于结构体的编码在黄皮书中并没有公式定义,我们来看下源码了解一下:

type field struct {
	index int
	info  *typeinfo
}

func makeStructWriter(typ reflect.Type) (writer, error) {
	fields, err := structFields(typ) // 通过typ.NumField反射机制来解析struct结构,并获取每个字段的解码器
	if err != nil {
		return nil, err
	}
	writer := func(val reflect.Value, w *encbuf) error {
		lh := w.list()
		for _, f := range fields {
		  //f是field结构, f.info是typeinfo的指针, 所以f.info.writer就是调用字段的编码器方法
			if err := f.info.writer(val.Field(f.index), w); err != nil {
				return err
			}
		}
		w.listEnd(lh)
		return nil
	}
	return writer, nil
}

structFields 方法中通过 reflect.Type 的 NumField 获取其 Field,然后调用 cachedTypeInfo1 来获取每个 Field 的编码器,所以这是一个递归的调用。最后遍历 Field 的数组 fields,调用 f.info.writer 具体的编码器来编码。 我们继续回到encoder_example_test.go来看下示例中

var t *MyCoolType
bytes, _ := EncodeToBytes(t)

这里的 t 是 MyCoolType 的一个指针,MyCoolType 实现了 EncodeRLP 的接口,根据makeWriter中的 case 找到typ.Implements(encoderInterface)分支,调用了writeEncoder:

func writeEncoder(val reflect.Value, w *encbuf) error {
	return val.Interface().(Encoder).EncodeRLP(w)
}

这里直接调用了EncodeRLP(w)接口方法,从上面的示例代码中看,那么就是调用Encode(w, []uint{0, 0}),我们上面分析过了,encbuf 实现了 io.Writer 接口的 Writer 方法,这里的 w 就是 encbuf:

func Encode(w io.Writer, val interface{}) error {
	if outer, ok := w.(*encbuf); ok {
	   // 如果是*encbuf类型,则直接返回outer.encode
			return outer.encode(val)
	}

	eb := encbufPool.Get().(*encbuf)
	defer encbufPool.Put(eb)
	eb.reset()
	if err := eb.encode(val); err != nil {
		return err
	}
	w是io.Writer,eb.toWriter(w)流
	return eb.toWriter(w)
}

这样一个 rlp 的编码过程就解析完了,解码就是一个逆向的过程,不继续分析了,要理解黄皮书中的规则,还是需要看下makeWriter中的每一个类型对应的编码的具体实现代码。

转载请注明: 转载自Ryan 是菜鸟 | LNMP 技术栈笔记

如果觉得本篇文章对您十分有益,何不 打赏一下

谢谢打赏

本文链接地址: 以太坊源码分析–RLP 编码

知识共享许可协议 本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可