這是以太坊源碼研究的第一篇文章±？ǎ基本上來說溢豆，我寫什么內容，說明我正好在學習什么內容瘸羡，并沒有固定的順序漩仙。之所以先寫RLP編碼，是因為在一開始研究以太坊交易結構的時候，就遇上RLP編碼了讯赏，所謂揀上不如撞上垮兑，就從它開始吧。
RLP（Recursive Length Prefix）是以太坊中廣泛運用的一種編碼方法漱挎，用于序列化以太坊中各類對象。RLP可以把任意嵌套的二進制數據數組雀哨，都編碼成為一個“扁平”的無嵌套的byte數組磕谅。
任意嵌套的二進制數據數組，可能是一個空字符串“”雾棺，可能是一個整數比如36膊夹，也可能是一個非常復雜的數據結構，比如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]捌浩。對于這些千變萬化的數據放刨，RLP到底是怎么進行編碼的呢？其主要規(guī)則如下：
如果是單個字節(jié)尸饺，并且值在[0x00, 0x7f]范圍內进统，則RLP編碼就是它自己。這個好理解浪听，不用解釋螟碎。
如果是長度不超過55的字符串，那么RLP編碼的第一個字節(jié)用來指定字符串長度迹栓，其值為0x80加上字符串長度掉分，之后再跟整個字符串。因此克伊，第一個字節(jié)值范圍從0x80到0xb7酥郭，空字符串時為0x80，長度55的字符串為0x80+0x37=0xb7愿吹。
例：“dog"編碼后為4個字節(jié)：[0x83, 'd', 'o', 'g']如果是長度超過55的字符串不从，這時字符串的長度可能會很長，甚至超過一個字節(jié)洗搂。RLP規(guī)定這種情況下消返，從第二個字節(jié)開始存儲字符串的長度，將長度所花的字節(jié)數再加上0xb7的和作為第一個字節(jié)耘拇，字符串長度之后再跟字符串的內容撵颊。
例："Lorem ipsum dolor sit amet, consectetur adipisicing elit"字符串一共56個字節(jié)，編碼結果為58字節(jié)：[ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]惫叛。其中倡勇，0x38即56為字符串長度，0xb8為0xb7+1嘉涌，1就是0x38這個長度本身的長度也就是1個字節(jié)妻熊。如果是長度不超過55的列表夸浅，那么RLP編碼的第一個字節(jié)是0xc0加上列表長度，后跟列表內容扔役。因此帆喇，第一個字節(jié)值范圍從0xc0到0xf7。
例： [ "cat", "dog" ]列表亿胸，編碼后為[ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]坯钦。其中0xc8為0xc0+8，8就是兩個字符串的總長度侈玄。如果是長度超過55的列表婉刀，那么RLP編碼的第一個字節(jié)是0xf7加上列表長度的字節(jié)長度，后跟列表總長度序仙，再跟列表項目內容的串聯突颊。因此，第一個字節(jié)的范圍[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)
下面再看解碼。解碼其實就是編碼的逆過程挥等，每次讀入第一個字節(jié)時判斷其類型友绝，計算出長度和偏移量，再解構具體數字肝劲。其具體規(guī)則如下：
如果第一個字節(jié)的范圍是[0x00,0x7f]迁客，則數據是一個字符串，且字符串本身就是第一個字節(jié);
如果第一個字節(jié)的范圍是[0x80,0xb7]辞槐，則數據是一個字符串掷漱，其長度等于第一個字節(jié)減去0x80，字符串內容在第一個字節(jié)之后;
如果第一個字節(jié)的范圍是[0xb8,0xbf]榄檬，則數據是一個字符串卜范，并且字節(jié)長度等于第一個字節(jié)減去0xb7，字符串長度在第一個字節(jié)之后鹿榜，字符串跟隨長度串;
如果第一個字節(jié)的范圍是[0xc0,0xf7]海雪，則數據是一個列表，其總長度等于第一個字節(jié)減去0xc0舱殿，列表中各項目的RLP編碼的串聯在第一個字節(jié)之后;
如果第一個字節(jié)的范圍是[0xf8,0xff]奥裸，則數據是一個列表，字節(jié)長度等于第一個字節(jié)減去0xf7沪袭，列表總長度在第一個字節(jié)之后湾宙，再接下來是所有項目的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是字節(jié)數組蒿叠，包含所有內容但除了列表頭；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()函數取得字節(jié)數組
}
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來具體看看編碼細節(jié)：
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"
全文結束枪汪。
說不出來寫不出來涌穆，那就說明沒學到家。
