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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Приклад бінарного дерева гешування. Геші 0-0 і 0-1 це геші блоків даних L1 і L2, відповідно. Геш 0 — це геш об'єднання Гешів 0-0 і 0-1.

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

Дані поділяються на малі частини (блоки), які індивідуально гешуються за допомогою 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[en] [1]. Геш-дерева також використовуються в геш-криптографії[en] .

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

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

Tiger геш-дерево (TTH)[ред.ред. код]

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

Tiger геш-дерево використовуються в Gnutella та Direct Connect P2P, Phex [en] та DC ++ [en] [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. 
  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. (March 4, 2003). Tree Hash EXchange format (THEX). Архів оригіналу за 2009-08-03. 
  9. DC++'s feature list. dcplusplus.sourceforge.net.