Recursive-Length-Prefix-Serialisierung (RLP)

Die Recursive-Length-Prefix-Serialisierung (RLP) wird in den Ausführungs-Clients von Ethereum umfassend verwendet. RLP standardisiert die Datenübertragung zwischen Blockchain-Knoten in einem platzsparenden Format. Der Zweck von RLP besteht darin, beliebig verschachtelte Arrays von Binärdaten zu codieren, und RLP ist die primäre Codierungsmethode, die zur Serialisierung von Objekten in der Ausführungsebene von Ethereum verwendet wird. Der Hauptzweck von RLP ist die Codierung von Strukturen; mit Ausnahme von positiven Ganzzahlen (Integers) delegiert RLP die Codierung spezifischer Datentypen (z. B. Strings, Floats) an Protokolle höherer Ordnung. Positive Ganzzahlen müssen in Big-Endian-Binärform ohne führende Nullen dargestellt werden (wodurch der ganzzahlige Wert Null dem leeren Byte-Array entspricht). Deserialisierte positive Ganzzahlen mit führenden Nullen müssen von jedem Protokoll höherer Ordnung, das RLP verwendet, als ungültig behandelt werden.

Weitere Informationen finden Sie im Ethereum Yellow Paper (Anhang B) (opens in a new tab).

Um RLP zur Codierung eines Wörterbuchs (Dictionary) zu verwenden, sind die beiden vorgeschlagenen kanonischen Formen:

• Verwendung von [[k1,v1],[k2,v2]...] mit Schlüsseln in lexikografischer Reihenfolge
• Verwendung der übergeordneten Patricia-Tree-Codierung, wie es Ethereum tut

Definition

Die RLP-Codierungsfunktion nimmt ein Element (Item) auf. Ein Element ist wie folgt definiert:

• ein String (d. h. ein Byte-Array) ist ein Element
• eine Liste von Elementen ist ein Element
• eine positive Ganzzahl ist ein Element

Zum Beispiel sind alle folgenden Dinge Elemente:

• ein leerer String;
• der String, der das Wort "cat" enthält;
• eine Liste, die eine beliebige Anzahl von Strings enthält;
• und komplexere Datenstrukturen wie ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"].
• die Zahl 100

Beachten Sie, dass im Kontext des Rests dieser Seite „String“ „eine bestimmte Anzahl von Bytes an Binärdaten“ bedeutet; es werden keine speziellen Codierungen verwendet und es wird kein Wissen über den Inhalt der Strings vorausgesetzt (außer wie durch die Regel gegen nicht-minimale positive Ganzzahlen gefordert).

Die RLP-Codierung ist wie folgt definiert:

• Eine positive Ganzzahl wird in das kürzeste Byte-Array umgewandelt, dessen Big-Endian-Interpretation die Ganzzahl ist, und dann gemäß den unten stehenden Regeln als String codiert.
• Für ein einzelnes Byte, dessen Wert im Bereich [0x00, 0x7f] (dezimal [0, 127]) liegt, ist dieses Byte seine eigene RLP-Codierung.
• Andernfalls, wenn ein String 0-55 Bytes lang ist, besteht die RLP-Codierung aus einem einzelnen Byte mit dem Wert 0x80 (dez. 128) plus der Länge des Strings, gefolgt vom String. Der Bereich des ersten Bytes ist somit [0x80, 0xb7] (dez. [128, 183]).
• Wenn ein String mehr als 55 Bytes lang ist, besteht die RLP-Codierung aus einem einzelnen Byte mit dem Wert 0xb7 (dez. 183) plus der Länge in Bytes der Länge des Strings in Binärform, gefolgt von der Länge des Strings, gefolgt vom String. Zum Beispiel würde ein 1024 Byte langer String als \xb9\x04\x00 (dez. 185, 4, 0) gefolgt vom String codiert werden. Hier ist 0xb9 (183 + 2 = 185) das erste Byte, gefolgt von den 2 Bytes 0x0400 (dez. 1024), die die Länge des eigentlichen Strings angeben. Der Bereich des ersten Bytes ist somit [0xb8, 0xbf] (dez. [184, 191]).
• Wenn ein String 2^64 Bytes lang oder länger ist, darf er nicht codiert werden.
• Wenn die gesamten Nutzdaten (Payload) einer Liste (d. h. die kombinierte Länge aller ihrer RLP-codierten Elemente) 0-55 Bytes lang sind, besteht die RLP-Codierung aus einem einzelnen Byte mit dem Wert 0xc0 plus der Länge der Nutzdaten, gefolgt von der Verkettung der RLP-Codierungen der Elemente. Der Bereich des ersten Bytes ist somit [0xc0, 0xf7] (dez. [192, 247]).
• Wenn die gesamten Nutzdaten einer Liste mehr als 55 Bytes lang sind, besteht die RLP-Codierung aus einem einzelnen Byte mit dem Wert 0xf7 plus der Länge in Bytes der Länge der Nutzdaten in Binärform, gefolgt von der Länge der Nutzdaten, gefolgt von der Verkettung der RLP-Codierungen der Elemente. Der Bereich des ersten Bytes ist somit [0xf8, 0xff] (dez. [248, 255]).

In Kurzform:

• p = Nutzdaten (Payload)
• n = Länge (Anzahl der Nutzdaten-Bytes)
• N = Länge-der-Länge-Offset (N+1 n Bytes folgen)

Im Code sieht das so aus:

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)
Alle anzeigen
Kopieren

Beispiele

• der String "dog" = [ 0x83, 'd', 'o', 'g' ]
• die Liste [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
• der leere String ('null') = [ 0x80 ]
• die leere Liste = [ 0xc0 ]
• die Ganzzahl 0 = [ 0x80 ]
• das Byte '\x00' = [ 0x00 ]
• das Byte '\x0f' = [ 0x0f ]
• die Bytes '\x04\x00' = [ 0x82, 0x04, 0x00 ]
• die mengentheoretische Darstellung (opens in a new tab) von drei, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
• der String "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

RLP-Decodierung

Gemäß den Regeln und dem Prozess der RLP-Codierung wird die Eingabe der RLP-Decodierung als ein Array von Binärdaten betrachtet. Der RLP-Decodierungsprozess läuft wie folgt ab:

1. Anhand des ersten Bytes (d. h. des Präfixes) der Eingabedaten werden der Datentyp, die Länge der eigentlichen Daten und der Offset decodiert;

2. Anhand des Typs und des Offsets der Daten werden die Daten entsprechend decodiert, wobei die minimale Codierungsregel für positive Ganzzahlen beachtet wird;

3. Fahren Sie mit der Decodierung des Rests der Eingabe fort;

Dabei lauten die Regeln für die Decodierung von Datentypen und Offsets wie folgt:

1. Die Daten sind ein String, wenn der Bereich des ersten Bytes (d. h. des Präfixes) [0x00, 0x7f] ist, und der String ist exakt das erste Byte selbst;

2. Die Daten sind ein String, wenn der Bereich des ersten Bytes [0x80, 0xb7] ist, und der String, dessen Länge gleich dem ersten Byte minus 0x80 ist, folgt auf das erste Byte;

3. Die Daten sind ein String, wenn der Bereich des ersten Bytes [0xb8, 0xbf] ist, und die Länge des Strings, dessen Länge in Bytes gleich dem ersten Byte minus 0xb7 ist, folgt auf das erste Byte, und der String folgt auf die Länge des Strings;

4. Die Daten sind eine Liste, wenn der Bereich des ersten Bytes [0xc0, 0xf7] ist, und die Verkettung der RLP-Codierungen aller Elemente der Liste, deren gesamte Nutzdaten gleich dem ersten Byte minus 0xc0 sind, folgt auf das erste Byte;

5. Die Daten sind eine Liste, wenn der Bereich des ersten Bytes [0xf8, 0xff] ist, und die gesamten Nutzdaten der Liste, deren Länge gleich dem ersten Byte minus 0xf7 ist, folgen auf das erste Byte, und die Verkettung der RLP-Codierungen aller Elemente der Liste folgt auf die gesamten Nutzdaten der Liste;

Im Code sieht das so aus:

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
Alle anzeigen
Kopieren

Weiterführende Literatur

• RLP in Ethereum (opens in a new tab)
• Ethereum under the hood: RLP (opens in a new tab)
• Coglio, A. (2020). Ethereum's Recursive Length Prefix in ACL2. arXiv preprint arXiv:2009.13769. (opens in a new tab)

Verwandte Themen

• Patricia Merkle Trie