这是以太坊源码研究的第一篇文章。基本上来说，我写什么内容，说明我正好在学习什么内容，并没有固定的顺序。之所以先写RLP编码，是因为在一开始研究以太坊交易结构的时候，就遇上RLP编码了，所谓拣上不如撞上，就从它开始吧。
RLP（Recursive Length Prefix）是以太坊中广泛运用的一种编码方法，用于序列化以太坊中各类对象。RLP可以把任意嵌套的二进制数据数组，都编码成为一个“扁平”的无嵌套的byte数组。
任意嵌套的二进制数据数组，可能是一个空字符串“”，可能是一个整数比如36，也可能是一个非常复杂的数据结构，比如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]。对于这些千变万化的数据，RLP到底是怎么进行编码的呢？其主要规则如下：
如果是单个字节，并且值在[0x00, 0x7f]范围内，则RLP编码就是它自己。这个好理解，不用解释。
如果是长度不超过55的字符串，那么RLP编码的第一个字节用来指定字符串长度，其值为0x80加上字符串长度，之后再跟整个字符串。因此，第一个字节值范围从0x80到0xb7，空字符串时为0x80，长度55的字符串为0x80+0x37=0xb7。
例：“dog"编码后为4个字节：[0x83, 'd', 'o', 'g']如果是长度超过55的字符串，这时字符串的长度可能会很长，甚至超过一个字节。RLP规定这种情况下，从第二个字节开始存储字符串的长度，将长度所花的字节数再加上0xb7的和作为第一个字节，字符串长度之后再跟字符串的内容。
例："Lorem ipsum dolor sit amet, consectetur adipisicing elit"字符串一共56个字节，编码结果为58字节：[ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]。其中，0x38即56为字符串长度，0xb8为0xb7+1，1就是0x38这个长度本身的长度也就是1个字节。如果是长度不超过55的列表，那么RLP编码的第一个字节是0xc0加上列表长度，后跟列表内容。因此，第一个字节值范围从0xc0到0xf7。
例： [ "cat", "dog" ]列表，编码后为[ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]。其中0xc8为0xc0+8，8就是两个字符串的总长度。如果是长度超过55的列表，那么RLP编码的第一个字节是0xf7加上列表长度的字节长度，后跟列表总长度，再跟列表项目内容的串联。因此，第一个字节的范围[0xf8, 0xff]。
再举个稍微复杂的例子：[ [ ], [ [ ] ], [ [ ], [ [ ] ] ] ] 的编码结果是 [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]。
编码过程用python语言来描述是下面这样的：
def rlp_encode(input):
if isinstance(input,str):
if len(input) == 1 and ord(input) < 0x80: return input
else: return encode_length(len(input), 0x80) + input
elif isinstance(input,list):
output = ''
for item in input: output += rlp_encode(item)
return encode_length(len(output), 0xc0) + output
def encode_length(L,offset):
if L < 56:
return chr(L + offset)
elif L < 256**8:
BL = to_binary(L)
return chr(len(BL) + offset + 55) + BL
else:
raise Exception("input too long")
def to_binary(x):
if x == 0:
return ''
else:
return to_binary(int(x / 256)) + chr(x % 256)
下面再看解码。解码其实就是编码的逆过程，每次读入第一个字节时判断其类型，计算出长度和偏移量，再解构具体数字。其具体规则如下：
如果第一个字节的范围是[0x00,0x7f]，则数据是一个字符串，且字符串本身就是第一个字节;
如果第一个字节的范围是[0x80,0xb7]，则数据是一个字符串，其长度等于第一个字节减去0x80，字符串内容在第一个字节之后;
如果第一个字节的范围是[0xb8,0xbf]，则数据是一个字符串，并且字节长度等于第一个字节减去0xb7，字符串长度在第一个字节之后，字符串跟随长度串;
如果第一个字节的范围是[0xc0,0xf7]，则数据是一个列表，其总长度等于第一个字节减去0xc0，列表中各项目的RLP编码的串联在第一个字节之后;
如果第一个字节的范围是[0xf8,0xff]，则数据是一个列表，字节长度等于第一个字节减去0xf7，列表总长度在第一个字节之后，再接下来是所有项目的RLP编码串联。
例子就不再举了。解码过程的python代码如下：
def rlp_decode(input):
if len(input) == 0: return
output = ''
(offset, dataLen, type) = decode_length(input)
if type is str: output = instantiate_str(substr(input, offset, dataLen))
elif type is list: output = instantiate_list(substr(input, offset, dataLen))
output + rlp_decode(substr(input, offset + dataLen))
return output
def decode_length(input):
length = len(input)
if length == 0: raise Exception("input is null")
prefix = ord(input[0])
if prefix <= 0x7f: return (0, 1, str)
elif prefix <= 0xb7 and length > prefix - 0x80:
strLen = prefix - 0x80
return (1, strLen, str)
elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
lenOfStrLen = prefix - 0xb7
strLen = to_integer(substr(input, 1, lenOfStrLen))
return (1 + lenOfStrLen, strLen, str)
elif prefix <= 0xf7 and length > prefix - 0xc0:
listLen = prefix - 0xc0;
return (1, listLen, list)
elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
lenOfListLen = prefix - 0xf7
listLen = to_integer(substr(input, 1, lenOfListLen))
return (1 + lenOfListLen, listLen, list)
else:
raise Exception("input don't conform RLP encoding form")
def to_integer(b):
length = len(b)
if length == 0: raise Exception("input is null")
elif length == 1: return ord(b[0])
else: return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256
好，RLP编码的算法搞清楚了，接下来回头看以太坊源码里，RLP编码和解码分别是怎么实现的。我用的是以太坊的Go语言版本源码。实际的实现过程很全很细，这里只挑主干。先看rlp/encode.go中的编码过程：
func EncodeToBytes(val interface{}) ([]byte, error) {
eb := encbufPool.Get().(*encbuf) //从encbuf池当中取出一个encbuf
defer encbufPool.Put(eb) //运算完了要把encbuf放回池中
eb.reset()
if err := eb.encode(val); err != nil { //调用实际的编码过程
return nil, err
}
return eb.toBytes(), nil //取得编码后的byte数组
}
encbuf是用来进行编码运算的结构，由于它会非常频繁地调用，为了提高效率，避免反复进行new和dispose，对其进行池化（顺便说一下，由此可见Go语言的效率当然远远超过python等脚本语言，直追C/C++）：
var encbufPool = sync.Pool{
New: func() interface{} { return &encbuf{sizebuf: make([]byte, 9)} },
}
encbuf类有4个数据成员。str是字节数组，包含所有内容但除了列表头；lheads里存放了所有的列表头；lhsize是所有列表头的总大小；sizebuf是编码期间用到的辅助缓存。除此之外还有一大堆成员函数，篇幅原因这里不一一解释了。重点看一下encode函数：
func (w *encbuf) encode(val interface{}) error {
rval := reflect.ValueOf(val) //取得val的Value
ti, err := cachedTypeInfo(rval.Type(), tags{}) //获取val的类型信息
if err != nil {
return err
}
return ti.writer(rval, w) //最后写入w，之后可以用toBytes()函数取得字节数组
}
reflect类似于.net中的反射。注意这里调用了cachedTypeInfo函数，它声明在typecache.go文件内，其内部调用了genTypeInfo函数，然后通过makeDecoder、makeWriter，根据不同的数据类型找到不同的编码和解码函数。以下是makeWriter函数的实现：
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)
}
}
我们从中抽选writeString来具体看看编码细节：
func writeString(val reflect.Value, w *encbuf) error {
s := val.String()
if len(s) == 1 && s[0] <= 0x7f {
w.str = append(w.str, s[0]) //直接编，不需要头
} else {
w.encodeStringHeader(len(s)) //长度大于1，或者首字符大于0x7f
w.str = append(w.str, s...)
}
return nil
}
Decode里相应的解码过程，其实就是编码过程的逆向工程，其算法过程这里不再详细介绍了。但需要注意的一点是，对于一个struct结构，它的数据成员可以带3个解码标志："tail", ”nil" 和 "-"。"-"标志代表忽略本字段，"nil"标志代表如果这个字段的size为0则改变其值为nil。看下面的代码：
input := []byte{0xC1, 0x80}
var normalRules struct {
String *string
}
Decode(bytes.NewReader(input), &normalRules)
fmt.Printf("normal: String = %q\n", *normalRules.String) //normal: String = ""
var withEmptyOK struct {
String *string `rlp:"nil"`
}
Decode(bytes.NewReader(input), &withEmptyOK)
fmt.Printf("with nil tag: String = %v\n", withEmptyOK.String) //with nil tag: String = <nil>
“tail"标志一般用在数组字段，表示余下的内容都存入这里。看下面的示例代码：
type structWithTail struct {
A, B uint
C []uint `rlp:"tail"`
}
var val structWithTail
err := Decode(bytes.NewReader([]byte{0xC4, 0x01, 0x02, 0x03, 0x04}), &val)
fmt.Printf("with 4 elements: err=%v val=%v\n", err, val)
// with 4 elements: err=<nil> val={1 2 [3 4]}
err = Decode(bytes.NewReader([]byte{0xC6, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06}), &val)
fmt.Printf("with 6 elements: err=%v val=%v\n", err, val)
// with 6 elements: err=<nil> val={1 2 [3 4 5 6]}
err = Decode(bytes.NewReader([]byte{0xC1, 0x01}), &val)
fmt.Printf("with 1 element: err=%q\n", err)
// with 1 element: err="rlp: too few elements for rlp.structWithTail"
全文结束。
说不出来写不出来，那就说明没学到家。
