TTH

TTH — это один из «китов», на которых держатся файлообменные сети Direct Connect. У каждого файла, передаваемого в этих сетях, должен быть вычислен TTH. TTH используется, чтобы убедиться в целостности передаваемых файлов. TTH используется, чтобы находить источники файла.

TTH выглядит, например, так:

MZCKRVQ4DQM5WHCVDLCU5RQMTY222VESIO3WJLQ

TTH зависит только от содержимого файла. Не важно, называется ли файл «Человек–паук.avi» или «Чиловек поук.avi». Если у них одинаковое содержимое, будут одинаковыми и TTH. В контекстном меню каждого файла в GreyLink есть пункт «Поиск альтернатив», запускающий поиск по TTH. Вы можете использовать поиск альтернатив, чтобы узнать, у кого ещё в сети есть такой же файл и как он называется у других пользователей.

TTH — это сокращение от Tiger Tree Hash, специальный код (хеш), обладающий следующими свойствами:

Файлы с одинаковым содержимым обязательно имеют одинаковые TTH.
Файлы с разным содержимым, очень вероятно¹, имеют разные TTH.
Несмотря на то, что для любого TTH существует бесконечное количество файлов, имеющих такой же TTH, подобрать замену (коллизию) очень сложно.
В отличие от обычных необратимых криптографических функций (дайджестов), TTH вычисляется в несколько этапов, что позволяет проверять целостность файла по частям², а не полностью.
В отличие от некоторых других аналогичных хешей, таких, как BTIH в протоколе BitTorrent и ed2k в протоколе eDonkey2000, TTH вычисляется не в один, а в несколько этапов, что позволяет варьировать размер проверяемого блока, не изменяя основной хеш.
В основе TTH лежит криптографическая функция TIGER, которая вычисляется быстрее своих аналогов (SHA1, MD5).

Всё это делает TTH лучшим хешем для файлообменых протоколов и кандидатом номер один при выборе хеша для других операций с файлами, например, синхронизации файлов или распределённого хранилища.

Технические подробности

Пример TTH для 0б

LWPNACQDBZRYXW3VHJVCJ64QBZNGHOHHHZWCLNQ

Вычисления TTH

Сначала данные делим на блоки не более 1024 байта на блок. Далее к каждому получившемуся блоку спереди добавляется байт 00 — это так называемый Leaf Tiger Hash. Затем для каждой пары хешей вычисляется так называемый Internal Tiger Hash — это хеш от пары хешей Internal Tiger Hash или Leaf Tiger Hash с добавлением в начале байта 01. После хеширования всех пар получается один хеш, который называется Tiger Tree Root, и который является хешем всего дерева. Именно его используют для однозначной идентификации файла и указывают в различных P2P ссылках.

Схема хеширования

деление на блоки по 1024 байта
получение Leaf Tiger Hash (LTH) — это Tiger Hash от блока данных с добавленным в начале байтом 00 (Байт 00 & Блок данных)
получение Internal Tiger Hash (ITH) — это Tiger Hash от двух других Tiger Hash (Internal Tiger Hash или Leaf Tiger Hash) с добавленным в начале байтом 01 (Байт 01 & Hash1 & Hash2)
получение Tiger Tree Root (TTR) — это хеш всего дерева или единственный оставшийся хеш, полученный из пары уровнем ниже.

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

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

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

Поиск ($Search)

На данный момент в DC клиентах за поиск по TTH отвечает девятый тип поиска. Строка поиска девятого типа обязательно должна содержать TTH:[base32_encoded_tth_hash]

Результаты поиска ($SR)

Когда клиенту известен корневой хеш файла, клиент в команде $SR не должен отсылать имя хаба. Вместо имени хаба должен стоять TTH:[base32_encoded_tth_hash]. См. описание команды $SR.

См. также

^ «Очень вероятно» и «очень сложно», грубо говоря, имеют оценку сложности взлома или случайного совпадения (коллизии), сопоставимую с временем жизни и количеством атомов в нашей галактике.
^ Одного лишь ТТH недостаточно. Чтобы это было возможно, файлообменные клиенты хранят промежуточные результаты вычисления TTH, а структура вычислений TTH позволяет убедиться в их подлинности.

Тэги:

G+

Код для вставки: