Послушайте эту статью
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Пример двоичного хеш-дерева. Хеш-значения 0-0 и 0-1 - это хеш-значения блоков данных L1 и L2, соответственно, а хеш-код 0 - это хеш-код объединения хеш-значений 0-0 и 0-1.

В криптографии и компьютерной науки , хэш дерева или Merkle дерево представляет собой дерево , в котором каждый узел лист помечен криптографической хэш - блока данных, и каждый узел не лист помечен криптографической хэш меток его дочерних узлов . Деревья хеширования позволяют эффективно и безопасно проверять содержимое больших структур данных . Хеш-деревья - это обобщение хеш-списков и хеш-цепочек .

Чтобы продемонстрировать, что листовой узел является частью заданного двоичного хеш-дерева, необходимо вычислить количество хеш-значений, пропорциональное логарифму количества листовых узлов дерева; [1] это контрастирует с хэш-списками, где число пропорционально количеству самих листовых узлов.

Концепция хеш-деревьев названа в честь Ральфа Меркла , который запатентовал ее в 1979 году. [2] [3]

Использует [ редактировать ]

Деревья хеширования могут использоваться для проверки любых данных, которые хранятся, обрабатываются и передаются между компьютерами. Они могут помочь гарантировать, что блоки данных, полученные от других одноранговых узлов в одноранговой сети , получены неповрежденными и неизменными, и даже для проверки того, что другие одноранговые узлы не лгут и не отправляют поддельные блоки.

Деревья хеширования используются в криптографии на основе хешей . Деревья хеширования также используются в файловых системах IPFS , Btrfs и ZFS [4] (для противодействия деградации данных [5] ); Dat протокола; Протокол Apache Wave ; [6] Распределенные системы контроля версий Git и Mercurial ; Тахо-LAFS системы резервного копирования; Зеронет ; в Bitcoin и Эфириума равный-равному сети; [7] структура прозрачности сертификатов ; и рядСистемы NoSQL , такие как Apache Cassandra , Riak и Dynamo . [8] Были сделаны предложения использовать хеш-деревья в надежных вычислительных системах. [9]

Первоначальная реализация деревьев Меркла в биткойнах, разработанная Сатоши Накамото, чрезмерно использует этап сжатия хэш-функции, что смягчается за счет использования быстрых деревьев Меркла. [10]

Обзор [ править ]

Хэш дерево представляет собой дерево из хэш , в котором листы являются хэш данных блоков в, например, файл или набор файлов. Узлы, расположенные дальше по дереву, являются хешами своих дочерних узлов. Например, в картине хэша 0 результат хэширования конкатенацию из хэш 0-0 и хэш 0-1 . То есть хэш 0 = хэш (хеш (0-0) + хеш (0-1)), где + означает конкатенацию.

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

Обычно для хеширования используется криптографическая хеш-функция, такая как SHA-2 . Если хеш-дереву требуется только защита от непреднамеренного повреждения, можно использовать незащищенные контрольные суммы, такие как CRC .

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

Основное отличие от хеш-списка заключается в том, что за раз можно загружать одну ветвь хеш-дерева, а целостность каждой ветки может быть проверена немедленно, даже если все дерево еще не доступно. Например, на картинке целостность блока данных L2 может быть проверена немедленно, если дерево уже содержит хэш 0-0 и хэш 1, путем хеширования блока данных и итеративного объединения результата с хешем 0-0, а затем с хешем 1 и, наконец, сравнивая результат с верхним хешем . Точно так же целостность блока данных L3 может быть проверена, если у дерева уже есть хэш 1-1 и хэш 0.. Это может быть преимуществом, поскольку эффективно разбивать файлы на очень маленькие блоки данных, чтобы повторно загружать только небольшие блоки, если они будут повреждены. Если хешированный файл очень большой, такое хеш-дерево или хеш-список становится довольно большим. Но если это дерево, можно быстро загрузить одну небольшую ветвь, можно проверить целостность ветки, а затем можно начать загрузку блоков данных. [ необходима цитата ]

Вторая атака на прообраз [ править ]

Корень хэша Меркла не указывает глубину дерева, что позволяет использовать атаку второго прообраза, при которой злоумышленник создает документ, отличный от оригинала, имеющий тот же корень хеш-функции Меркла. В приведенном выше примере злоумышленник может создать новый документ, содержащий два блока данных, где первый - это хэш 0-0 + хэш 0-1, а второй - хэш 1-0 + хэш 1-1. [12] [13]

Одно простое исправление определено в « Прозрачности сертификата» : при вычислении хэшей конечных узлов к хеш-данным добавляется байт 0x00, а при вычислении хэшей внутренних узлов добавляется байт 0x01. [11] Ограничение размера хеш-дерева является предпосылкой некоторых формальных доказательств безопасности и помогает сделать некоторые доказательства более строгими. Некоторые реализации ограничивают глубину дерева с помощью префиксов глубины хэш-дерева перед хешами, поэтому любая извлеченная цепочка хешей определяется как действительная только в том случае, если префикс уменьшается на каждом шаге и все еще остается положительным при достижении листа.

Хеш тигрового дерева [ править ]

Хеш-дерево Тигра - широко используемая форма хеш-дерева. Он использует двоичное хеш-дерево (два дочерних узла под каждым узлом), обычно имеет размер блока данных 1024 байта и использует хеш-код Tiger . [14]

Тигровые дерево хэшей используются в Gnutella , [15] Gnutella2 и Direct Connect P2P протоколы обмена файлами [16] и в общий доступ к файлам приложений , таких как PHex , [17] BearShare , LimeWire , Shareaza , DC ++ [18] и Valknut . [19]

Пример [ править ]

Base32 :R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN :urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

магнит :magnet:?xt=urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

См. Также [ править ]

  • Двоичное дерево
  • Блокчейн (база данных)
  • Распределенная хеш-таблица
  • Хеш-таблица
  • Хэш-три
  • Связанная отметка времени
  • Основное дерево

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

  1. ^ Беккер, Георг (2008-07-18). «Схемы подписи Меркла, деревья Меркла и их криптоанализ» (PDF) . Ruhr-Universität Bochum. п. 16 . Проверено 20 ноября 2013 .
  2. Перейти ↑ Merkle, RC (1988). «Цифровая подпись, основанная на обычной функции шифрования». Достижения в криптологии - CRYPTO '87 . Конспект лекций по информатике. 293 . С. 369–378. DOI : 10.1007 / 3-540-48184-2_32 . ISBN 978-3-540-18796-7.
  3. ^ Патент США 4309569 , Меркл, «Способ предоставления цифровых подписей», опубликованной 5 января 1982, назначен Совет попечителей Леланд Стэнфорд Младший университета 
  4. ^ Бонвик, Джефф. «Сквозная целостность данных ZFS» . Блог Джеффа Бонвика .
  5. ^ Likai Лю. «Сопротивление Bitrot на одном диске» . likai.org .
  6. ^ "Общая проверяемая федерация" . Протокол Google Wave . Архивировано из оригинала на 2018-04-08 . Проверено 9 марта 2017 .
  7. ^ Коблиц, Нил; Менезес, Альфред Дж. (Январь 2016 г.). «Криптовалюта, криптовалюты и криптоконтракты». Конструкции, коды и криптография . 78 (1): 87–102. CiteSeerX 10.1.1.701.8721 . DOI : 10.1007 / s10623-015-0148-5 . S2CID 16594958 .  
  8. ^ Адам Маркус. «Экосистема NoSQL» . aosabook.org .Когда реплика не работает в течение длительного периода времени или машина, хранящая подсказки для передачи обслуживания недоступной реплики, также выходит из строя, реплики должны синхронизироваться друг с другом. В этом случае Кассандра и Риак реализуют вдохновленный Динамо процесс, называемый антиэнтропией. В антиэнтропии реплики обмениваются деревьями Меркла, чтобы идентифицировать части их реплицированных диапазонов ключей, которые не синхронизированы. Дерево Меркла - это иерархическая проверка хэшей: если хеш-значения по всему пространству ключей не одинаковы между двумя репликами, они будут обмениваться хэшами все меньших и меньших частей реплицированного пространства ключей, пока не будут идентифицированы несинхронизированные ключи. Такой подход сокращает ненужную передачу данных между репликами, которые содержат в основном похожие данные.
  9. Перейти ↑ Kilian, J. (1995). «Улучшенные дельные аргументы (предварительная версия)» (PDF) . КРИПТО . DOI : 10.1007 / 3-540-44750-4_25 .
  10. ^ Марк Фриденбах: Быстрые деревья Меркла
  11. ^ а б Лори, B .; Langley, A .; Каспер, Э. (июнь 2013 г.). «Прозрачность сертификата» . IETF : RFC6962. DOI : 10.17487 / rfc6962 .
  12. ^ Елена Андреева; Шарль Буйяге; Орр Дункельман; Джон Келси (январь 2009 г.). «Хердинг, второй прообраз и атаки троянских сообщений за пределами Меркла-Дамгарда». Избранные области криптографии . Конспект лекций по информатике. 5867 . SAC. С. 393–414. DOI : 10.1007 / 978-3-642-05445-7_25 . ISBN 978-3-642-05443-3.
  13. ^ Елена Андреева; Шарль Буйяге; Пьер-Ален Фук; Джонатан Дж. Хох; Джон Келси; Ади Шамир; Себастьян Циммер (2008). «Атаки второго прообраза на сглаженные хеш-функции». В Смарт, Найджел (ред.). Достижения в криптологии - EUROCRYPT 2008 . Конспект лекций по информатике. 4965 . Стамбул, Турция. С. 270–288. DOI : 10.1007 / 978-3-540-78967-3_16 . ISBN 978-3-540-78966-6.
  14. ^ Chapweske, J .; Мор, Г. (4 марта 2003 г.). «Формат Tree Hash EXchange (THEX)» . Архивировано из оригинала на 2009-08-03.
  15. ^ «Ссылка на файл tigertree.c» . Gtk-Gnutella . Проверено 23 сентября 2018 года .
  16. ^ «Аудит: приложение P2P DirectConnect» . Symantec . Проверено 23 сентября 2018 года .
  17. ↑ Arne Babenhauserheide (7 января 2007 г.). «Выпущен Phex 3.0.0» . Phex . Проверено 23 сентября 2018 года .
  18. ^ "Список возможностей DC ++" . dcplusplus.sourceforge.net .
  19. ^ «Развитие» . GTK-Gnutella . Проверено 23 сентября 2018 года .

Дальнейшее чтение [ править ]

  • Патент на дерево Меркла 4 309 569  - объясняет как структуру хеш-дерева, так и его использование для обработки множества одноразовых подписей.
  • Формат Tree Hash EXchange (THEX)  - подробное описание деревьев Tiger

Внешние ссылки [ править ]

Послушайте эту статью ( 5 минут )
Разговорный значок Википедии
Этот аудиофайл был создан на основе редакции этой статьи от 17 сентября 2013 г. и не отражает последующих правок. ( 2013-09-17 )
( Аудио справка  · Больше устных статей )
  • Реализация AC динамически изменяемого двоичного хеш-дерева SHA-256 (дерево Меркла)
  • Реализация дерева Меркла в Java
  • Исходный код Tiger Tree Hash (TTH) на C # , автор Gil Schmidt
  • Реализации Tiger Tree Hash (TTH) на C и Java
  • RHash , инструмент командной строки с открытым исходным кодом, который может вычислять TTH и магнитные ссылки с TTH.
  • Реализация Golang: Пакет merkleTree - это общая реализация дерева Меркла, для доказуемой публикации большого количества данных под одним кратким корнем дерева.
  • Другая реализация Golang:
  • Другая реализация Golang: пакет merkle - это фиксированная реализация дерева Меркла.
  • Другая реализация Golang:
  • Другая реализация Golang: пакет merkle вычисляет детерминированный хэш дерева Меркла минимальной высоты
  • Другая реализация Golang: Пакет merkletree предоставляет инструменты для вычисления корня Меркла набора данных, для создания доказательства того, что часть данных находится в дереве Меркла данного корня, и для проверки доказательств того, что часть данных находится в дереве Меркла. данного корня.
  • Реализация встроенного хранилища дерева Меркла в Golang: immudb Встроенный встраиваемый пакет Хранилище значений ключей со встроенным деревом Меркла. Поток обработки внутренних транзакций и криптографическая привязка были специально разработаны для использования модели «ключ-значение».