---
title: "Сериализация с префиксом рекурсивной длины (RLP)"
description: "Определение кодировки RLP на уровне исполнения Эфириума."
lang: ru
sidebarDepth: 2
---

Сериализация с префиксом рекурсивной длины (RLP) широко используется в клиентах уровня исполнения Эфириума. RLP стандартизирует передачу данных между узлами в компактном формате. Цель RLP — кодирование произвольно вложенных массивов двоичных данных, и RLP является основным методом кодирования, используемым для сериализации объектов на уровне исполнения Эфириума. Основная цель RLP — кодирование структуры; за исключением положительных целых чисел, RLP делегирует кодирование определенных типов данных (например, строк, чисел с плавающей запятой) протоколам более высокого порядка. Положительные целые числа должны быть представлены в двоичной форме, использующей прямой порядок байтов, без ведущих нулей (таким образом, целочисленное значение ноль эквивалентно пустому массиву байтов). Десериализованные положительные целые числа с ведущими нулями должны рассматриваться как недействительные любым протоколом более высокого порядка, использующим RLP.

Дополнительная информация доступна в [желтой книге Эфириума (Приложение B)](https://ethereum.github.io/yellowpaper/paper.pdf#page=19).

Для использования RLP при кодировании словаря предлагаются две канонические формы:

- использовать `[[k1,v1],[k2,v2]...]` с ключами в лексикографическом порядке
- использовать высокоуровневое кодирование дерева Патриции (Patricia Tree), как это делает [Эфириум](/)

## Определение {#definition}

Функция кодирования RLP принимает элемент. Элемент определяется следующим образом:

- строка (т. е. массив байтов) является элементом
- список элементов является элементом
- положительное целое число является элементом

Например, все нижеперечисленное является элементами:

- пустая строка;
- строка, содержащая слово «cat»;
- список, содержащий любое количество строк;
- и более сложные структуры данных, такие как `["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]`.
- число `100`

Обратите внимание, что в контексте остальной части этой страницы «строка» означает «определенное количество байтов двоичных данных»; никакие специальные кодировки не используются, и никакие знания о содержимом строк не подразумеваются (за исключением случаев, требуемых правилом против неминимальных положительных целых чисел).

Кодирование RLP определяется следующим образом:

- Положительное целое число преобразуется в кратчайший массив байтов, интерпретация которого, использующая прямой порядок байтов, является этим целым числом, а затем кодируется как строка в соответствии с приведенными ниже правилами.
- Для одного байта, значение которого находится в диапазоне `[0x00, 0x7f]` (десятичный `[0, 127]`), этот байт является собственной кодировкой RLP.
- В противном случае, если длина строки составляет 0-55 байтов, кодировка RLP состоит из одного байта со значением **0x80** (дес. 128) плюс длина строки, за которым следует сама строка. Таким образом, диапазон первого байта составляет `[0x80, 0xb7]` (дес. `[128, 183]`).
- Если длина строки превышает 55 байтов, кодировка RLP состоит из одного байта со значением **0xb7** (дес. 183) плюс длина в байтах длины строки в двоичной форме, за которым следует длина строки, а затем сама строка. Например, строка длиной 1024 байта будет закодирована как `\xb9\x04\x00` (дес. `185, 4, 0`), за которым следует строка. Здесь `0xb9` (183 + 2 = 185) в качестве первого байта, за которым следуют 2 байта `0x0400` (дес. 1024), обозначающие длину фактической строки. Таким образом, диапазон первого байта составляет `[0xb8, 0xbf]` (дес. `[184, 191]`).
- Если длина строки составляет 2^64 байта или больше, она не может быть закодирована.
- Если общая полезная нагрузка списка (т. е. общая длина всех его элементов, закодированных в RLP) составляет 0-55 байтов, кодировка RLP состоит из одного байта со значением **0xc0** плюс длина полезной нагрузки, за которым следует конкатенация кодировок RLP элементов. Таким образом, диапазон первого байта составляет `[0xc0, 0xf7]` (дес. `[192, 247]`).
- Если общая полезная нагрузка списка превышает 55 байтов, кодировка RLP состоит из одного байта со значением **0xf7** плюс длина в байтах длины полезной нагрузки в двоичной форме, за которым следует длина полезной нагрузки, а затем конкатенация кодировок RLP элементов. Таким образом, диапазон первого байта составляет `[0xf8, 0xff]` (дес. `[248, 255]`).

В краткой форме:

| Диапазон | Байт 1 | Байт 2 | ... | Байт 9 | Байт 10 | Значение |
| ----------- | ---------- | ---------- | ---------- | --------------------- | ---------- | ----------------------------------------- |
| `0x00-0x7f` | `0ppppppp` |            |            |                       |            | однобайтовая строка |
| `0x80-0xb7` | `10nnnnnn` | `pppppppp` | `...`      |                       |            | короткая строка (0-55 байтов) |
| `0xb8-0xbf` | `10111NNN` | `nnnnnnnn` | `...`      | `nnnnnnnn`/`pppppppp` | `pppppppp` | длинная строка, N+1 байтов для длины, затем полезная нагрузка |
| `0xc0-0xf7` | `11nnnnnn` | `pppppppp` | `...`      |                       |            | короткий список (0-55 байтов) |
| `0xf8-0xff` | `11111NNN` | `nnnnnnnn` | `...`      | `nnnnnnnn`/`pppppppp` | `pppppppp` | длинный список, N+1 байтов для длины, затем полезная нагрузка |

- `p` = полезная нагрузка
- `n` = длина (количество байтов полезной нагрузки)
- `N` = смещение длины длины (далее следуют N+1 байтов `n`)

В коде это выглядит так:

```python
def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80:
            return input
        return encode_length(len(input), 0x80) + input
    elif isinstance(input, list):
        output = ''
        for item in input:
            output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output

def encode_length(L, offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    return to_binary(int(x / 256)) + chr(x % 256)
```

## Примеры {#examples}

- строка «dog» = [ 0x83, 'd', 'o', 'g' ]
- список [ «cat», «dog» ] = `[ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]`
- пустая строка ('null') = `[ 0x80 ]`
- пустой список = `[ 0xc0 ]`
- целое число 0 = `[ 0x80 ]`
- байт '\x00' = `[ 0x00 ]`
- байт '\x0f' = `[ 0x0f ]`
- байты '\x04\x00' = `[ 0x82, 0x04, 0x00 ]`
- [теоретико-множественное представление](https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers) числа три, `[ [], [[]], [ [], [[]] ] ] = [ 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-decoding}

В соответствии с правилами и процессом кодирования RLP, входные данные для декодирования RLP рассматриваются как массив двоичных данных. Процесс декодирования RLP выглядит следующим образом:

1.  в зависимости от первого байта (т. е. префикса) входных данных декодируется тип данных, длина фактических данных и смещение;

2.  в зависимости от типа и смещения данных, данные декодируются соответствующим образом с соблюдением правила минимального кодирования для положительных целых чисел;

3.  продолжается декодирование остальной части входных данных;

При этом правила декодирования типов данных и смещения следующие:

1.  данные являются строкой, если диапазон первого байта (т. е. префикса) составляет [0x00, 0x7f], и строка в точности совпадает с самим первым байтом;

2.  данные являются строкой, если диапазон первого байта составляет [0x80, 0xb7], и строка, длина которой равна первому байту минус 0x80, следует за первым байтом;

3.  данные являются строкой, если диапазон первого байта составляет [0xb8, 0xbf], и длина строки, длина которой в байтах равна первому байту минус 0xb7, следует за первым байтом, а сама строка следует за длиной строки;

4.  данные являются списком, если диапазон первого байта составляет [0xc0, 0xf7], и конкатенация кодировок RLP всех элементов списка, общая полезная нагрузка которых равна первому байту минус 0xc0, следует за первым байтом;

5.  данные являются списком, если диапазон первого байта составляет [0xf8, 0xff], и общая полезная нагрузка списка, длина которой равна первому байту минус 0xf7, следует за первым байтом, а конкатенация кодировок RLP всех элементов списка следует за общей полезной нагрузкой списка;

В коде это выглядит так:

```python
def rlp_decode(input):
    if len(input) == 0:
        return
    output = ''
    (offset, dataLen, type) = decode_length(input)
    if type is str:
        output = instantiate_str(substr(input, offset, dataLen))
    elif type is list:
        output = instantiate_list(substr(input, offset, dataLen))
    output += rlp_decode(substr(input, offset + dataLen))
    return output

def decode_length(input):
    length = len(input)
    if length == 0:
        raise Exception("input is null")
    prefix = ord(input[0])
    if prefix <= 0x7f:
        return (0, 1, str)
    elif prefix <= 0xb7 and length > prefix - 0x80:
        strLen = prefix - 0x80
        return (1, strLen, str)
    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
        lenOfStrLen = prefix - 0xb7
        strLen = to_integer(substr(input, 1, lenOfStrLen))
        return (1 + lenOfStrLen, strLen, str)
    elif prefix <= 0xf7 and length > prefix - 0xc0:
        listLen = prefix - 0xc0;
        return (1, listLen, list)
    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
        lenOfListLen = prefix - 0xf7
        listLen = to_integer(substr(input, 1, lenOfListLen))
        return (1 + lenOfListLen, listLen, list)
    raise Exception("input does not conform to RLP encoding form")

def to_integer(b):
    length = len(b)
    if length == 0:
        raise Exception("input is null")
    elif length == 1:
        return ord(b[0])
    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256
```

## Дополнительная литература {#further-reading}

- [RLP в Эфириуме](https://medium.com/coinmonks/data-structure-in-ethereum-episode-1-recursive-length-prefix-rlp-encoding-decoding-d1016832f919)
- [Эфириум изнутри: RLP](https://medium.com/coinmonks/ethereum-under-the-hood-part-3-rlp-decoding-df236dc13e58)
- [Coglio, A. (2020). Ethereum's Recursive Length Prefix in ACL2. arXiv preprint arXiv:2009.13769.](https://arxiv.org/abs/2009.13769)

## Связанные темы {#related-topics}

- [Дерево Меркла — Патриции](/developers/docs/data-structures-and-encoding/patricia-merkle-trie)