Простая сериализация

Простая сериализация (SSZ) — это метод сериализации, используемый в сети Beacon. Она заменяет сериализацию RLP, используемую на уровне исполнения, везде на уровне консенсуса, за исключением протокола обнаружения пиров. Чтобы узнать больше о сериализации RLP, см. Префикс рекурсивной длины (RLP). SSZ разработан, чтобы быть детерминированным, а также эффективно мерклизировать данные. SSZ можно рассматривать как состоящий из двух компонентов: схемы сериализации и схемы мерклизации, которая предназначена для эффективной работы с сериализованной структурой данных.

Как работает SSZ?

Сериализация

SSZ — это схема сериализации, которая не является самоописываемой, а полагается на схему, которая должна быть известна заранее. Цель сериализации SSZ — представить объекты произвольной сложности в виде строк байтов. Для "базовых типов" это очень простой процесс. Элемент просто преобразуется в шестнадцатеричные байты. К базовым типам относятся:

целые числа без знака
логические значения

Для сложных "составных" типов сериализация сложнее, поскольку составной тип содержит несколько элементов, которые могут иметь разные типы, разные размеры или и то, и другое. Если все эти объекты имеют фиксированную длину (т. е. размер элементов всегда будет постоянным независимо от их фактических значений), сериализация — это просто преобразование каждого элемента составного типа, упорядоченного в байтовые строки little-endian. Эти байтовые строки соединяются вместе. Сериализованный объект имеет представление в виде списка байтов элементов фиксированной длины в том же порядке, в котором они появляются в десериализованном объекте.

Для типов с переменной длиной фактические данные заменяются значением "смещения" в позиции этого элемента в сериализованном объекте. Фактические данные добавляются в «кучу» (heap) в конце сериализованного объекта. Значение смещения — это индекс начала фактических данных в куче, действующий как указатель на соответствующие байты.

Приведенный ниже пример иллюстрирует, как работает смещение для контейнера с элементами как фиксированной, так и переменной длины:

1
2    struct Dummy {
3
4        number1: u64,
5        number2: u64,
6        vector: Vec<u8>,
7        number3: u64
8    }
9
10    dummy = Dummy{
11
12        number1: 37,
13        number2: 55,
14        vector: vec![1,2,3,4],
15        number3: 22,
16    }
17
18    serialized = ssz.serialize(dummy)
19
Показать все

serialized будет иметь следующую структуру (здесь дополнено до 4 бит, в реальности дополняется до 32 бит, а для ясности сохранено представление int):

1[37, 0, 0, 0, 55, 0, 0, 0, 16, 0, 0, 0, 22, 0, 0, 0, 1, 2, 3, 4]
2------------  -----------  -----------  -----------  ----------
3      |             |            |           |            |
4   число1        число2    смещение для   число3     значение для
5                              вектора                  вектора
6

для ясности разделено по строкам:

1[
2  37, 0, 0, 0,  # кодирование `number1` в формате little-endian.
3  55, 0, 0, 0,  # кодирование `number2` в формате little-endian.
4  16, 0, 0, 0,  # "Смещение", которое указывает, где начинается значение `vector` (16 в формате little-endian).
5  22, 0, 0, 0,  # кодирование `number3` в формате little-endian.
6  1, 2, 3, 4,   # Фактические значения в `vector`.
7]

Это все еще упрощение: целые числа и нули в приведенных выше схемах на самом деле будут храниться в виде списков байтов, вот так:

1[
2  10100101000000000000000000000000  # кодирование `number1` в формате little-endian
3  10110111000000000000000000000000  # кодирование `number2` в формате little-endian.
4  10010000000000000000000000000000  # "Смещение", которое указывает, где начинается значение `vector` (16 в формате little-endian).
5  10010110000000000000000000000000  # кодирование `number3` в формате little-endian.
6  10000001100000101000001110000100   # Фактическое значение поля `bytes`.
7]

Таким образом, фактические значения для типов переменной длины хранятся в куче в конце сериализованного объекта, а их смещения хранятся на своих правильных позициях в упорядоченном списке полей.

Существуют также некоторые особые случаи, требующие специальной обработки, например, тип BitList, который требует добавления ограничения длины во время сериализации и удаления во время десериализации. Полная информация доступна в спецификации SSZ (opens in a new tab).

Десериализация

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

Смотрите ssz.dev (opens in a new tab) для интерактивного объяснения этого.

Мерклизация

Затем этот сериализованный объект SSZ может быть мерклизирован, то есть преобразован в представление тех же данных в виде дерева Меркла. Сначала определяется количество 32-байтовых фрагментов в сериализованном объекте. Это "листья" дерева. Общее количество листьев должно быть степенью двойки, чтобы хеширование листьев в конечном итоге дало один корневой хэш дерева. Если это не так, добавляются дополнительные листья, содержащие 32 байта нулей. Схематично:

1        корневой хэш дерева
2            /     \
3           /       \
4          /         \
5         /           \
6   хэш листьев     хэш листьев
7     1 и 2           3 и 4
8      /   \            /  \
9     /     \          /    \
10    /       \        /      \
11 лист1     лист2    лист3     лист4
Показать все

Также бывают случаи, когда листья дерева естественным образом распределяются не так равномерно, как в примере выше. Например, лист 4 может быть контейнером с несколькими элементами, которые требуют добавления дополнительной "глубины" в дерево Меркла, создавая неровное дерево.

Вместо того, чтобы называть эти элементы дерева «лист X», «узел X» и т. д., мы можем дать им обобщенные индексы, начиная с корня = 1 и считая слева направо на каждом уровне. Это обобщенный индекс, объясненный выше. Каждый элемент в сериализованном списке имеет обобщенный индекс, равный 2**depth + idx, где idx — это его позиция с нулевым индексом в сериализованном объекте, а глубина — это количество уровней в дереве Меркла, которое можно определить как двоичный логарифм количества элементов (листьев).

Обобщенные индексы

Обобщенный индекс — это целое число, которое представляет узел в двоичном дереве Меркла, где каждый узел имеет обобщенный индекс 2 ** depth + index in row.

1        1           --глубина = 0  2**0 + 0 = 1
2    2       3       --глубина = 1  2**1 + 0 = 2, 2**1+1 = 3
3  4   5   6   7     --глубина = 2  2**2 + 0 = 4, 2**2 + 1 = 5...
4

Это представление дает индекс узла для каждого фрагмента данных в дереве Меркла.

Мультидоказательства

Предоставление списка обобщенных индексов, представляющих конкретный элемент, позволяет нам проверить его по корневому хэшу дерева. Этот корень является нашей принятой версией реальности. Любые предоставленные нам данные могут быть проверены на соответствие этой реальности путем вставки их в нужное место в дереве Меркла (определяемое его обобщенным индексом) и наблюдения за тем, что корень остается постоянным. В спецификации здесь (opens in a new tab) есть функции, которые показывают, как вычислить минимальный набор узлов, необходимый для проверки содержимого определенного набора обобщенных индексов.

Например, чтобы проверить данные в индексе 9 в дереве ниже, нам нужен хэш данных в индексах 8, 9, 5, 3, 1. Хэш (8,9) должен быть равен хэшу (4), который хешируется с 5 для получения 2, который хешируется с 3 для получения корня дерева 1. Если для 9 были предоставлены неверные данные, корень изменится — мы обнаружим это, и проверка ветви не удастся.

1* = данные, необходимые для генерации доказательства
2
3                    1*
4          2                      3*
5    4          5*          6          7
68*     9*   10    11   12    13    14    15
7