Дерево Меркла - Merkle tree

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

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

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

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

Использует

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

Деревья хеширования используются в криптография на основе хешей. Хеш-деревья также используются в IPFS, Btrfs и ZFS файловые системы[4] (чтобы противостоять деградация данных[5]); Дата протокол; Apache Wave протокол;[6] Git и Mercurial распределенные системы контроля версий; то Тахо-ЛАФС система резервного копирования; Zeronet; то Биткойн и Ethereum одноранговые сети;[7] то Сертификат прозрачности фреймворк; и ряд NoSQL такие системы как Apache Cassandra, Риак, и Динамо.[8]Были сделаны предложения использовать хеш-деревья в доверенные вычисления системы.[9]

Первоначальная реализация деревьев Меркла в биткойнах Сатоши Накамото применяет шаг сжатия хеш-функции в чрезмерной степени, что смягчается использованием Fast Merkle Trees.[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 байты и использует Тигровый хэш.[14]

Хэши тигрового дерева используются в Гнутелла,[15] Gnutella2, и Прямое соединение P2P протоколы обмена файлами[16] И в обмен файлами такие приложения, как Phex,[17] BearShare, LimeWire, Shareaza, DC ++[18] и Валкнут.[19]

пример

Base32: R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN: урна: дерево: тигр: R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

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

Смотрите также

Рекомендации

  1. ^ Беккер, Георг (18 июля 2008 г.). «Схемы подписи Меркла, деревья Меркла и их криптоанализ» (PDF). Ruhr-Universität Bochum. п. 16. Получено 2013-11-20.
  2. ^ Меркл, Р. К. (1988). «Цифровая подпись, основанная на обычной функции шифрования». Достижения в криптологии - CRYPTO '87. Конспект лекций по информатике. 293. С. 369–378. Дои: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. Получено 2017-03-09.
  7. ^ Коблиц, Нил; Менезес, Альфред Дж. (Январь 2016 г.). «Криптовалюта, криптовалюты и криптоконтракты». Конструкции, коды и криптография. 78 (1): 87–102. CiteSeerX  10.1.1.701.8721. Дои:10.1007 / s10623-015-0148-5. S2CID  16594958.
  8. ^ Адам Маркус. «Экосистема NoSQL». aosabook.org. Когда реплика не работает в течение длительного периода времени или машина, хранящая подсказки для передачи обслуживания недоступной реплики, также выходит из строя, реплики должны синхронизироваться друг с другом. В этом случае Кассандра и Риак реализуют вдохновленный Динамо процесс, называемый антиэнтропией. В антиэнтропии реплики обмениваются деревьями Меркла, чтобы идентифицировать части их реплицированных диапазонов ключей, которые не синхронизированы. Дерево Меркла - это иерархическая проверка хэшей: если хеш-значения по всему пространству ключей не одинаковы между двумя репликами, они будут обмениваться хэшами все меньших и меньших частей реплицированного пространства ключей, пока не будут идентифицированы несинхронизированные ключи. Такой подход сокращает ненужную передачу данных между репликами, которые содержат в основном похожие данные.
  9. ^ Килиан, Дж. (1995). «Улучшенные дельные аргументы (предварительная версия)» (PDF). КРИПТО. Дои:10.1007/3-540-44750-4_25.
  10. ^ Марк Фриденбах: Быстрые деревья Меркла
  11. ^ а б Лори, Б.; Langley, A .; Каспер, Э. (июнь 2013 г.). «Прозрачность сертификата». IETF: RFC6962. Дои:10.17487 / rfc6962.
  12. ^ Елена Андреева; Шарль Буйяге; Орр Дункельман; Джон Келси (январь 2009 г.). «Хердинг, второй прообраз и атаки троянских сообщений за пределами Меркла-Дамгарда». Избранные области криптографии. Конспект лекций по информатике. 5867. SAC. С. 393–414. Дои:10.1007/978-3-642-05445-7_25. ISBN  978-3-642-05443-3.
  13. ^ Елена Андреева; Шарль Буйяге; Пьер-Ален Фук; Джонатан Дж. Хох; Джон Келси; Ади Шамир; Себастьян Циммер (2008). «Атаки второго прообраза на сглаженные хеш-функции». В Смарт, Найджел (ред.). Достижения в криптологии - EUROCRYPT 2008. Конспект лекций по информатике. 4965. Стамбул, Турция. С. 270–288. Дои: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. ^ Арне Бабенхаузерхайде (7 января 2007 г.). «Выпущен Phex 3.0.0». Phex. Получено 23 сентября 2018.
  18. ^ "Список возможностей DC ++". dcplusplus.sourceforge.net.
  19. ^ «Развитие». GTK-Gnutella. Получено 23 сентября 2018.

дальнейшее чтение

внешняя ссылка