Открыть список
Как стать автором
Обновить

Комментарии 16

Честно говоря ничего не понял. Ну присвоили мы узлам какие-то id-хеши, а что дальше? Нам же надо получить их ip адреса, допустим скачали мы таблицу маршрутизации с bs ноды и нашли там нужный хеш, взяли оттуда ip, это просто, а если этого узла ещё нет в списке, что делать? Ну вычислим мы «расстояние», а как оно поможет нам узнать его ip?
Не случайно длина хеша документа совпадает с длиной ID ноды.

На пальцах. Пусть мой ID — ab12, я публикую документ 871e.

Для публикации я опрашиваю топ 10 известных пиров, с адресом, ближайшим к 871e.
Например, у меня в списке пир 8022, я его спрашиваю — кого ты знаешь максимально близкого к 871e? Он отвечает — это пир 87a0. Я отправляю пиру 87a0 инфмацию что у меня, у ab12, есть документ 871e.

Аналогично пиру ab15 (как и всем из топ-10 наиболее близких к моему ab12), я отправляю свой IP/порт.

Если кто-то ищет документ 871e, он спрашивает у топ-10 пиров, с адресом, наиболее близким к 871e, какие есть пиры, с ID, ещё ближе расположенным к 871e. Например, пир 5611 скажет, что ближе — 77a1, а 77a1 — скажет, что 87a0 (процес движения к хешу по пирам повторяется N итераций, обычно N=3 достаточно).

Дальше, пир 87a0 отвечает этому клиенту, что документ 871e есть у пира ab12. Он запускает аналогичный поиск, но уже не хешу, а по ID пира. Так он натыкается либо сразу на ab12, либо на «соседа» ab15, который сообщит IP-адрес пира ab12.
Благодарю, это уже понятнее.

> Например, у меня в списке пир 8022, я его спрашиваю — кого ты знаешь максимально близкого к 871e? Он отвечает — это пир 87a0. Я отправляю пиру 87a0 инфмацию что у меня, у ab12, есть документ 871e.

а как определяется что пора прекратить искать ближайший к 871e и уже передать информацию о документе?
Пир 87a0 должен сказать что более близких нет?
87a0 может отдать 2 списка:

1) список известных ему пиров, наиболее близких к искомому ID

2) список известных пиров-владельцов файла с искомым хешем (посколько он хранит файлы, наиболее близкие к его ID, у него и имеет смысл спрашивать владельцев этих файлов)

Причём, 87a0 знает, что владелец файла — ab12, но не хранит его IP, т.к. факт владения — долгосрочная информация, а текущий IP — краткосрочная. Пира ab12 нужно искать по его соседям, у них наиболее достоверная инфа по IP, т.к. они друг друга периодически пингуют.

Клиент, осуществляющий поиск, сам решает, остановить поиск, или двигаться дальше в направлении к искомому хешу.
Пиры периодически пингуют своих соседей-пиров, расположенных в k-бакетах. Если пингуемый пир не отвечает, он удаляется из бакета, освобождая место для другого живого пира.
Клиент, осуществляющий поиск, сам решает, остановить поиск, или двигаться дальше в направлении к искомому хешу.
Обычно глубина поиска ограничена некоторой константой.

Итерация 1 — опрашиваем пиров из своих k-buckets с ID, ближайшим к искомому хешу. При этом, возможно, мы уже получим владельцев искомого файла. Остаётся только соединиться с ними и запросить файл.

Итерация i+1 — опрашиваем пиров с ID, полученными от ответов итерации i, но не опрошенных ранее

Выполняем S раз (S — константа глубины поиска)
а как определяется что пора прекратить искать ближайший к 871e и уже передать информацию о документе?
Ступил, вопрос по публикации, а я продолжаю про поиск )))
Публикация и поиск — симметричные процессы. Поэтому всё вышеописанное к публикации тоже относится.
Не понял что вы имеете ввиду под присвоили узлам хеши и скачали таблицу маршрутизации.
Хеш или свой идентификатор вы сами себе выбираете случайно ну или не случайно. Скачать можно список узлов — это просто список структур типа ip адрес + udp порт + хеш.
Подобный список можно получить зная адрес и порт подключенного к сети узла.
Собственно как ниже и расписали процесс поиска это по сути два параллельных процесса — ищем новые узлы которые ближе искомому хешу опрашивая уже известные узлы и добавляя их ответы в список опроса и выполняем запрос ресурса на узлах которые достаточно близко к искомому хешу(tolerance zone).

Если узел знает о ресурсе который мы ищем — он выдаст в ответ список источников если ищем файл и список файлов с их именами и хешами если ищем ключевое слово. Вероятность того что узел знает о ключевом слове или файле тем выше чем ближе его собственный хеш к хешу файла или ключевого слова — потому что публикация это тоже самое что и поиск.

Расстояние важно для первой части процесса поиска или публикации — именно оно дает нам возможность двигаться в правильном направлении выбирая нужные ноды и отсекая лишнее.

Например всем кто в опросном списке рассылаем Kad2Req, a тем кто еще и достаточно близко к искомому хешу дополнительно Kad2SearchKeysReq.
в торрентах это MD5
В торрентах SHA1.
Спасибо за уточнение, действительно SHA1.
А кто-нибудь может рассказать об отравлении DHT?
Типа берем намеренно себе хэш, который максимально близок к хэшу некоторого контента, потом под видом того, что мы знаем где контент хранится выдавать неверные хэши тем, кто за контентом к нам придет?
На каждой итерации поиска запрос рассылается N нодам, максимально близким к хешу.

Для StrongDC++ значение N=50.

Как минимум, надо держать 50 фальшивых нод, но клиенты случайно могут выйти на нефальшивые, достаточно близкие к искомому хешу, но не совсем близкие к искомому хешу.

Конечно, на одном IP можно держать хоть 10000 нод на разных портах, если написать соответствующий софт.

Однако, это заблочит только один хеш. Мой опыт файлообмена говорит о том, что у крупных релизов бывает по 10-15 альтернатив для фильмов с разными хешами (разные рипы, разные вложены файлы), 3-8 альтернатив для игр. Так что, если один хеш плохо качается, в сети появится другой.
На одном IP не получится держать много нод, ну как минимум без ухищрений. Была идея поднять в облаке супер ноду как-раз с кучей кад клиентов каждый на своем порту — но облом, узел идентифицируется по IP — если порт не совпадает то узел апдейтится, а не добавляется. Конечно можно хеши выбрать сильно разные и теоретически пересечения не произойдет.
Интересно, я изучал DHT в DC++, там тоже заявлен алгоритм Kademlia. Но есть небольшие различия вроде вышеупомянутого (в dc клиент определяется по ip/port), а также там превосходно реализована защита от фильтрации протокола DPI-системами (все пакеты шифруются).

Но зато там нет поиска по словам, только по хешам файлов.
По ссылке «Хороший реверс Кадемлии» pdf в котором в конце рассматривается вариант отравления сети KAD.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.