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

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

Як працює SSZ?

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

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

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

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

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

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


    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]
------------  -----------  -----------  -----------  ----------
      |             |            |           |            |
   number1       number2    зміщення      number 3   значення
                           для вектора                 вектора

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

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

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

[
  10100101000000000000000000000000  # кодування little-endian для `number1`
  10110111000000000000000000000000  # кодування little-endian для `number2`.
  10010000000000000000000000000000  # «Зміщення», яке вказує, де починається значення `vector` (little-endian 16).
  10010110000000000000000000000000  # кодування little-endian для `number3`.
  10000001100000101000001110000100   # Фактичне значення поля `bytes`.
]

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

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

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

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

Див. ssz.dev (opens in a new tab) для інтерактивного пояснення цього процесу.

Мерклізація

Цей серіалізований об'єкт SSZ потім може бути мерклізований — тобто перетворений на представлення тих самих даних у вигляді дерева Меркла. Спочатку визначається кількість 32-байтових фрагментів у серіалізованому об'єкті. Це «листя» дерева. Загальна кількість листків має бути ступенем двійки, щоб хешування листків разом у підсумку дало єдиний корінь хеш-дерева (hash-tree-root). Якщо це не так від природи, додаються додаткові листки, що містять 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