Эта статья является кандидатом в добротные статьи

Дерево хешей

Материал из Википедии — свободной энциклопедии
(перенаправлено с «TTH»)
Перейти к: навигация, поиск
Бинарное хеш-дерево

Хеш-деревом, деревом Меркла (англ. Merkle tree) называют полное двоичное дерево, в листовые вершины которого помещены хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Корневой узел дерева содержит хеш от всего набора данных, то есть хеш-дерево является однонаправленной хеш-функцией. Дерево Меркла используется в различных областях криптографии. Его выгодно использовать как альтернативу обычному хешированию, поскольку оно позволяет эффективно проверять целостность данных[1].

История[править | править код]

Свое название Дерево Меркла получило в честь его создателя, Ральфа Меркла. Он предложил использовать хеш-дерево для генерации многоразовой подписи, которая основывалась на одноразовой подписи Лэмпорта. Патент на многоразовую подпись был зарегестрирован Ральфом Мерклом в 1979 году[2]. После этого Дерево Меркла нашло применение в задачах, требующих эффективной верификации больших объемов данных, полученных от недоверенных источников. На сегодняшний день его используют в p2p-сетях обмена файлами[3], в криптовалютах (Ethereum и Bitcoin) для хранения транзакций в блоке[4][5], в базах данных, критичных к целостности[6][7].

Структура[править | править код]

Хеш-дерево является древовидным графом, где каждый узел содержит некоторый хеш. Каждая листовая вершина содержит хеш от блока данных, например, от части файла, или же от файла целиком. Узловые ноды хранят хеши от объединенных хешей их детей. На дереве на картинке выше , где означает конкатенацию, а , это хеши от соответствующих блоков данных и [6].

Преимущества[править | править код]

Доказательство существования в хеш-дереве

Хеш-деревья имеют преимущество перед хеш-цепочками или хеш-функциями. При использовании хеш-деревьев гораздо менее затратным является доказательство принадлежности определенного блока данных к множеству. Поскольку различными блоками часто являются независимые данные, такие как транзакции или части файлов, то нас интересует возможность проверить только один блок, не пересчитывая хеши для остальных узлов дерева. Пусть интересующий нас блок это (см. рис.). Тогда доказательством его существования и валидности будут корневой хеш, а также верхние хеши других веток ( и )[7]. Зная эту информацию, проверить корневой хеш можно за операций, где это высота дерева.

В данном случае проверка не пройдена, если .

В общем случае можно записать

,

а проверку осуществить как , где

[8].

Недостатки[править | править код]

Как описано в разделе Преимущества, каждому блоку можно сопоставить подпись, подтверждающую его валидность. В нее войдут сам блок и узел дерева (на рис. отмечены желтым).

.

Для вычисления подписи произвольного блока нужно знать все значения из множества . Это не вызывает проблем, если есть возможность хранить все внутренние вершины дерева в памяти, однако для больших деревьев (количество листьев может увеличиваться до ) это не подходит. Можно также каждый раз вычислять внутренние блоки заново, но это значительно замедлит производительность такой системы. Поэтому возникает проблема эффективного обхода дерева и генерации подписей (англ. Merkle tree traversal problem)[8]. На сегодняшний день существуют решения использующие времени и памяти, где это количество листьев. Было также доказано, что не существует алгоритма обхода, который бы был одновременно лучше, чем и по времени, и по памяти[1].

Применение[править | править код]

Bitcoin[править | править код]

Хеш-деревья используются для хранения хеша набора транзакций в блокчейне криптовалют (например, в Bitcoin, Ethereum). В спецификации Bitcoin каждый блок содержит поле merkle_root размером 32 байта, которое соответствует корневому значению хеш-дерева всех транзакций в этом блоке[9]. В качестве хеш-функции используется двойное SHA-256, то есть .

Пример хеш-дерева в блоке Bitcoin

Если транзакция не имеет пары, она дублируется.

Снижение размера блока[править | править код]

После накопления достаточного числа блоков можно удалять старые транзакции для экономии места. При этом сам блок остается неизменным, так как в нем хранится только merkle_root. Блок без транзакций занимает 80 Б или 4.2 МБ в год (при генерации блока каждые 10 минут)[5].

Упрощенная проверка платежей[править | править код]

Существует возможность верификации транзакций без необходимости запускать свой узел p2p-сети. Пользователю достаточно запросить только заголовки блоков, а также «ветвь» дерева Меркла ведущую к необходимой транзакции (см. Преимущества). Проверив, что цепочка блоков корректна и имеет достаточную сложность, пользователь может считать, что транзакция верифицирована. Использование этого метода, однако, требует, чтобы пользователь доверял узлу сети, у которого будет запрашивать заголовки блоков. Один из способов избежать атаки, то есть подмены узла недобросовестной стороной, — рассылать оповещения по всей сети при обнаружении ошибки в блоке, вынуждая пользователя загружать блок целиком[5].

На упрощенной проверке платежей (англ. Simplified payment verification) основана работа так называемых «тонких» клиентов Bitcoin[10].

P2P-сети[править | править код]

В файлообменных p2p-сетях Дерево Меркла используется для идентификации, поиска источников и проверки целостности файлов. В протоколах Gnutella2 и Direct Connect применяется реализация хеш-деревеьев под названием Tiger Tree Hash[11][12].

Tiger Tree Hash[править | править код]

Широко распространенная реализация хеш-дерева общего назначения. Она имеет двоичную структуру и использует Tiger Hash в качестве хеш-функции. Размер блока составляет 1024 байта или меньше, если данных не хватает на полное заполнение блока.

Блоки индивидуально хешируются по схеме , а внутренние эелементы как . Корневой элемент называется Tiger Tree Root. Его используют для однозначной идентификации файла и указывают в различных P2P ссылках[3].

Пример хеш-дерева TTH

Если хеш не имеет пары, он переносится на следующий уровень без изменений.

Сжатый формат представления хеш-дерева[править | править код]

В p2p-протоколах существует общепринятый формат для записи хеш-дерева в сжатом виде. Запись хешей идет от корня дерева, каждый уровень записывается слева направо. Такой формат называется Breadth-first, поскольку соответствует обходу дерева в ширину[3].

Сравнение с BitTorrent Info Hash[править | править код]

В отличие от Info Hash торрент файла:

  1. Дерево Меркла зависит только от данных файла и не меняется при переименовании/перемещении файла.
  2. TTH обычно применяется ровно к одному файлу.
  3. Корень дерева Меркла не зависит от размера проверяемого блока, поскольку уровень детализации может варьироваться.

Примечания[править | править код]

  1. 1 2 Michael Szydlo Merkle Tree Traversal in Log Space and Time (англ.) // Advances in Cryptology - EUROCRYPT 2004. — Springer, Berlin, Heidelberg, 2004-05-02. — P. 541–554. — ISBN 9783540219354, 9783540246763. — DOI:10.1007/978-3-540-24676-3_32.
  2. Ральф Меркл. Method of providing digital signatures (патент US 4309569 A) (англ.). Патентное бюро США (January 1982).
  3. 1 2 3 J. Chapweske, G. Mohr. Tree Hash EXchange format (THEX) (англ.). Onion Networks, Inc. (4 March 2003). — Стандарт обмена хеш-деревьями над файлами. Проверено 8 декабря 2017.
  4. Whitepaper проекта Ethereum (англ.). Ethereum.
  5. 1 2 3 Сатоши Накамото Биткойн: система цифровой пиринговой наличности (рус.) // bitcoin.org.
  6. 1 2 Premkumar Devanbu, Michael Gertz, Charles Martel, Stuart G. Stubblebine Authentic Third-Party Data Publication (англ.) // Data and Application Security. — Springer, Boston, MA, 2002. — P. 101–112. — ISBN 9780792375142, 9780306470080. — DOI:10.1007/0-306-47008-x_9.
  7. 1 2 Einar Mykletun, Maithili Narasimha, Gene Tsudik. [https://people.eecs.berkeley.edu/~raluca/cs261-f15/readings/merkleodb.pdf Providing Authentication and Integrity in Outsourced Databases using Merkle Hash Tree’s] (англ.) // ACM Transactions on Storage : Журнал. — 2006. — Май (vol. 2, no. 2). — P. 107 — 138.
  8. 1 2 Georg Becker, Ruhr-universität Bochum. Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis.
  9. Спецификация заголовков блока в биткоин-сети (англ.). en.bitcoin.it/wiki.
  10. Simplified Payment Verification (англ.). Глоссарий Bitcoin. Проверено 7 декабря 2017.
  11. Возможности клиента DC++ (англ.). dcplusplus.sourceforge.net. Проверено 8 декабря 2017.
  12. Стандарт протокола Gnutella2 (англ.). g2.doxu.org. Проверено 8 декабря 2017.

См. также[править | править код]

Ссылки[править | править код]

  • Merkle Patricia Tree — улучшенная реализация дерева Меркла, использующаяся в Ethereum.
  • TTHSum — консольная утилита, позволяющая быстро вычислить TTH.
  • RHash — консольная утилита, вычисляющая TTH (и другие хэши) и создающая магнитные ссылки.
  • EAD TorrentBuild — генератор торрентов, позволяющий создавать .torrent файлы, богатые дополнительными хешами. Поддерживаются хеши CRC32, MD5, ED2K, TTH, SHA-1.
  • Tiger Tree Torrent — предложение по замене SHA-1 на Tiger Tree Hash в .torrent файлах.