Σειριοποίηση Recursive-length prefix (RLP)

Το Recursive Length Prefix (RLP) χρησιμοποιείται εκτενώς στους πελάτες εκτέλεσης του Ethereum. Το RLP τυποποιεί τη μεταφορά δεδομένων μεταξύ κόμβων σε μια μορφή αποδοτική στο χώρο. Ο σκοπός του RLP είναι να κωδικοποιεί αυθαίρετα ενσωματωμένους πίνακες δυαδικών δεδομένων και το RLP είναι η κύρια μέθοδος κωδικοποίησης που χρησιμοποιείται για τη σειριοποίηση αντικειμένων στο επίπεδο εκτέλεσης του Ethereum. Ο κύριος σκοπός του RLP είναι η κωδικοποίηση δομής με εξαίρεση τους θετικούς ακέραιους, το RLP αναθέτει την κωδικοποίηση συγκεκριμένων τύπων δεδομένων (π.χ. συμβολοσειρές, αριθμοί κινητής υποδιαστολής) σε πρωτόκολλα υψηλότερης τάξης. Οι θετικοί ακέραιοι πρέπει να αναπαρίστανται σε δυαδική μορφή big-endian χωρίς μηδενικά προηγούμενα (κάνοντας έτσι την τιμή ακέραιου μηδέν ισοδύναμη με τον κενό πίνακα byte). Οι αποσειριοποιημένοι θετικοί ακέραιοι με μηδενικά προηγούμενα πρέπει να αντιμετωπίζονται ως μη έγκυροι από οποιοδήποτε πρωτόκολλο υψηλότερης τάξης που χρησιμοποιεί RLP.

Περισσότερες πληροφορίες στο τεχνικές πληροφορίες του Ethereum (Παράρτημα Β)(opens in a new tab).

Για να χρησιμοποιήσετε το RLP για την κωδικοποίηση ενός λεξικού, οι δύο προτεινόμενες κανονικές μορφές είναι:

Χρησιμοποιήστε [[k1,v1],[k2,v2]...] με κλειδιά σε λεξικογραφική σειρά.
Χρησιμοποιήστε την κωδικοποίηση δέντρου Patricia υψηλότερου επιπέδου όπως κάνει το Ethereum.

Επεξήγηση

Η συνάρτηση κωδικοποίησης RLP παίρνει ένα στοιχείο. Ένα στοιχείο ορίζεται ως εξής：

Μια συμβολοσειρά (δηλαδή πίνακας byte) είναι ένα στοιχείο.
Μια λίστα στοιχείων είναι ένα αντικείμενο.
Ένας θετικός ακέραιος είναι ένα αντικείμενο.

Για παράδειγμα, όλα τα παρακάτω είναι αντικείμενα:

Μια κενή συμβολοσειρά.
Η συμβολοσειρά που περιέχει τη λέξη "cat".
Μια λίστα που περιέχει οποιοδήποτε αριθμό συμβολοσειρών.
Και πιο πολύπλοκες δομές δεδομένων όπως ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"].
Ο αριθμός 100.

Σημειώστε ότι στο πλαίσιο της υπόλοιπης σελίδας, η "συμβολοσειρά" σημαίνει "ένας συγκεκριμένος αριθμός byte δεδομένων", δε χρησιμοποιούνται ειδικές κωδικοποιήσεις και δεν υπονοείται καμία γνώση σχετικά με το περιεχόμενο των συμβολοσειρών (εκτός από ό, τι απαιτείται από τον κανόνα κατά των μη ελάχιστων θετικών ακεραίων).

Η κωδικοποίηση RLP ορίζεται ως εξής:

Για έναν θετικό ακέραιο, μετατρέπεται στον μικρότερο πίνακα byte του οποίου η ερμηνεία big-endian είναι ο ακέραιος και στη συνέχεια κωδικοποιείται ως συμβολοσειρά σύμφωνα με τους παρακάτω κανόνες.
Για ένα μόνο byte του οποίου η τιμή βρίσκεται στο εύρος [0x00, 0x7f] (δεκαδικό [0, 127]), αυτό το byte είναι η δική του κωδικοποίηση RLP.
Διαφορετικά, εάν μια συμβολοσειρά έχει μήκος 0-55 byte, η κωδικοποίηση RLP αποτελείται από ένα μόνο byte με τιμή 0x80 (δεκ. 128) συν το μήκος της συμβολοσειράς ακολουθούμενο από τη συμβολοσειρά. Το εύρος του πρώτου byte είναι έτσι [0x80, 0xb7] (δεκ. [128, 183]).
Εάν μια συμβολοσειρά έχει μήκος μεγαλύτερο από 55 byte, η κωδικοποίηση RLP αποτελείται από ένα μόνο byte με τιμή 0xb7 (δεκ. 183) συν το μήκος σε byte του μήκους της συμβολοσειράς σε δυαδική μορφή, ακολουθούμενο από το μήκος της συμβολοσειράς, ακολουθούμενο από τη συμβολοσειρά. Για παράδειγμα, μια συμβολοσειρά μήκους 1024 byte θα κωδικοποιηθεί ως \xb9\x04\x00 (δεκ. 185, 4, 0) ακολουθούμενη από τη συμβολοσειρά. Εδώ, 0xb9 (183 + 2 = 185) ως το πρώτο byte, ακολουθούμενο από τα 2 byte 0x0400 (δεκ. 1024) που υποδηλώνουν το μήκος της πραγματικής συμβολοσειράς. Το εύρος του πρώτου byte είναι έτσι [0xb8, 0xbf] (δεκ. [184, 191]).
Εάν μια συμβολοσειρά έχει μήκος 2^64 byte ή μεγαλύτερο, ενδέχεται να μην μπορεί να κωδικοποιηθεί.
Εάν το συνολικό φορτίο μιας λίστας (δηλαδή το συνδυασμένο μήκος όλων των στοιχείων της που κωδικοποιούνται RLP) έχει μήκος 0-55 byte, η κωδικοποίηση RLP αποτελείται από ένα μόνο byte με τιμή 0xc0 συν το μήκος του φορτίου ακολουθούμενο από τη συνένωση των κωδικοποιήσεων RLP των στοιχείων. Το εύρος του πρώτου byte είναι έτσι [0xc0, 0xf7] (δεκ. [192, 247]).
Εάν ο συνολικός όγκος μιας λίστας έχει μήκος μεγαλύτερο από 55 byte, η κωδικοποίηση RLP αποτελείται από ένα μόνο byte με τιμή 0xf7 συν το μήκος σε byte του φορτίου σε δυαδική μορφή, ακολουθούμενο από το μήκος του φορτίου, ακολουθούμενο από τη συνένωση των κωδικοποιήσεων RLP των στοιχείων. Το εύρος του πρώτου byte είναι έτσι [0xf8, 0xff] (δεκ. [248, 255]).

Σε κώδικα, αυτό είναι:

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)
Εμφάνιση όλων

Παραδείγματα

η συμβολοσειρά "dog" = [ 0x83, 'd', 'o', 'g' ]
η λίστα [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
η κενή συμβολοσειρά ('null') = [ 0x80 ]
η κενή λίστα = [ 0xc0 ]
ο ακέραιος 0 = [ 0x80 ]
το byte '\x00' = [ 0x00 ]
το byte '\x0f' = [ 0x0f ]
τα bytes '\x04\x00' = [ 0x82, 0x04, 0x00 ]
τα σύνολα θεωρητικής αναπαράστασης(opens in a new tab) of three, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
η συμβολοσειρά "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

Αποκωδικοποίηση RLP

Σύμφωνα με τους κανόνες και τη διαδικασία κωδικοποίησης RLP, η είσοδος της αποκωδικοποίησης RLP θεωρείται ως ένας πίνακας δυαδικών δεδομένων. Η διαδικασία αποκωδικοποίησης RLP είναι ως εξής:

Σύμφωνα με το πρώτο byte (δηλαδή το πρόθεμα) των δεδομένων εισόδου και την αποκωδικοποίηση του τύπου δεδομένων, το μήκος των πραγματικών δεδομένων και την απόσταση.
Σύμφωνα με τον τύπο και την απόσταση των δεδομένων, αποκωδικοποιήστε τα δεδομένα αντίστοιχα, τηρώντας τον ελάχιστο κανόνα κωδικοποίησης για θετικούς ακέραιους.
συνεχίστε να αποκωδικοποιείτε το υπόλοιπο της εισόδου.

Μεταξύ αυτών, οι κανόνες αποκωδικοποίησης των τύπων δεδομένων και της απόστασης είναι ως εξής:

Τα δεδομένα είναι μια συμβολοσειρά εάν το εύρος του πρώτου byte (δηλαδή το πρόθεμα) είναι [0x00, 0x7f] και η συμβολοσειρά είναι το ίδιο το πρώτο byte ακριβώς.
Τα δεδομένα είναι μια συμβολοσειρά εάν το εύρος του πρώτου byte είναι [0x80, 0xb7] και η συμβολοσειρά του οποίου το μήκος είναι ίσο με το πρώτο byte μείον 0x80 ακολουθεί το πρώτο byte.
Τα δεδομένα είναι μια συμβολοσειρά εάν το εύρος του πρώτου byte είναι [0xb8, 0xbf] και το μήκος της συμβολοσειράς του οποίου το μήκος σε byte είναι ίσο με το πρώτο byte μείον 0xb7 ακολουθεί το πρώτο byte και η συμβολοσειρά ακολουθεί το μήκος της συμβολοσειράς.
Τα δεδομένα είναι μια λίστα εάν το εύρος του πρώτου byte είναι [0xc0, 0xf7] και η σύμπλεξη των κωδικοποιήσεων RLP όλων των στοιχείων της λίστας των οποίων το συνολικό φορτίο είναι ίσο με το πρώτο byte μείον 0xc0 ακολουθεί το πρώτο byte.
Τα δεδομένα είναι μια λίστα εάν το εύρος του πρώτου byte είναι [0xf8, 0xff] και το συνολικό φορτίο της λίστας του οποίου το μήκος είναι ίσο με το πρώτο byte μείον 0xf7 ακολουθεί το πρώτο byte και η σύμπλεξη των κωδικοποιήσεων RLP όλων των στοιχείων της λίστας ακολουθεί το συνολικό φορτίο της λίστας.

Σε κώδικα, αυτό είναι:

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
Εμφάνιση όλων

Περισσότερες πληροφορίες

Patricia merkle trie

Σειριοποίηση Recursive-length prefix (RLP)

Επεξήγηση

Παραδείγματα

Αποκωδικοποίηση RLP

Περισσότερες πληροφορίες

Σχετικά θέματα

Ήταν χρήσιμο αυτό το άρθρο;