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

Проста серіалізація (SSZ) — це метод серіалізації, що використовується в Beacon Chain. Він замінює серіалізацію RLP, яка використовується на рівні виконання, всюди на рівні консенсусу, за винятком протоколу виявлення однорангових вузлів. Щоб дізнатися більше про серіалізацію RLP, див. Префікс рекурсивної довжини (RLP). SSZ розроблено так, щоб бути детермінованим, а також для ефективної мерклізації. Можна вважати, що SSZ складається з двох компонентів: схеми серіалізації та схеми мерклізації, розробленої для ефективної роботи з серіалізованою структурою даних.

Як працює SSZ?

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

SSZ — це схема серіалізації, яка не є самоописовою, а покладається на схему, яка має бути відома заздалегідь. Метою серіалізації SSZ є представлення об’єктів довільної складності у вигляді рядків байтів. Для «базових типів» це дуже простий процес. Елемент просто перетворюється на шістнадцяткові байти. До базових типів належать:

беззнакові цілі числа
Логічні значення

Для складних «композитних» типів серіалізація є складнішою, оскільки композитний тип містить кілька елементів, які можуть мати різні типи, різні розміри або і те, й інше. Якщо всі ці об’єкти мають фіксовану довжину (тобто розмір елементів завжди буде постійним незалежно від їхніх фактичних значень), серіалізація — це просто перетворення кожного елемента в композитному типі, упорядкованого в байтові рядки з порядком від молодшого до старшого. Ці байтові рядки об’єднуються. Серіалізований об’єкт має представлення у вигляді байтового списку елементів фіксованої довжини в тому самому порядку, у якому вони з’являються в десеріалізованому об’єкті.

Для типів зі змінною довжиною фактичні дані замінюються значенням «зсуву» в позиції цього елемента в серіалізованому об’єкті. Фактичні дані додаються до купи в кінці серіалізованого об’єкта. Значення зсуву — це індекс початку фактичних даних у купі, що діє як вказівник на відповідні байти.

Наведений нижче приклад ілюструє, як працює зсув для контейнера з елементами як фіксованої, так і змінної довжини:

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   number1       number2      зсув для    number3    значення для
5                              вектора                  вектора
6

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

1[
2  37, 0, 0, 0,  # кодування `number1` з порядком від молодшого до старшого.
3  55, 0, 0, 0,  # кодування `number2` з порядком від молодшого до старшого.
4  16, 0, 0, 0,  # «зсув», що вказує, де починається значення `vector` (16 з порядком від молодшого до старшого).
5  22, 0, 0, 0,  # кодування `number3` з порядком від молодшого до старшого.
6  1, 2, 3, 4,   # Фактичні значення у `vector`.
7]

Це все ще спрощення — цілі числа та нулі на наведених вище схемах насправді зберігатимуться у вигляді байтових списків, ось так:

1[
2  10100101000000000000000000000000  # кодування `number1` з порядком від молодшого до старшого
3  10110111000000000000000000000000  # кодування `number2` з порядком від молодшого до старшого.
4  10010000000000000000000000000000  # «зсув», що вказує, де починається значення `vector` (16 з порядком від молодшого до старшого).
5  10010110000000000000000000000000  # кодування `number3` з порядком від молодшого до старшого.
6  10000001100000101000001110000100   # Фактичне значення поля `bytes`.
7]

Отже, фактичні значення для типів змінної довжини зберігаються в купі в кінці серіалізованого об’єкта, а їхні зсуви зберігаються в правильних позиціях у впорядкованому списку полів.

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

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

Для десеріалізації цього об’єкта потрібна схема. Схема визначає точне компонування серіалізованих даних, щоб кожен конкретний елемент можна було десеріалізувати з блобу байтів у певний значущий об’єкт, елементи якого мають правильний тип, значення, розмір і положення. Саме схема вказує десеріалізатору, які значення є фактичними, а які — зсувами. Усі назви полів зникають під час серіалізації об’єкта, але відновлюються під час десеріалізації відповідно до схеми.

Дивіться інтерактивне пояснення на 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