5分鐘深入了解以太坊編碼原理

2019-07-22

以太坊編碼原理－RLP回歸前綴長度編碼

Recursive Length Prefix（RLP）在以太坊中使用目的是將輸入的項目編碼成序列化的格式，在介紹 RLP 的編碼規則前，建議參照ASCII的編碼表，ASCII編碼工具，與10進制與16進制的轉換工具以幫助理解。RLP編碼主要用於以太坊中資料傳輸與鏈上的儲存。其主要編碼特色是將長度與類型作為數據的前綴(prefix)。

RLP編碼只能處理字串(String)與列表(List)

幾個可以做RLP編碼的例子：

“dog”
[“cat”, “dog”]
[ [], [[]], [ [], [[]] ] ]
[“cat”, [“dog”, “duck”], “bird”, [[]] , [“”], “bunny”]

而其他的數據類型像是struct可以轉成列表，int可以轉成二進制(字串類型)，且在以太坊中的整數皆以大端模式表示，並去掉前導的0，例如4個byte的數0x1234用大端模式表示後為 00 00 12 34，去掉0後代表將開頭的0全部去掉，僅回傳12 34的值，若不了解大端與小端可以在這篇文章中找到更詳細的解釋。

RLP編碼（RLP Encoding）

首先針對字串類型，以太坊黃皮書中的附錄中介紹了3個規則：

字串類的編碼規則（一）：

若目標字串為單個 byte 時，且值的範圍為 [0x00,0x7f] 時，編碼其實就是 ASCII 的編碼，所以在0x7f之內當成 ASCII 使用，圖一中為 ASCII 在 [0x00,0x7f] 的編碼表(十進制的0~127)。

規則一公式可以寫成：

其中R_b(x)代表經由RLP編碼的函數，且輸入為字串（或是byte array）類型，而 ||x|| = 1 代表字串長度為1（單個byte），x[0] < 128則代表字串的值在0~127之間（16進制的[0x00, 0x7f]），^ 代表and的意思（需要上述兩者條件皆達成）。

舉個例子來說：

“c” => [0x63] (string)
“a” => [0x61] (string)
“t” => [0x74] (string)
126 => [0x7e] (int)

字串類的編碼規則（二）：

若目標的字串長度在0~55 byte，RLP編碼後會多一個byte的前綴，再接著字串本身的ASCII的編碼。前綴值為0x80再加上目標字串的長度（接續規則一範圍的0x7f之後），而前綴的最大值是發生在目標字串長度為55byte時，55會先轉換到16進制表示為37，因此前綴最大值是0x80+0x37 = 0xb7，也因此我們可以了解到編碼後前綴值的範圍一定會落在[0x80, 0xb7]。

規則二公式可以寫成

其中(128 + ||x|| )則代表上述提到的前綴值，128(0x80) 加上字串的長度，且長度在0 ~ 55的範圍內（前綴值域為[0x80, 0xb7])，而 x 則為原字串本身的ASCII編碼，並cascade在一起（例如： (a)(b, c)(d, e) = (a, b, c, d, e) ）

舉個例子來說：

“dog” = [0x83, ”d”, “o”, “g”] => ( 83 64 6f 67 )_hex
其中0x83 = 0x80 + 3( “dog” 字串的長度)

字串類的編碼規則（三）：

若字串長度大於55byte，RLP編碼後會有兩個byte的前綴，第一個byte為183(0xb7)加上目標字串長度值的長度，聽起來有些拗口，下面我們將直接用例子解釋，而第二個前綴則是字串的長度，最後才跟著原數據的ASCII編碼。此外前綴1限制在1個byte的長度，因此前綴1的值域為[0xb8, 0xbf]。

規則三的公式可以寫成

其中BE( ||x|| )代表原數據x的數據長度以大端模式表示後再將前導的0刪除的函數，而 || BE( ||x|| ) ||則是將得到的長度數據取位元長度的值。

舉例來說：

“Lorem ipsum dolor sit amet, consectetur adipisicing elit” 具有56個字元則數據長度為56byte，前綴2可以馬上得到為56取轉16進制的結果：(38)_hex，而前綴1則為 (38)_hex所佔的數據長度為1byte，因此可以得到是183 + 1 = 184 => (b8)_hex，並在後面加上經ASCII編碼後的原數據。

轉換的過程可以參考圖二的流程圖清楚了解。

再來看看RLP針對列表類的編碼規則，規則有兩個：

列表類的編碼規則（一）：

若目標的列表的總長度（包含列表中所有元素經 RLP 編碼後的長度和）在0~55 byte的範圍內，而列表的前綴為192(0xc0) + 列表的總長度，且前綴的最大值是發生在目標列表總長度為55byte時，則 c0 + 37 = f7，可以得到前綴的範圍為[0xc0, 0xf7]，注意：每個列表中的元素也會分別進行RLP的編碼。

規則一公式可以寫成

其中 R_l(x) 代表經由 RLP 編碼的函數，且輸入為列表（List）類型，而 s(x) 代表列表中的每一個元素進行 RLP 的編碼並cascade在一起（ s(x) = RLP(x₀)RLP(x₁)… ），得到合併後的編碼值s(x)後，將s(x)的長度 ||s(x)|| 加上 192(0xc0) 得出列表的前綴，最後在併入 s(x) 的第一項中。

舉例來說：

當目標列表為 [“cat”,”dog”,”p”]，首先需先將列表中的每一個元素進行 RLP 編碼，再來合併每個元素的編碼值並得出編碼的總長度，最後將長度值加上192(0xc0) 得出前綴，可以參考圖三中有詳細的流程。

列表類的編碼規則（二）：

若目標列表長度大於等於56時，列表產生兩個 byte 的前綴，其中第二個 byte 的前綴為列表中所有元素取 RLP 編碼值再連結後的長度，而第一的 byte 的前綴為長度值的長度加上 247(0xf7)。而前綴1限制在1個 byte 的長度，因此前綴1的值域為 [0xf8, 0xff]。

規則二公式可以表示為

其中 (247 + || BE( ||s(x)|| ) ||) 為第一個前綴，將連接後的編碼值長度取大端式的長度，再接上編碼值取大端模式的長度，最後接上連接後的編碼值。

舉個例子：

目標列表為[“The length of this sentence is more than 55 bytes, “, “I know it because I pre-designed it”]，而圖四可以直接看到完整的流程。

RLP解碼（RLP Decoding）

解碼過程很簡單，首先可以透過前綴的值域得出數據的類型與長度：

[0x00, 0x7f]：數據為字串(string)，且為單個字符
[0x80, 0xb7]：數據為字串(string)，且字串長度短(小於等於55個字符)
[0xb8, 0xbf]：數據為字串(string)，且字串長度長(大於56個字符)
[0xc0, 0xf7]：數據為列表(list)，且列表短
[0xf8, 0xff]：數據為列表(list)，且列表長

因此從第一個數開始解碼，將會得到前綴所對應的數據範圍（元素）。

舉例來說：
經RLP編碼後的數據為：(c9 83 63 61 74 83 64 6f 67 70)_hex。

首先編碼從0xc9得知數據為列表，且列表編碼連結後的總長為9 (c9 – c0 = 9)，由於列表不長(小於55)，因此可知83為列表中第一個元素的前綴值。
第二，83代表元素1為字串類型，且字串長度為3(83 – 80 = 3)，因此可得83後面的3個byte皆為單一字符的ASCII解碼，分別為 63 => “c”，61 => “a”，74 => “t”。
第三後可知83為第2個元素的前綴，同樣也是長度為3的字串，因此 64 => “d”，6f => “o”，67 => “g”。
最後，剩餘的70，由於不會僅有前綴存在而沒數據的情況，因此70為單一字符的ASCII編碼，因此可得到 70 => “p”。

最後解碼出來的值為：[“cat”,”dog”,”p”]。

RLP解析

RLP編碼的概念透過數據前綴快速判斷編碼數據的類型與長度，在以太坊中用於區塊，交易，帳戶狀態的數據序列化儲存，相比一般的Unicode的編碼（對於針對固定字符進行編碼），RLP編碼更能構處理具有結構化的資料，即是列表的型態。同時能共利用這樣的結構性輕鬆建立一個數據的數狀結構。但相對來說RLP碼也僅限制在特定的數據類型（string, list），對於其他類型並不支援。

以太坊選擇使用RLP編碼主要有兩個原因：