---
title: "Серіалізація з рекурсивним префіксом довжини (RLP)"
description: "Визначення кодування RLP на рівні виконання Етеріуму."
lang: uk
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)