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

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

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 выпуска (384) 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. магнитные ссылки на папки, но это менее надёжный метод по сравнению с метафайлами.
5. накладывает ограничения, не позволяющие, например, проверять файл размером 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.