Rekurzív hosszúságú prefix (RLP) sorosítás

Utolsó módosítás: @Satglow(opens in a new tab), 2024. február 20.

A rekurzív hosszúságú prefixum (RLP) egy sorosítási módszer, melyet kiterjedten használnak az Ethereum végrehajtási rétegén. Az RLP a csomópontok közötti adatátvitelt szabványosítja helytakarékos formátumban. Az RLP célja a bináris adatok tetszőlegesen egymásba ágyazott tömbjeinek kódolása, és ez az elsődleges kódolási módszer, amelyet az Ethereum végrehajtási rétegén az objektumok sorosítására használnak. Az RLP célja a struktúra kódolása; bizonyos adattípusok (például sztring, float) kódolása a magasabb rendű protokollokra van bízva; de a pozitív RLP egész számokat nagy-endian bináris formában kell ábrázolni, vezető nullák nélkül (így a nulla integer ekvivalens az üres bájttömbbel). A vezető nullával rendelkező pozitív egész számok deszerializálása érvénytelen. A sztring hosszának egészértékű ábrázolását is így kell kódolni, csakúgy, mint a payloadban lévő egész számokat.

További információkat talál az Ethereum Sárgakönyvben (B függelék)(opens in a new tab).

Ahhoz, hogy az RLP-vel kódoljunk egy szótárt, a két javasolt kanonikus forma a következő:

a [[k1,v1],[k2,v2]...] használjuk olyan kulcsokkal, melyek lexikográfiai sorrendben vannak
a magasabb szintű Patricia-fa kódolást használjuk, mint az Ethereum

Definíció

Az RLP kódolási funkció egy elemet vesz fel. Az elem a következő lehet：

egy szting vagy karaktersorozat (bájttömb) az egy elem
az elemek listája is egy elem

Például a következők mindegyike elem:

egy üres sztring;
egy sztring, amely a "cat" (macska) szót tartalmazza;
egy lista, melyben bármennyi sztring található;
és az ennél bonyolultabb adatstruktúrák, mint ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"].

Érdemes megjegyezni, hogy az oldal további részében a sztring kifejezés a „bináris adat bizonyos számú bájtját” jelenti; nem használunk speciális kódolást, és a sztringek tartalmát nem ismerjük.

Az RPL kódolást a következő módon definiáljuk:

Egy bájt, amelynek értéke a [0x00, 0x7f] (decimális [0, 127]) tartományban van, annak RLP kódolása önmaga.
Máskülöben, ha a sztring 0-55 bájt hosszú, az RLP-kódolás egyetlen 0x80 (decimál 128) értékű bájtból és a sztring hosszából áll, amelyet a sztring követ. Az első bájt tartománya tehát [0x80, 0xb7] (dec. [128, 183]).
Ha a sztring több mint 55 bájt hosszú, az RLP-kódolás egyetlen bájtból áll, amelynek értéke 0xb7 (dec. 183), valamint a sztring hossza bájtokban kifejezve bináris formában, ezt követi a sztring hossza, majd a sztring. Például egy 1024 bájt hosszú sztring kódolása \xb9\x04\x00 (dec. 185, 4, 0), amelyet a sztring követ. Itt 0xb9 (183 + 2 = 185) az első bájt, majd az a 2 bájt 0x0400 (dec. 1024) jön, amely az aktuális sztring hosszát jelöli. Az első bájt tartománya tehát [0xb8, 0xbf] (dec. [184, 191]).
Ha egy lista teljes payload-ja (azaz az összes RLP-kódolt elemének együttes hossza) 0-55 bájt hosszú, az RLP-kódolás egyetlen 0xc0 értékű bájtból és a payload hosszából áll, amelyet az elemek RLP-kódolásainak összekapcsolása követ. Az első bájt tartománya tehát [0xc0, 0xf7] (dec. [192, 247]).
Ha egy lista teljes payload-ja több mint 55 bájt hosszú, az RLP-kódolás egyetlen 0xf7 értékű bájtból, valamint a payload hosszának bájtban kifejezett hosszából áll bináris formában, amelyet a payload hossza követ, majd az elemek RLP-kódolásainak összekapcsolása. Az első bájt tartománya tehát [0xf8, 0xff] (dec. [248, 255]).

Ez kódban a következőképpen néz ki:

1def rlp_encode(input):
2    if isinstance(input,str):
3        if len(input) == 1 and ord(input) < 0x80:
4            return input
5        return encode_length(len(input), 0x80) + input
6    elif isinstance(input, list):
7        output = ''
8        for item in input:
9            output += rlp_encode(item)
10        return encode_length(len(output), 0xc0) + output
11
12def encode_length(L, offset):
13    if L < 56:
14         return chr(L + offset)
15    elif L < 256**8:
16         BL = to_binary(L)
17         return chr(len(BL) + offset + 55) + BL
18     raise Exception("input too long")
19
20def to_binary(x):
21    if x == 0:
22        return ''
23    return to_binary(int(x / 256)) + chr(x % 256)
Összes megjelenítése
 Másolás

Példák

a sztring "dog" = [ 0x83, 'd', 'o', 'g' ]
a lista [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
az üres sztring ('null') = [ 0x80 ]
az üres lista = [ 0xc0 ]
az integer 0 = [ 0x80 ]
a kódolt integer 0 ('\x00') = [ 0x00 ]
a kódolt integer 15 ('\x0f') = [ 0x0f ]
a kódolt integer 1024 ('\x04\x00') = [ 0x82, 0x04, 0x00 ]
a háromnak a halmazelméleti ábrázolása(opens in a new tab) [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
a sztring "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

RLP dekódolás

Az RLP kódolás szabályai és folyamata szerint az RLP dekódolás bemenete bináris adatok tömbjének tekinthető. Az RLP dekódolási folyamat a következő:

a bemeneti adatok első bájtja (azaz előtagja) alapján dekódolja az adattípust, a tényleges adat hosszát és az eltolást;
az adatok típusának és eltolásának megfelelően dekódolja az adatokat;
folytatja a bemenet többi részének dekódolását;

Ezek közül az adattípusok és az eltolás dekódolásának szabályai a következők:

az adat egy sztring, ha az első bájt tartománya (az előtag) [0x00, 0x7f], és a sztring pontosan maga az első bájt;
az adat egy sztring, ha az első bájt tartománya [0x80, 0xb7], és az első bájtot az a sztring követi, amelynek hossza egyenlő az első bájt mínusz 0x80;
az adat egy sztring, ha az első bájt tartománya [0xb8, 0xbf], és a sztring hossza, amelynek hossza bájtokban egyenlő az első bájt mínusz 0xb7, követi az első bájtot, és a sztring követi a sztring hosszát;
az adat egy lista, ha az első bájt tartománya [0xc0, 0xf7], és a lista minden olyan eleme RLP-kódolásának összekapcsolása, amelynek teljes payload-ja megegyezik az első bájttal mínusz 0xc0, az első bájtot követi;
az adat egy lista, ha az első bájt tartománya [0xf8, 0xff], és a lista teljes payload-ja, amelynek hossza megegyezik az első bájttal mínusz 0xf7, követi az első bájtot, és a lista összes elemének RLP-kódolásának konkatenációja követi a lista teljes payload-ját;

Ez kódban a következőképpen néz ki:

1def rlp_decode(input):
2    if len(input) == 0:
3        return
4    output = ''
5    (offset, dataLen, type) = decode_length(input)
6    if type is str:
7        output = instantiate_str(substr(input, offset, dataLen))
8    elif type is list:
9        output = instantiate_list(substr(input, offset, dataLen))
10    output += rlp_decode(substr(input, offset + dataLen))
11    return output
12
13def decode_length(input):
14    length = len(input)
15    if length == 0:
16        raise Exception("input is null")
17    prefix = ord(input[0])
18    if prefix <= 0x7f:
19        return (0, 1, str)
20    elif prefix <= 0xb7 and length > prefix - 0x80:
21        strLen = prefix - 0x80
22        return (1, strLen, str)
23    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
24        lenOfStrLen = prefix - 0xb7
25        strLen = to_integer(substr(input, 1, lenOfStrLen))
26        return (1 + lenOfStrLen, strLen, str)
27    elif prefix <= 0xf7 and length > prefix - 0xc0:
28        listLen = prefix - 0xc0;
29        return (1, listLen, list)
30    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
31        lenOfListLen = prefix - 0xf7
32        listLen = to_integer(substr(input, 1, lenOfListLen))
33        return (1 + lenOfListLen, listLen, list)
34    raise Exception("input does not conform to RLP encoding form")
35
36def to_integer(b):
37    length = len(b)
38    if length == 0:
39        raise Exception("input is null")
40    elif length == 1:
41        return ord(b[0])
42    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256
Összes megjelenítése
 Másolás

További olvasnivaló

Patricia Merkle-fa

back-to-top ↑