Послушайте эту статью
Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Merkle Tree )
Перейти к навигации Перейти к поиску
Пример двоичного хеш-дерева. Хеш-значения 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. ^ Ликай Лю. «Сопротивление 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 # , автор - Гил Шмидт
  • Реализации Tiger Tree Hash (TTH) на C и Java
  • RHash , инструмент командной строки с открытым исходным кодом, который может вычислять TTH и магнитные ссылки с TTH.