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编码表

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 0 )RLP(x 1 )… ),得到合并后的编码值s(x)后,将s(x)的长度||s(x)||加上192(0xc0)得出列表的前缀,最后在并入s(x)的第一项中。

举例来说:

当目标列表为[“cat”,”dog”,”p”],首先需先将列表中的每一个元素进行RLP 编码,再来合并每个元素的编码值并得出编码的总长度,最后将长度值加上192(0xc0) 得出前缀,可以参考图三中有详细的流程。


图三: 列表类型的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编码将是以太坊中的首选方法。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

相关文章阅读