В криптографии и информатике хэш-дерево или дерево Меркла — это дерево , в котором каждый «листовой» узел помечен криптографическим хешем блока данных, а каждый узел, не являющийся листом (называемый ветвью , внутренним узлом или инодом ), помечен криптографическим хешем меток его дочерних узлов. Хэш-дерево позволяет эффективно и безопасно проверять содержимое большой структуры данных . Хэш-дерево является обобщением хэш-списка и хэш-цепочки .
Демонстрация того, что конечный узел является частью данного бинарного хэш-дерева, требует вычисления количества хешей, пропорционального логарифму количества конечных узлов в дереве. [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]
Одно простое исправление определено в Certificate Transparency : при вычислении хэшей листовых узлов к данным хэша добавляется байт 0x00, а при вычислении хэшей внутренних узлов добавляется байт 0x01. [13] Ограничение размера хэш-дерева является предпосылкой некоторых формальных доказательств безопасности и помогает сделать некоторые доказательства более жесткими. Некоторые реализации ограничивают глубину дерева, используя префиксы глубины хэш-дерева перед хэшами, поэтому любая извлеченная цепочка хэшей определяется как действительная, только если префикс уменьшается на каждом шаге и остается положительным при достижении листа.
Хэш Tiger tree — широко используемая форма хэш-дерева. Он использует бинарное хэш-дерево (два дочерних узла под каждым узлом), обычно имеет размер блока данных 1024 байта и использует хэш Tiger . [16]
Хэши Tiger Tree используются в протоколах обмена файлами Gnutella [17], Gnutella2 и Direct Connect P2P [18], а также в приложениях для обмена файлами , таких как Phex [19] , BearShare , LimeWire , Shareaza , DC++ [20] и gtk-gnutella [21] .
Когда реплика не работает в течение длительного периода времени или машина, хранящая подсказанные передачи для недоступной реплики, также выходит из строя, реплики должны синхронизироваться друг с другом. В этом случае Cassandra и Riak реализуют вдохновленный Dynamo процесс, называемый антиэнтропией. В антиэнтропии реплики обмениваются деревьями Меркла для определения частей своих реплицированных диапазонов ключей, которые не синхронизированы. Дерево Меркла — это иерархическая проверка хеша: если хеш по всему пространству ключей не одинаков между двумя репликами, они будут обмениваться хешами все меньших и меньших частей реплицированного пространства ключей, пока не будут идентифицированы несинхронизированные ключи. Такой подход сокращает ненужную передачу данных между репликами, которые содержат в основном похожие данные.
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )