Простая сериализация
Простая сериализация (SSZ) — это метод сериализации, используемый в сигнальной цепочке. Он заменяет сериализацию RLP, используемую на уровне исполнения, повсюду на уровне консенсуса, за исключением протокола обнаружения пиров. Чтобы узнать больше о сериализации RLP, см. Префикс рекурсивной длины (RLP). SSZ разработан так, чтобы быть детерминированным, а также эффективно преобразовываться в дерево Меркла. Можно считать, что SSZ состоит из двух компонентов: схемы сериализации и схемы построения дерева Меркла, которая предназначена для эффективной работы с сериализованной структурой данных.
Как работает SSZ?
Сериализация
SSZ — это схема сериализации, которая не является самоописываемой; вместо этого она опирается на схему, которая должна быть известна заранее. Цель сериализации SSZ — представить объекты произвольной сложности в виде строк байтов. Это очень простой процесс для «базовых типов». Элемент просто преобразуется в шестнадцатеричные байты. К базовым типам относятся:
- беззнаковые целые числа
- логические значения (булевы типы)
Для сложных «составных» типов сериализация сложнее, поскольку составной тип содержит несколько элементов, которые могут иметь разные типы, разные размеры или и то, и другое. Если все эти объекты имеют фиксированную длину (т. е. размер элементов всегда будет постоянным независимо от их фактических значений), сериализация представляет собой простое преобразование каждого элемента составного типа в упорядоченные строки байтов в формате little-endian (от младшего к старшему). Эти строки байтов объединяются вместе. Сериализованный объект имеет представление элементов фиксированной длины в виде списка байтов в том же порядке, в котором они появляются в десериализованном объекте.
Для типов с переменной длиной фактические данные заменяются значением «смещения» в позиции этого элемента в сериализованном объекте. Фактические данные добавляются в кучу в конце сериализованного объекта. Значение смещения — это индекс начала фактических данных в куче, действующий как указатель на соответствующие байты.
В приведенном ниже примере показано, как работает смещение для контейнера с элементами как фиксированной, так и переменной длины:
struct Dummy {
number1: u64,
number2: u64,
vector: Vec<u8>,
number3: u64
}
dummy = Dummy{
number1: 37,
number2: 55,
vector: vec![1,2,3,4],
number3: 22,
}
serialized = ssz.serialize(dummy)
serialized будет иметь следующую структуру (здесь дополнено только до 4 бит, в реальности дополняется до 32 бит, а представление int сохранено для ясности):
[37, 0, 0, 0, 55, 0, 0, 0, 16, 0, 0, 0, 22, 0, 0, 0, 1, 2, 3, 4]
------------ ----------- ----------- ----------- ----------
| | | | |
число1 число2 смещение число 3 значение
для вектора для вектора
разделено на строки для ясности:
[
37, 0, 0, 0, # кодирование `number1` в формате little-endian.
55, 0, 0, 0, # кодирование `number2` в формате little-endian.
16, 0, 0, 0, # «Смещение», указывающее, где начинается значение `vector` (16 в формате little-endian).
22, 0, 0, 0, # кодирование `number3` в формате little-endian.
1, 2, 3, 4, # Фактические значения в `vector`.
]
Это все еще упрощение — целые числа и нули на схемах выше на самом деле будут храниться в виде списков байтов, например так:
[
10100101000000000000000000000000 # кодирование `number1` в формате little-endian
10110111000000000000000000000000 # кодирование `number2` в формате little-endian.
10010000000000000000000000000000 # «Смещение», указывающее, где начинается значение `vector` (16 в формате little-endian).
10010110000000000000000000000000 # кодирование `number3` в формате little-endian.
10000001100000101000001110000100 # Фактическое значение поля `bytes`.
]
Таким образом, фактические значения для типов переменной длины хранятся в куче в конце сериализованного объекта, а их смещения хранятся на соответствующих позициях в упорядоченном списке полей.
Существуют также некоторые особые случаи, требующие специфической обработки, например тип BitList, который требует добавления ограничения длины во время сериализации и его удаления во время десериализации. Полная информация доступна в спецификации SSZ (opens in a new tab).
Для десериализации этого объекта требуется схема. Схема определяет точную структуру сериализованных данных, чтобы каждый конкретный элемент мог быть десериализован из блоба байтов в осмысленный объект, элементы которого имеют правильный тип, значение, размер и позицию. Именно схема сообщает десериализатору, какие значения являются фактическими, а какие — смещениями. Все имена полей исчезают при сериализации объекта, но восстанавливаются при десериализации в соответствии со схемой.
Построение дерева Меркла
Этот сериализованный объект SSZ затем может быть преобразован в дерево Меркла, то есть трансформирован в представление тех же данных в виде дерева Меркла. Сначала определяется количество 32-байтовых фрагментов в сериализованном объекте. Это «листья» дерева. Общее количество листьев должно быть степенью двойки, чтобы хеширование листьев вместе в конечном итоге дало единый корень хеш-дерева. Если это не так по умолчанию, добавляются дополнительные листья, содержащие 32 байта нулей. Схематично:
корень хеш-дерева
/ \
/ \
/ \
/ \
хеш листьев хеш листьев
1 и 2 3 и 4
/ \ / \
/ \ / \
/ \ / \
лист1 лист2 лист3 лист4
Бывают также случаи, когда листья дерева не распределяются равномерно естественным образом, как в примере выше. Например, лист 4 может быть контейнером с несколькими элементами, которые требуют добавления дополнительной «глубины» в дерево Меркла, создавая неравномерное дерево.
Вместо того чтобы называть эти элементы дерева листом X, узлом X и т. д., мы можем присвоить им обобщенные индексы, начиная с корня = 1 и считая слева направо на каждом уровне. Это и есть обобщенный индекс, объясненный выше. Каждый элемент в сериализованном списке имеет обобщенный индекс, равный 2**depth + idx, где idx — это его позиция с нулевым индексом в сериализованном объекте, а depth (глубина) — это количество уровней в дереве Меркла, которое можно определить как логарифм по основанию два от количества элементов (листьев).
Обобщенные индексы
Обобщенный индекс — это целое число, представляющее узел в бинарном дереве Меркла, где каждый узел имеет обобщенный индекс 2 ** depth + index in row.
1 --глубина = 0 2**0 + 0 = 1
2 3 --глубина = 1 2**1 + 0 = 2, 2**1+1 = 3
4 5 6 7 --глубина = 2 2**2 + 0 = 4, 2**2 + 1 = 5...
Это представление дает индекс узла для каждого фрагмента данных в дереве Меркла.
Мультидоказательства
Предоставление списка обобщенных индексов, представляющих конкретный элемент, позволяет нам проверить его по корню хеш-дерева. Этот корень — наша принятая версия реальности. Любые предоставленные нам данные могут быть проверены на соответствие этой реальности путем вставки их в правильное место в дереве Меркла (определяемое его обобщенным индексом) и наблюдения за тем, что корень остается неизменным. В спецификации здесь (opens in a new tab) есть функции, которые показывают, как вычислить минимальный набор узлов, необходимый для проверки содержимого определенного набора обобщенных индексов.
Например, чтобы проверить данные по индексу 9 в дереве ниже, нам нужен хеш данных по индексам 8, 9, 5, 3, 1. Хеш (8,9) должен равняться хешу (4), который хешируется с 5 для получения 2, который хешируется с 3 для получения корня дерева 1. Если бы для 9 были предоставлены неверные данные, корень изменился бы — мы бы обнаружили это и не смогли бы проверить ветвь.
* = данные, необходимые для генерации доказательства
1*
2 3*
4 5* 6 7
8* 9* 10 11 12 13 14 15