В криптографии и информатике хеш -дерево или дерево Меркла — это дерево , в котором каждый «лист» ( узел ) помечен криптографическим хешем блока данных, а каждый узел, не являющийся листом (называемый ветвью , внутренний узел или inode ) помечен криптографическим хешем меток его дочерних узлов. Хэш-дерево позволяет эффективно и безопасно проверять содержимое большой структуры данных . Хэш-дерево — это обобщение хэш -списка и хэш-цепочки .
Чтобы продемонстрировать, что листовой узел является частью данного двоичного хэш-дерева, необходимо вычислить количество хэшей, пропорциональное логарифму количества конечных узлов в дереве. [1] И наоборот, в хэш-списке число пропорционально количеству самих конечных узлов. Таким образом, дерево Меркла является эффективным примером схемы криптографических обязательств , в которой корень дерева рассматривается как обязательство, а конечные узлы могут быть обнаружены и признаны частью исходного обязательства. [2]
Концепция хеш-дерева названа в честь Ральфа Меркла , который запатентовал ее в 1979 году. [3] [4]
Хэш-деревья можно использовать для проверки любых данных, хранящихся, обрабатываемых и передаваемых между компьютерами. Они могут помочь гарантировать, что блоки данных , полученные от других узлов в одноранговой сети, будут получены неповрежденными и неизмененными, и даже проверить, что другие узлы не лгут и не отправляют поддельные блоки.
Хэш-деревья используются в
Были сделаны предложения использовать хэш-деревья в доверенных вычислительных системах. [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]
Когда реплика не работает в течение длительного периода времени или машина, хранящая подсказки для недоступной реплики, также выходит из строя, реплики должны синхронизироваться друг с другом. В этом случае Кассандра и Риак реализуют процесс, вдохновленный Dynamo, называемый антиэнтропией. В антиэнтропии реплики обмениваются деревьями Меркла, чтобы идентифицировать части своих реплицируемых диапазонов ключей, которые не синхронизированы. Дерево Меркла представляет собой иерархическую проверку хэша: если хэш по всему пространству ключей не одинаков между двумя репликами, они будут обмениваться хэшами все меньших и меньших частей реплицированного пространства ключей до тех пор, пока не будут идентифицированы несинхронизированные ключи. Этот подход уменьшает ненужную передачу данных между репликами, которые содержат в основном схожие данные.
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )