,

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

以太坊編碼

以太坊編碼原理-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的值,若不了解大端與小端可以在這篇文章中找到更詳細的解釋。

ASCII編碼表
圖一 : ASCII編碼表

RLP編碼(RLP Encoding)

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

  • 字串類的編碼規則(一):

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

規則一公式可以寫成:

字串的規則一公式
字串的規則一公式

其中Rb(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的編碼。

規則一公式可以寫成

列表的規則一公式
列表的規則一公式

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

舉例來說:

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

 列表類型的RLP編碼
圖三 : 列表類型的RLP編碼

  • 列表類的編碼規則(二):

若目標列表長度大於等於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編碼主要有兩個原因:

  1. 實現簡單
  2. 對應的編碼直具有完整的對應性

在許多編碼中,依據不同數據類型有可能產生相同的數據卻編碼出不同的編碼值,以太坊中不同的編碼值裝會導致後續hash後的結果值不同。因此具有通用性且能表示結構性的RLP編碼將是以太坊中的首選方法。

1 Comment
  • Jason Ho
    says:

    真的很詳細,建議網站排版可以用系列的方式,方便讀者循序漸進。謝謝用心撰寫這詳細的文章。

發佈留言