RLP(Recursive Length Prefix侮东，遞歸長度前綴)是一種編碼算法，用于編碼任意的嵌套結(jié)構(gòu)的二進(jìn)制數(shù)據(jù)豹芯，它是以太坊中數(shù)據(jù)序列化/反序列化的主要方法悄雅，區(qū)塊、交易等數(shù)據(jù)結(jié)構(gòu)在持久化時(shí)會(huì)先經(jīng)過RLP編碼后再存儲(chǔ)到數(shù)據(jù)庫中铁蹈。

定義

RLP編碼的定義只處理兩類數(shù)據(jù)：一類是字符串（例如字節(jié)數(shù)組）宽闲，一類是列表。字符串指的是一串二進(jìn)制數(shù)據(jù)，列表是一個(gè)嵌套遞歸的結(jié)構(gòu)容诬，里面可以包含字符串和列表娩梨，例如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]就是一個(gè)復(fù)雜的列表。其他類型的數(shù)據(jù)需要轉(zhuǎn)成以上的兩類览徒，轉(zhuǎn)換的規(guī)則不是RLP編碼定義的狈定，可以根據(jù)自己的規(guī)則轉(zhuǎn)換，例如struct可以轉(zhuǎn)成列表吱殉，int可以轉(zhuǎn)成二進(jìn)制（屬于字符串一類）掸冤，以太坊中整數(shù)都以大端形式存儲(chǔ)。

從RLP編碼的名字可以看出它的特點(diǎn)：一個(gè)是遞歸友雳，被編碼的數(shù)據(jù)是遞歸的結(jié)構(gòu)稿湿，編碼算法也是遞歸進(jìn)行處理的；二是長度前綴押赊，也就是RLP編碼都帶有一個(gè)前綴饺藤，這個(gè)前綴是跟被編碼數(shù)據(jù)的長度相關(guān)的，從下面的編碼規(guī)則中可以看出這一點(diǎn)流礁。

RLP編碼規(guī)則

對(duì)于單個(gè)字節(jié)涕俗，如果它的值范圍是[0x00, 0x7f]，它的RLP編碼就是它本身神帅。

否則再姑，如果一個(gè)字符串的長度是0-55字節(jié)，它的RLP編碼包含一個(gè)單字節(jié)的前綴找御，后面跟著字符串本身元镀，這個(gè)前綴的值是0x80加上字符串的長度。由于被編碼的字符串最大長度是55=0x37,因此單字節(jié)前綴的最大值是0x80+0x37=0xb7霎桅，即編碼的第一個(gè)字節(jié)的取值范圍是[0x80, 0xb7]栖疑。

如果字符串的長度大于55個(gè)字節(jié)，它的RLP編碼包含一個(gè)單字節(jié)的前綴滔驶，后面跟著字符串的長度遇革，后面再跟著字符串本身。這個(gè)前綴的值是0xb7加上字符串長度的二進(jìn)制形式的字節(jié)長度揭糕，說的有點(diǎn)繞萝快，舉個(gè)例子就明白了，例如一個(gè)字符串的長度是1024著角，它的二進(jìn)制形式是10000000000杠巡，這個(gè)二進(jìn)制形式的長度是2個(gè)字節(jié)，所以前綴應(yīng)該是0xb7+2=0xb9雇寇，字符串長度1024=0x400，因此整個(gè)RLP編碼應(yīng)該是\xb9\x04\x00再跟上字符串本身。編碼的第一個(gè)字節(jié)即前綴的取值范圍是[0xb8, 0xbf]锨侯，因?yàn)樽址L度二進(jìn)制形式最少是1個(gè)字節(jié)嫩海，因此最小值是0xb7+1=0xb8，字符串長度二進(jìn)制最大是8個(gè)字節(jié)囚痴，因此最大值是0xb7+8=0xbf叁怪。

如果一個(gè)列表的總長度（列表的總長度指的是它包含的項(xiàng)的數(shù)量加它包含的各項(xiàng)的長度之和）是0-55字節(jié)，它的RLP編碼包含一個(gè)單字節(jié)的前綴深滚，后面跟著列表中各元素項(xiàng)的RLP編碼奕谭，這個(gè)前綴的值是0xc0加上列表的總長度。編碼的第一個(gè)字節(jié)的取值范圍是[0xc0, 0xf7]痴荐。

如果一個(gè)列表的總長度大于55字節(jié)血柳，它的RLP編碼包含一個(gè)單字節(jié)的前綴，后面跟著列表的長度生兆，后面再跟著列表中各元素項(xiàng)的RLP編碼难捌，這個(gè)前綴的值是0xf7加上列表總長度的二進(jìn)制形式的字節(jié)長度。編碼的第一個(gè)字節(jié)的取值范圍是[0xf8, 0xff]鸦难。

RLP編碼例子

字符串"dog" = [0x83, 'd', 'o', 'g' ]（規(guī)則二）

列表["cat","dog"] = [0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]（規(guī)則四）

空字符串"" = 0x80（規(guī)則二）

空列表[] = [0xc0]（規(guī)則四）

整數(shù)15('\x0f') = 0x0f（規(guī)則一）

整數(shù)1024('\x04\00') = [0x82, 0x04, 0x00]（規(guī)則二）

列表[ [], [[]], [ [], [[]] ] ] = [0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0]（規(guī)則四）

字符串"Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't']（規(guī)則三）

本文大部分翻譯自以太坊github wiki文檔根吁，并加入自己的理解。

參考資料：https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-RLP