TTH

TTH (Tiger Tree Hashing) — тип хэш-кода. Используется для того, чтобы проверять целостность данных (файлов), получить уникальный идентификатор файла, а также дает возможность восстановить файл. Впервые TTH появился в DC++ 0.400.

Пример

RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Вычисление

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Данные делятся на маленькие части "Блоки", которые индивидуально хешируются при помощи Leaf Tiger Hash, затем из каждой пары хешей поочерёдно вычисляется Internal Tiger Hash. Если хешу нет пары, то он переносится в новую цепочку без изменений. Далее в цепочке для каждой пары снова вычисляется Internal Tiger Hash. Эта процедура повторяется до тех пор, пока не останется один хеш. Этот единственный оставшийся Internal Tiger Hash называют Tiger Tree Root. Именно его используют для однозначной идентификации файла и указывают в различных P2P ссылках.

Level           Tiger Tree Root
|                   /
0:            --- 21 -- -------\            
             /         \        \
1:       - 20 -         19 ------\
        /      \         \        \
2:    17        18        19 ------ Internal Tiger Hashes
     /  \      /  \      /  \     /   
3:  12   13   14   15   16  11 --/
    /\   /\   /\   /\   /\   \
4: 1  2 3  4 5  6 7  8 9 10  11 ---  Leaf Tiger Hashes

Блок данных

Часть данных размером 1024 байта или меньше, если данных не хватает на полное заполнение блока.

Leaf Tiger Hash

Leaf Tiger Hash (LTH) - Это Tiger Hash от блока данных с добавленным в начале байтом 00h.

LTH = Tiger Hash (Байт 00h + Блок данных)

+ Конкатенация

Internal Tiger Hash

Internal Tiger Hash (ITH) - Это Tiger Hash от двух других Tiger Hash (Internal Tiger Hash или Leaf Tiger Hash) с добавленным в начале байтом 01h.

ITH = Tiger Hash (Байт 01h + Hash1 + Hash2)

Hash1 и Hash2 это Leaf Tiger Hash или Internal Tiger Hash

+ Конкатенация

Представление

Результат вычисления хеш-функции TTH обычно выводится в представлении Base32. Количество символов в строке равно 39.

Tiger Tree Root

Tiger Tree Root (TTR) — хеш всего дерева или единственный оставшийся хеш полученный из пары уровнем ниже.

Вычисление количества хешей на уровне

Количество хешей на уровне можно посчитать циклически от нижнего до верхнего уровня.

1. Количество хешей самого нижнего уровня = Округлить до большего целого (Количество байт данных / 1024)
2. Количество хешей выше = Округлить до большего целого (Количество хешей ниже / 2)
3. Повторить пункт 2 для нового уровня пока не будет найдено количество хешей нужного уровня.

Применение

TTH используется в DC++, Gnutella2 клиентах для идентификации, поиска источников и проверки целостности файла.

При помощи Tiger Tree Root (TTR) можно проверить только полный файл, поэтому в p2p сетях имеется возможность по TTR получить несколько уровней хешей ниже главного TTR в формате Breadth-First (Gnutella, G2), либо набор хешей самого нижнего доступного уровня (Direct Connect). Это позволяет проверять части файла независимо от того, имеются ли остальные.

Breadth-First

Это формат в котором Tiger хеши (TTR, ITH, LTH) записываются в RAW виде. Запись хешей идет от TTR опускаясь к LTH. Каждый уровень записывается слева направо. Непарный хеш пишется в каждом уровне, который он проскочил.

Используется в P2P сетях: Gnutella, G2

Direct Connect

В этой сети передаётся набор хешей самого нижнего доступного уровня в RAW-виде. По этому набору воссоздается дерево и полученный TTR сравнивается с исходным (полученным из поиска либо по магнет-ссылке). В случае если TTR совпадает то полученный набор хешей принимается для проверки частей файла.

Хранение вместе с файлом в NTFS

Клиент GreyLink (исходный код закрыт, веб сайт не имеет стационарного хостинга) c 2007 года для файлов больше 16 МБ в файловой системе NTFS может хранить дерево TTH вместе с файлом (используя альтернативный поток)^[1]. Это позволяет не вычислять хеш заново при перемещении файла, переименовании (в пределах NTFS тома) и повторном добавлении в шару. Также это позволяет перепроверить целостность файла и при необходимости восстановить его найдя в [p2p] сети его исходные копии. Формат записи в потоке был открыт разработчиками GreyLink и добавлен разработчиками других клиентов в свои проекты, например в p2p клиент FlyLinkDC++ начиная c выпуска (r384) 15.5.2009 ( ^[2] )

Имя альтернативного потока: ".gltth"
Заголовок (C++):^[3]

           struct TTHStreamHeader
           {
              uint32_t magic; // = '++lg'
              uint32_t checksum;  // xor of other TTHStreamHeader DWORDs
              uint64_t fileSize;
              uint64_t timeStamp;
              uint64_t blockSize;
              TTHValue root;
           };

Далее следует RAW набор TTH хешей блоков размером blockSize.

Сравнение с BitTorrent Info Hash

В отличие от Info Hash торрент файла:

1. TTH зависит только от данных файла и не меняется при переименовании/перемещении файла.
2. TTH может быть только для одного файла. ^[4]
3. TTH не зависит от размера проверяемого блока. Direct Connect, Gnutella2, а также другие потенциальные программы, использующие TTH, вольны варьировать уровень дерева, на котором пересылаются промежуточные хеши. Таким образом, можно получать набор хешей разного размера. Минимальный размер блока данных, который при этом можно проверить, является степенью двойки, но не меньше, чем 1024 байта. ^[5]

Примечания

1. ↑ .greylink - эксклюзивные возможности клиента
2. ↑ ru:history [FlylinkDC++]
3. ↑ http://flylinkdc.googlecode.com/svn/trunk/client/HashManager.h
4. ↑ Но этим файлом может быть архив либо другой вид объединения файлов. В GreyLink DC++ поддерживаются метафайлы. Начиная с версии 0.39, поддержка метафайлов близка к совершенству: если создавать магнитные ссылки на метафайлы, greylink добавляет в них дополнительный атрибут dl=, позволяющий отобразить в чате или на форуме размер директории, описываемой метафайлом (например, 6Гб) вместо размера метафайла (например, 1Кб). Рекурсивные метафайлы виртуально содержат себя внутри директории, ими описываемой, что позволяет перераспространять метафайлы вместе с директориями. Это важно, так как при использовании магнитной ссылки на метафайл сам метафайл должен присутствовать в сети. Кроме того, во многих клиентах поддерживаются магнитные ссылки на папки, но это менее надёжный метод по сравнению с метафайлами.
5. ↑ Например, в изображённом на рисунке примере набор хешей (17, 18, 19) позволяет проверять целостность данных с точностью до блоков размером 4096 байт. Direct Connect накладывает ограничения, не позволяющие, например, проверять файл размером 4Гб блоками размером по 1Гб: A base segment size of 1024 bytes must be used when generating the tree, but clients may then discard parts of the tree as long as at least 7 levels are kept or a block granularity of 64 KiB is achieved.

См. также

• Tiger (хэш-функция)
• Magnet-ссылка
• URN

Ссылки

• Tree Hash EXchange format (THEX)  (англ.)
• TTHSum — Консольная утилита, позволяющая быстро вычислить TTH.
• RHash — Консольная утилита, вычисляющая TTH (и другие хэши) и создающая магнитные ссылки.
• EAD TorrentBuild — Генератор торрентов, позволяющий создавать .torrent файлы, богатые дополнительными хешами. Поддерживаются хеши CRC32, MD5, ED2K, TTH, SHA1.
• Tiger Tree Torrent - Предложение по замене sha1 на Tiger Tree Hash в .torrent файлах.

Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным.