Що таке Дерево Меркла?

Коротко

- Дерева Меркла були названі на честь вченого комп'ютерника, який їх запропонував.

- Це форма структури даних, яка використовується в інформатиці та блокчейні.

- Дерева Меркла або хеш-дерева призначені для ефективної та безпечної перевірки транзакцій у блокчейні.

- Щоб підтвердити наявність транзакції у блокчейні, потрібно просто запитати її, і дерево Меркла прискорить процес перевірки.

Словосполучення Merkle Tree було названо на честь однойменного комп’ютерника. Ральфа Меркла, який також розробив криптографічне хешування, запропонував ідею дерев Меркла в 1987 році. Він написав статтю під назвою «Цифровий підпис на основі звичайної функції шифрування».

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



Композиція Дерева Меркла

---

Дерево Меркла, як на показано прикладі вище, має структуру дерева. Він має корінь і гілки, кожна зі своєю функцією. На відміну від справжніх дерев, коріння дерев Меркла знаходиться вгорі, а не внизу. Отже, хеш на самій вершині цього дерева - це корінь, за яким йдуть гілки та листя внизу.

У Біткойні корінь є частиною заголовка блоку, що гарантує наявність транзакцій. Гілки - це вузли, які містять значення вузлів під ними, виступаючи як їхні "батьківські вузли". Як правило, у деревах Меркла ці вузли ніколи не містять більше двох вузлів під ними, тому вони називаються бінарними хеш-деревами.

Однак хеш-дерево може мати більше двох вузлів.

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

Як працюють дерева Меркла

Блокчейн Біткойна, мабуть, є визначним прикладом використання дерев Меркла, і ось як це працює. Зазвичай дерева Меркла використовуються для прискорення та підвищення ефективності перевірки даних.

Щоразу, коли виникає необхідність перевірити правильність набору даних з первинного набору транзакцій, дерева Меркла гарантують, що немає необхідності отримувати весь інформаційний файл.

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

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





Важливість дерева Меркла

---

Дерева Меркла є безцінним інструментом для перевірки даних у блокчейні та інформатиці загалом з наступних причин:

Скорість

Уявіть, що вам потрібно перевірити наявність певних даних у блокчейні. Без дерев Меркла вам довелося б завантажувати весь блокчейн і просівати його. Очевидно, що це зайняло набагато більше часу, ніж необхідно, оскільки обсяг даних в блокчейнах зазвичай величезний і досягає сотень гігабайт. Біткойн, наприклад, містить до 389 гігабайт даних станом на квітень цього року, згідно зі звітом Statista. Однак за допомогою Дерева Меркла ви можете легко відслідковувати свій конкретний запит про транзакцію та отримувати відповіді протягом меншого періоду часу.

Ефективність

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

Довіра

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



А також нещодавній привабливий "100% доказ маржі"

---

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




Як Gate.io використовує зашифрований UID користувача та баланс для побудови Дерева Меркла?

---

Спочатку експортуйте зашифрований ідентифікатор користувача та відповідний баланс користувача з бази даних Gate.io. Кожна пара зашифрованих ідентифікаторів і балансів користувача буде хешуватися окремо, а потім об'єднуватися для формування базових блоків даних. Для кожного блоку даних використовується та сама хеш-функція для генерації кінцевого вузла Дерева Меркла. Отримані зашифровані дані будуть хешовані разом у парах для створення батьківського вузла кінцевого вузла. Цей процес триває доти, доки не будуть отримані єдині хеш-дані, а саме корінь Меркла. Після успішної побудови дерева Меркла кінцевий вузол буде експортований у вигляді текстового файлу, а потім випущений аудитором разом із кореневим хешем Меркла.

Коли загальні активи платформи, перевірені у вигляді дерева Меркла, більші або рівні 100%, це доводить, що платформа зберегла засоби користувача незайманими, що означає, що платформа надає 100% відповідних активів як маржу. Ви можете переглянути більше інформації про Gate.io 100% Proof of Margin на сторінці з деталями Gate.io або на офіційному сайті Armanino.



Висновок

---

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

Автор: М. Олатунджі, дослідник Gate.io
* Ця стаття представляє лише погляди спостерігачів і не містить інвестиційних пропозицій.
*Gate.io залишає за собою всі права на цю статтю. Повторне розміщення статті буде дозволено за умови посилання на Gate.io. У всіх інших випадках через порушення авторських прав буде подано судовий позов.