Дерево Меркла

Дерево Меркла (геш-дерево, tiger tree tashing, англ. Merkle tree) представляє собою особливу структуру даних, яка містить підсумкову інформацію про якийсь більший обсяг даних. Використовується для перевірки цілісності даних.

Приклад бінарного дерева гешування. Геші 0-0 і 0-1 це геші блоків даних L1 і L2, відповідно. Геш 0 — це геш об'єднання Гешів 0-0 і 0-1.

Дані поділяються на малі частини (блоки), які індивідуально гешуються за допомогою Leaf Tiger Hash, потім з кожної пари гешів по черзі обчислюється Internal Tiger Hash. Якщо до гешу немає пари, то він переноситься в новий ланцюжок без змін. Далі в ланцюжку для кожної пари знову обчислюється Internal Tiger Hash. Ця процедура повторюється до тих пір, поки не залишиться один геш. Цей один геш, що залишився, називають Tiger Tree Root. Саме його використовують для однозначної ідентифікації файлу і вказують у різних P2P посиланнях.

Level		Tiger Tree Root
|                   /
0:            --- 21 -- -------\            
             /         \        \
1:       - 20 -         19 ------\
        /      \         \        \
2:    17        18        19 ------ Internal Tiger Hashes
     /  \      /  \      /  \     /   
3:  12   13   14   15   16  11 --/
    /\   /\   /\   /\   /\   \
4: 1  2 3  4 5  6 7  8 9 10  11 ---  Leaf Tiger Hashes

Використання

Геш-дерева використовуються для перевірки даних, що зберігаються, обробляються та передаються в комп'ютерах та між ними. Забезпечують перевірку на цілісність та достовірність даних та окремих блоків, що передаються між вузлами peer-to-peer мережі. Геш-дерева застосовуються в системах trusted computing[1]. Геш-дерева також використовуються в геш-криптографії.

Геш-дерева використовуються у файлових системах IPFS, Btrfs та ZFS[2] для протидії Деградації даних[3], програмі розповсюдженя даних Dat, протоколі Google Wave[4], розподіленій системи керування версіями Git та Mercurial, резервній системі Tahoe-LAFS, однорангових мережах Bitcoin та Ethereum[5], фреймворку прозорості сертифікатів, системах Riak та Dynamo[6].

Початкова реалізація дерева Меркла у Bitcoin від Сатосі Накамото застосовує крок стиснення геш-функції до надмірного рівня, що полегшує використання дерев типу Fast Merkle[7].

Огляд

Дерево гешів це двійкове дерево гешів, в якому листи є геш-блоками даних, наприклад, файлу або набору файлів. Верхні вузли дерева є гешами своїх «дітей». Наприклад, на зображенні hash 0 є результат гешування конкатенації hash 0-0 та hash 0-1. Тобто, hash 0 = hash (hash 0-0 + hash 0-1), де + означає конкатенацію.

Більшість реалізацій геш-дерев є двійковими (два дочірні вузли під кожним вузлом), але вони можуть використовувати також і багато інших дочірніх вузлів під кожним вузлом.

Як правило, для гешування використовується криптографічна геш-функція, така як SHA-2. Якщо геш-дерево потребує лише захисту від ненавмисного пошкодження, може бути використана необов'язкова контрольна сума, така як CRCs.

У верхній частині геш-дерева є верхній геш (або root hash, або master hash). Перш ніж завантажувати файл у мережу P2P, в більшості випадків верхній геш отримується з надійного джерела, наприклад, вебсайту, який, як відомо, має хороші рекомендації щодо завантаження файлів. Коли доступний верхній геш, геш-дерево може бути отримано з будь-якого неперевіреного джерела, як і будь-який рівноправний вузол у мережі P2P. Потім отримане геш-дерево порівнюється з перевіреним верхнім гешем, а якщо дерево гешування пошкоджене або підроблене, буде братися інше дерево гешу з іншого джерела, поки програма не знайде той, який дорівнює верхньому гешу.

Основна відмінність від геш-таблиці полягає в тому, що одна гілка геш-дерева може бути завантажена у необхідний час, а цілісність кожної гілки може бути перевірена негайно, навіть якщо все дерево ще недоступне. Наприклад, на зображенні цілісність блоку даних L2 можна перевірити негайно, якщо дерево вже містить hash 0-0 і hash 1, гешувавши блок даних і послідовно поєднуючи його результат з hash 0-0, а потім hash 1 і, нарешті, порівняння результату з top hash. Аналогічним чином, цілісність блоку даних L3 можна перевірити, якщо в дереві вже є hash 1-1 і hash 0. Це є перевагою, оскільки необхідно розбивати файли в дуже малих блоках даних, так що лише невеликі блоки повинні бути повторно завантажені, якщо вони пошкоджені. Якщо геш-файл дуже великий, таке геш-дерево або геш-список стає досить великим. Але якщо це дерево, можна швидко завантажити одну невелику гілку, можна перевірити цілісність гілки, а потім завантажувати блоки даних.

Друга атака знаходження першовзору

Merkle root hash не вказує на глибину дерева, застосувавши атаку знаходження першовзору, в якому зловмисник створює документ, відмінний від оригіналу, який має той же Merkle hash root. У наведеному вище прикладі зловмисник може створити новий документ, що містить два блоки даних, де в першому є hash 0-0 + hash 0-1, а другий — hash 1-0 + hash 1-1.

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

Tiger геш-дерево (TTH)

Tiger геш-дерево є широко використовуваною формою геш-дерева. Він використовує двійкове геш-дерево (два дочірні вузли під кожним вузлом), зазвичай має розмір блоку даних 1024 байт і використовує Tiger hash.[8]

Tiger геш-дерево використовуються в Gnutella та Direct Connect P2P, Phex та DC ++[9] .

Приклади

Base32: RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN: urn:tree:tiger:RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Magnet-посилання: magnet:?xt=urn:tree:tiger:RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Див. також

Примітки
  1. Kilian, J. (1995). Improved efficient arguments (preliminary version). CRYPTO.
  2. Bonwick, Jeff. ZFS End-to-End Data Integrity. Jeff Bonwick's Blog.
  3. Likai Liu. Bitrot Resistance on a Single Drive. likai.org.
  4. General Verifiable Federation. Google Wave Protocol. Архів оригіналу за 28 вересня 2013. Процитовано 6 січня 2018.
  5. Koblitz, Neal; Menezes, Alfred J. (January 2016). Cryptocash, cryptocurrencies, and cryptocontracts. Designs, Codes and Cryptography 78 (1): 87–102. doi:10.1007/s10623-015-0148-5.
  6. Adam Marcus. The NoSQL Ecosystem. aosabook.org. «When a replica is down for an extended period of time, or the machine storing hinted handoffs for an unavailable replica goes down as well, replicas must synchronize from one another. In this case, Cassandra and Riak implement a Dynamo-inspired process called anti-entropy. In anti-entropy, replicas exchange Merkle trees to identify parts of their replicated key ranges which are out of sync. A Merkle tree is a hierarchical hash verification: if the hash over the entire keyspace is not the same between two replicas, they will exchange hashes of smaller and smaller portions of the replicated keyspace until the out-of-sync keys are identified. This approach reduces unnecessary data transfer between replicas which contain mostly similar data.»
  7. Mark Friedenbach: Fast Merkle Trees
  8. Chapweske, J.; Mohr, G. (4 березня 2003). Tree Hash EXchange format (THEX). Архів оригіналу за 3 серпня 2009.
  9. DC++'s feature list. dcplusplus.sourceforge.net.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.