Дерево Меркла
В криптографии и информатике или хеш-дерево дерево Меркла — это дерево , в котором каждый «листовой» узел помечен криптографическим хешем блока данных, а каждый узел, не являющийся листом (называемый ветвью , внутренним узлом или inode ) помечен криптографическим хешем меток его дочерних узлов. Хэш-дерево позволяет эффективно и безопасно проверять содержимое большой структуры данных . Хэш-дерево — это обобщение хэш-списка и хэш-цепочки .
Чтобы продемонстрировать, что листовой узел является частью данного двоичного хэш-дерева, необходимо вычислить количество хэшей, пропорциональное логарифму количества конечных узлов в дереве. [ 1 ] И наоборот, в хеш-списке число пропорционально количеству самих конечных узлов. Таким образом, дерево Меркла является эффективным примером схемы криптографических обязательств , в которой корень дерева рассматривается как обязательство, а конечные узлы могут быть выявлены и признаны частью исходного обязательства. [ 2 ]
Концепция хеш-дерева названа в честь Ральфа Меркла , который запатентовал ее в 1979 году. [ 3 ] [ 4 ]
Использование
[ редактировать ]Хэш-деревья можно использовать для проверки любых данных, хранящихся, обрабатываемых и передаваемых между компьютерами. Они могут помочь гарантировать, что блоки данных , полученные от других узлов в одноранговой сети, будут получены неповрежденными и неизмененными, и даже проверить, что другие узлы не лгут и не отправляют поддельные блоки.
Хэш-деревья используются в:
- криптография на основе хеша .
- Межпланетная файловая система (IPFS),
- БитТоррент
- Btrfs и ZFS. Файловые системы [ 5 ] (для противодействия ухудшению качества данных [ 6 ] );
- Этот протокол;
- протокол Apache Wave ; [ 7 ]
- Git и Mercurial распределенные системы контроля версий (хотя, строго говоря, они используют ориентированные ациклические графы , а не деревья);
- резервная система Tahoe -LAFS ;
- Зеронет ;
- Bitcoin Ethereum и ; одноранговые сети [ 8 ]
- система прозрачности сертификатов ;
- менеджер пакетов Nix и его потомки, такие как GNU Guix ; [ 9 ]
- ряд систем NoSQL, таких как Apache Cassandra , Riak и Dynamo . [ 10 ]
Были сделаны предложения использовать хэш-деревья в доверенных вычислительных системах. [ 11 ]
Первоначальная реализация деревьев Меркла в Биткойне Сатоши Накамото применяет этап сжатия хэш-функции в чрезмерной степени, что смягчается за счет использования быстрых деревьев Меркла. [ 12 ]
Обзор
[ редактировать ]Хэш-дерево — это дерево хешей , в котором листья (т. е. листовые узлы, иногда также называемые «листами») представляют собой хэши блоков данных , например, в файле или наборе файлов. Узлы, расположенные выше в дереве, представляют собой хэши соответствующих дочерних элементов. Например, на изображении выше хэш 0 является результатом хеширования конкатенации хеша 0-0 и хеша 0-1 . То есть хэш 0 = хэш ( хеш 0-0 + хеш 0-1 ), где «+» обозначает конкатенацию.
Большинство реализаций хэш-дерева являются двоичными (два дочерних узла в каждом узле), но они с таким же успехом могут использовать гораздо больше дочерних узлов в каждом узле.
Обычно криптографическая хеш-функция, такая как SHA-2 для хеширования используется . Если хеш-дереву необходимо защитить только от непреднамеренного повреждения, незащищенные контрольные суммы, такие как CRC можно использовать .
В верхней части хеш-дерева находится верхний хеш (или корневой хэш , или главный хэш ). Перед загрузкой файла в сети P2P в большинстве случаев верхний хэш получается из надежного источника, например, от друга или веб-сайта, который, как известно, имеет хорошие рекомендации по файлам для загрузки. Когда доступен верхний хеш, хэш-дерево можно получить из любого недоверенного источника, например, от любого узла в сети P2P. Затем полученное хеш-дерево сверяется с доверенным верхним хешем, и если хеш-дерево повреждено или поддельно, будет проверено другое хэш-дерево из другого источника, пока программа не найдет то, которое соответствует верхнему хешу. [ 13 ]
Основное отличие от хэш-списка заключается в том, что за раз можно загрузить одну ветвь хэш-дерева и сразу же проверить целостность каждой ветки, даже если все дерево еще не доступно. Например, на рисунке целостность блока данных L2 можно проверить сразу, если дерево уже содержит хэш 0-0 и хэш 1, хешируя блок данных и итеративно объединяя результат с хешем 0-0 , затем хэшем 1 и, наконец, сравнение результата с верхним хешем . Аналогично, целостность блока данных L3 можно проверить, если дерево уже имеет хэш 1-1 и хеш 0 . Это может быть преимуществом, поскольку эффективно разбивать файлы на очень маленькие блоки данных, так что в случае повреждения необходимо повторно загружать только небольшие блоки. Если хешированный файл большой, такой хэш-список или хэш-цепочка становится довольно большим. Но если это дерево, то можно быстро загрузить одну небольшую ветку, проверить целостность ветки и затем начать загрузку блоков данных. [ нужна ссылка ]
Вторая атака прообраза
[ редактировать ]Корень хеша Меркла не указывает глубину дерева, что позволяет провести атаку второго прообраза , при которой злоумышленник создает документ, отличный от оригинала, который имеет тот же корень хэша Меркла. В приведенном выше примере злоумышленник может создать новый документ, содержащий два блока данных, где первый — это хеш 0-0 + хеш 0-1 , а второй — хеш 1-0 + хэш 1-1 . [ 14 ] [ 15 ]
Одно простое исправление определено в «Прозрачности сертификатов» : при вычислении хэшей конечных узлов к хеш-данным добавляется байт 0x00, а при вычислении внутренних хешей узлов добавляется байт 0x00. [ 13 ] Ограничение размера хеш-дерева является обязательным условием некоторых формальных доказательств безопасности и помогает сделать некоторые доказательства более надежными. Некоторые реализации ограничивают глубину дерева, используя префиксы глубины хеш-дерева перед хэшами, поэтому любая извлеченная хэш-цепочка определяется как действительная только в том случае, если префикс уменьшается на каждом шаге и остается положительным при достижении листа.
Хэш тигрового дерева
[ редактировать ]Хэш тигрового дерева — широко используемая форма хеш-дерева. Он использует двоичное хэш-дерево (два дочерних узла под каждым узлом), обычно имеет размер блока данных 1024 байта и использует хэш Tiger . [ 16 ]
используются хеши тигрового дерева В Gnutella , [ 17 ] Gnutella2 и Direct Connect P2P. Протоколы обмена файлами [ 18 ] и в приложениях для обмена файлами, таких как Phex , [ 19 ] BearShare , LimeWire , Shareaza , DC++ [ 20 ] и gtk-gnutella . [ 21 ]
См. также
[ редактировать ]
- Бинарное дерево
- Блокчейн
- Распределенная хеш-таблица
- Хэш-таблица
- Хэш-три
- Связанная временная метка
- Радикс-дерево
Ссылки
[ редактировать ]- ^ Беккер, Георг (18 июля 2008 г.). «Схемы подписей Меркла, деревья Меркла и их криптоанализ» (PDF) . Рурский университет в Бохуме. п. 16. Архивировано из оригинала (PDF) 22 декабря 2014 г. Проверено 20 ноября 2013 г.
- ^ «Справочник по прикладной криптографии» . cacr.uwaterloo.ca . Раздел 13.4.1 . Проверено 7 марта 2024 г.
- ^ Меркл, Р.К. (1988). «Цифровая подпись, основанная на традиционной функции шифрования». Достижения в криптологии – КРИПТО '87 . Конспекты лекций по информатике. Том. 293. стр. 369–378. дои : 10.1007/3-540-48184-2_32 . ISBN 978-3-540-18796-7 .
- ^ Патент США 4309569 , Ральф Меркл, «Метод предоставления цифровых подписей», опубликован 5 января 1982 г., передан Попечительскому совету Стэнфордского младшего университета Леланда.
- ^ Бонвик, Джефф (08 декабря 2005 г.). «Сквозная целостность данных ZFS» . blogs.oracle.com . Архивировано из оригинала 3 апреля 2012 года . Проверено 19 сентября 2013 г.
- ^ Ликай Лю. «Сопротивление Битрота на одном приводе» . likai.org .
- ^ «Общая проверяемая федерация» . Протокол Google Wave . Архивировано из оригинала 08 апреля 2018 г. Проверено 9 марта 2017 г.
- ^ Коблиц, Нил; Менезес, Альфред Дж. (январь 2016 г.). «Криптовалюта, криптовалюты и криптоконтракты». Проекты, коды и криптография . 78 (1): 87–102. CiteSeerX 10.1.1.701.8721 . дои : 10.1007/s10623-015-0148-5 . S2CID 16594958 .
- ^ Долстра, Э. Чисто функциональная модель развертывания программного обеспечения. Кандидатская диссертация, Факультет естественных наук, Утрехт, Нидерланды. Январь 2006. стр. 21. ISBN 90-393-4130-3 .
- ^ Адам Маркус. «Экосистема NoSQL» . aosabook.org .
Когда реплика не работает в течение длительного периода времени или машина, хранящая подсказки для недоступной реплики, также выходит из строя, реплики должны синхронизироваться друг с другом. В этом случае Кассандра и Риак реализуют процесс, вдохновленный Dynamo, называемый антиэнтропией. В антиэнтропии реплики обмениваются деревьями Меркла, чтобы идентифицировать части своих реплицируемых диапазонов ключей, которые не синхронизированы. Дерево Меркла представляет собой иерархическую проверку хеша: если хэш по всему пространству ключей не одинаков между двумя репликами, они будут обмениваться хэшами все меньших и меньших частей реплицированного пространства ключей до тех пор, пока не будут идентифицированы несинхронизированные ключи. Этот подход уменьшает ненужную передачу данных между репликами, которые содержат в основном схожие данные.
- ^ Килиан, Дж. (1995). «Улучшенные эффективные аргументы (предварительная версия)» (PDF) . КРИПТО . дои : 10.1007/3-540-44750-4_25 .
- ^ Марк Фриденбах: Быстрые деревья Меркла
- ^ Перейти обратно: а б Лори, Б.; Лэнгли, А.; Каспер, Э. (июнь 2013 г.). «Прозрачность сертификата» . IETF : RFC6962. дои : 10.17487/rfc6962 .
- ^ Елена Андреева; Шарль Буйаге; Орр Данкельман; Джон Келси (январь 2009 г.). «Атака стада, второго прообраза и троянских сообщений за пределами Меркле-Дамгорда». Избранные области криптографии . Конспекты лекций по информатике. Том. 5867. САК. стр. 393–414. дои : 10.1007/978-3-642-05445-7_25 . ISBN 978-3-642-05443-3 .
- ^ Елена Андреева; Шарль Буйаге; Пьер-Ален Фуке; Джонатан Дж. Хох; Джон Келси; Ади Шамир; Себастьян Циммер (2008). «Вторые атаки прообразов на сглаживаемые хеш-функции». В Смарт, Найджел (ред.). Достижения в криптологии – EUROCRYPT 2008 . Конспекты лекций по информатике. Том. 4965. Стамбул, Турция. стр. 270–288. дои : 10.1007/978-3-540-78967-3_16 . ISBN 978-3-540-78966-6 . S2CID 12844017 .
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) - ^ Чапвеске, Дж.; Мор, Г. (4 марта 2003 г.). «Формат Tree Hash EXchange (THEX)» . Архивировано из оригинала 3 августа 2009 г.
- ^ «Ссылка на файл Tigertree.c» . Гтк-Гнутелла . Проверено 23 сентября 2018 г.
- ^ «Аудит: приложение P2P DirectConnect» . Симантек . Архивировано из оригинала 29 января 2015 года . Проверено 23 сентября 2018 г.
- ^ Арне Бабенхаузерхайде (7 января 2007 г.). «Выпущен Phex 3.0.0» . Фекс . Проверено 23 сентября 2018 г.
- ^ «Список функций DC++» . dcplusplus.sourceforge.net .
- ^ "Разработка" . ГТК-Гнутелла . Проверено 23 сентября 2018 г.
Дальнейшее чтение
[ редактировать ]- Патент на дерево Меркла 4 309 569 - объясняет как структуру хеш-дерева, так и его использование для обработки множества одноразовых подписей.
- Формат Tree Hash EXchange (THEX) — подробное описание тигровых деревьев.
Внешние ссылки
[ редактировать ]
- AC-реализация двоичного хэш-дерева SHA-256 с динамически изменяемым размером (дерево Меркла)
- Реализация дерева Меркла в Java
- Исходный код Tiger Tree Hash (TTH) на C# , автор Гил Шмидт
- Реализации Tiger Tree Hash (TTH) на C и Java
- RHash , инструмент командной строки с открытым исходным кодом, который может рассчитывать TTH и магнитные ссылки с помощью TTH.
