29 липня 2022

Дерево Меркла: ось чому Optimistic Rollups будуть безпечними

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

Анонс доказів Меркла пройшов непомітно: в описі оновлення Jakarta їм приділили один рядок, а в документації — сторінку про формат доказів. Тому ми розповімо про все послідовно.

Що таке дерево Меркла

Основа дерева Меркла — хешування даних. Хешування — це перетворення інформації за спеціальним алгоритмом, в результаті якого виходить унікальний рядок певної довжини. Якщо повторно хешувати ту саму інформацію, то результат — хеш чи чек-сума — буде однаковим. Якщо у файлі змінився хоч один біт інформації, то хеш також зміниться.

Хешування використовується для автентифікації отриманих даних. Наприклад, до файлів на торент-трекерах часто додаються чек-суми оригіналу. Коли користувач завантажить його на свій комп’ютер, він може порахувати чек-суму своєї копії та порівняти з оригінальною. Якщо вони збігаються, файл завантажився без помилок.

При завантаженні великої кількості файлів неефективно рахувати і порівнювати чек-суми кожного фрагмента. Простіше зібрати дані в одне місце, наприклад в архів, і хешувати вже його. Порівнюючи хеші двох таких архівів можна зрозуміти, чи файли завантажувалися правильно. Але якщо хеші не збігаються, то доведеться розпакувати архів і все ж хешувати фрагменти окремо та порівнювати результати з хешами оригінальних файлів, щоб знайти битий фрагмент.

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

Дерево Меркла складається з трьох елементів:

лиски — початкові фрагменти даних (DATA A, DATA B…);
гілки або вузли дерева (не плутати з вузлами блокчейну) — хеші попередніх пар листків або гілок (ABC, BDE);
корінь — хеш всього дерева (DFA).

Ноди в блокчейн-протоколі зберігають у дереві Меркла всі блоки та їх хеші. Корінь відповідає поточному стану всього блокчейна, тобто в ньому захешовані баланси всіх користувачів. У Tezos він називається Context Hash, і бейкери включають його в заголовок кожного видобутого блоку.

За допомогою звіряння Context ноди можуть швидко підтвердити або спростувати те, що бейкер при створенні блоку використовував коректні дані про попередні операції в блокчейні.

Але це спрощене пояснення. Насправді структура Tezos складніша і включає велику кількість гілок для оптимізації пошуку та роботи з даними.

Чому дерево Меркла важливе для Optimistic Rollups

За допомогою дерева Меркла можна швидко довести, що якийсь фрагмент даних входить до зазначеного набору даних без розкриття всіх інших фрагментів — це називається доказом Меркла (Merkle Proof).

Наприклад, щоб довести, що транзакція дійсно була включена до блоку C, нода надає для перевірки опис шляху від транзакції C до кореня дерева. При цьому їй не потрібно розкривати вміст інших елементів (Blinded Nodes або прихованих вузлів) — достатньо надати відповідні хеші. Якщо все правильно, то при повторенні шляху перевіряючий отримає той самий корінь.

За розрахунками команди Tarides, такий доказ Меркла для 100 операцій вміщується в 46 КБ, тоді як «реальний» доказ із усіма транзакціями та балансами користувачів займе 3,4 ГБ.

Доказ Меркла необхідний для роботи ролапів, оскільки він дозволяє L1-ноді за секунди переконатися у валідності операцій на L2-чейні, навіть якщо L1-ноди немає повного L2-чейна. Або навпаки, довести, що транзакція в L2-чейні хибна, і оператор ролапа намагається всіх обдурити.

Ось так дерево Меркла робить ролапи безпечними та чесними для користувачів.

Підписуйтесь на соціальні мережі Tezos Ukraine, щоб нічого не пропустити: